2차 논리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

2차 논리는 1차 논리보다 더 많은 변수 종류를 허용하는 형식 논리 체계이다. 2차 논리는 개체의 집합, 관계, 함수 등을 변수로 사용할 수 있으며, 이러한 변수를 전칭 또는 존재 기호로 양화할 수 있다. 2차 논리는 표준 의미론과 헹킨 의미론의 두 가지 의미론을 가지며, 표준 의미론에서는 양자 기호가 모든 집합 또는 함수를 포함하는 반면, 헹킨 의미론에서는 2차 변수의 범위를 제한한다. 2차 논리는 1차 논리보다 표현력이 풍부하지만, 괴델의 불완전성 정리로 인해 완전한 증명 체계를 가질 수 없으며, 콤팩트성 정리와 뢰벤하임-스콜렘 정리가 성립하지 않는다. 계산 복잡도 이론과 관련하여 2차 논리는 정규 언어, NP, co-NP, PH, PSPACE, EXPTIME 등 다양한 복잡도 클래스를 특징짓는 데 사용된다. 2차 논리에 대한 콰인의 비판과 불로스의 옹호, 헹킨 의미론의 도입은 2차 논리 연구의 중요한 역사적 사건이다.

더 읽어볼만한 페이지

수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

2차 논리
개요
유형	수리 논리학의 한 분야
분야	논리학, 수학, 철학, 컴퓨터 과학
특징
설명	1차 논리에서 허용되지 않는 술어에 대한 양화를 허용하는 논리의 형태이다.
형식적 정의
정의	2차 논리는 1차 논리의 확장으로, 술어 변수와 함수 변수에 대한 양화를 허용한다.
예시
예시	'모든 속성 P에 대해, 만약 0이 P를 가지고 있고, 모든 수 x에 대해 x가 P를 가지면 x + 1도 P를 가진다면, 모든 수 x는 P를 가진다.' (수학적 귀납법의 2차 논리 표현)
의미론 및 완전성
완전성	2차 논리는 1차 논리와 달리 완전성 정리가 성립하지 않는다. 즉, 모든 진리를 증명할 수 있는 공리계가 존재하지 않는다.
표현력
표현력	2차 논리는 1차 논리보다 훨씬 더 강력한 표현력을 가진다. 예를 들어, 자연수의 집합을 정의하거나, 실수의 완비성을 표현할 수 있다.
복잡성
복잡성	2차 논리의 진리값 문제는 매우 복잡하며, 결정 불가능한 경우가 많다.
활용
활용 분야	수학 기초론, 철학 논리학, 컴퓨터 과학 등 다양한 분야에서 활용된다. 특히, 2차 논리는 집합론의 공리계를 형식화하는 데 사용될 수 있다.
관련 개념
관련 개념	1차 논리, 고차 논리, 집합론

2. 정의

2차 논리의 구문은 어떤 표현식이 잘 구성된 논리식인지 알려준다. 1차 논리의 구문 외에도 2차 논리는 많은 새로운 변수 ''종류''(때로는 ''유형''이라고도 함)를 포함한다. 다음과 같다.

개체의 집합을 범위로 하는 변수 종류. ''S''가 이 종류의 변수이고 ''t''가 1차 항이면 표현식 ''t'' ∈ ''S''(또는 ''S''(''t''), 또는 괄호를 생략하기 위해 ''St'')는 원자 논리식이다. 개체의 집합은 또한 영역에 대한 단항 관계로 볼 수 있다.
각 자연수 ''k''에 대해 개체에 대한 모든 ''k''-항 관계를 범위로 하는 변수 종류가 있다. ''R''이 그러한 ''k''-항 관계 변수이고 ''t''₁,...,''t''_''k''가 1차 항이면 표현식 ''R''(''t''₁,...,''t''_''k'')는 원자 논리식이다.
각 자연수 ''k''에 대해 영역의 ''k''개의 요소를 취하여 영역의 단일 요소를 반환하는 모든 함수를 범위로 하는 변수 종류가 있다. ''f''가 그러한 ''k''-항 함수 변수이고 ''t''₁,...,''t''_''k''가 1차 항이면 표현식 ''f''(''t''₁,...,''t''_''k'')는 1차 항이다.

이 변수들은 전체적으로 또는/및 존재적으로 양화될 수 있다. 따라서 변수의 각 종류에 대해 두 개씩 많은 종류의 양화자가 있다. 1차 논리와 마찬가지로 2차 논리의 ''문장''은 (어떤 종류의) 자유 변수가 없는 잘 구성된 논리식이다.

함수 변수는 ''n''-항 함수 변수는 아리티 ''n''+1의 관계 변수와 관계의 ''n''+1 인수에 대한 "결과"의 고유성에 대한 적절한 논리식으로 나타낼 수 있기 때문에 생략 가능하다.^[15]

모나딕 2차 논리(MSO)는 단항 관계(즉, 집합)에 대한 양화만 허용하는 2차 논리의 제한이다. 관계에 대한 등가성으로 인해 함수에 대한 양화도 허용되지 않는다. 이러한 제한이 없는 2차 논리는 모나딕 버전과 구별하기 위해 때때로 ''전체 2차 논리''라고 한다. 모나딕 2차 논리는 특히 그래프 이론의 알고리즘 메타 정리인 쿠르셀 정리의 맥락에서 사용된다.

1차 논리와 마찬가지로 2차 논리는 특정 2차 언어에 비논리 기호를 포함할 수 있다. 그러나 모든 항은 1차 항(1차 변수로 대체될 수 있음) 또는 2차 항(적절한 종류의 2차 변수로 대체될 수 있음)이어야 한다.

2차 논리의 논리식은 양화자가 1차 변수 범위로만 지정되지만 2차 자유 변수를 가질 수 있는 경우 1차(때로는

\Sigma^1_0

또는

\Pi^1_0

으로 표시됨)라고 한다.

