Církevní práce (konstruktivní matematika) - Churchs thesis (constructive mathematics) - Wikipedia

v konstruktivní matematika, Církevní teze (CT) je axiom o tom, že jsou všechny funkce celkem vypočitatelný. Axiom odvozuje svůj název od Církev – Turingova teze,^{[Citace je zapotřebí ]} který uvádí, že každý efektivně vypočítatelná funkce je vypočítatelná funkce, ale konstruktivistická verze je mnohem silnější a tvrdí, že každá funkce je vypočítatelná.

Axiom CT je nekompatibilní s klasická logika v dostatečně silných systémech. Například, Heyting aritmetic (HA) s CT jako přídavný axiom je schopen vyvrátit některé případy zákon vyloučeného středu. Heyting aritmetika však je ekvikonzistentní s Peano aritmetika (PA) a také s Heyting arithmetic plus Church's thesis. To znamená, že přidání buď zákona vyloučeného středu, nebo církevní teze nezpůsobí Heytingovu aritmetiku nekonzistentní, ale přidání obou ano.

Formální prohlášení

V teoriích prvního řádu, jako je HA, které nemohou přímo kvantifikovat nad funkcemi, je CT uvedeno jako schéma axiomu, které říká, že jakoukoli definovatelnou funkci lze vypočítat pomocí Kleeneův T predikát definovat vypočítatelnost. Pro každý vzorec φ (X,y) dvou proměnných obsahuje schéma axiom

${ displaystyle ( forall x ; existuje y ; varphi (x, y)) to ( existuje e ; forall x ; existuje y, u ; mathbf {T} (e, x, y, u) klín varphi (x, y))}$

Tento axiom tvrdí, že pokud pro každého X tady je y splňující φ, pak ve skutečnosti existuje E toto je Gödelovo číslo obecné rekurzivní funkce, která bude pro každého X, vyrábět takové a y uspokojující vzorec, s některými u je Gödelovo číslo kódující ověřitelný výpočet vydávat svědectví k tomu, že y je ve skutečnosti hodnota této funkce na X.

V systémech vyššího řádu, které mohou přímo kvantifikovat funkce, lze CT označit jako jeden axiom, který říká, že každá funkce od přirozených čísel k přirozeným číslům je vypočítatelná.

Vztah ke klasické logice

Schéma formy CT zobrazené výše, když je přidáno do konstruktivních systémů, jako je HA, implikuje negaci zákona vyloučeného středu. Jako příklad je to klasický tautologie že každý Turingův stroj na daném vstupu buď zastaví, nebo se nezastaví. Za předpokladu této tautologie je možné v dostatečně silných systémech, jako je HA, vytvořit funkci h který vezme kód pro Turingův stroj a vrátí 1, pokud se stroj zastaví, a 0, pokud se nezastaví. Z Církve práce by se tedy dalo usoudit, že tato funkce je sama o sobě vypočítatelná, ale je známo, že je nepravdivá, protože problém zastavení není vypočítatelně řešitelný. HA a CT tak vyvrací určitý důsledek zákona vyloučeného středu.

Výše zmíněná forma „jednoho axiomu“ CT,

${ displaystyle ( forall f) ( existuje e) ( forall n) ( existuje u) [ mathbf {T} (e, n, f (n), u)],}$

kvantifikuje přes funkce a říká, že každá funkce F je vypočítatelný (s indexem E). Tento axiom je v souladu s některými slabými klasickými systémy, které nemají sílu vytvářet funkce, jako je funkce F předchozího odstavce. Například slabý klasický systém ${ displaystyle { mathsf {RCA}} _ {0}}$ je v souladu s tímto jediným axiomem, protože ${ displaystyle { mathsf {RCA}} _ {0}}$ má model, ve kterém je každá funkce vypočítatelná. Forma jedné axiomy se však stává nekonzistentní se zákonem vyloučeného středu v každém systému, který má dostatečné axiomy pro konstrukci funkcí, jako je funkce h v předchozím odstavci.

Rozšířená církevní teze

Rozšířená církevní práce (ECT) rozšiřuje nárok na funkce, které jsou zcela definovány přes určitý typ domény. Používá ji škola konstruktivní matematiky založená Andrey Markov ml. Schéma může být formálně uvedeno:

${ displaystyle ( forall x ; psi (x) to existuje y ; varphi (x, y)) to existuje f ( forall x ; psi (x) to existuje y , u ; mathbf {T} (f, x, y, u) klín varphi (x, y))}$

Ve výše uvedeném ${ displaystyle psi}$ je omezeno na téměř negativní. Pro aritmetiku prvního řádu (kde je uvedeno schéma ${ displaystyle ECT_ {0}}$), to znamená ${ displaystyle psi}$ nemůže obsahovat žádné disjunkce a existenciální kvantifikátory se může zobrazit pouze před ${ displaystyle Delta _ {0} ^ {0}}$ (rozhodnutelné) vzorce.

Tuto práci lze charakterizovat jako tvrzení, že věta je pravdivá právě tehdy, je-li vypočítatelná realizovatelné. Ve skutečnosti to zachycují následující meta-teoretické ekvivalence:^[1]

${ displaystyle HA + ECT_ {0} vdash ( varphi leftrightarrow ( existuje n ; n Vdash varphi))}$

${ displaystyle (HA + ECT_ {0} vdash varphi) leftrightarrow (HA vdash existuje n ; (n Vdash varphi))}$

Tady, ${ displaystyle n Vdash varphi}$ znamená „${ displaystyle n { text {realizuje}} varphi}$". Takže je to prokazatelné v ${ displaystyle HA}$ s ${ displaystyle ECT_ {0}}$ že věta je pravdivá, pokud je realizovatelná. Ale také, ${ displaystyle varphi}$ je prokazatelně pravda v ${ displaystyle HA}$ s ${ displaystyle ECT_ {0}}$ iff ${ displaystyle varphi}$ je prokazatelně realizovatelný v ${ displaystyle HA}$ bez ${ displaystyle ECT_ {0}}$.

Druhou rovnocennost lze rozšířit pomocí Markovův princip (M) takto:

${ displaystyle (HA + ECT_ {0} + M vdash varphi) leftrightarrow ( existuje n ; PA vdash ({ bar {n}} Vdash varphi))}$

Tak, ${ displaystyle varphi}$ je prokazatelně pravda v ${ displaystyle HA}$ s ${ displaystyle ECT_ {0}}$ a ${ displaystyle M}$ pokud existuje číslo n který prokazatelně realizuje ${ displaystyle varphi}$ v ${ displaystyle PA}$. Existenční kvantifikátor musí být venku ${ displaystyle PA}$ v tomto případě, protože PA je nekonstruktivní a postrádá existence majetku.

Reference

• Elliott Mendelson (1990) „Druhé myšlenky na církevní teze a matematické důkazy“, Journal of Philosophy 87(5): 225–233.