Nguyên lý sắp thứ tự tốt

Trong toán học, nguyên lý sắp thứ tự tốt, còn gọi là tính chất sắp thứ tự tốt hay đơn giản là nguyên lý sắp tốt, phát biểu rằng mỗi tập con khác rỗng của tập hợp số nguyên không âm có phần tử nhỏ nhất. Nói cách khác, nếu formula_1 là một tập con khác rỗng của tập số nguyên không âm, thì có một phần tử của formula_1 nhỏ hơn hoặc bằng mọi phần tử khác của formula_1. Về mặt hình thức, formula_4. Hầu hết các nguồn nói rằng đây là một tiên đề hoặc định lý về số tự nhiên, nhưng cụm từ "số tự nhiên" đã được tránh ở trên do tranh cãi về việc bao gồm số không. Phát biểu này đúng cho tập hợp số tự nhiên formula_5 bất kể nó được định nghĩa là formula_6 (số nguyên không âm) hay formula_7 (số nguyên dương), vì một trong các tiên đề Peano cho formula_5, "tiên đề quy nạp" (hoặc "nguyên lý quy nạp toán học"), là tương đương về mặt logic với nguyên lý sắp thứ tự tốt. Do formula_9 và quan hệ tập hợp con formula_10 bắc cầu, mệnh đề về formula_7 được suy ra từ mệnh đề về formula_6.

Thứ tự tiêu chuẩn trên formula_5 được sắp tốt theo nguyên lý sắp thứ tự tốt, vì nó bắt đầu bằng phần tử nhỏ nhất, bất kể là 1 hay 0. Ngược lại, thứ tự tiêu chuẩn trên formula_14 (hoặc trên formula_15) không được sắp tốt theo nguyên lý này, vì không có số âm nhỏ nhất. Theo Deaconu và Pfaff, cụm từ "nguyên lý sắp thứ tự tốt" được một số tác giả (không nêu tên) sử dụng làm tên cho "định lý sắp thứ tự tốt" của Zermelo trong lý thuyết tập hợp, theo đó "mọi" tập hợp đều có thể được sắp tốt. Định lý, không phải là chủ đề của bài viết này, kéo theo rằng "về nguyên tắc, có thứ tự khác nào đó trên formula_14 được sắp tốt, mặc dù dường như không có mô tả cụ thể nào về thứ tự như vậy."
== Tương đương với quy nạp ==
Nguyên lý sắp tốt tương đương về mặt logic với nguyên lý quy nạp toán học, theo đó formula_17. Nói cách khác, nếu ta lấy nguyên lý quy nạp toán học làm tiên đề, ta có thể chứng minh nguyên lý sắp tốt như định lý (như đã thực hiện trong ), và ngược lại, nếu ta lấy nguyên lý sắp tốt làm tiên đề, ta có thể chứng minh nguyên lý quy nạp toán học như định lý (như đã thực hiện trong ). Cách đầu tiên phổ biến hơn theo truyền thống, vì nguyên lý quy nạp toán học là một trong những tiên đề về các số tự nhiên của Peano, một nhà toán học có ảnh hưởng.

Nguyên lý quy nạp toán học và nguyên lý sắp tốt đều tương đương với nguyên lý quy nạp mạnh, theo đó formula_18. Vì vậy, người ta cũng có thể dùng nguyên lý quy nạp mạnh làm tiên đề để chứng minh nguyên lý sắp tốt như định lý (như đã thực hiện trong ), hoặc xem nguyên lý sắp tốt là tiên đề để chứng minh nguyên lý quy nạp mạnh như định lý (như trong ).

Điều này cũng có nghĩa, trong lý thuyết tập hợp tiên đề, định nghĩa tập số tự nhiên là tập quy nạp nhỏ nhất, formula_19, tương đương việc phát biểu nguyên lý sắp tốt đúng với nó.

== Suy ra từ tính đầy đủ của số thực ==
Nếu biết rằng các số thực là đầy đủ, thì người ta có thể sử dụng điều này để chứng minh nguyên lý sắp tốt cho các số nguyên không âm. Điều này là do tính đầy đủ kéo theo mọi tập hợp bị chặn dưới của formula_14 có một cận dưới đúng, nghĩa là, vì formula_6 là một tập con bị chặn dưới của formula_14 (và quan hệ tập hợp con formula_10 bắc cầu), nên mọi tập formula_24 có một cận dưới đúng formula_25, dẫn đến tồn tại số nguyên formula_26 sao cho formula_25 nằm trong nửa khoảng formula_28, suy ra rằng formula_29 và "formula_30".