2. 1. 문법

2차 논리의 문법은 변수, 논리 기호, 항, 논리식으로 구성된다. 1차 논리와 달리 2차 논리는 변수의 종류가 더 다양하다.

변수:
각 자연수 $n$ 에 대해, $n$ 항 연산 변수 $f_0^n, f_1^n, f_2^n, \dots$ 가 있다.
$n=0$ 일 때, $f_0^0, f_1^0, \dots$ 는 1차 논리의 변수와 같다.
$n>0$ 인 연산 변수는 생략 가능하다.^[15]
각 자연수 $n$ 에 대해, $n$ 항 관계 변수 $R_0^n, R_1^n, R_2^n, \dots$ 가 있다.
$n=1$ 일 때, $R_0^1, R_1^1, \dots$ 는 1차 논리 변수들의 집합과 같다.
논리 기호: ( 1차 논리와 같음)
전칭 기호 $\forall$ 와 존재 기호 $\exists$
등호 $=$
명제 논리 기호 $\land$ (논리곱), $\lor$ (논리합), $\lnot$ (부정) 등
괄호 $()$ 및 반점 $,$ 등
주어진 $n$ 항 연산 $\mathsf f$ 및 $n$ 항 관계 $\mathsf R$ .
예: 집합론의 언어는 하나의 2항 관계 $\in$ 를 갖는다.
예: 순서체의 언어는 2항 연산 $+$ 와 $\cdot$ , 1항 연산 $-$ , 0항 연산 $0$ 과 $1$ , 그리고 2항 관계 $\le$ 를 갖는다.

항:
$n$ 항 연산 변수 $f_i^n$ 과 $n$ 개의 항 $t_1, t_2, \dots, t_n$ 에 대해, $f_i^n(t_1, t_2, \dots, t_n)$ 은 항이다. ( $n=0$ 일 때 $f_i^0()$ 는 $f_i^0$ 로 쓴다.)
$n$ 항 연산 $\mathsf f$ 와 $n$ 개의 항 $t_1, t_2, \dots, t_n$ 에 대해, $\mathsf f(t_1, t_2, \dots, t_n)$ 은 항이다. ( $n=0$ 일 때 $\mathsf f()$ 는 $\mathsf f$ 로 쓴다.)

논리식:
$n$ 항 관계 변수 $R_i^n$ 과 $n$ 개의 항 $t_1, t_2, \dots, t_n$ 에 대해, $R_i^n(t_1, t_2, \dots, t_n)$ 는 논리식이다.
$n$ 항 관계 $\mathsf R$ 와 $n$ 개의 항 $t_1, t_2, \dots, t_n$ 에 대해, $\mathsf R(t_1, t_2, \dots, t_n)$ 는 논리식이다.
두 항 $t_1$ , $t_2$ 에 대해, $t_1=t_2$ 는 논리식이다.
논리식 $\phi$ 와 $\phi$ 에 등장하는 $n$ 항 자유 연산 변수 $f_i^n$ 에 대해, $\forall f_i^n \phi$ 와 $\exists f_i^n \phi$ 는 논리식이다.
논리식 $\phi$ 와 $\phi$ 에 등장하는 $n$ 항 자유 관계 변수 $R_i^n$ 에 대해, $\forall R_i^n \phi$ 와 $\exists R_i^n \phi$ 는 논리식이다.
두 논리식 $\phi$ 와 $\chi$ 에 대해, $\phi \land \chi$ 와 $\phi \lor \chi$ 및 $\phi$ 에 대하여, $\lnot \phi$ 는 논리식이다.
여기서, 논리식 $\phi$ 에 등장하는 연산 변수 또는 관계 변수 $x$ 가 '''자유 변수'''라는 것은 $\phi$ 에 $\forall x$ 나 $\exists x$ 가 포함되지 않는 것을 의미한다.

2차 논리는 1차 논리에 비해 변수의 종류가 다양하여, 변수는 개체 집합, 개체 간 관계, 함수 등을 나타낼 수 있다. 예를 들어, 한국 사회의 가족 관계, 직장 내 위계 관계, 사회적 연결망 등을 2차 논리를 통해 분석할 수 있다.

2. 2. 의미론

2차 논리의 의미론은 흔히 2차 논리의 모형으로 주어진다. 2차 논리에는 일반적으로 사용되는 두 가지 다른 의미론, 즉 '''표준 의미론'''과 '''헹킨 의미론'''(Henkin semantics^영어)이 있다. 1차 논리와 달리, 2차 논리에서는 이 두 가지 의미론이 사용된다. 1차 논리 양자 기호와 논리적 연결사의 해석은 1차 논리와 동일하며, 두 가지 유형의 의미론에서 2차 변수에 대한 양자 기호의 범위만 다르다.^[3]

표준 의미론(전체 의미론이라고도 함)에서 양자 기호는 적절한 종류의 ''모든'' 집합 또는 함수를 포함한다. 이러한 조건을 가진 모델을 전체 모델이라고 하며, 이는 2차 양자 기호의 범위가 모델의 1차 부분의 멱집합인 모델과 동일하다. 따라서 1차 변수의 영역이 설정되면 나머지 양자 기호의 의미가 고정된다. 2차 논리에 표현력을 부여하는 것은 이러한 의미론이다.

