Enderton

진리는 무엇인가? 참과 거짓이란 근본적으로 무엇인가? 어떤 것이 참되다는 것을 어떻게 증명할 수 있는가? 타당한 증명이란 무엇인가?

기호 논리는 연역적 생각의 수학 모델이다. 확률론이 확률적이고 불확실한 상황의 모델인 것처럼 말이다. 모델은 어떻게 만들어지는가? 비행기 같은 자연 대상으로부터 시작하여 본질적이라고 판단되는 대상의 특성을 추출한다. 가령 비행기의 모양을 제외하고 비행기의 나머지 속성을 다 제거하는 것이다.

자연 대상의 모델을 만들면 수학적으로 다루기 쉬워진다. 옛부터 인류는 자연 대상을 모델링하여 발전해왔다. 가령, 지구와 해와 달을 직접 다룰 수 없으니 그것을 원과 원들의 관계로 추상화시켰다. 이것은 행성을 행성의 무게, 실제 크기, 그 안에 있는 디테일한 내용물들을 모두 제거하고 원이라는 수학적 대상으로 변환시킨 것이다. 이렇게 자연 대상을 수학의 세계로 끌어내리면 수학의 세계는 매우 명료하고 구체적이며 어둠이 없으며 말싸움도 논쟁도 전쟁도 없기 때문에 대상을 효과적으로 다룰 수 있다. 그리고 이미 수학의 세계에 수천년간 쌓여온 강력한 도구들을 사용할 수 있다. 또한, 수학의 세계로 이끌어내린 것들은 기계화시키기에도 편하고, 또는 기계화 가능한지 따지는 것도 편하다.

이제 우리는 처음에 했던 질문에 대한 대답이 무엇인지 논해보기 위하여 인간의 생각을 추상화시켜서 모델링하고 결국 수학적 대상으로 만들 것이다. 이로써 우리가 무엇을 참되다고 생각하고, 거짓되다고 생각하며, 참된 것들은 어떻게 증명할 수 있고, 혹은 증명 불가능하지만 참되다고 할 수 있는 것들이 존재하는지에 대해서 논해볼 것이다.

인간의 생각은 그 자체로써 이미 비행기나 행성 보다 더 추상적이다. 그래서 인간의 생각을 추상화하는 작업은 다른 물리적 대상을 추상화하는 작업보다 더욱 어려울 수 있지만, 더욱 고귀하고 가치있는 작업이다. 가령, 우리는 다음과 같이 생각한다.

1. 모든 인간은 죽는다.
2. 소크라테스는 인간이다.
3. 소크라테스는 죽는다.

공리적 수학은 이런 유의 연역으로 구성되어 있다. 이 연역은 그 특성이 모델(수학적 대상)로 사상될 수 있는 현실 세계의 자연 대상의 실제를 구성한다.

우리는 이렇게 연역된 논리를 참되다고 생각한다. 하지만 이 논리의 참됨은 소크라테스의 특성 같은 문장의 내부적인 의미에 의존하지 않고, 문장의 형태와 구조에 의존한다. 그러므로 "소크라테스" 나 "죽음" 의 의미 같은 문장 내부적 의미가 중요한 것이 아니라 "모든" 이라는 단어가 중요하다.

하지만 이 표준이 아직은 애매하다. 그러므로 우리의 목적은 모델 안에서 정확한 표준을 정립하는 것이다. 구체적으로 말하면 다음과 같은 질문에 대답하는 것이다.

1. 어떤 문장에서 다른 문장으로 논리적으로 넘어가는 것은 어떤 것인가?
2. 어떤 문장에서 다른 문장으로 논리적으로 넘어갔다면, 이 사실을 정립하기 위한 증명이란 어떤 것인가?
3. 공리 체계에서 증명할 수 있는 것과 진리 사이에 괴리가 존재하는가? 즉, 참이라고 믿을 수 있는 사실들은 모두 증명가능한가?
4. 논리와 계산가능성의 관계는 무엇인가?

3) 의 질문에 대한 대답은 중요한데, 진리를 밝혀내기 위하여 항상 증명에 의존해도 되는지 여부를 결정해주기 때문이다.

이제 우리는 두 가지 모델을 살펴본다. 첫번째는 명제 논리(sentential logic, propositional logic)이고, 두번째는 1차 논리(first-order logic)이다. 명제 논리는 간단하지만 유의미한 연역을 다룰 수 없다. 1차 논리는 수학에서의 수행해야 하는 연역을 다루기에 적합하다. 그래서 수학자가 집합론의 공리에서 도출된 문장을 1차 논리로 다룰 수 있다.

하지만 그 전에 먼저 집합론에 대한 중요한 사실들을 짚고 넘어가자.

Prerequisite Set Theory✔

• \(k = 1\) 이면 절편을 초기 절편(initial segment)이라고 하고, 절편이 \(S\) 와 다르면 적절하다(proper, 진부분집합)고 한다.

• 증명

• 예시

  \(0\) 부터 \(3\) 의 순서 관계 \(<\) 는 다음과 같다.

  \[ < = \{\left< 0,1 \right>, \left< 0,2 \right>, \left< 0,3 \right>, \left< 1,2 \right>, \left< 1,3 \right>, \left< 2,3 \right> \} \]

  이때 \(\left< a, b \right> \in <\) 이면 \(a < b\) 라고 표기한다. 가령, \(0 < 1\) 이다.

• 관계 \(R\) 의 정의역(domain)은 어떤 \(y\) 에 대하여 \(\left< x, y \right> \in R\) 을 만족하는 \(x\) 의 집합이고, \(\operatorname{dom} R\) 로 표기한다. 관계 \(R\) 의 치역(range)은 어떤 \(x\) 에 대하여 \(\left< x, y \right> \in R\) 을 만족하는 \(y\) 의 집합이고, \(\operatorname{ran} R\) 로 표기한다. 관계 \(R\) 의 필드(field)는 정의역과 치역의 합집합이고, \(\operatorname{fld} R\) 로 표기한다.

• \(n>1\) 일 경우 관계가 되지만, \(n=1\) 일 경우 단순히 \(A\) 의 부분집합이 된다.

• 예시

  기호 \(=\) 로 표기되는 동등 관계 \(\{\left< x,x \right> : x \in A\}\) 는 \(A ^{2}\) 의 부분집합이다.

• 예시

  \(0\) 부터 \(3\) 까지의 순서 관계는 \(\N\) 위의 순서 관계의 \(\{0,1,2,3\}\) 으로의 제한이다.

• 이 유일성이 정의역의 원소 \(x\) 와 치역의 원소 \(y\) 에 대하여 \(F(x) = y\) 임을 보장해준다. 함수 \(F\) 의 정의역이 \(A\) 이고 치역이 \(B\) 이면 \(F\) 가 \(A\) 를 \(B\) 로 사상한다고 하고, \(F: A \to B\) 로 표기한다.

• 정의역의 원소가 순서쌍 \(\left< x_1, x_2, \dots, x_n \right>\) 이면 \(F(\left< x_1, x_2, \dots, x_n \right>)\) 라고 표기하지 않고 편하게 \(F( x_1, x_2, \dots, x_n )\) 로 표기한다.

• 증명

• 몇몇 곳에서 선택공리를 사용할 것이지만, 정리가 가산 언어(countable language)에 제한될 경우 그렇지 않을 것이다. 선택공리와 동치인 초른의 보조정리는 특히 유용하다. 집합의 모임 \(C\) 가 사슬(chain)인 것과 임의의 \(x, y \in C\) 에 대하여 \(x \subset y\) 또는 \(y \subset x\) 인 것은 동치이다.

• 집합론에서의 초른의 보조정리와 일맥상통한다.

  "집합 \(A\) 의 임의의 사슬을 \(C \subset A\) 에 대하여 \(\bigcup_{}^{}C \in A\) 이면" 은 "(포함관계를 순서관계로 갖는) 공집합이 아닌 순서집합 \(X\) 의 모든 사슬이 상계를 가지면" 과 동치이다.

  그리고 "\(A\) 는 다른 원소의 부분집합이 되지 않는 극대원소를 가진다" 는 "\(X\) 는 극대원소를 가진다" 와 동치이다.

• 집합론에서의 베른슈타인 정리와 같다. 다만, 2) 가 추가되었다. 하지만 2) 는 단지 1) 을 다르게 말한 것에 불과하다.

• 증명

• 이 정리에 의하여 임의의 기수는 반드시 다른 기수보다 작다.

Sentential Logic✔

형식 언어(informal language)를 사용하면 자연 언어에 남아있는 모호함과 어두움을 제거할 수 있다.

형식 언어를 사용하는 대표적인 대상은 컴퓨터이다. 가령, 컴퓨터는 다음과 같은 형식 언어를 사용한다.

프로그래밍 언어는 가령 다음과 같은 형식 언어를 사용한다.

프로그래머는 자신의 생각을 이 형식 언어로 변환해시켜야만 컴퓨터를 다룰 수 있다. 반면 형식 언어를 다시 자연어로 격상시킬 수 있다면 더욱 놀라운 일들을 할 수 있다.

컴퓨터가 사용하는 이러한 형식 언어에 대해서는 컴퓨터를 모델링한 튜링의 논문을 보면서 더 심도있게 살펴보기로 하고, 지금은 인간의 생각을 논리로 정형화시켜서 나타내어줄 수 있는 형식 언어를 구성하려 한다. 첫 시작은 명제 논리(sentential logic, propositional logic)이다.

Language of Sentential Logic✔

