Tag Archives: Mathematical Logic

괴델의 불완전성 증명

이 글은 한국 『SKEPTIC』 8권 140-157쪽에 실린 이광근 교수님 글 「튜링의 1935년 - 앨런 튜링은 정말로 천재인가」의 일부를 발췌하여 수정한 것입니다. 괴델의 불완전성 정리(Gödel's incompleteness theorem)를 직관적으로 표현하면 다음과 같다. “참이지만 기계적인 논리체계로는 증명 불가능한 것이 존재한다. 자연수에 대한 명제들의 세계로 국한되더라도 그런 것이 존재한다.” 괴델이 이것을 어떻게 증명했는지 살펴보자. 불완전성 정리를 증명하기 위해서는 다음 등식을 만족시키는 명제… Read More »

일계논리와 무모순성

Hilbert는 수학의 기초를 확립하는 단계에서 무모순성에 관한 형식적 증명을 찾아냄으로써 수학의 여러 모순을 제거하고자 하였다. 그 증명은 오직 유한 단계의 기계적 절차에 의해 행해질 수 있는 것이어야 했다. Hilbert는 수학적 개체의 존재성과 그 개체의 무모순성은 일치한다고 믿었다. 예컨대 Hilbert의 관점에서 보면 실수 범위에서 제곱하여 \(-1\)이 되는 성질은 자기모순적이므로 그러한 조건을 만족시키는 실수는 존재하지 않는다. Euclid 기하학은 실수 집합의… Read More »

일계논리와 Peano 산술

일계논리 문장의 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\) 중 하나가 \(\varSigma\)의 논리적 귀결인 것이다. 완전성 정리에서는 형식계의 완전성을 말하기 때문에 완전성이라는 용어를 조금 다르게 사용한다. 그러나 두 상황에서 완전성이라는 개념은 서로 깊은 연관이 있다. 왜냐하면 \(\varSigma\)가 완전할 때 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\)가 \(\varSigma\)로부터 증명될 수 있기… Read More »

일계논리와 범주

수학의 분야 중에서는 일계논리만으로 그 분야를 논하기에 충분한 경우가 있고, 그렇지 않은 경우도 있다. 예컨대 군론(group theory)은 일계논리만으로 다룰 수 있지만 위상수학은 일계논리만으로는 직접 다룰 수 없다. 그렇다면 자연스럽게 다음과 같은 의문이 생긴다. 어떤 구조가 일계논리의 문장으로 다루어지기에 충분한가? 이를 논하기 위해 몇 가지 개념을 도입해야 한다. 두 \(\mathcal{L}\)-구조 \(M\)과 \(N\) 사이의 동형사상(isomorphism)이라 함은 다음 조건을 만족시키는 일대일대응… Read More »

일계논리의 긴밀성과 Löwenheim-Skolem 정리

긴밀성 정리와 Löwenheim-Skolem 정리는 일계논리에서 핵심적인 역할을 하는 정리이다. 이들 두 정리는 모두 Gödel의 불완전성 정리로부터 나온다. 여기서는 Gödel의 불완전성 정리를 도입하는 대신 긴밀성 정리와 Löwenheim-Skolem 정리의 증명을 간략하게 살펴보기로 한다. 또한 이 글에서는 일계논리언어가 가산인 경우로 논의를 한정한다. 정리 1.  일계논리의 긴밀성. \(\varSigma\)가 가산인 일계논리언어의 문장의 모임이고 \(\varSigma\)의 임의의 유한부분집합이 모델을 가지면 \(\varSigma\)도 모델을 가진다. 증명. 완전성… Read More »

일계논리의 건전성과 완전성

일계논리언어 \(\mathcal{L}\)에서 논리식 \(\phi\)가 논리적으로 유효하다(logically valid)는 것은 임의의 \(\mathcal{L}\)-구조 \(M\)과 \(M\)에서의 임의의 값매김에 대하여 \(\phi\)의 값이 \(\mathrm{T}\)가 되는 것을 의미한다. 만약 \(\phi\)가 문장이면 \(\phi\)의 참거짓 여부는 값매김에 영향을 받지 않고 오직 구조에 의해서만 결정된다. 그러므로 다음을 얻는다. 문장 \(\phi\)가 논리적으로 유효할 필요충분조건은 임의의 \(\mathcal{L}\)-구조 \(M\)에 대하여 \(M \models \phi\)인 것이다. 위 정리에 의하면, 논리식 \(\phi\)가 논리적으로 유효하지… Read More »

일계논리의 추론규칙

일계논리의 형식계는 명제논리와 마찬가지로 알파벳(alphabet), 공리(axioms), 추론규칙(rules of inference)으로 이루어져 있다. 추론규칙은 유한 개의 논리식을 입력받아 하나의 논리식을 출력하는 규칙이다. 증명(proof)이란 논리식의 유한열이다. 이때 증명의 각 줄은 공리이거나 또는 앞에 나타난 줄에 추론규칙을 적용하여 얻어지는 것이다. 증명의 마지막 줄을 정리(theorem)라고 부른다. 더 일반적으로, \(\varSigma\)가 논리식의 집합일 때, \(\varSigma\)로부터의 \(\phi\)의 증명이란 논리식의 유한열인데, 이때 증명의 각 줄은 공리이거나, \(\varSigma\)에… Read More »

일계논리의 의미론

일계논리의 구문론을 소개하면서 일계논리에서 사용하는 기호에 'not', 'if and only if', 'for all'과 같은 이름을 붙였다. 이것은 구문론에서 비록 의미를 부여하지 않은 기호의 나열을 논하지만, 실은 그러한 기호로 이루어진 문장이 어떠한 의미를 갖는지를 방법을 암시한 것이다. 이 글에서는 그러한 방법을 명확하게 밝힌 의미론(semantics)을 살펴본다. \(\mathcal{L}\)-구조 \(\mathcal{L}\)이 일계논리언어라고 하자. \(\mathcal{L}\)은 그것이 가지고 있는 관계기호, 함수기호, 상수기호에 의하여 완전히 결정된다.… Read More »

일계논리의 구문론

일계논리란 간단히 말하면 명제논리의 체계에 한정기호를 추가하여 확장한 것이다. 논리체계에 한정기호를 추가함으로써 명제논리에서는 다루지 못하였던 수학의 다양한 체계를 일계논리에서 다룰 수 있게 된다. 명제논리와 마찬가지로 일계논리에 대하여 논할 때에도 구문론과 의미론을 생각할 수 있다. 여기서는 일계논리의 구문론을 살펴보자. 일계논리언어 수학에서 '일계논리'를 적용하여 설명할 수 있는 분야는 여러 가지가 있다. 그리고 각각의 분야는 그 분야 고유의 일계논리언어를 가진다. 수학에서… Read More »

명제논리와 Bool 대수

19세기는 수학이 극도로 추상화되고 정제되는 시점이었다. Hilbert는 Euclid의 기하학 공리를 개선하여 새로운 기하학의 공리를 만들었으며, 그 공리들로부터 Descartes의 좌표를 이용한 Euclid 평면 \(\mathbb{R} ^2\)가 만들어질 수 있음을 보였다. Dyck과 Cayley는 기존의 군(group)의 개념을 정제하여 공리적으로 군을 정의하였다. 이 시기에 George Bool은 사고의 법칙을 정제하여 대수적 공리로 변환하고자 노력하였다. 즉 Bool은 논리와 대수의 공통점과 차이점을 비교하고 그들을 통합할 방법을… Read More »