PROOF 27
증명하라.
반례 하나면 명제는 무너진다
명제 논리 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
∀x P(x) 는 정의역의 모든 x 에 대하여 P(x) 가 성립함을 뜻한다.
증명.
정의역이 무엇인지 정하지 않으면 이 명제는 뜻을 갖지 않는다.약속
∎
정의 D2
∀x P(x) 의 반례란 ¬P(a) 를 만족하는 정의역의 원소 a 를 뜻한다.
증명.
반례는 하나의 원소이며, 그 하나에서 P 가 성립하지 않는다는 사실이다.약속
∎
정의 D3
1 보다 큰 자연수 가운데 약수가 1 과 자기 자신뿐인 것을 소수라 한다.
증명.
1 도 자기 자신도 아닌 약수가 하나라도 있으면 소수가 아니다.약속
∎
정리 T1
∀x P(x) 가 거짓인 것과 반례가 존재하는 것은 같다.
증명.
(1)반례 a 가 있다고 하자. 즉 ¬P(a) 이다.가정, D2
(2)∃x ¬P(x)(1), A3
(3)¬∀x P(x)(2), A1
(4)거꾸로 ¬∀x P(x) 라 하자.가정
(5)∃x ¬P(x)(4), A1
(6)¬P(a) 인 a 가 존재하며, 그것이 반례다.(5), D2
(7)두 방향이 모두 성립하므로 둘은 같다.(3), (6)
∎
정리 T2
존재명제는 예 하나로 참이 되지만, 전칭명제는 예의 개수로 참이 되지 않는다.
증명.
(1)P(a) 가 성립하면 ∃x P(x) 가 성립한다.A3
(2)그러므로 존재명제는 예 하나로 확정된다.(1)
(3)∀x P(x) 는 정의역의 모든 x 에 대한 주장이다.D1
(4)∀x P(x) 에서는 정의역의 어떤 a 에 대해서도 P(a) 가 따라 나온다.A2
(5)거꾸로 P(a₁), …, P(aₙ) 에서 ∀x P(x) 를 얻으려면 정의역이 그 n 개뿐이어야 한다.(3), (4)
(6)정의역이 무한하면 확인하지 않은 x 가 남는다.(5)
(7)남은 x 가운데 하나가 반례이면 ∀x P(x) 는 거짓이 된다.(6), T1
(8)존재명제는 예 하나로 끝나고, 전칭명제는 예 n 개로 끝나지 않는다.(2), (6), (7)
∎
따름정리 C
P(n) 을 「n² + n + 41 은 소수이다」라 하고 정의역을 0 이상의 정수라 하면, ∀n P(n) 은 거짓이다.
증명.
(1)n = 0, 1, …, 39 에 대하여 n² + n + 41 은 모두 소수다.N, D3
(2)n = 40 에 대하여 40² + 40 + 41 = 1681N
(3)1681 = 41 × 41 이므로 41 은 1 도 1681 도 아닌 약수다.(2), N
(4)그러므로 P(40) 은 거짓이다.(3), D3
(5)n = 40 은 ∀n P(n) 의 반례다.(4), D2
(6)그러므로 ∀n P(n) 은 거짓이다.(5), T1
(7)(1)의 마흔 개의 예는 (6)을 막지 못한다.(1), (6), T2
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
반례가 명제를 무너뜨린다는 것은 사실이 아니라 규칙이다. 제거하면 어느 줄이 근거를 잃는지 확인하라.