• 예시

  \((( \implies A_3\) 는 wff 가 아니다.

• 이 규칙을 좀 더 정확하게 표현하면, wff 는 다음의 다섯가지 식구성 연산(formula-building operation)에 의하여 정의된다고 할 수 있다.

  \[ \mathcal{E}_{\neg }(\alpha) = \neg \alpha \]
  \[ \mathcal{E}_{\land }(\alpha, \beta ) = (\alpha \land \beta ) \]
  \[ \mathcal{E}_{\lor }(\alpha, \beta ) = (\alpha \lor \beta ) \]
  \[ \mathcal{E}_{\implies }(\alpha, \beta ) = (\alpha \implies \beta ) \]
  \[ \mathcal{E}_{\iff }(\alpha, \beta ) = (\alpha \iff \beta ) \]

• 증명

  임의의 wff \(\alpha\) 는 문장 기호에 식구성 연산을 유한번 적용하여 얻은 결과이다. 식구성 연산이 닫혀있으니 개별 문장 기호가 \(S\) 에 포함되므로 식구성 연산을 적용한 결과도 \(S\) 에 포함되고, 결국 그 결론인 \(\alpha\) 도 \(S\) 에 포함된다. ■

Truth Assignments✔

• 예시

  \(S = \{A_1, A_2\}\) 이면 진리 할당 \(v\) 는 다음과 같이 정의될 수 있다.

  \[ v(A_1) = T, v(A_2) = T \]
  \[ v(A_1) = T, v(A_2) = F \]
  \[ v(A_1) = F, v(A_2) = T \]
  \[ v(A_1) = F, v(A_2) = F \]

• 그러나 문장 기호에만 사용가능한 \(v\) 는 쓸모가 없으므로 wff 에 사용가능한 진리 할당을 정의해야만 한다. \(\bar{S}\) 가 식구성 연산에 의하여 \(S\) 로부터 구성된 wff 들의 집합이라고 하자. 그러면 \(v\) 를 다음과 같은 \(\bar{v}\) 로 할당할 수 있다.

  \[ \bar{v} : \bar{S} \to \{F, T\} \]

  이때 \(\bar{v}\) 는 다음의 조건을 만족해야 한다.

  1. 임의의 \(A \in S\) 에 대하여 \(\bar{v}(A) = v(A)\) 이다.

  임의의 \(\alpha,\beta \in \bar{S}\) 에 대하여:

  2. \(\bar{v}((\neg \alpha)) = \begin{cases} T & \bar{v}(\alpha) = F\\ F & \text{else} \\ \end{cases}\)
  3. \(\bar{v}((\alpha \land \beta )) = \begin{cases} T & \bar{v}(\alpha) \land \bar{v}(\beta ) = T\\ F & \text{else} \\ \end{cases}\)
  4. \(\bar{v}((\alpha \lor \beta )) = \begin{cases} T &\bar{v}(\alpha ) = T \lor \bar{v}(\beta ) = T\\ F & \text{else} \\ \end{cases}\)
  5. \(\bar{v}((\alpha \implies \beta )) = \begin{cases} F &\bar{v}(\alpha ) = T \land \bar{v}(\beta ) = F\\ T & \text{else} \\ \end{cases}\)
  6. \(\bar{v}((\alpha \iff \beta )) = \begin{cases} T &\bar{v}(\alpha ) = \bar{v}(\beta ) \\ F & \text{else} \\ \end{cases}\)

• 증명

• 진리 할당 \(v\) 가 \(\phi\) 를 만족한다는 것은 \(\bar{v}(\phi ) = T\) 인 것과 동치이다. 물론 이것이 성립하기 위하여 \(v\) 의 정의역이 \(\phi\) 의 모든 문장 기호를 포함해야 한다.

Tautological Implication✔

• "\(\Sigma\) 가 참이면 \(\tau\) 도 참이다" 라는 말이다.

• 예시

  \(\{A, (A \implies B)\} \vDash B\) 이다. 왜 그런지 조사해보자.

  \(\{A, B\}\) 에 대하여 다음과 같은 4가지의 진리할당이 존재한다.

  \[ v(A) = T, v(B) = T \]
  \[ v(A) = T, v(B) = F \]
  \[ v(A) = F, v(B) = T \]
  \[ v(A) = F, v(B) = F \]

  이 4가지의 진리 할당 중 \(v(A) = v(B) = T\) 인 진리 할당만이 \(A\) 와 \(A \implies B\) 를 만족한다. 이 \(v\) 는 \(B\) 도 만족한다. 그러므로 \(\{A, (A \implies B)\}\) 는 항진적으로 \(B\) 를 함의한다.

• 사실 wff \(\sigma _1, \dots , \sigma _k, \tau\) 에 대한 다음이 성립하는지 확인하는 것은 쉽다.

  \[ \{\sigma _1, \dots , \sigma _k\} \vDash \tau \]

  각 명제들의 모든 진리 할당의 경우의 수를 따져보면 되기 때문이다.

• 예시

  \[ \neg (A \land B) \vDash ((\neg A) \lor (\neg B)) \]

  가 성립하는지 따져보려면 \(A, B\) 에 입력 가능한 \(T, F\) 의 모든 조합을 대입해보면 된다. 명제가 \(2\) 개이므로 \(T,T\) 와 \(T,F\) 와 \(F,T\) 와 \(F,F\) 의 \(2 ^{2} = 4\) 개의 경우의 수만 따져보면 된다. 명제가 \(n\) 개이면 \(2 ^{n}\) 의 경우의 수를 따져보면 된다.

• 예시

  문장 집합 \(\{A_1, A_2, A_6\}\) 에 대한 임의의 진리 할당에서 \(((A_2 \implies (A_1 \implies A_6)) \iff ((A_2 \land A_1) \implies A_6))\) 은 항상 참이 되므로 이것은 항진식이다.

• 문장 집합 \(\Sigma\) 의 모든 원소를 만족할 수 있는 어떠한 진리 할당도 존재하지 않으면, 임의의 \(\tau\) 에 대하여 \(\Sigma \vDash \tau\) 는 공허하게 진리가 된다.

• 예시

  다음이 성립한다.

  \[ \{A, \neg A\} \vDash B \]

• 공허한 진리, 공진리의 원리를 그리 깊이 고민하지 않아도 된다. 공진리는 단순히 인위적인 정의의 부산물에 불과하다.

• 만약 \(\Sigma\) 가 단일 원소 \(\sigma\) 로 이루어진 \(\{\sigma \}\) 라면 \(\{\sigma \} \vDash \tau\) 라고 표기하는 것보다 편하게 \(\sigma \vDash \tau\) 라고 표기한다.

• 즉, \(\Sigma\) 의 모든 유한 부분집합이 만족가능하면, \(\Sigma\) 도 만족가능하다는 것이다. 한편, 위상수학에 익숙하다면 이 정리가 콤팩트성 정리라고 불리는 것이 이해될 것이다. 이 정리가 특정 위상 공간에 대한 콤팩트성을 주장하는 것이기 때문이다. 이 정리는 곱공간(product space)에 대한 티호노프 정리(Tychonoff's theorem)로 증명가능하다.

• (집합 \(A\) 와 원소 \(t\) 의 합집합 \(A \cup \{t\}\) 을 \(A;t\) 로 정의했던 것을 기억하자.)

• 증명

Induction✔

수학과 논리학에서 자주 나타나는 특별한 종류의 구성법이 있다.

• \(U\) 가 식 집합이고, 초기 원소가 문장 기호이고, 적용될 연산이 \(\mathcal{E}_{\neg }\) 같은 식 구성 연산인 경우에서는 구성될 집합은 wff 집합이다.

• 가령 다음의 두 함수 \(f\)(이항연산), \(g\)(단항연산) 를 포함하는 함수 클래스 \(\mathcal{F}\) 가 연산 후보가 된다.

  \[ f: U \times U \to U, \qquad g : U \to U \]

  연산 \(f, g\) 에 대하여 \(S\) 가 닫혀있다는 것은 \(x, y \in S \implies f(x,y), g(x) \in S\) 라는 것이다.

  이때 \(\mathcal{F}\) 는 무한집합이어도 된다. \(\mathcal{F}\) 는 \(U\) 위의 관계 집합이 될 수도 있다.

• 예시

  초기 집합 \(B \subset U\) 가 원소 \(a, b\) 를 갖는다고 하고, 우리가 구성하려는 집합이 \(C\) 라고 하자. 그러면 \(C\) 는 가령, 다음의 원소들을 포함하게 될 것이다.

  \[ b, \quad f(b,b), \quad g(a), \quad f(g(a), f(b, b)) \]

• \(C ^{*}\) 가 귀납적이라는 것을 증명하는 것은 쉽다.

• 이 방식으로 가령, 정수를 구성할 수 있다. 실수 집합을 \(U\) 로 두고 초기 집합을 \(B = \{0\}\) 로 두고 두 연산을 \(S(x) = x+1, P(x) = x - 1\) 로 두면 \(C\) 는 다음과 같은 정수 집합이 된다.

  \[ C _{*} = \{\dots ,-1, 0, 1, \dots \} \]

• 이제 \(U\) 를 모든 식 집합으로 두고, \(B\) 를 문장 기호 집합으로 두고, \(\mathcal{F}\) 는 5개의 식 구성 연산으로 두면 \(C _{*}\) 는 모든 wff 집합이 된다.

• 두 방식으로 구성한 \(C ^{*}, C _{*}\) 가 \(C ^{*} = C _{*}\) 를 만족하는 것을 증명하는 것은 쉬운 일이다.

• 증명

  \(S\) 가 귀납적이므로 \(C = C ^{*} \subset S\) 이다. ■

• 이제 \(C\) 를 식 구성 연산에 의하여 문장 기호 집합으로부터 생성된 wff 집합이라고 생각하자. \(\alpha , \beta\) 는 \(\mathcal{E}_{\land }(\alpha , \beta ) = (\alpha \land \beta )\) 의 적절한 절편이다. 더욱 일반적으로 wff 의 구성 성분은 wff 의 적절한 절편이다.

• 예시

  우리가 문장 기호 \(\{A_2, A_3, A_5\}\) 와 논리 기호 \(\{\neg , \implies \}\) 로 이루어진 식을 특별하다고 했다고 하자. 그러면 귀납 원리는 모든 특별한 wff 가 \(\mathcal{E}_{\neg }, \mathcal{E}_{\implies }\) 에 의하여 \(\{A_2, A_3, A_5\}\) 로부터 생성된 \(C_s\) 에 포함된다는 것을 보장해준다.

Recursion✔

집합 \(U\), 부분집합 \(B \subset U\), 두 함수 \(f: U \times U \to U, g: U \to U\) 에 대하여 \(C\) 를 \(f, g\) 에 의하여 \(B\) 로부터 생성된 집합이라고 생각하자.

이제 \(B\) 위에 정의된 함수 \(h\) 를 \(C\) 로 확장시킨 함수 \(\bar{h}\) 를 다음과 같이 재귀적으로 정의하는 문제를 생각하자.

1. \(x \in B\) 에 대하여 \(\bar{h}(x)\) 에 대한 계산 규칙
2. \(\bar{h}(f(x, y))\) 에 대한 계산 규칙
3. \(\bar{h}(g(x))\) 에 대한 계산 규칙

이 조건을 만족하는 \(C\) 위의 함수 \(\bar{h}\) 는 존재하지 않을 수도 있다.

• 예시

  \(U = \R, B = \{0\}, f(x,y)=x \cdot y, g(x)=x+1\) 로 두면 \(C = \N\) 인데, \(\bar{h}\) 를 다음과 같이 두면 \(\bar{h}\) 는 존재하지 않는다.

  1. \(\bar{h}(0) = 0\)
  2. \(\bar{h}(f(x, y)) = f(\bar{h}(x), \bar{h}(y))\)
  3. \(\bar{h}(g(x)) = \bar{h}(x) + 2\)

  왜냐하면 \(\bar{h}(f(x, y)) = \bar{h}(f(1, 1)) = \bar{h}(1) = f(\bar{h}(1), \bar{h}(y)) = \{\bar{h}(1)\}^{2} \implies \bar{h}(1) = 1\) 인데, \(\bar{h}(g(x)) = \bar{h}(g(0)) = \bar{h}(1) = \bar{h}(0) + 2 = 2\) 이기 때문이다.

이제 자유롭게 생성되었다는 개념을 정의하자.

• 이 정리는 \(C\) 가 자유롭게 생성되었다면 \(B\) 위의 함수 \(h\) 가 반드시 \(C\) 위의 확장 \(\bar{h}\) 를 갖는다는 것을 보장해준다.

• 증명

• 예시

  연산 \(S(x) = x+1\) 만을 갖는 \(B = \{0\}\) 로부터 생성된 \(C\) 는 \(C = \N\) 이다. \(S\) 는 단사이고 치역에 \(0\) 가 포함되어 있지 않으므로 \(C\) 는 자유롭게 생성된 것이다. 그러면 재귀 정리에 의하여 임의의 집합 \(V\), 임의의 \(a \in V\), 임의의 \(F:V \to V\) 에 대하여 다음을 만족하는 \(\bar{h}: \N \to V\) 가 유일하게 존재한다.

  \[ \begin{align}\begin{split} &\bar{h}(0) = a \\ &\forall x \in \N : \bar{h}(S(x)) = F(\bar{h}(x)) \\ \end{split}\end{align} \tag*{} \]

• 예시

  wff 들은 5개의 식 구성 연산에 의하여 문장 기호로부터 자유롭게 생성되었다.

• 증명

• 이제 진리할당 \(v\) 를 \(\bar{v}\) 로 확장시키는 문제를 생각하자. 먼저 \(v\) 가 모든 문장 기호 집합에 대한 진리 할당인 경우를 생각하자. 그러면 URT 와 재귀 정리에 의하여 wff 집합에 대한 유일한 확장 \(\bar{v}\) 가 존재한다.

  이제 일반적으로 \(v\) 가 문장 기호 집합 \(S\) 에 대한 진리 할당이라고 생각하자. \(\bar{S}\) 는 URT 에 의하여 식 구성 연산에 의하여 \(S\) 로부터 자유롭게 생성된다. 그러면 재귀 정리에 의하여 \(\bar{S}\) 에 대한 유일한 확장 \(\bar{v}\) 가 존재한다.

Completeness✔

우리는 지금까지 5개의 명제 연결사(\(\neg ,\land ,\lor ,\implies ,\iff\))만을 사용해왔다. 그런데 다른 연결사를 추가하면 체계에 더 이득이 있지는 않을까? 한편, 연결사 중 하나를 제거하면 체계에 어떤 손실이 있을까? 이 문제를 설명하는 체계의 속성을 완전성(Completeness)이라고 한다.

• 예시

  \(\alpha = A_1 \land A_2\) 는 \(\{A_1, A_2\}\) 에 대한 \(2 ^{2}\) 줄의 진리표로 구성된 진리할당을 갖는 불 함수이다. 각 \(2 ^{2}\) 개의 쌍 \(\overrightarrow{X}\) 에 대하여 \(B _{\alpha }(\overrightarrow{X})\) 를 \(\alpha\) 의 진리값으로 정의하면 \(B _{\alpha }(T, T) = T\) 인 경우를 제외한 나머지는 \(F\) 가 된다.

• \(A_1, A_2, \dots, A_n\) 에 대하여 주어진 진리값 \(X_1, X_2, \dots, X_n\) 에 대하여 \(B _{\alpha}^{n}(X_1, X_2, \dots, X_n)\) 는 진리값을 부여받는다. 이것은 각 \(v(A_i) = X_i\) 에 대한 진리 할당 \(v\) 에 대하여 \(B _{\alpha}^{n}(X_1, X_2, \dots, X_n) = \bar{v}(\alpha )\) 가 된다는 것이다.

• 이 정리는 wff 를 불 함수로 보면 wff 에 대한 항진적으로 동등한 wff 를 알 수 있다는 것을 말해준다.

  이 정리 덕분에 wff 의 항진적 동치를 밝히기 위하여 형식 언어에 집착하지 않아도 불 함수를 다루기만 하면 된다.

• 증명

  1:

  \(\alpha \vDash \beta\) 는 \(A_1, A_2, \dots, A_n\) 에 대한 모든 \(2 ^{n}\) 개의 진리 할당 \(v\) 에 대하여 \(\bar{v}(\alpha ) = T \implies \bar{v}(\beta ) = T\) 인 것과 동치이다.

  이 사실은 임의의 \(n\)-튜플 \(\overrightarrow{X}\) 에 대하여 \(B _{\alpha}^{n}(\overrightarrow{X}) = T \implies B _{\beta}^{n}(\overrightarrow{X}) = T\) 인 것과 동치이다.

  이 사실은 임의의 \(n\)-튜플 \(\overrightarrow{X}\) 에 대하여 \(B _{\alpha}^{n}(\overrightarrow{X}) \leq B _{\beta}^{n}(\overrightarrow{X})\) 인 것과 동치이다.

• 이 정리는 모든 wff 가 불 함수로 구현될 수 있음을 말해준다. 불 함수를 구현하는 wff 는 유일하지 않다. 항진적 동치인 wff 들은 모두 똑같은 불 함수를 구현하기 때문이다.

• 증명

  \(G\) 가 \(F\) 에 대한 상수 함수이면 \(\alpha = A_1 \land \neg A_1\) 이다. ▲

  가령 \(G\) 가 다음과 같은 3항 불 함수라고 해보자.

  \[ \begin{align}\begin{split} G(F, F, F) &= F , \qquad G(F, F, T) = T, \\ G(F, T, F) &= T , \qquad G(F, T, T) = F, \\ G(T, F, F) &= T , \qquad G(T, F, T) = F, \\ G(T, T, F) &= F , \qquad G(T, T, T) = T \\ \end{split}\end{align} \tag*{} \]

  그러면 \(G\) 는 다음의 경우에 \(T\) 를 갖는다.

  \[ \begin{align}\begin{split} FFT&\quad \neg A_1 \land \neg A_2 \land A_3 \\ FTF&\quad \neg A_1 \land A_2 \land \neg A_3 \\ TFF&\quad A_1 \land \neg A_2 \land \neg A_3 \\ TTT&\quad A_1 \land A_2 \land A_3 \\ \end{split}\end{align} \tag*{} \]

  우측의 항들을 다음과 같이 결합하면 \(\alpha\) 를 얻는다.

  \[ \begin{align}\begin{split} & (\neg A_1 \land \neg A_2 \land A_3) \lor (\neg A_1 \land A_2 \land \neg A_3) \lor \\ & (A_1 \land \neg A_2 \land \neg A_3) \lor (A_1 \land A_2 \land A_3) \\ \end{split}\end{align} \tag*{} \]

  이제 일반적으로 다음과 같은 \(k >0\) 개의 점에서 \(T\) 를 갖는 \(G\) 를 생각하자.

  \[ \begin{align}\begin{split} \overrightarrow{X}_1 &= \left< X _{11}, X _{12}, \dots , X _{1n} \right> \\ \overrightarrow{X}_2 &= \left< X _{21}, X _{22}, \dots , X _{2n} \right> \\ &\vdots \\ \overrightarrow{X}_k &= \left< X _{k1}, X _{k2}, \dots , X _{kn} \right> \\ \end{split}\end{align} \tag*{} \]

  그러면

  \[ \begin{align}\begin{split} \beta _{ij}&= \begin{cases} A_j & X _{ij} = T\\ \neg A_j & X _{ij} = F\\ \end{cases} \\ \gamma _i &= \beta _{i1} \land \dots \land \beta _{in} \\ \alpha &= \gamma _1 \lor \gamma _2 \lor \dots \lor \gamma _k \end{split}\end{align} \tag*{} \]

  와 같이 두면 \(G = B _{\alpha }^{n}\) 이 된다. 그러면 \(1 \leq i \leq k\) 에 대하여 \(B _{\alpha}^{n}(\overrightarrow{X}_i) = T\) 이다. 반대로, \(k\) 개의 진리 할당만이 \(\alpha\) 를 만족하므로 다른 \(2 ^{n} - k\) 개의 \(n\)-튜플 \(\overrightarrow{Y}\) 에 대해서는 \(B _{\alpha}^{n}(\overrightarrow{X}) = F\) 이다. 그러므로 \(B _{\alpha}^{n}(\overrightarrow{Y}) = G(\overrightarrow{Y})\) 가 된다. ■

• 이제 우리는 논리 연결사가 충분하다는 결론을 내릴 수 있다. 만약 새로운 논리 연결사를 추가하여 언어를 확장했다고 해보자. 확장된 언어의 wff \(a\) 는 불 함수 \(B _{a}^{n}\) 을 구현한다. 그러면 이 정리에 의하여 \(B _{a}^{n} = B _{\alpha}^{n}\) 인 wff \(\alpha\) 가 존재한다. 정리 15A 에 의하여 \(a\) 과 \(\alpha\) 는 항진적 동치이다.

  또한, 이 정리는 \(\beta _{ij}\) 를 \(\land\) 로 연결한 \(\gamma_i\) 를 \(\lor\) 로 연결한 특별한 형태로 wff \(\alpha\) 를 표현할 수 있다는 것을 말해준다. 이 형태를 논리합 정규형(disjunctive normal form)이라고 한다.

• 다음과 같은 \(\alpha\) 가 논리합 정규형이다.

  \[ \begin{align}\begin{split} \gamma _i &= \beta _{i1} \land \dots \land \beta _{in} \\ \alpha &= \gamma _1 \lor \gamma _2 \lor \dots \lor \gamma _k \end{split}\end{align} \tag*{} \]

• 그러므로 모든 함수 \(G: \{F,T\}^{n} \to \{F,T\}\) 를 오직 \(\{\land , \lor ,\neg \}\) 으로 wff 로 만들 수 있으므로 집합 \(\{\land , \lor ,\neg \}\) 는 완전하다.

• 증명

  \(\{\neg , \land ,\lor \}\) 를 사용하는 wff \(\alpha\) 가 \(\{\neg , \land \}\) 를 사용하는 wff \(\alpha'\) 와 항진적으로 동등하다는 것은 다음과 같은 드모르간의 법칙에 의하여 쉽게 보일 수 있다.

  \[ \beta \lor \gamma \vDash \Dashv \neg (\neg \beta \land \neg \gamma ) \]

  이것을 사용하여 \(\lor\) 를 완벽하게 제거할 수 있다. 그러므로 \(\{\neg , \land \}\) 도 완전하다. ▲

  \(\{\neg ,\lor \}\) 의 완전성도 쉽게 보일 수 있다. ■

• 즉, 임의의 \(v\) 에 대하여 \(\bar{v}(\bot ) = F\) 가 된다. \(A \implies \bot\) 이 wff 이면 이것의 항진적 동치는 \(\neg A\) 이다.

Compactness✔

• wff 집합 \(\Sigma\) 가 유한집합일 때는 자명하지만, 무한집합일 때 \(\Sigma\) 의 모든 유한 부분집합이 만족가능하다고 해서 \(\Sigma\) 까지 만족가능하다는 것은 자명하지 않다.

• 증명

• 증명

First-Order Logic✔

• 명제 논리가 인간의 연역적 생각의 첫번째 수학적 모델이지만, 이것은 너무 단순하여 인간의 생각을 제대로 표현할 수 없어서 쓸모가 없다. 하지만 1차 논리는 명제 논리보다 강력하며, 수론을 구성할 수 있을 정도이다.

• 동등 기호 \(=\) 는 언어마다 채택될 수도 있고 채택되지 않을 수도 있다. 상수 기호는 0항 함수 기호로 볼 수도 있다.

• 중요한 사실은 이 1차 언어의 개념이 집합론의 언어를 포함한다는 것이다. 이것은 수학 전체가 집합론 안으로 매장될 수 있다는 것을 의미한다. 즉, 다음이 성립한다.

  1. 미적분의 기본정리 같은 수학의 명제는 집합론의 언어로 표현 된다.
  2. 수학의 정리는 집합론 공리로부터 논리적으로 도출된다.

• 예시

  1차 논리 언어는 다음과 같은 것들이 있다.

  • 순수 술어 언어(Pure predicate language)

    동등기호: 없음

    n항 술어 기호: \(A _{1}^{n}, A _{2}^{n},\dots\)

    상수 기호: \(A_1, A_2, \dots\)

    n항 함수 기호: 없음

  • 집합론 언어(Language of set theory)

    동등기호: 있음

    술어 파라미터: 2항 술어 기호 \(\in\)

    함수 기호: 없음(상수 기호 \(\varnothing\) 을 0항 함수로 볼 수 있음)

  • 수론 언어(Language of elementary number theory)

    동등기호: 있음

    술어 파라미터: 2항 술어 기호 \(<\)

    상수 기호: \(0\)

    1항 함수 기호: \(S\)(successor 연산)

    2항 함수 기호: \(+, \cdot , E\) (각각 덧셈, 곱셈, 제곱)

Formula✔

• 식은 단순한 기호의 나열이므로 대부분의 식은 무의미하다. 하지만 항(term)과 wff 는 유의미하다.

• 수학의 항은 언어에서의 명사와 대명사이다. 항은 대상의 이름을 짓는 것으로 해석되는 식이다.

• 항은 상수기호나 변수이거나 함수 기호에 상수 기호나 변수를 접붙여서 만들어진 식이다. 그래서 함수 기호가 없으면 항은 단지 상수기호나 변수가 된다.

• 원자식은 명제논리에서 문장기호의 역할을 한다.

• 예시

  수론의 언어에 2항 술어 기호 \(=\) 와 항 \(v_1,v_2\) 에 대하여 \(v_1 = v_2\) 는 원자식이다. 집합론의 언어에서 \(v_5 \in v_3\) 도 원자식이다. 함수 기호가 있을 때 항이 귀납적으로 정의될 수 있는 반면, 원자식은 귀납적으로 정의되지 않는다.

• 정형논리식은 원자식에 연결 기호나 양화 기호를 사용하여 얻은 식이다. 즉, 식 구성 연산으로 정의하면 wff 는 다음과 같다.

  \[ \begin{align}\begin{split} \mathcal{E}_{\neg }(\gamma ) &= (\neg \gamma ) \\ \mathcal{E}_{\implies}(\gamma , \delta) &= (\gamma \to \delta ) \\ \mathcal{Q}_i(\gamma ) &= \forall v_i \gamma \\ \end{split}\end{align} \tag*{} \]

• 그러므로, 가령, \(\neg v_3\) 은 wff 가 아니다. 원자식에 \(\mathcal{E}_{\neg }\) 을 적용한 게 아니라 항에 적용하여 얻은 식이기 때문이다.

• 예시

  \(\forall v_2 (v_1 \in v_2)\) 에서 \(v_1\) 은 자유변수이다.

• 자유변수를 wff \(\alpha\) 에 대하여 다음과 같이 귀납적으로 정의하자.

  1. 원자식 \(\alpha\) 에 대하여 \(x\) 가 \(\alpha\) 의 자유변수인 것은 \(x\) 가 \(\alpha\) 에 나타난 것이다.
  2. \(x\) 가 \(\neg \alpha\) 의 자유변수인 것은 \(x\) 가 \(\alpha\) 에서 자유변수인 것이다.
  3. \(x\) 가 \(\alpha \to \beta\) 의 자유변수인 것은 \(x\) 가 \(\alpha\) 나 \(\beta\) 에서 자유변수인 것이다.
  4. \(x\) 가 \(\forall v_i \alpha\) 의 자유변수인 것은 \(x\) 가 \(\alpha\) 의 자유변수이고 \(x \neq v_i\) 인 것이다.

Truth and Models✔

• 명제 논리에서 진리 할당이 문장 기호를 참이나 거짓으로 해석해주었다면, 1차 논리에서는 구조가 그 역할을 한다. 구조는 해석이라고도 한다.

• 1차 논리에서 구조는 다음을 말해준다.

  1. 보편양화기호 \(\forall\) 이 어떤 대상의 모임을 지칭하는지
  2. 다른 파라미터(술어나 함수기호)가 무엇을 지칭하는지

• \(\mathfrak{A}\) 은 파라미터에 의미를 부여한다. \(\forall\) 은 "\(\left| \mathfrak{A} \right|\) 의 모든 것" 를 의미하게 되고, 기호 \(c\) 는 점 \(c ^{\mathfrak{A} }\) 의 이름을 지정하는 것이다. 원자식 \(P t_1t_2\dots t_n\) 은 점 \(t_1, t_2, \dots, t_n\) 의 \(n\)-튜플의 관계 \(P ^{\mathfrak{A} }\) 을 의미하게 된다.

• 예시

  \(\in\) 만을 파라미터로 갖는 집합론의 언어에서 다음과 같은 구조 \(\mathfrak{A}\) 를 취하자.

  \[ \begin{align}\begin{split} \left| \mathfrak{A} \right|&= \N \\ \in ^{\mathfrak{A} }&= \{\left< m, n \right> : m < n\}\\ \end{split}\end{align} \tag*{} \]

  구조는 형식 언어를 자연어로 해석해주고, 이에 따라 참인지 거짓인지 결정가능하게 해준다. 다음과 같은 1차 논리 문장은 이 해석에서 참이다.

  \[ \exists x (\forall y (\neg (y \in x))) \]

  이 문장은 공집합의 존재성을 주장하고 있으므로 자연어 "최소 자연수가 존재한다" 로 번역될 수 있으며, 이는 참이다. 이 상황을 이 문장이 \(\mathfrak{A}\) 에서 참이다, 또는 \(\mathfrak{A}\) 가 문장의 모델(model)이다라고 한다.

  반면 \(\mathfrak{A}\) 은 다음 문장에 대한 모델이 아니다.

  \[ \forall x \forall y \exists z \forall t(t \in z \iff t = x \lor t = y) \]

  \(\mathfrak{A}\) 에서 이 문장의 해석이 거짓이 되기 때문이다. 왜냐하면 임의의 \(n\) 에 대하여 다음을 만족하는 자연수 \(m\) 이 존재하지 않기 때문이다.

  \[ n < m \quad\text{iff}\quad n = 1 \]

이렇게 형식 언어의 어떤 문장은 구조 속에서 참이고 어떤 문장은 거짓이 된다. 이제 "어떤 문장이 구조 속에서 참이다" 라는 것의 엄밀한 수학적 정의를 내려보자. 즉, "문장 \(\sigma\) 이 구조 \(\mathfrak{A}\) 속에서 참이다" 라는 자연어를 수학의 세계로 격하시켜보자. 먼저 이것을 다음과 같은 기호로 표현하자.

이것을 정의하기 위하여 wff 에 관련된 일반적인 개념들을 정의해보자.

• \(s(x|d)\) 는 다음과 같이 정의된다.

  \[ s(x|d)(y) = \begin{cases} s(y) & y \neq x\\ d & y = x\\ \end{cases} \]

  이 만족에 대한 정의는 wff 가 유일한 분해를 가진다는 사실과 재귀 정리를 적용한 결과이다.

• 예시

  언어가 파라미터 \(\forall\), 2항 술어 기호 \(P\), 단항 함수 기호 \(f\), 상수 기호 \(c\) 를 가진다고 하고, 언어의 구조 \(\mathfrak{A}\) 를 다음과 같이 정의하자.

  \[ \begin{align}\begin{split} \left| \mathfrak{A} \right|&= \N \\ P ^{\mathfrak{A} }&= \{\left< m,n \right>:m \leq n\}\\ f ^{\mathfrak{A} }&= S \quad\text{(successor)}\quad \\ c ^{\mathfrak{A} }&= 0 \end{split}\end{align} \tag*{} \]

  그러면 구조 \(\mathfrak{A}\) 를 다음과 같이 쓸 수 있다.(successor \(S\) 란 1 을 더하는 연산이다)

  \[ \mathfrak{A} = (\N;\leq ,S,0) \]

  이제 함수 \(s: V \to \N, v_i \mapsto i-1\) 를 취하면 \(s(v_1) = 0, s(v_2) = 1\) 와 같이 된다. \(s\) 는 변수를 \(\left| \mathfrak{A} \right| = \N\) 로 보내는 단순한 함수이므로 이것을 항으로 확장한 함수 \(\bar{s}:T \to \N\) 을 사용해야 한다.

  이제 본격적으로 1차 논리 형식 언어의 무의미한 기호의 나열에 불과한 것들에 의미를 부여하고 참거짓을 해석해보자.

  1. \(\bar{s}(ffv_3) = f ^{\mathfrak{A}}(f ^{\mathfrak{A}}(\bar{s}(v_3))) = S(S(2)) = 4\) 이고 \(\bar{s}(fv_1) = S(0) = 1\) 이다.
  2. \(\bar{s}(c) = 0\) 이고 \(\bar{s}(ffc) = 2\) 이다.
  3. \(\vDash _{\mathfrak{A}} Pcfv_1[s]\) 는 \(\left< \bar{s}(c), \bar{s}(fv_1) \right> = \left< 0,1 \right> \in P ^{\mathfrak{A}}\) 라는 것이다. 이것은 \(0 \leq 1\) 라고 해석되고, 명백히 참이다. \(0 \leq 1\) 라는 초등학교 때 나오는 간단한 수식의 옷을 벗겨보면 이런 복잡한 형식 언어가 나온다.
  4. \(\vDash _{\mathfrak{A}}\forall v_1Pcv_1\) 는 \(0\) 이 임의의 자연수와 같거나 작다고 해석되며, 당연히 참이다.

• 사실, 구조 \(\mathfrak{A}\) 가 \(s\) 로 wff \(\varphi\) 를 만족하는지 검증할 때 \(s\) 가 제공하는 무한한 정보 전부가 필요한 것은 아니다. 왜냐하면 \(\varphi\) 의 자유변수에서의 함수 \(s\) 의 값만 상관하면 되기 때문이다. 실제로 \(\varphi\) 가 문장이면 \(s\) 를 전혀 상관하지 않아도 된다.

• 증명

• 이 정리는 구조에서도 비슷하게 성립한다. 즉, 구조 \(\mathfrak{A}, \mathfrak{B}\) 가 \(\varphi\) 에서 나타나는 모든 파라미터에서 같다면, 다음이 성립한다.

• 이 정의는 정리 22A 를 기반으로 \(s(v_i) = a_i\) 를 만족하는 임의의 함수에 대한 정의이다.

• \(\left| \mathfrak{A} \right|\) 가 공집합이 아니므로 두 경우 모두 성립할 수 없다. 또한 문장에는 자유변수가 없으므로 두 경우의 중간의 경우는 없다.

• 따름정리 22B 의 1) 의 경우가 성립하면 \(\mathfrak{A}\) 를 \(\sigma\) 의 모델이라고 정의하는 것이다. 따름정리 22B 의 2) 의 경우가 성립하는 경우에서는 단지 \(\sigma\) 가 \(\mathfrak{A}\) 에서 거짓이라고 한다.

• \(\mathfrak{A}\) 가 문장 집합 \(\Sigma\) 의 모델이라는 것은 그것이 \(\Sigma\) 의 모든 원소에 대하여 모델이라는 것이다.

• 예시

  구조 \(\mathfrak{R}\) 을 실수체 \((\R; 0, 1, +, \cdot )\) 로 두고, 구조 \(\mathfrak{Q}\) 를 유리수체 \((\Bbb{Q};0,1,+,\cdot )\) 로 두자.

  \(\sqrt[]{2}\) 의 존재성을 주장하는 문장 \(\exists x(x \cdot x = 1 + 1)\) 은 유리수체 구조에서 거짓이지만, 실수체 구조에서는 참이다.

  그러므로 \(\mathfrak{R}\) 이 문장 \(\exists x(x \cdot x = 1 + 1)\) 의 모델이다.

Logical Implication✔

이제 언어의 논리적 함의를 정의할 수 있다.

• \(\Gamma\) 가 참일 때 \(\varphi\) 도 참이라는 말이다.

• 예시

  논리적 함의의 예시는 다음과 같다.

  1. \(\forall v_1 Q v_1 \vDash Qv_2\)
  2. \(Q v_1 \not \vDash \forall v_1 Q v_1\)
  3. \(\vDash \neg \neg \sigma \implies \sigma\)
  4. \(\forall v_1 Q v_1 \vDash \exists v_2 Q v_2\)
  5. \(\exists x \forall y Pxy \vDash \forall y \exists x Pxy\)
  6. \(\forall y \exists x Pxy \not \vDash \exists x \forall y Pxy\)
  7. \(\vDash \exists x(Qx \implies \forall xQx)\)

• 명제 논리의 항진적 함의처럼 \(\{\gamma \} \vDash \varphi\) 대신 편하게 \(\gamma \vDash \varphi\) 라고 쓰고, \(\varphi \vDash \psi\) 와 \(\psi \vDash \varphi\) 인 것을 \(\varphi \vDash \Dashv \psi\) 로 표기한다.

• wff \(\varphi\) 가 \(\varnothing \vDash \varphi\) 를 만족하면 \(\varphi\) 가 타당하다(valid)고 하고, \(\vDash \varphi\) 라고 표기한다. 즉, 임의의 구조 \(\mathfrak{A}\) 와 임의의 \(s: V \to \left| \mathfrak{A} \right|\) 에 대하여 \(\mathfrak{A}\) 가 \(s\) 로 \(\varphi\) 를 만족하면 \(\varphi\) 가 타당하다고 하는 것이다.

• 문장에 대하여 논리적 함의를 정리 22A 를 적용하여 더욱 엄밀하게 정의할 수 있다.

• 정리 22A 의 따름정리이다.

• 타당한 문장은 명제 논리의 항진식의 역할을 한다.

• 논리적 함의가 명제 논리의 항진적 함의와 비슷해보이지만 복잡도에서 큰 차이가 있다. 명제 논리에서 wff \(\alpha\) 가 항진식임을 보이기 위해서는 유한한 진리 할당과 유한한 함수를 유한번 계산하면 된다. 하지만 1차 논리 언어의 wff \(\varphi\) 가 타당한지 검증하려면 모든 구조 \(\mathfrak{A}\) 에 대하여 각 함수 \(s:V \to \left| \mathfrak{A} \right|\) 를 검증해야 한다. 이때 \(\left| \mathfrak{A} \right|\) 는 무한집합일 수 있다.

  복잡성의 관점에서 타당한 식 집합을 결정불가능하다는 것은 놀라운 사실이 아니다. 놀라운 사실은 타당성(validity)이 유한성과 관련되어 있는 연역가능성(deducibility) 같은 다른 개념들과 동등하다는 것이다. 이 동등성으로 타당한 wff 집합 같은 타당성 집합들이 효과적으로 열거가능하다(effectively enumerable)는 것을 보일 수 있다.

• 증명

Definability in a Structure✔

• 예시

  동등성을 가진 언어가 상수 기호 \(\mathbf{ 0, 1}\) 과 이항 함수 기호 \(+, \cdot\) 를 가질 때, 실수체를 구조 \(\mathfrak{R} = (\R; 0, 1, + ,\cdot)\) 로 취할 수 있다.

  언어에 순서 기호 \(<\) 가 없지만 \(x \geq 0\) 를 표현할 방법이 있다. 왜냐하면 이 구조 안에서 음이 아닌 원소는 제곱근을 갖는 원소이기 때문이다. 그러므로 식 \(\exists v_2 x = v_2 \cdot v_2\) 는 구조 \(\mathfrak{R}\) 안에서 \(x\) 에 음이 아닌 숫자가 할당될 때 만족된다. 그리고 다음이 성립한다.

  \[ \vDash _{\mathfrak{R}} \exists v_2 v_1 = v_2 \cdot v_2 \llbracket a \rrbracket \iff a \geq 0 \]

  그러므로 구간 \([0, \infty)\) 을 \(\mathfrak{R}\) 에서 정의가능하다(definable). 왜냐하면 식 \(\exists v_2 v_1 = v_2 \cdot v_2\) 가 모든 음이 아닌 수를 정의하기 때문이다.

  다음과 같이 표현되는 식 \(v_1 \leq v_2\) 에 의하여 구조 \(\mathfrak{R}\) 에서 이항 관계 \(\{\left< a, b \right> \in \R \times \R | a \leq b\}\) 같은 실수 위의 순서 관계가 정의된다. 그러므로 \(<\) 같은 순서 기호를 언어 자체에 추가할 필요는 없다.

  \[ \exists v_3 v_2 = v_1 + v_3 \cdot v_3 \]

• 예시

  유향 그래프 \(\mathfrak{A} = (\{a,b,c\}; \{\left< a,b \right>, \left< a,c \right>\})\) 를 생각해보자. 이 구조는 다음과 같은 유향 그래프를 뜻하며, \(\forall\) 과 \(E\) 를 파라미터로 갖는다.

  

  \(E\) 는 노드와 노드를 잇는 선(Edge)이 존재한다는 관계기호이다. 따라서 \(\mathfrak{A}\) 에서 관계 \(E ^{\mathfrak{A}}\) 에 포함되는 집합 \(\{b,c\}\) 는 며, 식 \(\exists v_2 Ev_2v_1\) 에 의하여 정의된다. 반면 집합 \(\{b\}\) 는 정의 불가능하다. \(b\) 와 \(c\) 를 분리하여 이 집합을 정의할 수 있는 속성이 없기 때문이다.

• 예시

  수론의 언어의 부분을 상정하자. 이 언어가 파라미터 \(\forall , \mathbf{ 0, S, +, \cdot}\) 을 갖는다고 하고, 다음과 같은 구조 \(\mathfrak{N} = (\N; 0, S, +, \cdot )\) 를 정의하자.

  \[ \begin{align}\begin{split} \left| \mathfrak{N} \right|&= \N \\ \mathbf 0 ^{\mathfrak{N}} &= 0 \in \N \quad\text{(zero)}\quad \\ \mathbf S ^{\mathfrak{N}} &= S \quad\text{(successor)}\quad \\ + ^{\mathfrak{N}} &= + \quad\text{(addition)}\quad \\ \cdot ^{\mathfrak{N}} &= \cdot \quad\text{(multiplication)}\quad \\ \end{split}\end{align} \tag*{} \]

  좌측 항이 언어가 갖고 있는 무의미한 형식기호에 불과한 파라미터들이고, 우측 항들이 구조가 부여하는 의미들이다. 가령 구조 \(\mathfrak{N}\) 이 \(\mathbf 0 ^{\mathfrak{N}}\) 에 실제 자연수 \(0 \in \N\) 을 부여함으로써 비로소 언어의 의미없는 형식기호 파라미터 \(\mathbf 0\) 이 영(zero)이라는 의미를 얻는다.

  \(\N\) 에서 어떤 관계는 정의가능하지만 어떤 것은 불가능하다. 왜냐하면 \(\N\) 위의 모든 관계는 비가산이지만, 그것을 정의할 수 있는 식은 가산 무한이기 때문이다.

  1. 순서 관계 \(\{\left< m,n \right> | m < n\}\) 은 \(\mathfrak{N}\) 에서 다음의 식에 의하여 정의된다.

     \[ \exists v_3 v_1 + \mathbf Sv_3 = v_2 \]

  2. 임의의 자연수 \(n\) 에 대한 \(\{n\}\) 은 다음의 식에 의하여 정의가능하다.

     \[ v_1 = \mathbf{ \overbrace{ SS \dots S}^{n}0 }\]

  그러므로 언어에 파라미터 \(<\) 이나 각 자연수 \(\mathbf n\) 을 추가할 필요가 없다. 왜냐하면 정의 가능하기 때문이다.

• 지금까지 수학 공부를 해왔다면 수학 교재나 수학 교수가 수학적 대상을 정의할 때 이렇게 말했을 것이다. "그래프의 정의는 비어있지 않은 집합 \(V\) 와 집합 \(E\) 로 구성되어...", "군의 정의는 비어있지 않은 집합 \(G\) 와 이항연산 \(\cdot\) 과 다음의 공리를...", "벡터공간의 정의는 비어있지 않은 집합 \(V\) 와 이항 연산 \(+\) 와 스칼라 곱 \(\cdot\) 과 다음을 만족하는..."

  이제 이 정의 자체를 추상화시킬 차례이다. 이 수학적 대상들은 언어에 적합한 구조들이다. 이때 구조는 공리(axiom)라고 불리는 특정 문장들의 집합 \(\Sigma\) 를 만족해야 한다. 그러므로 공리 집합 \(\Sigma\) 를 만족하는 모델을 찾아야 한다.

• 예시

  동등성과 이항 술어 기호 \(E\) 에 대한 파라미터 \(\forall , E\) 를 갖는 언어에서 그래프는 비어있지 않은 꼭지점(vertex, node) 집합과 간선(edge) 관계 \(E ^{\mathfrak{A}}\) 에 대한 \(V\) 구조 \(\mathfrak{A} = (V; E ^{\mathfrak{A}})\) 이다. 이때 간선은 \(uE ^{\mathfrak{A}}v \implies v E ^{\mathfrak{A}}u\) 와 같이 대칭적이어야 하고 \(\neg v E ^{\mathfrak{A}}v\) 와 같이 비반사적이어야 한다. 이 공리의 대칭성과 비반사성을 다음과 같은 문장으로 표현할 수 있다.

  \[ \forall x(\neg xEx \land \forall y(x Ey \implies yEx)) \]

  그러므로 모든 그래프의 클래스는 기본 클래스이다.

  유향 그래프에서는 대칭성 공리가 제거되며, 루프가 허용된 그래프에서는 비반사성 공리까지 제거된다.

• 예시

  동등성과 이항 술어 기호 \(P\) 에 대한 파라미터 \(\forall , P\) 를 갖는 언어에서 공집합이 아닌 집합 \(A\) 와 \(A\) 위의 이항 관계 \(R\) 에 대한 구조 \((A; R)\) 를 생각하자. 구조 \((A; R)\) 이 순서 집합(ordered set)이라는 것은 \(R\) 이 추이적이고 \(a, b \in A\) 에 대하여 \(\left< a,b \right> \in R, a = b, \left< b,a \right> \in R\) 중 하나가 성립한다는 삼분조건을 만족한다는 것이다. 이 공리는 다음 문장의 결합인 \(\tau\) 로 표현할 수 있으므로 비어있지 않은 순서 집합 클래스는 기본 클래스이다.

  \[ \begin{align}\begin{split} &\forall x \forall y \forall z (xPy \implies yPz \implies xPz) \\ &\forall x \forall y (xPy \lor x = y \lor y P x) \\ &\forall x \forall y (xPy \implies \neg yPx) \\ \end{split}\end{align} \tag*{} \]

• 예시

  동등성과 파라미터 \(\mathbf{\forall , 0, 1, + , \cdot }\) 을 가지는 언어에서 체(field)도 구조이다. 모든 체의 클래스도 기본 클래스이다. 지표가 \(0\) 인 체의 클래스는 \(\text{EC}_{\Delta }\) 이다.

Homomorphisms✔

• 그래프나, 벡터공간이나, 위상공간에서 두 구조 \(\mathfrak{A},\mathfrak{B}\) 가 동형(isomorphic)이라는 표현을 사용한다. 러프하게, 이는 두 전체 \(\left| \mathfrak{A} \right|, \left| \mathfrak{B} \right|\) 사이에 연산과 관계를 보존하는 전단사 대응이 존재한다는 것이다. 서로 동형인 구조는 서로 동일하지는 않지만 모든 똑같은 수학적 속성을 공유한다.

  조건 1) 과 2) 가 \(h\) 가 관계와 함수를 보존한다는 것을 말해준다.

