Editing Power set (section)

== Representing subsets as functions ==
In [[set theory]], {{math|[[Function (mathematics)#Function space|''X''<sup>''Y''</sup>]]}} is the notation representing the set of all [[function (mathematics)|function]]s from {{mvar|Y}} to {{mvar|X}}.  As "{{math|2}}" can be defined as {{math|{{mset|0, 1}}}} (see, for example, [[von Neumann ordinals]]), {{math|2<sup>''S''</sup>}} (i.e., {{math|{{mset|0, 1}}<sup>''S''</sup>}}) is the set of all [[function (mathematics)|function]]s from {{math|''S''}} to {{math|{{mset|0, 1}}}}. As [[power set#Properties|shown above]], {{math|2<sup>''S''</sup>}} and the power set of {{math|''S''}}, {{math|{{itco|{{mathcal|P}}}}(''S'')}}, are considered identical set-theoretically.

This equivalence can be applied to the example [[Power set#Example|above]], in which {{math|1=''S'' = {{mset|''x'', ''y'', ''z''}}}}, to get the [[isomorphism]] with the binary representations of numbers from 0 to {{math|2<sup>''n''</sup> − 1}}, with {{mvar|n}} being the number of elements in the set {{math|''S''}} or {{math|1={{abs|''S''}} = ''n''}}. First, the enumerated set {{math|1={{mset| (''x'', 1), (''y'', 2), (''z'', 3) }}}} is defined in which the number in each ordered pair represents the position of the paired element of {{math|''S''}} in a sequence of binary digits such as {{math|1={{mset|''x'', ''y''}} = 011<sub>(2)</sub>}}; {{math|1=''x''}} of {{math|''S''}} is located at the first from the right of this sequence and {{math|''y''}} is at the second from the right, and 1 in the sequence means the element of {{math|''S''}} corresponding to the position of it in the sequence exists in the subset of {{math|''S''}} for the sequence while 0 means it does not.

For the whole power set of {{math|''S''}}, we get:
{|class="wikitable"
|-
!scope="col"| Subset
!scope="col"| Sequence<br /> of binary digits
!scope="col"| Binary<br /> interpretation
!scope="col"| Decimal<br /> equivalent
|-
| {{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>}}
|}

Such an [[Injective function|injective mapping]] from {{math|{{itco|{{mathcal|P}}}}(''S'')}} to integers is arbitrary, so this representation of all the subsets of {{math|''S''}} is not unique, but the sort order of the enumerated set does not change its cardinality. (E.g., {{math|{{mset| (''y'', 1), (''z'', 2), (''x'', 3) }}}} can be used to construct another injective mapping from {{math|{{itco|{{mathcal|P}}}}(''S'')}} to the integers without changing the number of one-to-one correspondences.)

However, such finite binary representation is only possible if {{math|''S''}} can be enumerated. (In this example, {{math|1=''x''}}, {{math|1=''y''}}, and {{math|1=''z''}} are enumerated with {{math|1}}, {{math|2}}, and {{math|3}} respectively as the position of binary digit sequences.) The enumeration is possible even if {{math|''S''}} has an infinite cardinality (i.e., the number of elements in {{math|''S''}} is infinite), such as the set of integers or rationals, but not possible for example if {{math|''S''}} is the set of real numbers, in which case we cannot enumerate all irrational numbers.