Logik - Christian · PDF fileVorlesung aus dem Wintersemester 11/12 Logik Prof. Dr. Hans-Dieter Donder geTEXtvonChrisIttner Inhaltsverzeichnis 0 Aussagenlogik2 1

Vorlesung aus dem Wintersemester 11/12

LogikProf. Dr. Hans-Dieter Donder

geTEXt von Chris Ittner

Inhaltsverzeichnis

0 Aussagenlogik 2

1 Prädikatenlogik erster Stufe 3

2 Termmodelle, Kompaktheitssatz 16

3 Kalküle, Gödelscher Vollständigkeitssatz 26

4 Rekursive Funktionen 36

5 Unentscheidbarkeit, Unvollständigkeit 44

6 Der zweite Gödelsche Unvollständigkeitssatz 55

7 Axiomatische Mengenlehre 58

0 Aussagenlogik

18.10.2011

0 AussagenlogikDefinition. Die Sprache der Aussagenlogik besteht aus

(a) einer unendlichen Menge von Aussagenvariablen tpn | n P Nu

(b) den logischen Junktoren , _

(c) den beiden Hilfszeichen p und q

Mithilfe dieses Alphabets kann man Zeichenreihen bilden.

Beispiel. pq , pp_ qq

Definition. Die Menge der aussagenlogischen Formeln wird rekursiv definiert durch:

(A) Ist p eine Aussagenvariable, so ist p eine aussagenlogische Formel

(B) Sind ϕ, ψ aussagenlogische Formeln so sind auch ϕ und pϕ _ ψq aussagenlogischeFormeln.

Form �Menge aller aussagenlogischen Formeln. Damit ist die Syntax der Sprache festgelegt.

Definition. Eine AbbildungW : Menge aller AussagenvariablenÑ tw, fu heißt eine Wahr-heitsbelegung. Ist W eine Wahrheitsbelegung, so definieren wir rekursivW � : FormÑ tw, fu durch

(1) ist p eine Aussagenvariable, so W �ppq �W ppq

(2) W �p ϕq �

"w falls W �pϕq � ff falls W �pϕq � w

(3) W �pϕ_ ψq �

"w falls W �pϕq � w oder W �pψq � wf sonst

also: ϕ ist die Negation von ϕ und pϕ_ ψq ist die Disjunktion von ϕ,ψ.

Bemerkung. Ist W eine Wahrheitsbelegung, so hängt W �pϕq nur von den Werten W pϕqfür die in ϕ vorkommenden Aussagenvariablen ab, d.h. es gilt:SeienW1,W2 Wahrheitsbelegungen, ϕ ist eine aussagenlogische Formel und V die (endliche)Menge der in ϕ vorkommenden Variablen. Dann gilt:

ist W1 æV �W2 æV, so ist W �1 pϕq �W �

2 pϕq

Definition. Eine aussagenlogische Formel ϕ ist allgemeingültig, wenn W �pϕq � w für alleWahrheitsbelegungen W (Tautologie). Ob ϕ allgemeingültig ist, ist (nach obiger Bemer-kung) effektiv entscheidbar, da wir nur W �pϕq für endlich viele W ausrechnen müssen.

2

1 Prädikatenlogik erster Stufe

Frage. Warum genügen und _? Andere Operatoren lassen sich durch diese ausdrücken,z.b. die Konjunktion: pϕ^ ψq � p ϕ_ ψq Allgemeiner gilt:

Satz. Sei n P N. Sei Mn � tg | g : tp0, . . . , pnu Ñ tw, fuu. Sei F : Mn Ñ tw, fu. Dann exis-tiert eine aussagenlogische Formel ϕ, in der höchstens die Variablen p0, . . . , pn vorkommen,und für die gilt:

@ Wahrheitsbelegungen W : W �pϕq � F pW ætp0, . . . , pnuq

1 Prädikatenlogik erster StufeWir betrachten math. Strukturen.

Beispiel. pR, �, �loomoonFkt.

, loomoonRel.

, 0, 1loomoonKonst.

q @x@y@z : px� yq � z � x� py � zq

20.10.2011

Definition. Eine Sprache erster Stufe L besteht aus

(a) einer abzählbar unendlichen Menge V ar an (Individuen-)Variablen tvn | n P Nu

(b) den logischen Zeichen �, ,_, D

(c) den drei Hilfszeichen p, ,, q

(d) einer Menge FunknL von n-stelligen Funktionszeichen für alle n ¥ 1

(e) einer Menge RelnL von n-stelligen Relationszeichen für alle n ¥ 1

(f) einer Menge KonstL von (Individuen-)Konstanten.

Natürlich sollen die jeweiligen Bestandteile paarweise disjunkt sein.Setze noch FunkL �

�n¥1 Funk

nL, RelL �

�n¥1Rel

nL.

Konvention. Die Elemente von (a)-(c) sollen unabhängig von L sein. Die Elemente von(d)-(f) sind die nichtlogischen Zeichen von L.

Definition. Sei L eine Sprache erster Stufe. Die Menge der L-Terme wird rekursiv definiertdurch:

(T1) Jede Variable oder Konstante aus L ist ein L-Term

(T2) Sind t1, . . . , tn L-Terme und f ein n-stelliges Funktionszeichen von L, so ist fpt1, . . . , tnqein L-Term.

Beispiel. L habe ein zweistelliges Funktionszeichen f , ein einstelliges Funktionszeichen g,eine Konstante c. Seien etwa x,y Variablen.

fpgpgpcqq, fpgpxq, yqq ist ein Termfpg, cq ist kein Term

3


Notation. TermL � Menge aller L-TermeEin Term ist konstant, wenn keine Variablen in ihm vorkommen.

Definition. Sei L eine Sprache erster Stufe. Die Menge der L-Formeln wird rekursiv defi-niert durch:

(F1) Sind t1,t2 L-Terme, so ist t1 � t2 eine L-Formel

(F2) Sind t1, . . . , tn L-Terme undR ein n-stelliges Relationszeichen von L, so istRpt1, . . . , tnqeine L-Formel

(F3) Ist ϕ eine L-Formel, so auch ϕ

(F4) Sind ϕ,ψ L-Formeln, so auch pϕ_ ψq

(F5) Ist ϕ eine L-Formel und x eine Variable, so ist Dx ϕ eine L-Formel.

Notation. FormL � Menge aller L-Formeln

Beispiel. Sei L wie eben, sei R ein zweistelliges Relationszeichen

pDx fpgpcq, xq � gpyq _Rpc, gpxqqq

Definition. L-Formeln, die nur mit (F1),(F2) gebildet sind heißen atomar. ϕ ist die Negation von ϕ. pϕ_ ψq ist die Disjunktion von ϕ,ψ. D ist der Existenzquantor.

Konvention.pϕ^ ψq :� p ϕ_ ψqpϕÑ ψq :� p ϕ_ ψqpϕØ ψq :� ppϕÑ ψq ^ pψ Ñ ϕqq@x ϕ :� Dx ϕt1 � t2 :� t1 � t2

Bemerkung. aus ökonomischen Gründen kommen ^,Ñ,Ø,@,� nicht offiziell in der Spra-che vor. Ausserdem lassen wir meist einige Klammern weg (sofern dies die Bedeutung derFormel nicht beeinflusst): z.b. schreibe ϕ_ ψ für pϕ_ ψq.

Definition. Sei ϕ L-Formel. Eine Variable x komme in ϕ an einer festen Stelle vor. Dannist dieses Vorkommen gebunden, falls diese Stelle in einer Teilformel von ϕ Auftritt, die dieGestalt Dx ψ hat. Andernfalls ist das Vorkommen frei.

Beispiel. Seien x, y verschiedene Variablen.

Dx fp xloomoongeb.

q � yloomoonfrei

_ yloomoonfrei

� gp xloomoonfrei

q

Dx pfp xloomoongeb.

q � yloomoonfrei

_ yloomoonfrei

� gp xloomoongeb.

qq

4


Definition. Sei t ein L-Term und sein ~x � x1, . . . , xm eine Folge von paarweise verschie-denen Variablen. Weiterhin seien s1, . . . , sm L-Terme. Dann ist t~xps1, . . . , smq eine Zeichen-reihe, die aus t entsteht indem man in t überall xi durch si ersetzt.

Bemerkung. t~xps1, . . . , smq ist ein L-Term.

Beispiel. Sei t gleich gpx, hpx, yqq, s1 gleich a und s2 gleich fpzq. Dann ist tx,yps1, s2q gleichgpa, hpa, fpzqqq.

25.10.2011

Definition. Sei ϕ eine L-Formel, ~x � x1, . . . , xm Folge von paarweise verschiedenen Varia-blen und s1, . . . , sm L-Terme. Es gelte:

(sub) Sei 1 ¤ i ¤ m, sei y eine Variable, die in si vorkommt. Dann existiert keine TeilformelDy ψ von ϕ mit: xi kommt in ψ so vor, dass dieses Vorkommen in ϕ frei ist.

Dann ist ϕ~xps1, . . . , smq die Zeichenkette, die aus ϕ entsteht, indem man für 1 ¤ i ¤ m xian jeder Stelle, an der xi frei vorkommt, xi durch si ersetzt. Ist (sub) nicht erfüllt, so seiϕ~xps1, . . . , smq gleich ϕ. Die Bedingung (sub) hat semantische Gründe.

Bemerkung. ϕ~xps1, . . . , smq ist eine L-Formel. Beweis: Übung!

Beispiel. Sei ϕ gleich Dx fpxq � gpyq_Rpx, yq. Sei s1 gleich hpz1, z2q, s2 gleich z1, x, y, z1, z2paarweise verschieden. Dann ist ϕx,yps1, s2q gleich

Dx fpxq � gpz1q _Rphpz1, z2q, z1q

Definition. Sei L eine Sprache erster Stufe.

• Eine L-Struktur ist ein Tupel

A � pA, pfAqfPFunkL, pRAqRPRelL , pc

AqcPKonstLq

mit den Eigenschaften:(a) A ist nichtleere Menge(b) falls f P FunknL, so ist fA eine n-stellige Funktion auf A, d.h. fA : An Ñ A

(c) falls R P RelnL, so ist RA eine n-stellige Relation auf A, d.h. RA � An

(d) falls c P KonstL, so ist cA P AA ist der Träger von A. Ist A wie oben, so schreibe oft a P A statt a P A.

• In L-Strukturen können wir L-Formeln auf natürliche Weise interpretieren.Sei A L-Struktur.Wir definieren zuerst für jeden L-Term t in dem höchstens die paar-weise verschiedenen Variablen ~x � x1, . . . , xm vorkommen, für a1, . . . , am P A einElement tA~x ra1, . . . , ams P A rekursiv wie folgt:(L1) (a) Ist t gleich c mit c P KonstL, so setze tA~x ra1, . . . , ams � cA

5


(b) Ist t gleich z mit z P V arL, etwa z gleich xi, so ist tA~x ra1, . . . , ams � ai

(L2) ist t gleich fpt1, . . . , tnq mit f P FunknL, so ist

tA~x ra1, . . . , ams � fAptA1,~xra1, . . . , ams, . . . , tAn,~xra1, . . . , amsq

für m � 0 setze tAH gleich tA

Beispiel. Sei t gleich fpgpx, yq, xq mit x verschieden von y. Dann ist für a, b P A tAx,yra, bs

gleich fApgApa, bq, aq.

Definition. Hiermit definieren wir die Gültigkeitsrelation A |ù ϕ~xra1, . . . , ams (sprich: “inA gilt ϕ von ~x für a1, . . . , am“) für L-Formel ϕ, ~x � x1, . . . , xm Folge von paarweise ver-schiedenen Variablen, a1, . . . , am P A, höchstens die Variablen x1, . . . , xm kommen frei in ϕvor, rekursiv wie folgt:

(G1) Ist ϕ gleich t1 � t2 mit t1, t2 L-Terme, so A |ù ϕ~xra1, . . . , ams genau dann wenntA1,~xra1, . . . , ams � tA2,~xra1, . . . , ams

(G2) Ist ϕ gleich Rpt1, . . . , tnq, so

A |ù ϕ~xra1, . . . , amsAptA1,~xra1, . . . , ams, . . . , t

An,~xra1, . . . , amsq

(G3) Ist ϕ gleich ψ, so A |ù ϕ~xra1, . . . , ams ðñ nicht A |ù ψ~xra1, . . . , ams

