Sekwencja - Sequent

W logice matematycznej , A SEQUENT jest bardzo ogólny rodzaju twierdzenia warunkowego.

${\ Displaystyle A_ {1}, \, \ kropki, A_ {m} \, \ vdash \, B_ {1}, \, \ kropki, B_ {n}.}$

Sekwencja może mieć dowolną liczbę m formuł warunkowych A _i (zwanych „ poprzednikami ”) i dowolną liczbę n potwierdzonych formuł B _j (nazywanych „ następczymi ” lub „ następnikami ”). Przez sekwencję rozumie się, że jeśli wszystkie warunki poprzedzające są prawdziwe, to przynajmniej jedna z następujących formuł jest prawdziwa. Ten styl warunkowego twierdzenia jest prawie zawsze związany z pojęciowymi ramami rachunku sekwencyjnego .

Wprowadzenie

Forma i semantyka ciągów

Sekwencje najlepiej zrozumieć w kontekście następujących trzech rodzajów sądów logicznych :

1. Bezwarunkowe twierdzenie . Brak formuł poprzedzających.
   • Przykład: ⊢ B
   • Znaczenie: B jest prawdą.
2. Asercja warunkowa . Dowolna liczba formuł poprzedzających.
   1. Proste twierdzenie warunkowe . Pojedyncza następująca formuła.
      • Przykład: A ₁ , A ₂ , A ₃ ⊢ B
      • Znaczenie: JEŻELI A ₁ ORAZ A ₂ ORAZ A ₃ są prawdziwe, TO B jest prawdziwe.
   2. Sekwencja . Dowolna liczba następujących po sobie formuł.
      • Przykład: A ₁ , A ₂ , A ₃ ⊢ B ₁ , B ₂ , B ₃ , B ₄
      • Znaczenie: JEŻELI A ₁ ORAZ A ₂ ORAZ A ₃ są prawdziwe, TO B ₁ LUB B ₂ LUB B ₃ LUB B ₄ jest prawdziwe.

Zatem sekwencje są uogólnieniem prostych twierdzeń warunkowych, które są uogólnieniem twierdzeń bezwarunkowych.

W tym przypadku słowo „LUB” jest włączającym operatorem LUB . Motywacja semantyki rozłącznej po prawej stronie sekwencji pochodzi z trzech głównych korzyści.

1. Symetria klasycznych reguł wnioskowania dla sekwencji z taką semantyką.
2. Łatwość i prostota konwersji takich klasycznych reguł na reguły intuicjonistyczne.
3. Możliwość udowodnienia kompletności rachunku predykatów, gdy jest wyrażona w ten sposób.

Wszystkie te trzy korzyści zostały zidentyfikowane w opracowaniu założycielskim Gentzena (1934 , s. 194).

Nie wszyscy autorzy trzymali się oryginalnego znaczenia Gentzena dla słowa „sequent”. Na przykład Lemmon (1965) użył słowa „sekwencyjny” wyłącznie dla prostych twierdzeń warunkowych z jedną i tylko jedną następującą formułą. Ta sama pojedyncza konsekwentna definicja sekwencji jest podana przez Huth & Ryan 2004 , s. 5.

Szczegóły składni

W ogólnej kolejności formularza

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

zarówno Γ, jak i Σ są ciągami formuł logicznych, a nie zbiorami . Dlatego zarówno liczba, jak i kolejność występowania formuł są istotne. W szczególności ta sama formuła może pojawić się dwukrotnie w tej samej kolejności. Pełny zestaw reguł wnioskowania z rachunku różniczkowego sekwencyjnego zawiera reguły do ​​zamiany sąsiednich formuł po lewej i po prawej stronie symbolu asercji (a tym samym do arbitralnego permutowania lewej i prawej sekwencji), a także do wstawiania dowolnych formuł i usuwania zduplikowanych kopii po lewej stronie i właściwe sekwencje. (Jednak Smullyan (1995 , s. 107–108) używa zestawów formuł w sekwencjach zamiast sekwencji formuł. W konsekwencji nie są wymagane trzy pary reguł strukturalnych zwane „przerzedzaniem”, „kurczeniem się” i „wymianą”).

