수학의 논리: 기초부터 현대까지

일상에서 수학적 논리로

우리는 일상생활에서 끊임없이 논리적 추론을 사용한다. 예를 들어, “비가 내리면 땅이 젖는다”라는 법칙과 “지금 비가 내린다”라는 정보가 주어졌을 때, 우리는 자연스럽게 “곧 땅이 젖을 것이다”라고 추론한다. 이러한 추론은 논리적 사고의 기본적인 형태이다.

또 다른 예로, “모든 사람은 언젠가는 죽는다”라는 법칙과 “소크라테스는 사람이다”라는 전제로부터 “소크라테스는 언젠가는 죽는다”라는 결론을 도출하는 과정을 들 수 있다. 이는 고전적인 삼단논법의 예시로, 우리의 일상적인 사고 과정에서 자주 사용되는 논리적 구조이다.

이처럼 우리는 일상생활에서 부지불식간에 논리적인 추론을 하며 살아간다. 수학에서는 이러한 논리적 사고가 더욱 중요한 위치를 차지한다. 수학에서 어떤 주장이 참임을 입증하기 위해서는 그 증명 과정이 논리적이어야 한다. 즉, 각 단계가 이전 단계로부터 타당하게 도출되어야 하며, 전체적인 흐름이 일관성 있게 구성되어야 한다.

그렇다면 수학에서 말하는 ‘논리’란 정확히 무엇을 의미할까? 일상에서 사용하는 논리와는 어떤 차이가 있을까? 이러한 질문에 답하기 위해 수학적 논리의 세계로 더 깊이 들어가 보자.

명제논리: 논리학의 기초

명제논리(propositional logic)는 논리학의 가장 기본적인 형태로, 명제들 사이의 관계와 명제의 진릿값을 다루는 논리 체계이다. 더 정확하게 정의하자면, 명제논리는 다음과 같은 요소들로 구성된다.

원자명제(atomic propositions): 더 이상 분해할 수 없는 가장 기본적인 진술.
논리 연결사(logical connectives): ‘not’, ‘and’, ‘or’, ‘if, then’, ‘if and only if’ 등.
괄호: 명제의 구조를 명확하게 하기 위한 기호.
추론 규칙(inference rules): 주어진 명제로부터 새로운 명제를 도출하는 규칙.

명제논리에서는 이러한 요소를 사용하여 복합명제를 구성하고, 명제의 진릿값을 결정하며, 논리적 추론을 수행한다.

명제논리를 사용한 증명의 간단한 예를 살펴보자. 다음과 같은 전제들이 주어졌다고 가정하자:

“만약 비가 내리면, 곧 땅이 젖는다.” (P → Q)
“비가 내린다.” (P)

이로부터 우리는 “곧 땅이 젖는다”(Q)라는 결론을 도출할 수 있다. 이는 ‘Modus Ponens’(줄여서 ‘M.P.’)라고 불리는 추론 규칙을 사용한 것이다.

이러한 과정에서 우리는 삼단논법(syllogism)을 사용했다. 삼단논법은 두 개의 전제로부터 하나의 결론을 이끌어내는 논리적 추론 규칙이다. (그러나, 뒤에서 설명하겠지만, 모든 삼단논법이 완벽하게 논리적인 것은 아니다.)

명제논리의 중요한 특성으로는 완전성(completeness), 건전성(soundness), 그리고 컴팩트성(compactness)이 있다.

완전성: 명제논리에서 의미론적으로 참인 모든 명제를 구문론적으로 증명할 수 있다.
건전성: 명제논리에서 구문론적으로 증명할 수 있는 모든 명제는 의미론적으로 참이다.
컴팩트성: 명제논리의 언어에서 잘 정의된 문장을 원소로 가지는 어떤 무한집합의 임의의 유한 부분집합이 모델을 가지면, 그 무한집합도 모델을 가진다.

명제논리의 완전성과 건전성 덕분에, 우리는 명제를 증명할 때 추론 규칙을 사용하든 진리표를 사용하든 동일한 결과를 얻게 된다. 이는 명제논리에서 다양한 증명 방식이 서로 일관성을 가진다는 것을 보장한다.

