Logika nekonečna

Nekonečný logika je logika , která umožňuje nekonečně dlouhé vzorce a / nebo nekonečně dlouhý demonstrace . Některé nekonečné logiky mohou mít odlišné vlastnosti od vlastností standardní logiky prvního řádu . Zejména nekonečná logika nemusí být kompaktní nebo úplná . Pojmy kompaktnosti a úplnosti, které jsou ekvivalentní ve finitární logice, nemusí být nutně ekvivalentní v nekonečných logikách. V důsledku toho jsou pro nekonečnou logiku definovány pojmy silné kompaktnosti a úplnosti. Tento článek pojednává o nekonečných logikách prezentovaných v systémech à la Hilbert , protože byly široce studovány a představují nejjednodušší rozšíření finitární logiky. Nejsou to však jediné nekonečné logiky, které byly formulovány nebo studovány.

Zápis a axiom výběru

Protože představujeme jazyk s nekonečně dlouhými vzorci, není možné tyto vzorce výslovně psát. K řešení tohoto problému se používá řada notačních zařízení, která, přísně vzato, nejsou součástí formálního jazyka. " " Používá se k podtržení nekonečně dlouhého výrazu. V případě, že tento zápis není jasný, délka sekvence se zaznamená později. Když se tento zápis stane nejednoznačným nebo matoucím, použijí se přípony, které se používají k označení nekonečné disjunkce nad množinou vzorců mohutnosti . Stejný zápis může být aplikován na quantifiers , například . To má představovat nekonečnou řadu kvantifikátorů pro každý, kde . $\ cdots$ ${\ displaystyle \ lor _ {\ gamma <\ delta} {A _ {\ gamma}}}$ $\delta$ ${\ displaystyle \ forall _ {\ gamma <\ delta} {V _ {\ gamma}:}}$ ${\ displaystyle V _ {\ gamma}}$ ${\ displaystyle \ gamma <\ delta}$

Přípony a znak „ “ nejsou součástí formální abecedy nekonečných jazyků. $\ cdots$

Axiom výběru se předpokládá, že je to pravda, tak, aby měly odpovídající distributivní zákony.

Definice nekonečných logik typu Hilberta

Logika nekonečna prvního řádu L α, β , α regulérní , β = 0 nebo ω ≤ β ≤ α, má stejnou sadu symbolů jako konečná logika a může použít všechna pravidla pro tvorbu vzorců konečné logiky jako a také následující:

Vzhledem k tomu, sada vzorců pak a jsou vzorce. (v každém případě je vzorec délka .) ${\ displaystyle A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alpha \}}$ ${\ displaystyle (A_ {0} \ lor A_ {1} \ lor \ cdots)}$ ${\ displaystyle (A_ {0} \ land A_ {1} \ land \ cdots)}$ $\delta$
Vzhledem k tomu, sada proměnných a vzorec pak a jsou vzorce. (v každém případě má posloupnost kvantifikátorů délku .) ${\ displaystyle V = \ {V _ {\ gamma} | \ gamma <\ delta <\ beta \}}$ $A_0$ ${\ displaystyle \ forall V_ {0}: \ forall V_ {1} \ cdots (A_ {0})}$ ${\ displaystyle \ existuje V_ {0}: \ existuje V_ {1} \ cdots (A_ {0})}$ $\delta$

Pojmy volné a vázané proměnné platí stejným způsobem i pro nekonečné vzorce. Stejně jako v konečné logice se vzorec, ve kterém jsou všechny proměnné příbuzné, nazývá příkaz.

Teorie T v nekonečné logiky je množina formulí. Důkazem v nekonečné logice teorie T je řada výroků o délce, která se řídí následujícími podmínkami: každý výrok je buď logickým axiomem , prvkem T , nebo odvozen z předchozích výroků pomocí odvozovacího pravidla . Stejně jako dříve lze použít všechna pravidla odvození v konečné logice s: ${\ displaystyle L _ {\ alpha, \ beta}}$ $\ gama$

Vzhledem k souboru vzorců, které již v důkazu dříve existovaly, lze z něj odvodit tvrzení . ${\ displaystyle A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alpha \}}$ ${\ displaystyle \ land _ {\ gamma <\ delta} {A _ {\ gamma}}}$

Níže jsou uvedena schémata logických axiomů specifických pro logiku nekonečna. Proměnné globálního schématu: a jako např . $\delta$ $\ gama$ ${\ displaystyle 0 <\ delta <\ alpha}$

