수리논리학이란 무엇인가

요약

이 수업은 수리논리학의 대상을 규정한다. 그 대상은 각 과학의 몫인 개별 진술의 참과 거짓이 아니라, 추론의 형식과 타당성, 곧 전제의 참이 결론으로 옮겨 감을 보장하는 전제와 결론 사이의 관계이다. 명제, 논증, 전제, 결론, 형식, 반례를 정의하고, 결론이 거짓인 타당한 논증과 결론이 참인 부당한 논증으로 타당성을 참과 구별한다. 또 모호하고 자기 자신에 대해 말할 수 있는 자연 언어가 타당성을 엄밀하게 연구하기에 왜 충분하지 않은지 보이고, 강좌 전체를 이끄는 대상 언어와 메타언어의 구별을 세운다. 이어서 명시적인 가정과 증명을 갖추어 거짓말쟁이 역설, 베리 역설, 이발사 역설, 그리고 이발사 역설이 예고하는 러셀 역설을 제시하고, 형식 언어가 이 역설들을 어떻게 피하거나 정리로 바꾸는지 설명한다. 끝으로 수리논리학의 네 기둥과 강좌의 지도를 제시한다.

학습 목표

논증의 타당성을 그 전제와 결론의 참과 구별하고, 반례를 구성하여 부당한 형식을 논박한다.
자연 언어의 모호성을 알아보고, 모호한 진술의 각 읽기를 명확히 한다.
대상 언어와 메타언어를 구별하고, 표현의 사용과 언급을 구별한다.
역설을 분석한다. 곧 그 가정들을 분리하고, 모순을 도출하고, 어느 가정을 버려야 하는지 결정한다.

논리학은 무엇을 연구하는가

직접 관찰로 얻지 않는 모든 지식은 추론으로 얻는다. 받아들인 몇몇 주장에서 그것들로부터 따라 나오는 다른 주장으로 넘어가는 것이다. 기하학에서, 삼각형의 내각의 합이 두 직각임을 아는 사람은 둔각을 두 개 가진 삼각형은 없다고 결론짓는다. 의학에서, 어떤 병이 열을 일으킨다는 것과 진찰받는 사람에게 열이 없다는 것을 아는 사람은 그 병을 배제한다. 논리학은 이러한 넘어감이 언제 정당한지를 연구하는 학문이고, 수리논리학은 그것을 수학의 방법으로 연구하는 논리학이다. 곧 그 대상인 언어, 논리식, 연역을 정확하게 정의하고, 그것들에 관한 정리를 증명한다.

무엇을 연구하는지 정확하게 말하기 위해 먼저 용어를 정해 두자. 명제는 참이라고도 거짓이라고도 말하는 것이 의미 있는 평서문이다. “ $7$ 은 소수이다”는 참인 명제이고, “모든 짝수는 $5$ 보다 크다”는 거짓인 명제이다. 반면에 의문문(“지금 몇 시인가?”), 명령문(“문을 닫아라”), 그리고 “ $x$ 는 짝수이다”처럼 자유 변항을 포함하여 그 값이 $x$ 가 가리키는 것에 의존하는 표현은 명제가 아니다.

논증은 명제들의 목록인 전제와, 그것들의 귀결로 제시되는 또 하나의 명제인 결론을 함께 묶은 것이다. 전제는 어떤 명제라도 될 수 있다. 참이든 거짓이든, 알려진 것이든 단순한 상정이든 상관없다. 그것들을 전제로 만드는 것은 오직 논증 안에서 차지하는 자리뿐이다. 논증은 전제를 한 줄씩 차례로 쓰고, 결론 앞에 “그러므로”를 붙여 쓰기로 한다.

예시논증

어떤 수가 $4$ 의 배수이면 그 수는 짝수이다. 수 $28$ 은 $4$ 의 배수이다. 그러므로 $28$ 은 짝수이다.

전제는 “어떤 수가 $4$ 의 배수이면 그 수는 짝수이다”와 “ $28$ 은 $4$ 의 배수이다”이고, 결론은 “ $28$ 은 짝수이다”이다.

논리학은 진리의 이론이 아니다

그렇다면 논증의 전제가 참인지 확인하는 것은 논리학의 일이 아니다. $28$ 이 $4$ 의 배수인지는 산술이 정하고, 어떤 사람에게 열이 있는지는 체온계가 정하며, 어떤 전투가 어느 해에 일어났는지는 역사가 정한다. 진리가 무엇인지 정의하는 것도 논리학의 몫이 아니며, 그것은 철학에 속하는 물음이다. 논리학은 명제가 무엇이든 진리값을 가진다는 것을 인정하고, 그 값들이 서로 어떻게 관계하는지, 특히 어떤 명제들의 참이 언제 다른 명제의 참을 강제하는지를 연구한다. 다시 말해 논리학은 진리의 이론이 아니라 진리의 전달의 이론이다.

그런데 진리를 전달하는 것은 논증의 주제가 아니라 그 구조에 달려 있다. 앞의 논증을 다음 논증과 비교해 보자. “어떤 동물이 포유류이면 그 동물은 공기를 호흡한다. 고래는 포유류이다. 그러므로 고래는 공기를 호흡한다.” 둘은 같은 형식을 가진다. “어떤 것이 $A$ 이면 그것은 $B$ 이다. $c$ 는 $A$ 이다. 그러므로 $c$ 는 $B$ 이다.” 논증의 형식이란 논리어(“아니다”, “그리고”, “또는”, “이면”, “모든”, “어떤”)는 남겨 둔 채 논리어가 아닌 항(수, 동물, 성질)을 문자로 바꾸었을 때 남는 것이다. 형식의 문자에 내용을 주어 얻는 논증은 모두 그 형식의 대입례이다.

형식이 타당하다는 것은 그 대입례 가운데 어느 것도 전제가 모두 참이면서 결론이 거짓이 되지 않는다는 것이다. 논증이 타당하다는 것은 그 형식이 타당하다는 것이다. 전제가 참이고 결론이 거짓인 대입례를 그 형식의 반례라 한다. 따라서 형식이 부당한 것은 정확히 그것이 반례를 가질 때이다.