레온 헹킨은 2차 및 고차 이론에 대한 대안적 의미론을 정의했는데, 여기서 고차 영역의 의미는 집합 또는 함수의 속성에 대한 명시적인 공리화를 통해 부분적으로 결정된다. 헹킨 의미론은 일종의 다중 정렬 1차 의미론이며, 표준 의미론에서처럼 의미론이 표준 모델로만 고정되는 대신 공리의 모델 클래스가 있다. 헹킨 의미론의 모델은 고차 영역의 해석으로 모든 집합 또는 해당 종류의 함수의 진부분 집합일 수 있는 집합의 집합 또는 함수의 집합을 제공한다. 헹킨은 자신의 공리화를 위해 괴델의 완전성 정리와 콤팩트성 정리가 1차 논리에 적용되는 것처럼 헹킨 의미론을 가진 2차 논리로 옮겨진다는 것을 증명했다. 또한 Skolem–Löwenheim 정리가 헹킨 의미론에 적용되므로 린드스트롬의 정리는 헹킨 모델이 단지 ''위장된 1차 모델''임을 보여준다.^[3] 헹킨 의미론은 2차 산술 연구에 일반적으로 사용된다.

3. 성질

2차 논리의 '''증명 체계'''(proof system^영어)는 변수 및 $=,\forall,\exists,\lor,\land,\lnot$ 만을 포함하는 2차 논리 명제에 대해 증명을 제시하거나 제시하지 않는 함수이다. 증명 체계가 증명을 제시하는 명제를 '''증명 가능 명제'''(provable proposition^영어)라고 하며, 여기서 "증명"이란 일련의 문자열을 뜻한다.

2차 논리에서는 콤팩트성 정리와 뢰벤하임-스콜렘 정리가 성립하지 않으며, 괴델의 불완전성 정리에 따라 특정 조건을 모두 만족하는 증명 체계는 존재하지 않는다. 이러한 성질들은 2차 논리가 표준 의미론을 사용할 때 1차 논리와 구별되는 지점이다.

레온 헹킨은 헹킨 의미론을 정의하고, 1차 술어 논리에서 성립하는 괴델의 완전성 정리와 콤팩트성 정리가 헹킨 의미론을 사용하는 2차 술어 논리에서도 성립함을 증명했다. 헹킨 의미론에서는 2차 변항에 대한 도메인이 별도로 존재하여, 해당 종류의 집합이나 함수 전체의 진부분집합일 수 있다.

3. 1. 증명 체계

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

가장 약한 연역 시스템은 2차 용어에 대한 치환 규칙이 추가된 1차 논리(예: 자연 연역)의 표준 연역 시스템이다.^[6] 이 연역 시스템은 2차 산술 연구에 주로 사용된다.

샤피로(Shapiro, 1991)와 헨킨(Henkin, 1950)이 고려한 연역 시스템은 보편 공리 및 선택 공리 모두를 보강된 1차 연역 체계에 추가한다. 이 공리들은 표준 2차 의미론에 대해 무모순성을 갖는다. 이는 보편 공리 및 선택 공리를 만족하는 Henkin 모델로 제한된 Henkin 의미론에 대해 무모순성을 갖는다.^[7]

3. 2. 불완전성 정리

괴델의 불완전성 정리에 따라, 2차 논리의 증명 체계는 다음 세 조건을 동시에 만족시킬 수 없다.^[8]

(정당성) 증명 체계가 증명할 수 있는 모든 명제는 2차 논리의 모든 (표준) 모형에서 참이다.
(완전성) 증명 체계는 2차 논리의 모든 (표준) 모형에서 참인 2차 논리 명제를 증명할 수 있다.
(유효성) 증명들의 집합은 재귀적 집합이다. 즉, 주어진 문자열이 어떤 명제의 증명인지 여부를 항상 종료하는 알고리즘으로 판별할 수 있다.

반면, 1차 논리의 경우 위 세 조건을 만족시키는 증명 체계가 존재한다 (괴델의 완전성 정리).

이러한 결과는 때때로 2차 논리가 완전한 증명 이론을 허용하지 않는다고 표현된다. 이 점에서 표준 의미론을 사용하는 2차 논리는 1차 논리와 다르다. 콰인은 완전한 증명 시스템이 없다는 점을 2차 논리를 '논리'로 간주하지 않는 이유로 지적했다.^[9]

3. 3. 콤팩트성 정리와 뢰벤하임-스콜렘 정리

2차 논리에서는 콤팩트성 정리와 뢰벤하임-스콜렘 정리가 성립하지 않는다.^[4] 이는 2차 논리가 표준 의미론을 사용할 때 1차 논리와 다른 점이다.

축약 정리와 뢰벤하임-스콜렘 정리는 2차 논리의 완전한 모델에는 적용되지 않지만, 헹킨 모델에는 적용된다.^[4] 레온 헹킨은 헹킨 의미론을 정의하고, 1차 술어 논리에서 성립하는 괴델의 완전성 정리와 콤팩트성 정리가 헹킨 의미론을 사용하는 2차 술어 논리에서도 성립함을 증명했다. 헹킨 의미론에서는 2차 변항에 대한 도메인이 별도로 존재하여, 해당 종류의 집합이나 함수 전체의 진부분집합일 수 있다.

4. 표현 능력

2차 논리는 1차 논리보다 표현력이 더 풍부하다. 1차 논리에서는 개체에 대해서만 양화할 수 있지만, 2차 논리에서는 술어(속성)와 함수에 대해서도 양화할 수 있기 때문이다.^[1]

예를 들어, 1차 논리로는 "모든 실수는 덧셈에 대한 역원을 가진다"라는 명제를 표현할 수 있지만, "실수의 모든 유계이고 비어있지 않은 집합은 최소 상한을 가진다"라는 명제는 표현할 수 없다. 하지만 2차 논리에서는 이 명제를 다음과 같이 표현할 수 있다.

: $\forall A ([\exists w (w \in A) \land \exists z\,\forall w ( w \in A \rightarrow w \leq z)] \rightarrow \exists x\,\forall y ([\forall w (w \in A \rightarrow w \leq y)] \leftrightarrow x \leq y))$

이 공식은 "모든 비어 있지 않고 유계인 실수 집합 A는 최소 상한을 가진다"는 것을 의미한다.