그러나 명제논리에는 한계가 있다. 예를 들어, 앞서 언급한 “모든 사람은 언젠가는 죽는다”와 “소크라테스는 사람이다”라는 전제로부터 “소크라테스는 언젠가는 죽는다”라는결론을 끌어내는 추론은 실제로는 완전한 삼단논법이 아니다.

이는 명제논리에서 ‘모든’이라는 한정사(quantifier)를 표현할 수 없기 때문이다. 명제논리는 개별 대상에 대한 성질이나 관계를 표현하는 데 한계가 있으며, ‘모든’, ‘어떤’ 등의 한정사를 포함하는 더 복잡한 논리적 구조를 다루기 어렵다.

일차논리: 더 강력한 논리 체계

일차논리(first-order logic)는 명제논리를 확장한 더 강력한 논리 체계이다. (‘일차논리’를 ‘일계논리’라고 부르기도 한다.) 간단히 말하자면, 일차논리는 개체(individuals), 성질(properties), 관계(relations), 그리고 한정사(quantifiers)를 다룰 수 있는 논리 체계이다. 더 정확하게 정의하면, 일차논리는 다음과 같은 요소들로 구성된다:

명제논리의 모든 요소(원자명제, 논리 연결사, 괄호, 추론 규칙).
변수(variables): 개체를 나타내는 기호.
상수(constants): 특정 개체를 나타내는 기호.
함수(functions): 개체들 사이의 대응 관계를 나타내는 기호.
술어(predicates): 개체들의 성질이나 관계를 나타내는 기호.
한정사(quantifiers): ‘모든’을 의미하는 전칭 한정사(∀)와 ‘어떤’을 의미하는 존재 한정사(∃).

일차논리와 명제논리의 주요 차이점은 일차논리가 개체들의 내부 구조와 그들 사이의 관계를 표현할 수 있다는 것이다. 이를 통해 우리는 “모든 x에 대해 P(x)이다”나 “어떤 x가 존재해서 P(x)이다”와 같은 더 복잡한 논리적 구조를 다룰 수 있다.

일차논리를 사용한 증명의 예를 살펴보자. 다음과 같은 전제들이 주어졌다고 하자:

모든 사람은 언젠가는 죽는다. (∀x(H(x) → D(x)))
소크라테스는 사람이다. (H(소크라테스))

이로부터 우리는 “소크라테스는 언젠가는 죽는다”(D(소크라테스))라는 결론을 도출할 수 있다. 이는 전칭 예화(Universal Instantiation)와 Modus Ponens라는 추론 규칙을 사용한 것이다.

일차논리 역시 명제논리와 마찬가지로 완전성, 건전성, 컴팩트성을 가진다. 이와 같은 일차논리의 특성은 일차논리의 강력함을 보여주는 동시에, 그 한계도 규정한다.

일차논리의 컴팩트성은 특히 중요한 의미를 가진다. 이를 통해 우리는 유한 사색 정리(Finite Four Color Theorem)를 무한 사색 정리(Infinite Four Color Theorem)로 확장할 수 있다. 즉, 임의의 유한 평면 그래프를 네 가지 색으로 경계가 구분되도록 칠할 수 있다는 사실로부터, 임의의 무한 평면 그래프도 네 가지 색으로 경계가 구분되도록 칠할 수 있다는 결론을 끌어낼 수 있다.

그러나 일차논리도 한계가 있다. 예를 들어, 자연수를 정의하는 페아노 공리계를 살펴보자. 페아노 공리계는 다음과 같은 공리들로 구성된다:

0은 자연수이다.¹
모든 자연수 n에 대해, n의 후자(successor) S(n)도 자연수이다. (n의 후자는 직관적으로 n+1을 가리킨다.)
0은 어떤 자연수의 후자도 아니다.
서로 다른 자연수는 서로 다른 후자를 가진다.
(귀납적 원리) 어떤 성질 P에 대해, P(0)이 참이고 ‘모든 자연수 n에 대해 P(n)이 참이면 P(S(n))도 참’일 때, 모든 자연수는 성질 P를 만족시킨다.

여기서 마지막 공리인 귀납적 원리는 일차논리로 표현할 수 없다. 이는 귀납적 원리가 자연수의 모든 부분집합에 대해 성립하는 성질을 기술하기 때문이다. 이러한 ‘모든 부분집합’에 대한 양화(quantification)는 일차논리의 범위를 넘어선다.