• 예시

  벡터공간의 준동형사상(선형변환)

• 예시

  파라미터 \(\forall , +, \cdot\) 을 갖는 언어에서 자연수를 의미하는 구조 \(\mathfrak{A} = (\N; +, \cdot )\) 와 다음과 같은 연산이 정의된 구조 \(\mathfrak{B} = (\{e,o\} ; + , \cdot )\) 은 준동형이다.

  \[ \begin{align}\begin{split} e + ^{\mathfrak{B}} e &= e \qquad e \cdot ^{\mathfrak{B}} e = e \\ e + ^{\mathfrak{B}} o &= o \qquad e \cdot ^{\mathfrak{B}} o = e \\ o + ^{\mathfrak{B}} e &= o \qquad o \cdot ^{\mathfrak{B}} e = e \\ o + ^{\mathfrak{B}} o &= e \qquad o \cdot ^{\mathfrak{B}} o = o \\ \end{split}\end{align} \tag*{} \]

  왜냐하면 다음과 같은 준동형사상 \(h: \N \to \{e,o\}\) 가 존재하기 때문이다.

  \[ h(n) = \begin{cases} e &\text{n 이 짝수}\\ o &\text{n 이 홀수}\\ \end{cases} \]

  이 \(h\) 에서는 가령 홀수 \(a, b\) 대하여 다음이 성립하므로 준동형사상 조건 2)가 만족된다.

  \[ h(a + b) = e, \qquad h(a) + ^{\mathfrak{B}} h(b) = o + ^{\mathfrak{B}} o = e \]

