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

Tính chất

Nếu là tập hữu hạn với số lực lượng (tức là số các phần tử trong bằng với ), thì số các tập hợp con của sẽ là . Nội dung này cũng chính là lý do vì sao có ký hiệu cho tập luỹ thừa 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ì là tập các hàm từ S đến 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 tương đương với hay có song ánh với tập luỹ thừa . 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 , số các hàm trong là 2ⁿ và bởi vì số 2 được dùng để định nghĩa (xem ví dụ số thứ tự von Neumann), nên tập cũng được ký hiệu là . Dĩ nhiên ta có . Tổng quát hơn, X^Y là tập các hàm từ Y đến X và . 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 , 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 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, ký hiệu cho tập các hàm số từ đến . Có thể dùng "2" để định nghĩa tập (xem ví dụ số thứ tự von Neumann), (tức ), là tập các hàm số từ tới . Như đã chứng minh ban đầu trong các tính chất, và tập luỹ thừa của , , đượ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 đó , để lấy ra đẳng cấu với biểu diễn nhị phân của các số từ 0 đến , trong đó là số các phần tử trong tập hợp hay . Đầu tiên, định nghĩa tập liệt kê tuần tự 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 ; phần tử của nằm ở vị trí đầu tiên từ bên phải còn phần tử 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 , 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 , và 0 khi ngược lại

Xét toàn bộ tập luỹ thừa của , ta được:

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

Do đó ta có thể suy ra định thức sau, coi $|S|\; =\; n$, ta có:

Đị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)\; =\; \{\backslash ,\{\}\backslash ,\}$. Mặt khác, nếu $e\backslash in\; S$ và $T=S\backslash setminus\{e\}$; thì $P(S)\; =\; P(T)\backslash cup\; \{t\backslash cup\; \{e\}\; :\; t\backslash 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 có lực lượng nhỏ hơn hoặc bằng đôi khi được kỳ hiệu là hoặc , 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à hoặc . Tương tự, tập các tập con khác rỗng của đôi khi được ký hiệu bởi hay .

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

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.