| Version current |
Version 14 |
| \PMlinkescapeword{states} |
\PMlinkescapeword{states} |
| \PMlinkescapeword{property} |
\PMlinkescapeword{property} |
| {\bf Definition} |
{\bf Definition} |
| If $X$ is a set, then the \emph{power set of $X$}, denoted by $\powset{X}$, is the |
If $X$ is a set, then the \emph{power set of $X$}, denoted by $\powset{X}$, is the |
| set whose elements are the subsets of $X$. |
set whose elements are the subsets of $X$. |
|
|
| \subsubsection*{Properties} |
\subsubsection*{Properties} |
| \begin{enumerate} |
\begin{enumerate} |
| \item If $X$ is finite, then $|\powset{X}|=2^{|X|}$. |
\item If $X$ is finite, then $|\powset{X}|=2^{|X|}$. |
| \item The above property also holds when $X$ is not finite. |
\item The above property also holds when $X$ is not finite. |
| For a set $X$, let $|X|$ be the cardinality of $X$. |
For a set $X$, let $|X|$ be the cardinality of $X$. |
| Then $|\powset{X}|=2^{|X|}=|2^X|$, |
Then $|\powset{X}|=2^{|X|}=|2^X|$, |
|
where $2^X$ is the set of all functions from $X$ to $\{0,1\}$.
|
where $2^X$ is the set $\big\{f:X\to \{0,1\}\big\}$.
|
| \item For an arbitrary set $X$, Cantor's theorem states: |
\item For an arbitrary set $X$, Cantor's theorem states: |
| a) there is no bijection between $X$ and $\powset{X}$, and |
a) there is no bijection between $X$ and $\powset{X}$, and |
| b) the cardinality of $\powset{X}$ is greater than the cardinality of $X$. |
b) the cardinality of $\powset{X}$ is greater than the cardinality of $X$. |
| \end{enumerate} |
\end{enumerate} |
|
|
| \subsubsection*{Example} |
\subsubsection*{Example} |
| Suppose $S=\{a,b\}$. Then $\powset{S}=\{\emptyset, \{a\}, \{b\}, S\}$. |
Suppose $S=\{a,b\}$. Then $\powset{S}=\{\emptyset, \{a\}, \{b\}, S\}$. |
| In particular, $|\powset{S}|=2^{|S|}=4$. |
In particular, $|\powset{S}|=2^{|S|}=4$. |
|
|
| \subsubsection*{Related definition} |
\subsubsection*{Related definition} |
| If $X$ is a set, then the \emph{finite power set of $X$}, denoted by $\mathcal{F}(X)$, is the |
If $X$ is a set, then the \emph{finite power set of $X$}, denoted by $\mathcal{F}(X)$, is the |
| set whose elements are the {\bf finite} subsets of $X$. |
set whose elements are the {\bf finite} subsets of $X$. |
|
|
|
|
| \subsubsection*{Remark} |
\subsubsection*{Remark} |
| Due to the canonical correspondence between elements of $\powset{X}$ and elements of $2^X$, the power set is sometimes also denoted by $2^X$. |
Due to the canonical correspondence between elements of $\powset{X}$ and elements of $2^X$, the power set is sometimes also denoted by $2^X$. |
