Volgorde - Sequent

In de wiskundige logica is een sequent een zeer algemeen soort voorwaardelijke bewering.

{\ displaystyle A_ {1}, \, \ dots, A_ {m} \, \ vdash \, B_ {1}, \, \ dots, B_ {n}.}

Een sequent kan elk aantal zijn m conditie formules A _i (zogenaamde " antecedenten ') en een willekeurig aantal n van beweerd formules B _j (zogenaamde 'succedents' of' consequenten "). Met een sequent wordt bedoeld dat als alle voorafgaande voorwaarden waar zijn, dan ten minste één van de daaruit voortvloeiende formules waar is. Deze stijl van voorwaardelijke bewering wordt bijna altijd geassocieerd met het conceptuele raamwerk van opeenvolgende calculus .

Invoering

De vorm en semantiek van sequenties

Sequenten worden het best begrepen in de context van de volgende drie soorten logische oordelen :

Onvoorwaardelijke bewering . Geen antecedentformules.
- Voorbeeld: ⊢ B
- Betekenis: B is waar.
Voorwaardelijke bewering . Een willekeurig aantal antecedentformules.
1. Eenvoudige voorwaardelijke bewering . Enkele consequente formule.
  - Voorbeeld: A ₁ , A ₂ , A ₃ ⊢ B
  - Betekenis: ALS A ₁ EN A ₂ EN A ₃ waar zijn, DAN is B waar.
2. Sequent . Een willekeurig aantal opeenvolgende formules.
  - Voorbeeld: A ₁ , A ₂ , A ₃ ⊢ B ₁ , B ₂ , B ₃ , B ₄
  - Betekenis: ALS A ₁ EN A ₂ EN A ₃ waar zijn, DAN is B ₁ OF B ₂ OF B ₃ OF B ₄ waar.

Sequenten zijn dus een generalisatie van eenvoudige voorwaardelijke beweringen, die een generalisatie zijn van onvoorwaardelijke beweringen.

Het woord "OF" is hier de allesomvattende OF . De motivatie voor disjunctieve semantiek aan de rechterkant van een sequent komt voort uit drie belangrijke voordelen.

De symmetrie van de klassieke inferentieregels voor sequenten met dergelijke semantiek.
Het gemak en de eenvoud van het omzetten van dergelijke klassieke regels in intuïtionistische regels.
Het vermogen om de volledigheid van predikatenrekening te bewijzen wanneer deze op deze manier wordt uitgedrukt.

Alle drie deze voordelen werden geïdentificeerd in het oprichtingsdocument van Gentzen (1934 , p. 194).

Niet alle auteurs hebben de oorspronkelijke betekenis van Gentzen voor het woord "sequent" gevolgd. Bijvoorbeeld Lemmon (1965) het woord "sequent" strikt voor eenvoudige voorwaardelijke beweringen met slechts één daaropvolgende formule. Dezelfde definitie voor een sequent met één consequentie wordt gegeven door Huth & Ryan 2004 , p. 5.

Syntaxis details

In een algemene volgorde van het formulier

{\ displaystyle \ Gamma \ vdash \ Sigma}

zowel Γ en Σ zijn reeksen logische formules niet stelt . Daarom zijn zowel het aantal als de volgorde waarin formules voorkomen significant. In het bijzonder kan dezelfde formule twee keer in dezelfde volgorde voorkomen. De volledige set sequent calculus afleidingsregels bevat regels swap aangrenzende formules links en rechts van de bewering symbool (en daardoor willekeurig permuteren links en rechts sequenties), alsmede willekeurige formules voegen en duplicaten te verwijderen in de linker en de juiste sequenties. ( Smullyan (1995 , pp. 107-108) gebruikt echter reeksen formules in reeksen in plaats van reeksen formules. Bijgevolg zijn de drie paren structurele regels die ‘uitdunnen’, ‘contractie’ en ‘uitwisseling’ worden genoemd, niet vereist.)

Het symbool ' ' wordt vaak het ‘ tourniquet ’, ‘rechter overstag’, ‘tee’, ‘beweringsteken’ of ‘beweringsteken’ genoemd. Het wordt vaak suggestief gelezen als "levert op", "bewijst" of "inhoudt". ${\ displaystyle \ vdash}$

Eigendommen

Effecten van het invoegen en verwijderen van proposities

Aangezien elke formule in het antecedent (de linkerkant) waar moet zijn om de waarheid van ten minste één formule in het succedent (de rechterkant) te concluderen, resulteert het toevoegen van formules aan beide kanten in een zwakkere reeks, terwijl ze aan beide kanten worden verwijderd een sterkere. Dit is een van de symmetrievoordelen die voortvloeien uit het gebruik van disjunctieve semantiek aan de rechterkant van het beweringssymbool, terwijl conjunctieve semantiek aan de linkerkant wordt aangehouden.