Symbol „ ” jest często określany jako „ kołowrót ”, „prawy hals”, „trójnik”, „znak potwierdzenia” lub „symbol potwierdzenia”. Często czyta się je sugestywnie jako „ustępstwa”, „dowodzi” lub „pociąga za sobą”. ${\ displaystyle \ vdash}$

Nieruchomości

Skutki wstawiania i usuwania zdań

Ponieważ każda formuła w poprzedniku (po lewej stronie) musi być prawdziwa, aby stwierdzić prawdziwość co najmniej jednej formuły w następstwie (po prawej stronie), dodanie formuł po obu stronach skutkuje słabszą sekwencją, podczas gdy usunięcie ich z obu stron daje silniejszy. Jest to jedna z zalet symetrii, która wynika z zastosowania semantyki rozłącznej po prawej stronie symbolu asercji, podczas gdy semantyka koniunkcyjna jest stosowana po lewej stronie.

Konsekwencje pustych list formuł

W skrajnym przypadku, gdy lista poprzedzających formuł sekwencji jest pusta, następnik jest bezwarunkowy. Różni się to od prostego bezwarunkowego twierdzenia, ponieważ liczba następników jest dowolna, a niekoniecznie pojedynczy następnik. Na przykład „⊢ B ₁ , B ₂ ” oznacza, że ​​albo B ₁ , albo B ₂ , albo oba muszą być prawdziwe. Pusta lista formuł poprzedzających jest odpowiednikiem zdania „zawsze prawdziwego”, zwanego „ verum ”, oznaczonego jako „⊤”. (Zobacz Trójnik (symbol) .)

W skrajnym przypadku, gdzie lista konsekwencji formuł o SEQUENT jest pusta, reguła jest jeszcze co najmniej jeden termin na prawo być prawdą, co jest oczywiście niemożliwe . Wskazuje na to zdanie „zawsze fałszywe”, zwane „ falsum ”, oznaczane jako „⊥”. Ponieważ konsekwencja jest fałszywa, przynajmniej jeden z poprzedników musi być fałszywy. Na przykład „ A ₁ , A ₂ ⊢” oznacza, że ​​co najmniej jeden z poprzedników A ₁ i A ₂ musi być fałszywy.

Tu znowu widać symetrię z powodu rozłącznej semantyki po prawej stronie. Jeśli lewa strona jest pusta, to co najmniej jedno zdanie z prawej strony musi być prawdziwe. Jeśli prawa strona jest pusta, to co najmniej jedno ze zdań po lewej stronie musi być fałszywe.

Podwójnie skrajny przypadek „⊢”, w którym zarówno poprzednia, jak i następna lista formuł są puste, jest „ nie do spełnienia ”. W tym przypadku znaczenie sekwencji jest faktycznie „⊤ ⊢ ⊥”. Jest to równoważne z sekwencyjnym „⊢ ⊥”, które oczywiście nie może być poprawne.

Przykłady

Sekwencja postaci „⊢ α, β” dla formuł logicznych α i β oznacza, że ​​albo α jest prawdą, albo β jest prawdą (lub oba). Ale to nie znaczy, że albo α jest tautologią, albo β jest tautologią. Aby to wyjaśnić, rozważ przykład „⊢ B ∨ A, C ∨ ¬A”. Jest to poprawna sekwencja, ponieważ albo B ∨ A jest prawdą, albo C ∨ ¬A jest prawdą. Ale żadne z tych wyrażeń nie jest odrębną tautologią. To właśnie dysjunkcja tych dwóch wyrażeń jest tautologią.

Podobnie, sekwencja postaci „α, β ⊢” dla formuł logicznych α i β oznacza, że ​​albo α jest fałszem, albo β jest fałszem. Ale to nie znaczy, że albo α jest sprzecznością, albo β jest sprzecznością. Aby to wyjaśnić, rozważ przykład „B ∧ A, C ∧ ¬A ⊢”. Jest to poprawna sekwencja, ponieważ albo B ∧ A jest fałszem, albo C ∧ ¬A jest fałszem. Ale żadne z tych wyrażeń nie jest sprzecznością w oderwaniu. To połączenie tych dwóch wyrażeń jest sprzecznością.

