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 A 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 A nhỏ hơn hoặc bằng mọi phần tử khác của A. Về mặt hình thức, \forall A \left[ \left( A \subseteq \mathbb{Z}_{\geq 0} \land A \neq \varnothing \right) \rightarrow \left( \exists m \in A \, \forall a \in A \, (m \leq a) \right) \right]. 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 \mathbb{N} bất kể nó được định nghĩa là \mathbb{Z}_{\geq 0} (số nguyên không âm) hay \mathbb{Z}^+ (số nguyên dương), vì một trong các tiên đề Peano cho \mathbb{N}, *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 \mathbb{Z}^+ \subseteq \mathbb{Z}_{\geq 0} và quan hệ tập hợp con \subseteq bắc cầu, mệnh đề về \mathbb{Z}^+ được suy ra từ mệnh đề về \mathbb{Z}_{\geq 0}.

Thứ tự tiêu chuẩn trên \mathbb{N} đượ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 \mathbb{R} (hoặc trên \mathbb{Z}) 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 \mathbb{R} đượ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 đó \forall n \in \mathbb{Z}_{\geq 0} \left[ \left( P(0) \land \left( \forall k \in \mathbb{Z}_{\geq 1} [ P(k) \rightarrow P(k+1) ] \right) \right] \rightarrow P(n) \right]. 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 đó \left[ \left( P(0) \land \forall k \left( \left( \forall j \, (0 \leq j \leq k) \rightarrow P(j) \right) \rightarrow P(k+1) \right) \right) \right] \rightarrow \forall n \in \mathbb{Z}_{\geq 0}, \, P(n).  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, \mathbb{N} = \{ x \in S \mid 0 \in S \land \forall n \in S,\; n+1 \in S \}, 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 \mathbb{R} có một cận dưới đúng, nghĩa là, vì \mathbb{Z}_{\geq 0} là một tập con bị chặn dưới của \mathbb{R} (và quan hệ tập hợp con \subseteq bắc cầu), nên mọi tập A \subseteq \mathbb{Z}_{\geq 0} có một cận dưới đúng a, dẫn đến tồn tại số nguyên n sao cho a nằm trong nửa khoảng (n-1,n], suy ra rằng a = n và *<math>n \in A</math>*.

## 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ể S, 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 n thỏa mãn 0 . 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à n. Từ 0 , nhân mọi vế của bất đẳng thức với n thu được 0 . Nhưng nếu n là số nguyên, thì n^2 cũng là số nguyên, điều này mâu thuẫn với giả định ban đầu rằng n 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 S tạo thành bởi các số nguyên không âm a_1 > a_2 > a_3 > \cdots; khi đó theo nguyên lý sắp tốt, S có phần tử nhỏ nhất a_k với k nào đó. Nhưng a_k phải là phần tử cuối cùng trong dãy, nếu không a_{k+1} , điều này mâu thuẫn với giả định rằng a_k 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 C 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 C rỗng: giả sử phản chứng, C khác rỗng. Sau đó, theo nguyên lý sắp tốt, có một yếu tố ít nhất n \in C; n 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ố, n có các ước a, b, trong đó a, b là số nguyên lớn hơn một và nhỏ hơn n. Do a, b , chúng không thuộc C vì n là phần tử nhỏ nhất của C. Vì vậy, a, b có thể phân tích thành thừa số nguyên tố, với a = p_1p_2...p_k và b = q_1q_2...q_l, nghĩa là n = p_1p_2...p_k \cdot q_1q_2...q_l, một tích các số nguyên tố. Điều này mâu thuẫn với giả định n \in C, nên giả định C khác rỗng phải sai.

## Ghi chú

## Tham khảo

## 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