Chứng minh phản chứng

Chứng minh phản chứng là một kĩ thuật chứng minh được ưa chuộng. Muốn chứng minh một mệnh đề đúng, ta lập mệnh đề phủ định của nó, giả sử mệnh đề phủ định đúng, rồi tìm cách đi đến một mâu thuẫn. Mục tiêu là chỉ ra rằng giả thiết ta đã chọn dẫn đến một điều vô lí.

Ví dụ đơn giản

Xét khẳng định “không tồn tại số hữu tỉ dương nhỏ nhất”. Ta chứng minh khẳng định này bằng phản chứng. Trước hết lập mệnh đề phủ định: “tồn tại số hữu tỉ dương nhỏ nhất”, và kí hiệu số này là q. Nếu q là số hữu tỉ dương nhỏ nhất thì ta không thể tìm được số hữu tỉ dương nào nhỏ hơn, vì khi đó q không còn là số nhỏ nhất.

Ta dùng điều này để tìm mâu thuẫn. Nếu với q tuỳ ý ta luôn tìm được một số nhỏ hơn nó thì ta đã đi đến mâu thuẫn và mệnh đề phủ định sai. Chẳng hạn, nếu chọn 0,1 làm số nhỏ nhất, ta thấy 0,01 nhỏ hơn. Rồi 0,001 còn nhỏ hơn nữa, 0,0001 lại nhỏ hơn nữa, và cứ thế. Chỉ cần chia số q cho 10 là được một số nhỏ hơn. Thật ra chỉ cần chia cho bất kì số nào lớn hơn 1, chẳng hạn cho 2: một nửa số q chắc chắn nhỏ hơn q.

Vậy số q/2 chắc chắn nhỏ hơn q và đồng thời là số hữu tỉ dương. Như vậy ta đã đi đến mâu thuẫn với mệnh đề phủ định; do đó mệnh đề phủ định sai, và khẳng định ban đầu đúng.

Những số thú vị

Một chứng minh vui kinh điển minh hoạ nguyên tắc phản chứng là ví dụ sau. Giả sử có những số tự nhiên thú vị theo cách này hay cách khác. Chẳng hạn số 2 thú vị vì 2 · 2 = 2 + 2, một tính chất khá hiếm gặp. Số 42 thú vị vì nó là câu trả lời cho mọi câu hỏi. Và cứ như vậy. Câu hỏi đặt ra: có vô số số thú vị không?

Giả sử điều ngược lại, tức là chỉ có hữu hạn số thú vị và có những số không thú vị. Xếp các số tự nhiên không thú vị này vào tập hợp các số không thú vị. Bây giờ chọn số không thú vị nhỏ nhất. Khoan đã, số không thú vị nhỏ nhất? Nghe khá thú vị đấy chứ? :-)

Như vậy ta đã đi đến mâu thuẫn, vì số không thú vị nhỏ nhất thật ra lại khá thú vị. Do đó không thể tồn tại số không thú vị nhỏ nhất, và vì thế tập hợp các số không thú vị nhất định phải là tập rỗng.

Dĩ nhiên đây là chuyện đùa, vì ta chưa định nghĩa rõ thế nào là số thú vị, nhưng bản thân cách lập luận thì không có gì sai.

Chứng minh có vô số số nguyên tố

Ví dụ này dùng cách làm tương tự phần trước, nhưng lần này đúng về mọi mặt.

Số nguyên tố là số chỉ chia hết cho đúng hai số khác nhau: chính nó và 1. Lưu ý rằng số 1 không thoả mãn định nghĩa, còn số 2 thì thoả mãn.

Phân tích ra thừa số nguyên tố là viết một số tự nhiên lớn hơn 1 thành tích của các số nguyên tố. Đây là một tính chất khá thú vị của số tự nhiên: bất kì số tự nhiên nào lớn hơn 1 cũng phân tích được thành tích của một số số nguyên tố (có thể trùng nhau). Ví dụ:

$\begin{array}{rcl} 8 & = & 2 \cdot 2 \cdot 2 \\ 15 & = & 3 \cdot 5 \\ 26 & = & 2 \cdot 13 \\ 1800 & = & 2^{3} \cdot 3^{2} \cdot 5^{2} \end{array}$