집합론의 공리계

집합론의 공리계는 일차논리를 확장하여 집합과 자연수를 다룰 수 있도록 만든 공리계이다. 현대 수학의 대부분의 분야는 집합론을 기반으로 하고 있으며, 이는 수학의 기초를 제공한다.

가장 널리 사용되는 집합론의 공리계는 Zermelo-Fraenkel(ZF) 공리계와 이에 선택공리(Axiom of Choice)를 추가한 ZFC 공리계이다. ZF 공리계는 다음과 같은 공리들로 구성된다:

외연성 공리: 같은 원소를 가진 두 집합은 동일하다.
공집합 공리: 원소가 없는 집합이 존재한다.
쌍 공리: 임의의 두 집합 a, b에 대해, {a, b}라는 집합이 존재한다.
합집합 공리: 임의의 집합 A에 대해, A의 모든 원소의 원소로 이루어진 집합이 존재한다.
멱집합 공리: 임의의 집합 A에 대해, A의 모든 부분집합으로 이루어진 집합이 존재한다.
무한 공리: 무한집합이 존재한다.
치환 공리: 함수에 의해 정의된 집합이 존재한다.
정칙성 공리: 공집합이 아닌 임의의 집합 A에 대해, A와 A의 원소 중 어떤 것과도 공통원소를 갖지 않는 원소가 A에 존재한다.
분리 공리 스키마²: 임의의 성질 P에 대해, 주어진 집합의 원소 중 P를 만족하는 원소들의 집합이 존재한다.

이 공리들은 집합의 기본적인 성질과 연산을 정의한다.

선택 공리(Axiom of Choice)는 ZF 공리계에 추가되어 ZFC 공리계를 형성하는 중요한 공리이다. 이 공리는 다음과 같다:

“공집합이 아닌 집합들의 집합 A에 대해, A의 각 원소에서 하나씩 원소를 선택하여 만든 집합이 존재한다.”

이 공리는 처음에는 다른 공리들로부터 증명될 수 있을 것이라고 여겨졌다. 그러나 1938년 Kurt Gödel에 의해 선택 공리가 ZF의 다른 공리들과 모순되지 않음이 증명되었고, 1963년 Paul Cohen에 의해 선택 공리의 부정 역시 ZF와 모순되지 않음이 증명되었다.

이는 선택 공리가 ZF 공리계의 다른 공리들로부터 독립적이라는 것을 의미한다. 즉, 선택 공리를 받아들이든 거부하든 둘 다 수학적으로 가능하다. 이로 인해 ZF 공리계에 선택 공리를 추가한 ZFC 공리계가 현대 수학의 표준적인 기초로 사용되게 되었다.

선택 공리는 수학의 여러 분야에서 중요한 역할을 한다. 예를 들어, 선택 공리는 다음과 같은 정리들의 증명에 사용된다.

존재성과 관련된 정리들. (예: 모든 벡터 공간은 기저를 가진다.)
Tychonoff의 정리. (임의의 컴팩트 위상공간들의 곱공간도 컴팩트 공간이다.)
Hahn-Banach 정리. (함수해석학의 주요 정리 중 하나.)

그러나 선택 공리는 몇 가지 반직관적인 결과들도 이끌어낸다. 가장 유명한 예는 Banach-Tarski 역설로, 3차원 공간에서 하나의 구를 유한 개의 조각으로 나누어 재배열하면 원래 구와 같은 크기의 두 개의 구를 만들 수 있다는 것이다.

이러한 특성 때문에, 선택 공리를 받아들일지 여부가 때때로 수학자들 사이에서 논쟁의 대상이 되기도 하였다. 그럼에도 불구하고, 오늘날 선택 공리는 수학의 많은 부분에서 필수적인 역할을 하고 있다.

ZFC 공리계는 자연수를 다룰 수 있는 충분히 강력한 공리계이다. 이는 ZFC가 불완전성을 가진다는 것을 의미한다. Kurt Gödel의 불완전성 정리는 자연수를 다룰 수 있을 만큼 강력한 모든 공리계가 다음 성질을 가지고 있음을 말한다:

(제1 불완전성 정리) 만약 공리계(모델)가 무모순이라면, 그 공리계 내에서 참이지만 증명할 수 없는 명제가 존재한다.
(제2 불완전성 정리) 충분히 강력한 무모순 공리계는 자신의 무모순성을 그 체계 내에서 증명할 수 없다.

