시퀀트

수학 논리학에서, 시퀀트는 매우 일반적인 종류의 조건부 주장입니다.

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

시퀀스는 임의의 수의 조건식_i A('제안자'라고 함)와 임의의 수의_j 단언식 B('제안자' 또는 '결과'라고 함)를 가질 수 있다.시퀀스는 모든 선행조건이 참이면 적어도 하나의 결과식이 참임을 의미하는 것으로 이해된다.이러한 조건부 주장은 거의 항상 순차 미적분의 개념적 틀과 연관되어 있다.

서론

시퀀스의 형태와 의미론

시퀀스는 다음 세 가지 논리적 판단의 맥락에서 가장 잘 이해됩니다.

1. 무조건적인 주장.선행 수식이 없습니다.
   • 예: § B
   • 의미: B는 사실이다.
2. 조건부 어설션임의의 수의 선행 수식.
   1. 단순한 조건부 어설션.하나의 결과 공식입니다.
      • 예₁: A, A₂, A₃ b B
      • 의미: A, A₂, A, A가₃ 참이면₁ B가 참입니다.
   2. 시퀀트임의의 수의 후속 수식.
      • 예₁: A, A₂ b₃₁ B, B₂, B₃, B, B₄
      • 의미: A, A, A가₂₃ 참이면₁ B, B₂₃, B₄ 또는 B가 참입니다₁.

따라서 시퀀스는 단순 조건부 어설션의 일반화이며, 이는 무조건 어설션의 일반화이다.

여기서 "OR"은 포함 ^[1]OR입니다.시퀀스의 오른쪽에 있는 분리 의미론에 대한 동기는 세 가지 주요 이점으로부터 온다.

1. 그러한 의미론을 가진 시퀀스에 대한 고전적 추론 규칙의 대칭성.
2. 이러한 고전적인 규칙을 직관적인 규칙으로 변환하는 용이성과 단순성.
3. 술어 미적분이 이렇게 표현될 때 완전함을 증명하는 능력.

이 세 가지 이점은 모두 Gentzen(1934년, 페이지 194년)의 창립서에서 확인되었습니다.

모든 저자들이 젠젠의 "후계"라는 단어의 본래 의미를 고수하지는 않았다.예를 들어, Lemmon(1965)은 "순차적"이라는 단어를 오직 하나의 결과 ^[2]공식을 가진 단순한 조건부 어설션에만 사용했다.시퀀스에 대한 동일한 단일 시퀀스의 정의는 Huth & Ryan 2004, 페이지 5에 제시되어 있다.

구문 상세

일반적인 형태에서

$\displaystyle \Gamma \vdash \Sigma }$

δ와 δ는 모두 논리식의 시퀀스이며 집합이 아닙니다.따라서 공식의 발생 횟수와 순서 모두 유의합니다.특히, 같은 공식은 같은 순서로 두 번 나타날 수 있습니다.시퀀셜 미적분 추론 규칙의 전체 세트에는 어설션 기호의 왼쪽과 오른쪽에 인접한 공식을 교환하고(따라서 좌우 시퀀스를 임의로 허용), 임의의 공식을 삽입하고 좌우 시퀀스 내에서 중복된 복사본을 제거하는 규칙이 포함되어 있습니다.(단, Smullyan(1995, 페이지 107–108)은 일련의 공식 대신 시퀀스의 공식 집합을 사용한다.따라서, 「씬닝」, 「수축」, 「교환」이라고 불리는 3쌍의 구조 룰은 필요 없습니다.)

기호$$'는 종종 "개찰구$",$ "오른쪽 방향", "티", "주장 기호" 또는 "주장 기호$"$로 불립니다.암시적으로 "양식", "증거", 또는 "못"으로 읽힌다.

특성.

제안 삽입 및 제거의 효과

선행자(왼쪽)의 모든 공식은 참이어야 하므로, 양쪽(오른쪽)에 적어도 하나의 공식의 참을 더하면 더 약한 시퀀스가 되는 반면, 양쪽에서 공식을 제거하면 더 강한 시퀀스가 됩니다.이것은 어설션 기호의 오른쪽에 있는 분리적 의미론의 사용으로 따르는 대칭적 이점 중 하나이며, 반면 왼쪽에 있는 결합적 의미론은 고수된다.

공식 리스트의 결과