또한, 2차 논리에서는 "정의역(domain)이 유한하다" 또는 "정의역이 가산 무한이다"와 같은 명제도 표현할 수 있다. 1차 논리에서는 컴팩트성 정리와 상향 뢰벤하임-스코렘 정리에 의해 이러한 명제들을 표현할 수 없다.

노이쾰른의 그래피티는 2차 논리의 한 예시인 “ $\exists \phi \ \phi$ ”를 보여준다.

4. 1. 1차 논리와의 비교

1차 논리는 개체에 대해서는 양화(quantify)할 수 있지만, 술어(속성)에 대해서는 양화할 수 없다. 즉, `Cube(b)`와 같은 원자 문장이 있을 때, 여기서 이름 `b`를 변수로 바꾸고 양화사를 붙여 `∃x Cube(x)`와 같은 양화된 문장을 얻을 수 있다.^[1]

그러나 술어에 대해서는 같은 방식으로 할 수 없다. 예를 들어, `∃P P(b)`^[1] 와 같은 표현은 1차 논리의 문장이 아니다. 하지만 2차 논리에서는 `P`를 술어 변수로 사용하여 개체 집합을 의미하는 정당한 문장으로 만들 수 있다.

결과적으로 2차 논리는 1차 논리보다 표현력이 더 크다. 예를 들어, 1차 논리에서는 모든 정육면체(Cube)와 사면체(Tet)의 집합을 식별할 수 없다. 그러나 2차 논리에서는 `∃P ∀x (Px ↔ (Cube(x) ∨ Tet(x)))`와 같이 이 집합의 존재를 주장할 수 있다.

그런 다음 이 집합의 속성을 추가로 주장할 수 있다. 예를 들어, 다음 문장은 모든 정육면체와 사면체의 집합이 어떤 십이면체(Dodec)도 포함하지 않는다고 표현한다.

: `∀P (∀x (Px ↔ (Cube(x) ∨ Tet(x))) → ¬ ∃x (Px ∧ Dodec(x)))`

2차 양화는 도달 가능성 속성을 표현하는 데 유용하다. 예를 들어, `Parent(x, y)`가 `x`가 `y`의 부모임을 나타내는 경우, 1차 논리로는 `x`가 `y`의 조상이라는 속성을 표현할 수 없다. 하지만 2차 논리에서는 `y`를 포함하고 `Parent` 관계에 따라 닫혀 있는 모든 사람의 집합이 `x`를 포함한다고 표현할 수 있다.

: `∀P ((Py ∧ ∀a ∀b ((Pb ∧ Parent(a, b)) → Pa)) → Px)`

2차 논리에서는 술어에 대한 변수는 있지만, 술어의 속성에 대한 변수는 없다. 예를 들어, 술어 `P`가 `Cube`, `Tet`, `Dodec`에 대해 참인 속성 `Shape(P)`를 갖는다고 표현할 수 없다. 이를 위해서는 3차 논리가 필요하다.^[2]

4. 2. 유한성과 가산성

2차 논리에서는 "정의역은 유한 집합이다" 또는 "정의역은 가산 집합 기수이다"와 같은 문장을 작성할 수 있다.^[15] 정의역이 유한하다고 말하려면, 정의역에서 자체로의 모든 전사 함수가 단사 함수라는 문장을 사용한다. 정의역이 가산 기수를 갖는다고 말하려면, 정의역의 모든 두 개의 무한 부분 집합 사이에 전단사가 존재한다는 문장을 사용한다.^[15] 컴팩트성 정리와 상향 뢰벤하임-스코렘 정리에 따르면 1차 논리에서는 유한성 또는 가산성을 각각 특징지을 수 없다.

4. 3. 예시

2차 논리는 1차 논리보다 표현력이 더 풍부하다. 예를 들어, 1차 논리에서는 각 실수에 대한 덧셈 역원의 존재(∀''x'' ∃''y'' (''x'' + ''y'' = 0))는 표현할 수 있지만, 실수의 집합에 대한 최소 상한 속성은 2차 논리가 필요하다.^[1] 최소 상한 속성은 모든 유계이고 비어 있지 않은 실수 집합이 상한을 가진다는 것을 의미한다. 이를 2차 논리 문장으로 표현하면 다음과 같다.

:

\forall A \Big[(\exists w (w \in A) \land \exists z\,\forall w ( w \in A \rightarrow w \leq z)) \rightarrow \exists x\,\forall y ([\forall w (w \in A \rightarrow w \leq y)] \leftrightarrow x \leq y)\Big].

이 공식은 "모든 비어있지 않고 유계인 집합 A는 최소 상한을 갖는다"를 간결하게 표현한 것이다.

또한, 2차 논리에서는 "정의역은 유한 집합이다" 또는 "정의역은 가산 집합 기수이다"와 같은 문장을 작성할 수 있다.^[1] 정의역이 유한하다는 것은 정의역에서 자체로의 모든 전사 함수가 단사 함수라는 문장으로 표현할 수 있다. 정의역이 가산 기수를 갖는다는 것은 정의역의 모든 두 개의 무한 부분 집합 사이에 전단사가 존재한다는 문장으로 표현할 수 있다. 컴팩트성 정리와 상향 뢰벤하임-스코렘 정리에 따르면 1차 논리에서는 유한성 또는 가산성을 각각 특징지을 수 없다.

1차 논리에서는 Cube(''b'')와 같은 원자 문장에서 이름을 변수로 바꾸고 양화사를 붙여 ∃''x'' Cube(''x'')와 같이 양화된 문장을 얻을 수 있다.^[1] 그러나 술어에 대해서는 ∃P P(''b'')와 같이 표현할 수 없는데, 이는 1차 논리의 문장이 아니다. 하지만 2차 논리에서는 P를 술어 변수로 사용하여 집합으로 해석함으로써 정당한 문장으로 만들 수 있다.^[1]

