Impredicativity - Impredicativity

V matematice , logice a filozofii matematiky , něco, co je impredicative je self-odkazování na definici . Zhruba řečeno, definice je impredikativní, pokud vyvolává (zmiňuje nebo kvantifikuje) definovanou množinu nebo (běžněji) jinou množinu, která obsahuje definovanou věc. Neexistuje obecně přijímaná přesná definice toho, co to znamená být predikativní nebo nedůvěřivý. Autoři uvedli různé, ale související definice.

Opakem impredikativity je predikativita, což v podstatě znamená budování stratifikovaných (nebo rozvětvených) teorií, kde kvantifikace na nižších úrovních vede k proměnným nějakého nového typu, odlišených od nižších typů, nad kterými se proměnná pohybuje. Prototypickým příkladem je intuicionistická teorie typů , která si zachovává rozvětvení, aby se zbavila nedůtklivosti.

Russellův paradox je slavným příkladem nedůstojné konstrukce - jmenovitě množina všech množin, které neobsahují samy sebe. Paradoxem je, že takový soubor nemůže existovat: Pokud by existovalo, otázka by mohla být požádána, zda obsahuje sám, nebo ne - pokud ano, pak již pojmově to neměli, a pokud tomu tak není, pak podle definice by měla.

Největší spodní odhady z množiny X , GLB ( X ) , má také impredicative definici: y = GLB ( X ), tehdy a jen tehdy, jestliže pro všechny prvky x o X , y je menší než nebo se rovná x , a jakýkoli z méně než nebo rovno všem prvkům X je menší nebo rovno y . Tato definice kvantifikuje přes množinu (potenciálně nekonečnou , v závislosti na dotyčném pořadí ), jejíž členy jsou dolní hranice X , z nichž jeden je samotný glb. Proto by predikativismus tuto definici odmítl.

Dějiny

Pojmy „predikativní“ a „impredikativní“ zavedl Russell (1907) , ačkoli se od té doby význam trochu změnil.

Solomon Feferman poskytuje historický přehled predikativity a spojuje ji s aktuálními vynikajícími výzkumnými problémy.

Princip bludného kruhu navrhli Henri Poincaré (1905-6, 1908) a Bertrand Russell v návaznosti na paradoxy jako požadavek na legitimní zadané specifikace. Sady, které nesplňují požadavek, se nazývají impredicative .

První moderní paradox se objevil u otázky Cesare Burali-Fortiho z roku 1897 týkající se transfinitních čísel a stal by se známým jako paradox Burali-Forti . Cantor zjevně objevil stejný paradox ve své (Cantorově) „naivní“ teorii množin, která se stala známou jako Cantorův paradox . Russellovo povědomí o problému vzniklo v červnu 1901 čtením Fregeova pojednání o matematické logice, jeho 1879 Begriffsschrift ; trestná věta ve věci Frege je následující:

Na druhou stranu se také může stát, že argument je determinovaný a funkce neurčitá.

Jinými slovy, vzhledem k f ( a ) je funkce f proměnná a a je neměnná část. Tak proč ne nahradit hodnotu f ( z ) pro f sebe? Russell pohotově napsal Fregeovi dopis poukazující na to, že:

Uvedete ... že i funkce může fungovat jako neurčitý prvek. Tomu jsem dříve věřil, ale nyní se mi tento názor zdá pochybný kvůli následujícímu rozporu. Nechť w je predikát: být predikátem, který sám o sobě nelze predikovat. Může w být založena samo o sobě? Z každé odpovědi vyplývá její opak. Zde musíme dojít k závěru, že w není predikát. Stejně tak neexistuje žádná třída (jako celek) těch tříd, které každá z nich jako celek nepatří k sobě. Z toho usuzuji, že za určitých okolností definovatelná sbírka netvoří souhrn.

Frege pohotově odepsal Russellovi a uznal problém:

Vaše objevení rozporu mě způsobilo největší překvapení a, skoro bych řekl, zděšení, protože otřáslo základem, na kterém jsem měl v úmyslu stavět aritmetiku.

Zatímco problém měl nepříznivé osobní důsledky pro oba muže (oba měli práce u tiskařů, které musely být upraveny), van Heijenoort poznamenává, že „paradox otřásl světem logiků a dunění je cítit dodnes ... Russellův paradox , který používá holé představy množiny a prvku, spadá přímo do oblasti logiky. Paradox byl poprvé publikován Russellem v The Principy matematiky (1903) a je zde velmi podrobně diskutován ... “. Russell, po šesti letech falešných začátků, by na tuto otázku nakonec odpověděl svou teorií typů z roku 1908 „předložením svého axiomu redukovatelnosti . Říká, že jakákoli funkce je souběžná s tím, co nazývá predikativní funkcí: funkcí, ve které typy zdánlivé proměnné nepřesahují typy argumentů ". Ale tento „axiom“ narazil na odpor všech stran.

Odmítnutí nedefinovaně definovaných matematických objektů (při přijímání přirozených čísel jako klasicky chápaných) vede k postavení ve filozofii matematiky známému jako predikativismus, které obhajují Henri Poincaré a Hermann Weyl ve svém Das Kontinuum . Poincaré a Weyl tvrdili, že nedůstojné definice jsou problematické, pouze když je jedna nebo více základních sad nekonečných.

