come    

 [P. LORENZEN]Ein halbordnungstheoretischer Widerspruchsfreiheitsbeweis.

Die Dissertation von G. Gentzen enthält einen Wf-beweis der reinen Zahlentheorie ohne vollständige Induktion, der auf dem folgenden Grundgedanken beruht: jede herleitbare Sequenz muß sich auch ohne Umwege herleiten lassen, sodaß während der Herleitung nur die Verknüpfungen eingeführt werden, die unbedingt notwendig sind, nämlich diejenigen, die in der Sequenz selbst enthalten sind. In dem Wf-beweis der Zahlentheorie mit vollständiger Induktion tritt dieser Grundgedanke gegenüber anderen zurück. Ich möchte jedoch im folgenden zeigen, daß er allein genügt, auch diese Wf. zu erhalten.

Ohne Kenntnis der Dissertation von Gentzen bin ich auf diese Möglichkeit auf Grund einer halbordnungstheoretischen Frage gekommen. Diese lautete: wie läßt sich eine halbgeordnete Menge in einen orthokomplementären vollständigen Halbverband einbetten? Im allgemeinen sind mehrere solche Einbettungen möglich -unter den möglichen Einbettungen ist aber eine ausgezeichnet, nämlich die, welche sich in jede andere homomorph abbilden läßt. Die Existenz dieser ausgezeichneten Einbettung wird in § 2 bewiesen.

Um hieraus in § 3 den gesuchten Wf-beweis zu erhalten, ist nur noch eine Übersetzung des halbordnungstheoretischen Beweises in die logistische Sprache notwendig. Denn der Kalkül, den wir betrachten und auf den sich die üblichen Kalküle zurückführen lassen, ist in der ausgezeichneten Einbettung der halbgeordneten Menge der zahlentheoretischen Primformeln enthalten. § 1. Eine Menge M heißt halbgeordnet, wenn in M eine zweistellige Relation definiert ist, sodaß für die Elemente a, b, . . . von M gilt: 

M und a ′ , b ′ ∈ M ′ mit a → a ′ und b → b ′ gilt: a ∧ b → a ′ ∧ b ′ a → a ′ Ferner soll für jede Folge M = a 1 , a 2 , . . . in M und M ′ = a ′ 1 , a ′ 2 , . . . in M ′ mit a n → a ′ n gelten: M → M ′
Wir wollen jetzt beweisen, daß es zu jeder halbgeordneten Menge P einen orthokomplementären ω-vollständigen Halbverband K gibt, so daß 1) P ein Teil von K ist,

2) K in jeden orthokomplementären ω-vollständigen Halbverband, der P als Teil enthält, homomorph abbildbar ist.

Wäre K ′ ein weiterer orthokomplementärer ω-vollständiger Halbverband, der die Bedingungen 1) und 2) erfüllt, so gäbe es eine Zuordnung, durch die K in K ′ und K ′ in K homomorph abgebildet würde, d. h. K und K ′ wären isomorph. K ist also durch die Bedingungen 1) und 2) bis auf Isomorphie eindeutig bestimmt. Wir nennen K den ausgezeichneten orthokomplementären ω-vollständigen Halbverband über P. § 2. Satz: Über jeder halbgeordneten Menge gibt es den ausgezeichneten orthokomplementären ω-vollständigen Halbverband.

Wir konstruieren zu der halbgeordneten Menge P eine Menge K auf folgende Weise:

1) K enthalte die Elemente von P. (Diese nennen wir die Primelemente von K)

2) K enthalte mit endlich vielen Elementen a 1 , a 2 , . . . , a n auch die hieraus gebildete Kombination als Element.

(Diese bezeichnen wir durch

a 1 ∧ a 2 ∧ • • • ∧ a n ).
3) K enthalte mit jedem Element a auch ein Element a, 4) K enthalte mit jeder abzählbaren Folge M auch ein Element M Jedes Element von K läßt sich also eindeutig als Kombination

