존재증명과 반례

프로그램이 잘못 동작하는 입력 하나를 찾으면 "모든 입력에서 바르게 동작한다"는 주장이 틀렸다는 것을 보일 수 있습니다. 하지만 바르게 동작하는 입력 하나를 찾았다고 해서 모든 입력에서 바르게 동작한다고 말할 수는 없습니다. 같은 "예 하나"가 어떤 주장에는 충분하고 어떤 주장에는 턱없이 부족한 것입니다. 이 글에서는 양화사를 바탕으로, 명제의 꼴에 따라 무엇을 보여야 하는지가 어떻게 달라지는지 익힙니다.

존재는 예 하나로 보인다

"제곱이 9인 정수가 존재한다"는 $\exists x\,(x^2=9)$ 꼴의 존재 명제입니다. 이것을 증명하려면 x = 3을 제시하고 $3^2=9$임을 확인하면 됩니다. 이렇게 조건을 만족하는 대상을 실제로 만들어 보이는 증명을 구성적 존재증명(constructive existence proof)이라 하고, 제시한 대상을 그 명제의 증인이라고 부르기도 합니다. -3도 조건을 만족하므로, 존재를 증명했다고 해서 그런 수가 하나뿐이라는 것까지 증명한 것은 아닙니다.

반대로 "임의의 두 짝수 a, b에 대해 a + b도 짝수다"는 짝수 전체에 대해 성립한다고 말하는 전칭 명제입니다. a = 2, b = 4에서 합이 6으로 짝수임을 확인하는 것으로는 부족하고, 직접증명에서 한 것처럼 $a=2r$, $b=2s$로 쓰고 $a+b=2(r+s)$임을 보여 모든 경우를 다루어야 합니다. 존재 명제에는 예 하나가 증명이 되지만, 전칭 명제에는 예를 아무리 많이 들어도 증명이 되지 않습니다.

예를 만들지 않는 존재증명

존재를 보이면서도 그 대상이 무엇인지는 끝내 알려 주지 않는 증명도 있습니다. 이것을 비구성적 존재증명(nonconstructive existence proof)이라고 합니다. 유명한 예로 "a와 b가 모두 무리수이면서 $a^b$이 유리수인 수 a, b가 존재한다"를 보겠습니다.

$\sqrt2^{\sqrt2}$를 생각합니다. 이 수가 유리수라면 $a=b=\sqrt2$로 두면 됩니다. 이 수가 무리수라면 $a=\sqrt2^{\sqrt2}$, $b=\sqrt2$로 둡니다. 그러면 $a^b=(\sqrt2^{\sqrt2})^{\sqrt2}=\sqrt2^{\sqrt2\cdot\sqrt2}=\sqrt2^2=2$로 유리수입니다. $\sqrt2^{\sqrt2}$는 유리수이거나 무리수이므로 어느 경우든 조건을 만족하는 a, b가 존재합니다. 그런데 이 증명만으로는 두 경우 가운데 어느 쪽이 실제로 맞는지 알 수 없습니다. 사실은 $\sqrt2^{\sqrt2}$가 무리수라는 것이 알려져 있지만, 그것을 보이려면 훨씬 어려운 정리가 필요합니다.

비구성적 증명은 대상이 존재한다는 것을 확실히 보여 주지만, 그 대상을 계산하는 방법까지 주지는 않습니다. 프로그램을 만들 때는 대개 대상을 실제로 구해야 하므로, 구성적인 증명이 더 쓸모 있는 경우가 많습니다.

반례는 조건 안에서 찾는다

전칭 명제가 거짓임을 보이는 데는 반례 하나면 충분합니다. 다만 반례는 명제의 조건을 만족하면서 결론을 어기는 대상이어야 합니다. "모든 소수는 홀수다"의 반례는 2입니다. 2는 소수이면서 홀수가 아니기 때문입니다. 4는 홀수가 아니지만 소수라는 조건을 만족하지 않으므로 반례가 아닙니다. "$n\ge2$인 모든 정수 n에 대해 $n^2>n$"을 부정하려면 $n\ge2$를 지키면서 $n^2\le n$인 수를 찾아야 하고, 범위 밖의 n = 0이나 n = 1을 내놓으면 반례가 되지 않습니다.