Ernst Zermelo ve své knize z roku 1908 „Nový důkaz o možnosti řádného objednání“ představuje celou část „b. Námitka týkající se nepředvídatelné definice “, kde argumentoval proti „Poincaré (1906, s. 307) [který uvádí, že] definice je „predikativní“ a logicky přípustný, pouze pokud vylučuje všechny objekty, které jsou závislé na definovaném pojmu, tj. které jej mohou jakýmkoli způsobem určit “. Uvádí dva příklady neurčitých definic - (i) pojem Dedekindových řetězců a (ii) „v analýze, kdykoli se pro další závěry použije maximum nebo minimum dříve definované„ dokončené “množiny čísel Z. To se stane, například , ve známém Cauchyově důkazu ... “. Svou část zakončí následujícím postřehem: „Definice se může velmi dobře opírat o pojmy, které jsou ekvivalentní pojmu, který je definován; v každé definici jsou definiens a definiendum rovnocennými pojmy a důsledné dodržování Poincarého požadavku by znamenalo, že každá definice , tedy celá věda, nemožné “.

Zermeloův příklad minima a maxima dříve definované „dokončené“ množiny čísel se znovu objevuje v Kleene 1952: 42-42, kde Kleene používá příklad nejmenší horní meze ve své diskusi o nedůstojných definicích; Kleene tento problém nevyřeší. V následujících odstavcích se popisuje Weyl pokus v jeho 1918 Das Kontinuum ( kontinua ) k odstranění impredicative definice a jeho selhání, který uchovává „teorém, že libovolná neprázdná množina M z reálných čísel , která má horní mez má alespoň horní hranice ( viz také Weyl 1919) ".

Ramsey tvrdil, že „impredikativní“ definice mohou být neškodné: například definice „nejvyšší osoby v místnosti“ je improvizovaná, protože závisí na souboru věcí, jejichž je prvkem, konkrétně na souboru všech osob v pokoj, místnost. Pokud jde o matematiku, příkladem nedefinovatelné definice je nejmenší číslo v množině, které je formálně definováno jako: y = min ( X ) právě tehdy, když pro všechny prvky x z X je y menší nebo rovno x a y je v X .

Burgess (2005) pojednává o vypovídací a impredicative teorie obšírně, v souvislosti s Frege ‚s logikou, Peano aritmetiku , druhého řádu aritmetiky a axiomatické teorie množin .

Viz také

• Gödel, Escher, Bach
• Impredikativní polymorfismus
• Logika
• Richardův paradox

Poznámky

Reference

• Msgstr "Predikativní a nepředvídatelné definice" . Internetová encyklopedie filozofie .
• Článek PlanetMath o predikativismu
• John Burgess , 2005. Fixing Frege . Princeton Univ. Lis.
• Solomon Feferman , 2005, „ Predicativity “ v Oxfordské příručce filozofie matematiky a logiky . Oxford University Press: 590–624.
• Russell, B. (1907), „K některým obtížím v teorii transfinitních čísel a typů řádů“ , Proc. London Math. Soc. , s2–4 (1): 29–53, doi : 10,1112 / plms / s2-4.1.29
• Stephen C. Kleene 1952 (vydání z roku 1971), Introduction to Metamathematics , North-Holland Publishing Company, Amsterdam NY, ISBN   0-7204-2103-9 . Zejména srov. jeho §11 The Paradoxes (str. 36–40) a §12 První závěry z paradoxů IMPREDICATIVE DEFINITION (str. 42). Tvrdí, že jeho šest nebo tak (slavných) příkladů paradoxů (antinomií) je všech příkladů nedefinovatelné definice, a říká, že Poincaré (1905–6, 1908) a Russell (1906, 1910) „vysvětlili příčinu paradoxů lhát v těchto nedefinovatelných definicích “(str. 42) však„ části matematiky, které si chceme ponechat, zejména analýza, obsahují také nedefinativní definice “. (tamtéž). Weyl se ve své knize 1918 („Das Kontinuum“) pokusil odvodit co nejvíce analýzy, jak je to možné, bez použití neprůstřelných definic, „ale ne teorém, že libovolná neprázdná množina M reálných čísel s horní mezí má nejméně horní mez (CF. také Weyl 1919) “(str. 43).
• Hans Reichenbach 1947, Elements of Symbolic Logic , Dover Publications, Inc., NY, ISBN   0-486-24004-5 . Srov. jeho §40. Antinomie a teorie typů (str. 218 - kde předvádí, jak vytvořit antinomie, včetně samotné definice impedicable („Je definice„ impedicable “impedicable?)). Tvrdí, že ukazuje metody eliminace„ paradoxů “ syntaxe „(„ logické paradoxy “) - s využitím teorie typů - a„ paradoxy sémantiky “- s využitím metajazyku (jeho„ teorie jazykových úrovní “). Návrh tohoto pojmu připisuje Russell a konkrétněji Ramsey.
• Jean van Heijenoort 1967, třetí tisk 1976, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 , Harvard University Press, Cambridge MA, ISBN   0-674-32449-8 (pbk.)