a 1 ∧ a 2 ∧ • • • ∧ a n von Primelementen und Elementen der Form a oder M schreiben.
Wir definieren eine Relation in K auf folgende Weise:

1) Für Primelemente p, q gelte p q in K, wenn p q in P gilt. (Diese Relationen nennen wir die Grundrelationen)

2) Es soll jede Relation in K gelten, die sich aus den Grundrelationen mit Hilfe der folgenden Regeln herleiten läßt:

c a c b a) c a ∧ b a ∧ c b) c a c a 1 , . . . , c a n , . . . c) c M a c d) a ∧ b c a b e) a ∧ b c a n ∧ b c f ) M ∧ b c (M = a 1 , a 2 , . . . ) a ∧ a ∧ b c g) a ∧ b c
Wir nennen die Relationen über dem Strich die Prämissen der Relation unter dem Strich. Wir haben jetzt zunächst zu zeigen, daß K ein orthokomplementärer ω-vollständiger Halbverband bezügl. der Relation ist. Dazu müssen wir beweisen

α) a a β) a b, b c ⇒ a c γ) c a ∧ b ⇒ c a δ) c a ⇒ a ∧ c ε) c M ⇒ c a n (M = a 1 , a 2 , . . . ) Diese Eigenschaften zusammen mit a), b) und c) drücken nämlich aus, daß K ein orthokomplementärer ω-vollständiger Halb- verband ist. α) gilt für Primelemente. Gilt α) für a und b, so auch für a ∧ b wegen a a a ∧ b a b b a ∧ b b a ∧ b a ∧ b Gilt α) für jedes a n ∈ M , so auch für M wegen a 1 a 1 M a 1 • • • a n a n M a n • • • M M
Gilt α) für a, so auch für a, wegen 

c 1 c 2 c 1 ∧ c 2 a ∧ b (c = c 1 ∧ c 2 ) da dann sofort c 1 c 2 c 1 ∧ c 2 a
herleitbar wäre.

Für den letzten Schritt bleiben nur die Möglichkeiten 

