pondělí 27. dubna 2009

Dva logické stroje

První stroj lze nalézt ve Smullyanově knize Navěky nerozhodnuto. Stroj používá pouze těchto šest symbolů: P, → ⊥, (, ) a R. Stroj tiskne věty složené z těchto znaků. Věta a pravdivá věta je definována pomocí těchto pravidel:
(1) ⊥ je věta. Tato věta je nepravdivá.
(2) Jestliže je X a Y věta, pak je (XY) také věta. Tato věta je pravdivá, jestliže je pravdivá Y nebo není nepravdivá X.
(3) Pro každou větu X je věta i PX. Tato věta je pravdivá, jestliže stroj může vytisknout X.
(4) Kro každé dvě věty X a Y je (X R Y) také věta. Tato věta je pravdivá, jestliže stroj může vytisknout ((X R X) → Y).
Axiómy stroje jsou tyto:
(I) Všechny tautologie.
(II) Všechny věty ve tvaru P(XY) → (PXY).
(III) Všechny věty ve tvaru PXPPX.
(IV) Všechny věty ve tvaru (X R Y) ↔ P((X R X) → Y).
Použitá spojka AB je zkratka za (((AB) → ((BA) → ⊥)) → ⊥).
Operační pravidla tohoto stroje jsou:
(A) Může být vytištěn jakýkoli axióm.
(B) Jestliže byla vytištěna věta X a věta (XY), pak stroj může vytisknout větu Y.
(C) Jestliže byla vytištěna věta X, stroj může vytisknout PX.

Všechny axiómy jsou pravdivé. Lze se snadno přesvědčit, že stroj může vytisknout jen pravdivé věty. Stroj je tedy bezesporný. Zkoumejme dále tento stroj. Pro libovolné dvě věty X a Y podle (IV) platí, že věta

(X R Y) ↔ P((X R X) → Y)

může být vytištěna. Platí to tedy i pro X = Y. Stroj tedy může vytisknout

(X R X) ↔ P((X R X) → X).

Tudíž podle (4) stroj může vytisknout i větu

(X R XX) ↔ (P((X R X) → X) → X)

Zvolme nyní za X větu ⊥. Zkrátím-li (A → ⊥) jako, ¬A a větu (⊥ R ⊥ → ⊥) na G, pak lze napsat, že stroj může vytisknout

G ↔ (¬PG).

Tato věta je pravdivá, jestliže stroj nikdy větu G nevytiskne. A protože stroj tiskne jen pravdivé věty, stroj nikdy větu G nevytiskne. Přitom věta G je pravdivá. Smullyan větě G říká z pochopitelného důvodu věta Gödelova.

Jiný a jednodušší stroj lze nalézt ve Smullyanově knize Gödel’s Incompleteness Theorems. Stroj používá pět znaků: P, N, ~, ( a ). Závorky nemusí párovat. Řetězec P(x) znamená, že x je tisknutelný. Řetězec ~P(x) znamená, že x je netisknutelný. Norma řetězce x je řetězec x(x). Řetězec PN(x) znamená, že norma řetězce x je tisknutelná, a ~PN(x) znamená, že norma x je netisknutelná. Předpokládejme, že stroj tiskne jen pravdivé řetězce. Mějme řetězec ~PN(~PN). Tato věta znamená, že norma ~PN je netisknutelná. Norma ~PN je řetězec ~PN(~PN). Věta tedy sama o sobě říká, že je netisknutelná. Ale ani řetězec PN(~PN) není tisknutelný, protože pak by byl tisknutelný i ~PN(~PN) a stroj by se dostal do sporu sám se sebou. Řetězec ~PN(~PN) ani PN(~PN) stroj nevytiskne, ať už ho naprogramujeme jakkoli. Máme tu jasný příklad nerozhodnutelného tvrzení. Podívejme se ještě na větu ~P(~PN(~PN)). Tento řetězec už stroj vytisknout může. Stejně tak řetězec ~P(PN(~PN)). Tedy stroj, stejně jako v předchozím případě, věty o tom, že existuje nerozhodnutelný problém, stroj rozhodnout může.

