Buzz
Các phần tử trong tập luỹ thừa {x, y, z} được sắp thứ tự theo phép bao hàm tập hợp | |
| Loại | Phép toán tập hợp |
|---|---|
| Lĩnh vực | Lý thuyết tập hợp |
| Phát biểu | Tập luỹ thừa là tập chứa tất cả tập con của tập cho trước. |
| Phát biểu tương đương | |
Trong toán học, đặc biệt là trong lý thuyết tập hợp, tập hợp con của một tập hợp A là tập hợp gồm tất cả các tập con của A, bao gồm cả A và tập rỗng. Trong lý thuyết tập hợp cơ bản (như ZFC), sự tồn tại của tập lũy thừa được xem như một tiên đề.
Bất kỳ tập con nào của 𝒫(S) được gọi là họ tập con của S.
Ví dụ minh họa
Nếu S là tập {x, y, z}, thì tất cả các tập con của tập S là
- {} (hay hoặc , và được gọi là tập hợp rỗng hay tập rỗng)
- {x}
- {y}
- {z}
- {x, y}
- {x, z}
- {y, z}
- {x, y, z}
và do đó tập lũy thừa của S là tập {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.
Thuộc tính
Nếu S là tập hữu hạn với số phần tử |S| = n (tức là số phần tử trong S là n), thì số các tập con của S là |𝒫(S)| = 2. Điều này cũng là lý do vì sao tập lũy thừa 𝒫(S) được ký hiệu là 2 và được giải thích như sau.
- Hàm chỉ thị hay hàm đặc trưng của tập con A của tập hợp S cùng với số phần tử |S| = n là hàm tử S đến tập hai phần tử {0, 1}, và được ký hiệu là IA: S → {0, 1}, và nó được sử dụng để xác định xem một phần tử của S có thuộc về A hay không; Nếu x trong S thuộc về A, thì IA(x) = 1, ngược lại thì bằng 0. Mọi tập con A của S được định nghĩa bởi hàm chỉ thị IA, vì {0,1} là tập các hàm từ S đến {0,1} bao gồm tất cả các hàm chỉ thị của tất cả các tập con của S. Nói cách khác, tập {0,1} tương đương với hoặc có thể tương đương với tập lũy thừa 𝒫(S). Vì mỗi phần tử của S tương ứng với 0 hoặc 1 trong bất kỳ hàm nào của {0,1}, số hàm trong {0,1} là 2 và vì vậy số 2 được dùng để định nghĩa {0,1} (xem ví dụ về số nguyên từ X), tập 𝒫(S) được ký hiệu là 2. Tất nhiên, chúng ta có | 2 | = 2. Tổng quát hơn, X là tập các hàm từ Y đến X và |X| = |X|.
Định lí đường chéo Cantor chứng minh rằng tập lũy thừa của một tập cho trước luôn có cardinal lớn hơn tập gốc. Cụ thể, định lí Cantor khẳng định rằng tập lũy thừa của tập đếm được là tập không đếm được. Tập lũy thừa của các số tự nhiên tương ứng một-một với tập số thực (xem mô hình cardinal của dòng).
Tập lũy thừa của tập S, kèm các phép hợp, phép giao và phép bù, là ví dụ mô hình của đại số Boole. Thậm chí, mọi đại số Boole hữu hạn đều tương đương với đại số Boole của tập lũy thừa của một tập hữu hạn. Với đại số Boole vô hạn, điều này không còn đúng, nhưng mọi đại số Boole vô hạn có thể biểu diễn là đại số con của tập lũy thừa của một đại số Boole (xem định lý biểu diễn Stone).
Tập lũy thừa của tập hợp S tạo thành nhóm Abel khi cộng thêm phép đảo đối xứng (với tập rỗng là phần tử đơn vị và mỗi tập hợp là nghịch đảo của chính nó), và là monoid giao hoán khi cộng phép giao. Sử dụng luật phân phối, tập lũy thừa cùng hai phép toán này lập thành vành Boole.
Biểu diễn tập con bằng hàm số
Trong lý thuyết tập hợp, X biểu thị tập hàm số từ Y đến X. Có thể sử dụng '2' để định nghĩa tập {0,1} (xem ví dụ số hạng von Neumann), 2 (tức là {0,1}), là tập hàm số từ S tới {0,1}. Như đã chứng minh trong các tính chất ban đầu, 2 và tập lũy thừa của S, 𝒫(S), được xem là bằng nhau trong lý thuyết tập hợp.
Công thức này có thể áp dụng cho ví dụ ban đầu, trong đó S = {x, y, z}, để đạt được đẳng cấu với biểu diễn nhị phân của các số từ 0 đến 2 − 1, với n là số phần tử của tập hợp S hoặc |S| = n. Đầu tiên, ta định nghĩa tập liệt kê tuần tự { (x, 1), (y, 2), (z, 3) } là tập hợp sao cho mỗi số trong mỗi cặp chỉ định vị trí của phần tử tương ứng trong dãy nhị phân. Ví dụ, cho {x, y} = 011(2); phần tử x của S ở vị trí đầu tiên từ phải qua và phần tử y
Xét tất cả các tập lũy thừa của S, chúng ta có:
| Tập con | Dãy chữ số
nhị phân |
Biểu diễn
nhị phân |
Số thập phân
tương ứng |
|---|---|---|---|
| { } | 0, 0, 0 | 000(2) | 0(10) |
| { x } | 0, 0, 1 | 001(2) | 1(10) |
| { y } | 0, 1, 0 | 010(2) | 2(10) |
| { x, y } | 0, 1, 1 | 011(2) | 3(10) |
| { z } | 1, 0, 0 | 100(2) | 4(10) |
| { x, z } | 1, 0, 1 | 101(2) | 5(10) |
| { y, z } | 1, 1, 0 | 110(2) | 6(10) |
| { x, y, z } | 1, 1, 1 | 111(2) | 7(10) |
Tuy nhiên, vì các ánh xạ từ 𝒫(S) đến các số nguyên có thể lựa chọn tự do, nên biểu diễn này không duy nhất cho tất cả các tập con của S. Ví dụ, thay đổi thứ tự của các cặp trong tập liệt kê không làm thay đổi cardinal của nó (ví dụ, tập liệt kê { (y, 1), (z, 2), (x, 3) } có thể được sử dụng để xây dựng một ánh xạ khác từ 𝒫(S) đến các số nguyên mà không làm thay đổi ánh xạ một-một).
Tuy nhiên, biểu diễn nhị phân như vậy chỉ khả thi khi S có thể liệt kê tuần tự. (Trong ví dụ này, x, y, và z được liệt kê là 1, 2, và 3 tương ứng với vị trí của chúng trong dãy chữ số nhị phân.) Vẫn có thể liệt kê khi S có cardinal vô hạn (nghĩa là có vô hạn phần tử trong S), ví dụ như tập số nguyên hoặc tập số hữu tỉ, nhưng không thể khi S là tập số thực vì không thể liệt kê toàn bộ số vô tỉ.
Liên quan đến định lý nhị thức
Từ tính tương đương này, chúng ta có thể áp dụng cho tập lũy thừa. Tập hợp k phần tử từ một tập hợp khác được gọi là tập con chứa k phần tử, vì vậy số tổ hợp (được ký hiệu là C(n, k), hay còn gọi là hệ số nhị thức) của các tập con có k phần tử trong tập hợp có n phần tử. Theo định lý tập lũy thừa, đây là số tập hợp có k phần tử là thành viên của tập lũy thừa của một tập con có n phần tử.
Ví dụ, trong trường hợp tập hợp có ba phần tử, chúng ta có
- C(3, 0) = 1 tập con có 0 phần tử (tập rỗng),
- C(3, 1) = 3 tập con có 1 phần tử (tập đơn điểm),
- C(3, 2) = 3 tập con có 2 phần tử (bù của các tập đơn điểm),
- C(3, 3) = 1 tập con có 3 phần tử (tập gốc).
Bằng cách sử dụng quan hệ này, chúng ta có thể tính bằng công thức:
Do đó từ định thức sau, giả sử , chúng ta có:
Khái niệm đệ quy
Nếu là tập hữu hạn, thì định nghĩa đệ quy của là như sau:
- Nếu , thì .
- Ngược lại, nếu và ; thì .
Nói một cách đơn giản:
- Tập lũy thừa của tập rỗng là tập đơn điểm, trong đó phần tử duy nhất là tập rỗng.
- Đối với tập hợp khác rỗng , giả sử là một phần tử trong tập hợp và là tập bù tương đối của nó; khi đó tập lũy thừa của bao gồm tất cả các tập lũy thừa của và một phần tử bổ sung phần tử vào mỗi tập lũy thừa.'}
Tập con có lực hạn chế
Tập các tập con của S có số phần tử nhỏ hơn hoặc bằng κ đôi khi được gọi là 𝒫κ(S) hoặc [S], và tập các tập con có số phần tử nhỏ hơn nghiêm ngặt so với κ đôi khi được gọi là 𝒫< κ(S) hoặc [S]. Tương tự, tập các tập con khác rỗng của S đôi khi được gọi là 𝒫≥ 1(S) hay 𝒫(S).
Đại số của các tập con
Một cách tiếp cận khác là coi tập hợp như một đại số không có phép toán vô hướng hoặc định nghĩa phương trình. Theo cách nhìn này, ý tưởng rằng tập luỹ thừa của X là tập các tập con của X có thể được áp dụng cho các đại số con của một cấu trúc đại số hoặc một đại số.
Tập luỹ thừa của một tập hợp, được sắp xếp theo thứ tự bao hàm, luôn là đại số Boole nguyên tử và đầy đủ. Mọi đại số Boole nguyên tử và đầy đủ đều có thể được sinh ra từ các tập con của một số tập đã cho. Điều này áp dụng chung cho bất kỳ đại số nào là tập các đại số con của một đại số đã cho, được sắp xếp theo phép bao hàm, luôn là dàn đại số. Mọi dàn đại số đều có thể được sinh ra từ các đại số con của một số đại số. Do đó, các đại số con có hành vi tương tự như các tập con.
Tuy nhiên, có hai tính chất quan trọng của tập con không còn áp dụng khi áp dụng vào đại số con nói chung. Đầu tiên, mặc dù tập các tập con của một tập hợp có thể lập thành một tập hợp (như một dạng dàn), ngược lại không phải lúc nào cũng có thể sắp xếp các đại số con của một đại số sao cho chúng lập thành đại số, nhưng vẫn có thể sắp xếp thành một dạng dàn. Thứ hai, mặc dù tập các tập con của một tập khác có số phần tử song ánh với tập {0,1} = 2, không có đảm bảo rằng một lớp các đại số sẽ chứa một đại số có thể thay thế cho tập 2 ở đây.
Một số lớp đại số thỏa mãn cả hai tính chất này. Tính chất đầu tiên thường gặp nhiều hơn, và các trường hợp đồng thời có cả hai tính chất là hiếm. Một lớp chứa cả hai là lớp của các đồ thị toàn bộ. Cho đồ thị toàn bộ G và H, một phép đồng cấu h: G → H bao gồm hai hàm, một ánh xạ đỉnh sang đỉnh và một ánh xạ cạnh sang cạnh. Tập H chứa tất cả các đồng cấu từ G đến H có thể được tổ chức lại thành đồ thị trong đó các đỉnh và cạnh là các hàm tương ứng với đỉnh và cạnh trong tập hợp này. Hơn nữa, đồ thị con của đồ thị toàn bộ G có số phần tử song ánh với các đồ thị đồng cấu từ G đến đồ thị toàn bộ Ω được định nghĩa là đồ thị đầy đủ với hai đỉnh (bao gồm cả khuyên trên mỗi đỉnh, và hai cạnh lập thành một chu trình) kết hợp với cạnh thứ năm là cạnh lặp lại trên cùng một cặp đỉnh. Do đó, chúng ta có thể sắp xếp lại G thành đồ thị toàn bộ Ω, gọi là vật luỹ thừa của G.
Hàm chống và đại lượng từ
Trong lý thuyết phạm trù và lý thuyết topoi cơ bản, đại lượng từ trong mọi trường hợp là phép chập của hàm chống giữa các tập luỹ thừa, tức là hàm ngược của hàm số giữa các tập hợp; tương tự, đại lượng tồn tại là phép chập nghịch ngược.
