언어: 종합과 도전 과제

요약

이 수업은 명제 논리의 언어를 다루는 단원을 마무리한다. 타당성과 참의 구별, 그리고 역설의 분석에서 논리식의 유일 판독성과 진술 및 논증의 형식화에 이르는 연역의 사슬을 다시 세우면서, 고리마다 어떤 원리가 쓰이고 그것이 어느 수업에서 증명되는지를 짚는다. 이룬 것을 강좌 계획에 비추어 자리매김하고, 이미 세운 언어가 왜 연역을 다루는 다음 단원의 물음을 던지는지 설명한다. 마무리 평가에서는 입문 평가의 기능을 되풀이하며, 각 수업의 문제보다 어렵고 여러 수업의 도구를 엮어야 하는 여섯 개의 도전 과제로 끝맺는다.

학습 목표

단원의 결과들의 논리적 순서를 다시 세우고, 각 결과가 기대는 원리와 그것이 증명되는 수업을 밝힌다.
닫힘 원리, 단어로의 분해, 무게 보조정리, 유일 판독성이 어떻게 이어지는지, 그리고 왜 재귀적 정의와 형식화들의 비교가 유일 판독성에 달려 있는지 설명한다.
단원이 증명한 것을, 가정으로 받아들인 것(이치성, 진리 도식, 귀납법의 원리, 부정논리합의 읽기)과 다음 단원들로 넘긴 것에서 구별한다.
대각선 보조정리, 기호열의 개수 세기, 논리식에 관한 귀납법, 무게 논증, 약어 펼치기를 엮는 문제를 푼다.

단원에서 이룬 것

이 단원은 두 기호로 된 알파벳에서 출발하여 모든 논리식이 한 가지 방식으로만 읽히는 언어를 세우고, 그 언어의 성질을 엄밀하게 증명하며, 그 언어와 우리가 추론하는 언어 사이에 다리를 놓는 것을 목표로 삼았다. 이 목표는 몇 가지 유보와 함께 이루어졌고, 유보는 저마다 제자리에서 밝혀 두었다. 이치성과 진리 도식은 첫 수업이 참으로서가 아니라 명시적 가정으로서 받아들여, 둘을 동시에 유지할 때 무슨 일이 일어나는지 살폈다. 자연수에 관한 귀납법의 원리는 페아노의 다섯째 공리로서 받아들인다. 부정논리합의 비형식적 읽기는 규약으로 정하며, 의미론 단원이 그것을 정의로 바꿀 것이다. 그리고 집합론에서 꼭 필요한 것(소속, 포함, 합집합)은 필요한 곳에서 가르쳤다. 이러한 유보 아래, 지나온 길은 네 구간으로 이루어진 하나의 연역 사슬로 읽을 수 있다.

추론하기와 언어에 대해 말하기

수리논리학이란 무엇인가 수업은 강좌의 대상을 정했다. 그것은 진술의 참, 곧 각 과학이 다룰 일이 아니라, 참의 전달이다. 논증이 타당한 것은 그 형식이 전제가 참이고 결론이 거짓인 대입례를 하나도 허용하지 않을 때이며, 이 정의로부터 타당성이 보장하는 유일한 것이 도출되었다. 전제가 참이면 결론도 참이다. 따라서 결론이 거짓인 타당한 논증에는 거짓인 전제가 있고, 형식이 부당한 것은 정확히 그것이 반례를 가질 때이다. 같은 결과가 역설의 분석을 하나의 절차로 바꾸었다. 모순으로 끝나는 추론의 단계들이 타당하다면 어떤 가정이 거짓이며, 역설을 푼다는 것은 그것이 어느 것인지 찾는 일이다. 거짓말쟁이는 이렇게 다루어졌다. 거기서는 자기 자신이 거짓이라고 선언하는 문장에 대해 이치성과 진리 도식을 동시에 유지할 수 없다. 베리 역설과 형용사 “비자기 서술적인”도 이렇게 다루어졌다. 이발사에서는 일반적인 보조정리, 곧 대각선 보조정리를 뽑아냈고, 그것은 그런 이발사가 존재하지 않음과 제한 없는 내포 원리가 모순적임을 증명한다. 끝으로 이 수업은 대상 언어와 메타언어의 구별, 그리고 표현의 사용과 그 언급의 구별을 세웠으며, 이 구별이 이후의 모든 것을 다스린다. 논리식에 관한 단원의 결과들은 논리식이 아니라 메타정리이다.

원과 원판의 언어

명제 논리의 언어 수업은 집합과 기호열을 도입하고, 각 길이의 기호열을 세었으며( $2^{n}$ 개가 길이 $n$ 이고, $2^{N + 1} - 2$ 개가 길이 $1$ 부터 $N$ 까지이다), 기본 언어를 세웠다. 변항 $v_n = \sigO^{n}\sigI$ 과, 두 논리식 $\varphi$ 와 $\psi$ 로부터 $\sigI\varphi\psi$ 를 만드는 단 하나의 규칙이다. “그 밖의 것은 논리식이 아니다”라는 조항은 논리식을 모든 닫힌 집합에 속하는 기호열로 정의함으로써 엄밀해졌고, 이 정의로부터 닫힘 원리가 도출되었다. 닫힘 원리로 증명된 것은, 모든 논리식이 변항이거나 $\sigI\varphi\psi$ 이며 둘 다는 아니라는 것, 모든 논리식이 원판으로 끝난다는 것, 그리고 홀수 개의 원판을 포함한다는 것이다. 변항과 낱개의 원판이 접두 부호를 이룬다는 관찰에서 단어로의 유일한 분해가 나왔고, 그와 함께 무게의 개념이 나왔다. 이 수업은 또한 이후에 쓰는 메타언어도 세웠다. 메타변항, $(\varphi \downarrow \psi)$ 로 쓰는 부정논리합, 그리고 여섯 개의 공식 약어이다. 각 약어는 그보다 앞선 약어들로부터 단 한 번 정의되므로, 약어를 쓴 모든 표현은 단 하나의 기호열을 가리킨다.

귀납법과 유일 판독성

자연수와 논리식에 관한 귀납법 수업은 앞 수업이 “이와 같이 계속하여”로 처리한 셈들을 정당화하고, 단순한 귀납법에서 강한 귀납법을 이끌어 냈으며, 그것을 길이에 적용하여 구조적 귀납법을 얻었다. 구조적 귀납법은 논리식으로 옮겨진 자연수에 관한 귀납법 바로 그것으로 드러난다. 이 도구로 무게 보조정리를 증명했다. 모든 논리식의 무게는 $+1$ 이고, 비어 있지 않은 진 단어 단위 접두사의 무게는 모두 많아야 $0$ 이다. 이로부터 차례로, 어떤 논리식도 다른 논리식의 진 접두사가 아니라는 것과, 모든 복합 논리식이 한 가지 방식으로만 읽힌다는 것이 따라 나온다. 유일 판독성은 단원의 나머지 전부가 매달린 고리이다. 그것은 언어 수업이 갚아 나가는 빚으로 묘사한 결정 절차를 정당화하고, 재귀적 정의들(길이, 변항과 연결 원판의 개수, 부분식, 깊이, 대입)을 정당하게 만든다. 그것이 없다면 이 정의들은 한 논리식에 서로 다른 두 값을 줄 수도 있다.

한국어에서 논리식으로

자연어의 형식화 수업은 우리가 말하는 언어로 다리를 놓았다. 문자 $p$ , $q$ , $r$ , $s$ , $t$ 를 다섯 개의 정해진 변항의 이름으로 삼는 규약을 정하고, 모든 형식화에 사전을 밝히도록 요구했으며, 부정논리합의 규약상의 읽기 하나만으로부터 각 약어의 읽기를 이끌어 냈다. 유일 판독성으로 같은 연결사들을 서로 다르게 묶은 두 방식이 서로 다른 논리식임을 증명했고, 길이의 재귀적 정의로 펼친 약어의 길이를 계산했는데, 이는 형식화들을 가려내는 빠른 기준을 준다. 실질 조건문이 거짓이 되는 것은 전건이 참이고 후건이 거짓일 때뿐이라는 것, 그리고 그것이 부분들의 참에만 의존하는 읽기 가운데 수학의 조건 정리들을 참으로 만드는 유일한 읽기라는 것을 보였다. 형식화가 잃는 것(양화사, 시간, 인과성, 양상)을 짚었고, 끝으로 논증 전체를 전제 집합 $\Gamma$ 와 결론으로 형식화했다.

다음 그림은 네 구간을 하나의 사슬로 모은 것이다. 가운데 열의 각 마디는 정의나 결과이며, 논리적 순서에 따라 번호가 붙고, 그 증명이 쓰는 앞의 고리들과 호로 이어진다. 그 둘레에 떠 있는 것이 받침, 곧 사슬이 거듭 의지하는 원리들이다. 각 받침은 자신에게 기대는 고리들과 실선으로, 자신이 세워지는 고리와 점선으로 이어지며, 증명 없이 받아들이는 받침은 둥근 테로 그려진다. 받침을 누르면 그것을 쓰는 고리가 모두 강조되고, 각 고리는 그것이 증명되는 수업으로 이어진다. 결정 절차는 언어 수업에서 설명되지만, 그 논리적 자리는 그것이 기대는 유일 판독성 다음이라는 점에 주목하자.

사슬의 받침

A이치성. 모든 명제는 참이거나 거짓이며, 둘 다는 아니다. 거짓이라는 것은 참이 아니라는 것과 동치이다. 역설의 분석에서 명시적 가정으로 받아들인다. 이 단원에서는 증명 없이 받아들인다.
B진리 도식. 문장이 참인 것은 그 문장이 말하는 것이 성립할 때 그리고 그때에만이다. 명시적 가정으로 받아들인다. 타르스키의 해결은 이를 유지하지만, 자기 자신의 진리 술어를 포함하지 않는 언어의 문장들에 대해서만이다. 이 단원에서는 증명 없이 받아들인다.
C귀납법의 원리. 어떤 성질이 $1$ 에 대해 성립하고, 자연수 $k$ 에 대해 성립할 때마다 $k + 1$ 에 대해서도 성립하면, 그 성질은 모든 자연수에 대해 성립한다. 이것은 페아노의 다섯째 공리이며, 받아들인다. 이 단원에서는 증명 없이 받아들인다.
D대각선 보조정리. 어떤 모임의 어떤 대상 $b$ 도 $R(b, x) \Leftrightarrow \neg R(x, x)$ 를 그 모임의 모든 $x$ 에 대해 만족하지 않는다. 확립되는 곳: 3. 대각선 보조정리.
E닫힘 원리. 모든 변항이 가지며 $\varphi$ 와 $\psi$ 에서 $\sigI\varphi\psi$ 로 넘어가는 성질은 모든 논리식이 가진다. 확립되는 곳: 5. 닫힘 원리.
F구조적 귀납법. 길이에 관한 강한 귀납법에서 이끌어 낸, 논리식의 복잡도에 관한 귀납법. 기초 단계는 변항들이고, 귀납 단계는 단 하나의 형성 규칙이다. 확립되는 곳: 9. 구조적 귀납법.
G유일 판독성. $\sigI\varphi\psi = \sigI\varphi'\psi'$ 이고 네 기호열이 모두 논리식이면, $\varphi = \varphi'$ 이고 $\psi = \psi'$ 이다. 확립되는 곳: 11. 유일 판독성.
H부정논리합의 읽기. 논리식 $(\varphi \downarrow \psi)$ 가 참인 것은 정확히 $\varphi$ 와 $\psi$ 가 모두 거짓일 때이다. 이것은 규약으로 정하는 유일한 읽기이며, 나머지 읽기는 이로부터 이끌어 내고, 의미론 단원이 이를 엄밀하게 할 것이다. 이 단원에서는 증명 없이 받아들인다.

제1구간 추론하기와 언어에 대해 말하기
- 타당성을 참과 구별하고, 부당한 형식을 반례로 논박한다.
- 자연어의 중의성을 알아보고, 진술의 읽기들을 가른다.
- 대상 언어를 메타언어와 구별하고, 표현의 사용을 그 언급과 구별한다.
- 역설의 가정들을 떼어 내고 어느 것을 버려야 하는지 결정하여 역설을 분석한다.
1. 타당성이 보장하는 것. 논증이 타당하고 그 전제가 모두 참이면 그 결론은 참이다. 따라서 결론이 거짓인 타당한 논증에는 거짓인 전제가 있고, 형식이 부당한 것은 정확히 그것이 반례를 가질 때이다.
  증명된 수업: 수리논리학이란 무엇인가.
2. 거짓말쟁이 역설. 문장 $m$ , 곧 “문장 $m$ 은 거짓이다”에 적용하면 이치성과 진리 도식은 $V(m) \Leftrightarrow \neg V(m)$ 을 준다. $m$ 을 포함하는 언어에서는 두 가정 가운데 하나를 버려야 하며, 타르스키의 출구는 어떤 언어도 자기 자신의 진리 술어를 포함하지 않게 하는 것이다. 그러면 $m$ 은 만들 수 없다.
  사용: 1. 타당성이 보장하는 것. 받침: A (이치성), B (진리 도식). 증명된 수업: 수리논리학이란 무엇인가.
3. 대각선 보조정리. $R$ 이 모임 $D$ 의 대상들 사이의 관계이고 각 $R(x, y)$ 가 참이거나 거짓이면, 어떤 $b$ ( $D$ 의 대상)도 $R(b, x) \Leftrightarrow \neg R(x, x)$ 를 모든 $x$ ( $D$ 의 대상)에 대해 만족하지 않는다.
  받침: A (이치성). 증명된 수업: 수리논리학이란 무엇인가.
4. 이발사와 러셀. 스스로 면도하지 않는 마을의 남자들만을 정확히 면도해 주는 마을의 남자는 존재하지 않는다. 그리고 제한 없는 내포 원리는 모순적이다. 집합 $Z = \{ x : x \notin x \}$ 의 존재를 주장하기 때문이다.
  받침: D (대각선 보조정리). 증명된 수업: 수리논리학이란 무엇인가.
제2구간 원과 원판의 언어
- 기호열의 집합을 기술하고, 각 길이의 기호열을 센다.
- 논리식을 가장 작은 닫힌 집합으로 정의하고, 이로부터 닫힘 원리를 이끌어 낸다.
- 모든 논리식의 성질을 증명하고, 그것으로 기호열을 걸러 낸다.
- 기호열을 단어로 분해하고, 약어를 기본 언어까지 펼친다.
1. 닫힘 원리. 논리식의 집합 $\mathcal{F}$ 는 변항 $v_n = \sigO^{n}\sigI$ 을 포함하고, $\varphi$ 와 $\psi$ 와 함께 $\sigI\varphi\psi$ 도 포함하는 가장 작은 기호열 집합이다. 따라서 변항들이 가지며 $\varphi$ 와 $\psi$ 에서 $\sigI\varphi\psi$ 로 넘어가는 성질은 모든 논리식이 가진다.
  증명된 수업: 명제 논리의 언어.
2. 논리식의 꼴. 모든 논리식은 변항이거나 $\sigI\varphi\psi$ ( $\varphi$ 와 $\psi$ 는 논리식)이며, 둘 다는 아니다. 모든 변항은 $\sigO$ 으로 시작하고, 모든 복합 논리식은 $\sigI$ 으로 시작한다.
  받침: E (닫힘 원리). 증명된 수업: 명제 논리의 언어.
3. 마지막 기호와 원판의 개수. 모든 논리식은 원판으로 끝나고 홀수 개의 원판을 포함한다. 따라서 두 논리식의 연접도, 기호열 $\sigI\varphi$ 도 논리식이 아니다.
  받침: E (닫힘 원리). 증명된 수업: 명제 논리의 언어.
4. 단어로의 분해. 원판으로 끝나는 모든 기호열은 단어, 곧 변항 $\sigO^{n}\sigI$ 과 낱개의 원판으로 한 가지 방식으로만 분해된다. 각 단어는 자신의 유일한 원판으로 끝나고, 어떤 단어도 다른 단어의 진 접두사가 아니기 때문이다.
  증명된 수업: 명제 논리의 언어.
제3구간 귀납법과 유일 판독성
- 단순한 귀납법과 강한 귀납법으로 증명하고, 이로부터 논리식의 복잡도에 관한 귀납법을 이끌어 낸다.
- 무게 보조정리를 증명하고, 유일 판독성을 이끌어 낸다.
- 기호열이 논리식인지 판정하고, 그 형성 과정을 다시 세운다.
- 논리식 위의 함수를 재귀로 정의하고, 그것들 사이의 관계를 증명한다.
1. 구조적 귀납법. 강한 귀납법은 단순한 귀납법에서 이끌어 내며, 길이에 적용하면 복잡도에 관한 귀납법의 원리를 준다. 변항들이 어떤 성질을 가지고 그 성질이 $\varphi$ 와 $\psi$ 에서 $\sigI\varphi\psi$ 로 넘어가면, 모든 논리식이 그 성질을 가진다.
  사용: 6. 논리식의 꼴. 받침: C (귀납법의 원리). 증명된 수업: 자연수와 논리식에 관한 귀납법.
2. 무게 보조정리. 변항의 각 출현의 무게를 $+1$ , 각 연결 원판의 무게를 $-1$ 로 하면, 모든 논리식의 무게는 $+1$ 이고, 논리식의 비어 있지 않은 진 단어 단위 접두사의 무게는 모두 많아야 $0$ 이다. 특히 모든 논리식에서 변항의 출현은 연결 원판보다 하나 많다.
  사용: 8. 단어로의 분해. 받침: F (구조적 귀납법). 증명된 수업: 자연수와 논리식에 관한 귀납법.
3. 유일 판독성. 어떤 논리식도 다른 논리식의 진 접두사가 아니다. 따라서 $\sigI\varphi\psi = \sigI\varphi'\psi'$ 이고 네 기호열이 모두 논리식이면, $\varphi = \varphi'$ 이고 $\psi = \psi'$ 이다.
  사용: 7. 마지막 기호와 원판의 개수, 8. 단어로의 분해, 10. 무게 보조정리. 증명된 수업: 자연수와 논리식에 관한 귀납법.
4. 결정 절차. $\sigO$ 으로 끝나는 기호열은 논리식이 아니다. $\sigI$ 으로 끝나면 단어로 분해한다. 첫 단어가 변항이면, 그 기호열은 그 변항이 유일한 단어일 때 그리고 그때에만 논리식이다. 첫 단어가 원판이면 그 다음부터 빚을 센다. 빚이 한 번도 영이 되지 않으면 기호열은 논리식이 아니고, 영이 되면 $\varphi$ 와 $\psi$ 사이의 자르는 자리는 빚이 처음으로 영이 되는 곳이며, 각 부분을 같은 방식으로 조사한다. 단, 빈 기호열은 논리식이 아니다.
  사용: 6. 논리식의 꼴, 7. 마지막 기호와 원판의 개수, 8. 단어로의 분해. 받침: G (유일 판독성). 증명된 수업: 명제 논리의 언어.
5. 재귀에 의한 정의. 각 변항에 대한 값과, $\sigI\varphi\psi$ 의 값을 $\varphi$ , $\psi$ 와 그 값들로부터 계산하는 규칙이 주어지면, 그것들을 지키는 논리식 위의 함수가 정확히 하나 존재한다. 이렇게 길이, 부분식, 깊이, 그리고 늘 논리식을 낳는 대입이 정의된다.
  사용: 6. 논리식의 꼴. 받침: C (귀납법의 원리), F (구조적 귀납법), G (유일 판독성). 증명된 수업: 자연수와 논리식에 관한 귀납법.
제4구간 한국어에서 논리식으로
- 명시적인 사전으로 진술을 형식화하고, 각 연결사의 작용역을 정한다.
- 약어를 펼쳐 두 형식화가 같은 논리식인지 판정한다.
- 실질 조건문을 일상 언어의 “~이면”과 구별하고, 형식화가 잃는 것을 짚는다.
- 논증 전체를 전제 집합과 결론으로 형식화한다.
1. 약어의 길이. $L(\varphi) = a$ 이고 $L(\psi) = b$ 이면, $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ , $(\varphi \wedge \psi)$ 의 기호열의 길이는 $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ , $8a + 8b + 15$ 이다. 길이가 다른 두 형식화는 서로 다른 논리식이다.
  사용: 13. 재귀에 의한 정의. 증명된 수업: 자연어의 형식화.
2. 작용역과 서로 다른 논리식. 묶음 $((p \wedge q) \vee r)$ 과 $(p \wedge (q \vee r))$ 은 서로 다른 기호열이다. 둘이 같다면, 유일 판독성을 두 번 적용하여 변항 $r$ 이 복합 논리식 $(p \wedge q)$ 와 같아야 하게 된다.
  사용: 6. 논리식의 꼴. 받침: G (유일 판독성). 증명된 수업: 자연어의 형식화.
3. 실질 조건문. 함의 $(\varphi \rightarrow \psi)$ 는 $(\neg\varphi \vee \psi)$ 의 약어이며, 거짓이 되는 것은 $\varphi$ 가 참이고 $\psi$ 가 거짓일 때뿐이다. 이것은 부분들의 참에만 의존하는 읽기 가운데 수학의 조건 정리들을 참으로 만드는 유일한 읽기이다.
  받침: H (부정논리합의 읽기). 증명된 수업: 자연어의 형식화.

연역을 향하여. 사슬은 언어가 세워지고 논증이 전제 집합과 결론으로 형식화된 곳에서 멈춘다. 남은 것은 한 논리식이 언제 다른 논리식들로부터 따라 나오는지를 정하는 일이다. 먼저 다음 단원에서 규칙에 따라 기호를 다루고, 그다음에 그것들의 참을 살핀다.