Tập lũy thừa

Tập luỹ thừa

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	$x\in P(S)\iff x\subseteq S$

Trong toán học, đặc biệt là trong lý thuyết tập hợp, tập hợp lũy thừa (hay còn gọi là tập lũy thừa, tập hợp các bộ phận, tập các bộ phận, tập hợp các tập con, tập các tập con) của một tập hợp A là tập hợp chứa tất cả các tập con của A, bao gồm cả A và tập hợp rỗng. Trong lý thuyết tiên đề tập hợp (ví dụ như trong khuôn khổ của ZFC), sự tồn tại của tập luỹ thừa của bất kỳ tập hợp được đặt thành định đề theo tiên đề tập luỹ thừa. Tập luỹ thừa của S thường được ký hiệu là ${\mathcal {P}}$(S), 𝒫(S), P(S), $\mathbb {P} (S)$, $\wp (X)$, hoặc 2^S. Ký hiệu 2^S nghĩa là tập các hàm từ S đến tập chỉ chứa hai phần tử (ví dụ như tập {0, 1}), ký hiệu này cũng được dùng là bởi vì tập luỹ thừa của S có thể đồng nhất với, tương đương với, hay có song ánh với tập các hàm từ S đến tập hai phần tử cho trước.

Bất kỳ tập con của 𝒫(S) được gọi là họ tập hợp trên S.

Ví dụ

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 $\varnothing$ hoặc $\emptyset$, 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 luỹ thừa của S là tập {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.

Tính chất

Nếu S là tập hữu hạn với số lực lượng |S| = n (tức là số các phần tử trong S bằng với n), thì số các tập hợp con của S sẽ là |𝒫(S)| = 2ⁿ. Nội dung này cũng chính là lý do vì sao có ký hiệu 2^S cho tập luỹ thừa 𝒫(S) 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 lực lượng |S| = n là hàm tử S đến tập hai phần tử {0, 1}, và được ký hiệu là I_A: S → {0, 1}, và nó được dùng để chỉ ra rằng liệu 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ì I_A(x) = 1, còn nếu ngược lại thì bằng 0. Mọi tập con A của S xác định được hay tương đương với hàm chỉ thị I_A, vì {0,1}^S là tập các hàm từ S đến {0,1} chứa 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}^S tương đương với hay có song ánh với tập luỹ thừa 𝒫(S). Bởi mỗi phần tử thuộc S tương ứng với 0 hoặc 1 trong bất kỳ hàm thuộc {0,1}^S, số các hàm trong {0,1}^S là 2ⁿ và bởi vì số 2 được dùng để định nghĩa {0,1} (xem ví dụ số thứ tự von Neumann), nên tập 𝒫(S) cũng được ký hiệu là 2^S. Dĩ nhiên ta có | 2^S | = 2^| S |. Tổng quát hơn, X^Y là tập các hàm từ Y đến X và |X^Y| = |X|^|Y|.

Lập luận đường chéo của Cantor chứng minh rằng tập luỹ thừa của một tập cho trước (vô hạn hay không) thì luôn có số lực lượng lớn hơn tập cho trước đó (hay nói trực quan, tập luỹ thừa luôn lớn hơn tập gốc). Cụ thể hơn, định lý Cantor phát biểu rằng tập luỹ thừa của tập vô hạn đếm được là tập vô hạn không đếm được. Tập luỹ thừa của các số tự nhiên có tương ứng một-một với tập các số thực (xem Lực lượng của continuum).

Tập lũy thừa của tập S, cùng với phép hợp, phép giao và phép bù, có thể được xem là mô hình ví dụ của đại số Boole. Thậm chí, ta có thể chứng minh rằng bất kỳ đại số Boole hữu hạn đều đẳng cấu với đại số Boole của tập luỹ thừa của một tập hữu hạn. Đối với đại số Boole vô hạn thì nó không còn đúng nữa nhưng mọi đại số Boole vô hạn có thể biểu diễn là đại số con của tập luỹ thừa của đại số Boole (xem định lý biểu diễn Stone).