Zasady

Większość systemów dowodowych umożliwia wyprowadzenie jednej sekwencji z drugiej. Te reguły wnioskowania są zapisane z listą sekwencji powyżej i poniżej wiersza . Ta reguła wskazuje, że jeśli wszystko powyżej linii jest prawdą, tak samo jest z wszystkim pod linią.

Typowa zasada to:

${\ Displaystyle {\ Frac {\ Gamma, \ alpha \ vdash \ Sigma \ qquad \ Gamma \ vdash \ alpha} {\ Gamma \ vdash \ Sigma}}}$

Oznacza to, że jeśli możemy wydedukować, że daje , a to daje , to możemy również wydedukować, że daje . (Zobacz także pełny zestaw reguł wnioskowania o rachunku różniczkowym ). ${\ displaystyle \ Gamma, \ alpha}$${\ displaystyle \ Sigma}$${\ displaystyle \ Gamma}$${\ displaystyle \ alpha}$${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma}$

Interpretacja

Historia znaczenia kolejnych stwierdzeń

Symbol potwierdzenia w sekwencjach pierwotnie oznaczał dokładnie to samo, co operator implikacji. Ale z biegiem czasu jego znaczenie zmieniło się, aby oznaczać udowodnienie w teorii, a nie prawdę semantyczną we wszystkich modelach.

W 1934 roku Gentzen nie zdefiniował symbolu asercji „⊢” w kolejności oznaczającej możliwość udowodnienia. Zdefiniował to jako dokładnie to samo, co operator implikacji „⇒”. Używając „→” zamiast „⊢” i „⊃” zamiast „⇒”, napisał: „Sekwencja A ₁ ,…, A _μ → B ₁ ,…, B _ν oznacza, jeśli chodzi o zawartość, dokładnie taki sam jak wzór (A ₁ & ... & A _μ ) ⊃ (B ₁ ∨ ... ∨ B _ν ) ”. (Gentzen zastosował symbol strzałki w prawo między poprzednikami a następnikami sekwencji. Użył symbolu „⊃” dla operatora implikacji logicznej).

W 1939 roku Hilbert i Bernays stwierdzili również, że sekwencja ma takie samo znaczenie jak odpowiadająca jej formuła implikacji.

W 1944 roku Alonzo Church podkreślił, że kolejne twierdzenia Gentzena nie oznaczają udowodnienia.

„Zastosowania twierdzenia o dedukcji jako reguły pierwotnej lub pochodnej nie należy jednak mylić ze stosowaniem Sequenzena przez Gentzena. Strzała Gentzena → nie jest porównywalna z naszą notacją składniową, ⊢, ale należy do jego języka przedmiotowego (jak wynika jasno z faktu, że wyrażenia go zawierające pojawiają się jako przesłanki i wnioski w zastosowaniu jego reguł wnioskowania) ”.

Liczne publikacje po tym czasie stwierdziły, że symbol asercji w sekwencjach oznacza możliwość udowodnienia w ramach teorii, w której sekwencje są formułowane. Curry w 1963 r., Lemmon w 1965 r. I Huth i Ryan w 2004 r. Wszyscy twierdzą, że kolejny symbol asercji oznacza możliwość udowodnienia. Jednak Ben-Ari (2012 , s. 69) stwierdza, że ​​symbol asercji w sekwencjach systemu Gentzena, który określa jako „⇒”, jest częścią języka przedmiotowego, a nie metajęzyka.

Według Prawitza (1965): „Rachunki ciągów można rozumieć jako meta-rachunki dla relacji wyprowadzalności w odpowiednich systemach dedukcji naturalnej”. A ponadto: „Dowód w rachunku ciągów można traktować jako instrukcję, jak skonstruować odpowiednią dedukcję naturalną”. Innymi słowy, symbol asercji jest częścią języka przedmiotowego rachunku sekwencyjnego, który jest rodzajem meta-rachunku, ale jednocześnie oznacza możliwość wyprowadzenia w podstawowym systemie dedukcji naturalnej.