이 수업의 증명에서는 한국어의 속기를 사용한다. $V(A)$ 는 “ $A$ 는 참이다”의 약어이고, $F(A)$ 는 “ $A$ 는 거짓이다”의 약어이다. $\neg$ 의 뜻은 “아니다”, $\wedge$ 의 뜻은 “그리고”, $\vee$ 의 뜻은 “또는”, $\Rightarrow$ 의 뜻은 “이면”, $\Leftrightarrow$ 의 뜻은 “일 때 그리고 그때에만”이다. $\forall$ 의 읽기는 “모든”, $\exists$ 의 읽기는 “존재한다”이다. 이 기호들은 여기서 메타언어의 낱말을 줄인 것일 뿐이며, 이중선 화살표는 강좌 전체에서 이 용도로만 쓴다. 다음 수업에서는 단선 기호 $\rightarrow$ , $\leftrightarrow$ 두 가지가 $\neg$ , $\wedge$ , $\vee$ 세 기호와 함께 형식 언어의 약어로 나타나며, 그 뜻은 강좌가 정확하게 정한다. 화살표의 선의 차이가 어느 수준에서 말하고 있는지를 떠올리게 해 줄 것이다.

명제타당성이 보장하는 것

논증이 타당하고 그 전제가 모두 참이면, 그 결론은 참이다. 따라서 타당한 논증의 결론이 거짓이면, 그 전제 가운데 어느 것이 거짓이다.

증명

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
전제가 $A_1, \ldots, A_n$ 이고 결론이 $C$ 인 타당한 논증을 잡고, 전제가 모두 참이라고 가정하자.
$\resaltar{A_1, \ldots, A_n, C}$
모든 논증은 자기 자신의 형식의 대입례이다. 형식의 문자에 그것들이 논증 안에서 가졌던 내용을 주면 된다.
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
타당성의 정의에 따라, 이 형식의 어느 대입례도 전제가 참이면서 결론이 거짓이 되지 않는다. 특히 논증 자체도 그렇지 않다.
$\resaltar{V(C)}$
전제가 참이므로, 부정된 연언에서 성립하지 않을 수 있는 것은 결론의 거짓뿐이다. 따라서 결론은 참이다.
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
반대로 결론이 거짓이면, 전제가 모두 참일 수는 없다. 그렇다면 결론도 참이 될 것이기 때문이다.

이 명제는 타당성이 무엇을 보장하는지 말해 준다. 그만큼 분명하게, 타당성이 무엇을 보장하지 않는지도 보아 두는 것이 좋다. 논증의 타당성, 모든 전제의 참, 결론의 참을 조합하면, 가능한 여덟 가지 조합 가운데 배제되는 것은 전제가 참이고 결론이 거짓인 타당한 논증이라는 단 하나뿐이고, 나머지는 모두 일어난다.

예시타당하지만 결론이 거짓

모든 소수는 홀수이다. 수 $2$ 는 소수이다. 그러므로 $2$ 는 홀수이다.

형식이 이 수업의 첫 논증과 같으므로 이 논증은 타당하다. 그런데도 그 결론은 거짓이다. 앞의 명제가 결함이 있는 곳을 가리킨다. 어느 전제가 거짓이며, 실제로 첫 전제가 거짓이다. $2$ 는 소수이면서 짝수이기 때문이다. 타당한 논증은 진리를 만들어 내지 않는다. 받은 진리를 보존할 뿐이다.

예시부당하지만 결론이 참

어떤 수가 $4$ 의 배수이면 그 수는 짝수이다. 수 $8$ 은 짝수이다. 그러므로 $8$ 은 $4$ 의 배수이다.

전제와 결론이 모두 참인데도 이 논증은 부당하다. 그 형식 “어떤 것이 $A$ 이면 그것은 $B$ 이다. $c$ 는 $B$ 이다. 그러므로 $c$ 는 $A$ 이다”에는 반례가 있다. 수 $6$ 을 $8$ 의 자리에 놓으면 전제는 여전히 참이고(“어떤 수가 $4$ 의 배수이면 그 수는 짝수이다”, “ $6$ 은 짝수이다”) 결론 “ $6$ 은 $4$ 의 배수이다”는 거짓이다. 원래 결론의 참은 전제에서가 아니라 산술에서 온다. $8 = 4 \cdot 2$ 이다. 일상적인 추론에서 흔히 보이는 이 부당한 형식을 후건 긍정이라 한다.

여기서 이 수업이 연습할 실용적인 규칙이 따라 나온다. 논증이 부당함을 보이려면 어느 전제나 결론이 거짓이라고 지적하는 것으로는 충분하지 않고, 타당함을 보이려면 그 안의 모든 것이 참이라는 것으로는 충분하지 않다. 앞의 것은 그 형식의 반례를 내보일 것을 요구하고, 뒤의 것은 모든 대입례에 통하는 추론을 요구한다.

자연 언어와 형식 언어

타당성의 정의는 두 가지 조작에 기댄다. 논증의 형식을 알아보는 것과 명제가 참인지 거짓인지 결정하는 것이다. 둘 다 각 문장이 단 한 가지로 읽힌다는 것을 전제한다. 자연 언어, 곧 한국어, 중국어, 아랍어처럼 사람이 정식 교육 없이 배우고 의사소통에 쓰는 언어는 이 조건을 충족하지 않는다. 시와 대화와 뉘앙스에 알맞게 해 주는 그 유연성이 자연 언어를 모호하게도 만든다.

어휘적 모호성: 한 낱말이 여러 뜻을 가진다. “배를 보았다”는 타는 배를 가리킬 수도, 먹는 배를 가리킬 수도, 몸의 배를 가리킬 수도 있다.
통사적 모호성: 한 문장이 여러 구조를 허용한다. “이 곱하기 삼 더하기 사”는 $2 \cdot 3 + 4 = 10$ 일 수도 있고 $2 \cdot (3 + 4) = 14$ 일 수도 있다.
작용역의 모호성: 논리어가 문장의 어느 부분에 작용하는지 분명하지 않다. “모든 학생이 합격하지 않았다”는 아무도 합격하지 않았다는 뜻일 수도 있고, 모두가 합격한 것은 아니라는 뜻일 수도 있다.
부정확한 연결사: “또는”은 두 선택지가 함께 성립하는 것을 허용하기도 하고(“학위 또는 경력 필요”), 그것을 배제하기도 한다(“커피 또는 차”). “이면”은 원인을 나타내기도 하고, 규칙을 나타내기도 하며, 단순한 선후 관계를 나타내기도 한다.

모호성에 더하여 더 깊은 특징이 있다. 자연 언어는 자기 자신에 대해 말할 수 있다. 자연 언어에는 “문장”, “참인”, “정의하다”라는 낱말이 있고, 이것들로 “이 문장은 여섯 단어로 되어 있다”처럼 자기 자신을 가리키는 문장을 만들 수 있다. 이러한 자기 지시는 대체로 해가 없다. 그러나 나중에 보겠지만, 진리 개념과 결합하면 참일 수도 거짓일 수도 없는 문장을 낳는다.

