존재증명과 반례

버그가 있는 입력 하나를 찾으면 '모든 입력에서 정상 동작한다'는 주장을 깨뜨릴 수 있습니다. 그러나 정상 입력 하나를 찾았다고 전체 정확성을 보장하지는 못합니다. 양화사를 읽고, 주장 형태에 따라 필요한 증거의 양이 달라지는 이유를 익힙니다.

존재증명은 증인을 만든다

'제곱이 9인 정수가 존재한다'를 증명하려면 x=3을 제시하고 $3^2=9$임을 확인하면 됩니다. -3도 해당하므로 존재증명이 유일성까지 증명하지는 않습니다. 구성적 존재증명은 이런 대상을 실제로 만듭니다. 비구성적 증명은 대상이 없다는 가정의 모순 등으로 존재를 보일 수 있지만 대상 계산법이 자동으로 생기지는 않습니다.

'임의의 두 짝수 a,b에 대해 그 합도 짝수다'는 전체 주장입니다. a=2,b=4를 확인하는 것으로는 부족합니다. a=2r,b=2s로 쓰고 a+b=2(r+s)라 해야 임의의 경우를 다룹니다.

반례는 조건 안에서 찾는다

'모든 소수는 홀수다'의 반례는 2입니다. 2는 소수이면서 홀수가 아닙니다. 4는 홀수가 아니지만 소수라는 전제를 만족하지 않아 반례가 아닙니다. '$n\ge2$인 정수에 대해 $n^2>n$'을 부정하려면 조건 $n\ge2$를 지키면서 결론을 깨야 합니다. n=0을 내놓으면 범위 밖입니다.

'모든 정수 n에 대해 $n^2+n+41$은 소수다'는 작은 n에서 참처럼 보입니다. 그러나 n=41이면 $41^2+41+41=41\cdot43$으로 합성수입니다. 실험은 패턴을 발견하는 데 유용하지만 증명과 역할이 다릅니다.

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

'$2x+3=11$의 실수해가 유일하다'를 증명합니다. 먼저 x=4를 대입해 해가 존재함을 보입니다. 임의의 다른 해 y가 있다면 $2y+3=11$이므로 $2y=8$, y=4입니다. 모든 해가 이미 찾은 해와 같으므로 유일합니다. 해 하나만 대입한 첫 단계로 끝내지 않습니다.

스스로 풀어보기

문제 1. '유리수 두 개의 합이 무리수가 될 수 있다'가 참인지 판단하세요.

힌트: 존재 예를 찾다가 안 나오면 전체적으로 불가능함을 증명합니다.

풀이: 거짓입니다. 유리수 a/b,c/d에서 b,d는 0이 아니고 합은 $(ad+bc)/(bd)$입니다. 분자·분모가 정수이고 분모도 0이 아니므로 합은 유리수입니다. 예를 못 찾았다는 사실 대신 모든 경우를 다루는 계산으로 존재 주장을 부정했습니다.

문제 2. '서로 다른 무리수 두 개의 합은 항상 무리수다'의 반례를 구하세요.

풀이: $\sqrt2$와 $-\sqrt2$는 서로 다른 무리수이며 합은 0입니다. '서로 다름'까지 만족하는지 확인해야 합니다. 같은 수를 두 번 고르는 예는 이 문제의 반례가 아닙니다.

주장이 전체·존재·유일 중 무엇에 해당하는지 먼저 표시하세요. 무한히 많은 자연수를 다루는 체계적 방법은 수학적 귀납법으로 이어집니다.