c 1 a ∧ b c 1 ∧ c 2 a ∧ b c 1 ∧ c 1 ∧ c 2 a ∧ b (c = c 1 ∧ c 2 ) c 1 ∧ c 2 a ∧ b c 1 ∧ c ′ a ∧ b • • • c n ∧ c ′ a ∧ b • • • M = a 1 , a 2 , . . . c = M ∧ c ′ M ∧ c ′ a ∧ b Hier muß jetzt c 1 a bezw. c 1 ∧ c 1 ∧ c 2 a bezw.
a 1 b a 1 ∧ a 2 b a 1 ∧ a 1 ∧ a 2 b (a = a 1 ∧ a 2 ) a 1 ∧ a 2 b a 1 a 2 (a = a 1 ∧ a 2 ) a 1 ∧ a 2 b a n ∧ a ′ b M = a 1 , a 2 , . . . a = M ∧ a ′ M ∧ a ′ b Nach der Induktionsvoraussetzung ist dann a 1 ∧ c d bezw. a 1 ∧ a 1 ∧ a 2 ∧ c d bezw. a n ∧ a ′ ∧ c d herleitbar. In jedem Falle ist sofort a ∧ c d herleitbar, ebenso aus a 1 a 2 wegen a 1 a 2 a 1 ∧ a 2 d a ∧ c d Damit ist ζ)
M ∧ M ∧ • • • ∧ M ∧ c d kann folgende Prämisse haben: b n ∧ M ∧ • • • ∧ M ∧ c d. Nach Induktionsvoraus- setzung gilt dann a M , b n ∧ M ∧ • • • ∧ M ∧ c d ⇒ b n ∧ a ∧ c d Da ζ) aber auch für b = b n vorausgesetzt ist, und wegen a M ⇒ a b n gilt auch a M , b n ∧ a ∧ c d ⇒ a ∧ a ∧ c d Aus a ∧ a ∧ c d ist aber a ∧ c d herleitbar. Jede andere Prämisse von M ∧ M ∧ • • • ∧ M ∧ c d ist trivial). Gilt ζ) für b, so auch für b. (Beweis durch Prämisseninduk- tion: b ∧ b ∧ • • • ∧ b ∧ c d kann die folgende Prämisse haben: b ∧ • • • ∧ b ∧ c b. Dann gilt nach Induktionsvoraussetzung a b, b ∧ • • • ∧ b ∧ c b ⇒ a ∧ c b Da ζ) auch für b vorausgesetzt ist, gilt auch a ∧ c b, a ∧ b d ⇒ a ∧ a ∧ c d Also gilt auch a b, b ∧ • • • ∧ b ∧ c b ⇒ a ∧ c d wegen a b ⇒ a ∧ b d
Jede andere Prämisse ist wieder trivial.) Also ist ζ) allgemein gültig. Damit ist bewiesen, daß K ein orthokomplementärer ω-vollständiger Halbverband ist. P ist ein Teil von K, da p q in P ⇐⇒ p q in K gilt. Wir haben uns dazu zu überzeugen, daß keine Relation p q in K herleitbar ist, die nicht schon in P gilt. Das ist aber selbstverständlich, da keine der Regeln außer g) überhaupt Relationen p q unter dem Strich liefert. Eine Herleitung einer Relation p q kann also nur die Regeln d) und g) benutzen. Mit diesen sind aber nur die Grundrelationen herleitbar. Zum Beweis unseres Satzes bleibt jetzt noch zu zeigen, daß sich K in jeden anderen orthokomplementären ω-vollständigen Halbverband K ′ , der P als Teil enthält, homomorph abbilden läßt. Diese Abbildung definieren wir durch 1) für Primelemente p gilt p → p, 2) ferner soll gelten Hierdurch werden die Beweise von § 2 nur unwesentlich modifiziert. Wir erhalten insgesamt einen Kalkül N mit den folgenden Schlußregeln 

a → a ′ , b → b ′ ⇒ a ∧ b → a ′ ∧ b ′ a → a ′ ⇒ a → a ′ a n → a ′ n ⇒ M → M ′ M = a 1 , a 2 , . . . M ′ = a ′ 1 , a ′ 2 , . . .
C → A C → B a) C → A & B A & C → b) C → A C → A(1) • • • C → A(n) • • • c) C → (x) A(x) A → C d) A & B → C A → B e) A & B → C A(n) & B → C f ) (x) A(x) & B → C A & A & B → C g) A & B → C A & B → C h) B & A → C A & (B & C) → D i) (A & B) & C → D A(1) • • • A(n) • • • j) A(a) Die Schlußregeln h) und i) waren in § 2 überflüssig,
A → B B → C k) A → C C → A & B l) C → A C → A & B m) C → B C → A n) A & C → C → (x) A(x) o) C → A(n)
Zu den Grundrelationen kann A → A hinzugenommen werden. Dieses Ergebnis aus § 2 können wir jetzt ergänzen:

1) es kann auch die Schlußregel A(a) p) A(n) hinzugenommen werden.

Der Beweis wird wieder durch eine transfinite Prämisseninduktion geführt. Ist A(a) herleitbar in N und ist die letzte Schlußregel dieser Herleitung nicht

A(1) • • • A(n) • • • A(a)
so hat die Prämisse die Form A ′ (a). Nehmen wir als Induktionsvoraussetzung an, daß für jede Prämisse A ′ (a) auch A ′ (n) herleitbar ist, so folgt sofort A(n).

2) Zu den Grundrelationen darf A → A hinzugenommen werden.

Für jede Primformel P gilt nämlich stets → P oder P → 