시퀀스의 선행 공식 목록이 비어 있는 극단적인 경우 결과는 무조건입니다.이것은 결과의 수가 반드시 하나의 결과가 아닌 임의이기 때문에 단순한 무조건 주장과는 다릅니다.예를 들어 'B, B₁₂'는 B, B₂, 또는 둘 다₁ true여야 함을 의미합니다.비어 있는 선행 공식 목록은 "verum"이라고 불리는 "항상 참" 명제와 동등합니다. (Tee (기호 참조)

시퀀스의 결과 공식 목록이 비어 있는 극단적인 경우에는 여전히 오른쪽에 있는 적어도 하나의 항이 참이어야 하며, 이는 분명히 불가능합니다.이것은 "falsum"이라고 불리는 "always false" 명제로 나타나며, "falsum"은 "falsum"을 나타낸다.결과가 거짓이므로 선행 요소 중 적어도 하나는 거짓이어야 합니다.예를₁ 들어, 'A₂, A means '는 선행 요소₁ A와₂ A 중 적어도 하나가 거짓이어야 한다는 것을 의미합니다.

오른쪽의 분리 의미론 때문에 대칭을 다시 볼 수 있다.왼쪽이 비어 있으면 오른쪽 명제가 하나 이상 참이어야 합니다.오른쪽이 비어 있으면 왼쪽 명제 중 하나 이상이 거짓이어야 합니다.

이중 극단 대소문자 ' , '은 수식의 선행 리스트와 후속 리스트가 모두 비어 있는 경우 "만족할 ^[3]수 없다".이 경우 시퀀스의 의미는 사실상 '어느 정도'입니다.이것은 분명히 유효할 수 없는 연속적인 '어느 정도'와 같습니다.

예

논리식 α 및 β에 대해 βα, β 형식의 시퀀스는 α가 참 또는 β가 참(또는 둘 다)임을 의미한다.그러나 α가 동질성이거나 β가 동질성이라는 뜻은 아니다.이것을 명확하게 하기 위해서, 「B」 「A」 「C」 「A」의 예를 검토해 주세요.이것은 유효한 시퀀스입니다.B 'A'가 true 또는 C ' 'A'가 true이기 때문입니다.그러나 이 두 표현 모두 고립된 동어법이 아니다.이 두 표현의 분리는 동어법이다.

마찬가지로 논리식 α 및 β에 대해 α, β δ 형식의 시퀀스는 α가 거짓 또는 β가 거짓임을 의미한다.그러나 α가 모순이거나 β가 모순이라는 뜻은 아니다.이것을 명확하게 하기 위해서, 「B」A, 「C」의 예를 검토해 주세요.이것은 유효한 시퀀스입니다.B 'A'가 false 또는 C ' 'A'가 false이기 때문입니다.그러나 이 두 표현 모두 고립된 모순은 아니다.그것은 모순인 이 두 표현의 결합이다.

규칙.

대부분의 증명 시스템은 하나의 시퀀스를 다른 시퀀스에서 추론하는 방법을 제공합니다.이러한 추론 규칙은 한 줄 위와 아래에 시퀀스의 목록을 사용하여 작성됩니다.이 규칙은 회선 위의 모든 것이 참이면 회선 아래의 모든 것도 참임을 나타냅니다.

일반적인 규칙은 다음과 같습니다.

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

이는${\displaystyle \alpha }$,$α$, \$Displaystyle \$Gamma,$$$\alpha$가$\delta {\displaystyle \mathrm{}}$,$$\$Displaystyle \$$Sigma$가 α$,$ \$Displaystyle$$\Gamma$가$$$\alpha {\displaystyle \mathrm{}}$,$$\$Displaystyle$\Gamma가$$$\delta 임$을 추론할 수 있음을 $나타냅니다$.uent 미적분 추론 규칙).

해석

순차적 어설션의 의미

시퀀스의 어설션 기호는 원래 암시 연산자와 정확히 같은 의미였습니다.그러나 시간이 흐르면서, 그 의미는 모든 모델에서 의미적 진실보다는 이론 내에서 입증 가능성을 나타내는 것으로 바뀌었다.

