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à (S), , , , , 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.

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

Ví dụ
Nếu  là tập , thì tất cả các tập con của tập  là

  (hay  hoặc , và được gọi là tập hợp rỗng hay tập rỗng)
 
 
 
 
 
 
 
và do đó tập luỹ thừa của  là tập .

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à IA: 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ì IA(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ị IA, 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à 2n 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, XY 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  bằng công thức:

Do đó ta có thể suy ra định thức sau, coi , ta có:

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

Nếu , thì .
Mặt khác, nếu  và ; thì .

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 ,  gọi  là phần tử bất kỳ trong tập hợp và  là phần bù tương đối của nó; khi đó tập luỹ thừa của  là hợp của tập luỹ thừa của  và một tập luỹ thừa khác của  trong đó mỗi phần tử được gán thêm phần tử .

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.

Xem thêm

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

Tham khảo

Thư mục

Liên kết ngoài

 
 
 Power set Algorithm in C++

Lý thuyết tập hợp