Popisy těchto strojů nejsou ekvivalentní první Gödelově větě o neúplnosti, ale mají některé společné prvky.

neděle 19. dubna 2009

Gödel píše o Kantovi

Esej, ze které je citovaná ukázka, napsal Gödel v roce 1961. Celá je k dispozici zde.

I would like to point out that this intuitive grasping of ever newer axioms that are logically independent from the earlier ones, which is necessary for the solvability of all problems even within a very limited domain, agrees in principle with the Kantian conception of mathematics. The relevant utterances by Kant are, it is true, incorrect if taken literally, since Kant asserts that in the derivation of geometrical theorems we always need new geometrical intuitions, and that therefore a purely logical derivation from a finite number of axioms is impossible. That is demonstrably false. However, if in this proposition we replace the term "geometrical" - by "mathematical" or "set-theoretical", then it becomes a demonstrably true proposition. I believe it to be a general feature of many of Kant's assertions that literally understood they are false but in a broader sense contain deep truths. In particular, the whole phenomenological method, as I sketched it above, goes back in its central idea to Kant, and what Husserl did was merely that he first formulated it more precisely, made it fully conscious and actually carried it out for particular domains. Indeed, just from the terminology used by Husserl, one sees how positively he himself values his relation to Kant. I believe that precisely because in the last analysis the Kantian philosophy rests on the idea of phenomenology, albeit in a not entirely clear way, and has just thereby introduced into our thought something completely new, and indeed characteristic of every genuine philosophy - it is precisely on that, I believe, that the enormous influence which Kant has exercised over the entire subsequent development of philosophy rests. Indeed, there is hardly any later direction that is not somehow related to Kant's ideas. On the other hand, however, just because of the lack of clarity and the literal incorrectness of many of Kant's formulations, quite divergent directions have developed out of Kant's thought - none of which, however, really did justice to the core of Kant's thought. This requirement seems to me to be met for the first time by phenomenology, which, entirely as intended by Kant, avoids both the death-defying leaps of idealism into a new metaphysics as well as the positivistic rejection of all metaphysics. But now, if the misunderstood Kant has already led to so much that is interesting in philosophy, and also indirectly in science, how much more can we expect it from Kant understood correctly?
Kurt Gödel – The modern development of the foundations of mathematics in the light of philosophy

Chtěl bych upozornit na to, že toto intuitivní pojímání stále nových a nových axiomů, logicky nezávislých na axiomech dřívějších, které je nutné pro řešitelnost všech problémů v nějaké velmi omezené oblasti, je v principiální shodě s Kantovým pojetím matematiky. Kantovy výroky na toto téma jsou ovšem doslovně vzaty nesprávné, neboť Kant tvrdí, že k odvozování geometrických vět potřebujeme stále nové geometrické názory a že tedy jejich čistě logické odvození z konečného počtu axiomů není možné. To je prokazatelná nepravda. Jestliže však v tomto výroku nahradíme termín „geometrické“ termínem „matematické“, nebo „množinové“, stane se z něj prokazatelně správný výrok. Jsem přesvědčen, že toto je obecná vlastnost mnoha Kantových tvrzení, že totiž doslovně chápána jsou nepravdivá, avšak v obecném smyslu obsahují hluboké pravdy. Zvláště pak celá fenomenologická metoda (...) sahá zpět ve své ideji ke Kantovi, a to, co udělal Husserl, bylo jen to, že tuto ideu poprvé přesně formuloval a plně si ji uvědomil a uskutečnil ji pro jednotlivé oblasti. Už z terminologie, kterou Husserl používá, vidíme, jak kladně on sám oceňuje svůj vztah ke Kantovi. Jsem přesvědčen, že právě v tom, že Kantova filosofie spočívá nakonec byť i ne zcela jasným způsobem na ideji fenomenologie a tím uvedla do myšlení něco zcela nového a pro každou pravou filosofii charakteristického, spočívá obrovský vliv, který měl Kant na celý následný vývoj filosofie. Jistě, stěží existuje nějaký pozdější směr, který by se nějak nevztahoval ke Kantovým idejím. Z druhé strany však právě vzhledem k nejasnosti a doslovné nepravdivosti mnoha Kantových formulací se z Kantova myšlení vyvinuly zcela protikladné filosofické směry, z nichž však žádný nebyl práv jádru Kantova myšlení. Tento požadavek se mi zdá být uspokojivě naplněn teprve ve fenomenologii, který se zcela v Kantově smyslu vyhýbá jak saltu mortale idealismu do nové metafysiky, tak pozitivistickému odmítnutí jakékoli metafysiky. Jestliže však i takto špatně pochopený Kant vedl k tolika zajímavým věcem ve filosofii a nepřímo i ve vědě, co teprve můžeme očekávat od Kanta pochopeného správně?
Kurt Gödel – Moderní vývoj ve světle filosofie