(G4) Ist ϕ gleich (ψ _ θq, so A |ù ϕ~xra1, . . . , ams ðñ pA |ù ψ~xra1, . . . , ams oder A |ùθ~xra1, . . . , amsq

(G5) Ist ϕ gleich Dz ψ1. Fall z gleich xi für ein 1 ¤ i ¤ m. Dann A |ù ϕ~xra1, . . . , ams ðñ es existiert

b P A mit A |ù ψ~xra1, . . . , ai�1, b, ai�1, . . . , ams

2. Fall z verschieden von xi für alle 1 ¤ i ¤ m. Dann A |ù ϕ~xra1, . . . , ams ðñ esexistiert b P A mit A |ù ψz,~xrb, a1, . . . , ams

Für m � 0 schreibe A |ù ϕ statt A |ù ϕH

Bemerkung. Im folgenden sei L immer eine Sprache erster Stufe

Definition. Sei ϕ eine L-Formel. ϕ ist eine L-Aussage, wenn in ϕ keine Variable frei vor-kommt.

27.10.2011

Lemma 1. Sei A eine L-Struktur.

(a) Seien A |ù pϕ^ ψq ðñ A |ù ϕ und A |ù ψ

(b) Sei ϕ eine L-Formel, in der höchstens die Variable x frei vorkommt.

6


Dann: A |ù @x ϕ ðñ für alle a P A : A |ù ϕxras

Lemma 2. Sei A eine L-Struktur. Sei t ein L-Term, in dem höchstens die paarweiseverschiedenen Variablen x1, . . . , xm vorkommen. Seien s1, . . . , sm L-Terme und setze t �t~xps1, . . . , smq. Es gelte, dass in t nur die paarweise verschiedenen Variablen ~z � z1, . . . , zkvorkommen. Seien a1, . . . , ak P A und setze bi � sAi,~zra1, . . . , aks für i � 1, . . . ,m, falls xi int vorkommt, bi P A beliebig sonst. Dann gilt

tA~z ra1, . . . , aks � tA~x rb1, . . . , bms

Beweis. Durch Induktion über den Aufbau von t.

1. Fall t ist gleich c mit c Konstante. Dann ist einfach t gleich t und tA~x ra1, . . . , aks � cA �tA~x rb1, . . . , bms

2. Fall t ist gleich u mit u Variable. Dann ist u gleich xi für 1 ¤ i ¤ m. Also ist t gleich si.Somit tA~x ra1, . . . , aks � sAi,~zra1, . . . , aks � bi � tA~x rb1, . . . , bms

3. Fall t ist gleich fpt1, . . . , tnq mit f n-stelliges Funktionszeichen, t1, . . . , tn L-Terme. Dannist t gleich fpt1, . . . , tnq mit ti � ti,~xps1, . . . , snq. Also

tA~z ra1, . . . , aks � fApt

A1,~zra1, . . . , aks, . . . , t

An,~zra1, . . . , aksq

�Ind.�V or.

fAptA1,~xrb1, . . . , bms, . . . , tAn,~xrb1, . . . , bmsq � tAn,~xrb1, . . . , bms

.

Lemma 3. Sei A eine L-Struktur. Ist ϕ eine Formel, in der höchstens die paarweise ver-schiedenen Variablen ~x � x1, . . . , xm vorkommen. Weiterhin seien s1, . . . , sm L-Terme. Fürϕ, ~x, s1, . . . , sm sei die Bedingung (sub) aus der Definition der Substitution erfüllt. Setzeϕ � ϕ~xps1, . . . , smq. Es gelte, dass in ϕ höchstens die Variablen ~z � z1, . . . , zk vorkommen.Seien a1, . . . , ak P A und setze bi � sAi,~zra1, . . . , aks, falls xi in ϕ frei vorkommt, bi P Abeliebig sonst. Dann gilt

A |ù ϕ~zra1, . . . , aks ðñ A |ù ϕ~xrb1, . . . , bms

Beweis. durch Induktion über den Aufbau von ϕ

1. Fall ϕ gleich t1 � t2 mit t1, t2 L-Terme. Dann ist ϕ gleich t1,~xps1, . . . , smq � t2,~xps1, . . . , smq.Setze ti � ti,~xps1, . . . , smq für i � 1, 2. Nach Lemma 2 ist dann t

Ai,~zra1, . . . , aks �

tAi,~xrb1, . . . , bms. Also:

A |ù ϕ~zra1, . . . , aks ðñ tA1,~zra1, . . . , aks � t

A2,~zra1, . . . , aks

ðñ tA1,~xrb1, . . . , bms � tA2,~xrb1, . . . , bms

ðñ A |ù ϕ~xrb1, . . . , bms

7


2. Fall ϕ gleich Rpt1, . . . , tnq mit R n-stelliges Relationszeichen, t1, . . . , tn L-Terme. Vorge-hen analog zu 1. Fall

3. Fall ϕ gleich ψ. Dann:

A |ù ϕ~zra1, . . . , aks ðñ non A |ù ψ~zra1, . . . , aks ðñInd.V or.

non A |ù ψ~xrb1, . . . , bms


4. Fall ϕ gleich pϕ_ ψq analog zum 3. Fall

5. Fall ϕ gleich Dy ψ. Wir können ohne Einschränkung annehmen, dass ~x genau aus denVariablen besteht, die in ϕ vorkommen und ~z genau aus den Variablen besteht, diein ϕ frei vorkommen. Dann ist y verschieden von allen xi. Wegen (sub) ist außerdemy verschieden von allen zj . Setze man ψ� � ψy,~xpy, s1, . . . , smq. Für 1 ¤ i ¤ m undjedes b P A ist sAi,~zra1, . . . , aks � sAi,y,~zra1, . . . , aks. Also

A |ù ϕ~zra1, . . . , aks ðñ es existiert b P A mit A |ù ψAy,~zrb, a1, . . . , aks

ðñ es existiert b P A mit A |ù ψy,~xrb, b1, . . . , bms


Ind. Vor. Lemma 3 ist der Grund für die Bedingung (sub).

Beispiel. Sei ϕ die Formel Dx fpxq � y wobei x, y verschiedene Variablen. ϕ besagt, also “y ist im Bild von f“. Substituiert man hier y durch x, so entsteht die Aussage Dx fpxq � x,welche besagt “f hat Fixpunkt“, die nichts mit ϕ zu tun hat.

Konvention. Seien L, L Sprachen erster Stufe. Dann bedeutet L � L, dass FunknL�

FunknL, RelnL � RelnL (für alle n ¥ 1) und KonstL � KonstL. Ist allgemein L � L, soTermL � TermL, FormL � FormL.

03.11.2011

Definition. Seien L, L Sprachen erster Stufe mit L � L. Sei

A � pA, pfAqfPFunkL, pRAqRPRelL , pc

AqcPKonstLq

eine L-Struktur. Setze:

A � pA, pfAqfPFunkL, pRAqRPRel

L, pcAqcPKonst

Lq

Dann ist A eine L-Struktur. A heißt das L-Redukt von A. A heißt L-Expansion von A.

Notation. A � A æ L.

Beispiel. Sei K � K,�, �, 0, 1 ¡ ein Körper. Dann ist K � K,�, 0 ¡ ein Redukt von K.

8


Lemma 4. Seien L, L Sprachen erster Stufe mit L � L. Sei A eine L-Struktur. Dannexistiert eine L-Expansion von A.

Beweis. Sei A �Träger von A. Nun ist A � H. Also können wir die c P KonstL �KonstLirgendwie interpretieren. Der Rest ist klar.

Lemma 5. Seien L, L Sprachen erster Stufe, L � L. Seien ϕ eine L-Formel, A eineL-Struktur, a1, . . . , am P A Dann gilt:

A |ù ϕ~xra1, . . . , ams ðñ A æ L |ù ϕ~xra1, . . . , ams

Beweis. einfache Induktion über den Formelaufbau

Definition. Eine Menge von L-Aussagen ist eine (L-)Theorie erster Stufe. Sei T eine L-Theorie erster Stufe. Eine L-Struktur A ist ein Modell von T (Bezeichnung: A |ù T ), fallsA |ù ϕ für alle ϕ P T .

Bemerkung. Um eine Sprache erster Stufe anzugeben geben wir nur die nichtlogischenZeichen an.

Beispiel. (a) Gruppentheorie L � t � u (mit � ist stets �px, yq gemeint)

ϕ1 : @x @y @z px � yq � z � x � py � zq

ϕ2 : De p@x px � e � x^ e � x � xq ^ @x Dy px � y � e^ y � x � eqq

T � tϕ1, ϕ2u. Die Modelle von T sind genau die Gruppen.

(b) Theorie der R-Vektorräume L � t�, pfaqaPRu (fa einstelliges Funktionszeichen). fasoll die Skalarmultiplikation mit a bezeichnen. Schreibe die Axiome hin, z.B.

@x fapfbpxqq � fabpxq für alle a, b P R

Definition. Sei T eine L-Theorie erster Stufe und ϕ eine L-Aussage.

(a) ϕ folgt aus T ðñ A |ù ϕ für jedes Modell A von T .

Notation. T |ù ϕ für “ϕ folgt aus T“.

(b) ϕ ist allgemeingültig ðñ H |ù ϕ. Schreibe auch |ù ϕ statt H |ù ϕ.

(c) T ist erfüllbar ðñ es existiert ein Modell von T .

Ist T � tψu, so schreibe auch ψ |ù ϕ statt tψu |ù ϕ.

Bemerkung. Wegen Lemma 4, 5 hängt die Beziehung T |ù ϕ nicht von L ab.

Beispiel. Dx x � x ist allgemeingültig.

9


Lemma 6. Seien T L-Theorie erster Stufe, ϕ eine L-Aussage. Dann:

T |ù ϕ ðñ T Y t ϕu ist nicht erfüllbar.

Beweis. “Ñ“ indirekt: Sei T Y t ϕu erfüllbar. Sei also A ein Modell von T Y t ϕu. Dannist A ein Modell von T , in dem ϕ nicht gilt. Also folgt ϕ nicht aus T .“Ð“: Sei T Y t ϕu nicht erfüllbar. Sei A ein Modell von T . Dann nicht A |ù ϕ. AlsoA |ù ϕ.

Bemerkung. Insbesondere also: ϕ allgemeingültig ðñ ϕ nicht erfüllbar.Ziel: Analyse der Erfüllbarkeit. Natürliche Frage: Sei ϕ erfüllbar. Hat dann ϕ ein endlichesModell (d.h. Modell mit endlichem Träger)? Dies ist nicht der Fall!

Beispiel. L � tfu einstelliges Funktionszeichen.

Sei ϕ1 die Aussage @x @y pfpxq � fpyq ÝÑ x � yq

ϕ2 die Aussage Dz @x fpxq � z

und ϕ die L-Aussage ϕ1 ^ ϕ2.ϕ ist erfüllbar, denn A � pN, fNq mit fNpnq � 2n ist Modell von ϕ. Aber ϕ besitzt kein

endliches Modell. Denn sei A � pA, fAq ein Modell von ϕ. Dann ist fA : A Ñ A injektiv,aber nicht surjektiv, also nicht endlich. Also ist A unendlich.

Notation. Ist ϕ eine L-Formel, so sei Frpϕq � Menge der in ϕ frei vorkommenden Va-riablen. Ist ϕ eine L-Formel, so schreibe |ù ϕ für |ù @x1 . . . ,@xn ϕ, wobei Frpϕq �tx1, . . . , xnu.

Bemerkung (gebundene Umbenennung). Seien ϕ eine L-Formel und z eine Variable, diein ϕ nicht vorkommt. Dann

|ù pDx ϕÐÑ Dz ϕxpzqq08.11.2011

Definition. Sei ϕ eine L-Formel. ϕ ist pränex ðñ ϕ hat die Form Q1x1, . . . , Qnxn θ mitθ quantorfrei, Qi ist D oder @ (i � 1, . . . , n) und die x1, . . . , xn sind paarweise verschieden.

Lemma 7 (pränexe Normalform). Sei ϕ eine L-Formel. Dann existiert eine pränexe L-Formel ϕ mit Frpϕq � Frpϕq und |ù pϕÑ ϕq.

Beweis. 1. Fall ϕ ist atomar. Setze einfach ϕ gleich ϕ

2. Fall ϕ ist gleich ψ. Sei ψ gleich Q1x1, . . . , Qnxn θ mit θ quantorfrei. Setze ϕ gleich

Q1x1, . . . , Qnxn θ mit Q ist gleich"@ falls Qi gleich DD falls Qi gleich @

3. Fall ϕ ist gleich pϕ1_ϕ2q. Seien ϕ1, ϕ2 gleich Q1x1, . . . , Qnxn θ1 und Q�1z1, . . . , Q�mzm θ2

mit θ1, θ2 quantorfrei. Wegen gebundener Umbenennung können wir ohne Einschrän-kung annehmen, dass die Variablen z1, . . . , zm nicht in ϕ1 und die Variablen x1, . . . , xnnicht in ϕ2 vorkommen. Setze dann

ϕ gleich Q1, x1, . . . , Qnxn, Q�1z1, . . . , Q

�mzm pθ1 _ θ2q

10


4. Fall ϕ ist gleich Dz ψ. Sei ψ gleich Q1x1, . . . , Qnxn θ mit θ quantorfrei. Ist z gleich xi für1 ¤ i ¤ n, so setze ϕ gleich ψ. Ist z � xi, für alle 1 ¤ i ¤ n, so ϕ gleich Dz ψ.

Dies tut’s!

Ist ϕ wie oben, so ist ϕ eine pränexe Normalform von ϕ.

Definition. Sei ϕ eine L-Formel. ϕ ist eine @-Formel, wenn ϕ die Form hat @x1, . . . ,@xn θmit θ quantorfrei, x1, . . . , xn paarweise verschieden. (n � 0 ist zugelassen).

Lemma 8 (Skolemsche Normalform). Sei ϕ eine L-Aussage. Dann existieren Sprachenerster Stufe L� mit L� � L und eine L�-Aussage ϕ� mit:

(1) ϕ� ist eine @-Aussage,

(2) |ù pϕ� Ñ ϕq,

(3) Ist ϕ erfüllbar, so ist ϕ� erfüllbar.

Beweis. Wegen Lemma 7 können wir ohne Einschränkung annehmen, dass ϕ pränex ist.Wir eliminieren nun schrittweise alle Existenzquantoren. Sei hierzu ϕ pränex und vonder Form @x1, . . . ,@xm Dy ψ, wobei ψ noch weitere Quantoren enthalten darf. Ist m �0, so ist ϕ gleich ψypcq, wobei c eine neue Konstante ist. ist m ¡ 0, so sei ϕ gleich@x1, . . . ,@xm ψypfpx1, . . . , xmqq, wobei f ein neues m-stelliges Funktionszeichen ist. Es giltdann:

(1) ϕ ist pränex

(2) |ù pϕÑ ϕq

(3) Ist ϕ erfüllbar, so ist ϕ erfüllbar.

Zu p3q: Sei ϕ erfüllbar. Sei also A L-Struktur mit A |ù ϕ.

1. Fall m � 0: Dann A |ù Dy ψ. Also existiert ein a P A mit A |ù ψyras. Setze L � LY tcu.Expandiere A zu L-Struktur A indem c durch a interpretiert wird. Da A |ù ϕ also ϕerfüllbar.

2. Fall m ¡ 0: Dann A |ù @x1, . . . ,@xmDy ψ. Also existiert für alle a1, . . . , am P A ein b P Amit A |ù ψ~x,yra1, . . . , am, bs. Sei A der Träger von A. Wir können also eine Funktiong : Am Ñ A so definieren, dass gilt: für alle a1, . . . , am: A |ù ψ~x,yra1, . . . , am, gpa1, . . . , amqs.Sei nun L gleich LY tfu, wobei f ein m-stelliges Funktionszeichen ist. Expandiere Azu L-Struktur A, indem f durch g interpretiert wird. Nach Wahl von g ist dann A einModell von ϕ, d.h. ϕ ist erfüllbar.

Sei nun k � Anzahl der Existenzquantoren, die “explizit“ in ϕ vorkommen. Definiere dannϕi für i ¤ k durch:

ϕ0 �ϕ

ϕi�1 �ϕi

Setze ϕ� gleich ϕk. ϕ� ist wie gewünscht.

11


Ist ϕ� wie oben, so heißt ϕ� eine Skolemsche Normalform von ϕ. Beachte, dass wegen (2),(3) insbesondere gilt:

ϕ ist erfüllbar ðñ ϕ� ist erfüllbar.

Definition. Seien A,L L-Strukturen. Dann ist A Unterstruktur von L (bzw. L Erweiterungvon A), falls für A � Träger von A, B � Träger von L gilt:

(U1) A � B

(U2) für alle f P FunknL, fL æ An � fA

(U3) für alle R P RelnL, RA � RL XAn

(U4) für alle c P KonstL, cL � cA

Notation. A � L für “A ist Unterstruktur von L“

Beispiel. pN,�q ist Unterstruktur von pZ,�q10.11.2011

Lemma 9. Sei L eine L-Struktur, B � Träger von L. Sei A � B. Dann sind äquivalent:

(1) Es gibt A � L mit A � Träger von A

(2) (a) A � H(b) Für alle f P FunknL, a1, . . . , an P A, fLpa1, . . . , anq P A

(c) für alle c P KonstL, cL P A

Beweis. (1)Ñ(2) klar.(2)Ñ(1) Sei (2) erfüllt. Setze A �

�pA, fL æ AnqfPFunkL

, pRL XAnqRPRelL , pcLqcPKonstL

�,

dann A � L.

Außerdem gilt natürlich:

Falls A1,A2 � L, Träger von A1 gleich Träger von A2, so A1 � A2

.

Lemma 10. Seien A,L L-Strukturen, A � L. Dann gilt:

(a) Sei t L-Term, in dem höchstens die Variablen x1, . . . , xn vorkommen. Dann gilt für allea1 . . . , an P A

tL~xra1, . . . , ans � tA~x ra1, . . . , ans

(b) Sei ϕ quantorenfreie L-Formel. Dann gilt für alle a1, . . . , an P A:

A |ù ϕ~xra1, . . . , ans ðñ L |ù ϕ~xra1, . . . , ans

12


(c) Sei ϕ eine @-Formel. Dann gilt für alle a1, . . . , an P A:

falls L |ù ϕ~xra1, . . . , ans, so A |ù ϕ~xra1, . . . , ans

Beweis. (a), (b) durch einfache Induktion über den Aufbau.zu (c): Sei ϕ gleich @z1, . . . ,@zn ψ mit ψ quantorfrei. Seien ohne Einschränkung x1, . . . , xn

frei in ϕ und a1, . . . , an P A. Dann:

L |ù ϕ~xra1, . . . , ans

ñ für alle b1, . . . , bm P L : L |ù ϕ~z,~xrb1, . . . , bm, a1, . . . , ans

ñ für alle b1, . . . , bm P A : L |ù ϕ~z,~xrb1, . . . , bm, a1, . . . , ans

ñ für alle b1, . . . , bm P A : A |ù ϕ~z,~xrb1, . . . , bm, a1, . . . , ans

Satz 11 (schwache Version von Löwenheim-Skolem). Sei ϕ erfüllbare L-Aussage. Dann hatϕ ein höchstens abzählbares Modell.

Beweis. Sei ohne Einschränkung L endlich. Sei gemäß Lemma 8 ϕ� eine Skolemsche Normal-form (in Sprache L�), wobei ohne Einschränkung auch L� endlich ist. Nach Voraussetzungist ϕ erfüllbar. Also ist auch ϕ� erfüllbar. Sei L ein Modell von ϕ�. Sei B � Träger von L.Wähle ein a P B. Sei A die kleinste Teilmenge von B mit

(1) a P A

(2) für alle c P KonstL� cL P A

(3) für alle f P FunknL� und alle a1, . . . , an P A fLpa1, . . . , anq P A

Wegen L� endlich ist A höchstens abzählbar, denn:

setze A0 � tau Y tcL | c P KonstL�u

Ai�1 � Ai Y tfLpa1, . . . , anq | a1, . . . , an P Ai, f P Funk

nL� , n ¥ 0u

Dann ist A ��iPNAi, und jedes Ai ist endlich. Nach Lemma 9 existiert dann A � L mit

A � Träger von A. Da L |ù ϕ� und ϕ� eine reine @-Aussage ist, folgt aus Lemma 10 (c),dass A |ù ϕ�. Aber |ù pϕ� Ñ ϕq. Also auch A |ù ϕ. Aber A ist höchstens abzählbar.

Folgerung. ϕ erfüllbar? Wir müssen nur abzählbare Strukturen untersuchen.

Definition. Seien A, L L-Strukturen, g : A Ñ B, wobei A � Träger von A, B � Trägervon L. Dann ist g ein Isomorphismus von A auf L (Bez.: g : A Ñ L), wenn die folgendenBedinungen gelten:

(J1) g : AÑ B ist bijektiv

13


(J2) ist f P FunknL, so für alle a1, . . . , an P A

g�fApa1, . . . , anq

� fL pgpa1q, . . . , gpanqq

(J3) ist R P RelnL, so für alle a1, . . . , an P A

RA pa1, . . . , anq ðñ RL pgpa1q, . . . , gpanqq

(J4) ist c P KonstL, so gpcAq � cL

A, L sind isomorph (Bez.: A � L) ðñ es existiert g : A Ñ L

Lemma 12. Seien g : A Ñ L und t ein L-Term, in dem höchstens die paarweise verschie-denen Variablen x1, . . . , xn vorkommen. Dann gilt für alle a1, . . . , an P A:

gptA~x ra1, . . . , ansq � tA~x rgpa1q, . . . , gpanqs

Beweis. klar nach (J2), (J4).

Satz 13. Sei g : A Ñ L und ϕ eine L-Formel mit höchstens x1, . . . , xn frei in ϕ, x1, . . . , xnpaarweise verschieden. Dann gilt für alle a1, . . . , an P A:

A |ù ϕ~xra1, . . . , ans ðñ L |ù ϕ~xrgpa1q, . . . , gpanqs

Beweis. Induktion über den Aufbau:

1. Fall ϕ hat die Form t1 � t2 mit t1, t2 L-Terme. Dann

A |ù ϕ~xra1, . . . , ans ðñ tA1,~xra1, . . . , ans � tA2,~xra1, . . . , ans

ðùùùùñg injektiv

gptA1,~xra1, . . . , ansq � gptA2,~xra1, . . . , ansq

ðñ tL1,~xrgpa1q, . . . , gpanqs � tL2,~xrgpa1q, . . . , gpanqs

ðñ L |ù ϕ~xrgpa1q, . . . , gpanqs

2. Fall ϕ hat die Form Rpt1, . . . , tnq. Vorgehen unter Verwendung von Lemma 12 und (J3)analog.

3. Fall Sei ϕ von der Form Dy ψ. Sei ohne Einschränkung y � xi für 1 ¤ i ¤ n.“ñ“: Sei A |ù ϕ~xra1, . . . , ans. Dann existiert c P Amit A |ù ψy,~xrc, a1, . . . , ans. Nach In-duktionsvoraussetzung L |ù ψy,~xrgpcq, gpa1q, . . . , gpanqs. Also L |ù ϕ~xrgpa1q, . . . , gpanqs.“ð“: Sei L |ù ϕ~xrgpa1q, . . . , gpanqs. Dann existiert b P Lmit L |ù ψy,~xrb, gpa1q, . . . , gpanqs.Wegen g surjektiv existiert c P A mit b � gpcq. Also L |ù ψy,~xrgpcq, gpa1q, . . . , gpanqs.Somit nach Induktionsvoraussetzung A |ù ψy,~xrc, a1, . . . , ans. Also A |ù ϕ~xra1, . . . , ans.

Negations- und Disjunktionsschritt sind trivial.

14


Lemma 14. Sei A eine L-Struktur, B eine Menge und g : A Ñ B eine Bijektion, wobeiA � Träger von A. Dann existiert genau eine L-Struktur L mit B � Träger von L undg : A Ñ L.

Beweis. Zur Existenz: Für f P FunknL setze fLpgpa1q, . . . , gpanqq � gpfApa1, . . . , anqq. FürR P RelnL definiere RLpgpa1q, . . . , gpanqq ðñ RApa1, . . . , anq. Für c P KonstL setze cL �gpcAq.

15.11.2011

Folgerung. Sei ϕ erfüllbare Aussage. Dann hat ϕ ein Modell L mit Träger N oder t0, . . . , nufür ein n P N.

Beweis. Nach Satz 11 hat ϕ ein höchstens abzählbares Modell A. Sei A � Träger vonA. Definiere nun B wie folgt: Ist A unendlich, so ist B � N. Ist A endlich, so sei B �t0, . . . , n� 1u, wobei n die Anzahl der Elemente von A. Also existiert Bijektion g : AÑ B.Nach Lemma 14 existiert L-Struktur L mit B � Träger von L und g : A Ñ L. Wegen A |ù ϕgilt dann nach Satz 13 auch L |ù ϕ. L ist also wie gewünscht.

Satz 15. Sei ϕ eine reine @-Aussage, etwa ϕ � @x1, . . . ,@xn ψ mit ψ quantorfrei. SeiKonstL � H. Dann sind äquivalent:

(1) ϕ ist erfüllbar.

(2) T � tψ~xpt1, . . . , tnq | t1, . . . , tn konstanter L-Term u ist erfüllbar.

Beweis. (1) ñ (2): Sei A L-Struktur mit A |ù ϕ. Sind dann t1, . . . , tn konstante L-Terme,so natürlich A |ù ψ~xpt1, . . . , tnq. Also A |ù T .(2) ñ (1): Sei L L-Struktur mit L |ù T . Setze A �

tL | t konstanter L-Term

(. Dann

gilt:

(a) A � H

(b) für alle c P KonstL, cL P A

(c) für alle f P FunknL und alle a1, . . . , an P A ist fLpa1, . . . , anq P a

Denn: Zu (a): gilt, da KonstL � H. (b) ist trivial. Zu (c): Seien f P FunknL und a1, . . . , an PA. Dann existiert für jedes 1 ¤ i ¤ n ein konstanter L-Term ti mit ai � tL1 . Dann aberfLpa1, . . . , anq � fLptL1 , . . . , t

Lnq � fpt1, . . . , tnq

Llooooooomooooooonkonst. L-Term

P A.

Nach Lemma 9 existiert also A � L mit A � Träger von A. Da alle Elemente von Tquantorfrei sind, gilt dann wegen L |ù T nach Lemma 10 (b) auch A |ù T . Es genügt nunzu zeigen, dass A |ù ϕ. Hierzu ist zu zeigen: Für alle a1, . . . , an P A, A |ù ψ~xra1, . . . , ans.Seien also a1, . . . , an P A. Für jedes 1 ¤ i ¤ n existiert dann konstanter L-Term ti mit

ai � tLi . Nach Lemma 10 ist aber tLi gleich tAi . Nun aber A |ù ψ~xpt1, . . . , tnq wegen A |ù T .Also A |ù ψ~xra1, . . . , ans.

Beachte, dass die Elemente von T oben alle quantorfrei sind. Nun gilt aber:

15

2 Termmodelle, Kompaktheitssatz

Lemma 16. Sei ϕ eine erfüllbare quantorfreie Aussage. Sei n � Anzahl der Terme, die inϕ vorkommen. Dann hat ϕ ein Modell mit Träger t0, . . . ,m� 1u für ein m ¤ n.

Beweis. Sei L ein Modell von ϕ. Ohne Einschränkung sei L L-Struktur, wobei jedes nicht-logische Zeichen von L in ϕ vorkommt. Setze A � ttL | t L-Term, der in ϕ vorkommtu.(Beachte, dass diese L-Terme alle konstant sind.) Also hat A höchstens n Elemente. Beach-te, dass A � H. Sei a0 P A fest. Für f P FunknL definiere fA : An Ñ A durch:

fApa1, . . . , anq �

"fLpa1, . . . , anq falls fLpa1, . . . , anq P A

a0 sonst

Weiterhin sei RA � RL XAn für R P RelnL und cL für c P KonstL. Setze

A ��A, pfAqfPFunkn

L, pRAqRPRelL , pc

AqcPKonstL

Durch Induktion über den Aufbau zeigt man leicht:

Kommt ein Term t in ϕ vor, so tA gleich tL.

Hiermit erhält man leicht A |ù ϕ, indem man dies durch Indution für jede Teilformel von ϕzeigt.

Nun besteht zwar die Theorie T aus Satz 15 aus quantorfreien Aussagen, aber T ist imallgemeinen unendlich. Wir beschäftigen uns daher mit der Frage, wann eine unendlicheTheorie erfüllbar ist.

2 Termmodelle, KompaktheitssatzDefinition. Sei A eine L-Struktur, A � Träger von A. Sei LA die Sprache, die man aus Lerhält, indem man für jedes a P A eine neue Konstante a hinzufügt. Sei A� die LA-Expansionvon A mit aA� gleich a für alle a P A. Setze

ThpAq � tϕ | ϕ LA-Aussage, A� |ù ϕu

die “volle“ Theorie von A.

Bemerkung. Ist ϕ eine L-Formel, und sind a1, . . . , an P A, so:

A |ù ϕ~xra1, . . . , ans ðñ A� |ù ϕ~xpa1, . . . , anq

Lemma 1. Sei A eine L-Struktur, A � Träger von A. Setze T � ThpAq und L� � LA.Dann gelten die folgenden Eigenschaften (für alle konstanten Terme s1, . . . , sn, t1, . . . , tn):

(M1) (a) s1 � s1 P T

(b) s1 � s2 P T ñ s2 � s1 P T

16


(c) s1 � s2 P T , s2 � s3 P T ñ s1 � s3 P T

(d) falls f P FunknL, so:

s1 � t1, . . . , sn � tn P T ñ fps1, . . . , snq � fpt1, . . . , tnq P T

(e) falls, R P RelnL und s1 � t1, . . . sn � tn P T so

Rps1, . . . , snq P T ðñ Rpt1, . . . , tnq P T

(M2) Falls ϕ L�-Aussage, so: ϕ P T ðñ ϕ R T

(M3) Falls ϕ,ψ L�-Aussagen, so: pϕ_ ψq P T ðñ pϕ P T oder ψ P T q

(M4) Falls Dx ϕ L�-Aussage, so:

Dx ϕ P T ðñ es existiert konstanter L�-Term t mit ϕxptq P T

Beweis. (M1)-(M3) sind klar.zu (M4) “ñ“: Sei Dx ϕ P T . Also A� |ù Dx ϕ, d.h. es existiert a P A mit A� |ù ϕxras.

Somit auch A� |ù ϕxpaq. Also ϕxpaq P T und g ist konstanter L�-Term.“ð“: Sei ϕxptq P T . Also A |ù ϕxptq. Setze a � tA

� . Dann A� |ù ϕxras, also A� |ù Dx ϕ,d.h. Dx ϕ P T .

17.11.2011

Wir beweisen im folgenden eine Umkehrung (von Lemma 1).

Satz 2 (Henkin). Sei KonstL � H. Sei T eine L-Theorie erster Stufe, und T erfülle dieEigenschaften (M1)-(M4) (wenn man dort L� durch L ersetzt). Dann ist T erfüllbar.

Beweis. Sei M � tt | t ist konstanter L-Term u, M � H da KonstL � H. Definiere Relati-on � auf M durch:

s � t ðñ s � t P T

Dann ist � reflexiv nach (M1)(a), symmetrisch nach (M1)(b) und transitiv nach (M1)(c).Also ist � eine Äquivalenzrelation. Für s PM setze

rss � tt PM | s � tu

Setze A � trss | s P Mu. Für f P FunknL definiere fM : Mn Ñ M durch fM pt1, . . . , tnq �fpt1, . . . , tnq. Nach (M1)(d) gilt dann: (1) s1 � t1, . . . , sn � tn ñ fM ps1, . . . , snq �fM pt1, . . . , tnq. Also induziert fM eine Abbildung fA : An Ñ A vermöge

fA prs1s, . . . , rsnsq ��fM ps1, . . . , snq

�Für R P RelnL definiere RM �Mn durch:

RM ps1, . . . , snq ðñ Rps1, . . . , snq P T

17


Nach (M1)(e) gilt dann: (2) Es gelte s1 � t1, . . . , sn � tn. Dann pRM ps1, . . . , snq ðñRM pt1, . . . , tnqq. Also induziert RM eine Relation RA � An durch:

RAprs1s, . . . , rsnsq ðñ RM ps1, . . . , snq

Für c P KonstL setze schliesslich cA � rcs. Setze

A ��A, pfAqfPFunkL

, pRAqRPRelL , pcAqcPKonstL

�A ist L-Struktur. Wir werden zeigen, dass A ein Modell von T ist. Hierzu zuerst: (3) Seis PM . Dann sA � rss.

Beweis. Ist s P KonstL, so sA � rss nach Definition. Ist aber s � fps1, . . . , snq, so :

sA � fApsA1 , . . . , sAnq � fAprs1s, . . . , rsnsq �

�fM ps1, . . . , snq

�� rss

Schließlich: (4) Sei ϕ L-Aussage. Dann:

A |ù ϕ ðñ ϕ P T

Beweis. Induktion über den Aufbau.

(a) ϕ gleich s � t. Dann

A |ù ϕ ðñ sA � tA ðùùñ(3)

rss � rts ðñ s � t ðñ s � t P T

(b) ϕ gleich Rps1, . . . , snq. Dann

A |ù ϕ ðñ RApsA1 , . . . , sAnq ðùùñ(3)

RAprs1s, . . . , rsnsq ðùñDef.

RM ps1, . . . , snq

ðùñDef.

Rps1, . . . , snq P T

(c) ϕ gleich ψ. Dann

A |ù ϕ ðñ non A |ù ψ ðùùùùñInd. Vor.

ψ R T ðùùñ(M2)

ϕ P T

(d) ϕ gleich pψ _ θq. Dann

A |ù ϕ ðñ pA |ù ψ oder A |ù θq ðñ pψ P T oder θ P T q ðùùñ(M3)

ϕ P T

(e) ϕ gleich Dx ψ. “ñ“: Sei A |ù ϕ. Dann existiert a P A mit A |ù ψxras. Sei a � rss mits PM . Nach (3) ist dann a � sA. Also A |ù ψxpsq. Somit nach Induktionsvoraussetzungψxpsq P T . Also nach (M4) ϕ P T .“ð“: Sei ϕ P T . Nach (M4) existiert dann konstanter L-Term t mit ψxptq P T . NachInduktionsvoraussetzung also A |ù ψxptq. Also A |ù ϕ

18


Aus (4) folgt aber, dass A ein Modell von T ist. Somit ist T erfüllbar.

Satz 2 liefert also Folgendes: Um zu zeigen, dass eine L-Theorie T erfüllbar ist, genügtes eine Sprache L� � L und L�-Theorie T � � T zu finden, die die Bedingungen (M1)-(M4)(bezüglich L�) erfüllt.

Definition. Sei T eine L-Theorie erster Stufe. T ist endlich erfüllbar, wenn jede endlicheTeilmenge von T erfüllbar ist.

Ziel: T endlich erfüllbar ñ T erfüllbar (Kompaktheitssatz). Hierzu gehen wir wie ange-deutet vor. 22.11.2011

Definition. Sei T eine L-Theorie. T ist L-Henkintheorie, wenn gilt: Sei ϕ eine L-Formelmit höchstens x frei in ϕ. Dann existiert c P KonstL mit pDx ϕÑ ϕxpcqq P T .

Bemerkung. Seien T1, T2 L-Theorien. Dann gilt:

T1 � T2 und T1 L-Henkintheorie ñ T2 L-Henkintheorie.

Lemma 3. Sei L eine Sprache erster Stufe. Dann existiert eine Sprache erster Stufe L� � Lund eine L�-Theorie TLH mit:

(a) TLH ist L�-Henkintheorie

(b) Sei A eine L-Struktur. Dann existiert A� mit A� ist L�-Expansion von A und A� |ù TLH

Zusatz: Ist L abzählbar, so ist auch L� abzählbar.

Beweis. Konstruiere rekursiv eine Menge an Konstanten Ci durch:

C0 � H

Ci�1 � Ci Y tci,ϕ,x | ϕ Li-Formel mit höchstens x freiu

Dabei sei Li � LYCi und die Konstanten ci,ϕ,x seien neu und paarweise verschieden. SetzeL� �

�iPN Li und

TLH � tpDxϕÑ ϕxpci,ϕ,xqq | i P N, ϕ L-Formel mit höchstens x frei in ϕu

Offenbar gilt (a), denn FormL� ��iPN FormLi .

Zu (b): Sei A L-Struktur. Wir müssen noch die neuen Konstanten ci,ϕ,x interpretieren.Sei a ein festes Element von A. Wir definieren rekursiv Li-Expansion Ai von A mit Ai�1ist Li�1-Expansion von Ai. Setze A0 � A. Sei nun Ai schon definiert. Sei ϕ Li-Formel mithöchstens x frei in ϕ.

1. Fall Ai |ù Dx ϕ.Setze dann cAi�1

i,ϕ,x � a. Dann Ai�1 |ù pDx ϕÑ ϕxpci,ϕ,xqq.

19


2. Fall Ai |ù Dx ϕDann existiert b P Ai mit Ai |ù ϕxrbs. Setze cAi�1

i,ϕ,x � b. Dann wieder Ai�1 |ù pDx ϕ Ñϕxpci,ϕ,xqq.

Sei schliesslich A� die L�-Expansion von A mit A� ist L�-Expansion von jedem Ai. Dannnach Konstruktion A� |ù TLH .Zum Zusatz: L abzählbar ñ @i Ci abzählbar ñ

�iPNCi abzählbar ñ L� abzählbar.

Lemma 4. Sei T endlich erfüllbare L-Theorie. Dann ist T Y TLH endlich erfüllbar.

Beweis. Wir zeigen sogar etwas stärker: (*) für alle endlichen ∆ � T ist ∆Y TLH erfüllbar.Sei dann ∆ � T endlich. Nach Voraussetzung existiert dann eine L-Struktur A mit A |ù ∆.Nach Lemma 3(b) existiert L�-Expansion A� von A mit A� |ù TLH . Also A� |ù ∆Y TLH .

Definition. Sei T L-Theorie erster Stufe. T ist L-vollständig ðñ

für alle L-Aussagen ϕ gilt pϕ P T oder ϕ P T q

Wir sagen oft nur vollständig, wenn L aus dem Zusammenhang ersichtlich ist.

Lemma 5. Sei T vollständige, endlich erfüllbare L-Theorie. Sei ∆ � T endlich und ϕL-Aussage. Dann gilt:

∆ |ù ϕñ ϕ P T

Beweis. Sei ∆ |ù ϕ. Dann ist ∆ Y t ϕu nicht erfüllbar. Wegen T endlich erfüllbar also∆Y t ϕu � T . Wegen ∆ � T also ϕ R T . Wegen T vollständig also ϕ P T .

Lemma 6. Sei T endlich erfüllbare L-Theorie und ϕ L-Aussage. Dann gilt:

T Y tϕu ist endlich erfüllbar oder T Y t ϕu ist endlich erfüllbar.

Beweis. Sei T Y tϕu nicht endlich erfüllbar. Wir müssen zeigen, dass T Y t ϕu endlicherfüllbar ist. Wegen T Y tϕu nicht endlich erfüllbar, existiert ein endliches ∆0 � T mit∆0 Y tϕu nicht erfüllbar. Dann aber ∆0 |ù ϕ. Wir zeigen nun, dass T Y t ϕu endlicherfüllbar ist. Sei also ∆ � T endlich. Zu zeigen ∆ Y t ϕu hat Modell. Wegen T endlicherfüllbar existiert ein Modell A von ∆ Y ∆0. Wegen ∆0 |ù ϕ dann A |ù ϕ. Also ist AModell von ∆Y t ϕu.

Lemma 7. Sei T endlich erfüllbare L-Theorie. Dann sind äquivalent:

(1) T ist vollständig.

(2) Falls T � T 1, T 1 endlich erfüllbar, so T � T 1 (d.h. T ist maximale endlich erfüllbareL-Theorie)

20


Beweis. (1)ñ(2): Sei T 1 wie in (2). Annahme: T 1 � T . Also gibt es ein ϕ mit ϕ, ϕ P T 1.Dann ist aber T 1 nicht endlich erfüllbar, denn tϕ, ϕu hat kein Modell. Widerspruch zurVoraussetzung.(2)ñ(1): T erfülle (2). Sei ϕ L-Aussage. Nach Lemma 6 gilt dann: T Y tϕu endlich

erfüllbar oder T Yt ϕu endlich erfüllbar. Sei etwa T Ytϕu endlich erfüllbar. Dann nach (2)T Y tϕu � T , d.h. ϕ P T . Im anderen Fall ist ϕ P T .

Lemma (Lemma von Zorn). Sei K � H , und es gelte:

p�q H � K1 � K mit: für alle A,B P K1, A � B oder B � A. Dann ist¤

K1 P K

Dann existiert A P K mit:

falls A � B und B P K, so A � B

Lemma 8. Sei M eine Menge von endlich erfüllbaren L-Theorien mit:

für alle T, T 1 PM T � T 1 oder T 1 � T .

Dann ist�tT | T PMu endlich erfüllbar.

Beweis. Setze T ��tT | T P Mu. Falls M � H, so T � H endlich erfüllbar. Sei also

M � H. Sei ∆ � T endlich. Also existieren T0, . . . , Tn P M mit ∆ � T0 Y . . . Y Tn. NachVoraussetzung existiert aber i ¤ n, so dass T0 Y . . .Y Tn � Ti. Somit ist ∆ erfüllbar, da Tiendlich erfüllbar.

Lemma 9. Sei T endlich erfüllbare L-Theorie. Dann existiert L-Theorie T 1 � T mit T 1 istendlich erfüllbar und vollständig.

Beweis. Setze K � tT | T endlich erfüllbare L-Theorie, T � T u. Also T P K. Wegen Lemma8 existiert nach Zornschem Lemma ein T 1 P K mit folgender Eigenschaft

pT P K und T 1 � T Ñ T � T 1q

Ein etwas konkreterer Beweis von Lemma 9 für den Fall, dass L abzählbar ist:

Beweis. Sei dann pϕiqiPN Aufzählung aller L-Aussagen. Definiere rekursiv T0 � T1 � . . .durch:

T0 � T

Ti�1 �

"Ti Y tϕiu falls Ti Y tϕiu endlich erfüllbarTi Y t ϕiu sonst.

Nach Lemma 6 ist dann Ti endlich erfüllbar für alle i P N. Setze T 1 ��iPN Ti. T 1 ist endlich

erfüllbar nach Lemma 8 und vollständig nach Konstruktion.23.11.2011

21


Lemma 10. Sei T vollständige endlich erfüllbare L-Henkintheorie. Dann ist T erfüllbar.

Beweis. Wir zeigen: T erfüllt (M1)-(M4). Dann folgt die Behauptung mit Satz 2.

Zu (M1) Seien s1, . . . , sn, t1, . . . , tn konstante L-TermeZu (a): |ù s1 � s1. Also s1 � s1 P T nach Lemma 5.Zu (b): Sei s1 � s2 P T . Nun aber s1 � s2 |ù s2 � s1 also s2 � s1 nach Lemma 5Zu (c): Seien s1 � s2 P T und s2 � s3 P T . Nun aber ts1 � s2, s2 � s3u |ù s1 � s3.Also s1 � s3 P T nach Lemma 5Zu (d): Sei f P FunknL und s1 � t1, . . . , sn � tn P T : Nun aber

ts1 � t1, . . . , sn � tnu |ù fps1, . . . , snq � fpt1, . . . , tnq

Also fps1, . . . , snq � fpt1, . . . , tnq P T nach Lemma 5.Zu (e): Sei R P RelnL und s1 � t1, . . . , sn � tn P T . Zu zeigen Rps1, . . . , snq PT ðñ Rpt1, . . . , tnq P T . “ñ“: Sei Rps1, . . . , snq P T . Nun wieder ts1 � t1, . . . , sn �tn, Rps1, . . . , snqu |ù Rpt1, . . . , tnq. Also Rpt1, . . . , tnq P T nach Lemma 5. “ð“: analog.

Zu (M2) Sei ϕ L-Aussage. Wegen T vollständig gilt: pϕ P T oder ϕ P T Wegen T endlicherfüllbar gilt: pϕ R T oder ϕ R T q, da tϕ, ϕu nicht erfüllbar. Also ϕ P T ðñϕ R T .

Zu (M3) Seien ϕ,ψ L-Aussagen. Zu zeigen: pϕ_ ψq P T ðñ pϕ P T oder ψ P T q“ð“: Sei ϕ P T oder ψ P T . Aber ϕ |ù pϕ_ ψq und ψ |ù pϕ_ ψq. Also nach Lemma 5pϕ_ ψq P T

“ñ“: Sei pϕ _ ψq P T . Wegen T vollständig genügt es zu zeigen, dass ϕ R T oder ψ R T . Aber tpϕ _ ψq, ϕ, ψu ist nicht erfüllbar. Wegen T endlich erfüllbar alsotpϕ_ ψq, ϕ, ψu � T , d.h. ϕ � T oder ψ R T , da pϕ_ ψq P T .

Zu (M4) Sei Dx ϕ L-Aussage. Zu Zeigen Dx ϕ P T ðñ es existiert konstanter L-Termt mit ϕxptq P T . “ð“: Sei t konstanter L-Term mit ϕxptq. Nun aber ϕxptq |ù Dx ϕ.Also nach Lemma 5 Dx ϕ P T “ñ“: Sei Dx ϕ P T . Wegen T L-Henkintheorie existiertc P KonstL mit pDx ϕ Ñ ϕxpcqq P T . Nun aber tDx ϕ, Dx ϕ Ñ ϕxpcqu |ù ϕxpcq. Alsonach Lemma 5 ϕxpcq P T .

Satz 11 (Kompaktheitssatz). Sei T endlich erfüllbare L-Theorie. Dann ist T erfüllbar.

Beweis. Wähle L� wie in Lemma 3 und setze T � T Y TLH . Dann ist T L�-Henkintheorieund endlich erfüllbar nach Lemma 4. Nach Lemma 9 existiert dann L�-Theorie T � � T mitT � ist endlich erfüllbar und vollständig. Wegen T � � T ist auch T � L�-Henkintheorie. Alsoist T � endlich erfüllbar nach Lemma 10. Somit auch T erfüllbar, da T � T �.

22


Folgerung (Endlichkeitssatz). Seien ϕ L-Aussage und T L-Theorie. Es gelte T |ù ϕ. Dannexistiert endliches ∆ � T mit ∆ |ù ϕ.

Beweis. Annahme: Die Behauptung ist falsch. Dann ist für alle endlichen ∆ � T ∆Yt ϕuerfüllbar. Also ist TYt ϕu endlich erfüllbar. Also nach Kompaktheitssatz TYt ϕu erfüllbar,das heißt non T |ù ϕ. Widerspruch zur Voraussetzung.

Satz 12 (Herbrand). Sei ϕ eine reine @-Aussage, etwa ϕ � @x1, . . .@xn ψ mit ψ quantorfrei.Sei KonstL � H. Dann sind äquivalent:

(1) ϕ ist erfüllbar

(2) Für alle m P N und konstante L-Terme t1,i, . . . , tn,i p0 ¤ i ¤ mq ist

ψ~xpt1,0, . . . , tn,0q ^ . . .^ ψ~xpt1,m, . . . , tn,mq

erfüllbar.

Beweis. (1)ñ(2): trivial. (2)ñ(1): Sei (2) erfüllt. Dann ist

T � tψ~xpt1, . . . , tnq | t1, . . . , tn konstanter L-Termu

endlich erfüllbar. Nach Kompaktheitssatz ist also T erfüllbar. Dann aber ϕ erfüllbar nachSatz 15 aus Kapitel 1.

Folgerung (Test für Erfüllbarkeit). Sei θ L-Aussage. Ist θ erfüllbar?

1. Schritt Bestimme eine Skolemsche Normalform ϕ� von ϕ in Sprache L�, wobei ohneEinschränkung L� endlich ist. Sei ϕ� � @x1 . . .@xn ψ

� mit ψ� quantorfrei.

2. Schritt Nun prüfe nacheinander für alle Folgen von konstanten L-Termen t1,i, . . . , tn,inach, ob

ψ�~xpt1,0, . . . , tn,0q ^ . . .^ ψ�~xpt1,m, . . . , tn,mq

erfüllbar ist. Letztere Aussagen sind quantorfrei. Für jede einzelne Aussage geht dieseffektiv. Kommt irgendwann die Antwort nein, so ist ϕ nicht erfüllbar. Kommt nie dieAntwort nein, so ist ϕ erfüllbar. (Dies ist natürlich kein effektiver Test.)

Beispiel (Eine Anwendung der Kompaktheitssatzes). Sei T eine L-Theorie. T habe beliebiggroße, endliche Modelle. Dann hat T ein unendliches Modell.

Beweis. Seien cn pn P Nq neue Konstanten, paarweise verschieden. Setze L � LY tcn | n PNu. Setze T � T Y tcm � cn | m,n P N,m � nu. T ist endlich erfüllbar, denn sei ∆ � Tendlich. Dann existiert endliches E � N mit:

pci kommt in ∆ vor ñ i P Eq

Sei |E| � k. Nach Voraussetzung hat T ein Modell A, mit A hat mindestends k Elemente.Dann existiert Expansion A� von A mit cA�m � cA

�

n für m,n P E mit m � n. Dann A� |ù ∆.Nach Kompaktheitssatz sei L ein Modell von T . Dann cLm � cLn für alle m,n P N mit m � n.Also ist L unendlich.

23


Einschub über MengenlehreSeien A,B Mengen. Definiere

A ¨ B ðñ es existiert injektives f : AÑ B

B � A ðñ es existiert bijektives f : AÑ B

Man kann zeigen:

(I) pA ¨ B und B ¨ Aq Ñ A � B

(II) Ist A unendlich, so A2 � A

Es folgt dann:

(III) Sei A unendlich und für alle n P N, An ¨ A. Dann ist�nPNAn ¨ A

Beweis. Sei für n P N, hn : An Ñ A injektiv. Wegen A unendlich existiert g : NÑ A. SetzeB �

�nPNAn. Definiere f : B Ñ A2 wie folgt: Sei x P B. Wähle n P N mit x P An und setze

fpxq � phnpxq, gpxqq. Dann ist f injektiv. Also B ¨ A2 ¨pIIq A. Somit nach (I) A � B.

Setze SeqpAq ��nPNA

n, wobei A0 � tHu. Es gilt dann

(IV) Sei A unendlich. Dann SeqpAq � A.

Beweis. Aus (II) folgt durch Induktion An ¨ A für alle n. Also nach (III) SeqpAq ¨ A.A ¨ SeqpAq ist trivial. Also folgt die Behauptung aus (I).

29.11.2011

Im folgenden sei wieder L Sprache erster Stufe. Wir rechnen hier alle Zeichen zu L, so dassL immer unendlich ist.

(V) FormL � L, TermL ¨ L

Beweis. Dies folgt aus (IV) (wegen (I)).

(VI) Sei L� zu L wie in Lemma 3 konstruiert (die Henkinsprache). Dann ist L� � L

Beweis. Es ist L� ��iPN Li, wobei L0 � L und nach Konstruktion Li�1 ¨ Li Y TermLi �

V ar. Also Li�1 ¨ Li nach (V) und (II) und daher L� ¨ L nach (III). Wegen L ¨ L� folgtdie Behauptung aus (I).

Satz 13 (Löwenheim-Skolem). Sei T erfüllbare L-Theorie. Dann hat T ein Modell A �pA, . . .q mit A ¨ L.

Beweis. Sei L� zu L wie in Lemma 3 gewählt. Also nach (V) L� ¨ L. Sei dann A � pA, . . .qein Modell von T , wie im Beweis von Satz 11 konstruiert. Dann ist A ¨ TermL� ¨ L� ¨L.

24


Beispiel. Dies lässt sich nicht verbessern. Sei hierzu C eine beliebige unendliche Menge.Sei L � die Sprache mit den Konstanten tc | c P Cu (paarweise verschieden).

T � tc1 � c2 | c1, c2 P C, c1 � c2u

T ist erfüllbar, aber für jedes Modell A � pA, . . .q von T gilt C � L ¨ A.

Satz 14. Sei T L-Theorie, und T habe ein unendliches Modell. Sei D beliebige Menge mitL ¨ D. Dann hat T ein Modell A � pA, . . .q mit A � D.

Beweis. Sei L � LD, d.h. L � L Y td | d P Du, wobei d eine neue Konstante mit d � d1

für d, d1 P D, d � d1. Dann ist L � D. Setze nun T � T Y td � d1 | d, d1 P D, d � d1u. Wirzeigen: (*) T ist endlich erfüllbar.

Beweis. Sei ∆ � T endlich. Also kommen in ∆ nur endlich viele neue Konstanten vor, etwad1, . . . , dn, wobei d1, . . . , dn paarweise verschieden. Sei nach Voraussetzung A ein unendlichesModell von T . Wähle a1, . . . , an P A paarweise verschieden. Interpretiere nun di durch ai.Dies liefert Expansion A� von A mit A� |ù ∆.

Wegen (*) ist nach Kompaktheitssatz T erfüllbar. Sei nach Löwenheim-Skolem L �pB, . . .q ein Modell von T mit B ¨ L. Dann gilt aber B ¨ D, da D � L. Aber es giltauch D ¨ B, denn definiere f : D Ñ B durch fpdq � dL. Wegen L |ù T ist f injektiv.Insgesamt also B � D.

Insbesondere folgt also: T hat unendliches Modell ñ T hat beliebig große Modelle.

Definition. Seien A,L L-Strukturen. A und L sind elementar äquivalent (Bezeichnung:A � L) ðñ für alle L-Aussagen ϕ: pA |ù ϕ ðñ L |ù ϕq

Bemerkung. A�Lñ A � L. Für L-Strukturen A setze

T pAq � tϕ | ϕ L-Aussage, A |ù ϕu

Bemerkung. Seien A,L L-Strukturen. Dann:

A � L ðñ L |ù T pAq

Beweis. ñ: nach Definition. ð: Sei ϕ L-Aussage. Zu zeigen A |ù ϕ ðñ L |ù ϕ

Beweis. ñ: A |ù ϕñ ϕ P T pAqñ L |ù ϕð: indirekt: non A |ù ϕñ A |ù ϕñ ϕ P T pAqñ L |ù ϕñ non L |ù ϕ

Aus obigem folgt insbesondere: Sei A unendliche Struktur. Dann existieren beliebig großeL mit A � L.

Beweis. Setze T � T pAq. T hat unendliches Modell. Also hat T beliebig große Modelle.Jedes solcher Modelle ist elementar äquivalent zu A.

25

3 Kalküle, Gödelscher Vollständigkeitssatz

3 Kalküle, Gödelscher VollständigkeitssatzFrage. Was ist ein Beweis?Kann man die allgemeingültigen Aussagen “beweisen“?

Konvention. Sei weiterhin L eine Sprache erster Stufe.

Definition. Eine (L-)Sequenz ist eine nichtleere endliche L-Zeichenreihe der Form ϕ0 . . . ϕnmit ϕi L-Formel für i ¤ n. SeqL � Menge aller L-Sequenzen.

Bemerkung. Seien ϕ0, . . . , ϕn, ψ0, . . . , ψm L-Formeln mit ϕ0 . . . ϕn � ψ0 . . . ψm. Dann giltn � m und ϕi � ψi für alle i ¤ n.

Folgerung. Jede Sequenz lässt sich eindeutig schreiben in der Form Γϕ , wobei (Γ � Hoder Γ Sequenz) und ϕ L-Formel. Sei Γ eine Sequenz, Γ � ϕ0 . . . ϕn mit ϕi L-Formel. EineVariable x kommt in Γ frei vor, wenn: es existiert i ¤ n mit x kommt in ϕi frei vor.

Definition. Sei Γ � ϕ0 . . . ϕn eine Sequenz mit ϕi L-Formel. Seien genau x1, . . . , xm frei inΓ. Dann heißt Γ korrekt, wenn gilt:

(1) n � 0 und |ù @x1, . . . ,@xm ϕ0, oder

(2) n ¡ 0 und |ù @x1, . . . ,@xm ppϕ0 ^ . . .^ ϕn�1q Ñ ϕnq

(d.h. wir lesen ϕ0 . . . ϕn als pϕ0 ^ . . .^ ϕn�1q Ñ ϕn ).

Definition. Eine n-stellige Regel R ist eine pn � 1q-stellige Relation R � Seqn�1L . Hierbei

ist n � 0 zugelassen. Schreibe n-stellige Regeln in der Form

Γ1 . . .ΓnΓ

wobei R � tpΓ1, . . . ,Γn,Γq | Γ1, . . . ,Γn,Γ wie angegebenu

Definition. Sei R eine n-stellige Regel. R ist korrekt, wenn gilt:Falls Γ1, . . . ,Γn korrekte Sequenzen und RpΓ1, . . . ,Γn,Γq, so ist auch Γ korrekt.

Definition. Ein (Sequenzen-)Kalkül K ist eine (endliche) Menge tR1, . . . , Rku von Regeln.K ist korrekt, wenn R1, . . . , Rk korrekt sind.

Definition. Sei K � tR1, . . . , Rku ein Kalkül, wobei Rj nj-stellige Regel. Eine Ableitung inK ist eine endliche Folge pΓ0, . . . ,Γnq von Sequenzen mit der Eigenschaft:Sei i ¤ n. Dann existiert 1 ¤ j ¤ k und k1, . . . , knj i mit RjpΓk1 , . . . ,Γknj

,Γiq.Eine Sequenz Γ heißt ableitbar in K, wenn es eine Ableitung pΓ0, . . . ,Γnq in K mit Γ � Γn

gibt.01.12.2011

Lemma 1. Sei K ein korrekter Kalkül und sei Γ ableitbar in K. Dann ist Γ korrekt.

26


Beweis. Sei pΓ0, . . . ,Γnq eine Ableitung in K mit Γn � Γ. Da alle Regeln korrekt sind, folgtdurch Induktion, dass jedes Γi korrekt ist. Also ist Γ � Γn korrekt.

Definition. Seien K ein Kalkül, T L-Theorie, ϕ L-Aussage. Dann ist ϕ aus T ableitbar inK (Bezeichnung: T $K ϕ) ðñ es existieren ϕ1, . . . , ϕn P T mit

ϕ1 . . . ϕnϕ ist ableitbar in K.

Schreibe $K ϕ statt H $K ϕ. $K ϕ bedeutet “ϕ ist ableitbar“.

Bemerkung. ϕ ist als Aussage ableitbar ðñ ϕ ist als Sequenz ableitbar.

Notation. Ist Γ � ϕ0 . . . ϕn eine Sequenz, so bedeutet Γ � T : tϕ0, . . . , ϕnu � T .

Lemma 2. (Endlichkeitssatz) Sei K ein Kalkül. Dann gilt:

T $K ϕ ðñ es existiert endliches ∆ � T mit ∆ $K ϕ

Beweis. Trivial.

Lemma 3. Sei K ein korrekter Kalkül. Dann gilt:

T $K ϕñ T |ù ϕ

Beweis. Sei T $K ϕ. Dann existieren ϕ1, . . . , ϕn P T mit Γ � ϕ1 . . . ϕnϕ ableitbar in K.Also ist Γ korrekt nach Lemma 1. Aber in Γ, ϕ kommen keine Variablen frei vor. Also nachDefinition |ù ϕ oder |ù pϕ1 ^ . . .^ ϕnq Ñ ϕ. Wegen ϕ1, . . . , ϕn P T also T |ù ϕ.

Definition. Ein Kalkül K ist vollständig, wenn gilt: Sei T L-Theorie und ϕ eine L-Aussage.Dann:

T |ù ϕñ T $K ϕ

Informelle Definition: Eine n-stellige Regel R ist effektiv, wenn man effektiv feststellenkann, ob RpΓ1, . . . ,Γn,Γq gilt. Ein Kalkül K � tR1, . . . , Rnu heißt effektiv, wenn alle Rieffektiv sind.(informell) Gödelscher Vollständigkeitssatz: Es existiert effektiver, korrekter und vollstän-

diger Kalkül K.Für solch ein K gilt also: T |ù ϕ ðñ T $K ϕ. “ñ“: vollständig. “ð“: korrekt.

Notation. Sprich “ϕ in Γ“ für “Γ � ϕ0 . . . ϕn und es existiert i mit ϕ � ϕi“. Für SequenzenΓ,Γ1 schreibe “Γ � Γ1“ für “Jedes ϕ, dass in Γ vorkommt, kommt auch in Γ1 vor“.

Der kanonische Kalkül KL besteht aus folgenden Regeln (im folgenden immer Γ � H oderΓ Sequenz):

(Vor)

Γϕ , falls ϕ in Γ

27


(Ant)ΓϕΓ1ϕ , falls Γ � Γ1

(FU)Γψϕ Γ ψϕ

Γϕ

(Wid)Γψ Γ ψ

Γϕ

(vA)Γϕχ ΓψχΓpϕ_ ψqχ

(vS)Γϕ

Γpϕ_ ψq ,Γψ

Γpϕ_ ψq

(DA)

ΓϕxpyqψΓDx ϕψ , falls y nicht frei in ΓDx ϕψ und die Substitution ϕxpyq erlaubt ist.

(DS)ΓϕxptqΓDx ϕ , wobei t Term.

(GL1)

t � t

(GL2)

s � t t � s

(GL3)

s1 � s2 s2 � s3 s1 � s3

(GL4)

s1 � t1 . . . sn � tn fps1, . . . , snq � fpt1, . . . , tnq

(GL5)

s1 � t1 . . . sn � tn Rps1, . . . , snq Rpt1, . . . , tnq

Satz 4. KL ist korrekt.

28


Beweis. Wir müssen die Korrekheit aller Regeln zeigen. (Vor), (Ant) sind klar.Zu (FU): Seien aus Notationsgründen keine Variablen frei in Γψϕ. Seien Γψϕ und Γ ψϕ

korrekt. Zu zeigen: |ù�

Γ Ñ ϕ. Ist aber A Modell von�

Γ, so A |ù ψ oder A |ù ψ. IstA |ù ψ, so wegen |ù p

�Γ^ψq Ñ ϕ A |ù ϕ. Ist aber A |ù ψ, so wegen |ù p

�Γ^ ψq Ñ ϕ

A |ù ϕ.Zu (Wid) wieder Vereinfachung wie oben. Seien Γψ, Γ ψ korrekt. Also |ù p

�Γ Ñ ψq

und |ù p�

Γ Ñ ψq. Also existiert kein Modell von�

Γ. Also |ù p�

Γ Ñ ϕq.(vA), (vS) sind klar.Zu (DA): Sei wieder aus Notationsgründen höchstens x frei in Γϕψ (Beachte Voraussetzung

über y). Sei (*) |ù @y p�

Γ ^ ϕxpyq Ñ ψq. Zu zeigen |ù pp�

Γ ^ Dx ϕq Ñ ψq. Sei also Aein Modell von

�Γ ^ Dx ϕ. Insbesondere existiert dann ein a P A mit A |ù ϕxras. Somit

A |ù p�

Γ^ ϕxpyqqyras. Wegen (*) somit A |ù ψ.Zu (DS): Sei |ù

�Γ Ñ ϕxptq. Zu zeigen |ù p

�Γ Ñ Dx ϕq. Sei der Einfachheit halber

keine Variable frei in Γϕxptq. Sei A |ù�

Γ. Wegen Voraussetzung also A |ù ϕxptq, d.h.A |ù ϕxrt

As. Also A |ù Dx ϕ.(GL1)-(GL5) sind klar.

Notation. Schreibe T $L ϕ statt T $ KLϕ. Sage “L-ableitbar“ statt “ableitbar in KL“.

Definition. Eine n-stellige Regel R heisst ableitbar, falls:

Γ1, . . . ,Γn L-ableitbar und RpΓ1, . . . ,Γn,Γq ñ Γ L-ableitbar

Beispiel. Sei die Kettenschlussregel (KS) folgende Regel:

Γϕ ΓϕψΓψ

(KS) ist ableitbar.

Beweis.Γϕ p1qΓϕψ p2q

(Ant) aus (1) Γ ϕϕ p3q(Vor) Γ ϕ ϕ p4q

(Wid) aus (3),(4) Γ ϕψ p5q(FU) aus (2),(5) Γψ

Bemerkung. ableitbare Regeln dürfen in Ableitungen verwendet werden06.12.2011

Definition. Sei T L-Theorie. T ist L-widerspruchsfrei ðñ es existiert keine L-Aussageψ mit T $L ψ und T $L ψ. Andernfalls heißt T L-widerspruchsvoll.

29


Ziel: Jede L-widerspruchsfreie Theorie ist erfüllbar.

Lemma 5. Sei T L-widerspruchsvoll. Dann ist T $L ϕ für alle L-Aussagen ϕ.

Beweis. Sei ϕ L-Aussage. Sei nach Voraussetzung ψ L-Aussage mit T $L ψ und T $L ψ.Also

...Γ1ψ mit Γ1 � T

...Γ2 ψ mit Γ2 � T

(Ant) Γ1Γ2ψ

(Ant) Γ1Γ2 ψ

(Wid) Γ1Γ2ϕ

Lemma 6. Sei T L-Theorie, ϕ L-Aussage. Dann:

T $L ϕ ðñ T Y t ϕu L-widerspruchsvoll.

Beweis. “ñ“: Sei T $L ϕ. Dann auch T Y t ϕu $L ϕ. Aber auch T Y t ϕu $L ϕ, denn ϕ ϕ ist ableitbar nach (Vor). Also T Y t ϕu L-widerspruchsvoll.“ð“: Sei TYt ϕu L-widerspruchsvoll. Also nach Lemma 5 TYt ϕu $L ϕ. Also existiert

eine Sequenz Γ � T Y t ϕu mit Γϕ ableitbar. Dann nach (Ant) Γ1 ϕϕ ableitbar für einΓ1 � T . Also

...Γ1 ϕϕ

(Vor) Γ1ϕϕ

(FU) Γ1ϕ

Also T $L ϕ

Lemma 7. Sei M � H Menge von L-widerspruchsfreien Theorien mit der Eigenschaft:

für alle T, T 1 PM : pT � T 1 oder T � T 1q

Dann ist�

M L-widerspruchsfrei.

Beweis. Setze T ��

M. Annahme: T ist L-widerspruchsvoll. Dann existiert nach Endlich-keitssatz endliches ∆ � T mit ∆ ist L-widerspruchsvoll. Dann existieren T0, . . . , Tn P Mmit ∆ � T0 Y . . . Y Tn. Nach Voraussetzung existiert aber i mit T0 Y . . . Y Tn � Ti. Dannist aber Ti L-widerspruchsvoll. Widerspruch zur Voraussetzung.

30


Lemma 8. Sei T L-Theorie. Sei L� � LYC, wobei C Menge von neuen Konstanten. Danngilt:

für alle L-Aussagen ϕ : T $L� ϕñ T $L ϕ

Insbesondere also: T L-widerspruchsfrei ñ T L�-widerspruchsfrei.

Beweis. Zeige zuerst

p1q Sei pΓ0, . . . ,Γnq eine Ableitung in KL� .

Beweis. Seien c1, . . . , ck alle Elemente von C, die in Γi vorkommen. Seien y1, . . . , yk paar-weise verschiedene Variablen, die in keinem Γi vorkommen. Γi entstehe aus Γi, indem manüberall cj durch yj ersetzt (für 1 ¤ j ¤ k). Dann ist pΓ0, . . . ,Γnq eine Ableitung in KL.mühselig, aber klar (hier nicht ausgeführt).

Aus (1) folgt aber die Behauptung. Denn sei etwa T $L� ϕ. Sei Γϕ ableitbar in KL� mitΓ � T . Sei also pΓ0, . . . ,Γnq eine Ableitung in KL� mit Γn � Γϕ. Bilde Γi wie in (1). Dannist also pΓ0, . . . ,Γnq eine Ableitung in KL. Aber Γn � Γn � Γϕ. Also gilt T $L ϕ.

Lemma 9. Sei T L-widerspruchsfreie L-Theorie. Sei L� die zugehörige Henkinsprache (vgl.Kapitel 2 Lemma 3). Dann ist T Y TLH L�-widerspruchsfrei.

Beweis. zur Erinnerung: Wir hatten in Kapitel 2, Lemma 3 definiert:

C0 � H

Ci�1 � Ci Y tci,ϕ,x | ϕ Li-Formel mit höchstens x freiu

Dabei Li � LY Ci. L� ��iPN Li.

TLH � tpDx ϕÑ ϕxpci,ϕ,xqq | i P N, ϕ Li-Formel mit höchstens x freiu

Setze T i � tpDx ϕÑ ϕxpci,ϕ,xqq | ϕ Li-Formel mit höchstens x freiu

Sei T0 � T und Ti�1 � Ti Y T i. Dann ist T Y TLH ��iPN Ti. Wegen Lemma 7 genügt es zu

zeigen: für alle i ist Ti L�-widerspruchsfrei. Dies machen wir durch Induktion über i.i � 0: nach Lemma 8iÑ i� 1: wegen Endlichkeitssatz genügt es zu zeigen:

falls ψ1, . . . , ψn P T i, so Ti Y tψ1, . . . , ψnu L�-widerspruchsfrei

Hierzu machen wir Induktion über n:n � 0 Nach Induktionsvoraussetzung ist Ti L�-widerspruchsfrei.n Ñ n � 1: Seien ψ1, . . . , ψn�1 P T i gegeben. Setze T � Ti Y tψ1, . . . , ψnu, ψ � ψn�1.

ψ hat die Form Dx ϕÑ ϕxpcq.Es genügt zu zeigen: Falls σ L-Aussage, so: pT Y tψu $L� σ ñ T $L� σq. Sei hierzu

T Y tψu $L� σ mit σ L-Aussage. Also existiert nach (Ant) Γ � T mit

Γp Dx ϕ_ ϕxpcqqσ L�-ableitbar

31


Fixiere hiervon eine Ableitung. Sei y eine Variable, die nicht in dieser Ableitung vorkommt.Also existiert nach (1) aus dem Beweis von Lemma 8 eine L�-Ableitung

...Γp Dx ϕ_ ϕxpyqqσ

da c nicht in Γσ vorkommt. Diese Ableitung verlängern wir nun.

...Γp Dx ϕ_ ϕxpyqqσ p1q

(Vor) Γ Dx ϕ Dx ϕ p2q(vS) Γ Dx ϕp Dx ϕ_ ϕxpyqq p3q

(1),(3), (KS) Γ Dx ϕσ p4q(Vor) Γϕxpyqϕxpyq p5q(vS) Γϕxpyqp Dx ϕ_ ϕxpyqq p6q

(1),(6), (KS) Γϕxpyqσ p7qy nicht in ΓDx ϕσ, (EA) ΓDx ϕσ p8q

(4),(8), (FU) Γσ

Also T $L� σ, da Γ � T .

Lemma 10. Sei T L-Theorie, T L-widerspruchsfrei und sei ϕ eine L-Aussage. Dann gilt

T Y tϕu ist L-widerspruchsfrei oder T Y t ϕu ist L-widerspruchsfrei.

Beweis. (Beweis durch Widerspruch) Annahme: T Ytϕu, T Yt ϕu L-widerspruchsvoll. Wirzeigen: T $L ψ für alle L-Aussage ψ, also T L-widerspruchsvoll.Sei ψ gegeben. Nach Lemma 5 existieren Γ1 � T Y tϕu und Γ2 � T Y t ϕu mit Γ1ψ und

Γ2ψ L-ableitbar. Mit (Ant) erhält man dann Γ � T mit Γϕψ und Γ ϕψ L-ableitbar. Alsomit (FU) ist Γψ L-ableitbar. Also T $L ψ.

08.12.2011

Lemma 11. Sei T L-widerspruchsfreie L-Theorie. Dann sind äquivalent:

(1) T ist L-vollständig

(2) Falls T 1 L-widerspruchsfreie L-Theorie mit T � T 1, so T 1 � T (d.h. T ist maximaleL-widerspruchsfreie L-Theorie)

Beweis. (1)ñ(2): Sei T 1 wie in (2). Annahme T 1 � T . Sei dann ϕ P T 1 � T . Wegen TL-vollständig ist dann ϕ P T . Also tϕ, ϕu � T 1. Dann ist aber T 1 L-widerspruchsvoll. (2)ñ(1): T erfülle (2). Sei ϕ L-Aussage. Nach Lemma 10 ist dann T Ytϕu oder T Yt ϕu

L-widerspruchsfrei. Dann aber T � TYtϕu oder T � TYt ϕu, d.h. ϕ P T oder ϕ P T .

32


Lemma 12. Sei T L-widerspruchsfreie L-Theorie. Dann existiert L-Theorie T 1 � T mitT 1 ist L-widerspruchsfrei und L-vollständig.

Beweis. Setze K � tT 1 | T � T 1 und T 1 ist widerspruchsfreiu. Wegen Lemma 7 besitzt nachZornschem Lemma K ein maximales Element T 1. T 1 ist dann wie gewünscht nach Lemma11.

Lemma 13. Sei T L-widerspruchsfreie, L-vollständige L-Theorie. Sei ϕ eine L-Aussage.Dann gilt:

pT $L ϕñ ϕ P T q

Beweis. Sei T $L ϕ. Annahme: ϕ R T . Wegen T L-vollständig ist dann ϕ P T . Dann aberauch T $L ϕ nach (Vor). Also ist T L-widerspruchsvoll.

Lemma 14. Sei T L-vollständige, L-widerspruchsfreie L-Henkintheorie. Dann ist T erfüll-bar.

Beweis. Wir zeigen: T erfüllt (M1)-(M4) (für L). Dann folgt die Behauptung nach Kapitel 2Satz 2.

Zu (M1) Seien s1, . . . , sn, t1, . . . , tn konstante L-Terme(a) s1 � sa P T , da $L s1 � ss nach (GL1) und nach Lemma 13(b) Sei s1 � s2 P T . Nun s1 � s2 $L s2 � s1 nach (GL2). Also s2 � s1 P T nach

Lemma 13(c) Seien s1 � s2, s2 � s3 P T . Nun ts1 � s2, s2 � s3u $L s1 � s3 nach (GL3). Also

s1 � s3 P T nach Lemma 13(d) Sei f P FunknL und s1 � t1, . . . , sn � tn P T . Dann ts1 � t1, . . . , sn � tnu $L

fps1, . . . , snq � fpt1, . . . , tnq nach (GL4). Also fps1, . . . , snq � fpt1, . . . , tnq nachLemma 13.

(e) Sei R � RelnL und s1 � t1, . . . , sn � tn P T . Zu zeigen: Rps1, . . . , snq P T ðñRpt1, . . . , tnq P T .“ñ“: SeiRps1, . . . , snq P T . Nun ts1 � t1, . . . , sn � tn, Rps1, . . . , snqu $L Rpt1, . . . , tnq.Also Rpt1, . . . , tnq P T nach Lemma 13“ð“: Sei Rpt1, . . . , tnq P T . Wegen (M1)(b) ist t1 � s1, . . . , tn � sn P T . Alsonach “ñ“ auch Rps1, . . . , snq P T

Zu (M2) Sei ϕ L-Aussage. Zu zeigen: ϕ P T ðñ ϕ R T . “ñ“: Sei ϕ P T . Wegen TL-widerspruchsfrei ist dann ϕ R T . “ð“: Sei ϕ R T . Wegen T L-vollständig ist dann ϕ P T .

33


Zu (M3) Seien ϕ,ψ L-Aussagen. Zu zeigen: pϕ _ ψq P T ðñ pϕ P T oder ψ P T q.“ð“: 1. Fall: ϕ P T . Dann T $L pϕ_ ψq, da

(Vor) ϕϕ(vS) ϕpϕ_ ψq

Also pϕ_ ψq P T nach Lemma 13. 2. Fall: ψ P T . Dann wieder T $L pϕ_ ψq, da

(Vor) ψψ(vS) ψpϕ_ ψq

Also pϕ_ ψq P T nach Lemma 13.“ñ“: Sei pϕ_ ψq P T . Wir zeigen:

T Y tϕu L-widerspruchsfrei oder T Y tψu L-widerspruchsfrei

Wegen T L-vollständig und L-widerspruchsfrei, folgt dann nach Lemma 11 pϕ PT oder ψ P T q. Annahme: T Y tϕu, T Y tψu L-widerspruchsvoll. Wir zeigen $L σfür alle L-Aussagen σ, was ein Widerspruch ist. Sie hierzu σ L-Aussage. Nach Annah-me existieren Γ1 � T Y tϕu,Γ2 � T Y tψu. Γ1σ, Γ2σ L-ableitbar. Also existiert nach(Ant) Γ � T mit Γϕσ, Γψσ L-ableitbar. Also nach (vA) Γpϕ_ψqσ L-ableitbar. SomitT $L σ, da Γ � T , pϕ_ ψq P T .

Zu (M4) Sei Dx ϕ L-Aussage. Zu zeigen: Dx ϕ P T ðñ es existiert ein konstanter L-Termt mit ϕxptq P T . “ð“: Sei ϕxptq P T . Aus (Vor) und (DS) folgt aber, dass ϕxptqDx ϕL-ableitbar ist. Also Dx ϕ P T nach Lemma 13. “ñ“: Sei Dx ϕ P T . Wegen T L-Henkintheorie existiert eine Konstante c mit pDx ϕÑ ϕxptqq P T . Nun gilt aber

p�q Dx ϕp Dx ϕ_ ϕxpcqqϕxptq ist L-ableitbar, denn:

(Vor) ϕxpcqϕxpcq p1q(Ant) Dx ϕ ϕxpcqϕxpcq p2q(Vor) Dx ϕ Dx ϕDx ϕ p3q(Vor) Dx ϕ Dx ϕ Dx ϕ p4q

(3),(4), (Wid) Dx ϕ Dx ϕ ϕxpcq p5q(5),(2), (vA) Dx ϕp ϕx ϕ_ ϕxpcqqϕxpcq

Wegen (*) ist aber T $L ϕxpcq, da Dx ϕ, p Dx ϕ _ ϕxpcqq P T . Also ϕxpcq P T nachLemma 13.

Satz 15. Sei T L-widerspruchsfreie L-Theorie. Dann ist T erfüllbar.

34


Beweis. Sei L� wie in Lemma 9. Nach Lemma 11 existiert dann L�-Theorie T � � T mitT � ist L�-widerspruchsfrei und L�-vollständig. Wegen T � � TLH ist aber T � auch L�-Henkintheorie. Somit ist T � erfüllbar. Nach Lemma 14. Also T erfüllbar, da T � T �.

Satz 16 (Gödelscher Vollständigkeitssatz für KL). Sei T L-Theorie, ϕ L-Aussage. Dann:

pT $L ϕ ðñ T |ù ϕq

Beweis. “ñ“: Da KL korrekt nach Satz 4 folgt die Behauptung aus Lemma 3.“ð“: Es gelte non T $L ϕ. Dann ist nach Lemma 6 T Y t ϕu L-widerspruchsfrei. Also

T Y t ϕu erfüllbar nach Lemma 14. Somit non T |ù ϕ.

Korollar 17. Sei T L-Theorie, ϕ L-Aussage und L Sprache erster Stufe mit L � L. Dann

pT $L ϕ ðñ T $L ϕq

Beweis. T $L ϕ ðñ T |ù ϕ ðñ T $L ϕ

Notation. Schreibe daher im folgenden “T $ ϕ“ statt “T $L ϕ“. Schreibe außerdem“widerspruchsfrei“ statt “L-widerspruchsfrei“.

Bemerkung. Der Kompaktheitssatz folgt unmittelbar aus Satz 16

Frage 1. Sei ϕ L-Aussage. Ist es effektiv entscheidbar, ob ϕ allgemeingültig ist?Wir werden zeigen: nein.Hierzu benötigen wir eine exakte Definition von effektiv entscheidbar.

Frage 2. Sei A � pN,�, �, 0, 1q, L zugehörige Sprache. Kann man effektiv eine L-TheorieT angeben mit:

für alle L-Aussagen ϕ: pA |ù ϕ ðñ T $ ϕq

Ein Kandidat für T sind die Peano-Axiome:Sei PA (die Peano-Arithmetik) die folgende Theorie

(P1) @x x� 0 � x

(P2) @x @y x� py � 1q � px� yq � 1

(P3) @x x� 1 � 0

(P4) @x @y px� 1 � y � 1 Ñ x � yq

(P5) @x x � 0 � 0

(P6) @x @y x � py � 1q � x � y � x

Schließlich für L-Formeln ϕ mit höchstens x1, . . . , xn, y frei

(P7)ϕ @x1 . . .@xnppϕyp0q ^ @y pϕÑ ϕypy � 1qq Ñ @y ϕq

Offenbar ist A ein Modell von PA. Wir werden aber zeigen:

Es existiert ϕ mit A |ù ϕ und PA & ϕ13.12.2011

35

4 Rekursive Funktionen

4 Rekursive FunktionenDefinition. • Für R � Nn pn ¥ 1q definiere n-stellige Funktion KR : Nn Ñ N durch

KRp~aq �

#0 , falls Rp~aq1 , sonst

die charakteristische Funktion von R.

• Für 1 ¤ i ¤ n definiere Ini : Nn Ñ N durch

Ini pm1, . . . ,mnq � mi

• Definiere den µ-Operator: Sei R eine n � 1-stellige Relation auf N mit pn ¥ 1q mitder Eigenschaft

für alle ~a P Nn existiert m mit Rp~a,mq

F p~aq � µm : Rp~a,mq bedeutet dann: F p~aq � das kleinste m mit Rp~a,mq.

Definition. Eine Funktion f : Nn Ñ N pn ¥ 1q ist rekursiv, wenn sie durch Anwendung derfolgenden Schemata erzeugt wird

(R1) Ini ,�, �,K sind rekursiv

(R2) Falls G,H1, . . . ,Hk rekursiv, so auch F , definiert durch F p~aq � GpH1p~aq, . . . ,Hkp~aqq

(R3) Ist G rekursiv mit: für alle ~a existiert m mit Gp~a,mq � 0, so auch F definiert durchF p~aq � µm : Gp~a,mq � 0

Bemerkung. Jede rekursive Funktion ist “berechenbar“.Churchsche These: Jede “berechenbare“ Funktion von Nn nach N ist rekursiv. Hierfür gibt

es gewisse Evidenz.

Definition. Eine n-stellige Relation R � Nn pn ¥ 1q ist rekursiv, falls KR rekursiv ist.Weitere (abgeleitete) Regeln:

(R4) Seien Q rekursive Relation, H1, . . . ,Hk rekursive Funktionen und P definiert durchP p~aq ðñ QpH1p~aq, . . . ,Hkp~aqq. Dann ist P rekursiv.

Beweis. KP p~aq � KQpH1p~aq, . . . ,Hkp~aqq. Also folgt die Behauptung aus (R2).

(R5) Sei P rekursive Relation mit:

für alle ~a existiert m mit P p~a,mq

Sei F definiert durch F p~aq � µm : P p~a,mq. Dann ist F rekursiv.

36


Beweis. F p~aq � µm : KP p~a,mq � 0. Also rekursiv nach (R3).

(R6) Die rekursiven Funktionen sind abgeschlossen unter beliebigen Kompositionen.

Beispiel. Seien G,H,K rekursiv und F definiert durch

F pa, b, cq � GpHpb, cq,KpGpb, c, cq, aq, cq

Dann ist F rekursiv.

Beweis. Definiere F1, . . . , F6 durch

F1pa, b, cq � a F3pa, b, cq � c F5pa, b, cq � Gpb, c, cq

F2pa, b, cq � b F4pa, b, cq � Hpb, cq F6pa, b, cq � KpGpb, c, cq, aq

Dann sind F1, F2, F3 rekursiv, da Fi � I3i für 1 ¤ i ¤ 3. Aber

F4pa, b, cq � HpF2pa, b, cq, F3pa, b, cqq

Also F4 rekursiv nach (R2). Analog folgt, dass F5 rekursiv ist. Also F6 rekursiv nach(R2). Schließlich

F pa, b, cq � GpF4pa, b, cq, F6pa, b, cq, F3pa, b, cqq

Also F rekursiv nach (R2).

(R7) Jede konstante Funktion ist rekursiv.

Beweis. Sei n ¥ 1 fest und Fk die n-stellige Funktion auf Nn mit konstantem Wert k.Zeige durch Induktion über k, dass Fk rekursiv ist.k � 0: F0p~aq � µm : In�1

n�1 p~a,mq � 0k Ñ k � 1: Fk�1p~aq � µm : K pFkp~a,mq,mq � 0

(R8) Seien P,Q � Nn rekursiv. Dann sind Nn � P, P YQ,P XQ rekursiv.

Beweis. Setze P � Nn � P . Dann

KP p~aq � K p0,Kpp~aqq

KPYQp~aq � KP p~aq �KQp~aq

Schließlich P XQ � Nn � ppNn � P q Y pNn �Qqq.

(R9) ,¤,¡,¥,� sind rekursiv.

37


Beweis. ist rekursiv nach (R1). Also ist ¡ rekursiv nach (R6), da K¡pa, bq �K pb, aq. ¤ ist das Komplement von ¡, also rekursiv nach (R8). Somit nach (R6) auch¥ rekursiv. Aber � ist der Durchschnitt von ¤ und ¥, also rekursiv nach (R8).

(R10) Sei R rekursiv und P,Q definiert durch

P p~a, bq ðñ es existiert c b mit Rp~a, cqQp~a, bq ðñ für alle c b Rp~a, cq

Dann sind P,Q rekursiv.

Beweis. Setze F p~a, bq � µc : pRp~a, cq oder c � bloooooooooomoooooooooonrekursiv

qAlso ist F rekursiv. Aber P p~a, bq ðñ

F p~a, bq b. Also ist P rekursiv. Weiterhin Qp~a, bq ðñ non es existiert c b mit non Rp~a, cq. Also ist auch Q rekursiv.

(R11) Definiere � durch

a� b �

#a� b , falls a ¥ b

0 , falls a bfür a, b P N

Dann ist � rekursiv.

Beweis. a� b � µc : pb� c � a oder a bloooooooooooomoooooooooooonrekursiv

q

(R12) Seien G1, . . . , Gk rekursive Funktionen und R1, . . . , Rk rekursive Relationen mit

für alle ~a existiert genau ein 1 ¤ i ¤ k mit Rip~aq

Definiere F durch F p~aq � Gip~aq ðñ Rip~aq. Dann ist F rekursiv.

Beweis. Setze Ri � Nn �Ri. Dann gilt

F p~aq � G1p~aq �KR1p~aq � . . .�Gkp~aq �KRk

p~aq

(R12) gilt entsprechend für Relationen.

Bemerkung. Sei F : Nn Ñ N. Setze G � Graph von F � tp~a, F p~aqq | ~a P Nnu � Nn�1.Dann gilt: F ist rekursiv ðñ G ist (als Relation) rekursiv.

Beweis. “ñ“: p~a,mq P G ðñ F p~aq � m. “ð“: F p~aq � µm : Gp~a,mq.

38


nächstes Ziel: Sei G rekursiv, a P N und F definiert durch

F p0q � a

F pn� 1q � GpF pnqq

Dann ist F rekursiv.Wir könnten also ein allgemeines Schema dieser Art in die Definition der rekursiven Funk-

tionen hineinnehmen. Für spätere Zwecke ist es jedoch wichtig, dass dies nicht notwendigist.Für unser Ziel benötigen wir eine rekursive Kodierung der endlichen Folgen von natürli-

chen Zahlen durch natürliche Zahlen. Am natürlichsten würde dies mit Hilfe der eindeutigenPrimfaktorzerlegung der natürlichen Zahlen gehen. Aber wir können bis jetzt noch nicht zei-gen, dass die Exponentiation rekursiv ist.Also gehen wir anders vor. 15.12.2011

Bemerkung 1. Sei π : N2 Ñ N definiert durch

πpa, bq � pa� bqpa� bq � a� 1

Dann gilt:

(1) π ist rekursiv

(2) πpa, bq ¡ a, b

(3) π ist injektiv

Beweis. (1),(2) sind klar.Zu (3): Sei πpa, bq � πpc, dq. Zeige zuerst a � b � c � d. (Bew. d. Wid.) Annahme:

a�b � c�d. Dann o.E. a�b c�d. Dann aber πpa, bq ¤ pa�b�1q2 ¤ pc�dq2 πpc�dq. Wegen a � b � c � d folgt aber dann aus πpa � bq � πpc � dq, dass a � c, also auch

b � d.

Bemerkung 2. Es existieren rekursive Funktionen π1, π2 : NÑ N mit

(1) π1pπpa, bq � a

(2) π2pπpa, bqq � b

(3) πipaq ¤ a� 1 für i � 1, 2

Beweis. Sei einfach

π1pcq � µm : pp es existiert n c mit πpm,nq � cq oder m � c� 1qq

π2pcq � µn : pp es existiert n c mit πpm,nq � cq oder m � c� 1qq

Dies tut’s.

39


Bemerkung 3. Definiere r : N2 Ñ N durch

rpm,nq �

#dasjenige i n mit m � k � n� i für ein k , falls n � 0

0 , sonst

Offenbar ist r rekursiv, denn falls n � 0, so:

rpm,nq � µi : pi n und es existiert ein k ¤ m mit m � k � n� iq

Bemerkung 4 (Chinesischer Restsatz). Seien a0, . . . , an paarweise teilerfremd. Seienb0, . . . , bn P N gegeben mit bi ai. Dann existiert c P N mit rpc, aiq � bi für i � 0, . . . , n.

Beweis. Sei m � a0 � . . . � an. Setze M � t0, . . . ,m� 1u, Ni � t0, . . . , ai � 1u für i ¤ n undN � N0 � . . .�Nn. Definiere f : M Ñ N durch

fpcq � prpc, a0q, . . . , rpc, anqq

Dann gilt f ist injektiv. p�q

Beweis. Seien c1 c2 m. Annahme: fpc1q � fpc2q. Sei i ¤ n. Dann ist aber rpc1, aiq �rpc2, aiq �: d. Dann existieren aber k1 k2 mit cj � kjai � d pj � 1, 2q.Also ai teilt c2 � c1. Wegen a0, . . . , an paarweise teilerfremd. Dann aber m � a0 � . . . � an

teilt c2 � c1. Dies ist aber Widerspruch zu 0 c2 � c1 m.

Nun haben aber M,N beide m Elemente. Also ist f auch surjektiv. Somit existiert c P Nmit fpcq � pb0, . . . , bnq. Dies ist die Behauptung.

Bemerkung 5. Seien 1 ¤ k j n. Dann sind 1� kn!,1� jn! teilerfremd.

Beweis. Offenbar gilt: (+) Falls m � 1 teilt 1� in!, so ist m ¡ n

Beweis. Ist m ¤ n, so m teilt in!. Also m teilt nicht 1 � in!. Nehme nun an, dass 1 � kn!,1� jn! nicht teilerfremd sind. Dann haben sie einen gemeinsamen Primteiler p. Wegen (+)gilt p ¡ n. Andererseits teilt p auch p1� jn!q � p1� kn!q � pj � kq � n!. Wegen p prim alsop ¤ n.

Lemma 1. Es existiert rekursive Funktion β mit den Eigenschaften:

(1) für alle a, i βpa, iq ¤ a� 1

(2) für alle b0, . . . , bn P N existiert a mit βpa, iq � bi für alle i ¤ n

40


Beweis. Setze βpa, iq � rpπ1paq, 1 � pi � 1q � π2paqq. β ist rekursiv, da r, π1, π2 rekursiv.Offenbar ist (1) erfüllt, da nach Bemerkung 2 πipaq ¤ a� 1.Setze m � maxtb0, . . . , bmu und ai � 1� pi� 1q �m!, für i ¤ n. Nach Bemerkung 5 sind

a0, . . . , an paarweise teilerfremd. Außerdem bi ai. Also existiert nach Bemerkung 4 ein cmit rpc, aiq � bi für i ¤ n. Setze nun a � πpc,m!q. Dann für i ¤ n

βpa, iq � rpπ1paq, 1� pi� 1q � π2paqq � rpc, 1� pi� 1q �m!q � rpc, aiq � bi

Definition. Mithilfe der β-Funktion können wir nun auf rekursive Weise endliche Folgenvon natürlichen Zahlen durch natürliche Zahlen kodieren. Sei hierzu β wie in Lemma 1. Fürb1, . . . , bn P N setze

xb1, . . . , bny � µa : pβpa, 0q � n und βpa, 1q � b1 und . . . und βpa, nq � bnq

Setze noch `paq � βpa, 0q, paqi � βpa, i� 1q. Es gilt also:

`pxb1, . . . , bnyq � n

pxb1, . . . , bnyqi � bi�1 für i n

Außerdem: Für festes n ¥ 1 gilt:

pb1, . . . , bnq ÞÑ xb1, . . . , bny ist rekursiv

` ist rekursivDie Funktion pa, iq ÞÑ paqi ist rekursiv. Setze schließlich

Seq � ta | es existiert b1, . . . , bn mit a � xb1, . . . , bnyu

Seq ist rekursiv, denn:

a P Seq ðñ für alle b a p`pbq � `paq oder es existiert i `paq pbqi � paiqq

Weiterhin definiere Anf durch:

Anfpa, iq � µb : p`pbq � i und für alle j i pbqj � paqjq

Anf ist also rekursiv, und es gilt

Anfpxb1, . . . , bny, iq � xb1, . . . , biy für i ¤ n

Schließlich definiere noch die Verknüpfung � durch:

a � b � µc : p`pcq � `paq � `pbq und für alle i `paq pcqi � paqi

und für alle i `pbq pcq`paq�i � pbqiq

Es gilt also: � ist rekursiv.

xa1, . . . , any � xb1, . . . , bmy � xa1, . . . , an, b1, . . . , bmy

41


20.12.2011

Definition. Falls f : Nn Ñ N definiere xfy : NÑ N durch

xfypaq � fppaq0, . . . , paqn�1q

Analog für Relation P � Nn sei xP y � N definiert durch

xP ypaq ðñ P ppaq0, . . . paqn�1q

Bemerkung. f rekursiv ðñ xfy rekursiv.

Beweis. “ñ“: Klar. “ð“: fpa0, . . . , anq � xfypxa0, . . . , anyq. Sei f : Nn�1 Ñ N , n ¥ 0Definiere f : Nn�1 Ñ N durch fpn,~aq � xfp0,~aq, . . . , fpn� 1,~aqy

Bemerkung. f rekursiv ðñ f rekursiv.

Beweis. “ñ“: fpm,~aq � µc : pfpcq � m und für alle i mpcqi � fpi,~aqq“ð“: fpm,~aq �

�fpm� 1,~aq

�m

Satz 2 (Wertverlaufsatz). Sei g rekursive Funktion und f die eindeutig bestimmte Funktionmit

fpn,~aq � gpfpn,~aq,~aq

Dann ist f rekursiv.

Beweis. Es genügt zu zeigen, dass f rekursiv ist. Aber:

fpn,~aq � µc : pSeqpcq und `pcq � n und für alle i n : pcqi � gpAnfpc, iq,~aqq

Bemerkung. Die primitive Rekursion ist ein Spezialfall von Satz 2, d.h. es gilt folgendes:Seien b1, b2 rekursiv und f definiert durch

fp0,~aq � b1p~aq

fpn� 1,~aq � b2pfpn,~aq, n,~aq

Dann ist f rekursiv.

Beweis. Definiere g durch rekursive Fallunterscheidung wie folgt:

gpc,~aq �

#b1p~aq , falls `pcq � 0

b2ppcq`pcq�1, `pcq,~aq , falls `pcq ¡ 0

Dann ist g rekursiv. Andererseits ist f die Lösung der Rekursionsgleichung

fpn,~aq � gpfpn,~aq,~aq

Also ist f rekursiv nach Satz 2.

42


Definition. Sei R � Nn. R ist rekursiv aufzählbar, wenn es ein rekursives Q � Nn�1 gibtmit:

für alle ~a : Rp~aq ðñ es existiert b mit Qp~a, bq

Bemerkung. R rekursiv ñ R rekursiv aufzählbar.

Beweis. Wähle einfach in Definition Q � R� N.

Lemma 3. Sei R � N, R � H. Dann sind äquivalent

(1) R ist rekursiv aufzählbar.

(2) es existiert rekursive Funktion f : NÑ N mit R � rngpfq � tfpnq | n P Nu

Beweis. (2)ñ(1): Sei R � rngpfq mit f rekursiv. Dann

m P R ðñ es existiert n mit m � fpnqloooomoooonrek. Rel.

(1)ñ(2): Sei Q rekursiv mit:

m P R ðñ es existiert n mit Qpm,nq

Weiterhin sei etwa b festes Element von R (beachte R � H).

Definiere f durch fpaq �#

b , falls non Qppaq0, paq1qpaq0 , falls Qppaq0, paq1q

f ist rekursiv. Aber R � rngpfq, denn:“�“: Sei m P R. Dann existiert n mit Qpm,nq. Setze a � xm,ny. Dann also Qppaq0, paq1q.

Somit m � paq0 � fpaq P rngpfq.“�“: Sei m � fpaq. Ist m � b, so m P R. Sei also m � b. Dann aber m � paq0 und

Qppaq0, paq1q. Also existiert n mit Qpm,nq, d.h. m P R.

Bemerkung. Ist f rekursiv und streng monoton, so ist rngpfq rekursiv.

Beweis. Es ist fpnq ¥ n für alle n. Also n P rngpfq ðñ es existiert m ¤ n, n � fpmq.Somit ist rngpfq rekursiv.

Satz 4. Sei R � Nn. Dann sind äquivalent:

(1) R ist rekursiv.

(2) R und Nn �R sind rekursiv aufzählbar.

43

5 Unentscheidbarkeit, Unvollständigkeit

Beweis. (1)ñ(2): Klar. (2)ñ(1): Seien Q1, Q2 rekursiv mit

Rp~aq ðñ es existiert b mit Q1p~a, bq

non Rp~aq ðñ es existiert b mit Q2p~a, bq

Dann existiert b für alle ~a mit Q1p~a, bq oder Q2p~a, bq. Also ist g definiert durch

gp~aq � µb : pQ1p~a, bq oder Q2p~a, bqq

rekursiv. Aber offenbar Rp~aq ðñ Q1p~a, gp~aqq. Also R rekursiv.

Frage. Ist jede rekursiv aufzählbare Menge rekursiv? Ñ Nein, Beweis folgt.

5 Unentscheidbarkeit, UnvollständigkeitWir benutzen hier aus technischen Gründen eine andere β-Funktion zur Kodierung endlicherFolgen: Definiere zuerst durch Rekursion

ppnq � die n-te Primzahl

p ist rekursiv. Außerdem ist die Exponentiation rekursiv. Hierzu benötigen wir schon dieWertverlaufsrekursion. Definiere nun β1 : N2 Ñ N durch

β1pa, iq � µm :�ppiqm�1 ist kein Teiler von a

�β1 ist rekursiv, und es gilt auch:

(1)’ β1pa, iq ¤ a� 1

(2)’ für alle b0, . . . , bn P N existiert a mit β1pa, iq � bi für alle i ¤ n

Für (2)’ setze nämlich einfach a � pp0qb0 � . . . � ppnqbn . Dieses a ist auch das kleinste solche.Benutze nun diese Funktion β1 zur Definition von xa1, . . . , any, Seq, usw. Es gilt also dann

xa1, . . . , any � pp0qn � pp1qa1 � . . . � ppnqan

Somit gilt zusätzlich: Falls k n und 1 ¤ i1 i2 . . . ik ¤ n, so

xai1 , ai2 , . . . , aiky xa1, . . . , any Außerdem a xay.

Diese Eigenschaften benutzen wir im Folgenden ohne Kommentar. 22.12.2011

Definition. Wir kodieren nun eine feste endliche Sprache 1. Stufe. Sei also L eine endlicheSprache 1. Stufe. Sei SN : LÑ N injektiv mit: für alle i P N

SNpviq � 2i

44


wobei pviqiPN eine Aufzählung der Variablen sei. Es ist dann R � rngpSNq rekursiv, denn

R � t2i | i P Nu YA für eine endliche Menge A

SNpaq � die Symbolnummer von a.Definiere dann x y : Menge aller endlichen L-Zeichenreihen Ñ N durch

xa1, . . . , any � xSNpa1q, . . . , SNpanqy

xa1, . . . , any heißt die Gödelnummer von a1, . . . , an. x y ist injektiv. Wir identifizieren daheroft a1, . . . , an mit xa1, . . . , any. Insbesondere heißt A �Menge aller L-Zeichenreihen rekursiv,wenn txsy | s P Au rekursiv ist.

Bemerkung. Z � Menge aller L-Zeichenreihen ist rekursiv.

Beweis. R � rngpSNq ist rekursiv. Aber: n P Z ðñ Seqpnq und für alle i n pnqi P R

Lemma 1. TermL, FormL, AussL, SeqL sind rekursiv. (Wobei AussL � Menge allerL-Aussagen, SeqL � Menge aller L-Sequenzen)

Beweis. mühselig, aber im Prinzip einfach. Wir führen den Beweis nur für TermL durch:Seien f0, . . . , fk�1 die Funktionszeichen von L, fi ni-stellig. Sei K � tSNpcq | c P

KonstLu, K ist endlich, also rekursiv. Außerdem V ar � t2i | i P Nu ist rekursiv. Nunkann aber TermL rekursiv definiert werden durch:

n P TermL ðñ�Seqpnq und `pnq � 0 und�p`pnq � 1 und pnq0 P K Y V arq oder es existiert i k :�pnq0 � SNpfiq und es existieren a0, . . . , an n :�TermLpa1q ^ . . .^ TermLpaniq und

n � xSNpfiqy � xSNppqy � a1 � xSNp, qy � a2 � . . . � ani � xSNpqqy��

Also ist TermL rekursiv. Analog: FormL ist rekursiv. Zeige noch: Ist Frei definiert durch

Freipm,nq ðñ m P V ar, n P FormL, und m kommt in n frei vor

so ist Frei rekursiv. Dann: n P AussL ðñ pn P FormL und für alle m n : non Freipm,nqqSchließlich: n P SeqL ðñ

pn P FormL oder es existiert m, k n mit SeqLpmq und FormLpkq und n � m � kq

45


Lemma 2. Es existiert rekursive Funktion Sub mit der Eigenschaft:

falls ϕ L-Formel, x Variable, t L-Term, so Subpxϕy, SNpxq, xtyq � xϕxptqy

Beweis. Klar.

Lemma 3. Die Regeln von KL sind rekursiv.

Beweis. z.B. für (FU): Γψϕ Γ ψϕΓϕ

Rpn1, n2, n3q ðñ es existiert m, k, j n1 mit SeqLpmq oder m � x y, FormLpkq, FormLpjq

und n1 � m � k � j und n2 � m � xSNp qy � k � j und n3 � m � j

Definition. Der Kalkül KL hat 14 Regeln. Davon sind 6 0-stellig, 5 1-stellig und 3 2-stellig.Zähle diese so durch, dass KL die Regeln R1�R14 enthält, wobei R1�R6 0-stellig, R7�R111-stellig und R12 �R14 2-stellig. Wir können dann Abl definieren durch:

Ablpnq ðñ�Seqpnq und `pnq � 0 und für alle i `pnq :�SeqLppnqiq und

��R1ppnqiq oder . . . oder R6ppnqiq

�oder

es existiert j i mit�R7ppnqj , pnqiq oder . . . oder R11ppnqj , pnqiq

�oder

es existieren k, j i mit�R12ppnqk, pnqj , pnqiq oder . . . oder R14ppnqk, pnqj , pnqiq

��Abl ist also rekursiv und:

Ablpnq ðñ n ist Kode einer L-Ableitung

Bemerkung. Es existieren rekursive Funktionen Ant, Sub mit der Eigenschaft:

Ist ϕ0, . . . , ϕn eine L-Sequenz, so Subpxϕ0 . . . ϕnyq � xϕny

Antpxϕ0 . . . ϕnyq � xxϕ0y, . . . , xϕn�1yy

Sei nun T eine L-Theorie. Definiere Prädikat BewT durch:

BewT pm,nq ðñ�Ablpmq und AussLpnq und Subppmq`pmq�1q � n

und für alle i `pAntppmq`pmq�1qq : Antppmq`pmq�1qi P T�

BewT pm,nq bedeutet also: m ist ein Beweis für n in der Theorie T

Lemma 4. Sei T rekursiv. Dann ist BewT rekursiv.

Beweis. Klar.

Definition. Setze nun ThmT � tϕ | ϕ L-Aussage, T $ ϕu.

46


Satz 5. Sei T rekursive L-Theorie. Dann ist ThmT rekursiv aufzählbar.

Beweis. Es giltn P ThmT ðñ es existiert m mit BewT pm,nq

und BewT ist rekursiv nach Lemma 4

Wir wollen insbesondere zeigen, dass für viele rekursive L-Theorien T ThmT nicht re-kursiv ist. Dazu müssen wir natürlich zumindestends zeigen, dass es rekursiv aufzählbareMengen gibt, die nicht rekursiv sind. 10.01.2012

Definition. Sei P � N rekursiv aufzählbar. P ist universell, wenn es eine rekursive Funktionf : N2 Ñ N gibt, mit der Eigenschaft:

Sei Q � N rekursiv. Dann existiert ` P N mit: für alle n: pQpnq ðñ P pfp`, nqq

Lemma 6. Sei P universelle, rekursiv aufzählbare Menge. Dann ist P nicht rekursiv.

Beweis. (durch Diagonalisierung) Sei f : N2 Ñ N wie in Definition von universell. Annahme:P ist rekursiv. Definiere dann Q durch:

Qpnq ðñ non P pfpn, nqq

Dann ist Q rekursiv. Also existiert ` mit:

für alle n : pQpnq ðñ P pfp`, nqq

Also: non P pfp`, `qq ðñ Qp`q ðñ P pfp`, `qq.

L enthalte nun eine Konstante 0 und ein einstelliges Funktionszeichen S (für Nachfolger).Definiere rekursive Folge von Termen sn durch:

s0 � 0sn�1 � Spsnq

Weiterhin sei num : NÑ N die rekursive Funktion mit numpnq � xsny.

Definition. Sei T L-Theorie. Sei R � Nn und ϕ L-Formel mit höchstens x1, . . . , xn frei inϕ. ϕ repräsentiert R in T , wenn gilt:

(R1) wenn Rpk1, . . . , knq, so T $ ϕ~xpsk1 , . . . , sknq.

(R2) wenn non Rpk1, . . . , knq, so T $ ϕ~xpsk1 , . . . , sknq.

R ist repräsentierbar in T , wenn es ein ϕ gibt mit ϕ repräsentiert R in T .Schließlich: ReprpT q ðñ jedes rekursive R � N ist repräsentierbar in T .

Satz 7. Sei T rekursiv, widerspruchsfrei und gelte ReprpT q. Dann ist ThmT universell.

47


Beweis. ThmT ist rekursiv aufzählbar nach Satz 5.Zur Universalität: Sei x eine feste Variable. Definiere f : N2 Ñ N durch

fp`, nq � Subp`, SNpxq, numpnqq

f ist rekursiv. Sei nun Q � N rekursiv. ϕ repräsentiere Q in T (mit der Variablen x). WegenT widerspruchsfrei gilt dann insbesondere:

für alle n : pQpnq ðñ T $ ϕxpsnqq

Denn: “ñ“: nach (R1). “ð“: indirekt:

non QpnqñpR2q T $ ϕxpsnqñT wid. frei non T $ ϕxpsnq

Nun ist aber xϕxpsnqy � Subpxϕy, SNpxq, numpsnqq � fpxϕy, nq

Also: für alle n: Qpnq ðñ ThmT pxϕxpsnqyq

ðñ ThmT pfpxϕy, nqq

Also ist ` � xϕy wie gewünscht.

Definition. Sei nun L0 � t0, S,�, �, u, wobei 0 Konstante, S einstelliges Funktionszei-chen, �, � zweistellige Funktionszeichen, zweistelliges Relationszeichen. Die L0-Theorie Nbesteht aus folgenden neun Axiomen:

(N1) @x Spxq � 0

(N2) @x@y pSpxq � Spyq Ñ x � yq

(N3) @x x� 0 � x

(N4) @x@y x� Spyq � Spx� yq

(N5) @x x � 0 � 0

(N6) @x@y x � Spyq � x � y � x

(N7) @x x 0

(N8) @x@y px Spyq ÐÑ x y _ x � yq

(N9) @x@y px y _ x � y _ y xq

Bemerkung. Sei A � pN, 0, S,�, �, q, wobei Spnq � n� 1. Dann ist A ein Modell von N .

Lemma 8. Sei A � pA, 0, S,�,�,4q ein Modell von N . Setze B � tsAn | n P Nu. Dann gilt

(1) B ist abgeschlossen unter S,�,� , also existiert Unterstruktur L von A mit B � Trägervon L.

48


(2) für alle a P A�B, b P B: b4 a

(3) Sei f : NÑ B definiert durch fpnq � sAn . Dann ist f : AÑL

Beweis. einfache Induktion.

Definition. Sei T L-Theorie Sei f : Nn Ñ N Funktion. Sei ϕ L-Formel mit höchstensx1, . . . , xn, y frei in ϕ. ϕ repräsentiert f in T (als Funktion), wenn gelten:

(FR1) für alle k1, . . . , kn: T $ ϕ~x,ypsk1 , . . . , skn , sfpk1,...,knqq

(FR2) für alle k1, . . . , kn: T $ @y pϕ~x,ypsk1 , . . . , skn , yq Ñ y � sfpk1,...,knqq

Lemma 9. Sei R � Nn. Dann gilt: R ist repräsentierbar in N ðñ KR ist repräsentierbarin N .

Beweis. “ñ“: ϕ repräsentiere R in N (mit ~x). Setze ψ � pϕ ^ y � 0q _ p ϕ ^ y � Sp0qq.Dann repräsentiert ψ KR in N , denn: Seien k1, . . . , kn P N und m � fpk1, . . . , knq.

zu (FR1) 1. Fall: Rpk1, . . . , knq. Dann N $ ϕ~xpsk1 , . . . , sknq, also N $ ψ~x,ypsk1 , . . . , skn , s0qund 0 � KRpk1, . . . , knq.2. Fall: non Rpk1, . . . , knq: Dann N $ ϕpsk1 , . . . , sknq, also N $ ψ~x,ypsk1 , . . . skn , s1qund 1 � KRpk1, . . . , knq

zu (FR2) Offenbar N $ @y pψ~x,ypsk1 , . . . , skn , yq Ñ y � 0_ y � s1q

Außerdem: N $ ψ~x,ypsk1 , . . . , skn , 0q ÐÑ ϕpsk1 , . . . sknq, da N Ñ s1 � 0. Hieraus folgtdas Gewünschte.

“ð“: ψ repräsentiere KR in N (mit ~x, y). Setze ϕ � ψyp0q. Dann: ϕ repräsentiert R inN , denn: Sei Rpk1, . . . , knq. Dann KRpk1, . . . , knq � 0, also N $ ψ~x,ypsk1 , . . . , skn , 0q, d.h.T $ ϕ~xpsk1 , . . . , sknq.Sei non Rpk1, . . . , knq. Dann nach (FR2):

N $ ϕ~xpsk1 , . . . , sknq Ñ 0 � s1

Aber N $ s1 � 0. Aber N $ ϕ~xpsk1 , . . . , sknq.12.01.2012

Lemma 10. Jede rekursive Funktion ist repräsentierbar in N .

Beweis. Zu (R1) Offenbar xi � y repräsentiert Ini in N . Aus Lemma 8 folgt sofort

x1 � x2 � y repräsentiert � in Nx1 � x2 � y repräsentiert � in N

x1 x2 repräsentiert in N

Nach Lemma 8 ist also auch K repräsentierbar in N .

49


Zu (R2) Seien g, h1, . . . , hk rekursiv und

fpj1, . . . , jnq � g�h1p~jq, . . . , hkp~jq

Seien hi repräsentiert durch ϕi mit x1, . . . , xn, yi und g repräsentiert durch ψ mity1, . . . , yk, z. Setze σ � Dy1 � � � Dyk pϕ1 ^ . . . ^ ϕk ^ ψq. σ repräsentiert f in N mitx1, . . . , xn, z, denn:Zu (FR1) Seien j1, . . . , jn P N und m � fpj1, . . . , jnq. Setze mi � hip~jq. Also m �

gpm1, . . . ,mkq. DannN $ pϕiq~x,yipsj1 , . . . , sjn , smiq undN $ ψ~x,zpsm1 , . . . , smk

, smq.Also gilt N $ σ~x,zpsj1 , . . . , sjn , smq.

Zu (FR2) Seien j1, . . . , jn P N. Sei A ein Modell von N und A |ù σ~x,zrsj1 , . . . , sjn , as,für ein a P A. Dann existieren a1, . . . , ak P A mit:

A |ù pϕ1q~x,y1rsj1 , . . . , sjn , a1s ^ . . .^ pϕkq~x,ynrsj1 , . . . , sjn , aks ^ ψ~y,zra1, . . . , ak, as

Setze mi � hipj1, . . . , jnq. Also ai � sAmifür i � 1, . . . , k. Somit

A |ù ψ~y,zrsm1 , . . . , smk, as

Also a � gpm1, . . . ,mkq � fpj1, . . . , jnq.

Zu (R3) Sei g rekursiv mit: für alle k1, . . . , kn existiert m mit gp~k,mq � 0. Sei f definiertdurch fp~kq � µm : gp~k,mq � 0. ϕ repräsentiere g in N mit x1, . . . , xn, y, z. Sei w eineneue Variable und setze

ψ � ϕzp0q ^ @w pw y Ñ ϕy,zpw, 0qq

Zu Zeigen: ψ repräsentiert f mit ~x, y. Sei hierzu A ein Modell von N . Weiterhin seienk1, . . . , kn P N und m � fpk1, . . . , knq.Zu (FR1) Zu Zeigen: A |ù ψ~x,ypsk1 , . . . , skn , smq. Nun aber gpk1, . . . , kn,mq � 0. Also

A |ù ϕ~x,y,zpsk1 , . . . , skn , sm, 0q. Zu Zeigen bleibt:

A |ù @w�w sm Ñ ϕ~x,y,zpsk1 , . . . , skn , w, 0q

�Sei also a P A mit a A sAm. Dann existiert nach Lemma 8 j m mit a � sAj .Aber gpk1, . . . , kn, jq � 0. Also A |ù ϕ~x,y,zpsk1 , . . . , skn , sj , 0q.

Zu (FR2) Sei A |ù ψ~x,yrsk1 , . . . , skn , as für ein a P A. Zu Zeigen: a � sAm. Nun aberA |ù ϕ~x,y,zpsk1 , . . . , skn , sm, 0q. Also ist sAm A a nicht möglich. Also nach Lemma8 ist a � sAj für ein j P N mit j ¤ m. Daraus folgt sofort j � m.

Folgerung. Es gilt ReprpNq.

Beweis. Sei R � N rekursiv. Dann ist KR eine rekursive Funktion. Also ist nach Lemma 10KR repräsentierbar in N . Dann ist aber nach Lemma 9 auch R repräsentierbar in N .

50


Definition. Sei R � N, T L-Theorie, ϕ L-Formel mit höchstens x frei.

ϕ repräsentiert R schwach in T ðñ für alle n : pRpnq ðñ T $ ϕxpsnqq

SreprpT q bedeutet: für alle rekursiven R � N existiert ϕ, welches R schwach in T repräsen-tiert.

Bemerkung. (a) SreprpT qñ T widerspruchsfrei

(b) T widerspruchsfrei und ReprpT qñ SreprpT q

Beweis. Zu (a): Sei etwa R � H, ϕ repräsentiere R in T . Dann z.B. non T $ ϕxp0q, also Twiderspruchsfrei. Zu (b): Sei R � N rekursiv. ϕ repräsentiere R in T (mit x). Zu Zeigen:

für alle n : pRpnq ðñ T $ ϕxpsnqq

“ñ“: nach Definition. “ð“: indirekt: Sei non Rpnq. Dann T $ ϕxpsnq. Also non T $ϕxpsnq, wegen T widerspruchsfrei.

Satz (7�q. Sei T rekursiv (, widerspruchsfrei) und es gelte SreprpT q. Dann ist ThmT

universell.

Beweis. ThmT ist rekursiv aufzählbar nach Satz 5. Zur Universalität: Sei x feste Variable.Definiere f : N2 Ñ N durch fp`, nq � Subp`, SNpxq, numpnqq. Sei nun Q � N rekursiv.ϕ repräsentiere Q schwach in T (mit x). Dann ist für alle n : pQpnq ðñ T $ ϕxpsnqq. Aberxϕxpsnqy � Subpxϕy, SNpxq, numpnqq. Also für alle n:

Qpnq ðñ T $ ϕxpsnq ðñ ThmT pxϕxpsnqyq ðñ ThmT pfpxϕy, nqq

Lemma 11. Setze nun L0 � t0, S,�, �, u. Sei T L-Theorie , L � L0 und sei T Y Nwiderspruchsfrei. Dann gilt SreprpT q.

Beweis. Nach Folgerung zu Lemma 10 gilt ReprpNq. Sei nun σ die Konjunktion von (N1)-(N9). Sei R � N rekursiv. Dann existiert L0-Formel ϕ mit für alle n:

(i) Rpnqñ N $ ϕxpsnq

(ii) non Rpnqñ N $ ϕxpsnq

Das heisst: für alle n:

(i) Rpnqñ |ù pσ Ñ ϕxpsnqq

(ii) non Rpnqñ |ù pσ Ñ ϕxpsnqq

51


Setze nun ψ � pδ Ñ ϕq. Wir zeigen:

ψ repräsentiert R schwach in T

d.h. für alle n : pRpnq ðñ T $ ψxpsnqq.“ñ“: Sei Rpnq. Dann nach (ii) $ ψxpsnq. Also T $ ψxpsnq.“ð“: indirekt: Sei non Rpnq. Dann nach (ii) $ σ Ñ ϕxpsnq. Annahme: T $ ψxpsnq, d.h.

aber T $ σ Ñ ϕxpsnq. Insgesamt also T $ σ Ñ pϕxpsnq ^ ϕxpsnqq. Also T $ σ. SomitT YN widerspruchsvoll.

17.1.2012

Definition. Sei T eine L-Theorie. T ist entscheidbar, wenn ThmT rekursiv ist. Andernfallsheißt T unentscheidbar.

Satz 12 (Church). Sei T L-Theorie, L � L0, T rekursiv, T Y N widerspruchsfrei. Dannist T unentscheidbar.

Beweis. Nach Lemma 11 gilt SreprpT q. Also ist nach Satz 7* ThmT universell. Also ist Tunentscheidbar nach Lemma 6.

Spezialfälle:

(a) T � H. Liefert Unentscheidbarkeit der Logik erster Stufe. D.h. für L � L0 ist die Mengeder allgemeingültigen L-Aussagen nicht rekursiv.

(b) Ist T � ThpNq � tϕ | ϕ L0-Aussage, N $ ϕu rekursiv, so ist T unentscheidbar.

Konvention. Sei T L-Theorie. Ab nun heißt T vollständig, wenn für alle L-Aussagen ϕgilt, dass T $ ϕ oder T $ ϕ, d.h. wenn T � tϕ | ϕ L-Aussage, T $ ϕu vollständig imobigen Sinne sind.

Satz 13. Sei T rekursiv vollständige Theorie. Dann ist T entscheidbar.

Beweis. Falls T widerspruchsvoll ist, so ThmT � AussL, also rekursiv, also klar.Sei also T widerspruchsfrei. Wegen T rekursiv ist ThmT rekursiv aufzählbar. Nach Kapitel

4, Satz 4 genügt es zu zeigen, dass auch N � ThmT rekursiv aufzählbar ist. Wegen Tvollständig und widerspruchsfrei gilt aber für alle L-Aussagen ϕ:

non T $ ϕ ðñ T $ ϕ

Nun existiert rekursive Funktion neg mit: für alle L-Formeln ϕ negpxϕyq � x ϕy, nämlichnegpnq � xSNp qy � n. Dann gilt aber:

n P N� ThmT ðñ pnon AussLpnq oder ThmT pnegpnqqq

ðñ es existiert m pnon AussLpnq oder BewT pm,negpnqqq

Also ist N� ThmT rekursiv aufzählbar.

52


Satz 14 (Erster Gödelscher Unvollständigkeitssatz). Sei T L-Theorie, L � L0, T rekursiv,T YN widerspruchsfrei. Dann ist T unvollständig.

Beweis. Bew. d. Wid.: Annahme: T vollständig. Dann ist T entscheidbar nach Satz 13. Diesist ein Widerspruch zu Satz 12. .

Folgerung. PA ist unvollständig.

Der obige Beweis von Satz 14 ist etwas indirekt. Wir geben nun noch einen direktenBeweis einer etwas schwächeren Version von Satz 14 an.Sei hierzu T L0-Theorie, T rekursiv, T $ (N1) ^ . . .^ (N9), N |ù T . Insbesondere also

T widerspruchsfrei. Wegen T $ (N1) ^ . . .^ (N9), N |ù T ist jede rekursive Funktion (undRelation) in T repräsentierbar. Sei g definiert durch gpnq � Subpn, SNpxq, numpnqq, wobeix feste Variable. g ist rekursiv.Also existiert Formel ψ, welche g als Funktion in T repräsentiert (mit x,y). Also gilt für

alle n:T $ @y

�ψx,ypsn, yq Ø y � sgpnq

�Weiterhin ist BewT rekursiv. Sei also θ eine Formel, welche BewT in T repräsentiert (mitz, y). Sei nun ϕ � @y pψ Ñ @z θq. Setze ` � xϕy und ϕ� � ϕxps`q. Wir zeigen nun

p�q T $ pϕ� ÐÑ @z θypsxϕ�yqq

d.h. intuitiv bedeutet ϕ�:

“ich bin nicht beweisbar in T“

Beweis. von p�q. “ñ“: Es gilt T $ ψx,yps`, sxϕ�yq, da xϕ�y � xϕxps`qy � gp`q. Nun also istϕ� � @y pψxps`q Ñ @z θypsxϕ�yqq. Also T $ pϕ� Ñ @z θypsxϕ�yqq.“ð“: Es gilt: T $ @y pψxps`q Ñ y � s

xϕ�yq also:

T $ p@z θypsxϕ�yq Ñ ϕ�q

Somit also (1) non T $ ϕ�

Beweis. Annahme: T $ ϕ�. Dann existiert m mit BewT pm, xϕ�yq. Da BewT in T durchθ repräsentiert wird, also T $ θpsm, sxϕ�yq, insbesondere T $ Dz θypsxϕ�yq. Also nach p�qT $ ϕ�. Somit T widerspruchsvoll. .

(2) N |ù ϕ�

Beweis. Nach (1) haben wir: für alle m: non BewT pm, sxϕ�yq. Da BewT in T durch θ re-präsentiert wird, also wegen N |ù T also N |ù @z θypsxϕ�yq. Wegen N |ù T und p�q alsoN |ù ϕ�.

Also auch (3) non T $ ϕ�

53


Beweis. Wegen (2) und N |ù T .

Insgesamt also: ϕ�, ϕ� nicht ableitbar in T , d.h. T unvollständig. Außerdem: N |ù ϕ�. 19.01.2012

Satz 15 (Tarski). Es gibt keine L0-Formel θ mit der Eigenschaft:

p�q für alle L0-Aussagen ϕ: N |ù ϕ ðñ N |ù θypsxϕyq

d.h. die Menge der in N gültigen Aussagen ist nicht in N definierbar.

Beweis. Annahme: θ erfüllt p�q.Definiere g durch

gpnq � Subpn, SNpyq, numpnqq wobei y feste Variable

d.h. (1) gpxϕyq � xϕypsxϕyqy. g ist rekursiv. Sei also ψ eine Formel, welche g in N repräsen-tiert mit x,y. Also gilt insbesondere

(2) N |ù ψx,ypsn, skq ðñ gpnq � k

Setze nun ϕ � @y pψ Ñ θq. Sei ` � xϕy. Dann gilt

N |ù θypsxϕxps`qyq ðñ N |ù ϕxps`q

ðñ N |ù θypsxϕxps`qyq

.Intuitiv: ϕxps`q bedeutet “ich bin nicht wahr“.

Folgerung. W � tϕ | ϕ L0-Aussage, N |ù ϕu ist nicht rekursiv aufzählbar.

Beweis. Annahme: W ist rekursiv aufzählbar. Dann existiert rekursives P mit

n PW ðñ es existiert m mit P pm,nq

ψ repräsentiere P in N mit x, y. Setze θ � Dx ψ. Dann gilt für alle L0-Aussagen ϕ

N |ù ϕ ðñ xϕy PW ðñ es existiert m mit P pm,nqðñ es existiert m mit N |ù ψx,ypsm, snq

ðñ N |ù θypsxϕyq

d.h. θ erfüllt p�q aus Satz 15.

Bemerkung. Aus diesem Korollar folgt auch sofort, dass PA unvollständig ist.

54

6 Der zweite Gödelsche Unvollständigkeitssatz

6 Der zweite Gödelsche UnvollständigkeitssatzSei L0 die übliche Sprache der Zahlentheorie.

Definition. (a) Die Menge der Σ-Formeln wird rekursiv definiert durch:(1) Falls ϕ atomare Formel, so ϕ und ϕ sind Σ-Formeln.(2) Falls ϕ,ψ Σ-Formeln, so sind pϕ_ ψq, pϕ^ ψq Σ-Formeln(3) Ist ϕ Σ-Formel, x Variable, t Variable mit t � x, oder t � sn für ein n P N, so ist

@x px tÑ ϕq eine Σ-Formel.(4) Ist ϕ Σ-Formel, x Variable, so ist Dx ϕ eine Σ-Formel.

(b) Die Menge der Π-Formeln wird rekursiv definiert durch:(1) Falls ϕ atomare Formel, so sind ϕ und ϕ Π-Formeln.(2) Falls ϕ,ψ Π-Formeln, so sind pϕ_ ψq und pϕ^ ψq Π-Formeln.(3) Ist ϕ Π-Formel, x Variable, t Variable mit t � x oder t � sn für ein n P N, so ist

Dx px t^ ϕq eine Π-Formel.(4) Ist ϕ eine Π-Formel, x Variable, so ist @x ϕ eine Π-Formel.

Bemerkung. (a) Falls ϕ Σ-Formel (Π-Formel), so ist ϕxpsnq Σ-Formel (Π-Formel).

(b) Falls ϕ Σ-Formel (Π-Formel), w Variable, die in ϕ nicht vorkommt, so ist ϕxpwq Σ-Formel (Π-Formel)

Lemma 1. (a) Sei ϕ Σ-Formel. Dann existiert Π-Formel ψ mit $ @~x p ϕÐÑ ψq

(b) Sei ϕ Π-Formel. Dann existiert Σ-Formel ψ mit $ @~x p ϕÐÑ ψq

Beweis. zu (a) durch Induktion über den Aufbau von ϕ.zu (1) beachte $ ϕÐÑ ϕ

zu (2) $ pϕ_ ψq ÐÑ p ϕ^ ψq $ pϕ^ ψq ÐÑ p ϕ_ ψq

zu (3) $ @x px tÑ ϕq Ñ Dx px t^ ϕq

zu (4) $ Dx ϕÐÑ @x ϕ

zu (b) analog.

Lemma 2. Sei T L0-Theorie, f : Nn Ñ N. Weiterhin sei ϕ Σ-Formel, welche f in Trepräsentiert. Dann existiert auch Π-Formel ψ, welche f in T repräsentiert.

Beweis. Nach Voraussetzung gilt: Sei fpk1, . . . , knq � m. Dann

(i) T $ ϕ~x,ypsk1 , . . . , skn , smq

55


(ii) T $ @y pϕ~xpsk1 , . . . , sknq Ñ y � smq

Setze ψ� � @z pz � y Ñ ϕq. Nach Lemma 1 (a) existiert Π-Formel ψ mit $ @~x, y pψ� ÐÑψq. Also genügt zu zeigen, dass ψ� f in T repräsentiert. Sei hierzu fpk1, . . . , knq � m. Wegen(ii) gilt dann T $ ψ�~x,ypsk1 , . . . , skn , smq. Wegen (i) T $ @y pψ�~xpsk1 , . . . , sknq Ñ y � smq

24.01.2012

Lemma 3. Für jede rekursive Funktion f existiert Σ-Formel ϕ, welche f in N repräsentiert.

Beweis. zu (R1) xi � y repräsentiert Ini . x1�x2 � y repräsentiert “�“. x1 �x2 repräsentiert“�“. px1 x2 ^ y � 0q _ p x1 x2 ^ y � Sp0qq repräsentiert K .

zu (R2) Sei fpj1, . . . , jnq � gph1p~jq, . . . , hkp~jqq. Sei hi repräsentiert durch ϕi mit x1, . . . , xn, yi,g repräsentiert durch ψ mit y1, . . . yk, z. ϕi, ψ Σ-Formeln. Setze

θ � Dy1, . . . , Dyk pϕ1 ^ . . .^ ϕk ^ ψq

θ repräsentiert f mit x1, . . . , xn, z. θ ist Σ-Formel.

zu (R3) Sei g rekursiv mit: für alle j1, . . . , jn existiert m mit gp~j,mq � 0. Sei f definiertdurch fp~jq � µm : gp~j,mq � 0. ϕ repräsentiere g mit x1, . . . , xn, y, z und ϕ sei Σ-Formel. Setze ψ � ϕzp0q^@w pw y Ñ ϕy,zpw, 0qq. Früher wurde bereits gezeigt: ψrepräsentiert f . Aber ψ ist keine Σ-Formel. Nach Lemma 2 existiert jedoch auch eineΠ-Formel σ, welche g repräsentiert (mit ~x, y, z). Nach Lemma 1 existiert Σ-Formel σ�mit $ @~x, y, z p σ Ø σ�q. Setze nun ψ� � ϕzp0q ^ @w pw y Ñ σ�y,zpw, 0qq. ψ� istΣ-Formel, welche f repräsentiert in N .

Lemma 4. Sei ϕ eine Σ-Aussage mit N |ù ϕ. Dann ist N $ ϕ

Beweis. Durch Induktion über den Aufbau.

zu (1) Nach früherem Lemma über N .

zu (2) Klar.

zu (3) Sei ϕ � @x px sk Ñ ψq. Nun aber:

N $ @x p x s0q

N $ @x px sk ÐÑ px � s0 _ . . ._ x � sk�1qq für k ¡ 0

Also klar nach Induktionsvoraussetzung.

zu (4) Sei ϕ � Dx ψ. Wegen N |ù Dx ψ existiert n mit N |ù ϕxpskq. Aber nach Induktions-voraussetzung N $ ψxpsnq. Somit N $ Dx ψ.

56


Satz 5. Sei T widerspruchsfreie L0-Theorie, T rekursiv, T $ (N1)^ . . .^ (N9). Sei τ eineL0-Formel mit

(B1) τ ist Σ-Formel, τ repräsentiert BewT in T mit z, y.

(B2) Sind ψ1, ψ2 L0-Aussagen, so

T $ Dz τypsxψ1Ñψ2yq ^ Dz τypsxψ1yq Ñ Dzτypsxψ2yq

(B3) Ist ψ Σ-Aussage, soT $ ψ Ñ Dz τypsxψyq

Sei ρ eine L0-Formel, die neg in T repräsentiert mit u, v (hierbei negpxψyq � x ψy).Setze

ConT � @u@v pρÑ pDz τypuq ^ Dz τypvqqq

Dann ist ConT nicht in T beweisbar.

Beweis. Sei σ eine Σ-Formel, welche g in T repräsentiert mit x, y, wobei

gpnq � Subpn, SNpxq, numpnqq

(x feste Variable). Setze ϕ� � @y pσxps`q Ñ @z τq wobei ` � xϕy mit ϕ � @y pσ Ñ @z τq.Früher gezeigt:

(1) ϕ� ist nicht in T beweisbar.

(2) T $ ϕ� ÐÑ @z τypsxϕ�yq

Es genügt also wegen (1) zu zeigen:

(3) T $ ConT Ñ ϕ�

Hierzu genügt es zu zeigen: T $ ϕ� Ñ ConT . Nach (2) gilt

(4) T $ ϕ� Ñ Dz τypsxϕ�yq

Nun ist ϕ� eine Π-Aussage (bis auf logische Äquivalenz). Also existiert nach Lemma 1 eineΣ-Aussage ψ mit

(5) $ ϕ� ÐÑ ψ

Wegen (B1) gilt dann:

(6) T $ Dz τypsxψÑ ϕ�yq

Da ψ eine Σ-Aussage ist, folgt aus (B3):

(7) T $ ψ Ñ Dz τypsxψyq

Aus (B2) und (6), (7) erhalten wir:

57

7 Axiomatische Mengenlehre

(8) T $ ψ Ñ Dz τypsx ϕ�yq

Mit (5) also:

(9) T $ ϕ� Ñ Dz τypsx ϕ�yq

Aus (4) und (9) folgt also:

(10) T $ ϕ� Ñ�Dz τypskq ^ Dz τypsnegpkqq

�mit k � xϕ�y

Da ρ neg in T repräsentiert also

T $ ϕ� Ñ ConT

Bemerkung. (B2) T $�Dz τypsxψ1Ñψ2yq ^ Dz τypsxψ1yq Ñ Dz τypsxψ2yq

�(B3) Ist ψ Σ-Aussage, so T $ ψ Ñ Dz τypsxψyq.

26.01.2012

7 Axiomatische MengenlehreWir entwickeln die Theorie ZF(C) (Zermelo-Fraenkel Mengenlehre (mit Auswahlaxiom)).ZFC ist eine Theorie erster Stufe mit nur einem nichtlogischen Zeichen, nämlich dem zwei-stelligen Relationszeichen P. Wir lesen “x P y“ als “x ist Element von y“. x R y ist Abkürzungfür x P y. Als erstes Axiom von ZF haben wir:

(A1) (Extensionalitätsaxiom) @zpz P xÐÑ z P yq Ñ x � y

Die Sprache ZF ist so arm, dass wir auf systematische Weise Abkürzungen einführen. Diesgeschieht auf der Metaebene durch Einführung von Klassen(-termen) wie folgt:

x ist eine Klasse

Ist ϕpxq eine Formel, die eventuell schon Klassen enthält, so ist:

A � tx | ϕpxqu Klasse

lies: “Die Klasse aller x mit ϕpxq“. Wir benutzen große Buchstaben als Metavariablen fürKlassen. Für Klassen erlauben wir folgende Regeln:

(I) A � B ðñ @x px P AÐÑ x P Bq

(II) z P tx | ϕpxqu ðñ ϕpzq

(III) B P tx | ϕpxqu ðñ Dz pB � z ^ ϕpzqq

58


A � B ist Abkürzung für @x px P AÑ x P Bq. Setze noch

V � tx | x � xu AllklasseH � tx | x � xu leere Klasse

AYB � tx | x P A_ x P Bu

AXB � tx | x P A^ x P Bu

A � tx | x R Au

A�B � tx | x P A^ x R Bu

Wir lesen A P V also “A ist Menge“. Setze R � tx | x R xu. Es gilt (1): R R V . Denn:Annahme R P V . Dann R P R ðñ R R R. .

(A2) (Nullmengenaxiom) H P V

Setze tx0, . . . , xnu � tz | z � x0 _ . . ._ z � xnu.

(A3) (Paarmengenaxiom) @x, y tx, yu P V

Setze ¤A � tx | Dy P A x P yu£A � tx | @y P A x P yu

(A4) (Vereinigungsaxiom) @x�x P V

Weiter gilt (2) xY y P V .

Beweis. xY y ��tx, yu P V .

Durch Induktion folgt dann tx0, . . . , xnu P V .

Definition. xx, yy � ttxu, tx, yuu.

Es gilt (3):

(a) xx, yy P V

(b) xx, yy � xu, vy ÐÑ x � u^ y � v

allgemeiner: n-Tupel:xxy � x

xx0, , xn�1y � xxx0, . . . , xny, xn�1y

Für Klassen A,B setze:

A�B � txx, yy | x P A^ y P Bu

An � txx1, . . . , xny | x1 P A^ . . .^ xn P Au

A1 � . . .�An � pppA1 �A2q �A3q . . .q �An

59


R ist eine Relation, wenn R � V 2. Ist R eine Relation, so schreibe oft xRy statt xx, yy P R.dompRq, rngpRq, R � S, R�1 wie üblich. Etwas ungewöhnlich:

R2A � ty | Dx P A xRyu Bild von A unter RR � S � txx, zy | Dy xSy ^ yRzu

F ist Funktion ðñ pF ist Relation und @x, y, z pxx, yy P F ^ xx, zy P F Ñ y � zqDie übliche Notation F pxq für x P dompF q � dasjenige y mit xx, yy P F

F æ A � txx, yy P F | x P Au

(A5) (Ersetzungsschema) F FunktionÑ @x F 2x P V

Ohne Abkürzung:Sei ϕpx, y, ~wq eine Formel

Dann

@~w rp@x@y@zpϕpx, y, ~wq ^ ϕpx, z, ~wq Ñ y � zq Ñ @uDv@y py P v ÐÑ Dx P u ϕpx, y, ~wqqs

Als Folgerung erhalten wir: (4) (Aussonderung):

@x AX x P V

Beweis. AX x � pid æ Aq2x, wobei id � txx, xy | xV u

Also auch: @x pA � xÑ A P V q und damit wegen R R V auch V R V . 31.01.2012

Setze Ppxq � tz | z � xu

(A6) (Potenzmengenaxiom) @x Ppxq P V

Somit auch (5) u� v P V . Denn u� v P P pPpPpuY vqqq. Schließlich

(A7) (Fundierungsaxiom) @x px � HÑ Dz P x z X x � Hq.

Definition. Seien s � xu, ry und s � xu, ry (binäre) Strukturen, d.h. r � u2, r � u2. Wirschreiben:

f : sÑs ðñ f : uÑ u ist Bijektion und für alle a, b P u : parb ðñ fpaqrfpbqq

Definition. (a) Sei s � pu, rq eine Struktur. s ist eine endlich-geordnete Struktur (EGS)ðñ r ist irreflexiv, transitiv, total und jedes a � u mit a � H besitzt Minimum undMaximum bezüglich r.

(b) u ist endlich ðñ es existiert r � u2 mit xu, ry EGS.

(c) u ist unendlich ðñ u ist nicht endlich.

60


Definition. A ist transitiv ðñ @x P A x � A

@x, y py P x P AÑ y P Aq

Satz 1. Sei s � xu, ry EGS. Dann existiert genau ein Paar xf, vy mit v transitiv undf : sÑxv, Py.

Beweis. zur Existenz: Für x P u setze sx � xux, rxy, wobei ux � tz | zrx _ z � xu,rx � r X u2

x. sx ist EGS. Sei o.E u � H.Setze a � tx P u | Dg, ω pω transitiv ^g : sxÑxω, Pyqu. Sei z das Maximum von a. Man

zeigt, dass z das Maximum von u ist und ist fertig.

Definition. Sei s EGS.

otppsq � das transitive v mit s�xv, Py

ω � totppsq | s EGSu. Elemente von ω heißen natürliche Zahlen

(A8) (Unendlichkeitsaxoim) ω P V

Die Axiome pA1q � pA8q bilden die Theorie ZF.

Bemerkung. ω � tv | xv, Py EGS, v transitivu. Setze 0 � H, spxq � xYtxu. Es gilt: 0 P ωund @n P w spnq P ω.Setze 1 � sp0q, 2 � sp1q, usw.Für m,n P ω setze: m n ðñ m P n. xω, y ist geordnete Struktur. Es gilt: jedes

a � ω mit a � H besitzt Minimum.

Satz 2 (Rekursionssatz für ω). Sei G : ω � V Ñ B. Dann existiert genau ein F : ω Ñ Bmit @n F pnq � Gpn, F æ nq.

Beweis. Eindeutigkeit durch Induktion. Existenz: Setze P � tg | g Funktion, dom g Pω, rngpgq � B,@n dom g gpnq � Gpn, g æ nqu und F �

�P . F tut’s!

Hiermit können wir rekursiv �, � auf ω definieren. Es gilt dann insbesondere spnq � n�1.Sei R eine Relation.

A ist R-abgeschlossen ðñ @x P A tz | zRxu � A

Sei R eine Relation mit @x tz | zRxu P V . Dann existiert für alle a ein b � a mit bR-abgeschlossen. Denn definiere rekursiv

F p0q � a

F pn� 1q � F pnq Y tz | Dy P F pnq zRyu

und setze b ��tF pnq | n P ωu.

Definition. Sei R eine Relation.

61


(a) x ist R-minimal in A, wenn x P A und

tz | zRxu XA � H

(b) R ist fundiert ðñ jedes a � H besitzt R-minimales Element.

(c) R ist stark fundiert ðñ R ist fundiert und @x tz | zRxu P V .

Beispiel. P ist stark fundiert.

Bemerkung. Sei R stark fundiert und A � H eine Klasse. Dann besitzt A ein R-minimalesElement.

Beweis. Sei x P A. Wähle ein R-abgeschlossenes b mit x P b und setze a � AX b. Sei z einR-minimales Element von a. Dann ist z ein R-minimales Element von A.

Für stark fundierte Relation R � A2 gilt das Induktionsprinzip, d.h. es gelte:

@x P A p@z pzRxÑ ϕpzqq Ñ ϕpxqq

Dann gilt @x P A ϕpxq.

Beweis. Annahme: non @x P A ϕpxq. Setze Z � tx P A | ϕpxqu. Also Z � H. Sei a einR-minimales Element von Z. .

02.02.2012

Satz 3 (Rekursionssatz für stark fundierte Relationen). Sei R � A2 stark fundiert undG : A� V Ñ B. Dann existiert genau ein F : AÑ B mit

@x P A F pxq � Gpx, F æ tz | zRxuq

Beweis. Eindeutigkeit durch Induktion. Zur Existenz: Setze

P � f | f Funktion, dom f � A, rng f � B, dom f ist R-abgeschlossen und@x P dom f fpxq � Gpx, f æ tz | zRxuq

(Setze F �

�P . Wir zeigen: F ist wie gewünscht. Hierzu zeige:

(i) f, f P P , dom f � dom f Ñ f � f

(ii) f P P , v R-abgeschlossen Ñ f æ v P P

(iii) f, f P P Ñ f æ pdom f X dom fq � f æ pdomf X domfq

(iv) @a P A Df P P a P dom f

62


(i)-(iii) sind leicht.Zu (iv): Beweis durch R-Induktion. Sei a P A gegeben. Für bRa sei cb die kleinste R-

abgeschlossene Menge mit b P cb. Nach Induktionsvoraussetzung (und (i), (iii)) existiert füralle bRa genau ein fb P P mit dom fb � cb. Setze h �

�tfb | bRau. Nach (iii) ist h P P ,

da dom h ��tcb | bRau ist R-abgeschlossen. Setze nun f � hY txa,Gpa, h æ tz | zRauqyu.

Dann ist f P P , a P dom f .Aus (i)-(iv) folgt alles.

Satz 4 (Mostowskischer Isomorphiesatz). Sei R � A2 stark fundiert und extensional, d.h.

@x, y P A ptz | zRxu � tz | zRyu Ñ x � yq

Dann existiert genau ein Paar xF,Xy mit X transitiv und F : xA,Ry Ñ xX, Py.Zusatz: Es gilt @x P A F pxq � F 2tz | zRxu

Beweis. Zur Existenz: Definiere nach Rekursionssatz F : A Ñ V so, dass @x P A F pxq �F 2tz | zRxu. Setze X � rngpF q. Dann ist X transitiv. Zeige, dass F injektiv ist. DieIsomorphiebedingung folgt sofort.

Definition. Sei xA,Ry eine Struktur, d.h. R � A2.

(a) xA,Ry ist wohlgeordnete Struktur (WS) ðñ xA,Ry ist geordnete Struktur und R istfundiert.

(b) xA,Ry ist stark wohlgeordnete Struktur (SWS) ðñ xA,Ry ist geordnete Struktur undstark fundiert.

Bemerkung. Sei xA,Ry SWS. Dann besitzt jedes Z � A mit Z � H ein Minimum.

Bemerkung. Sei xA,Ry geordnete Struktur. Dann ist xA,Ry extensional. Somit könnenwir nach Satz 4 definieren: Sei S � xA,Ry SWS. Setze

otppSq � das transitive X mit S�xX, Py

Setze On � totppsq | s WSu. Elemente von On heißen Ordinalzahlen.Variablen hierfür α, β, γ, δ, ..

Definition. v heißt konnex ðñ @x, y P vpx � y oder x P y oder y P xq.

Es gilt On � tv | v transitiv und konnexu.

Beweis. “�“: klar nach Definition. “�“: Sei v transitiv und konnex. Es genügt zu zeigen,dass xv, Py WS. Dann ist v � otppxv, Pyq P On. Wegen Fundiertheitsaxiom genügt es aberhierfür zu zeigen, dass P Xv2 transitiv ist. Sei hierzu x, y, z P v mit x P y und y P z. WegenFundiertheit ist dann x � z und z P x nicht möglich. Wegen v konnex also x P z.

Hiermit sieht man dann leicht:

63


• ω � On

• ω P On

• @α spαq P On

Für α, β P On definiere:

α β ðñ α P β

α ¤ β ðñ pα β oder α � βq

07.02.2012

Bemerkung. α ¤ β ðñ α � β.Wir benötigen: (*) Sei a � α, a � α, a transitiv. Dann gilt a P α. Also: α ¤ β ðñ α � β.

Satz 5. (a) On ist transitiv

(b) xOn, y ist SWS

(c) On R V

(d) @α, β pα β ðñ spαq ¤ βq

Beweis. zu (a): Sei α P On und x P α. Dann ist x konnex, da x � α wegen α transitiv.Also genügt es zu zeigen, dass x transitiv ist. Sei hierzu y P x und z P y. Dann sind z, y P αwegen α transitiv. Also, da xα, Py geordnete Struktur, z P x.Zu (b): Da stark fundiert ist, ist nur zu zeigen, dass xOn, y eine geordnete Struktur

ist. Irreflexivität und Transitivität sind klar.Zur Totalität: Sei α, β P On. Zu zeigen:

α ¤ β oder β ¤ α

-Annahme: nicht. Dann ist αX β � α, β, αX β � α, αX β � β. Aber αX β ist transitiv.Also nach (*) αX β P αX β, was ein Widerspruch ist.Zu (c): -Annahme On P V . Dann On � otppxOn, yq P On. .Zu (d): “ñ“: α P β Ñ spαq � αY tαu � β “ð“: spαq � αY tαu � β Ñ α P β

Bemerkung. Falls a � On, so existiert γ P On mit a � γ. Denn setze einfach γ ��a,

falls a kein Maximum besitzt.

Definition. Sei α P On. α ist Limesordinalzahl ðñ pα � 0 und @γ α Dδ γ δ αq

Notation. limpαq

Beispiel. limpωq

Es gilt dann:α � 0 oder Dβ α � spβq oder limpαq

Damit erhält man folgendes Induktionsprinzip und Rekursionsprinzip für Ordinalzahlen:

64


(transfinite Induktion) Es gelte:(a) ϕp0q(b) @α pϕpαq Ñ ϕpspαqq

(c) Falls limpλq, so: p@α λ ϕpαq Ñ ϕpλqq

Dann gilt @α ϕpαq.

(transfinite Rekursion) Seien Gi : On � V Ñ B, i � 0, 1 und b P B. Dann existiert genauein F : OnÑ B mit(i) F p0q � b

(ii) F pspαqq � G0pα, F pαqq

(iii) F pλq � G1pλ, F æ λq falls limpλq.

Man kann dann Ordinalzahloperationen �, � auf On rekursiv definieren durch:

• α� 0 � α

• α� spβq � spα� βq

• α� λ � supγ λpα� γq, falls limpλq

• α � 0 � 0

• α � spβq � α � β � α

• α � λ � supγ λ α � γ, falls limpλq

Haben also insbesondere spαq � α� 1. Spielen keine große Rolle. Sind nicht kommutativ.

ω � 1� ω � ω � 1ω � 2 � ω � ω � 2 � ω � ω

Definiere nun rekursiv xVα | α P Ony durch:

V0 � H Vα�1 � PpVαq Vλ �¤α λ

Vα falls limpλq

Satz 6. (a) Vβ ist transitiv.

(b) α ¤ β Ñ Vα � Vβ

(c) α β Ñ Vα P Vβ

(d) Vα XOn � α

Beweis. Simultan durch Induktion über β:

• β � 0: klar.

65


• β Ñ β � 1: zu (b): Vβ � Vβ�1, denn:

a P Vβ Ñ a � Vβ Ñ a P Vβ�1

zu (a): a P Vβ�1 Ñ a � Vβ � Vβ�1

zu (c): Sei α β � 1. Falls α β, so Vα P Vβ � Vβ�1 Außerdem nach Def. Vβ P Vβ�1.zu (d): “�“: γ P Vβ�1 X On Ñ γ � Vβ X On � β Ñ γ ¤ β “�“: β � Vβ � Vβ�1,β P Vβ�1. Also β � 1 � β Y tβu � Vβ�1

• limpλq (a), (b), (c) sind klar. zu (d): Vγ XOn ��γ λpVγ XOnq �

�γ λ γ � λ.

Satz 7. V ��αPOn Vα

Beweis. “�“: klar. “�“: Zeige durch P-Induktion

@a Dα a P Vα

Sei a gegeben. Wegen Induktionsvoraussetzungen können wir f : a Ñ On definieren durchfpxq � mintγ | x P Vγu. Wähle α P On mit rngpfq � α. Dann gilt a � Vα, also a P Vα�1

Somit können wir eine Rangabbildung rn : V Ñ On definieren durch

rnpaq � mintα | a P Vαu

Es gilt dann für Klasse A:

A P V ðñ trnpxq | x P Au ist beschränkt in On

Definition.x � y ðñ es existiert Bijektion f : xÑ y

px, y sind gleichmächtigqx ¨ y ðñ es existiert Injektion f : xÑ y

(Schröder-Bernstein) x ¨ y und y ¨ xÑ x � y08.05.2012

Satz 8 (Cantor). x ¨ Ppxq, x � Ppxq

Beweis. Erster Teil ist klar, da fpzq � tzu eine Injektion von x nach Ppxq liefert. Fürden zweiten Teil zeigen wir sogar, dass es kein surjektives g : x Ñ Ppxq gibt. Sei hierzug : xÑ Ppxq. Setze

a � tz P x | z R gpzqu � x

Dann ist a R rngpgq. Denn: Annahme: a � gpz0q mit z0 P x. Dann

z0 P a ðñ z0 P gpz0q ðñ z0 R a

66


Definition. Card � tκ | @α κ κ � αu ist die Klasse der Kardinalzahlen.

Bemerkung. ω � 1 � Card. Aber: α ¥ ω Ñ α� 1 R Card

Bemerkung. κ P Card ðñ @α κ κ ¨ α.

Definition. Sei A � On. A ist abgeschlossen, wenn für alle H � b P A: sup b P A.

Bemerkung. Card ist abgeschlossen.

Beweis. Sei H � b P Card und κ � sup b. Annahme κ R Card. Dann existiert α κmit κ ¨ α. Wähle λ P b mit α λ. Dann λ ¤ κ, also auch λ ¨ α im Widerspruch zuλ P Card.

Satz 9. @x Dα α ¨ x

Beweis. Sei x gegeben. Setze a � txu, ry | u � x, xu, ry WSu. (beachte: a P V ). Dannexistiert α mit otppsq α für alle s P a. Wir zeigen α ¨ x. Annahme: Doch. Sei alsof : αÑ x injektiv. Setze u � rngpfq und definiere r � u2 durch:

yrz ðñ f�1pyq f�1pzq

Setze s � xu, ry. Dann ist f : xα, y Ñ xu, ry. Aber s P a, also otppsq α, was ein Wider-spruch ist.

Somit ist Card unbeschränkt in On, denn: Sei γ gegeben, setze A � tα | α ¨ γu. Dannist A � H. Setze κ � minA. Dann ist κ P Card, κ ¡ γ.

Definition. Für ein κ P Card� w setze

κ� � mintλ P Card | λ ¡ κu

kardinaler Nachfolger von κ

Definition. Definiere xωα | α P Ony rekursiv durch:

ω0 � ω

ωα�1 � ω�α

ωλ � supα λ

ωα, falls limpλq

Dann ist Card� ω � tωα | α P Onu.

Satz 10. Es sind äquivalent

(1) @u Dr � u2 xu, ry WS.

(2) @u Dα u � α

(3) @x, y px ¨ y oder y ¨ xq

67


Beweis. (1)Ñ(2): Sei xu, ry WS, α � otppxu, ryq. Sei f : xu, ry Ñ xα, y. Liefert u � α.(2)Ñ(3): Seien x, y gegeben. Gemäß (2) wähle α, β mit x � α, y � β. Dann α ¤ β oderβ ¤ α. Sei ohne Einschränkung α ¤ β. Dann

x � α ¨ β � y, d.h. x ¤ y

(3)Ñ(1): Sei u gegeben. Nach Satz 9 existiert α mit α ¨ u. Also nach (3) angewandt aufu, α gilt u ¨ α. Sei f : uÑ α injektiv. Definiere r � u2 durch zrz ðñ fpzq fpzq. Dannxu, ry WS.

Definition. Sei u P V und f : uÑ V .

f ist Auswahlfunktion für u ðñ @x P u px � HÑ fpxq P xq

(AC): @u Df pf ist Auswahlfunktion für uq.

Satz 11. Es sind äquivalent:

(1) (AC)

(2) @u Dα u � α

Beweis. (2)Ñ(1): Sei u gegeben. Gemäß (2) sei g :�uÑ α Bijektion. Definiere f : uÑ V

durch

fpxq �

#0 falls x � Hg�1pmin g2xq sonst

f ist Auswahlfunktion für u. (1)Ñ(2): Sei u gegeben. Sei g : Ppnq � tHu Ñ u eine Aus-wahlfunktion für Ppuq � tHu. Setze D � th | u� rngphq � Hu. Definiere G : D Ñ u durchGphq � fpu � rngphq. Nach Rekursionssatz existiert F : Γ Ñ u mit Γ � On oder Γ P Onund

(i) @α Γ F pαq � GpF æ αq

(ii) Γ � On oder pΓ P On und F R Dq

F ist injektiv, dennnach (i): @α Γ F pαq R rngpF æ αq Somit wegen u P V ist Γ P On. Dann wegen (ii) ist

F R D, d.h. aber u� rngpF q � H, d.h. rngpF q � u. Somit ist u � Γ, Γ P On.

(A9) (Auswahlaxiom) (AC)

Sei ZFC die Theorie (A1)-(A9). Wird arbeiten nun in ZFC. Wegen Satz 11 können wirdann definieren:

|x| � mintα P On | x � αu

|x| � die Mächtigkeit von x. Es gilt |x| P Card. Weiterhin ist Card � tα | |α| � αu. Fernergilt x ¨ y ðñ |x| ¤ |y| und x � y ðñ |x| � |y|.

68


Bemerkung. Sei f : xÑ y surjektiv. Dann gilt |y| ¤ |x|.

Wir definieren nun Kardinalzahloperationen. Setze

κ� λ � |pκ� t0uq Y pλ� t1uq|κ � λ � |κ� λ|

Warnung: ist verschieden von Ordinalzahladdition bzw. Ordinalzahlmultiplikation. Imfolgenden ist immer �, � wie oben gemeint.

Satz 12. Für alle x P Card� ω gilt κ � κ � κ.

Beweis. Definiere Relation � auf On�On durch

xα, βy � xγ, λy ðñ maxtα, βu maxtγ, λuoder pmaxtα, βu � maxtγ, λu und α γq

oder pmaxtα, βu � maxtγ, λu und α � γ und β λq

Man sieht leicht, dass L � xOn � On, �y eine SWS ist. Dann ist aber (!) otppLq � On,denn otppLq � On, otppLq ist transitiv und echt Klasse. Sei also F : LÑxOn, y. Es gilt also

p�q F pxγ, λyq � F 2txα, βy � xγ, λyu

Wir zeigen nun: p��q für alle κ P Card�ω F 2κ� κ � κ. Dann sind wir fertig, denn da Finjektiv ist, folgt aus p��q für κ P Card� ω κ� κ � |κ� κ| ¤ κ, was genügt, da κ ¤ κ� κtrivial ist. Wir zeigen p��q durch Induktion, d.h. wir zeigen durch Induktion über ν, dassF 2pων � ωνq � ων gilt.

ν � 0 Seien m,n P ω. Setze q � maxtm,nu�1. Dann gilt txr, s, y | xr, sy � xm,nyu � q�qund daher nach p�q F pxr, syq � F 2pq � qq. Also ist F pxm,nyq endlich und daherF pxr, syq P ω.

ν Ñ ν � 1 Seien xγ, ρy ων�1 und setze µ � maxtγ, ρu � 1. Dann gilt wieder F pxγ, ρyq �F 2pγ � γq. Aber |γ � γ � |γ| � |γ| ¤ ων � ων . Aber nach Ind. vor. ist ων � ων � ων .Insgesamt also |F pxγ, ρyq| ¤ ων , d.h. F pxγ, ρyq ων�1.

limpλq Dann F 2pωλ � ωλq ��α λ F

2pωα � ωαq ��α λ ωα � ωλ

Folgerung. Seien κ, λ P Card� t0u, maxtκ, λu ¥ ω. Dann κ� λ � κ � λ � maxtκ, λu.

Beweis. Setze τ � maxtκ, λu. Dann τ ¤ κ� λ, κ � λ ¤ τ � τ � τ .

Bemerkung. Sei I P V . Dann gilt

|¤iPI

ai| ¤ |I| � supt|ai| | i P Iu

69


Beweis. Setze κ � supt|ai| | i P Iu Für i P I sei fi : ai Ñ |ai| bijektiv. Definiere g :�iPI ai Ñ

I � κ wie folgt: Sei x P�iPI ai. Wähle ein i mit x P ai und setze gpxq � xi, fipxqy. g ist

injektiv. Also |�iPI ai| ¤ |I � κ| � |I| � κ.

Definition. Sei λ Limesordinalzahl. Setze

cfpλq � mint|a| | a � λ ist unbeschränkt in λu

Konfinalität von λ. Also trivialerweise cfpλq � λ. λ ist regulär, wenn cfpλq � λ.

Satz 13. Sei τ � cfpλq. Dann existiert f : τ Ñ λ mit

(i) f ist streng monoton

(ii) falls γ τ Limesordinalzahl, so ist fpγq � supα γfpαq.

(iii) f ist konfinal d.h. rngpfq ist unbeschränkt in λ.

Beweis. Sei a � λ unbeschränkt mit |a| � τ . Sei g : τ Ñ a eine Bijektion. Definiere nunf : τ Ñ λ rekursiv. Setze fp0q � 0. Für α τ setze fpα � 1q � maxtgpαq, fpαq � 1u. Istγ λ Limesordinalzahl, so ist f2γ beschränkt in λ, da |f2γ| τ . Wir können also setzenfpγq � supα γ fpαq. f tut’s.

Bemerkung. Ist f wie in Satz 13 und C � rngpfq, so ist otppCq � τ und C abgeschlossenund unbeschränkt in λ.

Folgerung (zu Satz 13). cfpλq ist regulär.

Beweis. Sei τ � cfpλq und f wie in Satz 13. Sei b � τ unbeschränkt in τ . Dann ist f2bunbeschränkt in λ. Also |b| � τ .

Offenbar ist jede reguläre Ordinalzahl eine unendliche Kardinalzahl. Aber die Umkehrungist falsch, da z.B. cfpωωq � ω, da tωn | n P ωu unbeschränkt in ωω ist. 10.05.2012

Satz 14. Sei κ P Card� ω. Dann ist κ� regulär.

Beweis. Sei a � κ� mit |a| ¤ κ. Dann gilt |�a| ¤ |a| � supt|α| | α P au ¤ κ � κ � κ. Also ist

a beschränkt in κ�.

Satz 15 (König). Seien I P V und xκi | i P Iy, xτi | i P Iy zwei Folgen mit κi P Card undτi κi (τi P On). Dann gilt:

|¤iPI

pτi � tiuq| |¹iPI

κi|

Beweis. Setze A ��iPI τi � tiu, B �

±iPI κi. Es genügt zu zeigen, dass es kein sur-

jektives h : A Ñ B gibt. Sei also h : A Ñ B. Wir zeigen rngphq � B. Für i P I setzeai � thpxγ, iyqpiq | γ τiu � κi. Dann gilt |ai| ¤ τi κi. Also κi � ai � H. Definierenun f P

±iPI κi durch fpiq � minpκi � aiq. Dann ist f R rngphq, denn sei g P rngphq, etwa

g � hpxγ, iyq. Dann gpiq � hpxγ, iyqpiq P ai, aber fpiq R ai. Also f � g.

70


Folgerung. Voraussetzugen wie oben. Dann gilt:

|¤iPI

τi| |¹iPI

κi|

Zur Erinnerung: uv � tf | f : uÑ vu Für κ, λ P Card setze κλ � |λκ|Es gilt also (charakteristische Funktion!) 2κ � |Ppκq| Man zeigt leicht, dass für κ, τ, ρ P

Cardpκτ qρ � κτ �ρ

Folgerung Sei κ P Card� ω. Dann ist 2κ � κκ.

Beweis. 2κ ¤ κκ ¤ p2κqκ � 2κ�κ � 2κ

Wir erhalten nun folgende Verstärkung des Satzes von Cantor.

Satz 16. Für alle κ P Card� ω ist cfp2κq ¡ κ.

Beweis. Sei g : κÑ 2κ. Wir zeigen, dass g nicht konfinal ist. Nun gilt für alle α κ gpαq 2κ. Also nach obigem Korollar

|¤α κ

gα| |¹α κ

2κ| � p2κqκ � 2κ�κ � 2κ

Somit ist g nicht konfinal.

Satz 17. Für alle κ P Card� ω gilt κcfpκq ¡ κ.

Beweis. Setze τ � cfpκq. Sei g : τ Ñ κ konfinal, also κ ��α κ gpαq. Nach obigem Korollar

gilt:κ � |

¤α τ

gpαq| |¹α τ

κ| � κτ

Die Veranstaltung wurde durch im SoSe 2012 durch ”Modelle der Mengenlehre” fortgesetzt. Linkzum Skript: http://christian-ittner.de/studium/skripten/mengenlehre/skript.pdf

71

http://christian-ittner.de/studium/skripten/mengenlehre/skript.pdf

Documents

Logik - Christian · PDF fileVorlesung aus dem Wintersemester 11/12 Logik Prof. Dr. Hans-Dieter Donder geTEXtvonChrisIttner Inhaltsverzeichnis 0 Aussagenlogik2 1