Power set

From CS2800 wiki


Definition: Power set
The power set of a set [math]A [/math] (written [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math])is the set of all subsets of [math]A [/math]. Formally, [math]\href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{B \mid} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A\} [/math].

Because the elements of the power set are themselves sets, it is easy to confuse elements and subsets. As with any set comprehension, the elements of [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] are the subsets of [math]A [/math]. Here are some examples:

Let [math]A := \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]. Then

  • [math]\href{/cs2800/wiki/index.php/2}{2}^A = \{ \href{/cs2800/wiki/index.php/Empty_set}{\{\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} \} [/math], by inspection. For example, [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] because [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].
  • [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/2}{2}^A [/math], because 1 is a number but [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] contains only sets. Put differently, [math]1 \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} A [/math].
  • Therefore [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} \href{/cs2800/wiki/index.php/2}{2}^A [/math]
  • But note that [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math].
  • for any set [math]X [/math], we have [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] and [math]X \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^X [/math], because ∅⊆X and X⊆X.