Khẳng định về việc phân tích ra thừa số nguyên tố gọi là định lí cơ bản của số học. Định lí này còn cho biết cách phân tích đó là duy nhất, tức là một số tự nhiên không có hai cách phân tích ra thừa số nguyên tố khác nhau. Ngoài ra, chỉ có số nguyên tố mới có dạng phân tích gồm đúng một thừa số, chính là nó. Chẳng hạn, dạng phân tích ra thừa số nguyên tố của 7 chính là số 7. Ta sẽ dùng các điều này để xây dựng chứng minh cho khẳng định sau.

Bây giờ ta chứng minh khẳng định “có vô số số nguyên tố”. Lại lập mệnh đề phủ định: “chỉ có hữu hạn số nguyên tố”. Giả sử dãy số

$a_{1}, a_{2}, a_{3}, \dots, a_{n}$

gồm tất cả các số nguyên tố. Nếu dãy này chứa mọi số nguyên tố thì chắc chắn ta không thể tìm được số nào vừa là số nguyên tố vừa không thuộc dãy. Mọi số nguyên tố đều nằm trong dãy, ngoài dãy không được có số nguyên tố nào.

Muốn đi đến mâu thuẫn, ta phải tạo ra một số nguyên tố không có trong dãy này. Ta dùng số q. Lập số này bằng cách nhân tất cả các số nguyên tố trong dãy rồi cộng thêm 1:

$q = a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n} + 1$

Bây giờ phải chỉ ra rằng số này hoặc là số nguyên tố, hoặc bằng cách nào đó sinh ra một số nguyên tố mới. Ta biết q là số tự nhiên và mọi số tự nhiên lớn hơn 1 đều viết được thành tích các số nguyên tố. Tuy nhiên, không số nguyên tố a_i nào chia hết số q: phép chia luôn dư 1. Chẳng hạn, nếu thử chia q cho số nguyên tố a₂, ta được:

$\frac{a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n} + 1}{a_{2}} = \frac{a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n}}{a_{2}} + \frac{1}{a_{2}} =$

$= a_{1} \cdot a_{3} \cdot a_{4} \cdot \dots \cdot a_{n} + \frac{1}{a_{2}}$

Trước hết ta tách phân số thành hai. Ở phân số thứ nhất, ta rút gọn a₂ và còn lại một tích các số nguyên tố, tức là một số nguyên nào đó không quan trọng. Ở phân số thứ hai không có gì để rút gọn, phân số này luôn là một số không nguyên (vì mẫu số không thể bằng 1, mà 1 không phải là số nguyên tố). Cộng lại, ta được một số không nguyên, tức là số nguyên tố a₂ không chia hết số q.

Như vậy ta đã chứng minh được rằng không số nguyên tố nào trong dãy a_n chia hết số q. (Chú ý: ta chỉ chứng minh với a₂, nhưng dễ dàng tổng quát hoá bằng cách thay a₂ bằng a_i bất kì.) Nhưng vì mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích các số nguyên tố, nên phải tồn tại những số nguyên tố khác, không thuộc dãy a_n, nhưng có mặt trong dạng phân tích của q. Bản thân số q cũng hoàn toàn có thể là số nguyên tố, khi đó dạng phân tích ra thừa số nguyên tố chỉ gồm chính số q. Tóm tắt lại toàn bộ lập luận một lần nữa:

Mọi số tự nhiên lớn hơn 1 đều viết được thành tích của các số nguyên tố.
Theo giả thiết, dãy a_n chứa tất cả các số nguyên tố.
Từ khẳng định thứ nhất suy ra mọi số tự nhiên lớn hơn 1 đều viết được thành tích của một số số hạng của dãy a_n, vì dãy này chứa mọi số nguyên tố.
Ta đã chứng minh rằng không số nào trong dãy a_n chia hết số q.
Điều này mâu thuẫn với giả thiết → nếu mọi số tự nhiên lớn hơn 1 đều phải phân tích được thành tích các số nguyên tố, mà dãy a_n không chứa số nào chia hết q, thì phải tồn tại những số nguyên tố khác chia hết q và có mặt trong dạng phân tích ra thừa số nguyên tố của q.

Như vậy ta đã đi đến mâu thuẫn. Dạng phân tích ra thừa số nguyên tố của q chứa những số nguyên tố không có trong dãy mà ta đã giả thiết là chứa mọi số nguyên tố. Vậy mệnh đề phủ định sai, khẳng định ban đầu đúng: có vô số số nguyên tố.

Mục lục: Chứng minh toán học, Chứng minh phản chứng, Phương pháp quy nạp toán học

« Bài trước: Chứng minh

Bài tiếp: Phương pháp quy nạp toán học »