Tập luỹ thừa của tập hợp S lập thành nhóm abel khi xét thêm phép hiệu đối xứng (trong đó 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 xét phép giao. Từ đây có thể chứng minh sử dụng luật phân phối rằng tập luỹ thừa khi đi cùng hai phép toán này sẽ lập thành vành Boole.

Biểu diễn các tập con bằng hàm số

Trong lý thuyết tập hợp, X^Y ký hiệu cho tập các hàm số từ Y đến X. Có thể dùng "2" để định nghĩa tập {0,1} (xem ví dụ số thứ tự von Neumann), 2^S (tức {0,1}^S), là tập các hàm số từ S tới {0,1}. Như đã chứng minh ban đầu trong các tính chất, 2^S và tập luỹ thừa của S, 𝒫(S), được coi là bằng nhau theo lý thuyết tập hợp.

Tính tương đương này có thể áp dụng cho ví dụ ban đầu, trong đó S = {x, y, z}, để lấy ra đẳng cấu với biểu diễn nhị phân của các số từ 0 đến 2ⁿ − 1, trong đó n là số các phần tử trong tập hợp S hay |S| = n. Đầu tiên, định nghĩa tập liệt kê tuần tự { (x, 1), (y, 2), (z, 3) } là tập hợp sao cho phần số trong mỗi cặp được sắp được dùng để chỉ vị trí của phần tử đó trong dãy các chữ số nhị phân. Ví dụ, xét {x, y} = 011₍₂₎; phần tử x của S nằm ở vị trí đầu tiên từ bên phải còn phần tử y nằm ở vị trí hai từ bên phải. Ngược lại, số 1 trong dãy và vị trí của nó tương ứng một cặp trong tập liệt kê tuần tự của S, tức là số 1 chỉ hiện khi có phần tử tương ứng với vị trí trong cặp trong tập con đang xét của S, và 0 khi ngược lại

Xét toàn bộ tập luỹ thừa của S, 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)

Song, vì các đơn ánh từ 𝒫(S) đến các số nguyên có thể lấy tuỳ ý, nên biểu diễn này cho tất cả tập con của S không phải biểu diễn duy nhất. Chẳng hạn, đổi thứ tự trong các cặp trong tập liệt kê sẽ không làm thay đổi lực lượng của nó (ví dụ, tập liệt kê { (y, 1), (z, 2), (x, 3) } có thể dùng để xây đơn ánh khác từ 𝒫(S) đến các số nguyên mà không làm thay đổi số tương ứng một-một.)

Tuy nhiên, dạng 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 liệt kê bằng 1, 2, và 3 tương ứng với vị trí của nó trong dãy chữ số nhị phân.) Vẫn có thể liệt kê khi S có lực lượng vô hạn (tức có vô hạn số phần tử thuộc S), chẳng hạn như tập số nguyên, hay tập số hữu tỉ, nhưng sẽ không khả thi nếu S là tập số thực vì ta không có cách nào để có thể liệt kê toàn bộ số vô tỉ.

Quan hệ với định lý nhị thức

Định lý nhị thức có quan hệ rất gần gũi với tập luỹ thừa. Tổ hợp k phần tử từ một tập khác là tên gọi khác cho tập con chứa k phần tử, và do vậy số tổ hợp (được ký hiệu bằng C(n, k), hay còn gọi là hệ số nhị thức) số các tập con có k phần tử trong tập hợp có n phần tử. Nói theo tập luỹ thừa, nó là số tập hợp có k phần tử và là phần tử của tập luỹ thừa của tập con có n phần tử.

Ví dụ chẳng hạn, trong tập hữu hạn có ba phần tử, 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ử (và chính là tập gốc).

Sử dụng quan hệ này, ta có thể tính ${\textstyle \left|2^{S}\right|}$ bằng công thức: $$\left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}$$

Do đó ta có thể suy ra định thức sau, coi ${\textstyle |S|=n}$, ta có: $$\left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}$$

Định nghĩa đệ quy

Nếu $S$ là tập hữu hạn, thì ta có định nghĩa đệ quy của $P(S)$ như sau:

• Nếu $S=\{\}$, thì $P(S)=\{\,\{\}\,\}$.
• Mặt khác, nếu $e\in S$ và $T=S\setminus \{e\}$; thì $P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}$.

Nói bằng từ:

• Tập luỹ thừa của tập rỗng là tập đơn điểm trong đó phần tử duy nhất trong tập là tập rỗng.
• Đối với tập khác rỗng $S$, gọi $e$ là phần tử bất kỳ trong tập hợp và $T$ là phần bù tương đối của nó; khi đó tập luỹ thừa của $S$ là hợp của tập luỹ thừa của $T$ và một tập luỹ thừa khác của $T$ trong đó mỗi phần tử được gán thêm phần tử $e$.

