Phản ví dụ là một trường hợp cụ thể làm một mệnh đề "với mọi" trở thành sai; chỉ cần đúng một trường hợp như vậy, kiểm được bằng tính toán, là mệnh đề bị bác bỏ hoàn toàn. Muốn chứng minh một mệnh đề tổng quát thì phải lập luận cho mọi trường hợp, nhưng muốn bác bỏ nó thì một con số là đủ. Sự bất đối xứng này là lý do phản ví dụ là công cụ rẻ và mạnh nhất trong tay người học toán.
Bài này giải thích vì sao một phản ví dụ đủ sức nặng, cách phủ định mệnh đề có lượng từ để biết mình cần tìm gì, những chỗ phản ví dụ hay ẩn nấp trong số học, giải tích và đại số tuyến tính, vài giả thuyết nổi tiếng trong lịch sử từng bị lật bởi một con số, và cách dùng máy tính hay AI để săn phản ví dụ mà không bị đánh lừa.
Vì sao một phản ví dụ là đủ
Mệnh đề "với mọi x trong tập A, P(x) đúng" là một lời hứa không có ngoại lệ. Phủ định của nó là "tồn tại ít nhất một x trong A mà P(x) sai". Hai câu này luôn trái nhau: đúng một trong hai đúng. Vì vậy, chỉ ra được một x cụ thể làm P sai là chứng minh trọn vẹn rằng mệnh đề ban đầu sai, không cần thêm gì nữa.
Điều kiện duy nhất là phản ví dụ phải thật sự nằm trong tập A và thật sự làm P sai, kiểm được bằng tính toán. Phản ví dụ "gần đúng", hay phản ví dụ nằm ngoài miền mà mệnh đề nói tới, không bác bỏ được gì. Nếu mệnh đề nói về số nguyên dương thì một số âm làm nó sai cũng không tính.
Chiều ngược lại thì không đối xứng. Hàng nghìn ví dụ đúng không chứng minh được mệnh đề "với mọi", vì luôn có thể còn một trường hợp chưa thử. Lịch sử toán học có những mệnh đề đúng với hàng chục, thậm chí hàng tỷ giá trị đầu tiên rồi mới sai ở một giá trị rất lớn. Thói quen tốt là: khi gặp một mệnh đề mới, dành vài phút săn phản ví dụ trước khi đầu tư hàng giờ cố chứng minh nó. Nếu tìm ra, bạn tiết kiệm được thời gian; nếu không tìm ra, những lần thất bại thường cho bạn ý tưởng vì sao mệnh đề đúng.
Phủ định mệnh đề có lượng từ: biết mình cần tìm gì
Trước khi săn phản ví dụ, bạn phải biết chính xác "sai" nghĩa là gì. Quy tắc gốc: phủ định đổi "với mọi" thành "tồn tại", đổi "tồn tại" thành "với mọi", và phủ định phần điều kiện ở trong cùng. Bảng dưới là các dạng hay gặp.
| Mệnh đề | Phủ định | Phản ví dụ cần tìm |
|---|---|---|
| Với mọi x, P(x) | Tồn tại x, không P(x) | Một x làm P sai |
| Tồn tại x, P(x) | Với mọi x, không P(x) | Không có phản ví dụ đơn lẻ, phải chứng minh cho mọi x |
| Với mọi x, nếu P(x) thì Q(x) | Tồn tại x mà P(x) đúng và Q(x) sai | Một x thoả giả thiết nhưng không thoả kết luận |
| Với mọi x, tồn tại y, P(x, y) | Tồn tại x, với mọi y, không P(x, y) | Một x mà không y nào hợp |
| Với mọi ε > 0, tồn tại N, với mọi n > N, điều kiện đúng | Tồn tại ε > 0, với mọi N, tồn tại n > N, điều kiện sai | Một ε cố định mà dãy cứ lại vi phạm mãi |
Dòng thứ ba là dạng hay gặp nhất: một phản ví dụ cho "nếu P thì Q" phải thoả P. Ví dụ, để bác bỏ "nếu a² = b² thì a = b", bạn cần một cặp có a² = b² mà a khác b, như a = 1 và b = −1. Dòng cuối là khung của định nghĩa giới hạn trong giải tích; phủ định nó đúng là kỹ năng nền để chứng minh một dãy không hội tụ.
Phản ví dụ hay ẩn ở đâu
Giá trị biên và giá trị đặc biệt. Số 0, số 1, số âm, hai đối tượng bằng nhau, tập rỗng, ma trận không. Rất nhiều mệnh đề nghe hợp lý gãy ngay ở một trong số này. "Tổng hai số vô tỉ là số vô tỉ" gãy với căn bậc hai của 2 và trừ căn bậc hai của 2, tổng bằng 0.
Những hàm có góc nhọn hoặc bước nhảy. Trong giải tích, hàm giá trị tuyệt đối f(x) = |x| là phản ví dụ cho "hàm liên tục thì khả vi": nó liên tục tại 0 nhưng đạo hàm bên trái bằng −1, bên phải bằng 1, nên không khả vi tại đó. Dãy (−1)ⁿ bác bỏ "dãy bị chặn thì hội tụ".
Phép toán không giao hoán. Quen với số thực, người học hay mặc định AB = BA với ma trận. Lấy A có hàng một là (1, 1), hàng hai là (0, 1), và B có hàng một là (1, 0), hàng hai là (1, 1). Tính ra AB có hàng là (2, 1) và (1, 1), còn BA có hàng là (1, 1) và (1, 2). Hai kết quả khác nhau.
Chỗ đổi thứ tự lượng từ. Câu "với mọi số thực x, tồn tại số thực y lớn hơn x" đúng, vì chọn y = x + 1 là xong. Câu "tồn tại số thực y lớn hơn mọi số thực x" thì sai, vì nếu có y như vậy thì chính y + 1 là một x không nhỏ hơn y. Hai câu chỉ khác thứ tự hai cụm từ, và khi một lập luận lặng lẽ tráo thứ tự đó, phản ví dụ thường nằm ngay ở chỗ tráo.
Những trường hợp nhỏ chưa ai thử. Khi mệnh đề nói về số nguyên, thử lần lượt n = 1 đến 10 trước khi làm gì khác. Phản ví dụ nhỏ hay xuất hiện hơn bạn nghĩ, và việc thử cũng giúp bạn hiểu mệnh đề.
Những giả thuyết từng bị lật bởi một con số
Đa thức n² + n + 41 cho ra số nguyên tố với mọi n từ 0 đến 39, một chuỗi dài đến mức ai thử vài chục giá trị cũng dễ tin là nó luôn ra số nguyên tố. Nhưng với n = 40, giá trị là 1600 + 40 + 41 = 1681 = 41², là hợp số. Với n = 41 thì càng rõ: cả ba số hạng đều chia hết cho 41. Đây là ví dụ được dùng nhiều nhất để dạy rằng một chuỗi dài ví dụ đúng không phải là chứng minh.
Số dạng 2ⁿ − 1 là số nguyên tố thì n phải là số nguyên tố, điều này chứng minh được. Nhưng chiều ngược lại sai: n = 11 là số nguyên tố mà 2¹¹ − 1 = 2047 = 23·89. Tương tự, Fermat từng cho rằng mọi số dạng 2 mũ (2 mũ n) cộng 1 đều là số nguyên tố, vì năm số đầu tiên 3, 5, 17, 257, 65537 đều nguyên tố. Euler chỉ ra số tiếp theo, 4294967297, bằng 641 nhân 6700417.
Một ví dụ nữa cho thấy vai trò của máy tính: Euler đưa ra giả thuyết rằng, với k lớn hơn 2, một lũy thừa bậc k không thể là tổng của ít hơn k lũy thừa bậc k dương. Năm 1966, hai nhà toán học Lander và Parkin dùng máy tính tìm ra 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵, bốn lũy thừa bậc năm có tổng là một lũy thừa bậc năm, và giả thuyết sụp đổ. Bài báo công bố kết quả này nổi tiếng vì cực ngắn: một phản ví dụ thì không cần nhiều lời.
Quy trình săn phản ví dụ cho một mệnh đề mới
Khi gặp một mệnh đề chưa biết đúng hay sai, đi theo các bước sau trước khi bắt tay chứng minh:
- Viết lại mệnh đề cho rõ lượng từ và miền: với mọi gì, trong tập nào, giả thiết nào.
- Viết phủ định của nó theo bảng ở trên, để biết chính xác phản ví dụ phải thoả những gì.
- Thử các giá trị biên: 0, 1, số âm nếu được phép, hai đối tượng bằng nhau, trường hợp suy biến.
- Thử lần lượt các giá trị nhỏ, ghi kết quả thành bảng để thấy quy luật hoặc thấy chỗ gãy.
- Nghĩ tới các ví dụ "kỳ quặc" quen thuộc của chủ đề: hàm giá trị tuyệt đối, dãy đan dấu, ma trận không giao hoán, tập rỗng.
- Nếu cần thử số lớn, dùng bảng tính hoặc một đoạn chương trình ngắn, nhưng nhớ rằng không tìm thấy phản ví dụ không có nghĩa là mệnh đề đúng.
- Khi tìm được ứng viên, tự tính lại bằng tay hoặc bằng hai cách độc lập trước khi tuyên bố.
Nếu sau nhiều lần thử vẫn không tìm ra, hãy hỏi vì sao các lần thử thất bại. Lý do thất bại thường là phần lõi của chứng minh.
Dùng AI và máy tính để săn phản ví dụ mà không bị lừa
Đây là việc AI làm khá hữu ích, với điều kiện bạn tự kiểm kết quả. Câu lệnh mẫu: "Mình nghi mệnh đề sau sai: mọi hàm liên tục trên khoảng mở thì bị chặn. Gợi ý cho mình ba kiểu phản ví dụ có thể, mỗi kiểu một dòng giải thích ý tưởng, chưa cần kiểm chi tiết." Sau đó bạn tự chọn một ứng viên, chẳng hạn hàm 1/x trên khoảng từ 0 đến 1, và tự chứng minh nó thật sự liên tục mà không bị chặn.
Lý do phải tự kiểm: chatbot đôi khi đưa ra phản ví dụ sai ngay ở phép tính, ví dụ khẳng định một số là hợp số rồi phân tích sai thừa số, hoặc đưa ra một hàm không thoả giả thiết của mệnh đề. Mọi phép tính số học trong phản ví dụ nên được nhân lại bằng tay hoặc bằng máy tính bỏ túi. Với phản ví dụ trong giải tích, kiểm từng giả thiết của mệnh đề một: liên tục ở đâu, xác định trên miền nào, có đúng là không bị chặn không.
Máy tính cũng có giới hạn ngược lại. Chạy một chương trình thử tới một triệu mà không thấy phản ví dụ chỉ cho bạn một chút tự tin, không cho bạn chứng minh. Và khi làm việc với số thực, lỗi làm tròn có thể tạo ra phản ví dụ giả. Nếu một phép thử số cho kết quả bất ngờ, hãy kiểm lại bằng số học chính xác trước khi tin.
Câu hỏi thường gặp
Một phản ví dụ có đủ để bác bỏ một định lý không?
Một phản ví dụ hợp lệ đủ để bác bỏ mọi mệnh đề có dạng với mọi. Điều kiện là nó phải thật sự thuộc miền mà mệnh đề nói tới, thoả mọi giả thiết, và làm kết luận sai, kiểm được bằng tính toán.
Có thể dùng phản ví dụ để bác bỏ mệnh đề tồn tại không?
Không trực tiếp. Phủ định của tồn tại x là với mọi x không thoả, nên muốn bác bỏ mệnh đề tồn tại bạn phải chứng minh cho mọi trường hợp, không thể chỉ đưa một ví dụ.
Vì sao đa thức n bình phương cộng n cộng 41 nổi tiếng?
Vì nó cho số nguyên tố với mọi n từ 0 đến 39, một chuỗi dài dễ khiến người ta tin, rồi sai ở n bằng 40 khi giá trị bằng 1681, tức 41 bình phương. Nó minh hoạ rằng nhiều ví dụ đúng không phải chứng minh.
Máy tính thử đến hàng tỷ trường hợp mà không thấy phản ví dụ thì mệnh đề có đúng không?
Chưa chắc. Thử nhiều trường hợp chỉ tăng độ tin, không thay được chứng minh. Lịch sử có những mệnh đề đúng với rất nhiều giá trị đầu tiên rồi mới sai ở một giá trị rất lớn.
Làm sao phủ định đúng một mệnh đề có nhiều lượng từ?
Đi từ trái sang phải, đổi mỗi với mọi thành tồn tại và ngược lại, rồi phủ định điều kiện ở trong cùng. Với mệnh đề dạng nếu P thì Q, phủ định là P đúng và Q sai.
Chatbot đưa ra phản ví dụ thì có tin được không?
Dùng như gợi ý, không dùng như kết luận. Hãy tự kiểm từng giả thiết và tính lại mọi con số bằng tay hoặc máy tính. Chatbot đôi khi phân tích sai thừa số hoặc đưa ví dụ không thoả giả thiết.