Richardův paradox - Richard's paradox

V logice , Richardův paradox je sémantické antinomie z teorie množin a přirozeného jazyka poprvé popsal francouzský matematik Jules Richard v roce 1905. Paradoxní je běžně používán motivovat je důležité pečlivě rozlišovat mezi matematikou a metamathematics .

Kurt Gödel konkrétně uvádí Richardovu antinomii jako sémantický analogický výsledek jeho syntaktické neúplnosti v úvodní části „ O formálně nerozhodnutelných návrzích v Principia Mathematica a souvisejících systémech I “. Paradox byl také motivací rozvoje predikativní matematiky.

Popis

Původní tvrzení o paradoxu, způsobené Richardem (1905), silně souvisí s Cantorovým diagonálním argumentem o nespočitatelnosti množiny reálných čísel .

Paradox začíná pozorováním, že určité výrazy přirozeného jazyka definují reálná čísla jednoznačně, zatímco jiné výrazy přirozeného jazyka nikoli. Například „Skutečné číslo, jehož celočíselná část je 17 a n -té desetinné místo je 0, pokud n je sudé a 1, pokud n je liché“ definuje skutečné číslo 17.1010101 ... = 1693/99, zatímco fráze „hlavní město Anglie“ nedefinuje skutečné číslo, ani fráze „nejmenší kladné celé číslo nedefinovatelné pod šedesát písmen“ (viz Berryho paradox ).

Existuje tedy nekonečný seznam anglických frází (takový, že každá fráze má konečnou délku, ale samotný seznam má nekonečnou délku), které jednoznačně definují reálná čísla. Tento seznam frází nejprve uspořádáme zvětšením délky, poté uspořádáme všechny fráze stejné délky lexikograficky (ve slovníkovém pořadí, např. Můžeme použít kód ASCII , fráze mohou obsahovat pouze kódy 32 až 126), takže řazení je kanonické . Výsledkem je nekonečný seznam odpovídajících reálných čísel: r 1 , r 2 , .... Nyní definujte nové reálné číslo r následujícím způsobem. Celá část r je 0, n -té desetinné místo r je 1, pokud n -té desetinné místo r n není 1 a n -té desetinné místo r je 2, pokud n -té desetinné místo r n je 1.

Předchozí odstavec je výraz v angličtině, který jednoznačně definuje skutečné číslo r . Tedy r musí být jedno z čísel r n . Avšak r bylo zkonstruováno tak, že se nemůže rovnat žádnému z r n (tedy r je nedefinovatelné číslo ). To je paradoxní rozpor.

Analýza a vztah k metamatematice

Richardův paradox má za následek neudržitelný rozpor, který je třeba analyzovat, aby se zjistila chyba.

Navrhovaná definice nového skutečného čísla r jasně zahrnuje konečnou posloupnost znaků, a proto se nejprve zdá být definicí skutečného čísla. Definice však odkazuje na samotnou definovatelnost v angličtině. Pokud by bylo možné určit, které anglické výrazy ve skutečnosti to definovat reálné číslo, a které ne, pak paradox by projít. Řešení Richardova paradoxu tedy spočívá v tom, že neexistuje žádný způsob, jak jednoznačně přesně určit, které anglické věty jsou definicemi reálných čísel (viz Good 1966). To znamená, že neexistuje žádný způsob, jak v konečném počtu slov popsat, jak zjistit, zda libovolný anglický výraz je definicí skutečného čísla. To není překvapivé, protože schopnost provést toto určení by také znamenala schopnost vyřešit problém se zastavením a provést jakýkoli jiný nealgoritmický výpočet, který lze popsat v angličtině.

K podobnému jevu dochází ve formalizovaných teoriích, které jsou schopny odkazovat na vlastní syntaxi, jako je například teorie množin Zermelo – Fraenkel (ZFC). Řekněme, že vzorec φ ( x ) definuje reálné číslo, pokud existuje právě jedno skutečné číslo r takové, že platí φ ( r ). Pak není možné pomocí ZFC definovat množinu všech ( Gödelových čísel ) vzorců, které definují reálná čísla. Neboť kdyby bylo možné definovat tuto množinu, bylo by možné ji diagonalizovat a vytvořit novou definici skutečného čísla podle výše uvedeného Richardova paradoxu. Všimněte si, že sada vzorců, které definují reálná čísla, může existovat jako množina F ; omezení ZFC je, že neexistuje žádný vzorec, který by definoval F bez odkazu na jiné sady. S tím souvisí Tarskiho věta o neurčitosti .

Příklad ZFC ilustruje důležitost rozlišení metamatematiky formálního systému od prohlášení samotného formálního systému. Vlastnost D (φ), kterou vzorec φ ZFC definuje jedinečné reálné číslo, není sama vyjádřitelná ZFC, ale musí být považována za součást metateorie používané k formalizaci ZFC. Z tohoto pohledu Richardův paradox vyplývá ze zpracování konstrukce metateorie (výčet všech příkazů v původním systému, které definují reálná čísla), jako by tuto konstrukci bylo možné provést v původním systému.

Obměna: Richardianova čísla

