HvězdárnaaplanetáriumBrno,9.března2017 VítězslavŠvejdar KurtGödel:úplnostaneúplnost

(1)

Životopis Logika Axiomy a teorie Neúplnost Dodatky

Kurt Gödel: úplnost a neúplnost

Vítězslav Švejdar

Karlova Univerzita v Praze, http://www.cuni.cz/~svejdar/

Hvězdárna a planetárium Brno, 9. března 2017

Vítězslav Švejdar, FF UK Praha Kurt Gödel: úplnost a neúplnost 1/13

(2)

Obsah

Několik životopisných údajů

Logické symboly a logické kroky

Axiomy, axiomatické teorie, struktury

Strukturální důkaz věty o neúplnosti

Dodatky, poznámky a literatura

(3)

Kurt Gödel: několik životopisných údajů

• Narozen 1906 (Wikipedia: Brün, Austria-Hungary).

• Maturoval 1924 a odešel studovat do Vídně.

• Volba rakouského občanství v roce 1929.

• Sňatek v září 1938.

• Od roku 1934 několik pobytů v USA (Institute for Advanced Study, University of Notre Dame), naposledy v zimě 38–39.

• Od března 1940, po dobrodružné cestě přes Sibiř, natrvalo v USA.

(4)

Kurt Gödel: několik životopisných údajů

(5)

Kurt Gödel: několik životopisných údajů

(6)

Kurt Gödel: několik životopisných údajů

(7)

Kurt Gödel: několik životopisných údajů

(8)

Kurt Gödel: několik životopisných údajů

(9)

Symbolický zápis tvrzení (vlastností, podmínek)

Logická struktura tvrzení

pokud vyhraji, koupím si auto nebo pojedu do Chile

jev → (a ∨ c). Symboly ∨, →, & , ¬jsou logické spojky. Papadimitriou v [Pap94]:

everybody loves my baby, my baby loves nobody but me:

∀xL(x,B) & ∀y(L(B,y) → y =M). Symboly∀ a∃ jsoukvantifikátory. Zápis podmínkyčíslox je prvočíslo: x6= 1 & ∀v(v|x → v= 1 ∨ v =x),

kdev 6= 1 je zkratka pro¬(v = 1), kdežtov |x je zkratka pro∃u(u·v =x) nebo proMod(x,v) = 0.

(10)

Symbolický zápis tvrzení (vlastností, podmínek)

pokud vyhraji, koupím si auto nebo pojedu do Chile jev → (a ∨ c).

Symboly ∨, →, & , ¬jsou logické spojky. Papadimitriou v [Pap94]:

(11)

Symbolický zápis tvrzení (vlastností, podmínek)

jev → (a ∨ c). Symboly ∨, →, & , ¬jsou logické spojky.

Papadimitriou v [Pap94]: everybody loves my baby, my baby loves nobody but me:

(12)

Symbolický zápis tvrzení (vlastností, podmínek)

Papadimitriou v [Pap94]:

∀xL(x,B) & ∀y(L(B,y) → y =M).

Symboly∀ a∃ jsoukvantifikátory. Zápis podmínkyčíslox je prvočíslo: x6= 1 & ∀v(v|x → v= 1 ∨ v =x),

(13)

Symbolický zápis tvrzení (vlastností, podmínek)

∀xL(x,B) & ∀y(L(B,y) → y =M).

Symboly∀ a∃ jsoukvantifikátory.

Zápis podmínkyčíslox je prvočíslo: x6= 1 & ∀v(v|x → v= 1 ∨ v =x),

(14)

Symbolický zápis tvrzení (vlastností, podmínek)

∀xL(x,B) & ∀y(L(B,y) → y =M).

Symboly∀ a∃ jsoukvantifikátory.

Zápis podmínkyčíslox je prvočíslo:

x6= 1 & ∀v(v |x → v= 1 ∨ v =x),

(15)

Příklady argumentů (důkazů)

Příklad 1 Z předpokladu, že každé číslo tvaru 100k+ 67 je prvočíslo, plyne, že 67 je prvočíslo. Také, že 167, a také 267.

Příklad 2 Z ∀xL(x,B) a∀y(L(B,y) → y =M) plyne B =M: Když∀xL(x,B), pak iL(B,B). Když ∀y(L(B,y) → y =M), pak iL(B,B) → B =M. Tedy B=M.

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Nechť jsou dánaa ab taková, že ¬(3|a) a¬(3|b). Pak a dává zbytek 1 nebo 2 při dělení třemi, čilia= 3i+ 1 neboa= 3i+ 2 pro vhodnéi. Analogicky, b = 3j + 1 nebob = 3j + 2 pro vhodnéj. Kdyža= 3i+ 1 ab = 3j + 1, paka·b = 9ij+ 3i+ 3j+ 1. Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2. Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(16)