• 예시

  벡터공간의 동형사상

  위상동형사상

• 예시

  양의 정수 집합 \(\Bbb{P}\) 와 순서 관계 \(<_P\), 그리고 자연수 집합 \(\N\) 과 순서관계 \(<_N\) 를 생각하자. 구조 \((\Bbb{P}; <_P)\) 에서 구조 \((\N; <_N)\) 로 가는 동형사상 \(h\) 이 존재한다. \(\Bbb{P} = \{1, 2, \dots \}\) 이고 \(\N = \{0, 1, 2, \dots \}\) 이니 만큼 \(h(n) = n - 1\) 로 정의해도 되고, 아예 \(h(n) = n\) 로 정의하여 \(h\) 를 항등함수로 정의해도 동형사상이 된다. (자연수 집합 \(\N\) 은 수학에서 엄밀하게 정의할 때 \(0\) 을 포함한다.)

  이렇게 구조 \((\Bbb{P}; <_P)\) 에서 구조 \((\N; <_N)\) 로 가는 동형사상이 존재하면 구조 \((\Bbb{P}; <_P)\) 를 구조 \((\N; <_N)\) 의 부분구조(substructure)라고 한다.

• \(\mathfrak{A}\) 가 \(\mathfrak{B}\) 의 부분구조이면, \(\left| \mathfrak{A} \right|\) 는 언어의 임의의 함수 기호 \(f\) 에 대한 \(f ^{\mathfrak{B}}\) 에 대하여 닫혀있어야 한다. 이때 \(\overrightarrow{a} \in \left| \mathfrak{A} \right|^{n}\) 에 대하여 \(f ^{\mathfrak{B}}(\overrightarrow{a}) = f ^{\mathfrak{A}}(\overrightarrow{a})\) 이다. 이 닫힘성은 영항 함수 즉, 상수 기호에서도 성립하여 언어의 각 상수 기호 \(c\) 에 대하여 \(c ^{\mathfrak{B}} \in \left| \mathfrak{A} \right|\) 이 성립한다.

  역으로, 구조 \(\mathfrak{B}\) 에 대하여 \(\left| \mathfrak{B} \right|\) 의 임의의 비어있지 않은 부분집합 \(A\) 가 \(\mathfrak{B}\) 의 모든 함수에 대하여 닫혀있으면, \(A\) 를 전체로 하는 \(\mathfrak{B}\) 의 부분구조를 만들 수 있다. 즉, \(A\) 를 전체로 하고, 각 술어 파라미터 \(P\) 에 \(P ^{\mathfrak{B}}|_A\) 를 부여하고 함수기호에도 같은 방식으로 제한을 부여하면 부분구조를 얻는다.

