Q0 (matematická logika) - Q0 (mathematical logic)

Q₀ je Peter Andrews "formulace jednoduše zadaný lambda kalkul, a poskytuje základ pro matematiku srovnatelnou s logikou prvního řádu plus teorií množin. Je to forma logika vyššího řádu a úzce souvisí s logikou HOL teorém prover rodina.

Věta prokazující systémy TPS a ETPS jsou založeny na Q₀. V srpnu 2009 vyhrála TPS vůbec první soutěž mezi systémy pro dokazování teorémů vyššího řádu.^[1]

Axiomy Q₀

Systém má pouze pět axiomů, které lze označit jako:

${ displaystyle (1)}$ ${ displaystyle g_ {oo} T land g_ {oo} F = forall x_ {o} centerdot g_ {oo} x_ {o}}$

${ displaystyle (2 ^ { alpha})}$ ${ displaystyle [x _ { alpha} = y _ { alpha}] supset centerdot , h_ {o alpha} x _ { alpha} = h_ {o alpha} y _ { alpha}}$

${ displaystyle (3 ^ { alpha beta})}$ ${ displaystyle f _ { alpha beta} = g _ { alpha beta} = forall x _ { beta} centerdot f _ { alpha beta} x _ { beta} = g _ { alpha beta} x_ { beta}}$

${ displaystyle (4)}$ ${ displaystyle [ lambda mathbf {x _ { alpha}} mathbf {B} _ { beta}] mathbf {A} _ { alpha} = mathbf {S} _ {A _ { alpha}} ^ { mathbf {x} _ { alpha}} mathbf {B} _ { beta}}$

${ displaystyle (5)}$ ℩ ${ displaystyle _ {i (oi)} [{ text {Q}} _ {oii} y_ {i}] = y_ {i} ,}$

(Axiomy 2, 3 a 4 jsou schémata axiomu - rodiny podobných axiomů. Instance Axiom 2 a Axiom 3 se liší pouze podle typů proměnných a konstant, ale instance Axiomu 4 mohou mít jakýkoli výraz nahrazující A a B.)

PřihlášenýÓ„je typový symbol pro booleovské hodnoty a indexováno“i"je typový symbol pro jednotlivé (nikoli booleovské) hodnoty. Jejich sekvence představují typy funkcí a pro rozlišení různých typů funkcí mohou obsahovat závorky. Dolní písmena v řečtině, jako jsou α a β, jsou syntaktické proměnné pro typy symbolů. Tučné velké písmeno, například $A$ , $B$ , a $C$ jsou syntaktické proměnné pro WFF a tučná malá písmena, jako např $X$ , $y$ jsou syntaktické proměnné pro proměnné. $S$ označuje syntaktickou substituci u všech volných výskytů.

Jediné primitivní konstanty jsou $Q ((oα) α)$ , označující rovnost členů každého typu α, a $℩ (i (oi))$ , označující operátor popisu pro jednotlivce, jedinečný prvek sady obsahující přesně jednoho jednotlivce. Symboly λ a závorky ("[" a "]") jsou syntaxí jazyka. Všechny ostatní symboly jsou zkratky výrazů, které je obsahují, včetně kvantifikátorů ∀ a ∃.

V Axiomu 4 $X$ musí být zdarma pro $A$ v $B$ , což znamená, že substituce nezpůsobí žádné výskyty volných proměnných $A$ stát se vázán v důsledku nahrazení.

O axiomech

Axiom 1 vyjadřuje myšlenku, že $T$ a $F$ jsou jediné booleovské hodnoty.
Axiomová schémata 2^α a 3^αβ vyjádřit základní vlastnosti funkcí.
Axiomové schéma 4 definuje povahu notace λ.
Axiom 5 říká, že operátor výběru je inverzní funkcí rovnosti u jednotlivců. (Vzhledem k jednomu argumentu, $Q$ mapuje tohoto jednotlivce na množinu / predikát obsahující jednotlivce. v Q₀, $x = y$ je zkratka pro $Qxy$ , což je zkratka pro $(Qx) r$ .)

v Andrews 2002, Axiom 4 je vyvinut v pěti částech, které rozkládají proces substituce. Axiom, jak je zde uveden, je diskutován jako alternativa a je prokázán z podkapitol.

Odvození v Q₀

Q₀ má jediné pravidlo odvození.

Pravítko. Z $C$ a $A α = B α$ odvodit výsledek nahrazení jednoho výskytu $A α$ v $C$ výskytem $B α$ , za předpokladu, že výskyt $A α$ v $C$ není (výskyt proměnné) bezprostředně předchází $λ$ .

Odvozené pravidlo závěru R ' umožňuje uvažování ze souboru hypotéz H.

Pravítko'. Li $H ⊦ A α = B α$ ,a $H ⊦ C$ , a $D$ se získává z $C$ nahrazením jednoho výskytu $A α$ výskytem $B α$ , pak $H ⊦ D$ , za předpokladu, že:

Výskyt $A α$ v $C$ není výskyt proměnné bezprostředně předcházející $λ$ , a
žádná proměnná zdarma v $A α = B α$ a člen $H$ je vázán dovnitř $C$ při nahrazeném výskytu $A α$ .

Poznámka: Omezení výměny $A α$ podle $B α$ v $C$ zajišťuje, že jakákoli proměnná bez jak hypotézy, tak i $A α = B α$ je i po nahrazení omezeno na stejnou hodnotu v obou.

Věta o dedukci pro Q₀ ukazuje, že důkazy z hypotéz pomocí pravidla R'n lze převést na důkazy bez hypotéz a použití pravidla R.

Na rozdíl od některých podobných systémů, odvození v Q₀ nahradí subexpresi v jakékoli hloubce uvnitř WFF stejným výrazem. Například zadané axiomy:

1. $Pxx Px$
2. $Px \supset Qx$

a skutečnost, že $A \supset B \equiv (A \equiv A \land B)$ , můžeme pokračovat bez odebrání kvantifikátoru:

3. $Px \equiv (Px \land Qx)$ vytváření instancí pro A a B.
4. $\existsx (Px \land Qx)$ pravidlo R dosazením do řádku 1 pomocí řádku 3.

Poznámky

^ Soutěž systému CADP-22 ATP (CASC-22)

Reference

Andrews, Peter B. (2002). Úvod do matematické logiky a teorie typů: K pravdě skrz důkaz (2. vyd.). Dordrecht, Nizozemsko: Kluwer Academic Publishers. ISBN 1-4020-0763-9. Viz také [1]
Kostel, Alonzo (1940). „Formulace jednoduché teorie typů“ (PDF). Journal of Symbolic Logic. 5: 56–58. doi:10.2307/2266170.

Další čtení

A popis Q₀ do větší hloubky; část článku o Teorie církevního typu v Stanfordská encyklopedie filozofie.
Přehled matematické logiky (včetně různých nástupců Q₀): Základy matematiky. Genealogie a přehled doi: 10,4444 / 100,111.

[1] Soutěž systému CADP-22 ATP (CASC-22)

[1]