čtvrtek 16. dubna 2009

Gödel o „vnímáni“ matematických objektů

Avšak vzdor tomu, že jsou vzdáleny od smyslových zkušeností, máme něco jako vnímání i objektů teorie množin, jak je vidět z faktu, že se nám axiomy vnucují jako pravdivé. Nevidím žádný důvod, proč bychom měli mít menší důvěru k tomuto druhu vjemů, tj. matematické intuici, než k vnímání smyslovému, které nás vede k vytváření fyzikálních teorií a k očekávání, že další smyslové vjemy s nimi budou souhlasit, a navíc k víře, že otázka, která nyní není rozhodnutelná, má smysl a může být rozhodnuta v budoucnu. Paradoxy teorie množin jsou stěží větší překážkou pro matematiku, než smyslové klamy pro fyziku. To, že jsou nové matematické intuice vedoucí k rozhodnutí takových problémů, jako je Cantorova hypotéza kontinua, dokonale možné, bylo již ukázáno dříve. Je třeba poznamenat, že matematická intuice nemusí být chápána jako nějaká schopnost bezprostředního poznání zkoumaných objektů. Spíše se zdá, že stejně jako v případě fyzikálních zkušeností vytváříme naše ideje i o těchto objektech na základě něčeho jiného, co však je bezprostředně dané. Rozdíl je jen v tom, že toto něco jiné nejsou, aspoň ne primárně, vjemy. To, že kromě vjemů je něco skutečně bezprostředně dáno, plyne (nezávisle na matematice) ze skutečnosti, že i naše ideje, které odkazují k fyzikálním objektům, obsahují složky kvalitativně odlišné od vjemů, nebo pouhých kombinací vjemů, např. ideu objektu samého, kdežto na druhé straně nemůžeme naším myšlení stvořit žádné kvalitativně nové prvky, nýbrž pouze reprodukovat a kombinovat ty, které jsou dány. Evidentně to „dané“, na čem se zakládá matematika, je těsně spjato s abstraktními prvky obsaženými v našich empirických idejích. [Všimněte si, že existuje těsná souvislost mezi pojmem množiny (...) a kategoriemi čistého rozumu v Kantově smyslu. Funkcí obou je totiž „syntéza“, tj. vytváření jednot z mnohostí (např. u Kanta vytváření ideje jednoho objektu z jeho rozmanitých aspektů).] Z toho však v žádném případě neplyne, že data tohoto druhého druhu, protože nemohou být spojována s působením určitých věcí na naše smyslové orgány, jsou něčím čistě subjektivním, jak tvrdil Kant. Spíše mohou představovat nějaký aspekt objektivní reality, avšak v protikladu k vjemům mohou v nás být přítomné díky jinému druhu vztahu mezi námi a realitou.
Kurt Gödel – Co je Cantorův problém kontinua