${\ displaystyle ((\ land _ {\ epsilon <\ delta} {(A _ {\ delta} \ implikuje A _ {\ epsilon})}) \ implikuje (A _ {\ delta} \ implikuje \ land _ {\ epsilon <\ delta} {A _ {\ epsilon}})}}$
U každého , ${\ displaystyle \ gamma <\ delta}$ ${\ displaystyle ((\ land _ {\ epsilon <\ delta} {A _ {\ epsilon}}) \ znamená A _ {\ gamma})}$
Changův distribuční zákon (pro každého ) :, kde nebo , a $\ gama$ ${\ displaystyle (\ lor _ {\ mu <\ gamma} {(\ land _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})}}}$ ${\ displaystyle \ forall \ mu \ forall \ delta \ existuje \ epsilon <\ gamma: A _ {\ mu, \ delta} = A _ {\ epsilon}}$ ${\ displaystyle A _ {\ mu, \ delta} = \ neg A _ {\ epsilon}}$ ${\ displaystyle \ forall g \ in \ gamma ^ {\ gamma} \ existuje \ epsilon <\ gamma: \ {A _ {\ epsilon}, \ neg A _ {\ epsilon} \} \ subseteq \ {A _ {\ mu, g (\ mu)}: \ mu <\ gamma \}}$
Pro ,, kde je dobře uspořádaná sada ${\ displaystyle \ gamma <\ alpha}$ ${\ displaystyle ((\ land _ {\ mu <\ gamma} {(\ lor _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})}) \ implikuje (\ lor _ {\ epsilon <\ gamma ^ {\ gamma}} {(\ land _ {\ mu <\ gamma} {A _ {\ mu, \ gamma _ {\ epsilon} (\ mu)})}))}}$ ${\ displaystyle \ {\ gamma _ {\ epsilon}: \ epsilon <\ gamma ^ {\ gamma} \}}$ ${\ displaystyle \ gamma ^ {\ gamma}}$

Poslední dvě schémata axiomu vyžadují axiom výběru, protože některé množiny musí být dobře uspořádány. Poslední schéma axiomu je přísně řečeno zbytečné, protože to naznačují Changovy distribuční zákony.

Úplnost, kompaktnost a vysoká kompaktnost

Teorie je soubor vzorců. Podle teorie modelů je platnost vzorců v modelech definována indukcí a odpovídá definici platnosti v konečné logice. My říkáme, že formule je platná v teorii T , pokud je platný ve všech modelech T .

Logika je kompletní, pokud pro každý vzorec S platný v každém modelu, existují důkazy o S . Je silně úplné, pokud pro každou teorie T pro každý vzorec S platný T , existují důkazy o S z T . Nekonečná logika může být úplná, aniž by byla silně úplná. ${\ displaystyle L _ {\ alpha, \ beta}}$

Hlavní je slabě kompaktní, když pro každou teorii T ve obsahující většině vzorců, pokud každý S T nižší mohutnost má model, pak T má model. Kardinál je silně kompaktní, když pro každou teorii T in , bez omezení velikosti, je-li každá S T mohutnosti menší než model, má T model. ${\ displaystyle \ kappa \ neq \ omega}$ ${\ displaystyle L _ {\ kappa, \ kappa}}$ $\ kappa$ $\ subseteq$ $\ kappa$ ${\ displaystyle \ kappa \ neq \ omega}$ ${\ displaystyle L _ {\ kappa, \ kappa}}$ $\ subseteq$ $\ kappa$

Expresivní koncepty v nekonečné logice

V jazyce teorie množin odpovídá základní výraz axiomu následující výraz :

{\ displaystyle \ forall _ {\ gamma <\ omega} {V _ {\ gamma}:} \ neg \ land _ {\ gamma <\ omega} {V _ {\ gamma +} \ ve V _ {\ gamma} }. \,}

Na rozdíl od základní axiomy tento výraz nepřipouští žádný nestandardní model . Koncept dobrého základu lze vyjádřit pouze logikou, která umožňuje nekonečné množství kvantifikátorů v jednom vzorci. V důsledku toho lze mnoho teorií, včetně Peanoovy aritmetiky , kterou nelze definitivně axiomatizovat, protože lze axiomatizovat pouze nekonečným schématem vzorců v konečné logice, lze axiomatizovat v nekonečné logice.

Kompletní nekonečná logika

Ve své úplnosti vynikají dvě nekonečné logiky. To jsou a . První je standardní finitární logika prvního řádu a druhá je nekonečná logika, která umožňuje pouze deklarace spočítatelné velikosti. ${\ displaystyle L _ {\ omega, \ omega}}$ ${\ displaystyle L _ {\ omega _ {1}, \ omega}}$

${\ displaystyle L _ {\ omega, \ omega}}$ je také vysoce kompletní, kompaktní a vysoce kompaktní.

${\ displaystyle L _ {\ omega _ {1}, \ omega}}$ není kompaktní, ale je kompletní. Kromě toho splňuje variantu Craigovy interpolační vlastnosti .

Pokud je silně kompletní, je silně kompaktní. ${\ displaystyle L _ {\ alpha, \ alpha}}$ $\ alfa$

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Infinitary logic “ ( viz seznam autorů ) .

Formální představa odpovídající neformální představě o „pravdě“

Bibliografie

Carol R. Karp , Jazyky s výrazy nekonečné délky , Amsterdam, North-Holland Publishing Co.,1964( Matematické recenze 0176910 )
Kenneth Jon Barwise , Infinitary logic and allowible sets , sv. 34,1969, 226–252 s. ( DOI 10.2307 / 2271099 , JSTOR 2271099 , Math Reviews 0406760 ) , kap. 2