×

zbMATH — the first resource for mathematics

Der Äquivalenzenkalkül. (Polish) JFM 65.0022.01
Collectanea Logica, Warszawa, 1, 145-169 (1939).
Der erste Band der von J. Łukasiewicz herausgegebenen Collectanea Logica hatte im Herbst 1939 erscheinen sollen. Im Kriege sind alle Exemplare dieses Bandes zugrunde gegangen. Erhalten geblieben sind nur ein paar Sonderdrucke der Arbeiten, die in diesem Bande erscheinen sollte. Ein Inhaltsverzeichnis habe ich nicht erhalten können, nur die Namen der Mitarbeiter. Es sind an diesem Bande beteiligt gewesen neben dem Herausgeber sein Schüler I. M. Bocheński mit einer Abhandlung über die Logik des Theophrast, sodann St. Leśniewski und sein Schüler B. Sobociński, über deren Arbeiten ich berichten werde. Die mir zugewendeten Exemplare gehen über in die Bibliothek des Logistischen Seminars der Universität Münster i. W. Hier können sie eingesehen werden. Wer ein Photogramm zu erhalten wünscht, wolle sich mit mir in Verbindung setzen.
Der vom Verf. betrachtete Äquivalenzenkalkül (\(EK\)) ist das Teilsystem des klassischen zweiwertigen Aussagenkalküls (\(AK\)), das sich aus diesem durch eine Beschränkung der zugelassenen aussageerzeugenden Funktoren auf “\(E\)” (“dann und nur dann wenn”) ergibt. “\(E\)” hat neben den trivialen Eigenschaften der Reflexivität und der Kommutativität auch die nichttriviale, vom Verf. entdeckte Eigenschaft der Assoziativität. Es sind also die folgenden in der klammerfreien Symbolik des Verf. angeschriebenen Ausdrücke Sätze des \(EK\): 1. \(Epp\) (\(p\) dann und nur dann, wenn \(p\)), 2. \(EEpqEqp\) [(\(p\) dann und nur dann, wenn \(q\)) dann und nur dann, wenn (\(q\) dann und nur dann, wenn \(p\))], 3. \(EEpEqrEEpqr\) [\(p\) dann und nur dann, wenn (\(q\) dann und nur dann, wenn \(r\)) dann und nur dann, wenn (\(p\) dann und nur dann, wenn \(q\)) dann und nur dann, wenn \(r\)].
Das erste System des \(EK\) ist 1929 von St. Leśniewski veröffentlicht worden (Fundam. Math., Warszawa, 14 (1929), 1-81; F. d. M. \(55_{\text{II}}\), 626). Es ist ein auf zwei Axiomen fußendes System, für welches von Leśniewski die Postsche Vollständigkeit bewiesen worden ist. Die ersten einzigen Axiome für diesen Kalkül hat M. Wajsberg gefunden (Mh. Math. Physik 39 (1932), 259-262; Wiadom. mat., Warszawa, 43 (1937); 132-133, 163-166; F. d. M. \(58_{\text{I}}\), 64; \(63_{\text{II}}\), 826). Auf zwei schon von Wajsberg gefundenen Axiomen hat E. G. Mihailescu, ohne die Axiome zu kennen, den \(EK\) ein zweites Mal aufgebaut (Ann. Sci. Univ. Jassy I 23 (1937), 106-124; F. d. M. \(63_{\text{I}}\), 24). Die Widerspruchsfreiheit und Unabhängigkeit dieses Axiomensystems ist mit Hilfe der Matrizenmethode, seine Vollständigkeit im Postschen Sinne auf eine originelle Art durch Zurückführung der sinnvollen Ausdrücke auf gewisse Normalformen bewiesen. Auf eine ungewöhnlich interessante Art ist das System von Leśniewski von M. H. Stone vom Standort der Theorie der Booleschen Ringe aus zu einer Theorie des vollständigen klassischen \(AK\) entwickelt worden (Amer. J. Math. 59 (1937), 506-514; F. d. M. \(63_{\text{I}}\), 25).
Die vorliegende Bearbeitung des \(EK\) durch Verf. darf als abschließend gelten aus folgendem Grunde: Es ist dem Verf. gelungen zu zeigen, daß jedes kürzeste einzige Axiom dieses Kalküls in seiner Symbolik aus genau 11 Buchstaben bestehen muß. Der Beweis gelingt so: (1) Es wird ein aus genau 11 Buchstaben bestehendes Axiom “\(EEpqEErqEpr\)” angegeben, für welches die Widerspruchsfreiheit und die Postsche Vollständigkeit bewiesen wird. (2) Durch eine vollständige Diskussion der möglichen Fälle wird mit Hilfe der Matrizenmethode gezeigt, daß es ein aus weniger als 11 Buchstaben bestehendes einziges widerspruchsfreies Axiom für den \(EK\) mit dieser Vollständigkeitseigenschaft nicht geben kann. Diese Diskussion fußt auf den folgenden beiden Eigenschaften der sinnvollen Ausdrücke in der Symbolik des Verf.: a) Die Anzahl der in einem solchen Ausdruck vorkommenden “\(E\)” muß um eins kleiner sein als die Anzahl der kleinen Buchstaben, b) in jedem Abschnitt, der an einer beliebigen Stelle des Ausdrucks beginnt und bis zum Ende des Ausdrucks reicht, muß die Anzahl der “\(E\)” kleiner sein als die Anzahl der kleinen Buchstaben.
Verf. hat noch zwei andere kürzeste einzige Axiome gefunden: “\(EEpqEEprErq\)” und “\(EEpqEErpEqr\)”. – Es ist das erstemal, daß für einen Kalkül gezeigt worden ist, daß es für diesen Kalkül kürzeste einzige Axiome gibt.
Der Beweis für die Postsche Vollständigkeit wird durch eine Betrachtung der möglichen Ausdrucksstrukturen so durchgeführt, daß zugleich ein allgemeines Verfahren gewonnen wird, durch dessen Anwendung für einen beliebigen Ausdruck effektiv entschieden werden kann, ob er ein Satz ist oder von der Art, daß durch seine Hinzufügung zu dem einzigen Axiom jeder Ausguck ableitbar wird, wobei die Ableitbarkeit eines Ausdrucks aus einer Axiomenmenge auf der üblichen Einsetzungs- und einer Abtrennungsregel fußt, die besagt, daß, wenn \(E\alpha\beta\) und \(\alpha\) Sätze sind, auch \(\beta\) ein Satz ist. Natürlich ist jedes Axiom ein Satz.
Für den Vollständigkeitsbeweis genügt es zu zeigen, daß jeder Ausdruck \(\alpha\) deduktionsgleich ist mit einem Ausdruck von der Form \(\pi\) oder von der Form \(E\pi \pi\), wo \(\pi\) eine Aussagenvariable ist. Ist nämlich \(\alpha\) länger als \(E\pi \pi\) und kommt \(\pi_1\) in \(\alpha\) vor, so ist (auf Grund der Kommutativität und Assoziativität von \(E\)) \(\alpha\) deduktionsgleich mit einem Ausdruck von der Form \(E\pi_1 \alpha_1\) (wo \(\pi_1\) in \(\alpha_1\) nicht vorkommt) bzw. \(EE\pi_1 \pi_1 \alpha_2\) (wo \(\pi_1\) in \(\alpha_2\) vorkommen kann), je nachdem ob \(\pi_1\) in \(\alpha\) genau einmal oder mehr als einmal vorkommt. Im ersten Falle ist \(\alpha\) deduktionsgleich mit \(\pi_1\) im zweiten mit \(\alpha_2\). Die deduktionsgleiche Reduktion von \(\alpha\) auf \(\pi\) bzw. \(E\pi \pi\) erfolgt auf Grund von sechs Hilfssätzen.
Die Widerspruchsfreiheit wird gleichfalls durch eine strukturelle Betrachtung bewiesen, mit Hilfe der zuerst von St. Leśniewski bemerkten Tatsache, daß die Sätze des \(EK\) mit den Ausdrücken zusammenfallen, in denen jede in ihnen vorkommende Aussagenvariable eine gerade Anzahl von Malen vorkommt.
Abschließend wird folgender Satz betrachtet: “\(EEsEppEEsEppEEpqEErqEpr\)”. Dieser Satz hat die merkwürdige Eigenschaft der Unabtrennbarkeit: Was aus ihm abgeleitet werden kann, kann nur durch Einsetzungen abgeleitet werden. Dieser Satz kann also nicht eine ausreichende Axiomatisierung des \(EK\) sein. Fügt man jedoch zu diesem Satz nach der Methode der axiomatisierten Definitionen (vgl. Hilbert, Bernays, Grundlagen der Mathematik I (1934; F. d. M. \(60_{\text{I}}\), 17), S. 292) das “Verum von \(p\)” (“\(Vp\)”) definitorisch ein durch das zusätzliche Axiom “\(EVpEpp\)”, so wird der betrachtete Satz auf Grund dieser Definition zu einem ausreichenden einzigen Axiom des \(EK\). Verf. nennt solche Definitionen mit Recht schöpferisch und empfiehlt auf eine überzeugende Art, daß sie nicht zugelassen werden sollten.
Die Darstellung ist in jeder Zeile von der meisterhaften kristallinischen Klarheit, durch die alle Arbeiten der Warschauer Schule ausgezeichnet sind. Der Gehalt der vorliegenden Arbeit geht auf Untersuchungen aus dem Jahre 1933 zurück.