2차 논리에서는 도달 가능성 속성을 표현할 수 있다. 예를 들어, Parent(''x'', ''y'')가 ''x''가 ''y''의 부모임을 나타내는 경우, 1차 논리는 ''x''가 ''y''의 조상이라는 속성을 표현할 수 없다. 2차 논리에서는 ''y''를 포함하고 Parent 관계에 따라 닫혀 있는 모든 사람의 집합이 ''x''를 포함한다고 말함으로써 이를 표현할 수 있다.^[2]

:

\forall P ((P''y'' \wedge \forall ''a'' \forall ''b'' ((P''b'' \wedge \text{Parent}(''a'', ''b'')) \rightarrow P''a'')) \rightarrow P''x'').

5. 역사

고틀로프 프레게는 1879년 《개념 표기법》에서 2차 논리와 유사한 체계를 도입했고, 찰스 샌더스 퍼스는 '2차 논리'라는 용어를 만들었지만, 초기에는 1차 논리와 명확히 구분되지 않았다.^[11] 러셀의 역설 발견 이후, 1차 논리가 정립되면서 2차 논리 연구는 침체기를 겪었다.

집합론이 1차 논리 내에서 공리화될 수 있다는 점과 쿠르트 괴델, 토럴프 스콜렘 등의 영향으로 1차 논리가 주류가 되었고, 윌러드 밴 오먼 콰인은 2차 논리를 비판했다.

그러나 최근 조지 불로스 등은 2차 논리를 옹호하며 다시 주목받고 있다. 리언 앨버트 헹킨이 1950년에 도입한 헹킨 의미론^[12]은 2차 논리 연구에 새로운 방향을 제시했다.

5. 1. 프레게와 퍼스

고틀로프 프레게는 1879년에 출판된 《개념 표기법》^[1]에서 오늘날의 2차 논리와 유사한 논리 체계를 도입하였다.^[11] 그러나 프레게는 1차 논리와 고차 논리를 구분하지 않았다. 이후 찰스 샌더스 퍼스가 1차 논리와 2차 논리를 구분하였으며, "2차 논리"라는 용어를 도입하였다.^[11]

찰스 샌더스 퍼스는 "2차 논리"라는 용어를 처음 사용하고 현대적인 형식과 가장 유사한 표기법을 사용하여 술어 논리를 수학계에 소개하였다.^[2] 그러나 오늘날 대부분의 논리학 학생들은 퍼스보다 수년 전에 연구를 발표했지만, 버트런드 러셀과 앨프레드 노스 화이트헤드에 의해 유명해질 때까지 덜 알려졌던 고틀로프 프레게의 연구에 더 익숙하다. 프레게는 대상에 대한 수량화와 속성 및 집합에 대한 수량화를 구별하기 위해 서로 다른 변수를 사용했지만, 자신이 두 종류의 다른 논리를 하고 있다고 생각하지 않았다. 러셀의 역설이 발견된 후, 그의 시스템에 무언가 잘못되었다는 것을 깨달았다.^[3]

5. 2. 콰인과 불로스

윌러드 밴 오먼 콰인은 2차 논리가 (이솝 우화에 빗대어) “양의 탈을 쓴 집합론”(set theory in sheep’s clothing^영어)이라고 비판하였다.^[13] 콰인은 2차 논리로는 멱집합 등 집합론에 해당하는 여러 개념들을 정의할 수 있고, 적절한 증명 이론을 제시할 수 없으므로, 1차 논리와 달리 2차 ‘논리’는 사실 논리가 아니라고 주장했다. 그는 술어 언어 문장에서 "`x`"는 대상을 나타내는 변수 또는 이름으로 간주되어 수량화될 수 있지만, "`F`"는 대상의 이름이 아니라 불완전한 문장의 "약어"로 간주되어야 한다고 보았다.

반면, 조지 불로스(George Boolos^영어)^[14]를 비롯한 다른 수리철학자들은^[15]^[16]^[17]^[18]^[19] 콰인의 비판에 반대하여 2차 논리를 옹호하였다. 불로스는 2차 수량화를 1차 수량화와 동일한 대상 영역에 대한 복수 수량화로 해석하여 2차 논리가 집합론으로 환원되지 않는다고 주장했다. 또한 "어떤 비평가들은 서로만 존경한다"와 같은 문장이 2차 수량화의 힘에 의해서만 표현될 수 있다고 지적했다.

5. 3. 헹킨 의미론

헹킨 의미론은 리언 앨버트 헹킨(1921~2006)이 1950년에 도입하였다.^[12] 헹킨은 2차 및 고차 이론에 대한 대안적 의미론을 정의했는데, 여기서 고차 영역의 의미는 집합 또는 함수의 속성에 대한 명시적인 공리화(유형 이론을 기반으로 함)를 통해 부분적으로 결정된다. 헹킨 의미론은 일종의 다중 정렬 1차 의미론이며, 표준 의미론에서처럼 의미론이 표준 모델로만 고정되는 대신 공리의 모델 클래스가 있다. 헹킨 의미론의 모델은 고차 영역의 해석으로 모든 집합 또는 해당 종류의 함수의 진부분 집합일 수 있는 집합의 집합 또는 함수의 집합을 제공한다.^[3]

헹킨은 자신의 공리화를 위해 괴델의 완전성 정리와 콤팩트성 정리가 1차 논리에 적용되는 것처럼 헹킨 의미론을 가진 2차 논리로 옮겨진다는 것을 증명했다. 또한 스코렘-뢰벤하임 정리가 헹킨 의미론에 적용되므로 린드스트롬의 정리는 헹킨 모델이 단지 ''위장된 1차 모델''임을 보여준다.^[3]

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