Intuicyjne znaczenie

Sekwencja to sformalizowane stwierdzenie możliwości udowodnienia, które jest często używane przy określaniu rachunków do odliczenia . W rachunku sekwencyjnym nazwa sequent jest używana dla konstruktu, co można uznać za specyficzny rodzaj sądu , charakterystyczny dla tego systemu dedukcyjnego.

Intuicyjne znaczenie sekwencji jest takie, że przy założeniu, że Γ zakończenie Σ jest możliwe do udowodnienia. Klasycznie wzory po lewej stronie kołowrotu można interpretować łącznie, podczas gdy wzory po prawej stronie można traktować jako rozłączność . Oznacza to, że jeśli wszystkie formuły w Γ trzymają się, to przynajmniej jedna formuła w Σ również musi być prawdziwa. Jeśli następca jest pusty, jest to interpretowane jako fałsz, tj. Oznacza, że ​​Γ dowodzi fałszu, a zatem jest niespójny. Z drugiej strony przyjmuje się, że pusty poprzednik jest prawdziwy, tj. Oznacza, że ​​Σ następuje bez żadnych założeń, tj. Zawsze jest prawdziwe (jako dysjunkcja). Sekwencja tej formy, z pustym Γ, jest nazywana asercją logiczną . ${\ displaystyle \ Gamma \ vdash \ Sigma}$${\ displaystyle \ Gamma \ vdash}$${\ displaystyle \ vdash \ Sigma}$

Oczywiście możliwe są inne intuicyjne wyjaśnienia, które są klasycznie równoważne. Na przykład można odczytać jako twierdzenie, że nie może być tak, że każda formuła w Γ jest prawdziwa, a każda formuła w Σ jest fałszywa (jest to związane z podwójną negacją interpretacji klasycznej logiki intuicjonistycznej , takiej jak twierdzenie Glivenko ). ${\ displaystyle \ Gamma \ vdash \ Sigma}$

W każdym razie te intuicyjne odczyty mają jedynie charakter pedagogiczny. Ponieważ dowody formalne w teorii dowodu są czysto syntaktyczne , znaczenie (wyprowadzenie) ciągu jest określone tylko przez właściwości rachunku, który dostarcza faktycznych reguł wnioskowania .

Pomijając jakiekolwiek sprzeczności w technicznie precyzyjnej definicji powyżej, możemy opisać sekwencje we wprowadzającej ich logicznej formie. reprezentuje zbiór założeń, od których zaczynamy nasz logiczny proces, na przykład „Sokrates jest człowiekiem” i „Wszyscy ludzie są śmiertelni”. Reprezentuje logiczny wniosek, że następuje w tych pomieszczeniach. Na przykład „Sokrates jest śmiertelny” wynika z rozsądnej formalizacji powyższych punktów i możemy się spodziewać, że zobaczymy go z boku kołowrotu . W tym sensie oznacza proces rozumowania, czyli „dlatego” w języku angielskim. ${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ vdash}$

Wariacje

Wprowadzone tutaj ogólne pojęcie sekwencji można wyspecjalizować na różne sposoby. Mówi się, że sekwencja jest sekwencją intuicjonistyczną, jeśli w następstwie występuje co najwyżej jedna formuła (chociaż możliwe są również rachunki wielu następstw dla logiki intuicjonistycznej). Dokładniej, ograniczenie ogólnego rachunku sekwencyjnego do ciągów z pojedynczym następczym wzorem, z tymi samymi regułami wnioskowania, jak w przypadku ciągów ogólnych, stanowi intuicyjny rachunek sekwencyjny. (Ten zastrzeżony rachunek sekwencyjny jest oznaczony LJ).

Podobnie, można uzyskać rachunki dla logiki dualnej intuicjonistycznej (rodzaj logiki parakonsystentnej ), wymagając, aby sekwencje były pojedyncze w poprzedniku.

