Indukce tyče - Bar induction

Indukce tyče je princip uvažování používaný v intuicionistická matematika, představil L. E. J. Brouwer. Hlavní použití indukce tyčí je intuitivní odvození věta o fanoušcích, klíčový výsledek použitý při odvození věta o jednotné spojitosti.

Je také užitečné poskytnout konstruktivní alternativy k jiným klasický Výsledek.

Cílem principu je prokázat vlastnosti pro všechny nekonečné posloupnosti přirozených čísel (tzv výběrové sekvence v intuicionistické terminologii), jejich indukčním snížením na vlastnosti konečných seznamů. Tyčovou indukci lze také použít k prokázání vlastností všech výběrové sekvence v šíření (zvláštní druh soubor ).

Definice

Vzhledem k pořadí výběru ${displaystyle x_ {0}, x_ {1}, x_ {2}, x_ {3}, ldots}$, jakákoli konečná posloupnost prvků ${displaystyle x_ {0}, x_ {1}, x_ {2}, x_ {3}, ldots, x_ {i}}$ této sekvence se nazývá počáteční segment této volby sekvence.

V současné době existují v literatuře tři formy indukce sloupců, každá z nich stanoví určitá omezení na dvojici predikátů a klíčové rozdíly jsou zvýrazněny tučným písmem.

Rozhodující indukce tyčí (BI_D)

Vzhledem k tomu, dva predikáty ${displaystyle R}$ a ${displaystyle A}$ na konečné posloupnosti přirozených čísel tak, že platí všechny následující podmínky:

• každá výběrová sekvence obsahuje alespoň jeden vyhovující počáteční segment ${displaystyle R}$ v určitém okamžiku (to je vyjádřeno tím, že ${displaystyle R}$ je bar);
• ${displaystyle R}$ je rozhodnutelné (tj. náš bar je rozhodnutelné);
• každá konečná sekvence uspokojivá ${displaystyle R}$ také uspokojuje ${displaystyle A}$ (tak ${displaystyle A}$ platí pro každou vybranou sekvenci počínaje výše uvedenou konečnou sekvencí);
• pokud splňují všechna rozšíření konečné posloupnosti o jeden prvek ${displaystyle A}$, pak konečná posloupnost také vyhovuje ${displaystyle A}$ (toto se někdy označuje jako ${displaystyle A}$ bytost vzhůru dědičná);

pak můžeme dojít k závěru, že ${displaystyle A}$ platí pro prázdnou sekvenci (tj. A platí pro všechny vybrané sekvence začínající prázdnou sekvencí).

Tento princip indukce tyčí je upřednostňován v pracích, A. S. Troelstra, S. C. Kleene a Dragalin.

Indukce tenkých tyčí (BI_T)

Vzhledem k tomu, dva predikáty ${displaystyle R}$ a ${displaystyle A}$ na konečné posloupnosti přirozených čísel tak, že platí všechny následující podmínky:

• každá výběrová sekvence obsahuje alespoň unikátní počáteční segment uspokojivý ${displaystyle R}$ v určitém okamžiku (tj. náš bar je tenký);
• každá konečná sekvence uspokojivá ${displaystyle R}$ také uspokojuje ${displaystyle A}$;
• pokud splňují všechna rozšíření konečné posloupnosti o jeden prvek ${displaystyle A}$, pak konečná posloupnost také vyhovuje ${displaystyle A}$;

pak můžeme dojít k závěru, že ${displaystyle A}$ platí pro prázdnou sekvenci.

Tento princip indukce tyčí je v pracích upřednostňován Joan Moschovakis a je (intuitivně) prokazatelně ekvivalentní rozhodující indukci baru.

Monotónní indukce pruhů (BI_M)

Vzhledem k tomu, dva predikáty ${displaystyle R}$ a ${displaystyle A}$ na konečné posloupnosti přirozených čísel tak, že platí všechny následující podmínky:

• každá výběrová sekvence obsahuje alespoň jeden vyhovující počáteční segment ${displaystyle R}$ v určitém okamžiku;
• jakmile konečná posloupnost vyhovuje ${displaystyle R}$, pak uspokojí také každé možné prodloužení této konečné posloupnosti ${displaystyle R}$ (tj. náš bar je monotóní);
• každá konečná sekvence uspokojivá ${displaystyle R}$ také uspokojuje ${displaystyle A}$;
• pokud splňují všechna rozšíření konečné posloupnosti o jeden prvek ${displaystyle A}$, pak konečná posloupnost také vyhovuje ${displaystyle A}$;

pak můžeme dojít k závěru, že ${displaystyle A}$ platí pro prázdnou sekvenci.

Tento princip indukce tyčí se používá v pracích A. S. Troelstra, S. C. Kleene, Dragalin a Joan Moschovakis. Obvykle se odvozuje buď od indukce tenkých tyčí, nebo od monotónní indukce tyčí. (Dummett 1977)

Vztahy mezi těmito schématy a dalšími informacemi

Následující výsledky o těchto schématech mohou být intuitivně dokázal:

${displaystyle {egin {aligned} B_ {M} & vdash B_ {D} [3pt] B_ {D} & vdash B_ {T} [3pt] B_ {T} & vdash B_ {D} end {aligned}}}$

(Symbol "${displaystyle, vdash,}$" je "turniket ".

Neomezená indukce tyčí

Další schémata indukce tyčí byla původně uvedena jako věta od Brouwer (1975) neobsahující žádné „zvláštní“ omezení R pod jménem The Bar Theorem. Důkaz pro tuto větu byl však chybný a neomezená indukce sloupců se nepovažuje za intuitivně platnou (shrnutí, proč tomu tak je, viz Dummett 1977, str. 94 - 104). Níže je pro úplnost uvedeno schéma neomezené indukce sloupců.

Vzhledem k tomu, dva predikáty ${displaystyle R}$ a ${displaystyle A}$ na konečné posloupnosti přirozených čísel tak, že platí všechny následující podmínky:

• každá výběrová sekvence obsahuje alespoň jeden vyhovující počáteční segment ${displaystyle R}$ v určitém okamžiku;
• každá konečná sekvence uspokojivá ${displaystyle R}$ také uspokojuje ${displaystyle A}$;
• pokud splňují všechna rozšíření konečné posloupnosti o jeden prvek ${displaystyle A}$, pak konečná posloupnost také vyhovuje ${displaystyle A}$;

pak můžeme dojít k závěru, že ${displaystyle A}$ platí pro prázdnou sekvenci.

Vztahy k jiným oborům

V klasickém reverzní matematika, "indukce tyčí" (${displaystyle BI_ {D}}$) označuje související princip, který uvádí, že pokud jde o vztah ${displaystyle R}$ je pořádek, pak máme schéma transfinitní indukce přes ${displaystyle R}$ pro libovolné vzorce.

Reference

• L. E. J. Brouwer Brouwer, L. E. J. Collected Works, Sv. I, Amsterdam: North-Holland (1975).
• Dragalin, A.G. (2001) [1994], "Indukce pruhu", Encyclopedia of Mathematics, Stiskněte EMS
• Michael Dummett, Prvky intuicionismu, Clarendon Press (1977)
• S. C. Kleene, R. E. Vesley, Základy intuicionistické matematiky: zejména ve vztahu k rekurzivním funkcím, Severní Holandsko (1965)
• Michael Rathjen, Role parametrů v pravidle a indukci tyče, Journal of Symbolic Logic 56 (1991), č. 1, str. 2, str. 715 - 730.
• A. S. Troelstra, Výběrové sekvence, Clarendon Press (1977)
• A. S. Troelstra a Dirk Van Dalen, Konstruktivismus v matematice, studium logiky a základy matematiky, Elsevier (1988)

Tento logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.