== Phi đại số ==
Nguyên lý sắp tốt, giống như nguyên lý cận trên đúng đối với số thực, phi đại số, tức là, nó không thể được suy ra từ các tính chất đại số của số nguyên (các tính chất này tạo thành một miền nguyên có thứ tự).

== Ứng dụng ==
Nguyên lý sắp tốt được sử dụng trong chứng minh bằng phản ví dụ cực tiểu, trong đó để chứng minh rằng mọi số tự nhiên đều thuộc về một tập hợp cụ thể formula_31, ta giả định điều ngược lại, từ đó suy ra rằng tập hợp phản ví dụ khác rỗng và do đó (áp dụng nguyên lý sắp giếng) chứa một phản ví dụ nhỏ nhất. Sau đó, ta chỉ ra rằng, với bất kỳ phản ví dụ nào, luôn tồn tại một phản ví dụ nhỏ hơn nữa, dẫn đến mâu thuẫn. Phương thức lập luận này là phản đảo của chứng minh bằng quy nạp mạnh, và về bản chất tương tự như phương pháp lùi vô hạn của Fermat. Sau đây là một vài ví dụ.

=== Ví dụ: không có số nguyên nào giữa 0 và 1 ===
Định lý: "Không có số nguyên nào nằm giữa 0 và 1, do đó 1 là số nguyên dương nhỏ nhất."

"Chứng minh." Giả sử phản chứng, tồn tại một số nguyên formula_26 thỏa mãn formula_33. Theo nguyên lý sắp tốt, tập hợp các số nguyên dương nhỏ hơn 1 có phần tử nhỏ nhất, đặt là formula_26. Từ formula_33, nhân mọi vế của bất đẳng thức với formula_26 thu được formula_37. Nhưng nếu formula_26 là số nguyên, thì formula_39 cũng là số nguyên, điều này mâu thuẫn với giả định ban đầu rằng formula_26 là số nguyên dương nhỏ nhất giữa 0 và 1. Do đó, giả định này là sai, hay không có số nguyên nào giữa 0 và 1.

=== Ví dụ: mọi dãy số nguyên không âm giảm hữu hạn ===
Định lý: "Mọi dãy số nguyên không âm giảm đều hữu hạn."

"Chứng minh." Giả sử tồn tại dãy giảm nghiêm ngặt formula_31 tạo thành bởi các số nguyên không âm formula_42; khi đó theo nguyên lý sắp tốt, formula_31 có phần tử nhỏ nhất formula_44 với formula_45 nào đó. Nhưng formula_44 phải là phần tử cuối cùng trong dãy, nếu không formula_47, điều này mâu thuẫn với giả định rằng formula_44 là phần tử nhỏ nhất.

=== Ví dụ: phân tích thừa số nguyên tố ===
Định lý: "Mọi số nguyên lớn hơn 1 đều là tích của hữu hạn số nguyên tố." Đây là một phần trong định lý cơ bản của Số học.

"Chứng minh". Gọi formula_49 là tập hợp tất cả số nguyên hơn một "không thể" phân tích thành thừa số nguyên tố. Ta chỉ ra formula_49 rỗng: giả sử phản chứng, formula_49 khác rỗng. Sau đó, theo nguyên lý sắp tốt, có một yếu tố ít nhất formula_52; formula_26 không thể là số nguyên tố vì mỗi số nguyên tố được coi là tích các số nguyên tố. Theo định nghĩa của các số không nguyên tố, formula_26 có các ước formula_55, trong đó formula_55 là số nguyên lớn hơn một và nhỏ hơn formula_26. Do formula_58, chúng không thuộc formula_49 vì formula_26 là phần tử nhỏ nhất của formula_49. Vì vậy, formula_55 có thể phân tích thành thừa số nguyên tố, với formula_63 và formula_64, nghĩa là formula_65, một tích các số nguyên tố. Điều này mâu thuẫn với giả định formula_52, nên giả định formula_49 khác rỗng phải sai.

== Liên kết ngoài ==
- Chứng minh sự tương đương giữa nguyên lý sắp thứ tự tốt và nguyên lý quy nạp toán học