형식 언어는 이 두 가지 어려움의 원천을 없애도록 설계된다. 기호들의 모음인 알파벳과, 어떤 기호 나열이 잘 형성된 표현인지를 해석의 여지 없이 정하는 형성 규칙을 정하고, 각 표현의 의미는 그다음에 똑같이 정확한 정의로 정한다. 이렇게 하면 기호 나열이 그 언어에 속하는지는 규칙을 확인하여 기계적으로 풀리는 문제가 되고, 각 표현은 단 한 가지로 읽힌다. 이 강좌의 언어는 명제 논리의 언어에 관한 수업에서 구성되는데, 그 알파벳은 원 $\sigO$ 과 원판 $\sigI$ 이라는 단 두 기호로 이루어지고 형성 규칙도 단 하나이다.

그 대가는 유연성이다. 형식 언어는 대화에 쓸 수 없고, 각 형식 언어는 그 규칙이 허용하는 것만 표현한다. 그렇다고 표현력이 모두 희생된다는 것은 옳지 않다. 일차 논리의 형식 언어만으로 거의 모든 수학을 쓸 수 있다. 희생되는 것은 모호성과 통제되지 않는 자기 지시이고, 얻는 것은 언어 자체에 관한 정리를 증명할 가능성이다.

대상 언어와 메타언어

어떤 언어를 연구하려면 그것에 대해 말해야 하고, 그것에 대해 말하려면 다른 언어가 필요하다. 대상 언어는 연구되는 언어이고, 메타언어는 그것을 연구하는 데 쓰는 언어이다. 한국어로 쓴 라틴어 문법책에서 라틴어는 대상 언어이고 한국어는 메타언어이다. 이 강좌에서 대상 언어는 원과 원판의 형식 언어이고, 메타언어는 한국어이다. 다만 수학 기호, 그리고 대상 언어의 임의의 논리식을 나타내지만 그 자신은 대상 언어에 속하지 않는 그리스 문자 $\varphi$ , $\psi$ 로 보충된다.

이 구별이 중심적인 데에는 분명한 이유가 있다. 강좌가 형식 언어에 대해 증명할 주장들(모든 논리식이 단 한 가지로 읽힌다는 것, 연역 가능한 것은 모두 참이라는 것)은 형식 언어의 논리식이 아니라 메타언어의 문장이다. 그래서 그것들은 메타정리라고 불리며, 연역 체계가 대상 언어 안에서 만들어 내는 정리와 구별된다.

이 구별의 기초적인 형태는 표현의 사용과 그 언급을 나누는 것이다. “로마는 도시이다”에서 그 낱말은 도시에 대해 말하기 위해 사용된다. “‘로마’는 두 글자이다”에서 그 낱말은 언급되며, 따옴표가 그것을 나타낸다. 이 문장이 말하는 것은 낱말이지 도시가 아니다. 둘을 혼동하면 “로마는 두 글자이다” 같은 터무니없는 진술이나, “로마는 도시이다. ‘로마’는 두 글자짜리 낱말이다. 그러므로 도시는 두 글자짜리 낱말이다” 같은 오류 논증이 생긴다.

예시세 수준

대상 언어로 라틴어를 잡자. 문장 “Roma aeterna est”는 대상 언어에 속한다. 문장 “‘Roma aeterna est’는 세 단어로 되어 있다”는 메타언어인 한국어에 속하며, 참이다. 문장 “앞의 문장은 한국어로 쓰여 있다”는 메타언어의 문장에 대해 말한다. 그것은 같은 언어로 쓰여 있는데도 셋째 수준, 곧 메타언어의 메타언어에 속한다. 같은 하나의 언어가 여러 수준에서 쓰이는 것을 막는 것은 아무것도 없다. 중요한 것은 무엇에 대해 말하고 있는지를 놓치지 않는 것이다.

언어의 역설

모순은 어떤 주장과 그 부정을 함께 묶은 것이며, $V(A) \wedge \neg V(A)$ 가 그 예이다. 역설은 받아들일 만해 보이는 가정에서 출발하여 타당해 보이는 단계를 밟아 모순에 이르는 추론이다. 명제 “타당성이 보장하는 것”에 따라, 단계들이 정말로 타당하다면 어느 가정이 거짓이다. 역설을 해결한다는 것은 그것이 어느 것인지 찾아내는 것이다. 역설을 읽기가 여럿 있을 뿐인 모호성과 혼동해서는 안 되고, 단지 놀라울 뿐인 것과 혼동해서도 안 된다.

거짓말쟁이

이런 종류의 역설 가운데 가장 오래된 것은 기원전 4세기 밀레토스의 에우불리데스에게 돌려진다. 정확한 형태에서 그것은 속이려는 의도를 전제하는 거짓말이 아니라 거짓에 대해 말한다. $m$ 을 문장 “문장 $m$ 은 거짓이다”라고 하자. 모순을 얻는 데에는 두 가정이면 충분하며, 그것들을 명시적으로 써 두는 것이 좋다.

이치성 (B): 모든 명제는 참이거나 거짓이며, 둘 다는 아니다. 거짓이라는 것은 참이 아니라는 것과 동치이다.
진리 도식 (T): 문장이 참인 것은 그 문장이 말하는 것이 성립할 때 그리고 그때에만이다. 예를 들어 “눈은 희다”가 참인 것은 눈이 흴 때 그리고 그때에만이다.

정리거짓말쟁이 역설

이치성과 진리 도식이라는 가정을 문장 $m$ 에 적용하면 모순에 이른다. 두 가정을 모두 지키는 진리값을 $m$ 에 배정할 방법이 없다. 그림에서 문장 $m$ 은 자기 자신을 가리키고, 화살표는 두 가능성을 차례로 지난다.

증명

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
이치성에 따라 $m$ 은 참이거나 거짓이며, 둘 다는 아니다. 거짓이라는 것은 참이 아니라는 것이다.
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
$m$ 이 말하는 것은 $m$ 이 거짓이라는 것이다. 진리 도식에 따라 $m$ 이 참인 것은 정확히 그것이 말하는 것이 성립할 때이다.
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
두 동치를 이으면 $m$ 의 참은 그 자신의 부정과 동치가 된다.
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
$m$ 이 참이라면, 동치를 왼쪽에서 오른쪽으로 읽을 때 그것은 참이 아니다. 이 상정은 스스로를 논박하므로 $m$ 은 참이 아니다.
$\resaltar{V(m) \wedge \neg V(m)}$
그런데 그렇다면 동치를 오른쪽에서 왼쪽으로 읽을 때 $m$ 은 참이다. 주장과 그 부정을 동시에 얻는다.