W wielu przypadkach sequents zakłada również składać się z multisets lub zestawów zamiast sekwencji. W ten sposób lekceważy się kolejność, a nawet liczbę wystąpień formuł. Dla klasycznej logiki zdań nie stanowi to problemu, ponieważ wnioski, jakie można wyciągnąć ze zbioru przesłanek, nie zależą od tych danych. Jednak w logice podstrukturalnej może to stać się bardzo ważne.

Systemy naturalnej dedukcji używają twierdzeń warunkowych o pojedynczej konsekwencji, ale zazwyczaj nie używają tych samych zestawów reguł wnioskowania co Gentzen wprowadzonych w 1934 roku. W szczególności tabelaryczne systemy dedukcji naturalnych , które są bardzo wygodne do praktycznego dowodzenia twierdzeń w rachunku zdań i predykatu rachunek różniczkowy, zostały zastosowane przez Suppesa (1957) i Lemmona (1965) do nauczania logiki wprowadzającej w podręcznikach. błąd harvtxt: brak celu: CITEREFSuppes1957 ( pomoc )

Etymologia

Historycznie rzecz biorąc, sekwencje zostały wprowadzone przez Gerharda Gentzena w celu sprecyzowania jego słynnego rachunku sekwencyjnego . W swojej niemieckiej publikacji użył słowa „Sequenz”. Jednak w języku angielskim słowo „ sekwencja ” jest już używane jako tłumaczenie na niemiecki „Folge” i pojawia się dość często w matematyce. W celu znalezienia alternatywnego tłumaczenia niemieckiego wyrażenia utworzono wówczas termin „sequent”.

Kleene komentuje tłumaczenie na język angielski: „Gentzen mówi„ Sequenz ”, co tłumaczymy jako„ sequent ”, ponieważ używaliśmy już wyrażenia„ sequence ”w odniesieniu do każdego ciągu obiektów, gdzie niemiecki to„ Folge ””.

Zobacz też

• Gerhard Gentzen
• Logika intuicyjna
• Odliczenie naturalne
• Rachunek sekwencyjny

Uwagi

Bibliografia

• Ben-Ari, Mordechai (2012) [1993]. Logika matematyczna dla informatyki . Londyn: Springer. ISBN   978-1-4471-4128-0 .
• Church, Alonzo (1996) [1944]. Wprowadzenie do logiki matematycznej . Princeton, New Jersey: Princeton University Press. ISBN   978-0-691-02906-1 .
• Curry, Haskell Brooks (1977) [1963]. Podstawy logiki matematycznej . Nowy Jork: ISBN Dover Publications Inc.   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 (wyd. Drugie). Berlin, Nowy Jork: Springer-Verlag. ISBN   978-3-642-86897-9 .
• Huth Michael; Ryan, Mark (2004). Logika w informatyce (wyd. Drugie). Cambridge, Wielka Brytania: Cambridge University Press. ISBN   978-0-521-54310-1 .
• Kleene, Stephen Cole (2009) [1952]. Wprowadzenie do metamatematyki . Ishi Press International. ISBN   978-0-923891-57-2 .
• Kleene, Stephen Cole (2002) [1967]. Logika matematyczna . Mineola, Nowy Jork: Dover Publications. ISBN   978-0-486-42533-7 .
• Lemmon, Edward John (1965). Logika początku . Thomas Nelson. ISBN   0-17-712040-1 .
• Prawitz, Dag (2006) [1965]. Naturalna dedukcja: badanie teoretyczne . Mineola, Nowy Jork: Dover Publications. ISBN   978-0-486-44655-4 .
• Smullyan, Raymond Merrill (1995) [1968]. Logika pierwszego rzędu . New York: Dover Publications. ISBN   978-0-486-68370-6 .
• Suppes, Patrick Colonel (1999) [1957]. Wprowadzenie do logiki . Mineola, Nowy Jork: Dover Publications. ISBN   978-0-486-40687-9 .
• Takeuti, Gaisi (2013) [1975]. Teoria dowodu (wyd. Drugie). Mineola, Nowy Jork: Dover Publications. ISBN   978-0-486-49073-1 .

Linki zewnętrzne

• „Sekwencja (w logice)” , Encyklopedia Matematyki , EMS Press , 2001 [1994]