2차 논리

논리학과 수학에서 2차 논리는 1차 논리의 확장이며, 그 자체가 명제 ^[1]논리의 확장이다.2차 논리는 고차 논리와 유형 이론으로 확장된다.

1차 논리는 개인(담화 영역의 요소) 위에 있는 변수만 수량화하고, 2차 논리는 관계 위에 수량화한다.예를 들어 두 번째 문장 ${\displaystyle P}{\displaystyle \mathrm{}\mathrm{xx}}$( ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle \vee \mathrm{}P}$x )$display$ 、 \ display style \$forall$ P , \$forall$x ( $Px \lor$ \$neg$ Px $)$는 모든 식 P에 대해 Px가 true 또는 not (Px)임을 나타냅니다.2차 로직에는 집합, 함수 및 기타 변수에 대한 정량화도 포함됩니다(아래 섹션 참조).1차 논리 및 2차 논리 모두 담화 영역의 개념을 사용한다(종 단순히 "도메인" 또는 "우주"라고 불린다)도메인은 개별 요소를 수량화할 수 있는 집합입니다.

예

1차 논리는 개인을 계량화할 수 있지만 속성을 계량화할 수는 없습니다.즉, Cube(b)와 같은 원자문을 사용하여 이름을 변수로 대체하고 수량자를 붙이면 수량화된 문장을 얻을 ^[2]수 있습니다.

§ x 큐브(x)

그러나 우리는 술어에 대해 같은 것을 할 수 없다.즉, 다음과 같은 표현입니다.

§ P P(b)

1차 논리의 문장은 아니지만 2차 논리의 정당한 문장입니다.여기서 P는 술어 변수이며 의미론적으로는 개인의 ^[2]집합이다.

그 결과 2차 논리는 1차 논리보다 표현력이 크다.예를 들어, 1차 논리에서는 모든 큐브와 4면체의 집합을 식별할 수 있는 방법은 없습니다.그러나 이 집합의 존재는 2차 논리에서 다음과 같이 주장될 수 있다.

δP(θx (Px ↔ (큐브(x) tet Tet(x)))).

그런 다음 이 집합의 속성을 주장할 수 있습니다.예를 들어, 다음은 모든 큐브와 사면체 집합이 12면체를 포함하지 않는다고 합니다.

∀ P （ x Px ↔ ( Cube ( x )) Tet ( x ) ) → ¬ x x x x Dodec ( x ) 。

2차 정량화는 도달 가능성 특성을 표현할 수 있는 기능을 제공하기 때문에 특히 유용합니다.예를 들어 부모(x, y)가 x가 y의 부모임을 나타내는 경우 1차 논리는 x가 y의 상위라는 속성을 표현할 수 없습니다.2차 논리에서는 부모 관계에서 y와 closed를 포함하는 모든 집합이 x:를 포함한다고 표현합니다.

py P Py ∀ ( a a b b Pb parent parent （ a 、 b ） → Pa ) → Px 。

2차 논리에는 술어 변수가 있지만 술어 속성에는 변수가 없습니다.예를 들어, 술어 P Cube, Tet 및 Dodec에 참인 Shape(P) 속성이 있다고 말할 수 없습니다.여기에는 ^[3]3차 논리가 필요합니다.

구문 및 단편

2차 로직의 구문은 어떤 식이 적절한 공식인지 알려줍니다.2차 로직에는 1차 로직의 구문 외에도 많은 새로운 변수 정렬(종류라고도 함)이 포함됩니다.다음과 같습니다.

• 여러 개인에 걸쳐 있는 일종의 변수입니다.S가 이런 종류의 변수이고 t가 1차 항일 경우 식 t s S(S(t) 또는 괄호를 저장하기 위한 St)는 원자식이 됩니다.개인 집합은 도메인에서 단항 관계로도 볼 수 있습니다.
• 각 자연수 k에 대해 개인에 대한 모든 k-ary 관계에 걸쳐 있는 일종의 변수가 있습니다.만약 R이 k-ary 관계 변수이고₁ t_k,…,t가 1차 항이라면, 식₁ R(t_k,…t)은 원자식이다.
• 각 자연수 k에 대해 도메인의 k개의 요소를 취하고 도메인의 단일 요소를 반환하는 모든 함수에 걸쳐 있는 일종의 변수가 있습니다.f가 k-ary 함수 변수이고 t₁,…,t가_k 1차 항이면 식 f₁(t_k,…t)는 1차 항이다.

