Tập lũy thừa

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 Bản mẫu:Mvar thường được ký hiệu là $𝒫$(S), Bản mẫu:Math, Bản mẫu:Math, $\mathbb{P}(S)$, $\mathrm{\wp }(X)$, hoặc Bản mẫu:Math. Ký hiệu Bản mẫu:Math 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 Bản mẫu:Mvar 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ừ Bản mẫu:Mvar đến tập hai phần tử cho trước.

Bất kỳ tập con của Bản mẫu:Math được gọi là họ tập hợp trên Bản mẫu:Mvar.

Ví dụ

Nếu Bản mẫu:Mvar là tập Bản mẫu:Math, thì tất cả các tập con của tập Bản mẫu:Mvar là

• Bản mẫu:Math (hay $\varnothing$ hoặc $\mathrm{\varnothing }$, và được gọi là tập hợp rỗng hay tập rỗng)
• Bản mẫu:Math
• Bản mẫu:Math
• Bản mẫu:Math
• Bản mẫu:Math
• Bản mẫu:Math
• Bản mẫu:Math
• Bản mẫu:Math

và do đó tập luỹ thừa của Bản mẫu:Mvar là tập Bản mẫu:Math.

Tính chất

Nếu Bản mẫu:Mvar là tập hữu hạn với số lực lượng Bản mẫu:Math (tức là số các phần tử trong Bản mẫu:Math bằng với Bản mẫu:Math), thì số các tập hợp con của Bản mẫu:Mvar sẽ là Bản mẫu:Math. Nội dung này cũng chính là lý do vì sao có ký hiệu Bản mẫu:Math cho tập luỹ thừa Bản mẫu:Math 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ì Bản mẫu:Math là tập các hàm từ S đến Bản mẫu:Math 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 Bản mẫu:Math tương đương với hay có song ánh với tập luỹ thừa Bản mẫu:Math. 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 Bản mẫu:Math, số các hàm trong Bản mẫu:Math là 2ⁿ và bởi vì số 2 được dùng để định nghĩa Bản mẫu:Math (xem ví dụ số thứ tự von Neumann), nên tập Bản mẫu:Math cũng được ký hiệu là Bản mẫu:Math. Dĩ nhiên ta có Bản mẫu:Math. Tổng quát hơn, X^Y là tập các hàm từ Y đến X và Bản mẫu:Math.

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 Bản mẫu:Mvar, 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 Bản mẫu:Mvar 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, Bản mẫu:Math ký hiệu cho tập các hàm số từ Bản mẫu:Mvar đến Bản mẫu:Mvar. Có thể dùng "2" để định nghĩa tập Bản mẫu:Math (xem ví dụ số thứ tự von Neumann), Bản mẫu:Math (tức Bản mẫu:Math), là tập các hàm số từ Bản mẫu:Mvar tới Bản mẫu:Math. Như đã chứng minh ban đầu trong các tính chất, Bản mẫu:Math và tập luỹ thừa của Bản mẫu:Mvar, Bản mẫu:Math, đượ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 đó Bản mẫu:Math, để lấy ra đẳng cấu với biểu diễn nhị phân của các số từ 0 đến Bản mẫu:Math, trong đó Bản mẫu:Mvar là số các phần tử trong tập hợp Bản mẫu:Mvar hay Bản mẫu:Mvar. Đầu tiên, định nghĩa tập liệt kê tuần tự Bản mẫu:Math 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 Bản mẫu:Math; phần tử Bản mẫu:Math của Bản mẫu:Mvar nằm ở vị trí đầu tiên từ bên phải còn phần tử Bản mẫu:Mvar 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 Bản mẫu:Mvar, 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 Bản mẫu:Mvar, và 0 khi ngược lại

Xét toàn bộ tập luỹ thừa của Bản mẫu:Mvar, 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
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math
Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math	Bản mẫu:Math

Song, vì các đơn ánh từ Bản mẫu:Math đế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 Bản mẫu:Mvar 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ê Bản mẫu:Math có thể dùng để xây đơn ánh khác từ Bản mẫu:Math đế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, Bản mẫu:Math, Bản mẫu:Math, và Bản mẫu:Math 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 Bản mẫu:Mvar có lực lượng vô hạn (tức có vô hạn số phần tử thuộc Bản mẫu:Mvar), 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 Bản mẫu:Math phần tử từ một tập khác là tên gọi khác cho tập con chứa Bản mẫu:Math phần tử, và do vậy số tổ hợp (được ký hiệu bằng Bản mẫu:Math, hay còn gọi là hệ số nhị thức) số các tập con có Bản mẫu:Mvar phần tử trong tập hợp có Bản mẫu:Mvar phần tử. Nói theo tập luỹ thừa, nó là số tập hợp có Bản mẫu:Math phần tử và là phần tử của tập luỹ thừa của tập con có Bản mẫu:Math 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 $\left|2^S\right|$ bằng công thức: $$\left|2^S\right|=\sum _{k=0}^{|S|}(\genfrac{}{}{0ex}{}{|S|}{k})$$

Do đó ta có thể suy ra định thức sau, coi $|S|=n$, ta có: $$\left|2^S\right|=2^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{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 Bản mẫu:Mvar có lực lượng nhỏ hơn hoặc bằng Bản mẫu:Math đôi khi được kỳ hiệu là Bản mẫu:Math hoặc Bản mẫu:Math, và tập các tập con có lực lượng nhỏ hơn nghiêm ngặt với Bản mẫu:Math đôi khi được ký hiệu là Bản mẫu:Math hoặc Bản mẫu:Math. Tương tự, tập các tập con khác rỗng của Bản mẫu:Mvar đôi khi được ký hiệu bởi Bản mẫu:Math hay Bản mẫu:Math.

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 Bản mẫu:Mvar là tập các tập con của Bản mẫu:Mvar 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ị Bản mẫu:Mvar và Bản mẫu:Mvar, phép đồng cấu Bản mẫu:Math 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 Bản mẫu:Math chứa các đồng cấu từ Bản mẫu:Mvar đến Bản mẫu:Mvar 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ị Bản mẫu:Mvar có song ánh với đồng cấu đồ thị từ Bản mẫu:Mvar đến đa đồ thị Bản mẫu:Math đượ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 Bản mẫu:Mvar thành đa đồ thị Bản mẫu:Math, được gọi là vật luỹ thừa của Bản mẫu:Mvar.

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

• Bản mẫu:Chú thích sách
• Bản mẫu:Chú thích sách
• Bản mẫu:Chú thích sách

Liên kết ngoài

• Bản mẫu:PlanetMath
• Bản mẫu:Nlab
• Bản mẫu:Nlab
• Power set Algorithm in C++