• 예시

  유리수 집합 \(\Bbb{Q}\) 와 유리수 덧셈 \(+_Q\) 에 대한 구조 \((\Bbb{Q}; +_Q)\) 는 복소수 집합 \(\Bbb{C}\) 와 복소수 덧셈 \(+_C\) 에 대한 구조 \((\Bbb{C}; +_C)\) 의 부분구조이다.

• \(h \circ s\) 란 변수 집합을 \(\left| \mathfrak{B} \right|\) 로 보내는 사상이다. 이것을 모든 항에 대하여 확장한 것이 \(\overline{h \circ s}\) 이다.

• 증명

• 증명

• 예시

  양의 정수 집합 \(\Bbb{P}\) 에 대한 구조 \((\Bbb{P}; <_P)\) 는 \((\N;<_N)\) 과 동형이므로 \((\Bbb{P}; <_P) \equiv (\N; <_N)\) 이며, 이 두 구조는 1차 논리 문장으로 구분불가능하다.

• 그 역은 성립하지 않을 수 있다. 즉, 기본적으로 동등하지만 동형이 아닐 수 있다.

  보통의 순서관계를 가지는 구조 \((R; <_R)\) 는 보통의 순서관계를 가지는 \((\Bbb{Q};<_Q)\) 와 기본적으로 동등하지만, \(\Bbb{Q}\) 는 가산이고 \(\R\) 은 비가산이므로 동형이 아니다.