Příklady argumentů (důkazů)

Příklad 2 Z ∀xL(x,B) a∀y(L(B,y) → y =M) plyne

B =M

:

Když∀xL(x,B), pak iL(B,B). Když ∀y(L(B,y) → y =M), pak iL(B,B) → B =M. Tedy B=M.

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

(17)

Příklady argumentů (důkazů)

B =M

: Když∀xL(x,B), pak iL(B,B).

Když ∀y(L(B,y) → y =M), pak iL(B,B) → B =M. Tedy B=M.

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

(18)

Příklady argumentů (důkazů)

B =M

: Když∀xL(x,B), pak iL(B,B). Když ∀y(L(B,y) → y =M), pak iL(B,B) → B =M.

Tedy B=M. Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

(19)

Příklady argumentů (důkazů)

Příklad 2 Z ∀xL(x,B) a∀y(L(B,y) → y =M) plyne B =M: Když∀xL(x,B), pak iL(B,B). Když ∀y(L(B,y) → y =M), pak iL(B,B) → B =M. Tedy B=M.

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

(20)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

(21)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Nechť jsou dánaa ab taková, že ¬(3|a) a¬(3|b).

Paka dává zbytek 1 nebo 2 při dělení třemi, čilia= 3i+ 1 neboa= 3i+ 2 pro vhodnéi. Analogicky, b = 3j + 1 nebob = 3j + 2 pro vhodnéj. Kdyža= 3i+ 1 ab = 3j + 1, paka·b = 9ij+ 3i+ 3j+ 1. Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2. Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(22)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Nechť jsou dánaa ab taková, že ¬(3|a) a¬(3|b). Pak a dává zbytek 1 nebo 2 při dělení třemi, čilia= 3i+ 1 neboa= 3i+ 2 pro vhodnéi.

Analogicky, b = 3j + 1 nebob = 3j + 2 pro vhodnéj. Kdyža= 3i+ 1 ab = 3j + 1, paka·b = 9ij+ 3i+ 3j+ 1. Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2. Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(23)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Nechť jsou dánaa ab taková, že ¬(3|a) a¬(3|b). Pak a dává zbytek 1 nebo 2 při dělení třemi, čilia= 3i+ 1 neboa= 3i+ 2 pro vhodnéi. Analogicky, b = 3j + 1 nebob = 3j+ 2 pro vhodné j.

Kdyža= 3i+ 1 ab = 3j + 1, paka·b = 9ij+ 3i+ 3j+ 1. Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2. Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(24)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Nechť jsou dánaa ab taková, že ¬(3|a) a¬(3|b). Pak a dává zbytek 1 nebo 2 při dělení třemi, čilia= 3i+ 1 neboa= 3i+ 2 pro vhodnéi. Analogicky, b = 3j + 1 nebob = 3j+ 2 pro vhodné j. Kdyža= 3i+ 1 ab = 3j + 1, paka·b = 9ij+ 3i+ 3j+ 1.

Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2. Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(25)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Kdyža= 3i+ 2 ab = 3j + 1, paka·b = 9ij+ 3i+ 6j+ 2.

Kdyža= 3i+ 1 ab = 3j + 2, paka·b = 9ij+ 6i+ 3j+ 2. Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(26)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1. Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(27)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1.

Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(28)

Příklady argumentů (důkazů)

Příklad 3 ∀a∀b(3|a·b → (3|a ∨ 3|b)):

Kdyža= 3i+ 2 ab = 3j + 2, paka·b = 9ij+ 6i+ 6j+ 3 + 1.

Ve všech případechMod(a·b,3) = 1, čili 3 není dělitel čísla a·b.

(29)

Analýza logických kroků v důkazech

Analýza logických kroků Ve všech důkazech se opakují stále tytéž logické kroky: specifikace čili konkretizace, modus ponens, rozbor případů (kdyžB → A i¬B → A, pakA), generalizace. Logické kroky jsou definovány čistě syntakticky, takže o jejich správném použití může rozhodovat počítač.

Kalkulus je soubor (soupis) takových kroků; obsahuje logické axiomy a odvozovací pravidla. Kalkuly se dnes uvažují hilbertovské, gentzenovské, . . .

Věta o úplnostipak tvrdí, že žádná další pravidla ani logické kroky nejsou potřeba: ty které máme, stačí ve všech (!) důkazech. Kanonická citace: [Göd30].

Algoritmický aspekt Korektnost důkazu lze verifikovatalgoritmem. Leibniz rozlišoval meziars inveniendia ars iudicandi.