주코 배너넌은 2차 논리에 대한 헨킨 의미론과 전체 의미론의 구별은 ZFC에서의 증명 가능성과 ''V''에서의 진실의 구별과 유사하며, 전자는 스코렘-뢰벤하임 정리와 콤팩트성 정리와 같은 모델 이론적 속성을 따르고 후자는 범주성 현상을 갖는다고 주장했다.

6. 계산 복잡도와의 관계

계산 복잡도 이론에서 유한 구조에 대한 2차 논리의 표현력은 특정 계산 복잡도 종류를 나타내는 논리적 힘과 밀접하게 관련되어 있다.

유한 구조에 대한 2차 논리의 변형에 대한 특징은 다음과 같다.

REG는 단항 2차 논리 공식으로 정의 가능하다 (Büchi-Elgot-Trakhtenbrot 정리, 1960).
NP는 존재 2차 논리 공식으로 정의 가능하다 (Fagin's 정리, 1974).
co-NP는 전칭 2차 논리 공식으로 정의 가능하다.
PH는 2차 논리 공식으로 정의 가능하다.
PSPACE는 추이적 폐쇄 연산자가 추가된 2차 논리 공식으로 정의 가능하다.
EXPTIME는 최소 고정점 연산자가 추가된 2차 논리 공식으로 정의 가능하다.

이러한 종류 간의 관계는 유한 구조에 대한 논리의 상대적 표현력에 직접적인 영향을 미친다. 예를 들어, '''PH''' = '''PSPACE'''이면, 2차 논리에 추이적 폐쇄 연산자를 추가해도 유한 구조에 대한 표현력이 더 이상 증가하지 않는다.

6. 1. 기술적 복잡도

계산 복잡도 이론과 관련하여, 유한 구조에서 다양한 형태의 2차 논리가 가지는 표현력은 특정 계산 복잡도 종류를 특징짓는 데 중요한 역할을 한다. 기술적 복잡도 분야에서는 어떤 복잡도 종류가 언어(유한 문자열 집합)를 표현하는 데 필요한 논리의 힘으로 특징지어질 수 있는지를 연구한다.

유한 알파벳 ''A''의 문자열 ''w'' = ''w''₁···''w_n''은 도메인 ''D'' = {1,...,''n''}을 가진 유한 구조로 표현될 수 있다. 이 구조는 각 ''a'' ∈ ''A''에 대해 ''w_i'' = ''a''인 인덱스 ''i''에 의해 만족되는 단항 술어 ''P_a''를 포함하며, 어떤 인덱스가 무엇인지를 고유하게 식별하는 데 사용되는 추가 술어(일반적으로 ''D''에 대한 후계 함수 또는 순서 관계 <의 그래프를 사용하며, 다른 산술 술어가 있을 수 있음)를 포함한다. 반대로, 유한 시그니처를 갖는 모든 유한 구조의 케일리 표는 유한 문자열로 인코딩될 수 있다.

이러한 관계는 유한 구조에 대한 2차 논리의 변형에 대한 다음과 같은 특징을 갖는다:

논리 형식	복잡도 종류	설명	관련 정리
단항 2차 논리	REG	단항 2차 논리 공식으로 정의 가능한 언어 집합	Büchi-Elgot-Trakhtenbrot 정리 (1960)
존재 2차 논리	NP	존재 2차 논리 공식으로 정의 가능한 언어 집합	Fagin's 정리 (1974)
전칭 2차 논리	co-NP	전칭 2차 논리 공식으로 정의 가능한 언어 집합
2차 논리	PH	2차 논리 공식으로 정의 가능한 언어 집합
2차 논리 + 추이적 폐쇄 연산자	PSPACE	추가된 추이적 폐쇄 연산자를 가진 2차 논리 공식으로 정의 가능한 언어 집합
2차 논리 + 최소 고정점 연산자	EXPTIME	추가된 최소 고정점 연산자를 가진 2차 논리 공식으로 정의 가능한 언어 집합

이러한 복잡도 종류 간의 관계는 유한 구조에 대한 논리의 상대적 표현력에 직접적인 영향을 미친다. 예를 들어, 만약 '''PH''' = '''PSPACE'''이면, 2차 논리에 추이적 폐쇄 연산자를 추가해도 유한 구조에 대한 표현력이 더 이상 증가하지 않는다.

6. 2. 복잡도 클래스와의 관계

계산 복잡도 이론에서 유한 구조에 대한 다양한 형태의 2차 논리의 표현력은, 특정 계산 복잡도 종류를 정의하는 데 필요한 논리적 힘과 밀접하게 관련되어 있다. 기술적 복잡도 분야는 이러한 관계를 연구한다.

유한 알파벳 ''A''의 문자열 ''w''= ''w''₁···''w_n''은 유한 구조로 표현될 수 있으며, 반대로 유한 구조의 케일리 표는 유한 문자열로 인코딩될 수 있다. 이러한 관계를 바탕으로, 유한 구조에 대한 2차 논리의 변형은 다음과 같은 특징을 갖는다.

REG(정규 언어)는 단항 2차 논리 공식으로 정의 가능하다 (Büchi-Elgot-Trakhtenbrot 정리, 1960).
NP는 존재 2차 논리 공식으로 정의 가능하다 (Fagin's 정리, 1974).
co-NP는 전칭 2차 논리 공식으로 정의 가능하다.
PH는 2차 논리 공식으로 정의 가능하다.
PSPACE는 추이적 폐쇄 연산자가 추가된 2차 논리 공식으로 정의 가능하다.
EXPTIME는 최소 고정점 연산자가 추가된 2차 논리 공식으로 정의 가능하다.

이러한 복잡도 클래스 간의 관계는 유한 구조에 대한 논리의 상대적 표현력에 직접적인 영향을 미친다. 예를 들어, '''PH'''= '''PSPACE'''이면 2차 논리에 추이적 폐쇄 연산자를 추가해도 표현력이 더 이상 증가하지 않는다.

7. 논쟁

레온 헨킨은 2차 논리에 대한 대안적인 의미론을 제시하여, 2차 영역의 의미를 집합이나 함수의 속성에 대한 공리화를 통해 부분적으로 결정했다. 헨킨 의미론은 다중 정렬 1차 의미론의 일종으로, 표준 의미론과 달리 공리의 모델 클래스를 가진다. 헨킨 의미론의 모델은 2차 영역의 해석으로 모든 집합이나 해당 종류의 함수의 진부분 집합일 수 있는 집합의 집합 또는 함수의 집합을 제공한다.^[3] 헨킨은 자신의 공리화에 대해 괴델의 완전성 정리와 콤팩트성 정리가 1차 논리에 적용되는 것처럼 헨킨 의미론을 가진 2차 논리로 옮겨진다는 것을 증명했다. 또한 Skolem–Löwenheim 정리가 헨킨 의미론에 적용되므로 린드스트롬의 정리는 헨킨 모델이 ''위장된 1차 모델''임을 보여준다.^[3]

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

2차 논리는 1차 논리보다 표현력이 더 풍부하다. 예를 들어, 정의역이 모든 실수의 집합인 경우, 1차 논리에서는 각 실수의 덧셈 역원의 존재를 주장할 수 있지만, 실수의 집합에 대한 최소 상한 속성을 주장하려면 2차 논리가 필요하다. 최소 상한 속성은 모든 유계이고 비어 있지 않은 실수 집합이 상한을 가진다고 명시한다. 정의역이 모든 실수 집합인 경우, 2차 논리를 통해 "모든 비어 있지 않은, 유계 집합 A는 최소 상한을 가진다"를 형식화할 수 있다. 이 속성을 만족하는 모든 순서체는 실수 필드와 동형임을 보일 수 있다. 반면에, 실수에서 유효한 1차 문장의 집합은 콤팩트성 정리에 의해 임의로 큰 모델을 가질 수 있다. 따라서 최소 상한 속성은 1차 논리의 어떤 문장 집합으로도 표현될 수 없다.

2차 논리에서는 "정의역은 유한 집합이다" 또는 "정의역은 가산 집합 기수이다"와 같은 형식적인 문장을 작성할 수 있다. 정의역이 유한하다고 말하려면, 정의역에서 자체로의 모든 전사 함수가 단사 함수라는 문장을 사용한다. 정의역이 가산 기수를 갖는다고 말하려면, 정의역의 모든 두 개의 무한 부분 집합 사이에 전단사가 존재한다는 문장을 사용한다. 콤팩트성 정리와 상향 뢰벤하임-스코렘 정리에 따르면 1차 논리에서는 유한성 또는 가산성을 각각 특징지을 수 없다.

7. 1. 1차 논리로의 환원 불가능성

레온 헨킨은 2차 논리에 대한 대안적인 의미론을 정의했는데, 여기서 2차 영역의 의미는 집합이나 함수의 속성에 대한 명시적인 공리화를 통해 부분적으로 결정된다. 헨킨 의미론은 일종의 다중 정렬 1차 의미론이며, 표준 의미론에서처럼 의미론이 표준 모델로만 고정되는 대신 공리의 모델 클래스가 있다. 헨킨 의미론의 모델은 2차 영역의 해석으로 모든 집합이나 해당 종류의 함수의 진부분 집합일 수 있는 집합의 집합 또는 함수의 집합을 제공한다.^[3] 헨킨은 자신의 공리화를 위해 괴델의 완전성 정리와 콤팩트성 정리가 1차 논리에 적용되는 것처럼 헨킨 의미론을 가진 2차 논리로 옮겨진다는 것을 증명했다. 또한 Skolem–Löwenheim 정리가 헨킨 의미론에 적용되므로 린드스트롬의 정리는 헨킨 모델이 단지 ''위장된 1차 모델''임을 보여준다.^[3]

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

2차 논리는 1차 논리보다 표현력이 더 풍부하다. 예를 들어, 정의역이 모든 실수의 집합인 경우, 1차 논리에서는 각 실수의 덧셈 역원의 존재를 주장할 수 있지만, 실수의 집합에 대한 최소 상한 속성을 주장하려면 2차 논리가 필요하다. 최소 상한 속성은 모든 유계이고 비어 있지 않은 실수 집합이 상한을 가진다고 명시한다. 정의역이 모든 실수 집합인 경우, 2차 논리를 통해 "모든 비어 있지 않은, 유계 집합 A는 최소 상한을 가진다"를 형식화할 수 있다. 이 속성을 만족하는 모든 순서체는 실수 필드와 동형임을 보일 수 있다. 반면에, 실수에서 유효한 1차 문장의 집합은 콤팩트성 정리에 의해 임의로 큰 모델을 가질 수 있다. 따라서 최소 상한 속성은 1차 논리의 어떤 문장 집합으로도 표현될 수 없다.

2차 논리에서는 "정의역은 유한 집합이다" 또는 "정의역은 가산 집합 기수이다"와 같은 형식적인 문장을 작성할 수 있다. 정의역이 유한하다고 말하려면, 정의역에서 자체로의 모든 전사 함수가 단사 함수라는 문장을 사용한다. 정의역이 가산 기수를 갖는다고 말하려면, 정의역의 모든 두 개의 무한 부분 집합 사이에 전단사가 존재한다는 문장을 사용한다. 콤팩트성 정리와 상향 뢰벤하임-스코렘 정리에 따르면 1차 논리에서는 유한성 또는 가산성을 각각 특징지을 수 없다.

2차 논리의 실수를 완전한 2차 논리 의미론으로 갖는 실수 이론을 1차 논리로 축소하려는 시도가 있을 수 있다. 먼저 도메인을 모든 실수의 집합에서, 두 번째 유형에는 모든 실수 ''집합''을 포함하는 두 가지 유형의 도메인으로 확장한다. 그리고 언어에 멤버십 관계를 나타내는 새로운 이항 술어를 추가한다. 그러면 이전에 2차였던 문장은 1차 문장이 되며, 이전에 2차였던 한정자는 두 번째 유형을 대신 범위로 한다.

그러나 도메인이 ''모든'' 실수 집합을 포함하도록 주장되었다는 점에 주목해야 한다. 그러한 요구 사항은 뢰벤하임-스콜렘 정리가 보여주는 것처럼 1차 문장으로 축소될 수 없다. 이 정리는 실수에 가산 무한 부분 집합이 있으며, 그 구성원을 ''내부 숫자''라고 부르고, 내부 숫자의 가산 무한 집합이 있으며, 그 구성원을 "내부 집합"이라고 부르며, 내부 숫자와 내부 집합으로 구성된 도메인이 실수와 실수 집합의 도메인에 의해 충족되는 것과 정확히 동일한 1차 문장을 충족함을 의미한다. 특히, 상한이 있는 모든 비어 있지 않은 ''내부'' 집합은 최소 ''내부'' 상한을 갖는다는 최소 상한 공리를 만족시킨다.

모든 내부 숫자의 집합의 가산성은 해당 집합이 완전한 최소 상한 공리를 충족하지 않음을 의미한다. 모든 ''내부'' 집합의 가산성은 해당 집합이 모든 ''내부'' 숫자의 집합의 ''모든'' 부분 집합이 아님을 의미한다. 이 구성은 스콜렘의 역설과 밀접하게 관련되어 있다.

따라서 실수와 실수 집합의 1차 이론에는 여러 모델이 있으며, 그 중 일부는 가산적이다. 그러나 실수의 2차 이론에는 단 하나의 모델만 있다. 이는 유일한 아르키메데스 완전 순서 체가 존재한다는 고전적인 정리와 아르키메데스 완전 순서 체의 모든 공리가 2차 논리로 표현될 수 있다는 사실에서 비롯된다. 이는 실수의 2차 이론이 1차 이론으로 축소될 수 없음을 보여준다. 즉, 실수의 2차 이론은 단 하나의 모델만 갖지만 해당 1차 이론은 여러 모델을 갖는다.

표준 의미론을 갖는 2차 논리가 1차 논리보다 더 표현력이 있음을 보여주는 더 극단적인 예가 있다. 연속체 가설이 참일 경우 유일한 모델이 실수가 되고, 연속체 가설이 참이 아닐 경우 모델이 없는 유한 2차 이론이 있다. 이 이론은 실수를 완전 아르키메데스 순서 체로 특징짓는 유한 이론과 도메인이 최초의 비가산 기수임을 나타내는 공리로 구성된다.

7. 2. 완전한 증명 시스템의 부재

괴델의 불완전성 정리의 결과로, 2차 논리에는 다음과 같은 세 가지 속성을 모두 만족하는 연역 시스템(즉, '증명 가능성' 개념)이 존재하지 않는다.^[8]

(건전성) 증명 가능한 모든 2차 논리 문장은 보편적으로 타당하며, 즉 표준 의미론에서 모든 영역에서 참이다.
(완전성) 표준 의미론에서 모든 보편적으로 타당한 2차 논리식은 증명 가능하다.
(효과성) 주어진 기호열이 증명인지 여부를 올바르게 결정할 수 있는 자동 증명 검사 알고리즘이 존재한다.

이러한 결과는 2차 논리가 완전한 증명 이론을 갖지 않는다는 것을 의미한다. 이러한 점에서 표준 의미론을 사용하는 2차 논리는 1차 논리와 다르다. 윌러드 밴 오먼 콰인은 완전한 증명 시스템이 없다는 점을 들어 2차 논리를 제대로 된 '논리'로 간주하지 않았다.^[9]

하지만, 헨킨은 1차 논리에 대한 표준 연역 시스템이 헨킨 의미론을 사용하는 2차 논리에 대해 건전하고, 완전하며, 효과적임을 증명했다. 또한, 이해(comprehension) 및 선택(choice) 공리를 사용하는 연역 시스템은 이러한 공리를 만족하는 모델만을 사용하여 헨킨 의미론에 대해 건전하고, 완전하며, 효과적이다.

축약 정리와 뢰벤하임-스코렘 정리는 2차 논리의 완전한 모델에는 적용되지 않지만, 헨킨 모델에는 적용된다.^[4]

참조

_[1] 웹사이트 Second Order Logic https://faculty.wash[...] 2007
_[2] 간행물 Second-order and Higher-order Logic https://plato.stanfo[...] Metaphysics Research Lab, Stanford University 2022-05-03
_[3] 서적 Introduction to Mathematical Logic Chapman and Hall/CRC
_[4] 문서 Model Theory https://books.google[...] "[[Oxford University Press#Clarendon Press|Clarendon Press]]"
_[5] 문서
_[6] 문서
_[7] 문서
_[8] 문서
_[9] 서적 Philosophy of Logic Prentice-Hall 1970
_[10] 서적 Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens http://gallica.bnf.f[...] Verlag von Louis Nebert 1879
_[11] 저널 Peirce the logician
_[12] 저널 Completeness in the theory of types
_[13] 서적 Philosophy of logic http://www.hup.harva[...] Harvard University Press 1986-06
_[14] 저널 On second-order logic 1975-09
_[15] 서적 Foundations without foundationalism: a case for second-order logic Oxford University Press 2000
_[16] 저널 Do not claim too much: second-order logic and first-order logic 1999-02
_[17] 저널 Higher-order logic or set theory: a false dilemma 2012-10
_[18] 저널 Second-order logic and foundations of mathematics http://www.math.hels[...]
_[19] 저널 A defense of second-order logic http://www.as.miami.[...] 2010

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com