우리가 옳다고 판단한 논증을
기호만으로도 증명할 수 있을까?

어떤 해석에서도 결론이 따라올까?

문장을 기호로 바꾸기 전에 무엇을 정해야 할까요?

앞의 동아리 예시에서 ‘연습을 마쳤다’와 ‘수료증을 받는다’를 구분해 보겠습니다. E(x)는 ‘x가 연습을 마쳤다’, C(x)는 ‘x가 수료증을 받는다’는 뜻으로 정합니다. a는 가람을 가리키는 이름입니다. 첫 조건은 ∀x(E(x) → C(x)), 둘째 조건은 E(a), 결론은 C(a)로 쓸 수 있습니다.

여기서 기호들의 역할이 서로 다릅니다. ∀x는 지금 고려하는 대상 전체를 뜻합니다. →는 앞 조건이 참일 때 뒤 조건도 참이어야 한다는 연결입니다. E와 C는 대상에게 어떤 성질이 있는지 표시합니다. a는 그 세계 안의 특정 대상을 가리킵니다. 같은 모양의 기호라도 뜻이 빠지면 독자가 논리식을 따라갈 수 없습니다.

무엇보다 ‘고려하는 대상 전체’가 누구인지 정해야 합니다. 학생들만 모은 세계를 선택할 수도 있고 사람 전체를 대상으로 정할 수도 있습니다. 논리학에서는 이런 대상의 범위와 기호의 해석을 정한 구조를 모형 또는 해석이라고 부릅니다. 해석마다 대상의 수와 E·C가 참인 대상을 다르게 정할 수 있습니다. 다만 논리기호 ∀, →, ∧, ¬ 등은 고전적인 1차 논리의 정해진 의미를 따릅니다.

이 말을 ‘아무렇게나 뜻을 바꿔도 된다’고 받아들이면 곤란합니다. 한 해석을 택한 뒤에는 E와 C, a의 뜻을 그 해석 안에서 일관되게 사용합니다. 해석을 바꿔 비교할 때에도 첫째 조건과 둘째 조건을 동시에 만족하는 세계만 검사합니다.

‘모든 해석에서 따라온다’는 말은 어떻게 검사할까요?

어떤 전제들이 참인 모든 해석에서 결론도 참일 때, 그 결론이 전제들에 의미상 따라온다고 합니다. 이것을 Γ ⊨ φ라고 적습니다. Γ는 모아 놓은 전제들을 가리키고, φ는 검사할 결론을 가리킵니다. 기호 ⊨는 ‘전제를 참으로 만드는 모든 해석에서 결론도 참이다’라는 약속입니다.

우리 사례에 적용하면 다음과 같습니다.

{∀x(E(x) → C(x)), E(a)} ⊨ C(a)

이 관계를 확인하려면 ‘가람이 연습을 마쳤고 연습을 마친 모든 학생이 수료증을 받는데도 가람이 수료증을 받지 않는’ 해석이 가능한지 살펴봅니다. 첫 조건과 둘째 조건을 만족하면서 결론을 거짓으로 만드는 해석은 없으므로, 이 논증은 타당합니다. 가람이라는 실제 학생이 있는지 조사할 필요는 없습니다. 기호에 주어진 관계만 판단하면 됩니다.

반대로 다음 논증은 어떨까요?

이 경우에는 다른 이유로 수료증을 받는 학생이 있을 수 있습니다. 대상이 가람 한 명뿐인 해석에서 E(a)는 거짓, C(a)는 참이라고 정합시다. 그러면 첫 조건 ∀x(E(x) → C(x))는 참입니다. 연습을 마친 사람이 없기 때문에 ‘연습을 마친 사람인데 수료증을 받지 않은 사람’도 없기 때문입니다. 둘째 조건 C(a) 역시 참이지만 결론 E(a)는 거짓입니다. 단 한 가지의 이런 해석을 제시하면 논증 전체의 타당성은 깨집니다. 이것이 반례 모형입니다.

큰 논리적 차이는 바로 여기 있습니다. 옳다고 주장할 때에는 가능한 모든 해석을 고려해야 하지만, 틀렸음을 보일 때에는 반례 한 개면 충분합니다.

유한한 증명의 줄을 만들 수 있을까?

기호를 따라 내려가는 ‘증명’은 뜻을 검사하는 일과 어떻게 다를까요?

뜻을 평가하는 대신 정해진 추론 규칙을 사용하는 방법도 있습니다. 기호 Γ ⊢ φ는 Γ의 전제들과 허용된 공리·추론 규칙을 사용하여 φ를 끝줄로 하는 유한한 증명을 만들 수 있다는 뜻입니다. 이때 ⊢는 종이에 실제로 쓸 수 있는 증명 단계에 관한 기호입니다. 반면 ⊨는 모든 해석에 관한 기호입니다. 둘이 닮았지만 역할은 다릅니다.

동아리 사례의 증명은 세 줄로 펼칠 수 있습니다.