Gevolgen van lege lijsten met formules

In het extreme geval waarin de lijst met antecedentformules van een sequent leeg is, is het vervolg onvoorwaardelijk. Dit verschilt van de simpele onvoorwaardelijke bewering omdat het aantal consequenties willekeurig is, niet noodzakelijk een enkele consequentie. Dus bijvoorbeeld '⊢ B ₁ , B ₂ ' betekent dat óf B ₁ , óf B ₂ , of beide waar moeten zijn. Een lege antecedentformulelijst is equivalent aan de "altijd waar" propositie, genaamd de " verum ", aangeduid met "⊤". (Zie T-stuk (symbool) .)

In het extreme geval waarin de lijst met opeenvolgende formules van een sequent leeg is, is de regel nog steeds dat ten minste één term aan de rechterkant waar is, wat duidelijk onmogelijk is . Dit wordt aangegeven door de 'altijd valse' propositie, de " falsum " genaamd , aangeduid met "⊥". Aangezien de consequentie onwaar is, moet ten minste één van de antecedenten onwaar zijn. Zo betekent ' A ₁ , A ₂ ⊢' bijvoorbeeld dat ten minste één van de antecedenten A ₁ en A ₂ onwaar moet zijn.

Men ziet hier weer een symmetrie vanwege de disjunctieve semantiek aan de rechterkant. Als de linkerkant leeg is, moeten een of meer proposities aan de rechterkant waar zijn. Als de rechterkant leeg is, moeten een of meer van de proposities aan de linkerkant onwaar zijn.

Het dubbel extreme geval '⊢', waarbij zowel de antecedente als de daaruit voortvloeiende lijst met formules leeg zijn, is " niet bevredigend ". In dit geval is de betekenis van de sequent in feite '⊤ ⊢ ⊥'. Dit komt overeen met de opeenvolgende '⊢ ⊥', die duidelijk niet geldig kan zijn.

Voorbeelden

Een opeenvolging van de vorm '⊢ α, β', voor logische formules α en β, betekent dat α waar is of β waar is (of beide). Maar het betekent niet dat α een tautologie of β een tautologie is. Beschouw ter verduidelijking het voorbeeld '⊢ B ∨ A, C ∨ ¬A'. Dit is een geldige reeks omdat ofwel B ∨ A waar is of C ∨ ¬A waar is. Maar geen van deze uitdrukkingen is een tautologie op zichzelf. Het is de scheiding van deze twee uitdrukkingen die een tautologie is.

Evenzo betekent een sequent van de vorm 'α, β ⊢' voor logische formules α en β dat α onwaar of β onwaar is. Maar het betekent niet dat α een tegenstrijdigheid of β een tegenspraak is. Beschouw ter verduidelijking het voorbeeld 'B ∧ A, C ∧ ¬A ⊢'. Dit is een geldige reeks omdat ofwel B ∧ A onwaar is of C ∧ ¬A onwaar. Maar geen van deze uitdrukkingen is op zichzelf een tegenstrijdigheid. Het is de combinatie van deze twee uitdrukkingen die in tegenspraak zijn.

Reglement

De meeste proof-systemen bieden manieren om de ene sequentie van de andere af te leiden. Deze inferentieregels zijn geschreven met een lijst met reeksen boven en onder een regel . Deze regel geeft aan dat als alles boven de regel waar is, ook alles onder de regel waar is.

Een typische regel is:

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

Dit geeft aan dat als we die opbrengsten kunnen afleiden , en die opbrengsten , we ook die opbrengsten kunnen afleiden . (Zie ook de volledige reeks opeenvolgende afleidingsregels voor calculus .) ${\ displaystyle \ Gamma, \ alpha}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle \ Sigma}$

Interpretatie

Geschiedenis van de betekenis van opeenvolgende beweringen

Het beweringssymbool in reeksen betekende oorspronkelijk precies hetzelfde als de implicatie-operator. Maar in de loop van de tijd is de betekenis ervan veranderd om bewijsbaarheid binnen een theorie aan te duiden in plaats van semantische waarheid in alle modellen.

In 1934 definieerde Gentzen het beweringssymbool '⊢' niet in een reeks om bewijsbaarheid aan te duiden. Hij definieerde het als precies hetzelfde als de implicatie-operator '⇒'. Gebruikmakend van '→' in plaats van '⊢' en '⊃' in plaats van '⇒', schreef hij: "De opeenvolging A ₁ , ..., A _μ → B ₁ , ..., B _ν betekent inhoudelijk, precies hetzelfde als de formule (A ₁ & ... & A _μ ) ⊃ (B ₁ ∨ ... ∨ B _ν ) ". (Gentzen gebruikte het symbool met de pijl naar rechts tussen de antecedenten en de gevolgen van sequenties. Hij gebruikte het symbool '⊃' voor de logische implicatie-operator.)

