2. Các tập được sắp thứ tự tốt
1. Các đoạn của một tập được sắp thứ tự tốt
Một quan hệ được gọi là một quan hệ sắp thứ tự tốt giữa và nếu R là một quan hệ thứ tự giữa và và nếu, với mỗi tập hợp E khác rỗng trên đó cảm sinh một quan hệ thứ tự (nghĩa là sao cho kéo theo ; cf. § 1, no. 1), E, được sắp thứ tự bởi quan hệ này, có một phần tử nhỏ nhất.
¶ Một tập hợp E có thứ tự bởi một phép sắp thứ tự được gọi là được sắp tốt nếu quan hệ là một quan hệ sắp thứ tự tốt giữa và ; khi đó được gọi là một phép sắp thứ tự tốt trên E. Định nghĩa sau tương đương với định nghĩa này:
Định nghĩa 1 03JY
Một tập hợp* E được gọi là được sắp tốt nếu nó có thứ tự và mỗi tập con khác rỗng của E *đều có một phần tử nhỏ nhất.
Một tập hợp được sắp tốt E được sắp thứ tự toàn phần vì mọi tập con của E đều có một phần tử nhỏ nhất. Mọi tập con A của E bị chặn trên trong E đều có một cận trên nhỏ nhất trong E.
Ví dụ
Ví dụ 1 03SX
Cho là một tập hợp có các phần tử phân biệt. Dễ dàng kiểm tra rằng tập con của là đồ thị của một thứ tự tốt trên E.
Ví dụ 2 03SY
Mọi tập con (đặc biệt là tập con rỗng) của một tập được sắp thứ tự tốt đều được sắp tốt theo thứ tự cảm sinh.
Ví dụ 3 03SZ
\* Sự tồn tại của các tập hợp được sắp thứ tự toàn phần nhưng không được sắp thứ tự tốt tương đương với tiên đề vô hạn (§ 4, no. 4, Hệ quả 1 của Mệnh đề 3, và Bài tập 3).
Ví dụ 4 03T0
Nếu là một thứ tự tốt trên E, thì thứ tự đối với là một thứ tự tốt trên E chỉ khi E hữu hạn (§ 4, Bài tập 3). \
Ví dụ 5 03T1
Cho E là một tập được sắp thứ tự tốt. Tập hợp nhận được bằng cách thêm vào E một phần tử lớn nhất (§ 1, no. 7) được sắp tốt, vì nếu H là một tập con khác rỗng bất kỳ của khác với , thì phần tử nhỏ nhất của cũng là phần tử nhỏ nhất của H.
Nhận xét 03JZ
\* Hệ quả của tiên đề vô hạn (§ 6, no. 1) là tồn tại các tập được sắp tốt không có phần tử lớn nhất, chẳng hạn tập hợp các số nguyên tự nhiên. \
Định nghĩa 2 03QN
Trong một tập hợp có thứ tự* E, một tập con của E sao cho các quan hệ , , và suy ra được gọi là một đoạn của E.
Rõ ràng, mọi giao và hợp của các đoạn của E đều là một đoạn của E. Nếu S là một đoạn của E, thì mọi đoạn của S cũng là một đoạn của E. Tập hợp E và tập rỗng đều là các đoạn của E.
Mệnh đề 1 03QO
Trong một tập hợp được sắp tốt* E, mọi đoạn của E khác E chính nó đều là một khoảng , trong đó .
Cho S là một đoạn của E sao cho . Vì không rỗng, nên nó có phần tử nhỏ nhất . Theo Định nghĩa 2, quan hệ suy ra ; nếu không, ta sẽ có , điều này là vô lý. Do đó là khoảng , và S là khoảng .
¶ Với mọi phần tử trong một tập hợp được sắp thứ tự toàn phần E, đoạn được gọi là đoạn có đầu mút x, và được ký hiệu bởi .
Lưu ý rằng nếu E được sắp thứ tự tốt và không rỗng, có một phần tử nhỏ nhất và do đó cũng là khoảng .
Cho E là một tập sắp thứ tự toàn phần. Hợp A của các , khi chạy qua E, là E nếu E không có phần tử lớn nhất; và nếu E có một phần tử lớn nhất , ta có .
Mệnh đề 2 03QP
Tập hợp* E\* các đoạn của một tập hợp được sắp thứ tự tốt E được sắp tốt theo quan hệ bao hàm. Ánh xạ là một đẳng cấu từ tập hợp được sắp thứ tự tốt E lên tập hợp các đoạn của E khác với chính E *.
Hiển nhiên rằng nếu và , quan hệ kéo theo , và kéo theo ; do đó ánh xạ là một đẳng cấu từ E lên tập hợp S(E) các đoạn của E phân biệt với chính E (§ 1, no. 12, Mệnh đề 11), và do đó S(E) được sắp tốt. Hơn nữa, E\* đẳng cấu với tập hợp được sắp thứ tự tốt thu được từ S(E) bằng cách thêm vào một phần tử lớn nhất.
Mệnh đề 3 03QQ
Cho* là một họ các tập hợp được sắp thứ tự tốt sao cho với mỗi cặp chỉ số một trong hai tập hợp , là một đoạn của tập hợp kia. Khi đó tồn tại duy nhất một thứ tự trên tập hợp cảm sinh thứ tự đã cho trên mỗi tập hợp . Được trang bị thứ tự này, E là một tập được sắp thứ tự tốt. Mọi đoạn của là một đoạn của E; với mỗi , đoạn có điểm cuối là trong bằng đoạn có điểm cuối là trong E; và mỗi đoạn của E hoặc là chính E hoặc là một đoạn của một trong các .
Mệnh đề đầu tiên là một hệ quả của bổ đề tổng quát sau:
Bổ đề 1 03QR
Cho* là một họ các tập hợp có thứ tự, có hướng đối với quan hệ (nói cách khác, sao cho với mỗi cặp chỉ số , tồn tại một chỉ số sao cho và ). Giả sử rằng, với mỗi cặp chỉ số sao cho , thứ tự cảm sinh trên bởi thứ tự của trùng với thứ tự đã cho trên . Khi đó tồn tại duy nhất một thứ tự trên tập hợp cảm sinh thứ tự đã cho trên mỗi .
Cho là đồ thị của thứ tự đã cho trên . Nếu G là đồ thị của một thứ tự trên E cảm sinh trên mỗi thứ tự có đồ thị là , thì ta phải có với mỗi ; do đó G chứa . Mặt khác, với mỗi cặp các phần tử của E, theo giả thiết tồn tại một chỉ số sao cho và ; nếu , ta có , do đó . Vậy nếu thứ tự cần tìm trên E tồn tại, đồ thị của nó tất yếu là . Còn phải chứng minh rằng tập hợp này thỏa mãn các điều kiện của bổ đề. Vì nếu , nên ta có với mọi ; mặt khác, từ giả thiết suy ra ba phần tử bất kỳ , , của E thuộc cùng một . Do đó là một quan hệ thứ tự trên E, và bổ đề được chứng minh.
¶ Bây giờ ta xét chứng minh của Mệnh đề 3. Trước hết, hãy chứng minh rằng mỗi là một đoạn của E. Thật vậy, nếu , và , thì tồn tại một chỉ số sao cho và ; theo giả thiết là một đoạn của , nên ta có , điều này chứng minh mệnh đề. Lập luận tương tự chứng minh rằng với mỗi , đoạn có điểm mút trong trùng với khoảng trong E. Tiếp theo, hãy chứng minh rằng E được sắp tốt. Nếu H là một tập con không rỗng của E, thì tồn tại một chỉ số sao cho ; nếu là phần tử nhỏ nhất của trong , thì cũng là phần tử nhỏ nhất của H trong E. Nghĩa là, nếu , thì tồn tại một chỉ số sao cho và ; ta không thể có , vì khoảng được chứa trong , và do đó ta có vì được sắp thứ tự toàn phần.
¶ Cuối cùng, ta phải chứng minh rằng một đoạn của E, khác với chính E, là một đoạn của một trong các ; điều này là một hệ quả ngay lập tức của các lập luận trên, vì một đoạn như vậy có dạng (Mệnh đề 1) và vì thuộc một nào đó.
2. Nguyên lý quy nạp siêu hạn
Bổ đề 2 03K0
Cho là một tập hợp được sắp thứ tự tốt và là một tập hợp các đoạn của có các tính chất sau: (1) hợp của mọi các đoạn thuộc đều thuộc ; (2) nếu , thì . Khi đó mọi đoạn của đều thuộc .
Giả sử rằng có những đoạn của không thuộc , và gọi là đoạn nhỏ nhất trong số đó (no. 1, Mệnh đề 2). Nếu không có phần tử lớn nhất, thì là hợp của các đoạn của phân biệt với chính , và các đoạn này thuộc theo định nghĩa của ; do đó , điều này vô lý. Ngược lại, nếu có phần tử lớn nhất , thì , và vì là một đoạn của phân biệt với , ta có ; nhưng khi đó cũng có , lại là điều vô lý.
¶ Để tiện lợi hơn, ta sẽ đặt mình trong một lý thuyết trong đó là một tập hợp được sắp tốt bởi một quan hệ viết dưới dạng . Khi đó ta có các tiêu chuẩn sau:
C59. (Nguyên lý quy nạp siêu hạn). *Cho là một quan hệ trong ( không phải là một hằng của ) sao cho quan hệ
là một định lý trong . Trong những điều kiện này, quan hệ là một định lý trong .*
Cho là tập hợp các đoạn của sao cho . Rõ ràng là mọi hợp của các đoạn thuộc cũng thuộc . Mặt khác, nếu , theo giả thiết ta có ; do đó theo phương pháp phân chia các trường hợp. Vậy (Bổ đề 2) , điều này chứng minh tiêu chuẩn.
¶ Trong các áp dụng của C59, quan hệ
thường được gọi là “giả thiết quy nạp”.
¶ Trong những điều sau đây, với mọi ánh xạ của một đoạn của vào một tập hợp , và với mỗi , ta sẽ ký hiệu là ánh xạ của đoạn của lên trùng với trên . Với ký hiệu này, ta có
C60. (Định nghĩa một ánh xạ bằng quy nạp siêu hạn.) Cho là một chữ cái, là một số hạng trong lý thuyết . Tồn tại một tập hợp và một ánh xạ của lên sao cho với mọi ta có . Hơn nữa, tập hợp và ánh xạ được xác định duy nhất bởi các điều kiện này.
Trước hết hãy chứng minh tính duy nhất. Giả sử rằng và cũng thỏa mãn các điều kiện của tiêu chuẩn. Gọi là tập hợp các đoạn S của E sao cho và trùng nhau trên S. Hiển nhiên mọi hợp của các đoạn thuộc cũng thuộc . Mặt khác, nếu , thì và trùng nhau trên và do đó ; do đó
điều đó cho thấy rằng . Suy ra (Bổ đề 2), do đó và .
¶ Bây giờ gọi là tập hợp các đoạn S của E sao cho tồn tại một tập và một ánh xạ của S lên sao cho với mọi ta có . Với mỗi , và được xác định duy nhất, theo phần đầu của chứng minh; đặc biệt, nếu và là hai đoạn thuộc sao cho , thì là ánh xạ của lên trùng với trên . Từ nhận xét này suy ra rằng mọi hợp của các đoạn thuộc cũng thuộc (Chương II, § 4, no. 6, Mệnh đề 7). Mặt khác, nếu , ta định nghĩa trên một hàm kéo dài bằng cách đặt
(Chương II, § 4, no. 7, Mệnh đề 8); vì , nên hiển nhiên là . Do đó (Bổ đề 2) , và chứng minh là đầy đủ.
¶ Thông thường tiêu chuẩn này được áp dụng trong những tình huống ở đó tồn tại một tập hợp F sao cho đối với mọi ánh xạ h của một đoạn của E lên một tập con của F ta có . Khi đó tập hợp U thu được bằng cách áp dụng C60 là một tập con của F. Thật vậy, với ký hiệu đã dùng ở trên, gọi là tập con của gồm các đoạn S của E sao cho . Hiển nhiên mọi hợp của các đoạn thuộc cũng đều thuộc ; mặt khác, giả thiết về F suy ra rằng nếu , thì ta có . Mệnh đề bây giờ suy ra từ Bổ đề 2.
3. Định lý zermelo
Bổ đề 3 03K1
Cho* E là một tập hợp, cho là một tập con của , và cho là một ánh xạ của vào E sao cho với mọi . Khi đó tồn tại một tập con M của E và một thứ tự tốt trên M sao cho, nếu ký hiệu quan hệ và ký hiệu đoạn ,
(1) với mọi ta có và ;
(2) .
Cho là tập hợp các tập con G của thỏa mãn các điều kiện sau đây :
(a) G là đồ thị của một thứ tự tốt trên ;
(b) nếu ký hiệu quan hệ trên U, thì với mỗi đoạn sao cho và .
¶ Ta sẽ chứng minh rằng nếu G và G' là hai phần tử của M và nếu U, U' ký hiệu các hình chiếu thứ nhất của chúng, thì một trong hai tập hợp U, U' được chứa trong tập kia và nếu, chẳng hạn, , thì (nói cách khác, quan hệ thứ tự trên U được cảm sinh bởi quan hệ thứ tự trên U') và U là một đoạn của U'.
¶ Xét tập hợp V gồm các phần tử sao cho các đoạn có đầu mút là như nhau trong U và U', và sao cho các thứ tự cảm sinh trên đoạn này bởi các thứ tự trên U và U' là đồng nhất. Rõ ràng V là một đoạn trong cả U lẫn U' và các thứ tự cảm sinh trên V là như nhau; vì vậy mệnh đề của chúng ta sẽ được chứng minh nếu ta chỉ ra rằng hoặc hoặc . Ta sẽ lập luận bằng phản chứng và giả sử rằng và . Gọi là phần tử bé nhất của trong U và gọi là phần tử bé nhất của trong U'; ta có trong U, và trong U'. Nhưng theo giả thiết, và
sao cho . Do đó theo định nghĩa , điều này vô lý.
¶ Vì vậy ta có thể áp dụng Mệnh đề 3 của no. 1 cho tập hợp các hình chiếu thứ nhất (trong đó ) và do đó thu được một tập hợp được sắp thứ tự tốt
Dễ thấy rằng đồ thị của thứ tự trên M thuộc . Nếu ta có , thì, đặt , ta sẽ có . Do đó ta có thể thêm vào M phần tử như phần tử lớn nhất, và tập hợp sẽ được sắp tốt. Vì trong M', nên ta sẽ có và ; do đó đồ thị của thứ tự trên M' sẽ thuộc , điều này vô lý.
Chú ý rằng nếu (và đặc biệt nếu rỗng), thì tập hợp M mà Bổ đề 3 khẳng định sự tồn tại là tập rỗng; điều này suy ra từ điều kiện 1 của Bổ đề 3.
Định lý 1 (Zermelo) 03QS
Mọi tập hợp* E *đều có thể được sắp tốt.
Cho là tập hợp tất cả các tập con của E trừ chính E. Với mỗi , đặt ; vì quan hệ kéo theo , nên ta có (Chương I, § 4, no. 1) và do đó . Vậy ta có thể áp dụng Bổ đề 3, và do đó tồn tại một sắp thứ tự tốt trên một tập con M của E sao cho ; nhưng tập con duy nhất của E không thuộc chính là E, và định lý được chứng minh.
4. Tập hợp quy nạp
Định nghĩa 3 03K2
Một tập hợp có thứ tự* E được gọi là quy nạp nếu mọi tập con được sắp thứ tự toàn phần của E đều có một cận trên trong E.
Ví dụ
Ví dụ 1 03T2
Cho là một tập hợp các tập con của một tập hợp A, được sắp thứ tự bởi quan hệ bao hàm, và sao cho đối với mọi tập con được sắp thứ tự toàn phần của thì hợp của các tập hợp thuộc thuộc về . Khi đó là quy nạp đối với quan hệ vì hợp của các tập hợp thuộc là cận trên bé nhất của trong .
Ví dụ 2 03T3
Một ví dụ quan trọng về một tập hợp các tập con là quy nạp đối với quan hệ là tập hợp các đồ thị của các ánh xạ từ các tập con của một tập hợp A vào một tập hợp B. Thật vậy, là một tập con của , và nói rằng một tập con của được sắp thứ tự toàn phần bởi quan hệ bao hàm có nghĩa là các phần tử của là các đồ thị của những ánh xạ sao cho, với hai ánh xạ bất kỳ trong số đó, một ánh xạ là một mở rộng của ánh xạ kia. Từ đó suy ra ngay lập tức rằng hợp của các tập hợp thuộc là một phần tử của (Chương II, § 4, no. 6, Mệnh đề 7). Do đó tập hợp các ánh xạ từ các tập con của A vào B là quy nạp đối với quan hệ thứ tự " là một mở rộng của " giữa và .
Ví dụ 3 03T4
\* Từ tiên đề vô hạn (§ 6, no. 1) suy ra rằng tập được sắp tốt các số nguyên tự nhiên không là quy nạp đối với quan hệ . \
Định lý 2 ("Bổ đề Zorn") 03QT
— *Mọi tập hợp có thứ tự quy nạp đều có một phần tử cực đại.
Định lý này là một trường hợp riêng của kết quả sau đây:
Mệnh đề 4 03K3
Cho* E là một tập hợp có thứ tự trong đó mọi tập con được sắp tốt đều bị chặn trên; khi đó E *có một phần tử cực đại.
Ta sẽ nói rằng một phần tử là một cận trên ngặt của một tập con X của E nếu là một cận trên của X và . Gọi là tập hợp các tập con của E có một cận trên ngặt trong E, và với mỗi đặt là một cận trên ngặt của S; khi đó là một cận trên ngặt của S. Áp dụng Bổ đề 3 của no. 3 cho và , ta thấy rằng tồn tại một tập con M của E và một thứ tự tốt trên M thỏa mãn các điều kiện của Bổ đề 3; đặc biệt, M không có cận trên ngặt nào trong E. Hơn nữa, thứ tự đồng nhất với thứ tự cảm sinh trên M bởi thứ tự trên E. Thật vậy, trong M quan hệ “ and ” tương đương với ; và vì là một cận trên của (đối với thứ tự trên E), nên điều đó suy ra trong E. Nhưng điều này có nghĩa là đơn ánh từ M vào E là một ánh xạ tăng ngặt (M được trang bị thứ tự ); và vì M được sắp thứ tự toàn phần, nên suy ra rằng các quan hệ và là tương đương trong M (§ 1, no. 12, Mệnh đề 11). Do đó, theo giả thiết, tồn tại một cận trên của M trong E; nhưng vì M không có cận trên ngặt, nên suy ra rằng là một phần tử cực đại của E.
Hệ quả 1 03K4
Cho E là một tập hợp có thứ tự quy nạp và cho a là một phần tử của E. Khi đó tồn tại một phần tử cực đại m của E sao cho .
Thật vậy, theo Định nghĩa 3 thì tập hợp F gồm các phần tử của E là quy nạp, và một phần tử cực đại của F cũng cực đại trong E.
Hệ quả 2 03K5
Cho là một tập hợp các tập con của một tập hợp E sao cho, với mọi tập con của được sắp thứ tự toàn phần bởi quan hệ bao hàm, hợp (resp. giao) của các tập hợp thuộc thuộc về ; khi đó có một phần tử cực đại (resp. cực tiểu).
5. Đẳng cấu của các tập hợp được sắp tốt
Định lý 3 03K6
Cho E và F là hai tập hợp được sắp tốt. Khi đó ít nhất một trong hai mệnh đề sau là đúng :
(1) tồn tại một đẳng cấu duy nhất của E lên một đoạn đầu của F;
(2) tồn tại một đẳng cấu duy nhất của F lên một đoạn đầu của E.
Cho là tập hợp các ánh xạ từ các tập con của E vào F sao cho mỗi ánh xạ được xác định trên một đoạn của E và là một đẳng cấu từ đoạn này lên một đoạn của F. Khi đó tập hợp , được sắp thứ tự bởi quan hệ “ mở rộng ” giữa và , là quy nạp. Thật vậy, nếu là một tập con được sắp thứ tự toàn phần của , thì hợp S của các miền xác định của các ánh xạ là một hợp các đoạn của E và do đó bản thân nó cũng là một đoạn của E. Nếu là cận trên bé nhất của trong (no. 4, Ví dụ 2), thì là hợp các ảnh của các ánh xạ và do đó là một đoạn của F. Cuối cùng, với mỗi cặp phần tử , của S sao cho thì tồn tại mà miền xác định chứa cả và (vì được sắp thứ tự toàn phần); và vì , nên là một đẳng cấu từ S lên , và mệnh đề của chúng ta được chứng minh.
¶ Bây giờ, cho là một phần tử cực đại của (no. 4, Định lý 2) và gọi là đoạn của E là miền xác định của . Nếu ta chỉ ra rằng hoặc hoặc , thì định lý sẽ được chứng minh. Ta lập luận bằng phản chứng và giả sử rằng và . Khi đó sẽ tồn tại một phần tử và một phần tử sao cho và (no. 1, Mệnh đề 1). Mở rộng thành một ánh xạ từ đoạn vào F bằng cách đặt ; vì là một đẳng cấu từ lên đoạn , điều này mâu thuẫn với tính cực đại của trong .
¶ Tính duy nhất được khẳng định trong Định lý 3 là một hệ quả của Bổ đề sau:
Bổ đề 4 03K7
Cho E, F là hai tập hợp được sắp tốt và f, g là hai ánh xạ tăng từ E vào F sao cho là một đoạn của F và g tăng ngặt; khi đó với mọi .
Giả sử ngược lại rằng tập hợp các phần tử sao cho không rỗng; khi đó tập hợp này có một phần tử nhỏ nhất . Nếu , khi đó ta có vì tăng ngặt. Vì là một đoạn của F, tồn tại sao cho ; tăng, do đó kéo theo . Vậy
điều này là vô lý.
Hệ quả 1 03K8
Đẳng cấu duy nhất của một tập hợp được sắp thứ tự tốt E lên một đoạn của E là ánh xạ đồng nhất của E lên chính nó.
Đặt trong Định lý 3.
Hệ quả 2 03K9
Cho E, F là hai tập được sắp thứ tự tốt. Nếu tồn tại một đẳng cấu của E lên một đoạn T của F và một đẳng cấu của F lên một đoạn S của E, thì tất yếu có , , và là nghịch đảo của nhau.
Thật vậy, là một đẳng cấu của E lên đoạn của E; theo Hệ quả 1 ta có , và là ánh xạ đồng nhất của E. Tương tự, là ánh xạ đồng nhất của F, do đó suy ra kết quả.
Hệ quả 3 03KA
Mọi tập con A của một tập hợp được sắp thứ tự tốt E đều đẳng cấu với một đoạn của E.
Do Định lý 3, chỉ cần chứng minh rằng không tồn tại đẳng cấu từ E lên một đoạn của A có dạng . Nếu có một đẳng cấu như vậy, thì khi đó sẽ là một ánh xạ tăng ngặt từ E vào E sao cho , nói cách khác sao cho ; nhưng bất đẳng thức này mâu thuẫn với Bổ đề 4 ( là ánh xạ đồng nhất).
6. Các tích từ điển
Cho là một họ các tập hợp có thứ tự, được đánh chỉ số bởi một tập hợp I được sắp tốt. Xét tập hợp tích , và quan hệ
mà ta sẽ ký hiệu bởi . Hiển nhiên là tương đương với , rằng suy ra và , và rằng suy ra . Cũng dễ kiểm tra rằng suy ra (xét chỉ số nhỏ nhất sao cho ít nhất hai trong ba phần tử , , là khác nhau); do đó là một quan hệ thứ tự trên tập hợp tích E. Quan hệ này và thứ tự mà nó xác định được gọi lần lượt là quan hệ thứ tự từ điển và thứ tự từ điển trên (được cảm sinh bởi các thứ tự đã cho trên và trên các ); tập hợp E được trang bị thứ tự này được gọi là tích từ điển của họ các tập hợp có thứ tự . Nếu mỗi đều được sắp thứ tự toàn phần thì tích từ điển cũng được sắp thứ tự toàn phần.
Bài tập
Xem bài tập cho § 2.