(30)

Analýza logických kroků v důkazech

Věta o úplnostipak tvrdí, že žádná další pravidla ani logické kroky nejsou potřeba: ty které máme, stačí ve všech (!) důkazech. Kanonická citace: [Göd30].

(31)

Analýza logických kroků v důkazech

Věta o úplnostipak tvrdí, že žádná další pravidla ani logické kroky nejsou potřeba: ty které máme, stačí ve všech (!) důkazech.

Kanonická citace: [Göd30].

(32)

Analýza logických kroků v důkazech

Věta o úplnostipak tvrdí, že žádná další pravidla ani logické kroky nejsou potřeba: ty které máme, stačí ve všech (!) důkazech.

Kanonická citace: [Göd30].

Algoritmický aspekt Korektnost důkazu lze verifikovatalgoritmem.

Leibniz rozlišoval meziars inveniendia ars iudicandi.

(33)

Analýza předpokladů použitých v důkazech

Jazyk V Příkladu 3 hraje roli jazyk{+,·,0,1}obsahující symboly pro sčítání i násobení.

Matematické předpoklady V tomtéž příkladu je například použita distributivita násobení vůči sčítání, jednoznačnost dělení se zbytkem, . . .

Axiomatická teorie má jazyk a množinu axiomů. Například Peanova aritmetikaPA má (může mít) axiomy postulující asociativitu a komutativitu obou operací, distributivitu násobení vůči sčítání atd. Lze ji chápat jako vážný pokus o axiomatizaci struktury přirozených čísel, tj. strukturyN=hN,+,·,0,1i.

(34)

Analýza předpokladů použitých v důkazech

(35)

Analýza předpokladů použitých v důkazech

(36)

Lze určitou strukturu úplně axiomatizovat?

Přirozená čísla pouze s uspořádáním Uvažujme například, co platí ve struktuřehN, <i:

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y <x → ∃z(z <x & ¬∃v(z <v & v <x))). Jiné struktury Analogicky to dopadne také se strukturami hN,+,0i,hR, <i,hR,+,0i,R=hR,+,·,0,1i.

Čím je strukturaN=hN,+,·,0,1i jiná? Může se pro určitou formuliϕ(x) stát, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . v PA dokazatelné jsou, ale∀xϕ(x) není?Příklad 3naznačuje sentenci kdyžx je prvočíslo, pak kdykolivx dělí součina·b, dělí ia nebob. Ta tuto vlastnost alenemá.

(37)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

(38)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

(39)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Jiné struktury Analogicky to dopadne také se strukturami hN,+,0i,hR, <i,hR,+,0i,R=hR,+,·,0,1i.

(40)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Jiné struktury Analogicky to dopadne také se strukturami hN,+,0i,

hR, <i,hR,+,0i,R=hR,+,·,0,1i.

(41)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Jiné struktury Analogicky to dopadne také se strukturami hN,+,0i,hR, <i,

hR,+,0i,R=hR,+,·,0,1i.

(42)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Jiné struktury Analogicky to dopadne také se strukturami hN,+,0i,hR, <i,hR,+,0i,

R=hR,+,·,0,1i.

(43)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

(44)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Čím je strukturaN=hN,+,·,0,1i jiná?

Může se pro určitou formuliϕ(x) stát, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . v PA dokazatelné jsou, ale∀xϕ(x) není?Příklad 3naznačuje sentenci kdyžx je prvočíslo, pak kdykolivx dělí součina·b, dělí ia nebob. Ta tuto vlastnost alenemá.

(45)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Čím je strukturaN=hN,+,·,0,1i jiná? Může se pro určitou formuliϕ(x) stát, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . v PA dokazatelné jsou, ale∀xϕ(x) není?

Příklad 3naznačuje sentenci kdyžx je prvočíslo, pak kdykolivx dělí součina·b, dělí ia nebob. Ta tuto vlastnost alenemá.

(46)

Lze určitou strukturu úplně axiomatizovat?

∀x∀y∀z(x <y & y<z → x <z),

∀x∀y(x<y → ¬(y <x)),

∀x∀y(x<y ∨ x =y ∨ y <x),

∃x∀y¬(y<x),

∀x∃y(x<y & ¬∃v(x<v & v <y)),

∀x∀y(y<x → ∃z(z <x & ¬∃v(z <v & v <x))).

Čím je strukturaN=hN,+,·,0,1i jiná? Může se pro určitou formuliϕ(x) stát, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . v PA dokazatelné jsou, ale∀xϕ(x) není?Příklad 3naznačuje sentenci kdyžx je prvočíslo, pak kdykolivx dělí součina·b, dělí ia nebob.

(47)

