23강에서 직접증명과 대우증명을 익혔고, 두 방법이 모두 막히면 귀류법을 쓴다고 예고했습니다. 이 강의가 그 세 번째 방법입니다.
귀류법이 필요한 자리는 분명합니다. "이런 것은 존재하지 않습니다"나 "이 수는 유리수가 아닙니다"처럼 없음을 주장하는 명제는 직접 만들어 보일 대상이 없습니다. 이때는 있다고 가정해 놓고 그 가정이 자기모순에 빠지는 것을 보이는 수밖에 없습니다.
강의의 뒷부분은 반대 방향입니다. 명제가 거짓일 때 반례를 찾는 일은 운에 맡기는 것처럼 보이지만 실제로는 뒤져 볼 자리가 정해져 있습니다. 그 자리 목록을 만들고, 반례를 찾은 뒤 명제를 어떻게 고쳐야 하는지까지 다룹니다.
문제. "가장 큰 자연수는 존재하지 않습니다"를 증명하세요.
생각의 실마리. 직접증명을 하려면 무엇에서 출발해야 할지 정할 수 없습니다. "존재하지 않는다"는 결론에는 식으로 옮길 대상이 없기 때문입니다. 그렇다면 반대로 존재한다고 가정해 보고, 그 가정에서 무엇이 따라 나오는지 따라가 봅니다.
풀이. 결론이 거짓이라고 가정합니다. 즉 가장 큰 자연수가 존재한다고 하고 그것을 이라 부릅니다.
이 가장 크다는 것은 모든 자연수 에 대하여 이라는 뜻입니다.
이제 을 봅니다. 이 자연수이므로 도 자연수입니다. 그런데 입니다.
은 자연수이면서 보다 크므로 "모든 자연수는 이하"라는 가정에 어긋납니다. 즉 과 이 동시에 성립해야 하는데 이는 불가능합니다.
모순이 나왔으므로 처음 가정이 틀렸습니다. 따라서 가장 큰 자연수는 존재하지 않습니다.
이 문제에서 배우는 것: 귀류법.
증명하려는 결론을 거짓이라고 가정하고, 그 가정에서 모순을 이끌어 내어 원래 결론이 참임을 보이는 방법을 귀류법이라고 합니다.
귀류법이 정당한 이유는 21강의 진리표로 확인됩니다. 어떤 가정에서 모순이 나왔다는 것은 그 가정이 참일 수 없다는 뜻이고, 가 참일 수 없으면 가 참입니다. 조건문 를 증명할 때는 를 가정해 모순을 얻으면 됩니다. 21강 문제 4에서 였으므로, 이 논리곱이 불가능하다는 것은 곧 가 참이라는 뜻입니다.
귀류법의 뼈대는 세 줄입니다.
3번에서 모순을 정확히 지목하는 것이 중요합니다. "이상해집니다"나 "말이 안 됩니다"로는 증명이 되지 않습니다. 와 가 동시에 성립한다는 것을 보여야 합니다. 위 증명에서는 과 이 그 쌍입니다.
귀류법을 써야 하는 신호는 다음과 같습니다.
| 신호 | 예 |
|---|---|
| 결론이 "존재하지 않습니다"입니다 | 가장 큰 자연수는 없습니다 |
| 결론이 "무한히 많습니다"입니다 | 소수는 무한히 많습니다 |
| 결론이 "~가 아닙니다"입니다 | 는 유리수가 아닙니다 |
| 결론이 유일성입니다 | 해가 오직 하나뿐입니다 |
바로 확인.
확인 1-1. "가장 작은 양의 유리수는 존재하지 않습니다"를 귀류법으로 증명하세요.
답. 가장 작은 양의 유리수 이 존재한다고 가정합니다. 도 양의 유리수이고 이므로 이 가장 작다는 가정에 어긋납니다. 모순이므로 그런 수는 없습니다.
확인 1-2. 귀류법에서 모순을 지목할 때 무엇과 무엇을 나란히 적어야 합니까?
답. 어떤 문장 와 그 부정 를 나란히 적어야 합니다. 둘이 동시에 참일 수 없다는 사실이 모순의 정의입니다.
확인 1-3. 를 귀류법으로 증명할 때 무엇을 가정합니까?
답. 가 참이고 동시에 가 거짓이라고 가정합니다. 가정 는 버리지 않습니다.
문제. 가 유리수가 아님을 증명하세요. 유리수란 로 쓸 수 있는 수이며 는 정수, 는 이 아닌 정수입니다.
생각의 실마리. 결론이 "아닙니다"이므로 귀류법의 신호입니다. 유리수라고 가정하면 를 얻는데, 여기서 분수를 그대로 두면 다루기 어렵습니다. 3강에서 분수를 정리할 때 무엇을 먼저 했는지 떠올립니다. 그리고 23강 문제 3에서 얻은 "이 짝수이면 도 짝수"를 어디에 쓸 수 있을지 봅니다.
풀이. 가 유리수라고 가정합니다. 그러면
인 정수 와 이 아닌 정수 가 존재합니다. 여기서 분수를 기약분수로 줄여 둡니다. 즉 와 의 공약수가 뿐이라고 놓아도 일반성을 잃지 않습니다. 어떤 분수든 공약수로 약분하면 기약분수가 되기 때문입니다.
양변을 제곱하고 정리합니다.
오른쪽이 의 배수이므로 은 짝수입니다. 23강 문제 3에서 증명한 대로 이 짝수이면 도 짝수입니다. 그러므로 인 정수 이 존재합니다.
이것을 대입합니다.
이번에는 이 짝수이므로 같은 정리에 의해 도 짝수입니다.
여기서 모순이 드러납니다. 와 가 모두 짝수이므로 둘의 공약수에 가 있습니다. 그런데 처음에 와 의 공약수가 뿐이라고 놓았습니다. 공약수가 뿐이다와 공약수 를 가진다가 동시에 성립할 수 없으므로 모순입니다.
따라서 가 유리수라는 가정이 틀렸고, 는 유리수가 아닙니다.
이 문제에서 배우는 것: 무리수와 일반성을 잃지 않는 가정.
유리수가 아닌 실수를 무리수라고 합니다. 1강에서 이고 둘이 같지 않다고 말했는데, 그 사실의 증명이 방금 것입니다. 실수 중에 유리수가 아닌 것이 실제로 존재함을 하나로 확인했습니다.
증명에서 결정적이었던 장치가 기약분수로 놓는 것입니다. 이런 가정을 "일반성을 잃지 않고"라고 부릅니다. 모든 유리수는 기약분수로 쓸 수 있으므로 이렇게 놓아도 다루는 범위가 줄지 않고, 대신 "공약수가 뿐"이라는 사실을 모순의 재료로 쓸 수 있게 됩니다.
일반성을 잃지 않는 가정을 쓸 때는 그렇게 놓아도 되는 이유를 반드시 적습니다. 여기서는 "어떤 분수든 약분하면 기약분수가 된다"가 그 이유입니다. 이유 없이 편한 조건을 붙이면 23강 확인 2-2에서 본 잘못이 됩니다.
이 증명은 에만 통하는 것이 아닙니다. 소수 에 대해 가 무리수임을 같은 방식으로 보일 수 있고, 그 일반화는 심화 문제에서 다룹니다.
바로 확인.
확인 2-1. 증명에서 와 가 기약이라는 가정을 빼면 어디가 무너집니까?
답. 마지막 단계가 무너집니다. 와 가 모두 짝수라는 결론은 나오지만, 기약이라는 조건이 없으면 그것이 모순이 되지 않습니다.
확인 2-2. 이 무리수임을 같은 방식으로 증명할 때 "이 의 배수이면 도 의 배수"라는 사실이 필요합니다. 23강 확인 4-3의 결과로 이것을 설명하세요.
답. 확인 4-3에서 이 의 배수가 아니면 을 으로 나눈 나머지가 임을 확인했습니다. 대우를 취하면 이 의 배수이면 도 의 배수입니다.
확인 2-3. 에 대해 같은 증명을 시도하면 어디서 실패합니까?
답. "이 의 배수이면 도 의 배수"가 성립하지 않는 자리에서 실패합니다. 이면 가 의 배수이지만 는 의 배수가 아닙니다. 실제로 는 유리수이므로 증명이 실패하는 것이 맞습니다.
문제. 소수가 무한히 많음을 증명하세요.
생각의 실마리. "무한히 많다"는 결론도 직접 만들어 보일 수 없습니다. 유한하다고 가정하면 소수를 모두 나열할 수 있게 되는데, 그 목록으로 무엇을 만들 수 있을지 생각합니다. 목록에 있는 모든 소수로 나누어 봤을 때 나머지가 어떻게 되는 수를 만들면 좋겠습니까?
풀이. 소수가 유한개라고 가정합니다. 그러면 소수를 모두 적을 수 있고, 그 전부를
라고 놓습니다. 이제 이 모두를 곱하고 을 더한 수를 만듭니다.
은 보다 큰 자연수입니다. 모든 소수의 곱이 이미 이상이기 때문입니다.
을 목록의 어떤 소수 로 나누어 봅니다. 곱 부분 는 로 나누어떨어지므로, 을 로 나누면 나머지가 입니다. 즉 은 목록의 어떤 소수로도 나누어떨어지지 않습니다.
한편 보다 큰 모든 자연수는 소수를 약수로 가집니다. 소수가 아니라면 더 작은 두 수의 곱으로 쪼갤 수 있고, 이 과정을 반복하면 반드시 소수에 도달하기 때문입니다. 따라서 도 어떤 소수 를 약수로 가집니다.
여기서 모순이 드러납니다. 는 소수이므로 목록 안에 있어야 합니다. 그런데 목록의 어떤 소수도 을 나누지 못한다고 방금 확인했습니다. 가 을 나눈다와 는 을 나누지 못한다가 동시에 성립하므로 모순입니다.
따라서 소수가 유한개라는 가정이 틀렸고, 소수는 무한히 많습니다.
이 문제에서 배우는 것: 유한하다는 가정에서 목록 만들기.
"무한히 많다"를 증명하는 표준 방법이 여기 있습니다. 유한하다고 가정해 전부를 목록으로 적고, 그 목록에 없는 새 원소를 만들어 모순을 얻습니다.
이 증명에서 흔히 오해하는 곳이 하나 있습니다. 이 소수라고 주장한 것이 아닙니다. 실제로 로 소수가 아닙니다. 증명이 말하는 것은 의 소인수가 목록 밖에 있다는 것이고, 그것만으로 모순이 나옵니다.
증명 안에서 사실 하나를 썼습니다. "보다 큰 모든 자연수는 소수를 약수로 가진다"입니다. 이것은 25강의 강한 귀납법으로 정식 증명하며, 여기서는 쪼개기가 반드시 끝난다는 관찰로 받아들입니다.
바로 확인.
확인 3-1. 을 계산하고 소수인지 판정하세요.
답. 이며 소수입니다. 다만 소수가 되는 것은 우연이고 증명이 요구하는 바는 아닙니다.
확인 3-2. 의 소인수를 구하고, 그것이 목록 밖에 있음을 확인하세요.
답. 입니다. 와 가 모두 목록 밖의 소수이므로 증명의 논리가 그대로 작동합니다.
확인 3-3. 을 로 잡아도 증명이 되겠습니까?
답. 됩니다. 목록의 어떤 소수로 나누어도 나머지가 이 되어 나누어떨어지지 않으므로 같은 모순이 나옵니다. 다만 일 때 이 되어 소인수가 없으므로 라는 단서를 붙여야 합니다.
문제. 다음 세 명제는 모두 거짓입니다. 각각의 반례를 찾고, 어느 자리를 뒤져서 찾았는지 적으세요.
(가) 모든 실수 에 대하여 입니다.
(나) 모든 실수 에 대하여 이면 입니다.
(다) 모든 실수 에 대하여 입니다.
생각의 실마리. 무작정 숫자를 넣어 보는 대신 순서를 정합니다. 식에 절댓값이나 제곱이 있으면 음수를 먼저 넣고, 분모가 있으면 분모가 이 되는 값을 먼저 넣고, 부등식이면 등호가 걸리는 경계를 먼저 봅니다.
풀이. (가)는 제곱과 근호가 있으므로 음수를 먼저 넣습니다. 이면 인데 이므로 같지 않습니다. 반례입니다. 참인 식은 이며 1강에서 확인한 내용입니다.
(나)도 제곱이 있으므로 음수를 봅니다. , 이면 이지만 이고 이므로 입니다. 반례입니다. , 처럼 인 경계도 반례가 됩니다.
(다)는 분모가 있으므로 분모가 이 되는 값을 넣습니다. 이면 왼쪽은 으로 정의되지 않고 오른쪽은 입니다. 왼쪽이 값을 가지지 않으므로 등식이 성립하지 않습니다. 반례입니다. 4강에서 유리식의 정의역을 먼저 확인하라고 한 이유가 이것입니다.
이 문제에서 배우는 것: 반례를 찾는 순서.
반례 찾기는 운이 아니라 절차입니다. 다음 순서로 뒤집니다.
| 순서 | 뒤질 자리 | 이유 |
|---|---|---|
| 1 | 곱셈과 나눗셈이 무너지는 유일한 수입니다 | |
| 2 | 음수 | 제곱, 절댓값, 근호, 부등식의 곱셈에서 부호가 뒤집힙니다 |
| 3 | 과 | 곱해도 크기가 변하지 않아 대소 논증이 깨집니다 |
| 4 | 분모를 으로 만드는 값 | 식 자체가 정의되지 않습니다 |
| 5 | 등호가 걸리는 경계 | 와 의 차이가 드러납니다 |
| 6 | 과 사이의 수 | 제곱하면 작아지므로 크기 논증이 뒤집힙니다 |
| 7 | 아주 큰 수 | 22강 문제 3처럼 뒤에서 깨지는 식이 있습니다 |
| 8 | 극단적 경우 | 공집합, 원소 하나, 같은 값 두 개 등입니다 |
이 목록의 앞쪽 다섯 개만 넣어 봐도 대부분의 거짓 명제가 무너집니다. 22강 문제 3의 처럼 작은 값이 전부 통과하는 경우는 오히려 드물고, 그때는 심화 3에서 본 대로 식의 구조를 보고 깨질 자리를 예측합니다.
바로 확인.
확인 4-1. "모든 실수 에 대하여 입니다"의 반례를 목록의 몇 번 자리에서 찾을 수 있습니까?
답. 6번입니다. 이면 입니다.
확인 4-2. "모든 실수 에 대하여 이면 입니다"의 반례를 드세요.
답. , 입니다. 이지만 입니다. 목록 2번 음수 자리입니다.
확인 4-3. "모든 실수 에 대하여 이면 입니다"의 반례를 드세요.
답. , 입니다. 목록 2번과 3번이 겹치는 자리입니다.
문제. 문제 4의 세 명제 각각에 대해, 반례가 무엇을 말해 주는지 읽고 명제를 참이 되도록 고치세요. 고치는 방법은 여러 가지일 수 있으니 각각 두 가지씩 제시하세요.
생각의 실마리. 반례가 하나 나왔다고 해서 그 명제가 쓸모없어진 것은 아닙니다. 반례가 어디에 있었는지를 보면 명제의 어느 부분이 과했는지 알 수 있습니다. 범위를 좁히거나 결론을 약하게 하는 두 방향을 각각 시도해 봅니다.
풀이. (가) 의 반례는 음수에 있었습니다. 반례가 음수에만 있다는 것은 양수 쪽에서는 명제가 맞다는 뜻입니다.
(나) 의 반례는 음수가 섞였을 때 나왔습니다. 제곱이 순서를 보존하려면 부호가 갖춰져야 합니다.
(다) 의 반례는 분모가 이 되는 한 점에만 있었습니다. 그 점을 빼면 등식은 정확히 성립합니다.
이 문제에서 배우는 것: 반례가 말해 주는 것.
반례는 명제를 폐기하라는 신호가 아니라 명제가 어디까지 참인지 알려 주는 표시입니다. 반례를 찾으면 다음 세 가지를 읽습니다.
세 방법을 다 써도 살릴 수 없으면 그때 명제를 버립니다. 그러나 대부분의 거짓 명제는 참인 명제에서 조건 하나가 빠진 것이므로, 반례가 그 빠진 조건이 무엇인지 가리킵니다.
이 작업이 중요한 이유가 있습니다. 뒤에서 만날 정리에는 "가 닫힌구간에서 연속이면"처럼 조건이 여러 개 붙습니다. 그 조건들은 장식이 아니라 각각이 어떤 반례를 막기 위해 붙은 것입니다. 36강에서 최대·최소 정리를 배울 때, 열린구간으로 바꾸면 어떤 반례가 살아나는지 보면 조건의 의미가 분명해집니다.
바로 확인.
확인 5-1. "모든 실수 에 대하여 가 정의됩니다"의 반례를 들고 명제를 고치세요.
답. 이 반례입니다. "인 모든 실수에 대하여 정의됩니다"로 고치면 참입니다.
확인 5-2. "모든 실수 에 대하여 입니다"의 반례를 들고 두 가지로 고치세요.
답. 이 반례입니다. 범위를 좁혀 "인 모든 실수에 대하여 "으로 하거나, 결론을 약하게 해 "모든 실수에 대하여 "으로 하면 참입니다.
확인 5-3. "이면 입니다"의 반례를 들고 결론을 고치세요.
답. , 이 반례입니다. 결론을 "이거나 입니다"로 고치면 참입니다.
| 결론의 모양 | 쓸 방법 |
|---|---|
| 존재하지 않습니다 | 귀류법 |
| 무한히 많습니다 | 귀류법으로 유한 목록을 만들고 새 원소를 찾습니다 |
| 무리수입니다 | 귀류법으로 기약분수를 놓고 모순을 얻습니다 |
| 유일합니다 | 두 개를 가정하고 같음을 보입니다 |
| 부정형입니다 | 대우증명 또는 귀류법 |
| 반례 찾기 순서 | 넣어 볼 값 |
|---|---|
| 1 | |
| 2 | 음수 |
| 3 | , |
| 4 | 분모를 으로 만드는 값 |
| 5 | 등호 경계 |
| 6 | 과 사이 |
| 7 | 아주 큰 수 |
| 8 | 공집합 등 극단적 경우 |
| 반례를 찾은 뒤 | 처방 |
|---|---|
| 반례가 한 영역에 몰려 있습니다 | 범위를 좁힙니다 |
| 반례가 부호 때문입니다 | 절댓값을 붙입니다 |
| 반례가 등호 자리입니다 | 부등호에 등호를 더합니다 |
| 반례가 한 점뿐입니다 | 그 점을 정의역에서 뺍니다 |
문제 6. "가장 작은 무리수는 존재하지 않습니다"를 귀류법으로 증명하세요.
답. 가장 작은 무리수 이 있다고 가정합니다. 도 무리수이고 이므로 모순입니다. 이 무리수인 이유는 유리수라면 이 유리수가 되어 가정에 어긋나기 때문입니다.
문제 7. 가 무리수임을 증명하세요.
답. 유리수라 가정해 기약분수 로 놓으면 입니다. 이 의 배수이면 도 의 배수입니다. 을 넣으면 이 되어 도 의 배수이므로 기약에 어긋납니다.
문제 8. "유리수와 무리수의 합은 무리수입니다"를 증명하세요.
답. 이 유리수, 가 무리수인데 가 유리수라고 가정합니다. 그러면 이 유리수 둘의 차이므로 유리수가 되어 가 무리수라는 가정에 어긋납니다.
문제 9. "무리수와 무리수의 합은 항상 무리수입니다"의 반례를 드세요.
답. 와 입니다. 둘 다 무리수이지만 합이 으로 유리수입니다.
문제 10. "모든 자연수 에 대하여 은 소수입니다"의 반례를 찾으세요.
답. 입니다. 이므로 소수가 아닙니다. 22강 심화 3과 같은 구조로 상수항의 배수를 먼저 시도해 찾습니다.
문제 11. "와 가 무리수이면 도 무리수입니다"의 반례를 드세요.
답. 입니다. 둘 다 무리수이지만 로 유리수입니다.
문제 12. 다음 귀류법의 잘못을 지적하세요. "가 유리수라 하자. 그러면 이다. 제곱하면 이다. 그런데 로 소수점이 끝나지 않는다. 모순이다."
답. 마지막 문장이 모순이 아닙니다. 소수점이 끝나지 않는 유리수는 처럼 얼마든지 있습니다. 모순은 와 를 지목해야 하는데 그런 쌍이 없습니다.
문제 13. "모든 실수 에 대하여 입니다"가 참임을 확인하고, 여기에는 반례가 없는 이유를 설명하세요.
답. 이므로 모든 실수에서 성립합니다. 반례는 참인 명제에는 존재하지 않으며, 반례를 찾지 못했다는 것과 반례가 없다는 것은 다른 말이므로 증명이 필요합니다.
문제 14. "두 홀수의 합은 홀수입니다"의 반례를 드세요.
답. 입니다. 두 홀수의 합은 항상 짝수이므로 아무 홀수 쌍이나 반례가 됩니다.
문제 15. "이면 입니다"는 참입니까? 에서는 어떻게 됩니까?
답. 참입니다. 이면 양변에 양수 를 곱해 입니다. 반면 에서는 같은 곱셈이 를 주므로 부등호가 뒤집힙니다. 반례 찾기 목록 6번이 여기서 나왔습니다.
문제 16. "이 소수이면 도 소수입니다"의 반례를 찾으세요.
답. 입니다. 이므로 소수가 아닙니다. 에서는 모두 소수가 나오므로 목록 7번인 큰 수를 뒤져야 찾습니다.
문제 17. "가 무리수이면 는 소수입니다"의 반례를 드세요.
답. 입니다. 은 무리수이지만 은 소수가 아닙니다. 도 반례입니다.
문제 18. "는 유리수입니다"가 거짓임을 귀류법으로 증명하세요.
답. 유리수라 하면 인 양의 정수 가 있습니다. 14강의 정의로 되돌리면 이고 양변을 제곱해 입니다. 왼쪽은 로 나누어떨어지지만 오른쪽은 의 거듭제곱이라 로 나누어떨어지지 않으므로 모순입니다.
심화 1. 귀류법과 대우증명은 어떻게 다릅니까? 문제 2의 증명은 둘 중 어느 쪽입니까?
답. 대우증명은 결론의 부정에서 가정의 부정으로 가고, 귀류법은 결론의 부정에서 아무 모순이나 얻으면 됩니다.
풀이. 대우증명은 도착점이 정해져 있어 목표가 분명한 대신 그 도착점에 닿아야만 성공합니다. 귀류법은 도착점이 정해지지 않아 어떤 모순이든 찾으면 되므로 자유롭지만, 그만큼 어디로 가야 할지 방향이 없습니다. 대우증명은 귀류법의 특수한 경우로 볼 수 있습니다. 와 를 가정해 를 얻으면 와 가 모순이기 때문입니다.
문제 2는 순수한 귀류법입니다. 가정의 부정이 아니라 "기약이면서 기약이 아니다"라는 별도의 모순에 도달했습니다.
남는 것. 방법을 고를 때 대우가 보이면 대우를 먼저 시도합니다. 도착점이 있는 쪽이 헤매지 않기 때문입니다. 대우의 도착점이 보이지 않을 때 귀류법으로 넘어갑니다.
심화 2. 소수 에 대하여 가 무리수임을 증명하세요. 문제 2의 증명에서 무엇을 일반화해야 합니까?
답. "이 의 배수이면 도 의 배수"라는 사실을 일반화해야 합니다.
풀이. 를 기약분수로 놓으면 입니다. 여기서 이 을 나눕니다. 이 소수이므로 를 소인수분해했을 때 이 들어 있어야 하고, 따라서 입니다. 대입하면 에서 이므로 도 의 배수가 되어 기약에 어긋납니다.
남는 것. 증명이 통하는 핵심은 이 소수라는 점입니다. 확인 2-3에서 일 때 실패한 이유가 여기 있습니다. 는 소수가 아니므로 을 나눈다고 해서 를 나누지 않습니다. 정리의 가정이 어디에 쓰이는지를 추적하면 그 가정을 뺄 수 있는지 없는지가 보입니다.
심화 3. 가 무리수임을 기약분수를 쓰지 않고 증명하세요.
답. 무한강하로 증명합니다.
풀이. 인 양의 정수 가 있다고 가정합니다. 기약이라는 조건은 붙이지 않되, 그런 중에서 가장 작은 것을 골라 라고 합니다. 자연수의 부분집합에는 가장 작은 원소가 있으므로 이런 선택이 가능합니다.
에서 가 짝수이므로 이고, 대입하면 입니다. 그러면 이고 입니다. 에서 이기 때문입니다. 이는 가 가장 작다는 선택에 어긋나므로 모순입니다.
남는 것. 23강 심화 2에서 예고한 무한강하가 이것입니다. 어떤 양의 정수 성질이 성립하면 더 작은 양의 정수에서도 성립함을 보이면, 끝없이 작아질 수 없다는 사실에서 모순이 나옵니다. 이 논법은 25강의 수학적 귀납법과 같은 원리의 뒷면이며, "자연수 집합의 공집합이 아닌 부분집합에는 최소원이 있다"는 성질을 공유합니다.
심화 4. "무리수의 무리수 거듭제곱은 무리수입니다"가 거짓임을 보이세요. 구체적인 반례를 제시할 수 없어도 됩니다.
답. 거짓입니다. 가 유리수인지 무리수인지 몰라도 증명됩니다.
풀이. 라고 둡니다. 경우를 나눕니다.
가 유리수라면 와 가 반례입니다. 무리수의 무리수 거듭제곱이 유리수가 되었습니다.
가 무리수라면 를 봅니다. 13강의 지수법칙으로
이므로 무리수 의 무리수 거듭제곱이 유리수 가 됩니다. 와 가 반례입니다.
두 경우 중 하나는 반드시 참이므로 반례가 존재합니다.
남는 것. 반례가 존재한다는 것은 증명했지만 어느 쪽이 반례인지는 모릅니다. 21강 문제 3에서 확인한 대로 가 유리수이거나 무리수이거나 둘 중 하나는 반드시 참이고, 그것만으로 존재가 증명됩니다. 이런 증명을 비구성적 증명이라고 하며, 답을 손에 쥐여 주지 않는 대신 존재는 확실히 보증합니다.
심화 5. 22강 문제 3에서 의 반례가 이었습니다. 반례 찾기 목록의 어느 항목도 을 가리키지 않는데, 이런 경우에는 어떻게 찾아야 합니까?
답. 식의 구조를 보고 깨질 자리를 예측합니다.
풀이. 목록은 값의 성질을 기준으로 만들어져 있어서 "상수항의 배수"처럼 식의 모양에서 나오는 자리는 담지 못합니다. 이럴 때는 식을 보고 결론을 무너뜨릴 방법을 역으로 설계합니다. 이 소수가 아니려면 어떤 수로 나누어떨어져야 하고, 식에 이미 이 있으니 로 나누어떨어지게 만드는 을 찾습니다. 이 의 배수이면 세 항이 모두 의 배수가 되므로 이 즉시 나옵니다. 은 그보다 앞서 우연히 깨지는 자리입니다.
남는 것. 반례 찾기에는 두 단계가 있습니다. 목록을 훑는 기계적 단계와, 식의 구조에서 깨질 조건을 역설계하는 단계입니다. 앞 단계로 안 나오면 뒤 단계로 넘어갑니다. 목록만 믿고 몇 개 넣어 본 뒤 "반례가 없으니 참"이라고 결론짓는 것이 가장 흔한 실수입니다.
심화 6. 다음 주장을 판정하세요. "반례를 개까지 찾지 못했으므로 이 명제는 참입니다."
답. 근거가 되지 않습니다.
풀이. 22강 문제 3에서 개가 통과한 뒤 번째에서 깨졌고, 문제 16에서는 이 통과한 뒤 에서 깨졌습니다. 확인한 개수는 아무리 커도 유한하고, 전칭 명제는 무한한 범위를 주장하므로 유한한 확인은 증명이 될 수 없습니다.
실제로 이 함정에 빠진 유명한 예가 있습니다. 라는 부등식은 까지 확인해도 성립하지만 어떤 지점에서 뒤집힌다는 것이 증명되어 있습니다.
남는 것. 코드 검산의 역할이 여기서 정확해집니다. 반례를 찾는 데는 강력하고, 참을 증명하는 데는 무력합니다. 코드가 반례를 찾지 못했다면 그것은 "명제가 참일 수도 있으니 이제 증명을 시도해 보라"는 신호이지 결론이 아닙니다.
귀류법으로 증명한 사실은 코드로 확인할 수 없습니다. 무한을 다루기 때문입니다. 대신 반례 찾기는 코드가 가장 잘하는 일입니다. 후보를 대량으로 넣어 보고 조건이 깨지는 첫 자리를 찾습니다.
import numpy as np
def is_prime(m):
if m < 2:
return False
d = np.arange(2, int(m**0.5) + 1)
return bool(len(d) == 0 or np.all(m % d != 0))
# 문제 10: n^2 - n + 11 이 소수가 아닌 첫 자연수
n = np.arange(1, 30)
flags = np.array([is_prime(int(v)) for v in n**2 - n + 11])
print(int(n[~flags][0])) # 11
# 문제 16: n 이 소수인데 2^n - 1 이 소수가 아닌 첫 경우
primes = np.array([p for p in range(2, 40) if is_prime(p)])
bad = [int(p) for p in primes if not is_prime(2**int(p) - 1)]
print(bad[0], 2**11 - 1, 23 * 89) # 11 2047 2047
# 문제 3 확인: 목록의 곱에 1을 더한 수가 소수가 아닐 수 있습니다.
N = 2 * 3 * 5 * 7 * 11 * 13 + 1
print(N, is_prime(N), 59 * 509) # 30031 False 30031
# 문제 4: 반례 찾기 목록을 그대로 훑습니다.
xs = np.array([0.0, -3.0, 1.0, -1.0, 0.5, 2.0, 100.0])
print(xs[np.sqrt(xs**2) != xs]) # [-3. -1.]
# 문제 2 확인: 유리수로는 2를 정확히 만들 수 없습니다.
q = np.arange(1, 2001)
p = np.round(np.sqrt(2) * q).astype(np.int64)
print(int(np.min(np.abs(p**2 - 2 * q**2)))) # 1
출력이 주석과 모두 일치합니다. 마지막 검산을 읽는 법이 중요합니다. 이 이 되는 경우가 범위에 하나도 없고 최소 오차가 이었습니다. 이것은 가 무리수라는 증거이지 증명이 아닙니다. 심화 6에서 확인한 대로 유한한 확인은 전칭 명제를 증명하지 못하며, 증명은 문제 2에서 손으로 한 것뿐입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 귀류법 | 모순에 의한 증명 | 결론의 부정에서 모순을 이끌어 냅니다 |
| 모순 | 서로 어긋나는 두 문장이 나왔음을 표시합니다 | |
| 기약분수 | 더 약분되지 않는 분수 | 분자와 분모의 공약수가 뿐입니다 |
| 무리수 | 유리수가 아닌 실수 | , , 등입니다 |
| 반례 | 명제를 깨는 예 | 가정은 만족하고 결론은 만족하지 않는 대상입니다 |
다음 25강에서는 자연수 전체에 대한 명제를 한꺼번에 증명하는 수학적 귀납법을 배웁니다. 심화 3에서 쓴 무한강하가 그 원리의 뒷면이며, 18강에서 관찰로만 넘어갔던 수열의 합 공식들이 그때 정식으로 증명됩니다.