Xem mã nguồn của Tập lũy thừa

{{short description|Tập hợp trong toán học chứa tất cả tập con của một tập hợp cho trước}}
{{Infobox mathematical statement
| name = Tập luỹ thừa
| image = Hasse diagram of powerset of 3.svg
| caption = Các phần tử trong tập luỹ thừa {''x'', ''y'', ''z''}  [[lý thuyết thứ tự|được sắp thứ tự]] theo [[tập hợp con|phép bao hàm tập hợp]]
| type = [[Tập hợp (toán học)|Phép toán tập hợp]]
| field = [[Lý thuyết tập hợp]]
| statement = Tập luỹ thừa là tập chứa tất cả tập con của tập cho trước.
| symbolic statement = <math>x\in P(S) \iff x\subseteq S</math>
}}

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 hợp con|tập con]] của ''A'', bao gồm cả ''A'' và [[tập hợp rỗng]]<ref name="Weisstein">{{chú thích web|last=Weisstein|first=Eric W.| title=Power Set| url=https://mathworld.wolfram.com/PowerSet.html|access-date=2020-09-05| website=mathworld.wolfram.com| language=en}}</ref>. 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 [[định đề|đặt thành định đề]] theo [[tiên đề tập luỹ thừa]].<ref>{{harvnb|Devlin|1979|page=50}}</ref> 
Tập luỹ thừa của {{mvar|S}} thường được ký hiệu là <math>\mathcal{P}</math>(''S''), {{math|𝒫(''S'')}}, {{math|''P''(''S'')}}, <math>\mathbb{P}(S)</math>, <math>\wp(X)</math>, hoặc {{math|2<sup>''S''</sup>}}. Ký hiệu {{math|2<sup>''S''</sup>}} 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 {{mvar|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ừ {{mvar|S}} đến tập hai phần tử cho trước.<ref name="Weisstein" />

Bất kỳ tập con của {{math|𝒫(''S'')}} được gọi là ''[[họ tập hợp]]'' trên {{mvar|S}}.

==Ví dụ==
Nếu {{mvar|S}} là tập {{math|{{mset|''x'', ''y'', ''z''}}}}, thì tất cả các tập con của tập {{mvar|S}} là

* {{math|{{mset}}}} (hay <math>\varnothing</math> hoặc <math>\empty</math>, và được gọi là [[tập hợp rỗng]] hay tập rỗng)
* {{math|{{mset|''x''}}}}
* {{math|{{mset|''y''}}}}
* {{math|{{mset|''z''}}}}
* {{math|{{mset|''x'', ''y''}}}}
* {{math|{{mset|''x'', ''z''}}}}
* {{math|{{mset|''y'', ''z''}}}}
* {{math|{{mset|''x'', ''y'', ''z''}}}}
và do đó tập luỹ thừa của {{mvar|S}} là tập {{math|{{mset|{{mset}},
{{mset|''x''}},
{{mset|''y''}},
{{mset|''z''}},
{{mset|''x'', ''y''}},
{{mset|''x'', ''z''}},
{{mset|''y'', ''z''}},
{{mset|''x'', ''y'', ''z''}}}}}}.<ref>{{harvnb|Puntambekar|2007|pages=1–2}}</ref>

==Tính chất==
Nếu {{mvar|''S''}} là tập hữu hạn với [[lực lượng (tập hợp)|số lực lượng]] {{math|1={{!}}''S''{{!}} = ''n''}} (tức là số các phần tử trong {{math|1=''S''}} bằng với {{math|1=''n''}}), thì số các tập hợp con của {{mvar|''S''}} sẽ là {{math|1={{!}}𝒫(''S''){{!}} = 2<sup>''n''</sup>}}. Nội dung này cũng chính là lý do vì sao có ký hiệu {{math|2<sup>''S''</sup>}} cho tập luỹ thừa {{math|1=𝒫(''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<sub>A</sub>'': ''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<sub>A</sub>''(''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<sub>A</sub>'', vì {{math|{{mset|0,1}}<sup>''S''</sup>}} là tập các hàm từ ''S'' đến {{math|{{mset|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 {{math|{{mset|0,1}}<sup>''S''</sup>}} tương đương với hay có [[song ánh]] với tập luỹ thừa {{math|1=𝒫(''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 {{math|{{mset|0,1}}<sup>''S''</sup>}}, số các hàm trong {{math|{{mset|0,1}}<sup>''S''</sup>}} là 2<sup>''n''</sup> và bởi vì số 2 được dùng để định nghĩa {{math|{{mset|0,1}}}} (xem ví dụ [[số thứ tự von Neumann]]), nên tập {{math|1=𝒫(''S'')}} cũng được ký hiệu là {{math|2<sup>''S''</sup>}}. Dĩ nhiên ta có {{math|1={{abs|2<sup>''S''</sup>}} = 2<sup>{{abs|''S''}}</sup>}}. Tổng quát hơn, ''X<sup>Y</sup>'' là tập các hàm từ ''Y'' đến ''X'' và {{math|1={{!}}''X''<sup>''Y''</sup>{{!}} = {{!}}''X''{{!}}<sup>{{!}}''Y''{{!}}</sup>}}.
[[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ó [[lực lượng (tập hợp)|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 đếm được|tập vô hạn đếm được]] là [[tập không đếm được|tập vô hạn không đếm được]]. Tập luỹ thừa của các [[số tự nhiên]] có [[song ánh|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 {{mvar|''S''}}, cùng với [[Hợp (lý thuyết tập hợp)|phép hợp]], [[Giao (lý thuyết tập hợp)|phép giao]] và [[phần bù (lý thuyết tập hợp)|phép bù]], có thể được xem là mô hình ví dụ của [[đại số Boole (cấu trúc)|đạ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 {{mvar|''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]] [[tính giao hoán|giao hoán]] khi xét phép giao. Từ đây có thể chứng minh sử dụng [[Tính phân phối|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]], {{math|[[Hàm số#Không gian hàm|''X''<sup>''Y''</sup>]]}} ký hiệu cho tập các [[hàm số]] từ {{mvar|Y}} đến {{mvar|X}}.  Có thể dùng "2" để định nghĩa tập {{math|{{mset|0,1}}}} (xem ví dụ [[số thứ tự von Neumann]]), {{math|2<sup>''S''</sup>}} (tức {{math|{{mset|0,1}}<sup>''S''</sup>}}), là tập các hàm số từ  {{mvar|''S''}} tới {{math|{{mset|0,1}}}}. Như đã chứng minh ban đầu trong các tính chất, {{math|2<sup>''S''</sup>}} và tập luỹ thừa của {{mvar|''S''}}, {{math|1=𝒫(''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ụ|ví dụ ban đầu]], trong đó {{math|1=''S'' = {{mset|''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 {{math|2<sup>''n''</sup> − 1}}, trong đó {{mvar|n}} là số các phần tử trong tập hợp {{mvar|''S''}} hay {{mvar|1={{!}}''S''{{!}} = n}}. Đầu tiên, định nghĩa tập liệt kê tuần tự {{math|1={{mset| (''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 {{math|1={{mset|''x'', ''y''}} = 011<sub>(2)</sub>}}; phần tử {{math|1=''x''}} của {{mvar|''S''}} nằm ở vị trí đầu tiên từ bên phải còn phần tử {{mvar|''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 {{mvar|''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 {{mvar|''S''}}, và 0 khi ngược lại

Xét toàn bộ tập luỹ thừa của {{mvar|''S''}}, ta được:
{|class="wikitable"
|-
!scope="col"| Tập con 
!scope="col"| Dãy chữ số 
nhị phân
!scope="col"| Biểu diễn 
nhị phân 
!scope="col"| Số thập phân 
tương ứng
|-
| {{math|1={{mset|                     }} }} || {{math|0, 0, 0}} || {{math|000<sub>(2)</sub>}} || {{math|0<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x''               }} }} || {{math|0, 0, 1}} || {{math|001<sub>(2)</sub>}} || {{math|1<sub>(10)</sub>}}
|-
| {{math|1={{mset|        ''y''        }} }} || {{math|0, 1, 0}} || {{math|010<sub>(2)</sub>}} || {{math|2<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'', ''y''        }} }} || {{math|0, 1, 1}} || {{math|011<sub>(2)</sub>}} || {{math|3<sub>(10)</sub>}}
|-
| {{math|1={{mset|               ''z'' }} }} || {{math|1, 0, 0}} || {{math|100<sub>(2)</sub>}} || {{math|4<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'',        ''z'' }} }} || {{math|1, 0, 1}} || {{math|101<sub>(2)</sub>}} || {{math|5<sub>(10)</sub>}}
|-
| {{math|1={{mset|        ''y'', ''z'' }} }} || {{math|1, 1, 0}} || {{math|110<sub>(2)</sub>}} || {{math|6<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'', ''y'', ''z'' }} }} || {{math|1, 1, 1}} || {{math|111<sub>(2)</sub>}} || {{math|7<sub>(10)</sub>}}
|}

Song, vì các đơn ánh từ {{math|1=𝒫(''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 {{mvar|''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ê {{math|{{mset| (''y'', 1), (''z'', 2), (''x'', 3) }}}} có thể dùng để xây đơn ánh khác từ {{math|𝒫(''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, {{math|1=''x''}}, {{math|1=''y''}}, và {{math|1=''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 {{mvar|''S''}} có lực lượng vô hạn (tức có vô hạn số phần tử thuộc {{mvar|''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 {{math|k}} phần tử từ một tập khác là tên gọi khác cho tập con chứa {{math|k}} phần tử, và do vậy số [[tổ hợp]] (được ký hiệu bằng {{math|C(''n'', ''k'')}}, hay còn gọi là hệ số nhị thức) số các tập con có {{mvar|k}} phần tử trong tập hợp có {{mvar|n}} phần tử. Nói theo tập luỹ thừa, nó là số tập hợp có {{math|k}} phần tử và là phần tử của tập luỹ thừa của tập con có {{math|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ử ([[Đơn điểm (toán học)|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 <math display="inline">\left|2^S \right|</math> bằng công thức:
<math display="block">\left|2^S \right | = \sum_{k=0}^{|S|} \binom{|S|}{k} </math>

Do đó ta có thể suy ra định thức sau, coi <math display="inline">|S| = n</math>, ta có:
<math display="block">\left |2^S \right| = 2^n = \sum_{k=0}^{n} \binom{n}{k} </math>

==Định nghĩa đệ quy==
Nếu <math>S</math> là [[tập hữu hạn]], thì ta có [[định nghĩa đệ quy]] của <math>P(S)</math> như sau:

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

Nói bằng từ: 
* Tập luỹ thừa của [[tập rỗng]] là [[Đơn điểm (toán học)|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 <math>S</math>,  gọi <math>e</math> là phần tử bất kỳ trong tập hợp và <math>T</math> là [[Phần bù#phần bù tương đối|phần bù tương đối]] của nó; khi đó tập luỹ thừa của <math>S</math> là hợp của tập luỹ thừa của <math>T</math> và một tập luỹ thừa khác của <math>T</math> trong đó mỗi phần tử được gán thêm phần tử <math>e</math>.

==Tập con bị giới hạn lực lượng==
Tập các tập con của {{mvar|''S''}} có [[Lực lượng (tập hợp)|lực lượng]] nhỏ hơn hoặc bằng {{math|κ}} đôi khi được kỳ hiệu là {{math|𝒫<sub>κ</sub>(''S'')}} hoặc {{math|[''S'']<sup>κ</sup>}}, và tập các tập con có lực lượng nhỏ hơn nghiêm ngặt với {{math|κ}} đôi khi được ký hiệu là {{math|𝒫<sub>< κ</sub>(''S'')}} hoặc {{math|[''S'']<sup><κ</sup>}}. Tương tự, tập các tập con khác rỗng của {{mvar|''S''}} đôi khi được ký hiệu bởi  {{math|𝒫<sub>≥ 1</sub>(''S'')}} hay {{math|𝒫<sup>+</sup>(''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 {{mvar|''X''}} là tập các tập con của {{mvar|''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 (lý thuyết thứ 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ị {{mvar|''G''}} và {{mvar|''H''}}, [[phép đồng cấu]] {{math|''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 {{math|''H''<sup>''G''</sup>}} chứa các đồng cấu từ {{mvar|''G''}} đến {{mvar|''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ị {{mvar|''G''}} có song ánh với đồng cấu đồ thị từ {{mvar|''G''}} đến đa đồ thị {{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 {{mvar|''G''}} thành đa đồ thị {{math|Ω<sup>''G''</sup>}}, được gọi là '''vật luỹ thừa''' của {{mvar|''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]]

==Tham khảo==
{{tham khảo}}

==Thư mục==
* {{chú thích sách | last=Devlin | first=Keith J. | author-link=Keith Devlin | title=Fundamentals of contemporary set theory | url=https://archive.org/details/fundamentalsofco0000devl | series=Universitext | publisher=[[Springer-Verlag]] | year=1979 | isbn=0-387-90441-7 | zbl=0407.04003 }}
* {{chú thích sách | last=Halmos | first=Paul R. | author-link=Paul Halmos | title=Naive set theory | url=https://archive.org/details/naivesettheory00halm | url-access=registration | series=The University Series in Undergraduate Mathematics | publisher=van Nostrand Company | year=1960 | zbl=0087.04403 }}
* {{chú thích sách |last=Puntambekar | first=A. A. | title=Theory Of Automata And Formal Languages | year=2007 | publisher=Technical Publications | isbn=978-81-8431-193-8 }}

==Liên kết ngoài==
{{Wiktionary|power set}}
*{{PlanetMath |urlname=powerset |title=Power set}}
* {{nlab|id=power+set|title=Power set}}
* {{nlab|id=power+object|title=Power object}}
* [http://www.programminglogic.com/powerset-algorithm-in-c/ Power set Algorithm] in [[C++]]

{{Logic toán học}}
{{Lý thuyết tập hợp}}

[[Thể loại:Lý thuyết tập hợp]]