이 정리는 논리학이 모순적이라고 말하는 것이 아니라, 문장 $m$ 을 포함하는 언어에서는 두 가정을 동시에 유지할 수 없다고 말한다. 그러므로 출구는 셋이다. 이치성을 버리고 진리값이 없는 문장을 인정하는 것, 진리 도식을 제한하는 것, 또는 언어가 문장 $m$ 을 만들지 못하게 하는 것이다. 셋째 출구는 1933년 알프레트 타르스키의 것이다. 어떤 언어의 술어 “참이다”는 그 언어가 아니라 그 메타언어에 속한다. 그러한 언어에서 $m$ 은 잘 형성된 문장이 아니며, 역설은 진술조차 될 수 없다.

베리 역설

1906년 버트런드 러셀이 발표하고 옥스퍼드의 사서 조지 베리에게 돌린 이 역설은 “참인”이라는 낱말이 아니라 “정의하다”라는 낱말을 쓴다. 한국어의 어구가 자연수를 정의한다는 것은 그 수를 모호함 없이 식별할 수 있도록 기술한다는 것이다. 예컨대 “십보다 큰 가장 작은 소수”는 $11$ 을 정의한다. 어구 “스무 개 미만의 단어로는 정의할 수 없는 모든 자연수 중에서 가장 작은 수”를 생각하고, 이것을 쓰인 그대로 읽기로 하며, 그것이 정의하려는 수를 $b$ 라 부르자. 이 강좌에서 자연수는 $1, 2, 3, \ldots$ 이다.

정리베리 역설

한국어의 어휘가 유한하고 관계 “어구가 그 수를 정의한다”가 확정되어 있다면 모순에 이른다. 수 $b$ 가 존재하고, 동시에 스무 개 미만의 단어로 정의될 수도 있고 정의될 수 없기도 하다. 그림에서 짧은 어구들은 그것들이 정의하는 수로 보내지는데, 그런 수는 많지 않다. 처음으로 비어 남는 수가 $b$ 이다.

증명

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
$k$ 를 사전에 실린 단어의 수라 하자. 한 단어로 된 어구는 많아야 $k$ 개, 두 단어로 된 어구는 많아야 $k^2$ 개이며, 이렇게 열아홉 단어로 된 어구까지 이어진다. 따라서 스무 개 미만의 단어로 된 어구는 유한하며, 그 개수를 $N$ 이라 하자.
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
각 어구가 정의하는 수는 많아야 하나이다. $D$ 를 스무 개 미만의 단어로 된 어떤 어구가 정의하는 자연수들의 집합이라 하자. 그 원소는 많아야 $N$ 개이다.
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
$N + 1$ 개의 수 $1, 2, \ldots, N + 1$ 가운데에는 $D$ 에 속하지 않는 것이 있다. 차례로 살펴보면, $D$ 에 속하지 않는 첫 수가 스무 개 미만의 단어로는 정의할 수 없는 가장 작은 자연수이다. 그 앞의 수는 모두 $D$ 에 속한다.
$13 < 20, \quad \resaltar{b \in D}$
그런데 어구 “스무 개 미만의 단어로는 정의할 수 없는 모든 자연수 중에서 가장 작은 수”는 열세 단어로 되어 있고, 바로 $b$ 를 정의한다.
$\resaltar{b \in D \wedge b \notin D}$
주장과 그 부정을 동시에 얻는다.

어구가 스무 단어보다 짧다는 것만 지적하는 흔한 설명은 논증의 절반을 빠뜨린다. 수 $b$ 가 존재한다는 것인데, 이를 위해서는 어휘의 유한성과 처음으로 빠진 수를 고르는 일이 필요하다. 무너지는 것은 둘째 가정이다. “정의하다”는 한국어의 정확한 관계가 아니다. $b$ 를 정의하는 어구가 “정의하다”라는 낱말 자체를 쓰고 있고, 그 뜻은 어떤 어구를 정의로 치느냐에 달려 있기 때문이다. 형식 언어 $L$ 에서는 “ $L$ 에서 정의 가능”이 무슨 뜻인지 정확하게 할 수 있지만, 그 개념은 메타언어에서만 표현된다. $b$ 를 정의하는 어구는 $L$ 에 속하지 않으며, 모순은 사라진다. $b$ 는 $L$ 에서는 적은 기호로 정의할 수 없지만, 메타언어에서는 정의할 수 있다.

이발사와 러셀 집합

이발사 역설은 흔히 이렇게 이야기된다. 어느 마을에 이발사가 있는데, 그는 그 마을의 남자이며, 스스로 면도하지 않는 마을의 모든 남자를 면도해 주고, 그들만 면도해 준다. 이발사는 자기 자신을 면도하는가? “그들만”이라는 말은 본질적이다. 이 제한 없이 스스로 면도하지 않는 모든 사람을 면도해 주는 이발사라면, 아무 모순 없이 자기 자신도 면도할 수 있다. 이 역설은 대각선 꼴을 한 일반적인 보조정리의 특수한 경우이며, 그 보조정리를 한 번 증명해 둘 만하다.

보조정리대각선 보조정리

$D$ 를 대상들의 모임, $R$ 을 그것들 사이의 관계라 하고, 대상들의 각 쌍 $x$ , $y$ 에 대하여, 그것들이 $D$ 의 대상이면 주장 $R(x, y)$ 는 참이거나 거짓이라 하자. 그러면 대상 $b$ 로서, $D$ 에 속하고, 또 $x$ 가 $D$ 의 어느 대상이든 $R(b, x)$ 가 성립하는 것이 $R(x, x)$ 가 성립하지 않을 때 그리고 그때에만인 것은 존재하지 않는다. 그림에서 각 행은 대상 $x$ , 각 열은 대상 $y$ 이고, $R(x, y)$ 가 성립할 때 그 칸이 칠해져 있다. $b$ 를 위해 찾는 행은 대각선을 뒤집어야 하며, 그래서 각 행과 그 행의 대각선 칸에서 다르다.

증명

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
그러한 $b$ 가 $D$ 에 있다고 가정하자.
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
조건은 $x$ 가 $D$ 의 어느 원소이든 성립하고, $b$ 는 그 가운데 하나이다. 따라서 $x = b$ 로 잡을 수 있다.
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
$R(b, b)$ 가 성립하면, 동치에 따라 그것은 성립하지 않는다. 모순이다.
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
$R(b, b)$ 가 성립하지 않으면, 동치에 따라 그것은 성립한다. 역시 모순이다.
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
두 경우 가운데 하나는 일어나야 하므로, 이 상정은 유지될 수 없다. 그러한 $b$ 는 존재하지 않는다.

따름정리이발사는 존재하지 않는다

어느 마을에도, 스스로 면도하지 않는 마을의 모든 남자를 면도해 주고 그들만 면도해 주는 그 마을의 남자는 없다.