In 1939 verklaarden Hilbert en Bernays eveneens dat een sequent dezelfde betekenis heeft als de overeenkomstige implicatieformule.

In 1944 benadrukte Alonzo Church dat de opeenvolgende beweringen van Gentzen geen bewijsbaarheid betekenden.

"Gebruik van de aftrekstelling als primitieve of afgeleide regel moet echter niet worden verward met het gebruik van Sequenzen door Gentzen. Want Gentzen's pijl, →, is niet vergelijkbaar met onze syntactische notatie, ⊢, maar behoort tot blijkt duidelijk uit het feit dat uitdrukkingen die het bevatten, verschijnen als premissen en conclusies bij het toepassen van zijn inferentieregels). "

Talloze publicaties na deze tijd hebben verklaard dat het beweringssymbool in reeksen bewijsbaarheid betekent binnen de theorie waarin de reeksen worden geformuleerd. Curry in 1963, Lemmon in 1965 en Huth en Ryan in 2004 stellen allemaal dat het opeenvolgende beweringssymbool bewijsbaarheid betekent. Echter, Ben-Ari (2012 , blz. 69) dat de stelling symbool Gentzen-systeem sequents, die hij geeft als '⇒', bevindt zich in de objecttaal, niet metataal.

Volgens Prawitz (1965): "De calculi van sequenten kunnen worden opgevat als metacalculi voor de afleidbaarheidsrelatie in de overeenkomstige systemen van natuurlijke deductie." En verder: "Een bewijs in een berekening van reeksen kan worden beschouwd als een instructie voor het construeren van een overeenkomstige natuurlijke aftrek." Met andere woorden, het beweringssymbool maakt deel uit van de objecttaal voor de opeenvolgende calculus, wat een soort metacalculus is, maar tegelijkertijd duidt op deducibiliteit in een onderliggend natuurlijk deductiesysteem.

Intuïtieve betekenis

Een sequent is een geformaliseerde verklaring van bewijsbaarheid die vaak wordt gebruikt bij het specificeren van calculi voor aftrek . In de sequent-calculus wordt de naam sequent gebruikt voor het construct, dat kan worden beschouwd als een specifiek soort oordeel , kenmerkend voor dit deductiesysteem.

De intuïtieve betekenis van de sequent is dat onder de aanname van Γ de conclusie van Σ aantoonbaar is. Klassiek kunnen de formules aan de linkerkant van het tourniquet conjunctief worden geïnterpreteerd, terwijl de formules aan de rechterkant als een disjunctie kunnen worden beschouwd . Dit betekent dat, als alle formules in Γ kloppen, er minstens één formule in Σ ook waar moet zijn. Als de succedent leeg is, wordt dit geïnterpreteerd als valsheid, dwz dat Γ valsheid bewijst en dus inconsistent is. Aan de andere kant wordt aangenomen dat een leeg antecedent waar is, dat wil zeggen dat Σ volgt zonder enige aanname, dat wil zeggen dat het altijd waar is (als een disjunctie). Een reeks van deze vorm, met Γ leeg, staat bekend als een logische bewering . ${\ displaystyle \ Gamma \ vdash \ Sigma}$ ${\ displaystyle \ Gamma \ vdash}$ ${\ displaystyle \ vdash \ Sigma}$

Natuurlijk zijn andere intuïtieve verklaringen mogelijk, die klassiek equivalent zijn. Het kan bijvoorbeeld worden gelezen als een bewering dat het niet zo kan zijn dat elke formule in Γ waar is en elke formule in Σ onwaar (dit houdt verband met de interpretaties van dubbele negatie van de klassieke intuïtionistische logica , zoals de stelling van Glivenko ). ${\ displaystyle \ Gamma \ vdash \ Sigma}$

In ieder geval zijn deze intuïtieve metingen alleen pedagogisch. Aangezien formele bewijzen in bewijstheorie puur syntactisch zijn , wordt de betekenis van (de afleiding van) een sequent alleen gegeven door de eigenschappen van de calculus die de feitelijke inferentieregels levert .

Behoudens tegenstrijdigheden in de technisch nauwkeurige definitie hierboven, kunnen we sequenten beschrijven in hun inleidende logische vorm. vertegenwoordigt een reeks aannames waarmee we ons logische proces beginnen, bijvoorbeeld "Socrates is een man" en "Alle mensen zijn sterfelijk". Het vertegenwoordigt een logische conclusie die volgt onder deze premissen. Bijvoorbeeld "Socrates is sterfelijk" volgt uit een redelijke formalisering van de bovenstaande punten en we zouden het kunnen verwachten aan de zijkant van het tourniquet . In deze zin betekent het redeneerproces, of "daarom" in het Engels. ${\ displaystyle \ Gamma}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ vdash}$