ZFC를 바탕으로 한 집합론은 자연수를 구성할 수 있으므로 불완전성을 가진다. 즉, ZFC 내에 참이지만 ZFC의 공리들로부터 증명할 수 없는 명제들이 존재하며, ZFC가 무모순이라는 사실(만약 그렇다면)을 ZFC 내에서 증명할 수 없다.

불완전성 정리의 한 예로, 지난 포스트에서 언급한 연속체 가설을 들 수 있다. 연속체 가설은 무한집합 S가 있을 때, S보다 많은 원소를 가지고 있으면서 그 멱집합인 P(S)보다 적은 원소를 가진 집합이 존재하지 않는다는 가설이다. Gödel과 Cohen에 의하여 연속체 가설은 ZFC 공리계와 독립적임이 밝혀졌다.

수리논리학과 모델 이론

수학의 논리는 현대 수학의 근간이 되는 기초이다. 그러나 수학의 논리를 도구로 사용하는 데에서 그치지 않고 논리 그 자체를 연구하는 학문도 존재한다. 바로 수리논리학과 모델 이론이다.

수리논리학은 논리학을 수학적 방법으로 연구하는 분야이다. 여기에는 증명 이론, 재귀 이론, 모델 이론, 집합론 등이 포함된다. 이 분야는 수학적 추론의 본질을 이해하고, 수학적 구조의 기본적인 성질을 연구하는 데 중요한 역할을 한다.

모델 이론은 수리논리학의 한 분야로, 수학적 구조와 형식 언어 사이의 관계를 연구한다. 모델 이론은 주어진 공리계의 모델(그 공리계를 만족하는 수학적 구조)을 연구하며, 이를 통해 공리계의 성질을 이해하고자 한다.

이러한 분야들은 단순히 수학의 기초를 제공하는 데 그치지 않고, 그 자체로 풍부한 연구 주제를 제공한다. 예를 들어 다음과 같은 것들이 있다.

증명 이론은 수학적 증명의 구조와 성질을 연구하며, 이는 컴퓨터 과학의 형식 검증(formal verification) 분야와 밀접한 관련이 있다.
재귀 이론은 계산 가능성과 알고리즘의 한계를 연구하며, 이는 컴퓨터 과학의 계산 복잡도 이론의 기초가 된다.
모델 이론은 대수학, 기하학, 정수론 등 수학의 여러 분야에서 새로운 결과들을 도출하는 데 사용된다.

이처럼 수학의 논리는 수학의 많은 분야를 뒷받침하는 학문일 뿐만 아니라, 그 자체로도 깊이 있는 연구의 대상이 되는 분야이다.

여정을 마치며

지금까지 우리는 명제논리에서 시작하여 일차논리, 그리고 집합론의 공리계에 이르기까지, 수학적 논리의 발전 과정을 따라가 보았다. 우리가 살펴본 바와 같이, 수학의 논리는 단순히 일상적인 추론을 형식화한 것 이상이다. 수학의 논리는 수학의 기초를 제공하고, 수학적 진리의 본질에 대한 깊은 통찰을 제공한다. 동시에 수리논리학은 그 자체로 풍부한 구조를 가진 연구 대상이기도 한다.

더욱이, 수학의 논리는 인공지능과 기계학습 등 현대 기술의 근간을 이룬다. 컴퓨터 프로그래밍 언어의 기초, 알고리즘의 설계와 분석, 데이터베이스 시스템의 쿼리 언어 등은 모두 수학적 논리에 기반을 두고 있다. 따라서 수학의 논리를 이해하는 것은 현대 기술 사회를 이해하고 그 발전에 기여하는 데 중요한 역할을 한다.

수학의 논리를 탐구하는 여정은 결코 쉽지 않지만, 그 여정에서 얻는 통찰과 지적 성장은 그 모든 노력을 충분히 보상할 만큼 짜릿하다. 수학에 깊은 관심을 가지고 있다면, 또는 논리학에 깊이 관심을 가지고 있다면, 수리논리학의 세계에 빠져보는 건 어떨까?

(하지만 수리논리학을 공부하려면 학부 과정의 수학부터 탄탄하게 공부해야 한다.)

🍭