증명

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
$D$ 를 마을 남자들의 모임, $R(x, y)$ 를 관계 “ $x$ 는 $y$ 를 면도해 준다”라 하자. 이발사 $b$ 는 마을의 남자이므로 $D$ 에 속한다. 그가 기술된 대로의 이발사라는 것은, 마을의 각 남자를 정확히 그 남자가 스스로 면도하지 않을 때 면도해 준다는 뜻이다.
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
대각선 보조정리에 따라 마을의 어떤 남자도 이 조건을 충족하지 않는다. 기술된 이발사는 존재하지 않는다. 이 이야기는 역설이 아니라 그 주인공이 불가능하다는 증명이다.

이발사에 관한 결론은 해가 없다. 그런 이발사가 존재한다고 주장한 사람은 아무도 없었기 때문이다. 집합론에서의 변형은 사정이 다르다. 1902년 러셀은 고틀로프 프레게에게 편지를 써서, 산술을 논리학 위에 세우려 한 프레게의 체계가 다음 내포 원리를 인정한다고 지적했다. 모든 성질에 대하여, 그 성질을 가진 대상들을 정확히 원소로 하는 집합이 존재한다. 자기 자신에 속하지 않는다는 성질에 이 원리를 적용하면, 다음 집합이 존재한다고 주장하게 된다.

Z = \{ x : x \notin x \}

따름정리러셀 역설

제한 없는 내포 원리는 모순적이다.

증명

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
$D$ 를 모든 집합의 모임, $R(x, y)$ 를 관계 “ $y$ 는 $x$ 에 속한다”라 하자. 내포 원리를 성질 $x \notin x$ 에 적용하면, 집합 $Z$ 가 존재하며 그 원소는 자기 자신에 속하지 않는 집합들이라고 주장하게 된다.
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
고른 관계 아래에서 $Z$ 의 조건은 정확히 대각선 보조정리의 조건이며, $Z$ 가 $b$ 의 자리에 있다. $x \in Z$ 는 $R(Z, x)$ 이고, $x \notin x$ 는 $\neg R(x, x)$ 이다.
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
집합 $Z$ 는 집합이므로 $D$ 에 속한다. 대각선 보조정리에 따라 그러한 $Z$ 는 존재하지 않으며, $x = Z$ 로 놓으면 불가능한 동치를 얻는다. 그런데 원리는 그것이 존재한다고 주장한다. 따라서 원리는 모순을 함의한다.

이발사와 달리, 여기서 $Z$ 의 존재는 이야기 속의 상정이 아니라 이론의 원리였다. 러셀 역설은 $Z$ 가 존재하지 않는다고 선언해서가 아니라 이론을 고쳐서 해결된다. 1908년 체르멜로의 공리적 집합론은 성질을 써서 이미 주어진 집합의 부분집합만 만들 수 있게 하며, 이 제한 아래에서는 모순이 도출되지 않는다.

역설이 아닌 것

공집합은 원소가 없는데도 존재한다는 관찰이 때때로 “공집합의 역설”이라고 불려 왔다. 마치 존재하는 대상은 존재하는 대상들로 이루어져야 한다는 듯이 말이다. 여기에는 아무 모순도 없다. 집합은 벽이 벽돌로 이루어지듯 그 원소로 이루어지는 것이 아니라 원소에 의해 정해지며, 집합의 원소들의 모임은 원소를 하나도 갖지 않을 수 있다. 빈 상자가 여전히 상자인 것과 같다. 어떤 사실이 놀랍다고 해서 역설이 되는 것은 아니다. 역설은 모순을 도출할 것을 요구하는데, 여기서는 아무 모순도 도출되지 않는다.

형식 언어는 역설을 어떻게 다루는가

이상에서 형식 언어가 역설을 피하는 것은 마법에 의해서가 아니라 두 가지 정확한 방식에 의해서임이 따라 나온다. 첫째는 역설을 낳는 수단을 갖지 않을 수 있다는 것이다. 이 강좌가 구성하는 명제 논리의 언어에는 자기 자신을 가리키는 문장도, 진리 술어도 없다. 그 안에서는 거짓말쟁이 문장을 쓸 수 없으며, 그 의미론은 변항들에 대한 각 진리값 할당에서 각 논리식에 단 하나의 진리값을 배정한다. 둘째는 더 풍부한 언어에서는 역설이 정리로 바뀐다는 것이다. 거짓말쟁이의 추론을 엄밀하게 수행하면, 충분히 표현력이 있는 언어의 진리는 바로 그 언어 안에서 정의할 수 없음이 증명된다(타르스키). 이발사와 러셀의 추론은 어떤 모임들이 집합이 아님을 증명한다. 그리고 베리의 논증과 가까운 논증들이 1931년 쿠르트 괴델의 불완전성 정리의 핵심에 놓여 있다. 이렇게 자연 언어에서는 당혹스러움인 것이 형식 언어에서는 정보가 된다.

수리논리학의 네 기둥

수리논리학은 19세기 말과 20세기 초에 프레게, 페아노, 러셀, 다비트 힐베르트와 함께, 정확한 물음에 대한 답으로 태어났다. 수학은 어떤 기초 위에 서 있으며 그 기초는 모순에서 자유로운가 하는 물음이다. 오늘날 수리논리학은 끊임없이 서로 얽히는 네 개의 큰 분야로 나뉜다.

증명론: 형식적 증명을 수학적 대상으로, 곧 명시적인 규칙을 따르는 논리식의 유한 열로 연구한다. 체계에서 무엇을 증명할 수 있는지, 체계가 무모순인지, 증명들이 서로 어떻게 변환되는지를 묻는다. 이 강좌의 단원 “연역”은 그 첫 입문이다.
모형 이론: 형식 언어와 그것을 해석하는 구조, 곧 그 모형 사이의 관계를 연구한다. 어떤 구조가 논리식의 집합을 충족하는지, 구조의 어떤 성질이 주어진 언어로 표현될 수 있는지를 묻는다. 진리값 할당을 다루는 단원 “의미론”은 그 가장 초보적인 형태이다.
집합론: 체르멜로와 프렝켈의 공리 같은 정확한 공리로 집합을 연구하며, 그 안에서 거의 모든 수학을 쓸 수 있다. 집합론은 상당 부분 러셀 역설을 피할 필요에서 생겨났다.
계산 가능성 이론: 어떤 문제가 기계적인 절차로 풀리고 어떤 문제가 풀리지 않는지를 연구한다. 강좌에서 보겠지만, 명제 논리는 결정 가능하다. 논리식이 타당한지를 유한한 단계 안에 결정하는 절차가 존재한다. 반면에 술어 논리는 결정 가능하지 않다.