• \(\left| \mathfrak{A} \right|\) 의 항등함수는 \(\mathfrak{A}\) 의 자명한 자기동형사상이다. 만약 구조가 항등함수만을 자기동형사상으로 가지면 구조를 강성이다(rigid, 굳은, 단단한)고 한다.

• 준동형사상의 따름정리로써 자기동형사상은 정의가능한 관계를 보존한다.

• 이 정리는 주어진 관계가 정의불가능함을 보일 때 유용하다.

• 증명

Deductive Calculus✔

\(\Sigma \vDash \tau\) 를 증명하고 싶다고 해보자. 그러면 어떤 증명이 필요할까? 기본적으로 증명이란 당신의 주장의 옳음(의로움)을 남에게 납득시키기 위한 논증이다. 따라서 증명이란 유한해야 한다. 무한한 증명을 남에게 설득할 수 없다. 만약 전제 \(\Sigma\) 가 무한 집합이면 이것을 사용할 수 없다. 그러나 아래에서 살펴볼 1차 논리 콤팩트성 정리는 \(\Sigma_0 \vDash \tau\) 를 만족하는 유한 집합 \(\Sigma_0 \subset \Sigma\) 가 존재한다는 것을 보장해준다.

증명의 또 하나의 중요한 특징은 증명이 설득 대상인 사람에게 의하여 오류가 없는지 효과적으로 확인가능해야 한다. 즉, 증명을 검증할 때 천재적인 통찰이 필요 없어야 한다. 특히 \(\vDash \tau\) 의 증명처럼 공집합으로부터 나오는 증명 집합은 결정가능해야 한다. 이는 전제 없이 증명가능한 식 집합이 효과적으로 열거가능해야 한다는 사실을 함의한다. 원칙적으로 증명가능한 문장은 모든 기호의 연속을 생성하고 비증명으로부터 증명들을 분류해냄으로써 열거가능해야 한다. 만약 증명이 발견되면 그것의 마지막 줄을 출력 리스트에 입력한다. 열거가능성 정리는 합리적인 조건 아래에서 타당한 식 집합이 효과적으로 열거가능함을 보장해준다.