Variace paradoxu používá namísto reálných čísel celá čísla, přičemž zachovává sebereferenční charakter originálu. Zvažte jazyk (například angličtinu), ve kterém jsou definovány aritmetické vlastnosti celých čísel. Například „první přirozené číslo“ definuje vlastnost prvního přirozeného čísla, jedna; a „dělitelné přesně dvěma přirozenými čísly“ definuje vlastnost prvočísla . (Je jasné, že některé vlastnosti nelze definovat explicitně, protože každý deduktivní systém musí začínat některými axiomy . Pro účely tohoto argumentu se však předpokládá, že fráze jako „celé číslo je součtem dvou celých čísel“ jsou již pochopeny. .) Přestože je seznam všech takových možných definic sám nekonečný, je snadno vidět, že každá jednotlivá definice se skládá z konečného počtu slov, a tedy také z konečného počtu znaků. Protože je to pravda, můžeme definice uspořádat nejprve podle délky a poté lexikograficky .

Nyní můžeme každou definici namapovat na množinu přirozených čísel , takže definice s nejmenším počtem znaků a abecedním pořadím bude odpovídat číslu 1, další definice v řadě bude odpovídat 2 a tak dále. Vzhledem k tomu, že každá definice je spojena s jedinečným celým číslem, je možné, že občas celé číslo přiřazené definici odpovídá této definici. Pokud by například definice „nedělitelná žádným jiným číslem než 1 a sama“ byla 43., pak by to byla pravda. Protože 43 není samo o sobě dělitelné žádným jiným číslem než 1 a samo, pak číslo této definice má vlastnost samotné definice. To však nemusí vždy platit. V případě, že definice „dělitelné 3“ byl přidělen na číslo 58, pak počet definice však nebude mít vlastnost samotného definice. Protože 58 není samo o sobě dělitelné 3. Tento druhý příklad bude nazýván jako majetek Richardian . Pokud je tedy číslo Richardian, pak definice odpovídající tomuto číslu je vlastnost, kterou samotné číslo nemá. (Více formálně, „ x je Richardian“ je ekvivalentní „ X se nebude mít vlastnost určený vymezující výraz, s níž x je v korelaci v sériově uspořádané soustavě definic“). Proto v tomto příkladu 58 Richardian, ale 43 není.

Protože vlastnost být Richardianem je sama o sobě číselnou vlastností celých čísel, patří do seznamu všech definic vlastností. Proto je vlastnosti bytí Richardian přiřazeno nějaké celé číslo, n . Například definici „být Richardiánem“ lze přiřadit číslu 92. Nakonec se paradoxem stává: Je 92 Richardián? Předpokládejme, že 92 je Richardian. To je možné pouze tehdy, pokud 92 nemá vlastnost určenou definujícím výrazem, se kterým je v korelaci. Jinými slovy to znamená, že 92 není Richardian, což je v rozporu s naším předpokladem. Pokud však předpokládáme, že 92 není Richardian, pak má definující vlastnost, které odpovídá. To podle definice znamená, že je to Richardian, opět v rozporu s předpokladem. Tvrzení „92 je Richardian“ tedy nelze důsledně označovat jako pravdivé ani nepravdivé.

Vztah k predikivismu

Další názor týkající se Richardova paradoxu se týká matematického predikativismu . Tímto pohledem jsou skutečná čísla definována ve fázích, přičemž každá fáze odkazuje pouze na předchozí fáze a další věci, které již byly definovány. Z predikativního hlediska není platné kvantifikovat všechna reálná čísla v procesu generování nového reálného čísla, protože se předpokládá, že to má za následek problém s kruhovitostí v definicích. Teorie množin, jako je ZFC, nevycházejí z tohoto druhu predikčního rámce a umožňují definice s náhledem.

Richard (1905) představil řešení paradoxu z hlediska predicativisimu. Richard tvrdil, že chyba paradoxní konstrukce spočívala v tom, že výraz pro konstrukci reálného čísla r ve skutečnosti jednoznačně nedefinuje reálné číslo, protože tvrzení odkazuje na konstrukci nekonečné množiny reálných čísel, z nichž samotné r je odděleně. Richard tedy říká, že skutečné číslo r nebude zahrnuto jako žádné r n , protože definice r nesplňuje kritéria pro zařazení do posloupnosti definic použitých k sestavení posloupnosti r n . Současní matematici se shodují, že definice r je neplatná, ale z jiného důvodu. Věří, že definice r je neplatná, protože neexistuje přesně definovaný pojem, kdy anglická fráze definuje skutečné číslo, a neexistuje tedy žádný jednoznačný způsob, jak sestrojit sekvenci r n .

Přestože Richardovo řešení paradoxu nezískalo přízeň matematiků, predikativismus je důležitou součástí studia základů matematiky . Predikativismus byl poprvé podrobně studován Hermannem Weylem v Das Kontinuum , kde ukázal, že velkou část elementární reálné analýzy lze provést predikativním způsobem počínaje pouze přirozenými čísly . Více nedávno, predicativism byl studován Solomon Feferman , kdo používal teorii důkazu prozkoumat vztah mezi predicativní a impredicative systémy.

Viz také

Reference

  1. ^ Solomon Feferman, „ Predicativity “ (2002)
  • Fraenkel, Abraham; Bar-Hillel, Yehoshua & Levy, Azriel (1973). Základy teorie množin . Ve spolupráci s Dirkem van Dalenem (druhé vydání). Amsterdam: Noord-Hollandsche. ISBN 0-7204-2270-1.
  • Dobře, IJ (1966). „Poznámka k Richardovu paradoxu“. Mysl . 75 (299): 431. doi : 10,1093/mind/LXXV.299.431 .
  • Richard, Jules (1905). Les Principes des Mathématiques et le Problème des Ensembles . Revue Générale des Sciences Pures et Appliquées.Přeloženo do Heijenoort, J. van, ed. (1964). Zdrojová kniha v matematické logice 1879-1931 . Cambridge, MA: Harvard University Press.

externí odkazy