\documentclass{amsart} \usepackage[parfill]{parskip} \usepackage{graphicx} \usepackage{amssymb, latexsym} \usepackage{epstopdf} \usepackage{color} \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png} \textwidth = 6.5 in \textheight = 9 in \oddsidemargin = 0.0 in \evensidemargin = 0.0 in \topmargin = 0.0 in \headheight = 0.0 in \headsep = 0.0 in \parskip = 0.2in \parindent = 0.0in \pagestyle{plain} \newsavebox{\savepar} \newenvironment{xbox}{\begin{lrbox}{\savepar} \begin{minipage}[c]{\textwidth}} {\end{minipage}\end{lrbox}\fcolorbox{black}{green}{\usebox{\savepar}}} \renewcommand{\baselinestretch}{1.3} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \theoremstyle{definition} \newtheorem*{definition}{Definition} \newtheorem*{defn}{Definition} \newtheorem{example}{Example} \theoremstyle{remark} \newtheorem*{notation}{Notation} \newtheorem*{note}{Note} \begin{document} \setcounter{section}{1} \section{Cardinal Numbers} \subsection{Infinite Sets and Cardinal Numbers} \begin{defn} Two sets $A$ and $B$ are \emph{equipotent}, or equivalently, \emph{have the same cardinality}, iff there exists a bijection $f:A \to B$. \end{defn} \begin{notation} $A \sim B$ \end{notation} \begin{xbox} \begin{example} Let $\mathbb{P}$ denote the positive integers and let $\mathbb{E}$ denote the even positive integers. Then $\mathbb{P} \sim \mathbb{E}$. Also $\mathbb{R} \sim (0, 1)$. \end{example} \end{xbox} \begin{prop} Equipotency is an equivalence relation on any collection of sets. \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{cor} Any collection of sets can be partitioned into equipotency classes; that is, two sets are in the same class if and only if they are equipotent (equivalently, they have the same cardinality). \end{cor} \begin{defn} A set $A$ is: \begin{enumerate} \item \emph{finite} iff $A = \emptyset$ or $A \sim \{1,2, \dots, n\}$ for some $n \in \mathbb{P}$; \item \emph{infinite} iff it is not finite; \item \emph{countably infinite} or \emph{denumerable} iff $A \sim \mathbb{P}$; \item \emph{countable} iff $A$ is finite or denumerable; \item \emph{uncountable} iff $A$ is not countable. \end{enumerate} \end{defn} \begin{example} From real analysis, we know that $\mathbb{Z}$ and $\mathbb{Q}$ are countably infinite, but $\mathbb{R}$ is uncountable. \end{example} The proof of the following proposition can be found in any real analysis textbook. \begin{prop}\hfill \begin{enumerate} \item Every subset of a countable set is countable. \item Every countable union of countable sets is countable; that is, if $I$ is countable and $A_i$ is countable for all $i \in I$, then $\bigcup\{ A_i\, | \, i \in I \}$ is countable. \end{enumerate} \end{prop} \begin{cor} If $B$ is uncountable and $A \subset B$ is countable, then $B\backslash A$ is uncountable. \end{cor} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{example} The set of irrationals numbers, $\mathbb{I}$, is uncountable. \end{example} \begin{note} From real analysis, we know that $\mathbb{Q}$ is \emph{dense} in $\mathbb{R}$; that is, between any two real numbers, there is a rational number. We also know that $\mathbb{I}$ is dense in $\mathbb{R}$. However, $\mathbb{Q}$ is denumerable while $\mathbb{I}$ is uncountable. This shows that \emph{density} does not determine \emph{cardinality}. \end{note} \begin{defn} A set has the \emph{power of the continuum} iff it is equipotent to $\mathbb{R}$. \end{defn} \begin{xbox} \begin{example} For any $a < b \in \mathbb{R}$, the open interval $(a, b)$ has the power of the continuum. \end{example} \end{xbox} \begin{theorem} \label{DenumSub} Every infinite set contains a denumerable subset. \end{theorem} \begin{xbox} \begin{proof} Assume $A$ is infinite. Then $A$ is nonempty, and so $\wp^*(A)$, the set of all nonempty subsets of $A$, is a nonempty collection of nonempty sets. Note that $\bigcup \wp^*(A) = A$. By the Axiom of Choice, there exists a choice function $f:\wp^*(A) \to A$. Let $a_1=f(A)$. Then $A_1=A\backslash \{a_1\}$ is nonempty, for otherwise $A = \{ a_1 \} \sim\{1\}$, meaning $A$ is finite. Let $a_2 = f(A_1)$. ..... \end{proof} \end{xbox} \begin{prop} If $B$ is denumerable and $A \subset B$ is finite, then $B\backslash A \sim B$; that is, $B\backslash A$ is also denumerable. \end{prop} \begin{xbox} \begin{proof} By definition, a denumerable set is countable. Hence, by Proposition 2.3 (1), $B\backslash A$ is countable.... \end{proof} \end{xbox} \begin{cor}\label{inf-fin} If $B$ is infinite and $A \subset B$ is finite, then $B\backslash A \sim B$. \end{cor} \begin{xbox} \begin{proof} By Theorem \ref{DenumSub} , $B$ contains a denumerable subset $D = \{d_1, d_2, \dots \}$. Without loss of generality, we may assume that $A \subset D$. [Why?] (\emph{Hint.} Now define a bijection $g:B \to B \backslash A$ by defining $g$ separately on elements of $D$ and $B \backslash D$.) \end{proof} \end{xbox} \begin{example} For any $a < b \in \mathbb{R}$, the intervals $(a,b), [a,b], (a, b]$ and $[a, b)$ all have the power of the continuum. \end{example} \begin{defn} A set is \emph{Dedekind infinite} iff it is equipotent to a proper subset of itself. \end{defn} \begin{xbox} \begin{example} The sets $\mathbb{P}, \mathbb{R}, \mathbb{Z}$ and $\mathbb{Q}$ are Dedekind infinite. \end{example} \end{xbox} \begin{prop} For all $n \in \mathbb{P}, \{ 1,2 , \dots, n \}$ is not Dedekind infinite. \end{prop} \begin{xbox} \begin{proof} (\emph{Hint.} Use induction on $n$. For the inductive hypothesis, assume that there is no bijection of $\{1, 2, \dots, n\}$ to a proper subset of itself. Assume that there is a bijection $f:\{1, 2, \dots, n, n+1\} \to A$, where $A$ is a proper subset of $\{1, 2, \dots, n, n+1\}$. We now divide into cases. \begin{itemize} \item Case 1. If $f(n+1) = n+1$, then the restriction of $f$ to $\{1, 2, \dots, n \}$ is a bijection of this set to $A\backslash \{n+1\}$, which is itself a proper subset of $\{1, 2, \dots, n\}$. [Why?] This contradicts the inductive hypothesis. \item Case 2. Assume $f(n+1) = k$, where $k \leq n$. \begin{itemize} \item Subcase a. If $n+1 \notin A$, then... \item Subcase b. If $f(m) = n+1$ for some $m \in \{1, 2, \dots, n\}$, then...) \end{itemize} \end{itemize} \end{proof} \end{xbox} \begin{theorem} A set is infinite if and only if it is Dedekind infinite. \end{theorem} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \framebox[\textwidth][c]{ \parbox{.9\textwidth}{ \begin{defn} Each set $A$ is assigned a symbol in such a way that two sets are assigned the same symbol iff they are equipotent. This symbol is called the \emph{cardinality} or \emph{cardinal number} of the set $A$ and is denoted by $|A|$. Note that by definition, \[ |A| = |B| \iff A \sim B. \] In other words, a cardinal number is an equivalence class of equipotent sets. \end{defn} } } \begin{example} The finite cardinal numbers correspond to the nonnegative integers, $\mathbb{N}$. More precisely, \linebreak $|A| = 0 \iff A = \emptyset$ and for each $n \in \mathbb{P}$, $|A|=n \iff A \sim \{1, 2, \dots, n\}$. Two examples of infinite or \emph{transfinite} cardinal numbers are $|\mathbb{P}| = \aleph_0$ (read as `aleph-null') and $|\mathbb{R}| = \mathbf{c}$. \end{example} \begin{note} If $A$ is a finite set, then everybody agrees that ``$|A|$" coincides with ``the number of elements in $A$". However, some would dispute this in the case where $A$ is an infinite set. \end{note} \subsection{Ordering of Cardinal Numbers} \begin{defn} Cardinal numbers $\alpha$ and $\beta$ satisfy $\alpha \leq \beta$ iff there exist sets $A$ and $B$ satisfying $\alpha = |A|$ and $\beta = |B|$, and an injection $f:A \to B$. \end{defn} \begin{xbox} \begin{note} Equivalently, $\alpha \leq \beta$ iff there exists sets $A$ and $B$, satisfying $\alpha = |A|$ and $\beta = |B|$, where $A \subseteq B$. \end{note} \end{xbox} \begin{xbox} \begin{note} This definition is independent of the sets $A$ and $B$, in the sense that if $A^\prime$ and $B^\prime$ are other sets satisfying $\alpha = |A^\prime|$ and $\beta = |B^\prime|$, then there exists an injection $f:A \to B$ if and only if there exists an injection $f^\prime:A^\prime \to B^\prime$. (Another way of saying this is that this ordering on cardinal numbers is \emph{well-defined}.) \end{note} \end{xbox} \begin{prop} For any infinite set $A$, $\aleph_0 \leq |A|$. \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{theorem}[Schr\"{o}der-Bernstein Theorem] If $\alpha$ and $\beta$ are cardinal numbers satisfying $\alpha \leq \beta$ and $\beta \leq \alpha$, then $\alpha = \beta$. \end{theorem} \begin{proof} It suffices to show that if sets $A, \, B$ and $A_1$ satisfy $A_1 \subseteq B \subseteq A$ and $A \sim A_1$, then $A \sim B$. To see this, assume $\alpha \leq \beta$ and $\beta \leq \alpha$. Let $A$ be a set of cardinality $ \alpha$. Since $\beta \leq \alpha$, there exists a subset $B \subseteq A$ of cardinality $\beta$. Since $\alpha \leq \beta$, there must be a subset $A_1 \subseteq B$, satisfying $|A_1| = |A| = \alpha$. If we could now conclude that $A \sim B$, then we would know $\alpha = \beta$. Since $A \sim A_1$, there exists a bijection $f:A \to A_1$. Note that the restriction of $f$ to $B \subseteq A$ is still injective and that $f(B) \subseteq f(A) = A_1$. If we let $B_1 = f(B)$, then we have $B_1 \subseteq A_1 \subseteq B$ and $B \sim B_1$ via (a restriction of) $f$. We can repeat this argument; if we let $A_2 = f(A_1)$, then $A_2 \subseteq B_1 \subseteq A_1$ and $A_2 \sim A_1$. See Figure 1. \begin{figure}[htbp] % figure placement: here, top, bottom, or page \centering \includegraphics[width=3.3in]{SBT2.pdf} \caption{Venn diagram for the proof of the Schr\"{o}der-Bernstein Theorem} \label{fig:Venn} \end{figure} Repeating this indefinitely, we obtain a nested sequence of sets, $ \dots B_3 \subseteq A_3 \subseteq B_2 \subseteq A_2 \subseteq B_1 \subseteq A_1 \subseteq B \subseteq A$, with the property that the appropriate restriction of $f$ bijectively `shrinks' $A_k$ to $A_{k+1}$ and $B_k$ to $B_{k+1}$, for all $k \in \mathbb{P}$. In particular, $f:(A_k\backslash B_k) \to (A_{k+1}\backslash B_{k+1})$ is a bijection, which means that in terms of the Venn diagram in Figure \ref{fig:Venn}, all of the shaded `rings' are equipotent sets, via (a restriction of) $f$. Let $Z= A \cap B \cap A_1 \cap B_1 \cap A_2 \cap B_2 \cap \dots$. (Note that it is possible that $Z = \emptyset$; it is also possible that $Z = A$.) We claim $f(Z)=Z$; that is, (an appropriate restriction of) $f$ is a bijection of $Z$ back onto itself. To show $f(Z) \subseteq Z$, first assume $z \in Z$; we must show $f(z)\in Z$. Since $z \in A$, $f(z) \in A_1$, which in turn implies $f(z) \in B$ and $f(z) \in A$, since $A_1 \subseteq B \subseteq A$. Next, since $z \in B$, $f(z) \in B_1$. More generally, for all $k \in \mathbb{P}$, $z\in A_k$ implies $f(z) \in A_{k+1}$ and $z\in B_k$ implies $f(z) \in B_{k+1}$ . This shows $f(z) \in Z$. For the reverse inclusion, suppose $w \in Z$; we must show $w = f(u)$ for some $u \in Z$. Since $w \in Z$, in particular $w \in A_1$, and since $f:A \to A_1$ is a bijection, there exists some $u \in A$ such that $f(u) = w$. Now, $w$ is also an element of $A_2 = f(A_1)$ so $u \in A_1$. In fact, for all $k \in \mathbb{P}, w \in A_{k+1}$ and so $u \in A_k$. Similarly, since $w \in Z$, $w \in B, B_1$ and $B_{k+1}$ for all $k \in \mathbb{P}$; this shows $u \in B$ and $u \in B_k$ for all $k \in \mathbb{P}$. Hence $u \in Z$. Now, we can express $A$ and $B$ as the \emph{disjoint} unions of nested shaded and unshaded `rings': \begin{align*} A &= Z \cup (A\backslash B) \cup (B \backslash A_1) \cup (A_1 \backslash B_1) \cup \dots; \\ B&= Z \cup (B \backslash A_1) \cup (A_1 \backslash B_1) \cup ( B_1 \backslash A_2 )\cup \dots. \end{align*} Define a function $g:A \to B$ as follows: \[ g(x) = \begin{cases} f(x),& \text{ if } x \in Z \text{ or } x \in A \backslash B \text{ or } x \in A_k \backslash B_k \text{ for some } k \in \mathbb{P};\\ x,& \text{ if } x \in B \backslash A_1 \text{ or } x \in B_k \backslash A_{k+1} \text{ for some } k \in \mathbb{P}. \end{cases} \] Intuitively, $g$ acts as $f$ on the intersection set $Z$ and all of the shaded `rings' (taking each shaded `ring' down to the next shaded `ring' inside it, bijectively), and as the identity on all of the unshaded `rings'. Then $g$ is a bijection because each piece of this piecewise-defined function is a bijection. \end{proof} \begin{defn} Cardinal numbers $\alpha$ and $\beta$ satisfy $\alpha < \beta$ iff there exist sets $A$ and $B$ satisfying $\alpha = |A|$ and $\beta = |B|$, and an injection $f:A \to B$, but no bijection exists from $A$ to $B$. \end{defn} \begin{xbox} \begin{note} [Why can't we say $\alpha < \beta$ iff there exists a set $A$ with $|A|=\alpha$ and a set $B$ with $|B|=\beta$ such that $A \subset B$ ({\it i.e.} $A$ is a {\it proper} subset of $B$)?] \end{note} \end{xbox} \begin{note} For all cardinal numbers, $\alpha < \beta$ implies $\alpha \leq \beta$. \end{note} \begin{theorem} Let $\alpha, \beta$ and $\gamma$ be cardinal numbers. Then \begin{enumerate} \item if $\alpha \leq \beta$ and $\beta \leq \gamma$, then $\alpha \leq \gamma$; \item if $\alpha < \beta$ and $\beta \leq \gamma$ \emph{or} if $\alpha \leq \beta$ and $\beta < \gamma$, then $\alpha < \gamma$. \end{enumerate} \end{theorem} \begin{xbox} \begin{proof} (\emph{Hint.} Use the Schr\"{o}der-Bernstein Theorem, indirectly, for part (2).) \end{proof} \end{xbox} \begin{xbox} \begin{example} As cardinal numbers, $0 < 1 < 2<\dots \beta$. \end{theorem} The proof of this theorem is postponed until Chapter 5. \framebox[\textwidth][c]{ \parbox{.9\textwidth}{ \vspace{8pt} \textbf{CONTINUUM HYPOTHESIS.} \emph{There is no cardinal number $\alpha$ such that $\aleph_0 < \alpha < \mathbf{c}$.} \vspace{8pt} } } \begin{note} In 1938, Kurt G\"{o}del proved that this statement is consistent with the rest of set theory; Paul Cohen showed in 1963 that the negation of this statement is also consistent with the rest of set theory. That is, neither assuming that it is true nor assuming that it is false results in a contradiction. In this sense, the Continuum Hypothesis is independent of the rest of set theory. The exact `truth status' of this statement is the subject of much debate. \end{note} \subsection{Cardinal Number Arithmetic} \begin{defn} Let $\alpha$ and $\beta$ be cardinal numbers, and let $A$ and $B$ be \emph{disjoint} sets such that $\alpha = |A|$ and $\beta = |B|$. Then $\alpha + \beta = |A \cup B|$. \end{defn} \begin{note} Cardinal number addition is well-defined; if $f:A \to A^\prime$ and $g:B \to B^\prime$ are bijections, and $A^\prime$ and $B^\prime$ are disjoint, then we can define a bijection $h:A \cup B \to A^\prime \cup B^\prime$ by \[ h(x) = \begin{cases} f(x), \quad& \text{ if } x \in A; \\ g(x), & \text{ if } x \in B. \end{cases} \] Moreover, cardinal number addition generalizes natural number addition; if $A$ and $B$ are disjoint \emph{finite} sets, then certainly $|A| + |B| = | A \cup B|$. \end{note} \begin{xbox} \begin{example}\hfill \begin{enumerate} \item For all $n \in \mathbb{N}$, $n + \aleph_0 = \aleph_0$. \item $\aleph_0 + \aleph_0 = \aleph_0.$ (\emph{Hint.} Look at odds and evens.) \item $\mathbf{c}+\mathbf{c}=\mathbf{c}.$ \end{enumerate} \end{example} \end{xbox} \begin{xbox} \begin{note} We have not defined cardinal number subtraction! [Why can't we define $\alpha - \beta = |A\backslash B|$, where $B$ is a subset of $A$?] \end{note} \end{xbox} \begin{defn} Let $\alpha$ and $\beta$ be cardinal numbers, and let $A$ and $B$ be (not necessarily disjoint) sets such that $\alpha = |A|$ and $\beta = |B|$. Then $\alpha \cdot \beta = |A \times B|$. \end{defn} \begin{xbox} \begin{note} Cardinal number multiplication is well-defined and generalizes natural number multiplication. \end{note} \end{xbox} \begin{xbox} \begin{example}\hfill \begin{enumerate} \item For all $n \in \mathbb{P}$, $n \cdot \aleph_0 = \aleph_0$. \item $\aleph_0\cdot \aleph_0 = \aleph_0.$ (\emph{Hint.} Recall how $\mathbb{Q}$ was shown to be denumerable.) \item $\mathbf{c} \cdot \mathbf{c}=\mathbf{c}$, which means $\mathbb{R}^2 \sim \mathbb{R}$, and by induction, $\mathbb{R}^n \sim \mathbb{R}$ for all $n \in \mathbb{P}$. After Georg Cantor proved this result in 1877, he famously wrote, ``I see it, but I don't believe it''. To show $\mathbf{c} \cdot \mathbf{c} \leq\mathbf{c}$, we can define an injection $(0, 1) \times (0, 1) \to (0, 1)$ by `shuffling' two decimal expansions: $(0.a_1a_2\dots, 0.b_1b_2\dots) \to 0.a_1b_1a_2b_2\dots$. [How do we take into account the fact that decimal representations are not always unique; for example, $0.5 = 0.49999\dots$? Also, will the resulting map be surjective?] \end{enumerate} \end{example} \end{xbox} \begin{prop} Let $\alpha, \beta$ and $\gamma$ be cardinal numbers. \begin{enumerate} \item Cardinal number addition and multiplication are commutative and associative; cardinal number multiplication distributes over cardinal number addition. \item The cardinal number $0$ is a cardinal additive identity; that is, $\alpha + 0 = 0 + \alpha = \alpha$. \item The cardinal number $1$ is a cardinal multiplicative identity; that is, $\alpha \cdot 1= 1 \cdot \alpha = \alpha$. \item If $\alpha \leq \beta$, then $\alpha + \gamma \leq \beta + \gamma$ and $\alpha \cdot \gamma \leq \beta \cdot \gamma$. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} Let $A, B$ and $C$ be \emph{disjoint} sets such that $\alpha = |A|, \beta = |B|$ and $\gamma= |C|$. \begin{enumerate} \item From elementary logic, we know that the logical connective ``or" is commutative and associative. This implies that $A \cup B = B \cup A$ and $(A\cup B ) \cup C = A \cup (B \cup C)$, which in turn implies that $\alpha + \beta = \beta + \alpha$ and $(\alpha + \beta )+ \gamma = \alpha + (\beta + \gamma)$. Next, the function $f: A \times B \to B \times A$ given by $f\big( (a,b) \big) = (b, a)$ is clearly a bijection and so $\alpha \cdot \beta = \beta \cdot \alpha$. Even more clearly, $g:(A \times B) \times C \to A \times (B \times C)$ given by $g[\big((a, b), c)] = \big(a, (b,c)\big)$ is a bijection and so $(\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma)$. For distributivity, . . . \end{enumerate} \end{proof} \end{xbox} \begin{theorem} Let $\alpha$ and $\beta$ be nonzero cardinal numbers such that at least one of them is infinite. Then $\alpha + \beta = \alpha \cdot \beta = \max \{\alpha, \beta\}$. \end{theorem} \begin{xbox} This remarkable theorem shows that although infinite cardinal number arithmetic has many of the same properties as finite number arithmetic, it can be significantly different. Although the proof of this theorem is beyond the scope of this course, note the supporting evidence provided by .... \end{xbox} \begin{xbox} \begin{example} If $\mathbb{I}$ denotes the set of irrational numbers, then $|\mathbb{I}| = ....$ \end{example} \end{xbox} \begin{notation} If $A$ and $B$ are sets, then $A^B$ denotes the set of all functions $f:B \to A$. \end{notation} \begin{defn} Let $\alpha$ and $\beta$ be cardinal numbers, and let $A$ and $B$ be sets such that $\alpha = |A|$ and $\beta = |B|$. Then $\alpha^\beta = |A^B|$. \end{defn} \begin{xbox} \begin{note} Cardinal number exponentiation is well-defined and generalizes natural number exponentiation. [Careful! This is trickier than showing that cardinal addition and multiplication are well-defined. To illustrate that cardinal number exponentiation generalizes natural number exponentiation, determine how many functions there are from $B = \{ 0, 1, 2 \}$ to $A = \{ a, b, c, d\}$.] \end{note} \end{xbox} \begin{xbox} \begin{example} In cardinal number arithmetic, for all $\alpha \neq 0$, $\alpha^0=\dots$ and $0^\alpha=\dots$. Moreover, $0^0 = \dots$ \end{example} \end{xbox} The following proposition generalizes a well-known result for finite sets. \begin{prop} For any set $A$, $\wp(A) \sim \{0, 1\}^A$. Hence, $|\wp(A)| = 2^{|A|}$. \end{prop} \begin{xbox} \begin{proof} For any subset $C\subseteq A$, the \emph{characteristic function} of $C$, $\chi_C:A \to \{0, 1\}$, is defined by: \[ \chi_C(a)= \begin{cases} 1, &\text {if $a \in C$,}\\ 0, &\text{if $a \notin C$}. \end{cases} \] (\emph{Hint.} Show that the map $\phi: \wp(A) \to \{0, 1\}^A$ given by $\phi(C) = \chi_C$ is a bijection.) \end{proof} \end{xbox} \begin{xbox} \begin{example} $2^{\aleph_0} = \mathbf{c}$. (\emph{Hint.} To show $2^{\aleph_0} \leq \mathbf{c}$, define $f:\wp(\mathbb{P}) \to [0,1]$ as follows. For any $C \in \wp(\mathbb{P})$, by definition $C \subseteq \mathbb{P}$; let $f(C) = 0.c_1 c_2 \dots c_n \dots$ where $c_n = \chi_C(n)$. To show $\mathbf{c} \leq 2^{\aleph_0}$, define $g:\mathbb{R} \to \wp(\mathbb{Q})$ by $g(r)=\{ q \in \mathbb{Q} \, | \, q \leq r \}$.) \end{example} \end{xbox} Although the definition of cardinal number exponentiation is rather strange, it satisfies some familiar properties of natural number exponentiation. \begin{prop} Let $\alpha, \beta$ and $\gamma$ be nonzero cardinal numbers. Then: \begin{enumerate} \item $\alpha^\gamma \cdot \beta^\gamma = (\alpha \cdot \beta)^\gamma $; \item $(\alpha^\beta)^\gamma = \alpha^{\beta \cdot \gamma}$; \item $\alpha^\beta \cdot \alpha^\gamma = \alpha^{\beta + \gamma}$; \item if $\alpha \leq \beta$, then $\alpha^\gamma \leq \beta^\gamma$ and $\gamma^\alpha \leq \gamma^\beta$. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} Let $A, B$ and $C$ be \emph{disjoint} sets such that $\alpha = |A|, \beta = |B|$ and $\gamma= |C|$. To prove (2), we must define a bijection $\phi:(A^B)^C \to A^{B \times C}$. First note that each element $f \in (A^B)^C$ is a function $f:C \to A^B$; that is, for each $c \in C$, $f(c) \equiv f_c$ is a function, $f_c:B \to A$. This in turn means that for each $b \in B$, $f_c(b)$ is an element of $A$. Now, $\phi(f)$ must be an element of $A^{B \times C}$; that is, $\phi(f)$ must be a function $\phi(f): B \times C \to A$. We define this function by setting $[\phi(f)](b, c) = f_c(b) \in A$ for all $(b, c) \in B \times C$. To show that $\phi$ is injective, suppose $g \in (A^B)^C$ and $f \neq g$. If $f$ and $g$ are different functions, then by definition, there exists $\hat{c} \in C$ such that $f(\hat{c}) \neq g(\hat{c})$; thus $f_{\hat{c}}$ and $g_{\hat{c}}$ must be different functions $B \to A$. This in turn means there exists $\hat{b} \in B$ such that $f_{\hat{c}}(\hat{b}) \neq g_{\hat{c}}(\hat{b})$. Then by definition, $[\phi(f)](\hat{b}, \hat{c}) \neq [\phi(g)](\hat{b}, \hat{c})$, so $\phi(f) \neq \phi(g)$ as functions $B \times C \to A$. To show that $\phi$ is surjective, let $h \in A^{B\times C}$; then $h$ is a function $h:B \times C \to A$. Define $k \in (A^B)^C$ by stipulating that for all $c \in C$, $k(c) \equiv k_c$ is the function $B \to A$ given by $k_c(b) = h(b, c)$ for all $b \in B$. Then clearly (!!!) $\phi(k) = h.$ ... Next, we prove the second half of (4). If $\alpha \leq \beta$, then by definition there exists an injection $j:A \to B$. What we must do is find an injection $\psi:C^A \to C^B$. Let $f \in C^A$; that is, $f$ is a function $f:A \to C$. We define $\psi(f) \in C^B$ (that is, $\psi(f):B \to C$) as follows. First, we pick an arbitrary $c_0 \in C$. [What if $C = \emptyset$?] For all $b \in B$ that satisfy $b = j(a)$ for some $a \in A$, set $[\psi(f)] (j(a)) = f(a)$. For all $b \in B$ that are not in the range of $j$, set $[\psi(f)](b) =c_0$. To show that $\psi$ is injective, suppose $f$ and $g$ are different functions $A \to C$. Then there exists $a \in A$ such that $f(a) \neq g(a)$. This implies that $[\psi(f)](j(a)) \neq [\psi(g)](j(a))$, and so $\psi(f) \neq \psi(g)$. \end{proof} \end{xbox} \begin{xbox} \begin{example} $\mathbf{c}^{\aleph_0} = \mathbf{c}$ and $\mathbf{c}^\mathbf{c} = 2^\mathbf{c}$. (\emph{Hint.} Use previous examples/results!) \end{example} \end{xbox} \end{document}