1. ∀x(E(x) → C(x)) — 처음 주어진 첫 전제.
2. E(a) — 처음 주어진 둘째 전제.
3. E(a) → C(a) — 첫 전제를 가람에게 적용한 결과.
4. C(a) — 둘째 전제와 셋째 줄을 연결한 결과.

셋째 줄에는 전칭 제거 규칙을 적용했고, 넷째 줄에는 조건문과 그 앞 조건으로 뒤 결론을 얻는 규칙을 적용했습니다. 전칭 제거에서는 ‘모든 x에게 적용된다’는 내용을 지금 선택한 한 대상 a에게 적용합니다. 마지막 단계에서는 E(a)가 참이라는 사실과 E(a)라면 C(a)라는 조건을 함께 이용합니다. 따라서 이 네 줄의 증명은 독자가 한 줄씩 검사할 수 있습니다.

여기서 건전성과 완전성을 구별해야 합니다. 건전성이란 허용된 규칙으로 증명한 결론이라면 모든 해석에서도 따라온다는 성질입니다. 공식으로 적으면 Γ ⊢ φ 이면 Γ ⊨ φ입니다. 잘못된 추론 규칙을 섞어 근거 없는 결론을 끌어내지 않도록 보장하는 쪽입니다.

완전성은 반대 방향을 질문합니다. Γ ⊨ φ 이면 Γ ⊢ φ입니까? 전제들을 참으로 만드는 어떤 해석을 살펴보더라도 결론이 거짓일 수 없다면, 그 사실을 규칙 몇 개로 이어 만든 유한한 증명에도 담을 수 있는가 하는 문제입니다. 괴델은 고전적인 1차 논리의 표준 증명 체계에서 그 방향도 성립함을 보였습니다.

완전성 정리를 정확한 문장으로 써 봅시다

앞에서 사용한 두 관계를 나란히 놓으면 정리의 구조가 선명해집니다.

Γ ⊨ φ ⇔ Γ ⊢ φ

왼쪽은 전제 집합 Γ의 모든 모형에서 결론 φ가 참이라는 뜻입니다. 오른쪽은 Γ에 있는 전제들 가운데 실제 증명에서 필요한 유한한 몇 개를 사용해 φ를 도출하는 증명이 있다는 뜻입니다. 양쪽 화살표 ⇔는 두 방향이 모두 성립한다는 표시입니다. 고전적인 1차 논리의 증명 규칙이 건전하고 완전하면 이 관계가 성립합니다.

특히 Γ가 빈 전제 집합인 경우에는 ⊨ φ ⇔ ⊢ φ로 읽습니다. 모든 해석에서 참인 논리적 타당식을 전제 없이 증명할 수 있다는 뜻입니다. 역사적으로 괴델의 완전성 정리를 소개할 때 자주 보는 형태입니다. 전제 집합을 포함한 관계는 현대 교과서에서 널리 쓰는 강한 완전성의 표현입니다.

이 공식은 모든 사람이 동의할 만한 주장이나 관찰된 경험적 사실에 관한 약속과는 다릅니다. 같은 문장을 가지고도 언어의 범위, 논리기호의 의미, 전제 Γ를 어떻게 고르는지에 따라 질문 자체가 달라집니다. 그래서 ‘모든 진리에는 증명이 있다’라는 문구만으로 완전성 정리를 설명하면 중요한 경계가 사라집니다.

반대로 생각하면 무엇이 보일까?

증명이 언제나 가능하다는 사실을 어떻게 한 번에 보일 수 있을까요?

앞의 네 줄짜리 증명은 그 논증 하나의 타당성을 설명합니다. 괴델의 정리는 그런 증명을 만들 수 있는 경우가 정확히 어디까지인지를 한꺼번에 말합니다. 하나하나의 논증을 모두 적어볼 수도 없습니다. 1차 논리 문장에는 대상 전체를 가리키는 ∀와 어떤 대상을 가리키는 ∃가 여러 번 겹쳐 나타날 수 있고, 길이가 제한된 것도 아니기 때문입니다.

핵심을 이해하려면 거꾸로 생각해 볼 수 있습니다. 만일 Γ로부터 φ를 증명할 수 없다면, Γ를 참으로 유지하면서 φ를 거짓으로 만드는 해석이 실제로 존재할까? 이 질문에 언제나 ‘그렇다’라고 답할 수 있다면 완전성이 따라옵니다. 전제들이 결론을 반드시 보장한다고 주장하면서도 증명할 수 없는 사례가 있다면, 이 거꾸로 된 조건과 충돌하게 됩니다.

이를 위해 Γ에 ¬φ, 곧 ‘결론 φ가 거짓이다’라는 조건을 추가합니다. 새 조건을 넣었는데도 그 조건들로부터 모순을 도출할 수 없다면, 그 조건을 동시에 만족하는 모형을 만들어 보겠다는 생각입니다. 중요한 연결고리는 모순이 없는 전제들의 모음에는 그 전제들을 참으로 만드는 모형이 존재한다는 모형 존재 정리입니다. 여기서 ‘모순이 없다’는 말은 선택한 형식적 증명 규칙으로 거짓을 도출할 수 없다는 뜻입니다.