úterý 14. dubna 2009

Locke o panství člověka nad rozumem

The dominion of man, in this little world of his own understanding being much what the same as it is in the great world of visible things; wherein his power, however managed by art and skill, reaches no farther than to compound and divide the materials that are made to his hand; but can do nothing towards the making the lest particle of new matter, or destroying one atom of what is already in being. The same inability will every one find in himself, who shall go about to fashion in his understanding one simple idea, not received in by his senses from external objects, or by reflection from the operations of his own mind about them.
John Locke – An Essay Concerning Humane Understanding

Panství člověka v tomto malém světě jeho vlastního rozumu se nadmíru podobá tomu, které uplatňuje ve velkém světě viditelných věcí, kde jeho moc, ať už jakkoli zdokonalovaná dovedností a obratností, nesahá dále než ke skládání a rozkládání tohoto materiálu, který mu byl dán k dispozici; avšak nemůže učinit sebeméně pro to, aby vytvořil sebemenší částečku nové hmoty nebo aby zničil jediný atom z těch, které už jsou součástí jsoucna. Se stejnou neschopností se setká každý sám u sebe, pokud se pokusí zpodobnit ve svém rozumu jakoukoli jednoduchou ideu, nepřejatou jeho smysly z vnějších objektů nebo reflexí toho, jak jeho mysl nakládá s ideami pocházejícími ze smyslů.
John Locke – Esej o lidském rozumu

Knihu Esej o lidském rozumu lze stáhnout zde. Jedná se však jen o výběr.

středa 8. dubna 2009

Smullyan o ontologickém důkazu

Chci dokázat, že existuje jednorožec. K tomu postačí dokázat silnější (jen zdánlivé) tvrzení, že existuje existující jednorožec. (Existujícím jednorožcem samozřejmě myslím jednorožce, který existuje.) Je totiž zřejmé, že pokud existuje existující jednorožec, pak existuje jednorožec. Dokážeme tedy, že existuje existující jednorožec. Jsou pravé dvě možnosti:
(1) Existující jednorožec existuje.
(2) Existující jednorožec neexistuje.
Možnost (2) je však zřejmě rozporná, jak by existující jednorožec mohl neexistovat? Tak jako je pravda, že běžící jednorožec běží, existující jednorožec existuje. Co na tomhle důkazu nehraje? Je to vlastně vypreparovaná podstata Descartova proslulého ontologického důkazu existence Boha, Descartes definuje Boha jako bytost mající všechny vlastnosti vůbec. Podle této definice má Bůh i vlastnost existence, takže Bůh existuje. Immanuel Kant označil Descartův argument jako chybný a zdůvodňoval to tím, že existence není vlastnost. Já myslím, že v důkaze je chyba daleko závažnější. Nehodlám se tu přít o tom, jeli existence vlastnost. Ukážu, že i kdyby existence vlastností byla, důkaz je to stejně pochybný. Podívejme se nejdřív důkladně na náš důkaz existence jednorožce. Když řeknu „Existující jednorožec existuje“, není jasné, mám-li na mysli, že každý existující jednorožec existuje, nebo že existuje vůbec nějaký existující jednorožec. Kdybych měl na mysli první význam, pak by to byla pravda – samozřejmě všichni existující jednorožci existují – jak by mohl nějaký existující jednorožec neexistovat? Jenomže to ještě neznamená, že ten výrok je pravdivý i ve druhém významu, to jest, že musí existovat nějaký existující jednorožec. Podobně je tomu s Descartovým důkazem: vyplývá z něho v podstatě jen to, že každý Bůh existuje, to jest že cokoliv, co vyhovuje Descartově definici Boha, musí mít i vlastnost existence, jenomže to neznamená, že musí vůbec nějaký Bůh existovat.
Raymond Merrill Smullyan – Jak se jmenuje tahle knížka