1934년, 겐첸은 증명 가능성을 나타내기 위해 어설션 기호 ' ' '을 순차적으로 정의하지 않았다.그는 그것은 정확하게 의미는 연산자의 ⇒과 같다는 의미로 '., Bν은,과 관련하여 콘텐츠, 그 공식(A1및과 동일하게'⊢'와 '⇒의 대신의 ⊃'그가:"당연한 A1,..., Aμ → B1,...을 썼다 대신에 '→'를 사용하여 정의했다...&Aμ)⊃(B1∨...∨ Bν)".[4](Gentzen은 선조들과 consequen 사이의right-arrow 상징을 채용했다.시퀀스의 ts.그는 논리적인 암시 연산자로 기호 ' ) '을 사용했다.)

1939년 힐버트와 버네이스는 마찬가지로 시퀀스가 대응하는 함축 ^[5]공식과 같은 의미를 갖는다고 말했다.

1944년, 알론조 교회는 겐젠의 순차적 주장이 입증 가능성을 의미하지 않는다고 강조했다.

「단, 연역 정리를 원시 룰 또는 파생 룰로서 채용하는 것은, 겐젠의 Sequenzen의 사용과 혼동해서는 안 된다.Gentzen의 화살표 →는 우리의 구문 표기법인 ,와 비교할 수 없지만, 그의 목적어에 속한다(그것을 포함한 표현들이 그의 추론 규칙 적용에서 전제 및 결론으로 나타나는 것을 보면 명백하다).^[6]

이 시기 이후의 수많은 출판물들은 시퀀스의 어설션 기호가 시퀀스가 공식화된 이론 내에서 입증 가능성을 나타낸다고 언급하고 있다.1963년의 ^[7]카레, 1965년의 ^[2]렘몬, 2004년의^[8] 허스와 라이언은 모두 순차적인 주장 기호가 입증 가능성을 의미한다고 말한다.그러나 Ben-Ari(2012, 페이지 69)는 Gentzen 시스템 시퀀스의 어설션 기호는 그가 ' ''로 나타내는 것은 메타 ^[9]언어가 아니라 객체 언어의 일부라고 기술하고 있다.

Prawitz(1965)에 따르면, "순차 계산은 자연 연산의 ^[10]대응하는 시스템에서 추론 관계에 대한 메타 계산으로 이해될 수 있다."게다가 「시퀀스 미적분에서의 증명은, 대응하는 자연 ^[11]연산을 구성하는 방법에 관한 지시로서 생각할 수 있다」라고 한다.즉, 어설션 심볼은 메타 계산의 일종인 시퀀셜 미적분 대상 언어의 일부이지만 동시에 기초 자연 연역 체계에서의 추론성을 나타낸다.

직관적인 의미

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 관련 토론은 토크 페이지에서 확인할 수 있습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2014년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

시퀀트는 공제를 위해 계산을 지정할 때 자주 사용되는 공식화된 입증 가능성 진술서입니다.시퀀셜 미적분에서는 특정 종류의 판단으로 간주할 수 있는 이 연역시스템에 특징적인 구조에 대해 시퀀셜이라는 명칭을 사용한다.

순차 $\gamma {\displaystyle \mathrm{}}$ $⊢$ $display$ \ $displaystyle$ \$Gamma$ \$vdash$ \ Sigma $}$의 직관적인 의미는 γ의 가정 하에서 σ의 결론이 입증 가능하다는 것이다.전형적으로 개찰구 왼쪽에 있는 공식은 결합적으로 해석될 수 있고 오른쪽에 있는 공식은 분리로 간주될 수 있다.즉, δ의 모든 공식이 유지되면 δ의 공식도 적어도 1개가 참이어야 합니다.If the succedent is empty, this is interpreted as falsity, i.e. ${\displaystyle \Gamma \vdash }$ means that Γ proves falsity and is thus inconsistent.한편, 빈 선행어는 참이라고 가정합니다.즉,$\display\vdash$\Sigma $}$는 아무런 전제 없이 δ가 이어지는 것을 의미합니다. 즉, 항상 참입니다(분리로서).δ가 비어 있는 이 형식의 시퀀스는 논리 어설션이라고 불립니다.