현대의 한 증명 방법은 이 모형 존재 정리를 먼저 세우고 완전성을 얻습니다. 이제 그 방법의 설계 원리를 따라가겠습니다. 아래 설명은 정식 교과서 증명의 모든 세부 경우를 전개한 원문 전사가 아니라, 왜 그런 모형을 만들 수 있는지 이해하도록 구성한 현대적인 증명 개요입니다.

조건을 만족하는 모형을 만들어 보자

‘누군가 있다’는 말에 이름을 붙이는 까닭

전제 중에 ∃x P(x)라는 문장이 있다고 합시다. 이는 P라는 성질을 가진 대상이 적어도 하나 존재한다는 뜻입니다. 그런데 대상에게 이름이 전혀 없다면 다음 증명에서 그 대상을 어떻게 다뤄야 할까요? ‘그 대상’이라는 말만 반복하면 어떤 문장을 검사해야 하는지 흐려집니다.

현대적인 헨킨 증명법은 필요한 때에 새로운 이름, 예를 들어 c를 준비하고 P(c)를 조건에 보탭니다. 새 이름은 이미 있던 어떤 특정 사람이나 물건을 몰래 가리키는 이름이 아닙니다. 존재한다는 전제를 만족시킬 증인을 가리키도록 새로 쓰는 이름입니다. 원래 전제들과 충돌하지 않도록 이름을 새롭게 고르는 절차가 필요합니다.

가장 간단한 예에서는 “어떤 학생은 연습을 마쳤다”라는 전제 ∃x E(x)가 있을 때 ‘그 학생’을 c라고 부릅니다. 그러면 E(c)라고 적을 수 있습니다. 여기에 “연습을 마친 학생은 수료증을 받는다”라는 전제가 있으면 C(c)도 얻습니다. 실제 학생의 이름을 알지 못해도 논증의 구조는 검사할 수 있습니다.

그러나 ∃x E(x)에서 아무나 선택한 기존 이름 a에 대해 E(a)를 결론으로 쓰면 잘못입니다. a는 이미 연습을 마치지 않은 다른 학생을 가리킬 수도 있습니다. 바로 그래서 사용하지 않은 새 이름을 도입하는 방식과 도입 조건이 중요합니다.

모순 없이 선택을 이어 가면 어떤 세계가 만들어질까요?

일관된 전제들을 하나의 세계로 만들려면 문장에 대한 판단도 차례로 정해야 합니다. P(a)가 참인지 아닌지 아직 결정되지 않았다면 P(a)나 ¬P(a) 중 일관성을 깨뜨리지 않는 쪽을 선택할 수 있습니다. 두 선택 모두 모순을 일으킨다면 이미 그 이전 조건들이 모순이라는 결론이 되므로, 처음부터 모순이 없다고 가정한 경우와 맞지 않습니다. 1차 논리의 문장들을 알맞은 순서로 열거하고 이 선택을 계속하는 것이 확장의 기본 생각입니다.

존재 문장이 나오면 앞 단계에서 설명한 증인 이름도 마련합니다. 이 과정을 통해 참으로 정할 문장들이 충분히 쌓인 집합을 만듭니다. 새 기호를 적절히 추가하고 고전논리의 공리와 규칙에 맞춰 선택하면, 원래의 조건을 보존하면서 각 문장의 참과 거짓을 일관되게 다루는 극대 일관적 집합에 도달할 수 있습니다.

그다음에는 문장 목록을 세계의 설계도로 읽습니다. 이름들은 세계 안의 대상을 나타내고, P(c)가 목록에 있으면 c가 P라는 성질을 갖도록 관계를 정합니다. 둘 이상의 대상을 다루는 관계 R(a,b)에도 같은 원리를 적용합니다. 등호가 포함된 언어라면 a=b라고 적힌 두 이름을 같은 대상으로 취급하도록 동치류를 만드는 조정이 필요합니다. 이처럼 만드는 모형을 항 모형이라고 부릅니다.

여기에서 가장 중요한 엄밀한 확인은 진리 보조정리입니다. 만든 모형에서 어떤 문장이 참인 것과, 그 문장이 일관적으로 확장한 집합에 들어 있는 것이 서로 일치한다는 사실을 식의 구조에 따라 귀납적으로 확인합니다. 단순한 술어에서 시작해 ¬, ∧, ∀, ∃의 단계까지 확인해야 합니다. 존재 기호에는 앞에서 마련한 증인 이름이 쓰입니다. 이 보조정리를 거치고 나서야 “일관된 조건들의 집합을 만족하는 모형이 존재한다”는 결론이 정당화됩니다.

이 방법은 훗날 레온 헨킨이 제시한 방식의 골격입니다. 괴델의 1929년 원증명은 다른 기술적 구성, 특히 공식의 정규형과 유한하게 갈라지는 경우들의 나무를 이용했습니다. 같은 완전성 정리로 향하는 서로 다른 증명 방식이라는 점을 기억해 주세요.