Tập con bị giới hạn lực lượng

Tập các tập con của S có lực lượng nhỏ hơn hoặc bằng κ đôi khi được kỳ hiệu là 𝒫_κ(S) hoặc [S]^κ, và tập các tập con có lực lượng nhỏ hơn nghiêm ngặt với κ đôi khi được ký hiệu 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 ký hiệu bởi 𝒫_{≥ 1}(S) hay 𝒫⁺(S).

Vật luỹ thừa

Một tập khác có thể coi là một đại số không có phép toán không tầm thường hay định nghĩa phương trình. Từ góc nhìn này, theo lẽ tự nhiên, ý tưởng rằng tập luỹ thừa của X là tập các tập con của X sẽ tổng quát cho đại số con của một cấu trúc đại số hay của một đại số.

Tập luỹ thừa của một tập hợp khi được sắp thứ tự theo phép bao hàm luôn là đại số Boole nguyên tử và đầy đủ, và mọi đại số Boole nguyên tử và đầy đủ đều nảy sinh từ dàn các tập con của một số tập cho trước. Dạng tổng quát cho bất kỳ đại số là tập các đại số con của một đại số cho trước, vẫn sắp theo phép bao hàm, luôn là dàn đại số, và mọi dàn đại số đều nảy sinh từ dàn các đại số con của một số đại số. Do vậy, các đại số con có hành vi tương tự với 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 đúng khi mang sang đại số con nói chung. Đầu tiên, mặc dù các tập con của tập hợp lập thành một tập hợp (tương tự như dàn), nhưng ngược lại, có một số trường hợp không thể sắp xếp các đại số con của một đại số sao cho tập các đại số con lập thành đại số, song nó vẫn có thể xếp thành dàn. Thứ hai, mặc dù tập các tập con của một tập khác có song ánh với tập {0,1} = 2, không có đảm bảo sao cho một lớp các đại số sẽ chứa một đại số có thể đóng vai trò của tập 2 ở đây.

Một số lớp đại số thoả mãn cả hai tính chất này. Tính chất đầu tiên được gặp nhiều hơn, và trường hợp sở hữu cả hai khá là hiếm. Một lớp chứa được cả hai là lớp của các đa đồ thị. Cho đa đồ thị G và H, phép đồng cấu h: G → H chứa hai hàm, một hàm ánh xạ đỉnh sang đỉnh và cái còn lại ánh xạ cạnh sang cạnh. Tập H^G chứa các đồng cấu từ G đến H có thể tổ chức lại thành đồ thị trong đó đỉnh và cạnh là các hàm đỉnh và cạnh tương ứng xuất hiện trong tập hợp đó. Hơn nữa, đồ thị con của đa đồ thị G có song ánh với đồng cấu đồ thị từ G đến đa đồ thị Ω được định nghĩa là đồ thị có hướng đầy đủ trên hai đỉnh (có bốn cạnh ban đầu, bao gồm khuyên trên mỗi đỉnh, và hai cạnh lập thành một chu trình) đi cùng với cạnh thứ năm là cạnh vòng lại trên mộ trong hai đỉnh. Do đó ta có thể tổ chức G thành đa đồ thị Ω^G, được gọi là vật luỹ thừa của G.

Hàm tử và lượng từ

Trong lý thuyết phạm trù và lý thuyết của các topoi sơ cấp, lượng từ với mọi có thể hiểu là liên hợp phải của hàm tử giữa các tập luỹ thừa, tức là hàm tử nghịch ảnh của hàm số giữa các tập hợp; tương tự như vậy, lượng từ tồn tại là liên hợp trái.

Xem thêm

• Định lý Cantor
• Họ tập hợp
• Trường các tập hợp
• Tổ hợp

Thư mục

• Devlin, Keith J. (1979). Fundamentals of contemporary set theory. Universitext. Springer-Verlag. ISBN 0-387-90441-7. Zbl 0407.04003.
• Halmos, Paul R. (1960). Naive set theory. The University Series in Undergraduate Mathematics. van Nostrand Company. Zbl 0087.04403.
• Puntambekar, A. A. (2007). Theory Of Automata And Formal Languages. Technical Publications. ISBN 978-81-8431-193-8.

Liên kết ngoài

• Power set tại trang PlanetMath.org.
• Power set tại nLab
• Power object tại nLab
• Power set Algorithm in C++