Rekurzívní a rekurzívně spočetné množiny

Definice Množina A(přirozených čísel nebo slov v nějaké abecedě) jerekurzívní, jestliže existuje algoritmus, který rozhoduje o náležení doA.

Definice Množina Ajerekurzívně spočetná (RE), jestliže existuje procedura (algoritmus, který nevyžaduje žádný vstup), která, je-li spuštěna, postupně vygeneruje všechny prvky množinA.

Definice (alternativní) AjeRE, jestliže existuje rekurzívní relace R taková, že∀x(x ∈A ⇔ ∃yR(x,y)).

Příklad Když T je teorie s rekurzívní množinou axiomů (rekurzívně axiomatizovatelnáteorie), pak relace R(x,y) definovaná

podmínkouR(x,y) ⇔ x je sentence ay je její důkaz v T

je rekurzívní. MnožinaThm(T) všech sentencí dokazatelných vT jeRE.

(48)

Rekurzívní a rekurzívně spočetné množiny

Definice (alternativní) AjeRE, jestliže existuje rekurzívní relace R taková, že∀x(x ∈A ⇔ ∃yR(x,y)).

(49)

Rekurzívní a rekurzívně spočetné množiny

Definice (alternativní) AjeRE, jestliže existuje rekurzívní relace R taková, že∀x(x ∈A ⇔ ∃yR(x,y)).

(50)

Rekurzívní a rekurzívně spočetné množiny

Definice (alternativní) AjeRE, jestliže existuje rekurzívní relace R taková, že∀x(x ∈A ⇔ ∃yR(x,y)).

(51)

Rekurzívní a RE množiny (pokračování)

Platí (a) Každá rekurzívní AjeRE, ale opačná inkluze neplatí.

(b) Komplement−Arekurzívní množinyA je opět rekurzívní množina.

(c) Komplement−AmnožinyA, která jeRE, je rekurzívní pouze tehdy, kdyžA je dokonce rekurzívní.

Aplikace v logice

Sent Th(N)

Thm(T) Ref(T)

T

(52)

Rekurzívní a RE množiny (pokračování)

Platí (a) Každá rekurzívní AjeRE, ale opačná inkluze neplatí.

(b) Komplement−Arekurzívní množinyA je opět rekurzívní množina.

(c) Komplement−AmnožinyA, která jeRE, je rekurzívní pouze tehdy, kdyžA je dokonce rekurzívní.

Aplikace v logice

Sent Th(N)

Thm(T) Ref(T)

T

(53)

Věty o neúplnosti

Platí (a) KdyžT je rekurzívně axiomatizovatelná teorie

v aritmetickém jazyce, jejíž všechny axiomy platí vN, pak existuje formuleϕ(x) taková, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . jsou vT dokazatelné, ale ∀xϕ(x) dokazatelná není.

(b) Je-liT navíc rozšíření Peanovy aritmetiky, vT lze formalizovat logickou syntax, a zaϕ(x) pak lze vzít formuli číslox není

důkazem (není numerickým kódem důkazu) sporu vT.

(54)

Věty o neúplnosti

Platí (a) KdyžT je rekurzívně axiomatizovatelná teorie

v aritmetickém jazyce, jejíž všechny axiomy platí vN, pak existuje formuleϕ(x) taková, že všechny instance ϕ(0), ϕ(1), ϕ(2), . . . jsou vT dokazatelné, ale ∀xϕ(x) dokazatelná není.

(b) Je-liT navíc rozšíření Peanovy aritmetiky, v T lze formalizovat logickou syntax, a zaϕ(x) pak lze vzít formuli číslox není

důkazem (není numerickým kódem důkazu) sporu vT.

(55)

Dodatky

Cvičení Napište v aritmetickém jazyce formuli, která vyjadřuje, že číslox je mocninou dvojky.

Kdyžp je prvočíslo ap |a·b, pak p |a nebop |b

Nechťp není dělitelem čísla a. V tom případě, protožep je prvočíslo, číslaaa p jsou spolu nesoudělná. Dle Bezoutovy věty existují číslax ay taková, že ax −py = 1. Z toho máme abx−pby =b. Číslo p je dělitelem jak čísla abx, tak čísla pby. Tedyp |b.

(56)

Literatura

K. Gödel. Die Vollständigkeit der Axiome des logischen Funktionenkalküls. Monatsh. Math. Phys., 37:349–360, 1930.

K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatsh. Math.

Phys., 38:173–198, 1931.

J. Malina a J. Novotný, editoři. Kurt Gödel. Georgetown, Nauma, Brno, 1996.

C. H. Papadimitriou. Computational Complexity.

Addison-Wesley, 1994.