예를 많이 확인한 것만으로 전칭 명제를 믿으면 안 되는 이유를 보여 주는 유명한 예가 있습니다. Euler가 찾은 식 $n^2+n+41$은 n에 0부터 차례로 넣으면 41, 43, 47, 53, …으로 소수가 계속 나옵니다.

def is_prime(m):
    return m >= 2 and all(m % d for d in range(2, int(m ** 0.5) + 1))


print(all(is_prime(n * n + n + 41) for n in range(40)))
first = next(n for n in range(100) if not is_prime(n * n + n + 41))
print(first, first * first + first + 41, 41 * 41)

True
40 1681 1681

is_prime은 2부터 m의 제곱근까지의 수로 나누어 보아 하나도 나누어떨어지지 않으면 소수로 판정합니다. n = 0부터 39까지 40개가 모두 소수이지만, n = 40에서 처음으로 $40^2+40+41=1681=41^2$이 되어 합성수입니다. 대입해 보면 $40^2+40+41=40\cdot41+41=41\cdot41$이기 때문입니다. 40번 연속으로 맞았는데도 "모든 n에 대해 소수"라는 명제는 거짓이었습니다. 이처럼 실험은 규칙을 발견하는 데 큰 도움이 되지만, 그 규칙이 참이라는 것은 증명으로 보여야 합니다.

유일성은 존재와 함께 해가 하나뿐임을 보여야 한다

"조건을 만족하는 대상이 정확히 하나 있다"는 유일성 명제는 두 가지를 보여야 합니다. 하나는 그런 대상이 존재한다는 것이고, 다른 하나는 그런 대상이 둘 이상 없다는 것입니다. 두 번째는 보통 "조건을 만족하는 대상 y가 있다면 y는 이미 찾은 대상과 같다"를 보이는 방식으로 증명합니다.

"방정식 $2x+3=11$의 실수 해가 유일하다"를 증명해 보겠습니다. 먼저 x = 4를 넣으면 $2\cdot4+3=11$이므로 해가 존재합니다. 다음으로 실수 y가 $2y+3=11$을 만족한다고 하면, 양변에서 3을 빼고 2로 나누어 $y=4$입니다. 조건을 만족하는 모든 해가 4와 같으므로 해는 하나뿐입니다. 해 하나를 대입해 확인한 첫 단계에서 멈추면 존재만 보인 것이라, 유일성은 증명하지 못한 것입니다.

정리

• 존재 명제는 조건을 만족하는 대상 하나를 제시하면 증명되지만, 전칭 명제는 예를 아무리 많이 들어도 증명되지 않고 임의의 대상으로 증명해야 합니다.
• 구성적 존재증명은 대상을 실제로 만들어 보이고, 비구성적 존재증명은 대상이 무엇인지 알려 주지 않은 채 존재만 보입니다.
• 전칭 명제의 반례는 조건을 만족하면서 결론을 어기는 대상이어야 하며, 조건을 만족하지 않는 대상은 반례가 아닙니다.
• $n^2+n+41$처럼 많은 예에서 맞는 규칙도 거짓일 수 있으므로, 실험은 규칙을 찾는 데 쓰고 참인지는 증명으로 판단합니다.
• 유일성은 존재와 함께, 조건을 만족하는 모든 대상이 하나와 같음을 보여야 증명됩니다.

연습 문제

1. 두 유리수의 합

"두 유리수의 합이 무리수가 될 수 있다"가 참인지 판단하고 증명하세요.

2. 서로 다른 두 무리수의 합

"서로 다른 두 무리수의 합은 언제나 무리수다"의 반례를 찾으세요.

3. 존재와 유일성 구분하기

다음 세 명제가 존재, 전체, 유일 가운데 어느 꼴인지 쓰고, 참인지 거짓인지 판단하세요. (가) 제곱이 16인 정수가 있다. (나) 제곱이 16인 정수는 하나뿐이다. (다) 모든 정수의 제곱은 0 이상이다.

명제를 보면 먼저 그것이 존재, 전체, 유일 가운데 어느 꼴인지 표시해 보세요. 끝없이 많은 자연수에 대한 전칭 명제를 체계적으로 증명하는 방법은 다음 글 수학적 귀납법과 불변식에서 다룹니다.