이는 콤팩트성 정리와 열거가능성 정리가 만족스러운 증명에 필요하다는 것을 뜻한다. \(\Sigma \vDash \tau\) 라고 하면 콤팩트성 정리에 의하여 유한 집합 \(\{\sigma_0,\dots ,\sigma_n\}\subset \Sigma\) 가 논리적으로 \(\tau\) 를 함의한다. 그러면 문제 2.2-1 에 의하여 \(\sigma_0 \implies \dots \implies \sigma_n \implies \tau\) 가 타당하다. 그러면 \(\Sigma \vDash \tau\) 를 검증하기 위하여 오직 유한한 단계의 타당성 열거를 수행하면 된다.

이제 연역이라고 부르는 형식적 증명을 살펴보자. 이 증명은 수학자가 다른 학자에게 특정 진리를 납득시키기 위한 연역적 생각의 모델이다. 우리의 목적은 1차 논리의 맥락에서 연역을 수학적으로 정확하게 정의하는 개념을 확립하는 것이다.

Formal Deductions✔

• \(\varphi\) 를 \(\Gamma\) 로부터 증명가능하다는 말이다.

\(\Lambda\) 와 추론규칙의 채택은 유일하지 않다. \(\Lambda =\varnothing\) 으로 두고 많은 추론 규칙을 채택할 수도 있지만, 지금은 \(\Lambda\) 를 무한집합으로 두고 단 하나의 추론 규칙 긍정 논법(modus ponens, MP)을 채택해보자.

• 특유의 형태 때문에 분리 규칙이라고도 불린다.

• 그러므로 식 집합 \(\Gamma\) 의 정리는 \(\Gamma \cup \Lambda\) 에 MP 를 유한번 적용하여 얻은 식이다.

• 예시

  "비가 온다" 와 "비가 온다면 땅이 축축하다" 가 참이면 "땅이 축축하다" 도 참이다.

• 연역이 존재하면 \(\varphi\) 가 \(\Gamma\) 로부터 연역가능하다고 하고, \(\varphi\) 를 \(\Gamma\) 의 정리라고 하고 \(\Gamma \vdash \varphi\) 라고 표기한다.

• 예시

  \(\beta,\gamma ,\gamma \implies \beta \implies \alpha \in \Gamma \cup \Lambda\) 이면 \(\Gamma \vdash \alpha\) 이다.

• \(n = 0\) 인 경우는 임의의 wff 가 자기 자신의 일반화라는 것을 말해준다.

Substitution✔

• 예시

  1. \(\varphi _{x}^{x} = \varphi\)
  2. \((Qx \implies \forall xPx)_{y}^{x} = (Qy \implies \forall xPx)\)

