1.1.2: Subsets and Power Sets

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

We will often want to compare sets. And one obvious kind of comparison one might make is as follows: everything in one set is in the other too. This situation is sufficiently important for us to introduce some new notation.

Definition \(\PageIndex{1}\): Subset

If every element of a set \(A\) is also an element of \(B\), then we say that \(A\) is a subset of \(B\), and write \(A \subseteq B\). If \(A\) is not a subset of \(B\) we write \(A \not\subseteq B\). If \(A \subseteq B\) but \(A \neq B\), we write \(A \subsetneq B\) and say that \(A\) is a proper subset of \(B\).

Example \(\PageIndex{1}\)

Every set is a subset of itself, and \(\emptyset\) is a subset of every set. The set of even numbers is a subset of the set of natural numbers. Also, \(\{ a, b \} \subseteq \{ a, b, c \}\). But \(\{ a, b, e \}\) is not a subset of \(\{ a, b, c \}\).

Example \(\PageIndex{2}\)

The number \(2\) is an element of the set of integers, whereas the set of even numbers is a subset of the set of integers. However, a set may happen to both be an element and a subset of some other set, e.g., \(\{0\} \in \{0, \{0\}\}\) and also \(\{0\} \subseteq \{0, \{0\}\}\).

Extensionality gives a criterion of identity for sets: \(A = B\) iff every element of \(A\) is also an element of \(B\) and vice versa. The definition of “subset” defines \(A \subseteq B\) precisely as the first half of this criterion: every element of \(A\) is also an element of \(B\). Of course the definition also applies if we switch \(A\) and \(B\): that is, \(B \subseteq A\) iff every element of \(B\) is also an element of \(A\). And that, in turn, is exactly the “vice versa” part of extensionality. In other words, extensionality entails that sets are equal iff they are subsets of one another.

Proposition \(\PageIndex{1}\)

\(A = B\) iff both \(A \subseteq B\) and \(B \subseteq A\).

Now is also a good opportunity to introduce some further bits of helpful notation. In defining when \(A\) is a subset of \(B\) we said that “every element of \(A\) is …,” and filled the “\(\dots\)” with “an element of \(B\)”. But this is such a common shape of expression that it will be helpful to introduce some formal notation for it.

Definition \(\PageIndex{2}\)

\((\forall x \in A)\phi\) abbreviates \(\forall x(x \in A \rightarrow \phi)\). Similarly, \((\exists x \in A)\phi\) abbreviates \(\exists x(x \in A \land \phi)\).

Using this notation, we can say that \(A \subseteq B\) iff \((\forall x \in A)x \in B\).

Now we move on to considering a certain kind of set: the set of all subsets of a given set.

Definition \(\PageIndex{3}\): Power Set

The set consisting of all subsets of a set \(A\) is called the power set of \(A\), written \(\Pow{A}\). \[\Pow{A} = \Setabs{B}{B \subseteq A}\nonumber\]

Example \(\PageIndex{3}\)

What are all the possible subsets of \(\{ a, b, c \}\)? They are: \(\emptyset\), \(\{a \}\), \(\{b\}\), \(\{c\}\), \(\{a, b\}\), \(\{a, c\}\), \(\{b, c\}\), \(\{a, b, c\}\). The set of all these subsets is \(\Pow{\{a,b,c\}}\): \[\Pow{\{ a, b, c \}} = \{\emptyset, \{a \}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a, c\}, \{a, b, c\}\}\nonumber\]

Problem \(\PageIndex{1}\)

List all subsets of \(\{a, b, c, d\}\).

Problem \(\PageIndex{2}\)

Show that if \(A\) has \(n\) elements, then \(\Pow{A}\) has \(2^n\) elements.