어느 기둥도 다른 기둥을 건드리지 않고는 깊이 연구할 수 없다. 이 강좌의 중심 결과인 완전성은 증명론의 정리이면서 동시에 모형 이론의 정리이며, 그로부터 얻는 결정 가능성은 계산 가능성 이론에 속한다.

강좌의 지도

이 강좌는 논리학의 가장 단순한 언어인 명제 논리의 언어에 대해, 논리 이론이 밟는 길 전체를 네 단원에 걸쳐 걷는다.

언어: 구문론. 두 기호로 된 알파벳과 형성 규칙을 갖춘 대상 언어를 구성하고, 모든 논리식이 단 한 가지로 읽힌다는 것을 증명하며, 귀납법으로 증명하는 법을 배우고, 자연 언어의 진술과 논증을 형식 언어로 번역하면서 번역이 무엇을 보존하고 무엇을 잃는지 짚는다.
연역: 공리와 추론 규칙의 체계를 정하고, 논리식 $\varphi$ 가 논리식의 집합 $\Gamma$ 로부터 연역된다는 것이 무슨 뜻인지 정의한다. 이것을 $\Gamma \vdash \varphi$ 로 쓴다. 이는 타당성의 구문론적 측면, 곧 기호를 그 뜻에 주의하지 않고 규칙에 따라 다루는 일이다.
의미론: 각 할당에서 각 논리식에 진리값을 배정하고, $\varphi$ 가 $\Gamma$ 의 귀결이라는 것이 무슨 뜻인지 정의하며, 이것을 $\Gamma \models \varphi$ 로 쓴다. 곧 $\Gamma$ 의 논리식들을 참으로 만드는 모든 할당이 $\varphi$ 도 참으로 만든다는 것이다. 이는 타당성의 의미론적 측면이며, 이 수업의 정의를 정확하게 만든 것이다.
메타이론: 두 측면이 일치함을 증명한다. 건전성은 연역 가능한 것은 모두 귀결이라고 말하고, 완전성은 모든 귀결이 연역 가능하다고 말한다. 이어서 콤팩트성과, 논리식의 집합이 충족 가능한지를 결정하는 기계적인 방법인 분해를 연구한다.

그렇다면 이 강좌는 추론 자체를 대상으로 하는 수학 이론의 첫 완전한 예이다. 그리고 이 수업에서 보았듯이, 형식 언어에 대한 강좌의 모든 주장은 수학의 엄밀함으로 증명된 메타언어의 문장이 될 것이다.

예제

다음 문제들은 난이도 순으로 이 수업의 구별을 연습한다. 모든 문장이 참인 논증을 논박하기, 모호한 진술의 읽기를 나누기, 대상 언어와 메타언어의 표현을 분류하기, 그리고 역설처럼 보이는 두 추론을 분석하여 정말로 역설인지 결정하기이다.

예제 1모두 참인데도 부당하다

다음 논증은 전제와 결론이 참인데도 부당함을 보여라. “ $6$ 의 배수는 모두 짝수이다. 수 $12$ 는 짝수이다. 그러므로 $12$ 는 $6$ 의 배수이다.”

풀이

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
“ $x$ 는 $6$ 의 배수이다”를 $S(x)$ 로, “ $x$ 는 짝수이다”를 $P(x)$ 로 줄여 쓴다. 전제와 결론은 참이다. $12 = 6 \cdot 2$ 이기 때문이다.
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
형식은 이름 $12$ 를 문자 $c$ 로 바꾸면 얻어진다. 전제가 둘, 결론이 하나이다.
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
전제가 참인 대입례를 찾는다. 첫 전제는 $c$ 에 의존하지 않고, 둘째 전제는 짝수를 요구한다. $c = 4$ 로 잡는다.
$\neg S(\resaltar{4})$
이 대입례의 결론은 거짓이다. $4$ 는 $6$ 의 배수가 아니기 때문이다.
$\resaltar{12 = 6 \cdot 2}$
형식에는 반례가 있다. 그러므로 형식은 부당하고, 논증도 부당하다. 결론의 참은 전제가 아니라 산술에서 온다.

예제 2작용역의 모호성

$L$ 을 수 $4$ , $6$ , $7$ 의 목록이라 하자. 문장 “ $L$ 의 모든 수가 소수가 아니다”에 두 가지 읽기가 있고, 이 목록에서는 한쪽이 참이고 다른 쪽이 거짓임을 보여라.

풀이

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
“ $x$ 는 소수이다”를 $Q(x)$ 로 줄여 쓴다. 첫째 읽기: 부정이 각 수에 작용하며, 문장은 어느 것도 소수가 아니라고 말한다.
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
둘째 읽기: 부정이 주장 전체에 작용하며, 문장은 모두가 소수인 것은 아니라고 말한다.
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
$7$ 은 소수이므로 첫째 읽기의 마지막 항은 거짓이고, 그와 함께 연언 전체도 거짓이다. 첫째 읽기는 거짓이다.
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
$4$ 는 소수가 아니므로 둘째 읽기의 연언은 거짓이고, 그 부정은 참이다. 둘째 읽기는 참이다.
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
두 읽기는 동치가 아니다. 첫째 읽기는 둘째 읽기를 함의하지만 그 역은 성립하지 않으며, 이 목록이 그것을 보여 준다. 수학에서는 둘째 읽기를 “ $L$ 의 수가 모두 소수인 것은 아니다”로, 첫째 읽기를 “ $L$ 의 어떤 수도 소수가 아니다”로 쓴다.

예제 3대상 언어와 메타언어

대상 언어로 기호 $\sigO$ 과 $\sigI$ 의 열을 잡고, 메타언어로 한국어를 잡으며, 임의의 열을 그리스 문자로 나타내기로 하자. 다음 각 표현을 분류하고, 의미가 있는 경우 참인지 결정하여라. (a) $\sigO\sigO\sigI$ . (b) “ $\sigO\sigO\sigI$ 은 세 기호로 되어 있다”. (c) “모든 열 $\varphi$ 에 대하여, 열 $\sigI\varphi$ 는 원판으로 시작한다”. (d) “ $\sigO\sigO\sigI$ 은 참이다”.

풀이