• 요점은 양화사가 지칭하는 종속변수를 치환하면 안된다는 것이다. 자유변수만 치환 가능하다. 함수 \(f(x) = \sum_{n=1}^{100}n+x\) 에서 \(x\) 만 치환 가능하고 \(n\) 은 치환불가능하다.

Tautologies✔

공리꼴 1) 은 항진식의 일반화된 식을 말한다. 항진식은 \(\neg ,\implies\) 만을 갖는 명제논리로부터 문장 기호를 1차 논리의 wff 로 치환하여 얻어진다.

가령 명제논리 항진식

에서 \(A\) 를 \(\forall y \neg Py\) 로, \(B\) 를 \(Px\) 로 치환하면 다음의 1차 논리 항진식을 얻는다.

wff 를 다음과 같이 분류할 수 있다.

1. 소인 논리식(prime formula, 소인식)은 원자식이나 \(\forall x \alpha\) 형태의 식이다.
2. 비소인 논리식(nonprime formula, 비소인식)은 \(\neg \alpha\) 나 \(\alpha \implies \beta\) 같은 그 외의 식이다.

명제 논리에서 1차 논리 언어에서 소인식이 되는 문장 기호를 택하면 그것은 공리꼴 1) 에 해당한다. 문장 기호를 1차 논리 wff 로 바꿀 필요가 없는 것은 이미 그것이 1차 논리 wff 이기 때문이다. 역으로 공리꼴 1) 에 속한 것은 명제 논리의 항진식의 일반화이다.

3가지 주목할 점이 있다. 먼저 1차 논리 언어가 가산적으로 많은 식을 포함한다고 상정하지는 않는다. 1차 논리 언어는 잠재적으로 비가산 문장 기호 집합을 상정하고 있다. 두번째로, 모든 항진식을 논리적 공리를 채택하는 것은 과하다. 공리꼴 1) 을 빠른 결정절차를 갖는 항진식 집합으로 축소해도 된다. 세번째로, 1차 논리 식은 명제 논리의 wff 이므로 명제 논리의 개념을 적용시킬 수 있다. \(\Gamma\) 가 항진적으로 \(\varphi\) 를 함의하면 \(\Gamma\) 가 논리적으로 \(\varphi\) 를 함의하는 것이다. 그러나 그 역은 성립하지 않는다.

• 증명

  \(\implies\):

  \(\{\alpha,\alpha \implies \beta\} \vdash \beta\) 이다. 이때 \(\{\alpha,\alpha \implies \beta\}\) 는 자명하게 \(\beta\) 를 항진적으로 함의한다.

  \(\Gamma \cup \Lambda\) 의 모든 원소를 만족하는 진리 할당 \(v\) 를 가정하면 귀납적으로 \(v\) 가 \(\Gamma\) 의 임의의 정리를 만족한다는 것을 확인할 수 있다. 정리는 MP 에 의하여 도출될 뿐이기 때문이다. ▲

  \(\impliedby\):

  \(\Gamma \cup \Lambda\) 가 항진적으로 \(\varphi\) 를 함의하면 따름정리 17A 에 의하여 \(\varphi\) 를 항진적으로 함의하는 유한 부분집합 \(\{\gamma _1,\dots ,\gamma _m,\lambda _1,\dots ,\lambda _n\}\) 이 존재한다. 그러면 문제 1.2-4 에 의하여 다음은 항진식이고 \(\Lambda\) 에 속한다.

  \[ \gamma _1 \implies \dots \implies \gamma _m \implies \lambda _1 \implies \dots \implies \lambda _n \implies \varphi \]

  여기에 MP 를 \(m+n\)번 적용하면 \(\varphi\) 를 얻는다. ■

Deductions and Metatheorems✔

집합 \(\Gamma\) 의 정리 집합은 \(\Gamma \cup \Lambda\) 에 MP 를 적용하여 얻은 집합이다. 가령 \(\Gamma = \varnothing\) 에 대하여 다음이 성립한다.

이 정리는 \(\Lambda\) 에 MP 를 적용하여 얻은 것이다. 공리꼴 1) 의

와 공리꼴 2) 에 속하는

에 MP 를 적용하여 \(\varnothing\) 로부터 \(Px \implies \exists yPy\) 를 연역해낸 것이다.

정리라는 말은 두 가지 다른 레벨에서 사용된다. \(\alpha\) 가 \(\Gamma \vdash \alpha\) 를 만족하면 \(\Gamma\) 의 정리라고 한다. 또한, 자연어에서 정리는 말을 사용할 수 있는데, 이것을 연역과 정리의 결과라는 것을 강조하기 위하여 상위정리(metatheorem)라고 부른다.

• 이 정리가 일반화가 가능하다는 것을 보장해준다.

• 증명

• 증명

• 증명

  \(\Gamma; \gamma \vdash \varphi\) 이면 정리 24B 에 의하여 \((\Gamma;\gamma )\cup \Lambda\) 가 항진적으로 \(\varphi\) 를 함의한다. 즉, \((\Gamma;\gamma )\cup \Lambda \vDash \varphi\) 인데 문제 2.2-1 에 의하여 \(\Gamma \cup \Lambda \vDash (\gamma \implies \varphi)\) 이다. 그러면 정리 24B 에 의하여 \(\Gamma \vdash (\gamma \implies \varphi)\) 이다. ■

• 증명

• 만약 체계가 모순적이면 임의의 식 \(\alpha\) 가 정리가 된다. 왜냐하면 \(\beta \implies \neg \beta \implies \alpha\) 가 항진식이기 때문이다. 즉, 모순을 가진 체계는 아무리 말도 안되는 말들이라도 참이라고 증명해낼 수 있다.

• 모순을 도출하여 가정이 잘못되었다는 것을 간접적으로 증명하는 방법이다.

• 증명

  연역 정리에 의하여 \(\Gamma \vdash (\varphi \implies \beta)\) 와 \(\Gamma \vdash (\varphi \implies \neg \beta)\) 가 성립한다. \(\{\varphi \implies \beta, \varphi \implies \neg \beta\}\) 는 항진적으로 \(\neg \varphi\) 를 함의한다. ■

Soundness and Completeness✔

• 증명

• 건전성 정리는 연역이 오직 올바른 결론만 이끌어낸다는 것을 말해준다. 그렇지 않으면 연역은 무의미할 것이다. 이 정리에 의하여 증명가능한 명제, 즉 정리는 의미론적으로도 참이다.

• 증명

  \(\Gamma\) 로부터 연역될 수 있는 임의의 식 \(\varphi\) 가 \(\Gamma\) 에 의하여 논리적으로 함의된다는 것을 귀납으로 증명해볼 것이다.

  \(\varphi\) 가 논리적 공리일 경우 보조정리에 의하여 \(\vDash \varphi\) 이다. 그러면 당연히 \(\Gamma \vDash \varphi\) 이다. ▲

  \(\varphi \in \Gamma\) 인 경우 명백히 \(\Gamma \vDash \varphi\) 이다. ▲

  \(\varphi\) 가 \(\psi\) 와 \(\psi \implies \varphi\) 로부터 MP 에 의하여 도출되었다고 하자. \(\psi\) 와 \(\psi \implies \varphi\) 는 귀납적 가정에 의하여 \(\Gamma \vDash \psi\) 와 \(\Gamma \vDash (\psi \implies \varphi)\) 을 만족한다. 즉, \(\Gamma\) 를 만족하는 임의의 구조가 \(\psi\) 와 \(\psi \implies \varphi\) 를 만족시킨다. 만약 \(\Gamma\) 를 만족하는 임의의 구조가 \(\varphi\) 를 만족하지 않으면 모순이다. 그러므로 \(\Gamma \vDash \varphi\) 이다. ■

• 증명

• 증명

• 이 따름정리는 건전성 정리와 동치이다.

• 1) 과 2) 는 동치이다. 둘 중 하나만 증명해도 증명이 끝난다.

• 이 정리는 1차 논리에서 증명가능한 명제 집합이 모델을 갖는다는 것을 말해준다. 즉, 증명 이론이 정의하는 진리가 모형 이론으로 정의한 진리가 일치한다는 것이다. 더 쉽게 말해서 참인 명제는 반드시 증명가능하다는 것이다.

  이 정리는 의미론적(semantic)으로 참인 명제가 구문론적(통사론적, syntactic)으로도 참이라는 것을 보장해주는 1차 논리의 가장 중요한 결론이다. 고차 논리에서는 성립하지 않는다.

  참과 거짓을 따져가며 진리표를 그리기도 하면서 명제의 진리를 판정해온 것들은 모두 의미론적 접근이다. 의미론적 접근으로 결론을 얻어내는 것을 귀결(\(\vDash\))이라고 한다. 반면 참거짓을 따지지 않고 오직 형식적인 규칙만으로 결론을 연역해내는 것은 구문론적 접근이다. 구문론적으로 결론을 얻어내는 것을 추론(\(\vdash\)) 이라고 한다.

• 건전성 정리과 완전성 정리로 1차 논리에서 다음의 결론을 얻는다.

  \[ \Gamma \vdash \varphi \iff \Gamma \vDash \varphi \]

  (사실, 엄밀하게는 메타언어를 사용하여 \(\Gamma \vdash \varphi \quad\text{iff}\quad \Gamma \vDash \varphi\) 라고 써야 한다.)

  즉, 진리와 증명가능이 동치이다. 진리이면 증명가능하고, 연역해낸 것들은 모두 진리이다. 불완전성 정리는 산술을 포함하는 체계에서 진리와 증명가능이 동치가 아니라는 것을 말해준다. 1차 논리만으로는 자연수를 표현할 수 없어서 불완전성 정리가 성립하지 않는다.

• 증명

• 증명

• 증명

Enderton, A Mathematical Introduction To Logic