방금 정의한 변수 각각은 공식을 구축하기 위해 보편적으로 또는 존재적으로 수량화할 수 있습니다.따라서 각 종류의 변수마다 두 가지씩 많은 종류의 수량화자가 있습니다.2차 논리에서의 문장은 1차 논리에서의 문장과 마찬가지로 (어떤 종류의) 자유 변수도 없는 잘 형성된 공식입니다.

n-ary 함수 변수는 arity n+1의 관계 변수와 관계의 n+1 인수의 "결과"의 고유성에 대한 적절한 공식으로 나타낼 수 있기 때문에 위에 주어진 정의에 함수 변수의 도입을 포기하는 것이 가능하다(그리고 일부 저자는 이것을 한다).(Shapiro 2000, 페이지 63)

모나딕 2차 논리(MSO)는 단항 관계(즉, 집합)에 대한 양자화만 허용되는 2차 로직의 제한입니다.따라서 위에서 설명한 관계와 동등하기 때문에 함수에 대한 정량화도 허용되지 않는다.이러한 제한이 없는 2차 로직은 모나드 버전과 구별하기 위해 완전한 2차 로직이라고 불리기도 합니다.모노딕 2차 논리는 특히 그래프 이론의 알고리즘 메타 이론인 쿠셀의 정리 맥락에서 사용됩니다.

1차 로직과 마찬가지로 2차 로직에도 특정 2차 언어로 논리가 아닌 기호가 포함될 수 있습니다.단, 이들 항은 모두 1차 항(1차 변수를 대체할 수 있음) 또는 2차 항(1차 변수를 대체할 수 있음)이어야 한다는 점에서 제한됩니다.

