Sekvenční - Sequent

V matematické logice je posloupnost velmi obecným druhem podmíněného tvrzení.

${\ displaystyle A_ {1}, \, \ tečky, A_ {m} \, \ vdash \, B_ {1}, \, \ tečky, B_ {n}.}$

Posloupnost může mít libovolný počet m podmíněných vzorců A _i (nazývaných „ předchůdci ") a libovolný počet n prosazovaných vzorců B _j (nazývaných „nástupci" nebo „ důsledky "). Sekvencí se rozumí, že pokud jsou splněny všechny předcházející podmínky, pak platí alespoň jeden z následujících vzorců. Tento styl podmíněného tvrzení je téměř vždy spojen s koncepčním rámcem sekvenčního počtu .

Úvod

Forma a sémantika sekvencí

Sekvencím lze nejlépe porozumět v kontextu následujících tří druhů logických úsudků :

1. Bezpodmínečné tvrzení . Žádné předchozí vzorce.
   • Příklad: ⊢ B
   • Význam: B je pravda.
2. Podmíněné tvrzení . Libovolný počet předcházejících vzorců.
   1. Jednoduché podmíněné tvrzení . Jediný následný vzorec.
      • Příklad: A ₁ , A ₂ , A ₃ ⊢ B
      • Význam: POKUD A ₁ A A ₂ A A ₃ jsou pravdivé, POTOM B je pravdivé.
   2. Sekvenční . Libovolný počet následných vzorců.
      • Příklad: A ₁ , A ₂ , A ₃ ⊢ B ₁ , B ₂ , B ₃ , B ₄
      • Význam: POKUD A ₁ A A ₂ A A ₃ jsou pravdivé, POTOM B ₁ NEBO B ₂ NEBO B ₃ NEBO B ₄ je pravda.

Sekvence jsou tedy zobecněním jednoduchých podmíněných tvrzení, která jsou zobecněním bezpodmínečných tvrzení.

Slovo „OR“ je zde včetně OR . Motivace disjunktivní sémantiky na pravé straně sekvence pochází ze tří hlavních výhod.

1. Symetrie pravidel klasického odvození pro sekvence s takovou sémantikou.
2. Snadnost a jednoduchost převodu těchto klasických pravidel na intuitivní pravidla.
3. Schopnost prokázat úplnost predikátového počtu, je-li vyjádřena tímto způsobem.

Všechny tři z těchto výhod identifikoval Gentzen (1934 , s. 194) v zakladatelské práci .

Ne všichni autoři dodržovali původní Gentzenův význam slova „následník“. Například Lemmon (1965) používal slovo „sequent“ přísně pro jednoduchá podmíněná tvrzení s jedním a pouze jedním následným vzorcem. Stejnou jednosekvenční definici sekvence uvádí Huth & Ryan 2004 , s. 5.

Podrobnosti syntaxe

V obecném pořadí formuláře

${\ displaystyle \ Gamma \ vdash \ Sigma}$

obě Γ a Σ jsou posloupnosti logických vzorců, nikoli množiny . Počet i pořadí výskytů vzorců jsou proto významné. Zejména se stejný vzorec může objevit dvakrát ve stejné sekvenci. Úplná sada pravidel odvození postupného počtu obsahuje pravidla pro výměnu sousedních vzorců vlevo a vpravo od symbolu tvrzení (a tím libovolně permutuje levou a pravou sekvenci) a také pro vložení libovolných vzorců a odstranění duplicitních kopií v levé části a správné sekvence. ( Smullyan (1995 , s. 107–108) však používá sady vzorců v sekvencích místo sekvencí vzorců. V důsledku toho nejsou vyžadovány tři páry strukturálních pravidel nazývaných „řídnutí“, „kontrakce“ a „výměna“.)

Symbol „ se často označuje jako„ turniket “,„ pravý směr “,„ tričko “,„ značka tvrzení “nebo„ symbol tvrzení “. Často se čte sugestivně jako „výnosy“, „dokazuje“ nebo „s sebou nese“. ${\ displaystyle \ vdash}$

Vlastnosti

Účinky vkládání a odebírání návrhů

Vzhledem k tomu, že každý vzorec v předchůdci (levá strana) musí být pravdivý, aby se dospělo k závěru o pravdivosti alespoň jednoho vzorce v následném (pravá strana), přidání vzorců na obě strany má za následek slabší posloupnost, zatímco jejich odstranění z obou stran dává silnější. Toto je jedna z výhod symetrie, která vyplývá z použití disjunktivní sémantiky na pravé straně symbolu tvrzení, zatímco spojovací sémantika je dodržována na levé straně.

Důsledky prázdných seznamů vzorců

V krajním případě, kdy je seznam předcházejících vzorců posloupnosti prázdný, je důsledek bezpodmínečný. To se liší od jednoduchého bezpodmínečného tvrzení, protože počet následků je libovolný, nemusí to být nutně jediný důsledek. Například například „⊢ B ₁ , B ₂ “ znamená, že buď B ₁ , nebo B ₂ nebo obojí musí být pravdivé. Prázdný seznam předcházejících vzorců odpovídá ekvivalentu „vždy pravdivého“ návrhu, který se nazývá „ verum “ a označuje se „⊤“. (Viz tričko (symbol) .)

V krajním případě, kdy je seznam následných vzorců posloupnosti prázdný, stále platí pravidlo, že alespoň jeden výraz vpravo je pravdivý, což je zjevně nemožné . To je označeno „ vždy falešnou“ větou , zvanou „ falsum “, označovanou „⊥“. Vzhledem k tomu, že důsledek je nepravdivý, musí být alespoň jeden z předchůdců nepravdivý. Například například „ A ₁ , A ₂ ⊢“ znamená, že alespoň jeden z předchůdců A ₁ a A ₂ musí být nepravdivý.

Jeden zde opět vidí symetrii kvůli disjunktivní sémantice na pravé straně. Pokud je levá strana prázdná, musí platit jedna nebo více propozic na pravé straně. Pokud je pravá strana prázdná, pak musí být jedna nebo více propozic na levé straně nepravdivých.

Dvojnásobně extrémní případ „⊢“, kdy jsou předchozí i následující seznamy vzorců prázdné, „ není uspokojivý “. V tomto případě je význam sekvence skutečně „⊤ ⊢ ⊥“. To odpovídá posloupnosti „⊢ ⊥“, která zjevně nemůže být platná.

Příklady

Posloupnost tvaru „⊢ α, β“ pro logické vzorce α a β znamená, že buď α je pravda, nebo β je pravda (nebo obojí). Ale to neznamená, že buď α je tautologie, nebo β je tautologie. Abychom to objasnili, zvažte příklad „⊢ B ∨ A, C ∨ ¬A“. Toto je platný sled, protože buď B B A je pravda, nebo C ∨ ¬A je pravda. Ani jeden z těchto výrazů však není tautologií v izolaci. Je to disjunkce těchto dvou výrazů, která je tautologií.

Podobně posloupnost tvaru „α, β ⊢“ pro logické vzorce α a β znamená, že buď α je nepravdivé, nebo β je nepravdivé. Ale to neznamená, že buď α je rozpor, nebo β je rozpor. Abychom to objasnili, zvažte příklad 'B ∧ A, C ∧ ¬A ⊢'. Toto je platný sled, protože buď B ∧ A je nepravdivé, nebo C ∧ ¬A je nepravdivé. Ani jeden z těchto výrazů však není rozporem v izolaci. Protikladem je spojení těchto dvou výrazů.

Pravidla

Většina důkazních systémů poskytuje způsoby, jak odvodit jednu sekvenci od druhé. Tato pravidla odvození jsou psána se seznamem sekvencí nad a pod řádkem . Toto pravidlo naznačuje, že pokud je vše nad řádkem pravdivé, platí také vše pod řádkem.

Typické pravidlo je:

${\ displaystyle {\ frac {\ Gamma, \ alpha \ vdash \ Sigma \ qquad \ Gamma \ vdash \ alpha} {\ Gamma \ vdash \ Sigma}}}$

To naznačuje, že pokud můžeme odvodit tyto výnosy a tyto výnosy , můžeme také odvodit tyto výnosy . (Viz také úplnou sadu pravidel odvození počtu .) ${\ displaystyle \ Gamma, \ alfa}$${\ displaystyle \ Sigma}$${\ displaystyle \ Gamma}$${\ displaystyle \ alpha}$${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma}$

Výklad

Historie významu následných tvrzení

Symbol tvrzení v sekvencích původně znamenal přesně to samé jako implikační operátor. Ale v průběhu času se jeho význam změnil, aby znamenal prokazatelnost v rámci teorie spíše než sémantické pravdy ve všech modelech.

V roce 1934 Gentzen nedefinoval symbol tvrzení „⊢“ v pořadí, který by znamenal prokazatelnost. Definoval to tak, že znamená přesně to samé jako implikační operátor „⇒“. Použitím '→' místo '⊢' a '⊃' místo '⇒' napsal: "Sekvence A ₁ , ..., A _μ → B ₁ , ..., B _ν znamená, pokud jde o obsah, přesně stejné jako vzorec (A ₁ & ... & A _μ ) ⊃ (B ₁ ∨ ... ∨ B _ν ) ". (Gentzen použil symbol šipky doprava mezi předchůdci a následníky sekvencí. Pro operátor logické implikace použil symbol „⊃“.)

V roce 1939 Hilbert a Bernays rovněž uvedli, že posloupnost má stejný význam jako odpovídající implikační vzorec.

V roce 1944 Alonzo Church zdůraznil, že Gentzenova následná tvrzení neznamenají prokazatelnost.

„Použití věty o dedukci jako primitivního nebo odvozeného pravidla nesmí být zaměňováno s použitím Sequenzenu Gentzenem . Gentzenův šíp → není srovnatelný s naší syntaktickou notací ⊢, ale patří do jeho objektového jazyka (jako je zřejmé ze skutečnosti, že výrazy, které jej obsahují, se objevují jako premisy a závěry při aplikaci jeho pravidel závěru). “

Mnoho publikací po této době uvádí, že symbol tvrzení v sekvencích znamená prokazatelnost v teorii, kde jsou sekvence formulovány. Curry v roce 1963, Lemmon v roce 1965 a Huth a Ryan v roce 2004 uvádějí, že symbol následného tvrzení znamená prokazatelnost. Nicméně, Ben-Ari (2012 , str. 69) uvádí, že symbol tvrzení v Gentzen-systémových sequents, kterou označuje jako ‚⇒‘ je součástí jazyka objekt není metajazyku.

Podle Prawitze (1965): „Kalkul sekvencí lze chápat jako metakalkul pro vztah dedukovatelnosti v odpovídajících systémech přirozené dedukce.“ A dále: „Na důkaz v počtu sekvencí lze pohlížet jako na návod, jak vytvořit odpovídající přirozený dedukce.“ Jinými slovy, symbol tvrzení je součástí jazykového objektu pro sekvenční kalkul, což je druh meta-kalkulu, ale současně znamená odvoditelnost v základním přirozeném dedukčním systému.

Intuitivní význam

Sekvence je formalizované prohlášení o prokazatelnosti, které se často používá při určování počtu pro odpočet . V následujícím počtu název sequent se používá pro konstrukce, které lze považovat za jakési specifické části rozsudku , charakteristické pro tuto odpočtů.

Intuitivní význam sekvence je ten, že za předpokladu Γ je závěr of prokazatelný. Klasicky lze vzorce vlevo od turniketu interpretovat konjunktivně, zatímco vzorce vpravo lze považovat za disjunkci . To znamená, že když všechny vzorce v Γ platí, pak alespoň jeden vzorec v Σ také musí být pravdivý. Pokud je následník prázdný, interpretuje se to jako faleš, tj. Znamená to, že Γ prokazuje faleš a je tedy nekonzistentní. Na druhou stranu se prázdný předchůdce považuje za pravdivý, tj. Znamená, že Σ následuje bez jakýchkoli předpokladů, tj. Vždy platí (jako disjunkce). Sekvence tohoto formuláře s prázdným Γ je známá jako logické tvrzení . ${\ displaystyle \ Gamma \ vdash \ Sigma}$${\ displaystyle \ Gamma \ vdash}$${\ displaystyle \ vdash \ Sigma}$

Samozřejmě jsou možná i další intuitivní vysvětlení, která jsou klasicky ekvivalentní. Lze jej například číst jako tvrzení, že nemůže být případ, že každý vzorec v Γ je pravdivý a každý vzorec v Σ je nepravdivý (to souvisí s interpretacemi dvojité negace klasické intuitivní logiky , jako je Glivenkova věta ). ${\ displaystyle \ Gamma \ vdash \ Sigma}$

V každém případě jsou tato intuitivní čtení pouze pedagogická. Protože formální důkazy v teorii důkazů jsou čistě syntaktické , význam (odvození) posloupnosti je dán pouze vlastnostmi kalkulu, který poskytuje skutečná pravidla závěru .

S vyloučením jakýchkoli rozporů v technicky přesné definici výše můžeme popsat sekvence v jejich úvodní logické formě. představuje soubor předpokladů, kterými začínáme náš logický proces, například „Sokrates je muž“ a „Všichni muži jsou smrtelní“. Představuje logický závěr, který následuje v těchto prostorách. Například „Sokrates je smrtelný“ vyplývá z rozumné formalizace výše uvedených bodů a mohli bychom očekávat, že to uvidíme na straně turniketu . V tomto smyslu znamená proces uvažování neboli „proto“ v angličtině. ${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ vdash}$

Variace

Obecný pojem zde představeného posloupnosti lze specializovat různými způsoby. O sekvenci se říká, že je intuicionistickou sekvencí, pokud je v následníkovi nanejvýš jeden vzorec (ačkoli jsou možné i vícenásledné výpočty pro intuitivní logiku). Přesněji řečeno, omezení obecného sekvenčního počtu na sekvence jednoduchého následného vzorce se stejnými pravidly odvození jako pro obecné sekvence představuje intuitivní sekvenční počet. (Tento omezený sekvenční počet je označen LJ.)

Podobně lze získat kalkul pro duální intuitivní logiku (typ parakonzistentní logiky ) tím, že v předchůdci bude vyžadováno, aby byly sekvence singulární.

V mnoha případech, sequents jsou také předpokládá, že se skládají z multimnozin nebo sad místo sekvencí. Tak se ignoruje pořadí nebo dokonce počty výskytů vzorců. Pro klasickou výrokovou logiku to nepřináší problém, protože závěry, které lze vyvodit ze souboru premis, nezávisí na těchto datech. V substrukturální logice to však může být docela důležité.

Systémy přirozené dedukce používají podmíněná tvrzení s jedním důsledkem, ale obvykle nepoužívají stejné sady pravidel odvození jako Gentzen zavedený v roce 1934. Zejména tabulkové systémy přirozené dedukce , které jsou velmi praktické pro praktické dokazování vět v propozičním počtu a predikátu kalkul, aplikovali Suppes (1957) a Lemmon (1965) pro výuku úvodní logiky v učebnicích. chyba harvtxt: žádný cíl: CITEREFSuppes1957 ( nápověda )

Etymologie

Historicky byly sekvence zavedeny Gerhardem Gentzenem , aby specifikoval jeho slavný sekvenční počet . Ve své německé publikaci použil slovo „Sequenz“. V angličtině se však slovo „ sekvence “ již používá jako překlad do němčiny „Folge“ a v matematice se vyskytuje poměrně často. Termín „následník“ byl poté vytvořen při hledání alternativního překladu německého výrazu.

Kleene k překladu do angličtiny uvádí následující poznámku: „Gentzen říká„ Sequenz “, což překládáme jako„ sekvenční “, protože„ sekvenci “jsme již použili pro jakoukoli posloupnost objektů, kde v němčině je„ Folge “.“

Viz také

• Gerhard Gentzen
• Intuicionistická logika
• Přirozený odpočet
• Sekvenční počet

Poznámky

Reference

• Ben-Ari, Mordechai (2012) [1993]. Matematická logika pro informatiku . Londýn: Springer. ISBN   978-1-4471-4128-0 .
• Church, Alonzo (1996) [1944]. Úvod do matematické logiky . Princeton, New Jersey: Princeton University Press. ISBN   978-0-691-02906-1 .
• Curry, Haskell Brooks (1977) [1963]. Základy matematické logiky . New York: Dover Publications Inc. ISBN   978-0-486-63462-3 .
• Gentzen, Gerhard (1934). „Untersuchungen über das logische Schließen. I“ . Mathematische Zeitschrift . 39 (2): 176–210. doi : 10,1007 / bf01201353 .
• Gentzen, Gerhard (1935). „Untersuchungen über das logische Schließen. II“ . Mathematische Zeitschrift . 39 (3): 405–431. doi : 10,1007 / bf01201363 .
• Hilbert, David ; Bernays, Paul (1970) [1939]. Grundlagen der Mathematik II (druhé vydání). Berlín, New York: Springer-Verlag. ISBN   978-3-642-86897-9 .
• Huth, Michael; Ryan, Mark (2004). Logika v informatice (druhé vydání). Cambridge, Velká Británie: Cambridge University Press. ISBN   978-0-521-54310-1 .
• Kleene, Stephen Cole (2009) [1952]. Úvod do metamatematiky . Ishi Press International. ISBN   978-0-923891-57-2 .
• Kleene, Stephen Cole (2002) [1967]. Matematická logika . Mineola, New York: Dover Publications. ISBN   978-0-486-42533-7 .
• Lemmon, Edward John (1965). Počáteční logika . Thomas Nelson. ISBN   0-17-712040-1 .
• Prawitz, Dag (2006) [1965]. Přirozená dedukce: Důkazová teoretická studie . Mineola, New York: Dover Publications. ISBN   978-0-486-44655-4 .
• Smullyan, Raymond Merrill (1995) [1968]. Logika prvního řádu . New York: Dover Publications. ISBN   978-0-486-68370-6 .
• Suppes, Patrick Colonel (1999) [1957]. Úvod do logiky . Mineola, New York: Dover Publications. ISBN   978-0-486-40687-9 .
• Takeuti, Gaisi (2013) [1975]. Teorie důkazů (druhé vydání). Mineola, New York: Dover Publications. ISBN   978-0-486-49073-1 .

externí odkazy

• „Sequent (in logic)“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]