물론 다른 직관적인 설명도 가능하지만, 이는 고전적으로 동등하다.For example, ${\displaystyle \Gamma \vdash \Sigma }$ can be read as asserting that it cannot be the case that every formula in Γ is true and every formula in Σ is false (this is related to the double-negation interpretations of classical intuitionistic logic, such as Glivenko's theorem).

어떤 경우든, 이러한 직관적인 읽기는 교육학적일 뿐이다.증명 이론에서 형식적인 증명은 순전히 구문론이기 때문에, 시퀀스의 의미는 실제 추론 규칙을 제공하는 미적분의 특성에 의해서만 주어진다.

상기의 기술적으로 정확한 정의의 모순을 배제하고, 도입 논리 형식으로 시퀀스를 기술할 수 있습니다.$γ$( $displaystyle$ \$$Gamma$$ )는 논리 프로세스를 시작하는 일련의 가정을 나타냅니다. 예를 들어 "Socrates is a man", "All man are filotal" 등입니다.$(\displaystyle$\Sigma$)$는 이러한 전제 하에 이어지는 논리적 결론을 나타냅니다$$.예를 들어, "Socrates is filotal"은 상기 사항을 합리적으로 공식화한 후에 이루어지며, 개찰구의$${\(\$displaystyle\Sigma)$ 쪽에서 확인할$$ 수 있습니다.그런 의미에서 ${\(\displaystyle\vdash)$은 영어로 추론하는 과정, 즉 "따라서"를 의미합니다.

바리에이션

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2014년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

여기서 소개하는 시퀀트의 일반적인 개념은 다양한 방법으로 전문화될 수 있다.수열은 수용체에 공식이 최대 1개 있을 경우 직관적 수열이라고 한다(단, 직관적 논리에 대한 다합 계산도 가능하다).더 정확히는, 일반 시퀀스와 동일한 추론 규칙을 가진, 일반 시퀀스의 단수 공식 시퀀스에 대한 제한은 직관적인 시퀀셜 미적분을 구성한다.(이 제한적 시퀀셜 미적분은 LJ로 표기됩니다.)

마찬가지로, 시퀀스가 선행에서 특이하도록 요구함으로써 이중직관논리(패러시스턴스존재논리의 일종)에 대한 계산을 얻을 수 있다.

많은 경우 시퀀스는 시퀀스 대신 멀티셋 또는 세트로 구성된다고 가정한다.따라서 공식의 순서나 발생 횟수조차 무시한다.고전 명제 논리의 경우, 전제 집합에서 도출할 수 있는 결론은 이러한 데이터에 의존하지 않기 때문에, 이것은 문제를 일으키지 않는다.그러나 하위구조 논리에서는 이것이 상당히 중요해질 수 있다.

자연 연역 시스템은 단일 결과 조건부 주장을 사용하지만, 일반적으로 1934년에 도입된 Gentzen과 동일한 추론 규칙 집합을 사용하지 않는다.특히 명제 미적분과 술어 미적분의 실용적인 정리 증명에 매우 편리한 표 형식의 자연 감점 시스템은 Suppes(1957) harvts 오류에 의해 적용되었다: 교과서에서 입문 논리를 가르칠 대상은 CITREFSuppes1957(도움말)와 Lemmon(1965)이었다.

어원학

역사적으로, 게르하르트 젠젠은 그의 유명한 순차 ^[12]미적분을 명시하기 위해 순차들을 도입해왔다.그의 독일어 출판물에서 그는 "세켄츠"라는 단어를 사용했다.하지만 영어에서 시퀀스라는 단어는 이미 독일어 Folge의 번역어로 사용되고 있고 수학에서도 꽤 자주 등장한다.그 후 "sequent"라는 용어는 독일어 표현의 대체 번역을 찾기 위해 만들어졌다.

클린은^[13] 영어로 번역한 것에 대해 다음과 같은 코멘트를 한다: "젠젠은 우리가 '시켄츠'라고 번역한다. 왜냐하면 우리는 이미 어떤 사물의 연속에도 '시퀀스'를 사용해왔기 때문이다. 여기서 독일어는 '폴지'이다."

「 」를 참조해 주세요.

• 게르하르트 겐첸
• 직관적 논리
• 자연공제
• 시퀀트 미적분

메모들

레퍼런스

• Ben-Ari, Mordechai (2012) [1993]. Mathematical logic for computer science. London: Springer. ISBN 978-1-4471-4128-0.
• Church, Alonzo (1996) [1944]. Introduction to mathematical logic. Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02906-1.
• Curry, Haskell Brooks (1977) [1963]. Foundations of mathematical logic. 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 (Second ed.). Berlin, New York: Springer-Verlag. ISBN 978-3-642-86897-9.
• Huth, Michael; Ryan, Mark (2004). Logic in Computer Science (Second ed.). Cambridge, United Kingdom: Cambridge University Press. ISBN 978-0-521-54310-1.
• Kleene, Stephen Cole (2009) [1952]. Introduction to metamathematics. Ishi Press International. ISBN 978-0-923891-57-2.
• Kleene, Stephen Cole (2002) [1967]. Mathematical logic. Mineola, New York: Dover Publications. ISBN 978-0-486-42533-7.
• Lemmon, Edward John (1965). Beginning logic. Thomas Nelson. ISBN 0-17-712040-1.
• Prawitz, Dag (2006) [1965]. Natural deduction: A proof-theoretical study. Mineola, New York: Dover Publications. ISBN 978-0-486-44655-4.
• Smullyan, Raymond Merrill (1995) [1968]. First-order logic. New York: Dover Publications. ISBN 978-0-486-68370-6.
• Suppes, Patrick Colonel (1999) [1957]. Introduction to logic. Mineola, New York: Dover Publications. ISBN 978-0-486-40687-9.
• Takeuti, Gaisi (2013) [1975]. Proof theory (Second ed.). Mineola, New York: Dover Publications. ISBN 978-0-486-49073-1.

외부 링크

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