Variaties

Het algemene begrip sequent dat hier wordt geïntroduceerd, kan op verschillende manieren worden gespecialiseerd. Van een sequent wordt gezegd dat het een intuïtionistische sequent is als er maximaal één formule in het succedent is (hoewel multi-succedent-calculi voor intuïtionistische logica ook mogelijk zijn). Preciezer gezegd, de beperking van de algemene sequent-calculus tot sequenties met één enkele succedent-formule, met dezelfde inferentieregels als voor algemene sequenties, vormt een intuïtionistische sequent-calculus. (Deze beperkte opeenvolgende calculus wordt aangeduid als LJ.)

Evenzo kan men calculi verkrijgen voor duaal-intuïtionistische logica (een soort paraconsistente logica ) door te eisen dat sequenten singulier zijn in het antecedent.

In veel gevallen wordt aangenomen dat reeksen ook bestaan uit multisets of sets in plaats van reeksen. Zo negeert men de volgorde of zelfs het aantal keren dat de formules voorkomen. Voor de klassieke propositielogica levert dit geen probleem op, aangezien de conclusies die men uit een verzameling premissen kan trekken niet van deze gegevens afhangen. In de substructurele logica kan dit echter behoorlijk belangrijk worden.

Natuurlijke aftrek systemen maken gebruik van single-gevolg voorwaardelijke beweringen, maar ze meestal niet dezelfde sets van afleidingsregels gebruiken als Gentzen in 1934. In het bijzonder, introduceerde in tabelvorm natuurlijke deductie systemen, die erg handig voor praktisch theorema-proving in de propositielogica en predicaat calculus, werden toegepast door Suppes (1957) en Lemmon (1965) voor het onderwijzen van inleidende logica in leerboeken.

Etymologie

Historisch gezien zijn sequenten geïntroduceerd door Gerhard Gentzen om zijn beroemde sequent-calculus te specificeren . In zijn Duitse publicatie gebruikte hij het woord "Sequenz". In het Engels wordt het woord " sequentie " echter al gebruikt als vertaling naar het Duitse "Folge" en komt het vrij vaak voor in de wiskunde. De term "sequent" is dan ontstaan op zoek naar een alternatieve vertaling van de Duitse uitdrukking.

Kleene maakt het volgende commentaar op de vertaling in het Engels: "Gentzen zegt 'Sequenz', wat we vertalen als 'sequent', omdat we al 'sequence' hebben gebruikt voor elke opeenvolging van objecten, waarbij het Duits 'Folge' is."

Zie ook

Opmerkingen

Referenties

Ben-Ari, Mordechai (2012) [1993]. Wiskundige logica voor informatica . Londen: Springer. ISBN 978-1-4471-4128-0
Church, Alonzo (1996) [1944]. Inleiding tot wiskundige logica . Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02906-1
Curry, Haskell Brooks (1977) [1963]. Fundamenten van wiskundige logica . 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 (Tweede ed.). Berlijn, New York: Springer-Verlag. ISBN 978-3-642-86897-9
Huth, Michael; Ryan, Mark (2004). Logic in Computer Science (tweede ed.). Cambridge, Verenigd Koninkrijk: Cambridge University Press. ISBN 978-0-521-54310-1
Kleene, Stephen Cole (2009) [1952]. Inleiding tot metamathematica . Ishi Press International. ISBN 978-0-923891-57-2
Kleene, Stephen Cole (2002) [1967]. Wiskundige logica . Mineola, New York: Dover Publications. ISBN 978-0-486-42533-7
Lemmon, Edward John (1965). Beginnende logica . Thomas Nelson. ISBN 0-17-712040-1
Prawitz, Dag (2006) [1965]. Natuurlijke deductie: een bewijstheoretische studie . Mineola, New York: Dover Publications. ISBN 978-0-486-44655-4
Smullyan, Raymond Merrill (1995) [1968]. Logica van de eerste orde . New York: Dover Publications. ISBN 978-0-486-68370-6
Suppes, Patrick Colonel (1999) [1957]. Inleiding tot logica . Mineola, New York: Dover Publications. ISBN 978-0-486-40687-9
Takeuti, Gaisi (2013) [1975]. Bewijs theorie (Tweede ed.). Mineola, New York: Dover Publications. ISBN 978-0-486-49073-1

Externe links

"Sequent (in logic)" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]

Languages

In other projects