$\resaltar{\sigO\sigO\sigI}$
표현 (a)는 대상 언어에 속한다. 그것은 기호의 열이지 한국어 문장이 아니며, 참도 거짓도 아니다. 그것에 대해 말할 수는 있지만, 그것 자체는 아무것도 주장하지 않는다.
$\sigO \; \sigO \; \sigI \quad (3)$
표현 (b)는 열 (a)를 언급하고 그 기호를 세는 메타언어의 문장이다. 그것은 참이다.
$\resaltar{\sigI}\varphi$
표현 (c)는 메타언어의 문장이다. 문자 $\varphi$ 는 대상 언어의 기호가 아니라 대상 언어의 열들을 움직이는 메타언어의 변항이다. 이 문장은 참이다. $\sigI\varphi$ 는 구성상 원판으로 시작하기 때문이다.
$v_2 = \sigO\sigO\sigI$
표현 (d)는 메타언어에 속하지만 아직 진리값을 갖지 않는다. 열 $\sigO\sigO\sigI$ 은 강좌의 언어의 변항이 될 것이며, 변항은 그 자체로는 참도 거짓도 아니고, 단원 “의미론”에서 할당이 그것에 값을 줄 때에야 참이나 거짓이 된다. 다음 수업에서 그것은 $v_2$ 로 불린다.

예제 4에피메니데스는 거짓말쟁이가 아니다

칠판에 문장 $e$ “이 칠판에 쓰인 모든 문장은 거짓이다”가 쓰여 있다(다른 문장들도 함께 있을 수 있다). 이치성과 진리 도식을 받아들여, $e$ 가 거짓이고 칠판에 다른 참인 문장이 있음을 증명하여라. 또 역설이 생기는 것은 칠판의 다른 문장이 하나도 참이 아닐 때, 그리고 그때뿐임을 이끌어 내어라. $e$ 가 칠판의 유일한 문장일 때가 그러하다.

풀이

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
$O$ 를 칠판의 문장들의 집합이라 하자. $e$ 는 그 가운데 하나이다. 진리 도식에 따라 $e$ 가 참인 것은 $O$ 의 모든 문장이 거짓일 때 그리고 그때에만이다.
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
$e$ 가 참이라면 $O$ 의 모든 문장은 거짓이고, $e$ 는 $O$ 에 속하므로 $e$ 는 거짓이 되며, 이치성에 따라 참이 아니게 된다. 이 상정은 스스로를 논박한다.
$\resaltar{F(e)}$
따라서 $e$ 는 참이 아니다. 이치성에 따라 그것은 거짓이다.
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
진리 도식에 따라 $e$ 가 거짓이라는 것은 $O$ 의 문장이 모두 거짓인 것은 아니라는 뜻이다. 어떤 문장은 참이며, 그것은 거짓인 $e$ 가 아니다.
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
칠판에 다른 참인 문장이 있으면 모든 것이 정합적이다. $e$ 는 그저 거짓일 뿐이다. 반면에 다른 문장이 하나도 참이 아니면, $x$ 로서 $e$ 와 다르면서 $O$ 에 속하고 참인 것은 없으며, 거짓말쟁이에서처럼 모순을 얻는다. 특히 $e$ 가 칠판의 유일한 문장일 때가 그러하다. 따라서 역설이 나타나는지는 경험적 사실, 곧 칠판에 무엇이 쓰여 있는지에 달려 있다.

예제 5비자기 서술적인 것

형용사는 자기 자신에 들어맞으면 자기 서술적이고(“짧은”은 짧은 낱말이다. “한국어의”는 한국어의 낱말이다), 그렇지 않으면 비자기 서술적이다(“긴”은 긴 낱말이 아니다. “영어의”는 영어의 낱말이 아니다). “비자기 서술적인”이 형용사이고 관계 “들어맞는다”가 모든 형용사에 대해 확정되어 있다면 모순에 이름을 증명하여라. 또 어느 가정을 버려야 하는지 결정하여라.

풀이

$\dato{R}{R(x, x)}$
$D$ 를 한국어 형용사들의 모임, $R(x, y)$ 를 관계 “형용사 $x$ 는 낱말 $y$ 에 들어맞는다”라 하자. 형용사 $x$ 는 $R(x, x)$ 이면 자기 서술적이고, $\neg R(x, x)$ 이면 비자기 서술적이다.
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
$h$ 를 형용사 “비자기 서술적인”이라 하자. 그 정의에 따라, 그것이 어떤 형용사에 들어맞는 것은 정확히 그 형용사가 자기 자신에 들어맞지 않을 때이다.
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
$h$ 가 형용사이면 그것은 $D$ 에 속하고, 그 조건은 대각선 보조정리의 조건이다. $x = h$ 로 놓으면 불가능한 동치를 얻는다.
$h \in D \Rightarrow \resaltar{h \notin D}$
대각선 보조정리에 따라 $D$ 의 어떤 대상도 $h$ 의 조건을 충족하지 않는다. $h$ 가 $D$ 에 속하면 모순이 생긴다.
$\resaltar{h \notin D}$
무너지는 것은 둘째 가정이다. “비자기 서술적인”처럼 그 자신이 바로 이 관계로 정의되는 형용사에 대해서는 “들어맞는다”가 정확한 관계가 아니다. 형식 언어에서는 관계 $R$ 이 메타언어에서 정의되고 형용사 $h$ 는 대상 언어에 속하지 않으므로, 조건 $h \in D$ 는 거짓이 되고 모순은 생기지 않는다.

연습 문제

처음 두 문제는 타당성과 모호성을, 셋째 문제는 사용과 언급을 연습한다. 마지막 두 문제는 새로운 역설을 분석하고 언어학 밖에서 대각선 보조정리를 적용할 것을 요구한다. 각 문제에는 힌트가 있으며, 스스로 시도해 본 뒤에 여는 것이 좋다.

연습 문제 1비슷한 두 형식

다음 두 형식을 생각하자. (a) “ $p$ 이면 $q$ . $q$ 가 아니다. 그러므로 $p$ 가 아니다”. (b) “ $p$ 이면 $q$ . $p$ 가 아니다. 그러므로 $q$ 가 아니다”. 어느 것이 타당하고 어느 것이 부당한지 결정하여라. 부당한 것에 대해서는 수에 관한 진술로 반례를 구성하고, 타당한 것에 대해서는 왜 어떤 대입례도 반례가 될 수 없는지 설명하여라.

힌트

형식 (b)에 대해서는 “ $n$ 이 $4$ 의 배수이면 짝수이다”처럼 수의 성질들 사이의 참인 함의와, 첫째 성질은 없지만 둘째 성질은 있는 수를 찾아라. 형식 (a)에 대해서는 전제가 참이라고 가정하고, $p$ 가 참이라면 무슨 일이 일어날지 생각해 보아라.

정답

형식 (a)는 후건 부정식(modus tollens)이라 불리며 타당하다. 전제가 참이고 $p$ 가 참이라면 $q$ 도 참이 되어 둘째 전제에 어긋난다. 형식 (b)는 전건 부정이며 부당하다. “ $6$ 이 $4$ 의 배수이면 $6$ 은 짝수이다. $6$ 은 $4$ 의 배수가 아니다. 그러므로 $6$ 은 짝수가 아니다”는 전제가 참이고 결론이 거짓이다.

연습 문제 2여권, 신분증, 비자

어떤 안내문에 “입국하려면 여권 또는 신분증과 비자가 필요하다”라고 쓰여 있다. 그 두 읽기를 문자 $p$ (여권), $d$ (신분증), $v$ (비자)로 쓰고, 한 읽기로는 입국할 수 있지만 다른 읽기로는 입국할 수 없는 여행자를 기술하여라.

힌트

문제는 비자가 신분증에만 따르는지, 두 서류 가운데 어느 것에나 따르는지이다. 서류를 하나만 가진 여행자로 시험해 보아라.

정답

두 읽기는 $p \vee (d \wedge v)$ 와 $(p \vee d) \wedge v$ 이다. 여권은 있고 비자는 없는 여행자는 첫째 읽기로는 입국할 수 있지만 둘째 읽기로는 입국할 수 없다.

연습 문제 3따옴표

각 문장이 도시에 대해 말하는지 낱말에 대해 말하는지, 그리고 참인지 거짓인지 결정하여라. (a) “로마는 두 글자이다”. (b) “‘로마’는 두 글자이다”. (c) “‘로마’는 이탈리아의 수도이다”. (d) “문장 ‘로마는 이탈리아의 수도이다’는 낱말 ‘로마’를 포함한다”.

힌트

따옴표는 표현을 그 표현의 이름으로 바꾼다. 각 경우에 문장의 주어가 어떤 대상, 곧 도시, 낱말, 문장 가운데 무엇을 가리키는지 생각해 보아라.

정답

(a) 도시에 대해 말하며 거짓이다. 도시에는 글자가 없기 때문이다. (b) 낱말에 대해 말하며 참이다. (c) 낱말에 대해 말하며 거짓이다. 낱말은 수도가 아니기 때문이다. (d) 문장과 낱말에 대해 말하며 참이다.

연습 문제 4카드 한 장의 양면

카드의 한 면에는 문장 $A$ “문장 $B$ 는 참이다”가, 다른 면에는 문장 $B$ “문장 $A$ 는 거짓이다”가 쓰여 있다. 이치성과 진리 도식을 받아들여, $A$ 와 $B$ 에 진리값을 배정할 방법이 없음을 증명하여라. $B$ 가 대신 “문장 $A$ 는 참이다”라고 말한다면 어떻게 되는가?

힌트

각 문장에 대해 진리 도식을 쓰고, $V(A)$ 를 그 자신과 잇는 동치가 나올 때까지 동치들을 이어라. 변형에 대해서도 같은 일을 하고, 어떤 값 배정이 그것을 충족하는지 확인하여라.

정답

첫째 형태에서는 어느 문장도 자기 자신에 대해 말하지 않는데도 거짓말쟁이에서처럼 $V(A) \Leftrightarrow \neg V(A)$ 를 얻는다. 변형에서는 $V(A) \Leftrightarrow V(B)$ 가 두 가지 배정, 곧 둘 다 참이거나 둘 다 거짓인 배정을 허용한다. 모순은 없지만, 그 가운데 어느 것인지 정해 주는 것도 없다.

풀이 과정

풀이

$\dato{A}{V(A) \Leftrightarrow V(B)}$
진리 도식에 따라 $A$ 가 참인 것은 정확히 $B$ 가 참일 때이다.
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
진리 도식에 따라 $B$ 가 참인 것은 정확히 $A$ 가 거짓일 때이다. 이치성에 따라 거짓이라는 것은 참이 아니라는 것이다.
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
두 동치를 이으면 $A$ 의 참은 그 자신의 부정과 동치가 되며, 거짓말쟁이에서처럼 추론할 수 있다. $A$ 가 참이면 참이 아니고, 참이 아니면 참이다.
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
변형에서는 $B$ 에 대한 진리 도식이 $V(B) \Leftrightarrow V(A)$ 를 주며, 이것은 첫째 동치와 합쳐도 두 문장이 같은 값을 가질 것만 요구한다. 정합적인 배정이 둘 있고 모순은 없다.

연습 문제 5칸토어의 대각선

$s_1, s_2, s_3, \ldots$ 을 영과 일로 이루어진 무한 수열들의 임의의 목록이라 하고, $s_x(y)$ 로 제 $y$ 항, 그것도 수열 $s_x$ 의 항을 나타내기로 하자. 대각선 보조정리를 써서, 수열 $d$ , 곧 $d(y) = 1$ ( $s_y(y) = 0$ 일 때)과 $d(y) = 0$ ( $s_y(y) = 1$ 일 때)으로 정해지는 수열이 목록에 나타나지 않음을 증명하여라. 또 번호가 붙은 어떤 목록도 영과 일로 이루어진 모든 수열을 포함하지 않음을 이끌어 내어라.

힌트

모임 $D$ 로 자연수를, 관계 $R(x, y)$ 로 주장 $s_x(y) = 1$ 을 잡아라. 수 $b$ 로서 $s_b = d$ 인 것은 어떤 조건을 충족하겠는가?

정답

$d = s_b$ 라면 수 $b$ 는 $R(b, y) \Leftrightarrow \neg R(y, y)$ 를 모든 $y$ 에 대해 충족하게 되는데, 이것은 대각선 보조정리가 금지한다. 따라서 $d$ 는 각 $s_b$ 와 적어도 제 $b$ 항에서 다르며, 어떤 목록도 모든 수열을 포함하지 않는다.

풀이 과정

풀이

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
$D$ 를 자연수의 집합, $R(x, y)$ 를 제 $y$ 항( $s_x$ 의 항)이 $1$ 과 같다는 주장이라 하자.
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
정의에 따라 $d(y)$ 가 $1$ 과 같은 것은 정확히 $s_y(y)$ 가 $1$ 과 같지 않을 때이다.
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
$d$ 가 목록의 자리 $b$ 에 나타난다고, 곧 $d = s_b$ 라고 가정하자. 그러면 모든 $y$ 에 대하여 $R(b, y)$ 는 $d(y) = 1$ 과 동치이고, 이것은 $\neg R(y, y)$ 와 동치이다.
$d(b) \neq s_b(b)$
대각선 보조정리에 따라 어떤 $b$ 도 이 조건을 충족하지 않는다. 수열 $d$ 는 목록에 나타나지 않는다. 구체적으로, 그것은 $s_b$ 와 제 $b$ 항에서 다르다.
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
목록은 임의였으므로, 번호가 붙은 어떤 목록도 영과 일로 이루어진 모든 수열을 포함하지 않는다. 각 목록에는 적어도 그 자신의 대각선 수열이 빠져 있다.