2차 로직의 공식은 1차(및 ${\displaystyle {\delta \mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 1$(\$ $\$$Sigma$ _${0}^1$$})$ $또는{\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$0 1(\$displaystyle$ \$Pi _{0}^$1$\})$이라고 불리며, 그 수량자(범용 또는 존재 가능)가 1차 변수만을 넘는 경우도 있지만, 2차 로직은 자유 변수일 수 있다.${\displaystyle {display\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$\ $display$$style$ \ $Sigma$_ { $1$}^{ $1$} (기존의 2차) 공식은${\displaystyle \mathrm{}{2차\mathrm{}}_{}}$ 변수 위에 존재하는 수식(R${\displaystyle {}_{}}$0 …${\displaystyle \mathrm{}{}_{}}$ R m$$${\$ \ $display$style \$exists R_ { m$ \ $phi$ $)$을 갖는 공식입니다$.$기존의 2차 공식으로만 구성된 2차 로직의 fragment는 존재의 2차 로직이라고 불리며 ESO로 단축되어 ${\displaystyle {\mathrm{}}_{}^{}}$\ $style$\$Sigma$_ {$1}^$1$\}$로 단축되어 있으며, SO로도 단축되어 있습니다.${\displaystyle {\delta \mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$1 \ $displaystyle$\ $Pi$_ {$1}^1$} 공식의$$ fragment는 이중으로 정의되어 있습니다.이것은 범용 2차 로직이라고 불립니다.더 표현적인 조각들이 어떤 k>0을 위한 상호 반복에 의해:∃ R0…∃ Rmϕ{\displaystyle \exists R_{0}\ldots R_{m}\phi \exists이ϕ{\displaystyle \phi}은Π k1{\displaystyle \Pi_{k}^{1}}공식, 그리고 similar, Σ k+11{\displaystyle \Sigma_{k+1}^{1}}}, 그 양식이 정의되어 있다. ${\displaystyle {\mathrm{\pi }}_{\mathrm{}}^{}}$+ 1 {$display$ style \ $Pi$_ { $k$+ $1$}^{1} ${\displaystyle {has}_{}}$ R 0 ${\displaystyle \mathrm{...}}$ $r$ R m$${\ { $display$ style \ $forall R_${ 0 } $\ldots$ \ $forall R_${ m } \ phi$$}${\displaystyle \mathrm{}}$$where{\displaystyle }$ $。$서$$${\$ \ $displaystyle$\ phi$$ ${\displaystyle a_{}^{}}$ {\$1$ \ k _ s _$syle${ \ \ \ \ \ \ \ \ \ {\ {\ {\ {\ {\ {\ _ {\ {\ {\1 \ 。

의미론

2차 논리의 의미론은 각 문장의 의미를 정한다.1차 논리(표준 의미론)와 달리 2차 논리에는 표준 의미론과 헨킨 의미론이라는 두 가지 다른 의미론이 일반적으로 사용됩니다.이들 각 시멘틱스에서 1차 수량화자와 논리접속자의 해석은 1차 로직과 동일하다.2차 변수에 대한 수량화 범위만이 두 가지 유형의 의미론에서 다르다(Vénénen 2001).

전체 의미론이라고도 불리는 표준 의미론에서 수량자는 적절한 정렬의 모든 집합 또는 함수에 걸쳐 있습니다.따라서 1차 변수의 도메인이 확립되면 나머지 수량자의 의미는 고정됩니다.2차 논리에 표현력을 부여하는 것은 이러한 의미론이며, 이 문서의 나머지 부분에서는 이러한 의미를 가정할 것이다.

Leon Henkin(1950)은 2차 및 고차 이론에 대한 대체 의미론의 종류를 정의했다. 여기서 고차 도메인의 의미는 집합 또는 함수의 특성에 대한 명시적 공리화, 유형 이론에 따라 부분적으로 결정된다.헨킨 시멘틱스는 표준 시멘틱스에서처럼 표준 모델에만 고정되는 대신 공리의 모델 클래스가 있는 다단계 1차 시멘틱스의 일종이다.Henkin semantics의 모델은 일련의 집합 또는 함수 집합을 고차 도메인의 해석으로 제공할 것이며, 이것은 그러한 종류의 모든 집합 또는 함수의 적절한 하위 집합일 수 있습니다.그의 공리화를 위해 헨킨은 1차 논리를 유지하는 괴델의 완전성 정리와 콤팩트성 정리가 헨킨의 의미론과 함께 2차 논리로 계승된다는 것을 증명했다.스콜렘도...Löwenheim 이론들은 Henkin semetics를 유지하며, Lindström의 정리는 Henkin 모델이 단지 위장한 1차 ^[4]모델이라는 것을 가져온다.

2차 산술과 같은 이론에서 고차 영역의 비표준 해석의 존재는 헨킨이 사용한 유형 이론에서 파생된 특정 공리화의 결핍일 뿐만 아니라 괴델의 불완전성 정리의 필연적인 결과이다.헨킨의 공리는 표준 해석이 유일한 가능한 모델임을 확실히 하기 위해 더 이상 보충될 수 없다.헨킨 의미론은 2차 산술 연구에 일반적으로 사용된다.

Jouko Vänénen(2001)은 2차 논리에 대한 헨킨 모델과 풀 모델 사이의 선택은 집합론의 기초로서 ZFC와 V 사이의 선택과 유사하다고 주장했다: "2차 논리와 마찬가지로, 우리는 V 또는 ZFC를 사용하여 수학을 공리화할지 선택할 수 없다.ZFC는 수학의 공리화로 V를 사용하는 지금까지의 시도 중 가장 좋은 시도이기 때문에 결과는 두 경우 모두 동일합니다.

표현력

2차 논리는 1차 논리에 비해 표현력이 높다.예를 들어, 만약 도메인이 모든 실수의 집합이라면, 1차 논리에서 각 실수의 덧셈 역(x + y = 0)의 존재를 주장할 수 있지만, 실수의 집합에 대한 최소 상한 속성을 주장하기 위해 2차 논리가 필요하다. 즉, 모든 유계, 비어 있지 않은 실수의 집합이 다음을 갖는다는 것이다.슈프림도메인이 모든 실수의 집합인 경우 다음 2차 문장은 최소 상한 속성을 나타냅니다.

(그림 A)([(그림 W)(w a A)(그림 A)(그림 A → u ≤ z)])

: → ( x A → w x x ) [ ( a A → w x x ) ][ ( ( A → u y y ] → x y y )

이 공식은 "모든 비어 있지 않은 경계 집합 A는 최소 상한을 가진다"를 직접 공식화한 것입니다.이 속성을 만족시키는 순서 필드는 모두 실수 필드와 동형임을 알 수 있습니다.한편, 실수에 유효한 1차 문장의 집합은 콤팩트성 정리에 의해 임의로 큰 모델을 가진다.따라서 최소 상한 속성은 1차 논리에서는 어떤 문장 집합으로도 표현할 수 없습니다.(실제로 모든 닫힘 필드는 시그니처${\displaystyle +,}$),$$)(\$displaystyle \langle +,\cdot,\leq \rangle }$의 1차 문장을 실수와 동일하게 만족시킵니다).

2차 논리에서는 "도메인은 유한하다" 또는 "도메인은 계산 가능한 카디널리티의 도메인이다"라고 하는 형식적인 문장을 쓸 수 있다.도메인이 유한하다고 하기 위해서는 도메인에서 그 자체로 이어지는 모든 피사적 함수가 주입적이라는 문장을 사용합니다.도메인에 계산 가능한 카디널리티가 있다고 하려면 도메인의 무한 서브셋 2개마다 바이젝션이 있음을 나타내는 문장을 사용합니다.콤팩트성 정리 및 상향 뢰벤하임-스콜렘 정리로부터 각각 1차 논리에서 미세성 또는 계수성을 특징짓는 것은 불가능하다.

ESO와 같은 2차 로직의 특정 fragment는 완전한 2차 로직보다 표현력이 엄격히 떨어지지만 1차 로직보다 표현력이 더 높습니다.ESO는 또한 Henkin 양자화자에 의해 확장된 1차 논리, Hintikka와 Sandu의 독립 친화적 논리, Vénénen의 의존성 논리 등 수량화 종속성의 비선형 순서를 허용하는 일부 1차 논리와의 변환 등가성을 즐긴다.

연역법

논리연역체계는 어떤 공식의 시퀀스가 유효한 증거를 구성하는지를 결정하는 추론 규칙과 논리 공리의 집합이다.표준 의미론에는 완전할 수 없지만, 2차 논리에는 여러 연역 시스템을 사용할 수 있습니다(아래 참조).이 시스템들 각각은 건전하며, 이것은 그들이 증명하기 위해 사용될 수 있는 모든 문장이 적절한 의미론에서 논리적으로 유효하다는 것을 의미한다.

사용할 수 있는 가장 약한 연역 체계는 2차 ^[5]항 대체 규칙으로 보강된 1차 논리(자연 공제 등)의 표준 연역 체계로 구성된다.이 연역 체계는 2차 산술 연구에 일반적으로 사용된다.

샤피로(1991)와 헨킨(1950)에 의해 고려된 연역 시스템은 이해 공리와 선택 공리를 모두 증강된 1차 연역 체계에 추가된다.이러한 공리는 표준 2차 의미론에 적합합니다.그것들은 이해와 선택 ^[6]공리를 만족시키는 헨킨 모델로 제한된 헨킨 의미론에 적합하다.

1차 논리에 대한 환원 불가

실수의 2차 이론을 완전한 2차 의미론과 함께 다음과 같은 방법으로 1차 이론으로 축소하려고 시도할 수 있다.먼저 도메인을 모든 실수의 집합에서2개의 정렬 도메인으로 확장합니다.두 번째 정렬에는 모든 실수의 집합이 포함됩니다.언어에 새 이진 술어인 구성원 관계를 추가합니다.그 후, 2차였던 문장은 1차, 이전의 2차 수량자는 2차 소트까지가 됩니다.이 감소는 원소가 숫자인지 집합인지를 알려주는 단항 술어를 추가하고, 도메인을 실수 집합과 실수들의 거듭제곱 집합의 결합으로 함으로써 원 정렬 이론에서 시도될 수 있다.

그러나 도메인이 모든 실수의 집합을 포함하도록 단언된 점에 유의하십시오.그 요건은 뢰벤하임-스콜렘 정리가 보여주듯이 1차 문장으로 환원될 수 없다.그 정리는 우리가 내부번호라고 부르는 실수의 무한 부분집합과 우리가 "내부 집합"이라고 부르는 실수의 무한 집합이 있다는 것을 의미하며, 그래서 내부번호와 내부집합으로 구성된 도메인이 정확히 같은 첫 번째 또는 첫 번째를 만족한다.실수의 영역과 실수의 집합으로 만족되는 문장을 말합니다.특히 다음과 같은 최소 상한 공리를 충족합니다.

모든 내부 번호 집합의 계수 가능성(이 집합이 조밀하게 정렬된 집합을 형성한다는 사실과 함께)은 해당 집합이 완전한 최소 상한 공리를 충족하지 않음을 의미합니다.모든 내부 집합의 집합의 계수성은 모든 내부 수 집합의 모든 부분 집합의 집합이 아니라는 것을 의미한다(칸토어의 정리는 셀 수 없을 정도로 무한한 집합의 집합이 셀 수 없을 정도로 무한하다는 것을 의미하기 때문이다).이 구성은 스콜렘의 역설과 밀접한 관련이 있다.

따라서 실수의 1차 이론과 실수의 집합은 셀 수 있는 많은 모델을 가지고 있다.그러나 2차 실수의 이론은 하나의 모형만을 가지고 있다.이것은 아르키메데스식 완전 순서장의 모든 공리가 2차 논리로 표현 가능하다는 사실과 함께 오직 하나의 아르키메데스식 완전 순서장이 있다는 고전적인 정리로부터 따라옵니다.이것은 실수의 2차 이론은 1개의 모델만을 가지고 있지만, 대응하는 1차 이론은 많은 모델을 가지고 있다는 점에서 실수의 2차 이론은 1차 이론으로 환원될 수 없다는 것을 보여준다.

표준 의미론을 가진 2차 논리가 1차 논리보다 더 표현적이라는 것을 보여주는 더 극단적인 예가 있습니다.연속체 가설이 성립하면 실수가 유일한 모델이고 연속체 가설이 성립하지 않으면 모델이 없는 유한 2차 이론이 있다.Shapiro 2000, 페이지 105).이 이론은 실수를 완전한 아르키메데스 순서 장으로 특징짓는 유한 이론과 도메인이 최초의 셀 수 없는 카디널리티라는 공리로 구성되어 있습니다.이 예는 2차 논리의 문장이 일관성이 있는지에 대한 질문이 매우 미묘하다는 것을 보여준다.

2차 로직의 추가 제한은 다음 섹션에서 설명합니다.

금속학적 결과

이 세 가지 바람직한 ^[7]속성을 동시에 만족시키는 2차 공식에 연역적 시스템(즉, 증명가능성의 개념 없음)이 없다는 것은 괴델의 불완전성 정리의 결과이다.

• (음향성) 모든 입증 가능한 2차 문장은 보편적으로 유효하다. 즉, 표준 의미론 하에서 모든 영역에서 참이다.
• (완전성) 표준 시멘틱스 하에서는 보편적으로 유효한 모든 2차 공식은 증명 가능합니다.
• (효과)주어진 일련의 기호가 증명인지 아닌지를 정확하게 판단할 수 있는 증명 검사 알고리즘이 있습니다.

이 결과는 때때로 2차 논리가 완전한 증명 이론을 인정하지 않는다는 말로 표현된다.이 점에서 표준 의미론을 가진 2차 논리는 1차 논리와 다르다. Quine(1970, 페이지 90–91)은 2차 논리를 논리가 아닌 것으로 생각하는 이유로 완전한 입증 시스템의 부족을 지적했다.

앞서 언급했듯이 헨킨은 1차 논리에 대한 표준 연역 체계가 헨킨 의미론에서 2차 논리에 대해 건전하고 완전하며 효과적이며, 이해와 선택 원리를 가진 연역 체계가 헨킨 의미론에서 이러한 원리를 충족하는 모델만을 사용하여 건전하고 완전하며 효과적이라는 것을 증명했다.

콤팩트성 정리 및 뢰벤하임-스콜렘 정리는 2차 논리의 전체 모델에 적용되지 않는다.Henkin ^{[8]: xi} 모델에는 해당됩니다.

역사와 논쟁의 가치

술어 논리는 C에 의해 수학계에 도입되었다. S. Peirce, 2차 논리라는 용어를 만들고 그 표기가 현대 형식과 가장 유사합니다(Putnam 1982).그러나 오늘날 대부분의 논리학과 학생들은 피어스보다 몇 년 전에 그의 작품을 출판했지만 버트런드 러셀과 알프레드 노스 화이트헤드가 그것들을 유명하게 만들기 전까지 그의 작품은 덜 알려져 있었다.프레게는 물체에 대한 계량화와 성질과 집합에 대한 계량화를 구별하기 위해 다른 변수를 사용했지만, 그는 자신이 두 가지 다른 종류의 논리를 한다고 생각하지 않았습니다.러셀의 역설의 발견 후에 그의 시스템에 뭔가 문제가 있다는 것을 깨달았다.결국 논리학자들은 Frege의 논리를 다양한 방식으로 제한함으로써 (현재는 1차 논리라고 불리는 것으로) 집합과 속성을 1차 논리만으로 수량화할 수 없다는 것을 발견했다.현재 표준화된 로직 순서 계층은 이때부터 시작됩니다.

집합론은 1차 논리 체계 내에서 공리화된 체계로 공식화될 수 있다는 것이 밝혀졌고 (여러 종류의 완전성을 희생하지만 러셀의 역설만큼 나쁜 것은 없다), 집합이 수학에 필수적이기 때문에 이것이 이루어졌다(저멜로-프랭켈 집합론 참조)산술, 단순학, 그리고 다른 강력한 논리 이론은 1차 수량화보다 더 논리적인 장치에 호소하지 않고 공리적으로 공식화할 수 있었고, 이것은 괴델과 스콜렘의 1차 논리 집착과 함께 2차 ^{[citation needed]}논리에서의 일반적인 작업 감소를 초래했다.

이 거절은 일부 논리학자, 특히 W. V. Quine에 의해 적극적으로 추진되었다.콰인은 Fx 같은 predicate-language 문장에서")"의 변수나 이름 개체를 나타내는으로 생각되기에이며, 따라서"모든 것들을 위해서, 그것이 사실이라고 하는."에 보고 있지만"F"의 불완전한 문장의 생략형이 아니라, 개체의 이름으로 생각되기에(e. 건 아니죠 양을 정할 수 있는 view[표창 필요한]고급한abstr의 ven물건처럼 행동하다).예를 들어, "...는 개입니다."를 의미할 수 있습니다.하지만 우리가 이런 것을 계량화할 수 있다고 생각하는 것은 말이 되지 않는다.(이러한 입장은 개념-객체 구분에 관한 프레지 자신의 주장과 상당히 일치한다.)따라서 술어를 변수로 사용하는 것은 개별 변수만이 점유해야 하는 이름 대신 술어가 점유되도록 하는 것입니다.이 논리는 조지 불로스에 ^{[citation needed]}의해 거부되었다.

최근^[when?] 몇 년 동안 2차 로직은 1차 로직과 동일한 범위의 물체에 대한 2차 로직의 복수 양으로서 해석함으로써 약간의 회복을 가져왔다(Boolos 1984).Boolos는 또한 "몇몇 비평가들은 서로 존경한다" "Fianchetto의 부하들 중 일부는 다른 사람과 동행하지 않고 창고에 들어갔다"와 같은 주장된 문장의 비순위성을 지적하는데, 그는 이것이 오직 2차 수량화의 완전한 힘에 의해서만 표현될 수 있다고 주장한다.단, 일반화된 정량화와 부분적으로 순서가 매겨진(또는 분기) 정량화는 1순서가 아닌 것으로 알려진 특정 종류의 문장도 표현하기에 충분할 수 있으며, 이것들은 2차 정량화에 어필하지 않는다.

계산 복잡도와의 관계

유한 구조에서 다양한 형태의 2차 논리의 표현력은 계산 복잡성 이론과 밀접하게 연관되어 있다.계산 복잡도 클래스가 기술 복잡도 연구 분야는 언어(유한 문자열 집합)를 표현하기 위해 필요한 논리의 힘으로 특징지을 수 있다.도메인 D){1,...,n}과 유한한 구조로 표시할 수 있는 유한한 알파벳 w는 문자열)w1···wn 단항의 아버지를 설파하고 있는 ∈ A을 충족하는에 의해 이 지수 나는 명확히 그 wi-1및 추가 predicates는 서브에 고유하게 식별하는 지수는 어떤 IT일반적으로,이 그래프의 후계자 기능에 D나 순서이다. relation <, 다른 산술 술어를 사용할 수 있습니다).반대로 (유한 시그니처에 걸쳐) 유한 구조의 Cayley 테이블은 유한 문자열로 부호화할 수 있습니다.

이 식별은 유한 구조에 대한 2차 논리의 변형을 다음과 같이 특징짓는다.

• REG(정규어 집합)는 단수 2차 공식으로 정의할 수 있다(Büchi의 정리, 1960년)
• NP는 실존적 2차 공식에 의해 정의될 수 있는 언어의 집합이다.
• co-NP는 범용 2차 공식으로 정의할 수 있는 언어 집합입니다.
• PH는 2차 공식으로 정의할 수 있는 언어 집합입니다.
• PSPACE는 추이적 폐쇄 연산자가 추가된 2차 공식으로 정의할 수 있는 언어 집합입니다.
• EXPTIME은 최소 고정점 연산자가 추가된 2차 공식으로 정의할 수 있는 언어 집합입니다.

이러한 클래스 간의 관계는 유한 구조에 대한 로직의 상대적 표현력에 직접적인 영향을 미친다. 예를 들어, PH = PSPACE인 경우, 2차 논리에 전이적 폐쇄 연산자를 추가하는 것은 유한 구조에 대한 로직의 표현을 더 이상 증가시키지 않을 것이다.

「 」를 참조해 주세요.

• 1차 논리
• 고차 논리
• 뢰벤하임 수
• 오메가어
• 2차 명제 논리
• 모노딕 2차 논리

메모들

레퍼런스

• Andrews, Peter (2002). An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd ed.). Kluwer Academic Publishers.
• 1998년Boolos, George (1984). "To Be Is To Be a Value of a Variable (or to Be Some Values of Some Variables)". Journal of Philosophy. 81 (8): 430–50. doi:10.2307/2026308. JSTOR 2026308. Boolos, Logic, Logic and Logic에 전재.
• Henkin, L. (1950). "Completeness in the theory of types". Journal of Symbolic Logic. 15 (2): 81–91. doi:10.2307/2266967. JSTOR 2266967.
• Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
• Harvard University Press, Putnam, Hilary(1990), Harvard University Press, 페이지 252-260에 전재Putnam, Hilary (1982). "Peirce the Logician". Historia Mathematica. 9 (3): 290–301. doi:10.1016/0315-0860(82)90123-9..
• W. V. Quine (1970). Philosophy of Logic. Prentice Hall. ISBN 9780674665637.
• Rossberg, M. (2004). "First-Order Logic, Second-Order Logic, and Completeness" (PDF). In V. Hendricks; et al. (eds.). First-order logic revisited. Berlin: Logos-Verlag.
• Shapiro, S. (2000) [1991]. Foundations without Foundationalism: A Case for Second-Order Logic. Oxford: Clarendon Press. ISBN 0-19-825029-0.
• Väänänen, J. (2001). "Second-Order Logic and Foundations of Mathematics" (PDF). Bulletin of Symbolic Logic. 7 (4): 504–520. CiteSeerX 10.1.1.25.5579. doi:10.2307/2687796. JSTOR 2687796. S2CID 7465054.

추가 정보

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

• Väänänen, Jouko. Edward N. Zalta (ed.). Second-order and Higher-order Logic. The Stanford Encyclopedia of Philosophy (Fall 2021 Edition).