Wegen

  Gilt a b und b a, so schreiben wir a ≡ b. Gilt a x für jedes x ∈ M, so schreiben wir a . Ebenso schreiben wir a, wenn x a für jedes x gilt. ( bedeutet also, daß x y für jedes x, y ∈ M gilt.) Eine halbgeordnete Menge M heißt Halbverband, wenn es zu jedem a, b ∈ M ein c ∈ M gibt, sodaß für jedes x ∈ M gilt x a, x b ⇐⇒ x c c heißt die Konjunktion von a und b: c ≡ a ∧ b Ein Halbverband M heißt orthokomplementär, wenn es zu jedem a ∈ M ein b ∈ M gibt, so daß für jedes x ∈ M gilt a ∧ x ⇐⇒ x b b heißt das Orthokomplement von a: b ≡ a Ein Halbverband M heißt ω-vollständig, wenn es zu jeder abzählbaren Folge M = a 1 , a 2 , . . . in M ein c ∈ M gibt, so daß für jedes x ∈ M gilt: (für jedes n: x a n ) ⇐⇒ x c c heißt die Konjunktion der Elemente von M : c ≡ n a n ≡ M Sind M und M ′ halbgeordnete Mengen, so heißt M ein Teil von M ′ , wenn M Untermenge von M ′ ist und für jedes a, b ∈ M genau dann a b in M ′ gilt, wenn a b in M gilt. Sind M und M ′ halbgeordnete Mengen, so verstehen wir unter einer Abbildung von M in M ′ eine Zuordnung, die jedem a ∈ M ein a ′ ∈ M ′ zuordnet, so daß gilt a ≡ b ⇒ a ′ ≡ b ′ Sind M und M ′ orthokomplementäre ω-vollständige Halbverbände, so verstehen wir unter einem Homomorphismus von M in M ′ eine Abbildung → von M in M ′ , so daß für jedes a, b ∈

  Dadurch ist α) allgemein bewiesen. Da β) am schwierigsten zu beweisen ist, nehmen wir zunächst γ) Um γ) zu beweisen, haben wir zu zeigen, daß, wenn c a ∧ b herleitbar ist, dann auch stets c a herleitbar sein muß. Wir führen den Beweis indirekt durch eine transfinite Induktion. Es sei c a ∧ b herleitbar, aber nicht c a. Der letzte Schritt der Herleitung von c a ∧ b kann dann nicht sein c a c b c a ∧ b ebenfalls nicht

  für mindestens ein n c n ∧ c ′ a nicht herleitbar sein, da sonst sofort c a herleitbar wäre. In der Herleitung von c a ∧ b wäre also schon für eine Prämisse die Behauptung γ) falsch. Gehe ich in der Herleitung von einer Relation zu einer Prämisse über, von dieser wieder zu einer Prämisse usw., so bin ich nach endlich vielen Schritten bei einer Grundrelation. Wir erhielten also eine Grundrelation, für die die Behauptung γ) falsch wäre. Da dieses aber unmöglich ist, ist damit γ) bewiesen. Wir nennen die Induktion, die wir hier durchgeführt haben, eine Prämisseninduktion. Mit Hilfe von Prämisseninduktionen verläuft der Beweis für δ) und ε) ebenso einfach wie für γ), so daß ich hierauf nicht weiter eingehe.Es bleibt nur noch β) zu zeigen. Statt dessen beweisen wir die stärkere Behauptungζ) a b, b ∧ b ∧ • • • ∧ b ∧ c d ⇒ a ∧ cd um hierauf Prämisseninduktionen anwenden zu können. Es seien zunächst b, c und d Primelemente. Dann gilt ζ) für jede Grundrelation a b. Wir nehmen als Induktionsvoraussetzung an, daß ζ für jede Prämisse von a b gelte. Da b ein Primelement ist, kann der letzte Schritt der Herleitung von a b nur sein:

  bewiesen für Primelemente b, c und d. Jetzt sei nur noch b ein Primelement. Dann gilt also ζ) für beliebiges a und Primelemente c, d. Eine Prämisseninduktion ergibt jetzt, daß ζ) für jede Relation b∧b 1 ∧• • •∧b 1 ∧c d gilt. Jede Prämisse von b ∧ b ∧ • • • ∧ b ∧ c d hat nämlich wieder die Form b ∧ • • • ∧ b ∧ c d. Damit ist ζ) allgemein für Primelemente b bewiesen. Gilt ζ) für Elemente b 1 und b 2 , so auch ersichtlich für b 1 ∧ b 2 . Gilt ζ) für jedes b n ∈ M , so auch für b =

  Dadurch wird ersichtlich ein Homomorphismus definiert, denn es gilt für a → a ′ und b → b ′ stets a b ⇒ a ′ b ′ . Jede Herleitung von a b beweist nämlich sofort auch a ′ b ′ , da die Herleitungsschritte a)g) in jedem orthokomplementären ω-vollständigen Halbverband stets richtig sind. § 3. Um aus dem im § 2 bewiesenen Satz die Widerspruchsfreiheit der reinen Zahlentheorie mit vollständiger Induktion beweisen zu können, benutzen wir die folgende Formalisierung. Als Primformeln nehmen wir die Zeichen für zahlentheoretische Prädikate A(. . . ), B(. . . ), ... mit den Zahlen 1, 1

  ist also für jede Primformel stets P → P herleitbar. Hieraus folgt allgemein die Herleitbarkeit von A → A (vergl. etwa Hilbert -Bernays, Grundlagen der Mathematik II) 3) Es kann auch die vollständige InduktionA(a) → A(a ′ ) q) A(1) → A(b)zu den Schlußregeln hinzugenommen werden ohne die Menge der herleitbaren Relationen zu vergrößern.Ist nämlich A(a) → A(a ′ ) herleitbar, so auch die Relation A(n) → A(n ′ ) für jede Zahl n.Für jede Zahl m folgt daraus durch m-malige Anwendung der Schlußregel k) sofort A(1) → A(m)Wegen A(1) → A(1) • • • A(1) → A(m) • • • A(1) → A(b) ist also auch A(1) → A(b) herleitbar.Damit ist die Wf. der reinen Zahlentheorie bewiesen, da die insgesamt zulässigen Schlußregeln einen Kalkül definieren, der den klassischen Prädikatenkalkül ersichtlich enthält.

  ′′ , . . . als Argumenten, z. B. 1 = 1 ′′ , 1 + 1 = 1 ′ . Diese Primformeln P, Q, . . . bilden eine halbgeordnete Menge, wenn wir P → Q setzen, falls das Prädikat P das Prädikat Q impliziert. Zu den Grundrelationen P → Q nehmen wir auch noch die Relationen der Form → P, P → , → hinzu, soweit sie inhaltlich richtig sind. Über dieser halbgeordneten Menge P der Primformeln konstruieren wir jetzt wie in § 2 den ausgezeichneten orthokomplementären ω-vollständigen Halbverband. Wir benutzen dazu die logistischen Zeichen, also → statt , & statt ∧. Zu den Formeln gehören also die Primformeln, mit A und B auch A & B, mit A auch A. Die Konjunktion abzählbarer Folgen beschränken wir auf die Folgen der Form A(1), A(1 ′ ), . . .

	Diese Konjunktion bezeichnen wir durch (x) A(x)
	Ferner führen wir noch freie Variable a = a, b, ... ein durch
	folgende Schlußregel:
	sind A(1), A(1 ′ ), . . . herleitbare Relationen, so
	soll auch A(a) herleitbar sein.

′ , 1

  da wir dort a ∧ b ∧ c . . . sofort als Zeichen für die Kombination von a, b, c, . . . eingeführt haben. Der Beweis in § 2 liefert jetzt das folgende Ergebnis: Der Kalkül N ist widerspruchsfrei, z. B. ist die leere Relation → nicht herleitbar, da nur die inhaltlich richtigen Relationen in P gelten und P ein Teil von N ist. Zu dem Kalkül N können die folgenden Schlußregeln hinzugenommen werden, ohne daß die Menge der herleitbaren Relationen vergrößert wird: