27강 문제 5에서 유한집합의 성질 하나가 무한집합에서 깨지는 것을 보았습니다. , 은 단사인데 전사가 아닙니다. 유한집합에서는 있을 수 없는 일입니다. 그때는 예외처럼 넘겼지만, 이 강의는 그 실패가 무한집합의 정의 자체임을 보입니다.
여기서 답할 질문은 이것입니다. 무한집합끼리도 크기를 비교할 수 있습니까. 정수는 자연수보다 많습니까. 유리수는 어떻습니까. 실수는 어떻습니까. 답은 놀랍습니다. 정수와 유리수는 자연수와 같은 크기이고, 실수는 더 큽니다. 그리고 더 큰 무한이 끝없이 이어집니다.
문제. 를 양의 짝수 전체의 집합이라고 합니다.
(1) 는 의 진부분집합입니다. 그런데도 두 집합의 크기가 같다고 말할 수 있습니까?
(2) 그렇게 말할 수 있으려면 크기가 같다는 것을 어떻게 정의해야 합니까?
생각의 실마리. 유한집합에서 크기가 같다는 것은 원소 개수가 같다는 뜻인데, 무한집합에서는 개수를 셀 수 없습니다. 대신 개수를 세지 않고도 크기를 비교하는 방법을 생각합니다. 양치기가 양의 수를 모른 채 돌멩이 하나씩 짝지어 두는 것처럼, 짝을 지을 수 있는지만 보면 어떻겠습니까.
풀이. (1) 유한집합이라면 불가능합니다. 진부분집합은 원소가 적어도 하나 빠져 있으므로 크기가 반드시 작습니다. 그러나 무한집합에서는 사정이 다릅니다.
를 으로 정의합니다. 이 함수가 전단사임을 확인합니다.
단사입니다. 이면 입니다.
전사입니다. 임의의 를 잡으면 이 양의 짝수이므로 인 자연수 가 있고 입니다.
즉 의 원소와 의 원소가 하나도 남김없이 짝지어집니다.
빠지는 원소가 양쪽 모두 없으므로 크기가 같다고 말할 근거가 있습니다.
(2) 개수를 세지 않고 짝짓기만으로 크기를 비교하는 정의가 필요합니다. 두 집합 사이에 전단사가 존재하면 크기가 같다고 정의하면 (1)의 관찰이 그대로 정당화됩니다.
이 문제에서 배우는 것: 대등과 무한집합의 정의.
두 집합 와 사이에 전단사 가 존재할 때 두 집합이 대등하다고 하고 로 씁니다. 그리고 대등한 두 집합은 크기가 같다고 말합니다.
이 정의가 유한집합에서 기존 개념과 어긋나지 않는지 확인해 둡니다. 원소가 개인 두 유한집합 사이에는 전단사가 존재하고, 원소 개수가 다르면 27강 확인 5-1과 5-2에서 본 대로 전단사가 존재하지 않습니다. 그러므로 새 정의는 유한집합에서 원소 개수 비교와 정확히 같습니다. 기존 개념을 확장하되 어긋나지 않는 것이 좋은 정의의 조건입니다.
대등 관계는 다음 세 성질을 가집니다. 모두 28강의 도구로 증명됩니다.
| 성질 | 근거 |
|---|---|
| 가 전단사입니다 | |
| 이면 | 전단사의 역함수도 전단사입니다 |
| 이고 이면 | 전단사의 합성은 전단사입니다 |
이제 무한을 정의할 수 있습니다. 자기 자신의 진부분집합과 대등한 집합을 무한집합이라고 합니다. 문제의 (1)이 이 무한집합임을 보인 것입니다. 유한집합은 이런 일이 불가능하므로 이 정의는 유한과 무한을 정확히 갈라 놓습니다.
27강 문제 5의 동치가 무한에서 깨졌던 것이 예외가 아니라 무한의 본질이었습니다. 그 실패를 정의로 삼은 것입니다.
바로 확인.
확인 1-1. 과 가 대등함을 보이세요.
답. 가 전단사입니다. 단사는 자명하고, 임의의 에 대해 가 자연수이므로 전사입니다.
확인 1-2. 과 가 대등함을 보이세요.
답. 이 전단사입니다. 자연수에서 제곱이 단사이고, 완전제곱수 전체를 공역으로 잡았으므로 전사입니다.
확인 1-3. 유한집합이 자기 진부분집합과 대등할 수 있습니까?
답. 없습니다. 진부분집합은 원소가 더 적으므로 27강 문제 18에 따라 전사가 될 수 없습니다. 이 불가능성이 유한집합의 특징입니다.
문제. 가 과 대등함을 증명하세요. 즉 모든 정수를 자연수로 번호 붙여 빠짐없이 나열할 수 있음을 보이세요.
생각의 실마리. 정수를 순서로 세려고 하면 시작점이 없어 실패합니다. 대신 에서 출발해 양쪽을 번갈아 가며 세어 봅니다. 그렇게 나열하면 어떤 정수든 유한한 번호를 받습니다.
풀이. 다음과 같이 나열합니다.
번이 , 번이 , 번이 , 번이 , 번이 입니다. 이 규칙을 식으로 적습니다.
를 넣으면 가 나옵니다. 나열 순서가 조금 달라지지만 정수 전체를 훑는다는 점은 같습니다.
단사임을 보입니다. 홀수 은 음이 아닌 정수로, 짝수 은 음의 정수로 갑니다. 두 무리의 상이 겹치지 않으므로 서로 다른 무리에서 온 값은 다릅니다. 같은 무리 안에서는 각 식이 일차식이라 단사입니다.
전사임을 보입니다. 임의의 정수 을 잡습니다. 이면 이 홀수인 자연수이고 입니다. 이면 이 짝수인 자연수이고 입니다. 어느 경우든 도달합니다.
따라서 는 전단사이고 입니다.
이 문제에서 배우는 것: 셀 수 있는 집합.
과 대등한 집합을 셀 수 있는 무한집합이라고 합니다. 유한집합까지 포함해 부를 때는 셀 수 있는 집합이라고 합니다.
셀 수 있다는 것은 곧 원소 전체를 하나의 무한 목록으로 빠짐없이 적을 수 있다는 뜻입니다.
이 목록이 갖춰야 할 조건이 두 가지입니다.
겹침없음 조건은 사실 느슨하게 다뤄도 됩니다. 겹치는 목록이 있으면 중복을 지워 나가면 되기 때문입니다. 그래서 실제 증명에서는 빠짐없이 나열할 수 있는지만 확인하는 경우가 많습니다.
가 과 대등하다는 결과는 처음에는 이상하게 들립니다. 정수가 자연수를 포함하고도 남는데 크기가 같다니 말이 되지 않아 보입니다. 그러나 문제 1에서 정한 정의를 따르면 그것이 정확히 옳습니다. 무한집합에서는 전체가 부분보다 크다는 유한의 직관이 성립하지 않습니다.
바로 확인.
확인 2-1. 위 에서 과 을 각각 구하세요.
답. 이 홀수이므로 이고, 이 짝수이므로 입니다.
확인 2-2. 정수 는 몇 번째로 나옵니까?
답. 이므로 입니다. 번째입니다.
확인 2-3. 셀 수 있는 집합의 무한 부분집합도 셀 수 있습니까?
답. 셀 수 있습니다. 원래 목록에서 그 부분집합에 속하는 원소만 순서대로 골라 남기면 새 목록이 되며, 부분집합이 무한이므로 목록도 끝나지 않습니다.
문제. 가 셀 수 있는 집합임을 증명하세요. 유리수는 임의의 두 유리수 사이에 무수히 많은 유리수가 있을 만큼 빽빽한데도 그렇습니까?
생각의 실마리. 크기 순으로 나열하려고 하면 실패합니다. 다음에 오는 유리수가 무엇인지 정할 수 없기 때문입니다. 크기 순을 포기하고 다른 기준을 찾습니다. 유리수는 분자와 분모라는 정수 두 개로 정해지므로, 정수쌍을 나열할 수 있으면 유리수도 나열할 수 있습니다. 정수쌍을 어떻게 훑을지 격자에 그려 봅니다.
풀이. 먼저 양의 유리수를 나열합니다. 양의 유리수는 꼴이므로 자연수의 순서쌍 와 대응합니다. 이 순서쌍들을 격자에 놓습니다. 가로가 분자 , 세로가 분모 입니다.
이 격자를 대각선을 따라 훑습니다. 가 작은 것부터 세는 것입니다.
각 대각선에는 원소가 유한개뿐이므로 이 순서로 세면 어떤 순서쌍이든 유한한 번호를 받습니다. 순서쌍 는 늦어도 번째 대각선에서 나오고, 그 앞의 대각선들에 있는 원소가 유한하기 때문입니다.
이 목록에는 처럼 이미 나온 값과 같은 것이 중복해 나타납니다. 문제 2에서 확인한 대로 중복은 지워 나가면 되므로 양의 유리수 전체를 빠짐없이 나열할 수 있습니다.
이제 전체 유리수로 넓힙니다. 양의 유리수 목록을 라 하고 문제 2의 지그재그를 씁니다.
모든 유리수가 이 목록 어딘가에 나타나므로 는 셀 수 있습니다.
이 문제에서 배우는 것: 대각선 나열과 셀 수 있음의 보존.
이 증명에서 쓴 기법이 대각선 나열입니다. 두 방향으로 무한히 뻗은 격자를 한 줄로 펴는 방법이며, 한 방향씩 훑으면 첫 줄에서 영영 벗어나지 못하지만 대각선으로 훑으면 유한 시간 안에 모든 칸에 도달합니다.
이 기법에서 다음 사실이 따라 나옵니다.
셀 수 있는 집합에 대한 유용한 성질을 정리합니다.
| 연산 | 결과 |
|---|---|
| 셀 수 있는 집합의 부분집합 | 셀 수 있습니다 |
| 셀 수 있는 두 집합의 합집합 | 셀 수 있습니다 |
| 셀 수 있는 두 집합의 곱집합 | 셀 수 있습니다 |
| 셀 수 있는 집합을 셀 수 있게 많이 합집합 | 셀 수 있습니다 |
즉 셀 수 있는 것들을 유한하거나 셀 수 있게 많이 조합해서는 셀 수 있음을 벗어날 수 없습니다. 그렇다면 셀 수 없는 집합이 있기는 한지 의심스러워집니다. 유리수처럼 빽빽한 집합조차 셀 수 있었기 때문입니다.
빽빽함과 크기는 다른 개념이라는 점도 여기서 분명해집니다. 임의의 두 유리수 사이에 무수히 많은 유리수가 있다는 사실은 나열 가능성과 아무 관계가 없습니다. 나열은 크기 순서를 따를 필요가 없기 때문입니다.
바로 확인.
확인 3-1. 대각선 나열에서 인 대각선에는 순서쌍이 몇 개 있습니까?
답. 개입니다. 입니다. 일반적으로 인 대각선에는 개가 있습니다.
확인 3-2. 는 셀 수 있습니까?
답. 셀 수 있습니다. 이므로 입니다.
확인 3-3. 유리수를 크기 순으로 나열할 수 없는 이유를 쓰세요.
답. 어떤 유리수 바로 다음에 오는 유리수가 없기 때문입니다. 인 두 유리수 사이에는 항상 가 있으므로 다음 원소를 정할 수 없습니다.
문제. 구간 의 실수 전체가 셀 수 없음을 증명하세요.
생각의 실마리. 셀 수 있다면 목록으로 적을 수 있습니다. 24강의 귀류법을 씁니다. 목록이 있다고 가정한 뒤 그 목록에 없는 실수를 하나 만들어 모순을 얻습니다. 각 실수를 소수로 적어 놓고, 만들려는 수의 번째 자리를 목록의 번째 수와 다르게 정하면 어떻게 됩니까.
풀이. 의 실수가 셀 수 있다고 가정합니다. 그러면 모두 목록으로 적을 수 있습니다.
여기서 는 의 소수 번째 자리 숫자입니다.
이제 새 실수 를 다음 규칙으로 만듭니다.
즉 의 번째 자리를 의 번째 자리와 다르게 정합니다. 대각선 위의 숫자들을 모두 바꾼 것입니다.
는 소수점 아래가 와 으로만 이루어지므로 과 사이의 실수입니다. 따라서 이고, 목록이 빠짐없다는 가정에 따라 인 가 있어야 합니다.
그런데 와 의 소수 번째 자리를 비교하면 입니다. 만드는 규칙이 그랬기 때문입니다. 두 수의 자릿수가 하나라도 다르면 두 수는 다릅니다. 따라서 입니다.
**이면서 **이므로 모순입니다. 따라서 처음 가정이 틀렸고 은 셀 수 없습니다.
숫자를 와 으로만 고른 데는 이유가 있습니다. 이나 를 쓰면 처럼 같은 실수가 두 가지 소수 표기를 가지는 경우가 생겨 "자릿수가 다르면 수도 다르다"는 단계가 무너집니다. 와 만 쓰면 그런 표기가 나타나지 않습니다.
이 문제에서 배우는 것: 대각선 논법과 셀 수 없는 집합.
과 대등하지 않은 무한집합을 셀 수 없는 집합이라고 합니다. 방금 이 그런 집합임을 보였고, 가 을 포함하므로 도 셀 수 없습니다.
여기서 쓴 대각선 논법의 구조를 정리합니다.
24강 문제 3에서 소수의 무한성을 증명할 때와 같은 뼈대입니다. 유한하다고 가정해 목록을 만들고 목록 밖의 새 원소를 만들어 모순을 얻었습니다. 여기서는 유한 대신 셀 수 있음을 가정했을 뿐 발상이 같습니다.
이제 무한에도 크기 차이가 있음이 확인되었습니다.
가 의 부분집합이고 둘 다 무한인데 크기가 다릅니다. 그리고 , 즉 무리수 전체가 셀 수 없다는 것도 따라 나옵니다. 만약 셀 수 있다면 와 합쳐도 셀 수 있어야 하는데 는 셀 수 없기 때문입니다.
이 결과를 해석하면 이렇습니다. 무리수가 유리수보다 압도적으로 많습니다. 24강에서 하나를 무리수로 보이는 데 증명 한 편이 필요했지만, 실제로는 무리수가 실수의 거의 전부입니다.
바로 확인.
확인 4-1. 대각선 논법에서 만든 가 에 속하는 이유를 쓰세요.
답. 소수점 아래 자리가 모두 또는 이므로 값이 이상 이하이고, 이는 과 사이입니다.
확인 4-2. 숫자를 과 로 골랐다면 어디가 문제입니까?
답. 처럼 한 실수가 두 표기를 가지는 경우가 생겨, 자릿수가 다른데도 같은 수일 수 있습니다. 그러면 라는 단계가 성립하지 않습니다.
확인 4-3. 무리수 전체가 셀 수 없음을 설명하세요.
답. 셀 수 있다고 하면 셀 수 있는 와의 합집합도 셀 수 있어야 하는데 그 합집합이 이고 는 셀 수 없으므로 모순입니다.
문제. 임의의 집합 에 대하여 와 사이에 전단사가 존재하지 않음을 증명하세요. 그리고 이 결과가 무한의 크기에 대해 무엇을 말해 주는지 해석하세요.
생각의 실마리. 유한집합이라면 이므로 자명합니다. 무한집합에서도 성립함을 보여야 하므로 크기 비교를 쓸 수 없고, 전단사가 없음을 직접 증명해야 합니다. 전사인 함수가 아예 없음을 보이면 충분합니다. 문제 4의 대각선 논법을 집합 버전으로 옮겨 봅니다. "번째 자리를 다르게"에 해당하는 것이 무엇이겠습니까.
풀이. 임의의 함수 를 잡고, 이 함수가 전사가 아님을 보입니다. 전사인 함수가 하나도 없으면 전단사도 없습니다.
다음 집합을 만듭니다.
가 의 부분집합이므로 "가 에 속하는가"라는 질문이 뜻을 가집니다. 는 자기 자신이 자기 상에 속하지 않는 원소들을 모은 것입니다. 는 의 부분집합이므로 입니다.
가 의 치역에 없음을 보입니다. 인 가 있다고 가정하고 가 에 속하는지 따집니다.
라면 의 정의에 따라 입니다. 모순입니다.
라면 의 정의에 따라 여야 합니다. 역시 모순입니다.
두 경우 모두 불가능하므로 그런 는 없고, 는 의 치역에 속하지 않습니다. 따라서 는 전사가 아닙니다.
가 임의였으므로 에서 로 가는 전사 함수가 존재하지 않고, 전단사도 존재하지 않습니다.
이 문제에서 배우는 것: 칸토어 정리와 무한의 위계.
방금 증명한 것을 칸토어 정리라고 합니다.
한편 는 에서 로 가는 단사이므로, 는 보다 크다고 말할 수 있습니다. 단사는 있는데 전단사는 없다는 것이 그 뜻입니다.
이 정리의 결론을 해석하면 다음과 같습니다.
첫째, 가장 큰 무한집합은 없습니다. 어떤 무한집합을 가져오든 그 멱집합이 더 크고, 그 멱집합의 멱집합은 또 더 큽니다. 무한의 크기가 끝없이 이어지는 사다리를 이룹니다.
둘째, 26강 심화 6에서 "모든 집합의 집합"을 만들 수 없다고 한 이유가 이것입니다. 그런 집합 가 있다면 인데 가 보다 커야 하므로 모순입니다.
셋째, 증명에 쓴 는 26강 심화 6의 와 같은 모양입니다. 자기 자신을 참조하는 조건으로 모순을 만드는 이 수법은 21강 심화 6의 "이 문장은 거짓입니다"에서 시작해 여기까지 이어집니다. 세 자리에서 같은 논리 구조가 반복해서 나타납니다.
참고로 임이 알려져 있습니다. 의 부분집합을 과 의 무한 수열로 적을 수 있고, 그것이 이진 소수와 대응하기 때문입니다. 그래서 문제 4의 결과는 칸토어 정리를 에 적용한 것과 같은 내용입니다.
바로 확인.
확인 5-1. 이고 , 일 때 를 구하세요.
답. 이므로 입니다. 이므로 입니다. 따라서 이며, 실제로 의 치역 에 들어 있지 않습니다.
확인 5-2. 에서 로 가는 단사를 하나 만드세요.
답. 입니다. 이면 이므로 단사입니다.
확인 5-3. 가장 큰 무한집합이 존재합니까?
답. 존재하지 않습니다. 어떤 집합이든 멱집합이 더 크므로 최대가 있을 수 없습니다.
| 개념 | 정의 |
|---|---|
| 대등 | 전단사 가 존재합니다 |
| 무한집합 | 자기 진부분집합과 대등합니다 |
| 셀 수 있음 | 과 대등하거나 유한합니다 |
| 셀 수 없음 | 무한이지만 과 대등하지 않습니다 |
| 집합 | 크기 |
|---|---|
| , , , \mathbb{N}\times\mathbb | 셀 수 있습니다 |
| , , 무리수 전체, | 셀 수 없습니다 |
| 무엇을 보입니까 | 어떻게 합니까 |
|---|---|
| 셀 수 있음 | 빠짐없이 나열하는 규칙을 제시합니다 |
| 두 방향 격자를 셉니다 | 대각선 나열을 씁니다 |
| 셀 수 없음 | 목록을 가정하고 대각선 논법으로 새 원소를 만듭니다 |
| 멱집합이 더 큼 | 를 만듭니다 |
문제 6. 과 홀수 전체의 집합이 대등함을 보이세요.
답. 이 전단사입니다. 단사는 일차식이라 자명하고, 임의의 홀수 에 대해 가 자연수입니다.
문제 7. 과 이 대등함을 보이세요.
답. 이 전단사입니다. 유한개를 빼도 무한집합의 크기는 변하지 않습니다.
문제 8. 셀 수 있는 두 집합의 합집합이 셀 수 있음을 설명하세요.
답. 두 목록 와 를 번갈아 로 엮으면 하나의 목록이 되고 중복은 지웁니다.
문제 9. 대각선 논법에서 을 로 정하면 어떤 문제가 생깁니까?
답. 이면 이 되어 한 자리 숫자가 아닙니다. 그리고 가 이어지는 표기 문제도 남습니다. 와 만 쓰면 두 문제를 모두 피합니다.
문제 10. 이 셀 수 없음을 설명하세요.
답. 을 포함하고, 셀 수 있는 집합의 부분집합은 셀 수 있으므로 대우에 따라 셀 수 없는 집합을 포함하면 셀 수 없습니다.
문제 11. 대수적 수는 정수 계수 다항식의 근인 실수입니다. 대수적 수 전체가 셀 수 있는 이유를 설명하세요.
답. 정수 계수 다항식은 계수의 유한한 나열이므로 의 유한 곱집합에 대응하고 셀 수 있습니다. 각 다항식은 유한개의 근을 가지므로, 셀 수 있게 많은 유한집합의 합집합이 되어 셀 수 있습니다.
문제 12. 문제 11에서 초월수가 존재함을 결론지으세요.
답. 실수는 셀 수 없는데 대수적 수는 셀 수 있으므로, 대수적이지 않은 실수가 반드시 존재합니다. 그런 수를 초월수라고 하며 와 가 그 예입니다. 구체적인 예를 들지 않고 개수 비교만으로 존재를 얻은 비구성적 증명입니다.
문제 13. 이 셀 수 없음을 칸토어 정리로 설명하세요.
답. 칸토어 정리에 의해 과 이 대등하지 않고, 이 무한이므로 셀 수 없습니다.
문제 14. 유한집합 에서 임을 26강의 결과로 확인하세요.
답. 이고 모든 자연수 에 대해 입니다. 25강 문제 12에서 을 증명했고 더 간단히는 을 귀납법으로 보일 수 있습니다.
문제 15. 과 가 대등함을 보이는 함수를 하나 제시하세요.
답. 이 전단사입니다. 더 간단히는 도 됩니다. 16강에서 본 탄젠트가 에서 전체를 훑기 때문입니다.
문제 16. 두 구간 과 가 대등함을 보이세요.
답. 가 전단사입니다. 길이가 달라도 크기는 같습니다.
문제 17. 셀 수 있는 집합에서 원소 하나를 빼면 크기가 줄어듭니까?
답. 줄어들지 않습니다. 문제 7과 같은 방식으로 번호를 하나씩 당기면 전단사가 만들어집니다.
문제 18. "무리수는 유리수보다 많다"를 정확한 문장으로 바꾸세요.
답. "무리수 전체는 셀 수 없고 유리수 전체는 셀 수 있습니다"입니다. 개수를 뺄셈으로 비교하는 것이 아니라 나열 가능성으로 비교합니다.
심화 1. 대각선 논법이 왜 유리수에는 적용되지 않는지 설명하세요.
답. 만들어진 대각선 수가 유리수라는 보장이 없기 때문입니다.
풀이. 유리수 목록에 대각선 논법을 적용하면 목록에 없는 실수 가 만들어집니다. 그러나 의 소수 전개는 와 이 불규칙하게 섞인 것이므로 순환소수라는 보장이 전혀 없습니다. 유리수는 순환소수여야 하므로 가 유리수 집합에 속한다고 말할 수 없고, 따라서 "목록이 빠짐없다"는 가정에 어긋나지 않습니다. 모순이 나오지 않으므로 증명이 성립하지 않습니다.
남는 것. 대각선 논법의 3단계인 "새 원소가 그 집합에 속한다"가 결정적입니다. 실수에서는 소수 전개가 아무 모양이어도 실수이므로 이 단계가 공짜로 얻어지지만, 유리수에서는 얻어지지 않습니다. 증명이 실패하는 자리를 정확히 짚는 것이 그 증명을 이해했다는 표시입니다.
심화 2. 을 대각선 나열이 아니라 구체적인 식으로 보이세요.
답. 이 전단사입니다.
풀이. 임의의 자연수는 의 거듭제곱과 홀수의 곱으로 유일하게 표현됩니다. 를 로 나눌 수 있는 만큼 나누면 가 되고, 이 분해가 유일합니다. 그러므로 , 을 그 홀수로 잡으면 각 자연수에 정확히 하나의 순서쌍이 대응합니다.
남는 것. 같은 사실을 나열로도 식으로도 보일 수 있습니다. 나열은 방법이 보이면 곧바로 통하고, 식은 몇 번째인지 계산할 수 있다는 장점이 있습니다. 예를 들어 는 번째입니다. 대각선 나열로는 이 번호를 세어야 알 수 있습니다.
심화 3. 셀 수 있게 많은 셀 수 있는 집합의 합집합이 셀 수 있음을 대각선 나열로 보이세요.
답. 각 집합의 목록을 격자의 행으로 놓고 대각선으로 훑습니다.
풀이. 집합들을 라 하고 각 의 원소를 로 나열합니다. 이것을 격자에 놓으면 행 열에 가 있습니다. 문제 3의 대각선 나열로 가 작은 것부터 훑으면 모든 칸에 유한한 번호가 붙고, 중복은 지웁니다.
남는 것. 문제 3에서 유리수를 나열한 것이 이 정리의 특수한 경우입니다. 분모가 인 유리수들의 집합을 로 보면, 각 가 셀 수 있고 그런 집합이 셀 수 있게 많습니다. 개별 증명을 하나의 일반 정리로 묶어 두면 비슷한 상황에서 다시 증명할 필요가 없습니다.
심화 4. 문제 4의 증명에서 만든 를 목록에 추가하면 모순이 해소됩니까?
답. 해소되지 않습니다.
풀이. 를 목록의 맨 앞에 넣어 새 목록을 만들 수 있습니다. 그러나 이 새 목록에 대해 대각선 논법을 다시 적용하면 또 다른 새 실수가 만들어집니다. 이 과정은 끝나지 않습니다.
더 중요한 것은 증명의 구조입니다. 증명은 특정한 목록 하나를 반박한 것이 아니라 임의의 목록에 대해 빠진 원소가 있음을 보였습니다. 목록을 어떻게 고쳐도 그 고친 목록에 같은 논증이 적용됩니다.
남는 것. 24강 문제 3에서 소수 목록에 새 소인수를 추가해도 같은 일이 반복되는 것과 정확히 같습니다. 귀류법에서 반박되는 대상이 "어떤 특정한 것"이 아니라 "임의로 주어진 것"임을 확인하는 습관이 필요합니다. 증명 첫 줄에 "임의의"라고 적혀 있는지 보면 됩니다.
심화 5. 이고 가 셀 수 있으면 도 셀 수 있음을 증명하세요.
답. 부분목록을 만들면 됩니다.
풀이. 의 목록을 라 합니다. 이 목록을 순서대로 훑으면서 에 속하는 것만 남기면 의 원소가 빠짐없이 나열됩니다. 의 임의의 원소는 에도 속하므로 원래 목록 어딘가에 있고, 남긴 목록에도 들어옵니다. 가 유한이면 목록이 유한하고 무한이면 무한합니다.
남는 것. 이 결과의 대우가 실전에서 더 자주 쓰입니다. 셀 수 없는 부분집합을 가지면 그 집합도 셀 수 없습니다. 문제 10에서 이 셀 수 없음을 보인 것이 이 대우의 적용이며, 가 셀 수 없다는 결론도 마찬가지입니다.
심화 6. 과 사이에 다른 크기가 있습니까?
답. 통상적인 집합론의 공리만으로는 참도 거짓도 증명할 수 없습니다.
풀이. 그런 중간 크기가 없다는 주장을 연속체 가설이라고 합니다. 20세기에 밝혀진 바에 따르면 이 가설은 표준 집합론 공리계와 모순되지 않고, 동시에 그 부정도 모순되지 않습니다. 즉 공리를 어느 쪽으로 보태도 일관된 수학이 만들어집니다.
남는 것. 21강 문제 1에서 명제란 참거짓이 정해지는 문장이라고 했습니다. 연속체 가설은 문장 자체로는 명제처럼 보이지만, 주어진 공리계 안에서는 진리값이 정해지지 않습니다. 수학의 명제는 언제나 어떤 공리 위에서 참인지를 묻는 것이며, 공리를 밝히지 않은 참거짓은 뜻이 불완전하다는 사실을 이 예가 보여 줍니다. 22강에서 한정 기호의 범위를 반드시 적으라고 한 것과 같은 성격의 요구입니다.
무한집합의 성질은 코드로 증명할 수 없지만, 나열 규칙이 실제로 빠짐없이 겹침없이 훑는지는 유한한 앞부분에서 확인할 수 있습니다.
import numpy as np
# 문제 2: 정수의 지그재그 나열
n = np.arange(1, 21)
z = np.where(n % 2 == 1, (n - 1) // 2, -(n // 2))
print(z) # [ 0 -1 1 -2 2 -3 3 -4 4 -5 5 -6 6 -7 7 -8 8 -9 9 -10]
print(len(np.unique(z)) == len(z)) # True
print(sorted(z) == list(range(-10, 10))) # True
# 문제 3: 대각선 나열이 격자를 빠짐없이 훑습니다.
pairs = []
for s in range(2, 12): # s = p + q
for p in range(s - 1, 0, -1):
pairs.append((p, s - p))
print(pairs[:6]) # [(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), (1, 3)]
grid = {(p, q) for p in range(1, 6) for q in range(1, 6)}
print(grid.issubset(set(pairs))) # True
# 심화 2: f(m, n) = 2^(m-1) (2n-1) 은 N x N 에서 N 으로 가는 전단사입니다.
m = np.arange(1, 8)[:, None]
k = np.arange(1, 8)[None, :]
vals = (2 ** (m - 1)) * (2 * k - 1)
flat = np.sort(vals.ravel())
print(len(np.unique(flat)) == flat.size) # True
print(sorted(vals[vals <= 12].tolist())) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
# 문제 4: 대각선 논법이 만드는 수는 목록의 어느 행과도 다릅니다.
rng_digits = np.array([[int(d) for d in f"{x:.10f}".split('.')[1]]
for x in [1/3, 1/7, 2/7, 3/7, 1/11, 2/11, 5/13, 1/17, 1/19, 1/23]])
diag = np.diagonal(rng_digits)
y = np.where(diag != 5, 5, 6)
print(diag) # [3 4 5 5 0 8 3 2 8 9]
print(y) # [5 5 6 6 5 5 5 5 5 5]
print(bool(np.all(y != diag))) # True
# 문제 14: n < 2^n 은 모든 자연수에서 성립합니다.
t = np.arange(1, 31)
print(bool(np.all(t < 2.0**t))) # True
출력이 주석과 모두 일치합니다. 마지막에서 두 번째 검산이 대각선 논법의 핵심 단계를 그대로 보여 줍니다. 만들어진 의 각 자리가 대각선 숫자와 하나도 겹치지 않으므로, 는 위 열 개의 수 중 어느 것과도 다릅니다. 목록을 아무리 길게 늘여도 같은 방식으로 새 수가 계속 만들어진다는 것이 심화 4의 내용입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 대등합니다 | 전단사가 존재합니다 | |
| 기수 | 집합의 크기입니다 | |
| 셀 수 있음 | countable | 과 대등하거나 유한합니다 |
| 셀 수 없음 | uncountable | 무한이면서 과 대등하지 않습니다 |
| 대각선 논법 | diagonal argument | 목록의 번째와 번째 자리에서 다른 원소를 만듭니다 |
| 칸토어 정리 | Cantor's theorem | 입니다 |
이 강의로 02단원 집합과 함수가 끝납니다. 26강에서 집합을 세우고, 27강에서 함수를 정의하고, 28강에서 역함수의 존재 조건을 얻고, 29강에서 그 도구로 무한을 재었습니다. 다음 30강부터 시작하는 03단원에서는 수와 식의 구조로 돌아가 복소수를 세우고 합과 곱 기호를 다루며 점화식을 닫힌 형태로 바꿉니다.