% Prerequisites for M771 set theory, excerpted from book
% Arnold W. Miller  miller@math.wisc.edu

\documentstyle[12pt]{article}
\oddsidemargin 5pt \evensidemargin 5pt \marginparwidth 68pt
\marginparsep 10pt \topmargin 10pt \headheight 10pt
\headsep 15pt \footskip 35pt
\textheight = 625pt  \textwidth 440pt \columnsep 10pt \columnseprule 5pt

\input amssym.def
\input amssym
 
%%%%%%% counters %%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\probno
\newcount\sectorno
\sectorno=0
\def\sector#1{\probno=1\advance\sectorno by 1
 \bigskip\begin{center}{\bf #1}\end{center}}
\def\prob{\par\medskip\noindent
 {\kern -.5in \parbox{.45in}{\the\sectorno .\the\probno}}\advance\probno by 1}
\newtheorem{lemma}{Lemma}

%%%%%%%%%%%% symbols %%%%%%%%%%%%%%
\def\ax #1.{\par\medskip\noindent{\bf #1:}}
\def\blank{\;\tilde{ }\;}   \def\cc{{\frak c}}  \def\conj{\mathop{\wedge}}
\def\disj{\mathop{\vee}}    \def\dom{{\rm dom}}  \def\dotminus{\dot{-}}
\def\fama{{\cal A}}         \def\famc{{\cal C}}   \def\famf{{\cal F}}
\def\HFin{(HF,\in)}         \def\implies{\rightarrow} \def\isom{\simeq}
\def\nn{{\Bbb N}}           \def\nor{\oplus}      \def\ord{{\bf ORD }}
\def\qq{{\Bbb Q}}          \def\res{\upharpoonright}
\def\rmand{{\mbox{ and }}} \def\rmiff{{\mbox{ iff }}}
\def\rmor{{\mbox{ or }}}   \def\rr{{\Bbb R}}       \def\ss{{\cal S}}
\def\zfc{{\rm ZFC}}        \def\zz{{\Bbb Z}}
\def\com#1{}         \def\dex#1{{\it #1}}       \def\sdex#1{} %   dummies


\begin{document}
 \begin{flushright}
  A.Miller\\
  M771\\
  Jan 1998\\
  http://www.math.wisc.edu/$\sim$miller/m771 \\
 \end{flushright}


\begin{center}
 A selected list of books about set theory
\end{center}

\noindent Beginning
\par  Roitman, Introduction to modern set theory
\par  Vaught, Set theory, an introduction
\par  Monk, Introduction to set theory
\par  Moschovakis, Notes on set theory
\par  Just and Weese, Discovering modern set theory I, II
\par  Hausdorff, Set theory

\noindent Intermediate
\par  Kunen, Set theory
\par  Jech, Set theory
\par  Handbook of mathematical logic, chapter on set theory
\par  Ciesielski, Set theory for the working mathematician

\noindent Advanced
\par  Bartoszynski and Judah, Set theory, on the structure of the real line
\par  Kanamori, The higher infinite
\par  Shelah, Proper forcing
\par  Shelah, Cardinal arithmetic
\par  Devlin, Constructibility
\par  Jech, The axiom of choice
\par  Fremlin, Consequences of Martin's axiom

\bigskip

\begin{center}
  Prerequisites
\end{center}

The prerequisite for this course is Math 770, Introduction to
Mathematical Logic.
Usually the following topics are among those covered in 770:

Naive set Theory: cardinal and ordinal arithmetic,
axioms of Zermelo-Fraenkel set theory with the axiom of choice.

First order logic: formulas, sentences, theories,
structures, models, satisfaction, the compactness, completeness and
incompleteness theorems.

What follows is excerpted from a manuscript which can be found on
my home page.

\newpage

\sector{The Axioms of Set Theory}

   Here are some.  The whole system is known as \dex{ZF} for Zermelo-Fraenkel
   set theory.  When the axiom of choice is included it is denoted
   \dex{ZFC}.  It was originally developed by Zermelo to
   make precise what he meant when he said that the
   well-ordering principal follows from the
   axiom of choice.   Latter Fraenkel added the axiom of replacement.
   Another interesting system is GBN which is G\"{o}del-Bernays-von Neumann
   set theory.

\medskip

\ax Empty Set. $$ \exists x\, \forall y ( y \notin x )$$
The empty set is usually written $\emptyset$. \sdex{$?emptyset$}

\ax Extensionality.
 $$ \forall x \forall y ( x = y \iff \forall z ( z \in x \iff z\in y)) $$
Hence there is only one empty set.

\ax Pairing. $$ \forall x \forall y \exists z \forall u
( u \in z \iff u = x \disj u = y ) $$
We usually write $z = \{ x,y \}$. \sdex{$z = ?{ x,y ?}$}

\ax Union. $$ \forall x\, \exists y\, ( \forall z ( z \in y \iff
(\exists u\, u \in x \conj z \in u ))$$
We usually write $y = \cup x$. \sdex{$y = \cup x $}  $A \cup B$
abbreviates  $ \cup \{ A,B \}$.  \sdex{$A \cup B$}
$z \subseteq x $  is an abbreviation
for $ \forall u \, (u\in z \implies u\in x)$. \sdex{$z ?subseteq x $}

\ax Power Set. $$ \forall x \, \exists y \, \forall z
( z \in y \iff z \subseteq x ) $$
We usually write $y = P(x)$. \sdex{$y = P(x)$}
 For any set x , $x + 1 = x \cup \{x\}$. \sdex{$x + 1 = x ?cup ?{x?}$}

\ax Infinity. $$\exists y \, (\emptyset\in y \conj \forall x
( x \in y \implies x + 1 \in y )) $$
The smallest such y is denoted $\omega$, \sdex{$?omega$} so
$\omega=\{0,1,2,\ldots\}$.

\ax Comprehension Scheme.
$$ \forall z \exists y \forall x [ x \in y \iff
                                 ( x \in z \conj \theta(x) ) ]$$
The comprehension axiom is being invoked when we say given $z$ let
$$y = \{ x \in z : \theta(x) \}.$$ \sdex{$y = ?{ x ?in z : ?theta(x) ?}$}
The formula $\theta$ may refer to $z$ and
to other sets, but not to $y$.  In general given a formula $\theta(x)$
the family $\{x:\theta(x)\}$ is referred to as a \dex{class}, it may not
be a set.    For example, the class of all sets is
$${\bf V}=\{x:x=x\}.$$ \sdex{$V$}
Classes that are not sets are referred to as
\dex{proper classes}.
Every set $a$ is a class, since the formula
``$x\in a$'' defines it.
The comprehension axioms say that the intersection
of a class and a set is a set.  We use {\bf boldface} characters to
refer to classes.

\bigskip

\prob Define  $X\cap Y$,
$X\setminus Y$, and
$\bigcap X$ and show they exist. \sdex{$X?cap Y$}
\sdex{$X?setminus Y$}  \sdex{$?bigcap X$}

\prob The \dex{ordered pair} is defined by
\sdex{$?langle x,y?rangle$}
$${\langle x,y\rangle =\{\{x\},\{x,y\}\}}.$$
Show it exists.
Show the $\langle x,y\rangle = \langle u,v\rangle$ iff $x = u$ and $y = v$.

\prob The \dex{cartesian product} is defined by
\sdex{$X ?times Y$}
$$ X \times Y =\{ \langle x,y\rangle : x \in X \mbox{ and } y \in Y\}.$$
 Show it exists.

\prob A function is identified with its graph. For any sets $X$ and $Y$ we let
$Y^X$ be the set of all functions with domain $X$ and
range $Y$.  \sdex{$Y^X$} Show this
set exists.

\prob Given a function $f:A\mapsto B$ and set $C\subseteq A$ the
\dex{restriction} of $f$ to $C$, written $f\res C$
is the function
with domain $C$
and equal to $f$ everywhere in $C$.  \sdex{$f?res C$} Show that it exists.
$f^{\prime\prime}C$   is the set
of all elements of $B$ that are in the image of  $C$.
\sdex{$f^{\prime\prime}C$} Show that it exists.

\prob Prove $\omega$ exists (i.e.
that there does exist a smallest such $y$).
Prove for any formula $\theta(x)$ if $\theta(0)$ and
$\forall x\in\omega (\theta(x)\implies \theta(x+1))$, then
$\forall x\in\omega\;\theta(x)$.

\prob Suppose $G:Z\to Z$.
Show that for any $x\in Z$ there exists a unique $f:\omega\to Z$
such that $f(0)=x$ and for all $n\in\omega\;\; f(n+1)=G(f(n))$.

\prob Let $(V,E)$ be a graph.  Informally, two vertices in any graph
are \dex{connected} iff (either they are the same or)  there is a
finite path using the edges of the graph connecting one to the other.
Use the preceding problem to formally define and prove that
the relation $x$ is connected to $y$, written $x\sim y$,
exists and is an equivalence relation on $V$.
Equivalence classes of $\sim$ are called the
\dex{components} of the graph.

\prob Let $A$ and $B$ be disjoint sets and $f:A\to B$ and $g:B\to A$
be one-to-one functions.  Consider the \dex{bipartite graph} $V$ which
has vertices $A\cup B$ and edges given by the union of the graphs of
$f$ and $g$, i.e., there is an edge between $a\in A$ and $b\in B$ iff
either $f(a)=b$ or $g(b)=a$.
Describe what the finite components of $V$ must look like as a
subgraph of $V$.
Describe the infinite components of $V$.


\prob Define $| X | = | Y |$  iff
there is a one-to-one onto map from $X$ to $Y$.  \sdex{$| X | = | Y |$}
We say $X$ and $Y$ have the same cardinality.
Define   ${| X | \leq | Y |}$ iff
there is a one-to-one map
from $X$ to $Y$.  \sdex{$| X | ?leq | Y |$}
Define ${| X | < |Y |}$ iff $ | X | \leq | Y |$ and $ | X | \not= | Y |$.
\sdex{$| X | < |Y |$}
(Cantor-Shr\"oder-Bernstein)
Show that if $| A | \leq | B |$ and $| B | \leq | A |$ then
$| A | = | B |$.

\bigskip

\prob Show that $|A|\leq |A|$.
Show that if $| A | \leq | B |$ and $| B | \leq | C |$ then
$| A | \leq | C |$.

\prob Show that
$|P(X)| = |\{ 0,1\}^X|$.

\prob (Cantor) Show that  $| X | < | P(X) |$.

\prob Show that the class of sets, ${\bf V}$, is not a set.

\prob Show that $|A \times ( B \times C )| = | ( A \times B ) \times C |$.

\prob Show that  $| A^{ B \times C}| =  | {( A^B)}^C |$.

\prob Show that if there is a function $f:A\mapsto B$ that is onto,
then $|B|\leq |A|$.
\footnote{This requires the axiom of choice. It is open if it is equivalent
to AC.}

\bigskip

A set is finite iff it can be put into one-to-one correspondence with
an element of $\omega$
A set is \dex{countable} iff it is either finite or of the same cardinality
as $\omega$. A set is \dex{uncountable} iff it is not countable.
${{\rr}}$   is the set of real numbers and we use
$\cc = |\rr|$
to denote its cardinality which is also called
the cardinality of the continuum. \sdex{${?rr}$} \sdex{$?cc$}
Below, you may use whatever set theoretic
definitions of the integers, rationals and real numbers that you know.
For example, you may regard the reals as either Dedekind cuts in
the rationals, equivalences classes of Cauchy sequences of rationals,
infinitely long decimals, or ?points on a line.

\bigskip

\prob Show that the set of integers $\zz$
is countable.\sdex{${?zz}$}

\prob Show that the set of odd positive integers is countable.

\prob Show that the set of points in the plane with integer coordinates is
   countable.

\prob Show that the countable union of countable sets is countable.
\footnote{Do you think you needed to use the Axiom of Choice?}

\prob
For any set $X$ let $[X]^{<\omega}$
be the finite subsets of $X$.  \sdex{$[X]^{<?omega}$}
Show that the set of finite subsets of $\omega$, which is
written $[\omega]^{<\omega}$,
is countable.  \sdex{$[?omega]^{<?omega}$}

\prob Show that if there are only countably many atomic sentences then the
set of all propositional sentences is countable.

\prob Show that the set of rationals $\qq$
is countable. \sdex{${?qq}$}

{Remark:
A clever mapping of the positive rationals to the positive
integers is ${p_1^{k_1}\cdots p_n^{k_n}}\over {q_1^{l_1}\cdots q_m^{l_m}}$
is mapped to ${p_1^{2k_1}\cdots p_n^{2k_n}
\cdot q_1^{2l_1+1}\cdots q_m^{2l_m+1}}$.}

\prob  A number is \dex{algebraic} iff it is the root of some polynomial with
rational coefficients. Show that the set of algebraic numbers is countable.

\prob Show that any nontrivial interval in $\rr$ has cardinality $\cc$.

\prob Show that $P(\omega)$ has cardinality $\cc$.

\prob Show that the set of all infinite subsets of $\omega$, which is
written $[\omega]^{\omega}$,
has cardinality $\cc$. \sdex{$[?omega]^{?omega}$}

\prob Show that the cardinality of $\rr \times \rr$ is $\cc$.

\prob For any set $X$ let
$[X]^{\omega}$
be the countably infinite subsets of $X$.\sdex{$[X]^{?omega}$}
Show that  $|\rr^{\omega}|=| [\rr]^{\omega}|= \cc$.
\footnote{See previous footnote.}
\com {
  $| [\rr]^{\omega}|= \cc$ requires AC. If every set of reals has
BP then there cannot be a map $g:\rr^{\omega}\mapsto \rr$ such
that $g(\langle x_n:n<\omega\rangle)=g(\langle y_n:n<\omega\rangle)$
iff $\{x_n:n<\omega\}=\{y_n:n<\omega\}$. Also can prove that
such a map gives a 1-1 map of $\omega_1$ into $\rr$, i.e.
$x_{\alpha}=f\{x_\beta:\beta<\alpha\}$ after starting with
$\{x_n:n<\omega\}$ not in the range of $f$.
}
\prob Show that the cardinality of the set of open subsets of $\rr$
is $\cc$.

\prob Show that the set of all continuous functions from $\rr$ to $\rr$
 has size $\cc$.

\prob Show that $\omega^{\omega}$  has cardinality $\cc$.

\sector{Wellorderings}

 A linear order $( L, \leq)$ is a \dex{wellorder} iff for every nonempty
 $X\subseteq L$
         there exists $x \in X$ such that for every $y \in X$
        $x \leq y$   ($x$ is the minimal element of $X$).
        For an ordering $\leq$ we use $<$ to refer to the strict ordering, i.e
       $x < y$ iff $x \leq y $ and not $x \not= y$. We use $>$ to refer to the
        converse  order, i.e. $x > y$ iff $y < x$.

\bigskip


\prob Prove:
   Let  $( L, \leq )$ be any well-ordering and $f: L \to L$ an
    increasing function
   ($\forall x,y \in L\;(  x < y \implies f(x) < f(y))$). Then
    for every $x$ in $L$ $x \leq f(x)$.

\prob For two binary relations $R$ on $A$ and $S$ on $B$  we write
        $(A,R)\isom (B,S)$
         iff there exists a one-to-one onto map
        $f:A\to B$
        such that

\centerline{for every $x,y$ in $A$ ($xRy$ iff $f(x)Sf(y)$).}

\noindent  Such a map is called an
\dex{isomorphism}.  \sdex{$(A,R)?isom (B,S)$}
 If $(L_1,\leq_1 )$ and $(L_2,\leq_2)$ are well-orders and
$(L_1,\leq_1)\isom (L_2,\leq_2)$ then
show the isomorphism is unique.

\prob Let $(L,\leq)$ be a wellorder and for any $a \in L$ let
$L_a = \{ c \in L : c < a \}$.  Show that
 $( L, \leq )$ is not isomorphic to $( L_a, \leq )$ for any $a \in L$.

\prob (Cantor) Show that for any two wellorders  exactly one
of the following occurs:
they are isomorphic, the first is isomorphic to an initial segment
of the second, or the second is isomorphic to an initial segment
of the first.

{Hint: Let $(L,\leq)$ and $(K,\leq^\prime)$ be two wellorders.
Let $$G=\{\langle a,b\rangle : ( L_a,\leq ) \isom ( K_b,\leq ^\prime )\}$$
Show that $G$ is the graph of an order preserving bijection whose domain
is all of $L$ or whose range is all of $K$.}


\sector{Axiom of Choice}

\bigskip
\noindent (AC)  \dex{Axiom of Choice}:  For every family $F$ of nonempty sets
   there exists a choice function, i.e. a function $f$
   with domain F such that for every $x$ in $F$,  $f(x) \in x$.

\bigskip
\noindent (WO) \dex{Well-ordering Principle} : Every nonempty set
   can be well ordered.

\bigskip
\noindent (TL) \dex{Tuckey's Lemma}: Every family of sets
   with finite character has a maximal
   element.   A family of sets F has finite character iff for every set X,
    $X\in F$   iff for every finite $Y\subseteq X$, $Y\in F$.
\bigskip
\noindent (MP)  \dex{Maximality Principle}:  Every family of sets closed
 under the unions of chains has a maximal member.

\bigskip
\noindent (ZL) \dex{Zorn's Lemma}:  Every family of sets contains a
 maximal chain.


\par\bigskip

\prob Show that  ZL implies MP.

\prob Show that  MP implies TL.

\prob Show that  TL implies AC.

\prob (Zermelo) Show that  AC implies WO.

{Hint: Given $X$  use AC to get a function
$f:P(X)\mapsto X$  such that $f(A) \in X\setminus A$
for all $A$ a proper subset of $X$.  Call a well ordering
$(L,\leq)$ respectful iff $L\subseteq X$ and for every
$a\in L\; f(L_a)=a$.
Show that the union of all respectful well orderings is a
well ordering of $X$. }

\prob  Given a nonempty family $\famf$ let $<$ be a
strict well-ordering of $\famf$.   Say that a chain $\famc\subseteq\famf$
is greedy
iff for every $a\in \famf$ if
 $$\{ b\in \famc : b < a \} \cup\{a\}$$
is a chain, then either
$a\in \famc$ or $b<a$ for every $b\in \famc$.
Show that the union of all greedy chains is a maximal chain.
Conclude that  WO implies ZL.









\sector{Ordinals}

A set $X$ is \dex{transitive} iff $\forall x \in X\,( x \subseteq X)$.
A set $\alpha$ is an \dex{ordinal} iff it is transitive and strictly
well ordered by the membership relation
(define $x\leq y$ iff $x\in y$ or $x=y$, then
$(\alpha,\leq)$ is a wellordering).  We also include the empty
set as an ordinal.
For ordinals $\alpha$ and $\beta$ we write $\alpha<\beta$ for
$\alpha \in \beta$.
The first infinite ordinal is written $\omega$. \sdex{$\omega$}
 We usually write
$$ 0 = \emptyset, 1 =\{\emptyset\}, 2 =\{\emptyset,\{\emptyset\}\}, \ldots,
n = \{ 0,1,\ldots,n-1\},\cdots, \omega =\{ 0,1,2,\ldots\} $$

\prob Show: If $\alpha$ is an ordinal then so is $\alpha + 1$.
(Remember $\alpha=\alpha\cup\{\alpha\}$.) Such
   ordinals are called \dex{successor ordinals}. Ordinals that are not
   successors are called \dex{limit ordinals}.

\prob Show: If $\alpha$ is an ordinal and $\beta < \alpha$, then $\beta$ is
 an ordinal and
$\beta \subseteq \alpha$ and $\beta=\{\gamma \in \alpha: \gamma \in \beta\}$.

\ax Axiom of Regularity.
$$ \forall x \, x \not= \emptyset \implies \exists y ( y\in x \conj
\neg \exists z\, (z \in y \conj z \in x ))$$

Another way to say this is that the binary relation
$R=\{(u,v)\in x\times x: u\in v\}$ has a minimal element, i.e.,
there exist $z$ such that for every $y\in x$ it is not the
case that $zRy$.  Note: a minimal element is not the same
as a least element.

\prob Show $ \alpha$ is an ordinal iff $\alpha$ is
   transitive and linearly ordered by the membership relation.

\prob For any ordinals $\alpha$ and $\beta$ show that
$\alpha \cap \beta  = \alpha$  or
$\alpha \cap \beta = \beta $. Show any two ordinals are comparable,
i.e., for any two distinct ordinals $\alpha$ and $\beta$ either
$\alpha\in\beta$ or $\beta\in\alpha$.

\prob The union of set $A$ of ordinals is an ordinal, and is $sup(A)$.

\prob Show that the intersection of a nonempty set $A$ of ordinals
is the least
element of $A$, written $inf(A)$.
Hence any nonempty set of  ordinals has a least element.

\prob Prove transfinite induction:  Suppose $\phi(0)$ and
$\forall \alpha\in\ord$ if $\forall \beta<\alpha\;  \phi(\beta)$,
then $\phi(\alpha)$.  Then $\forall\alpha\in\ord\; \phi(\alpha)$.


\ax Replacement Scheme Axioms.
$$\forall a\;(  [\forall x\in a \exists  ! y \,\psi (x,y)] \implies \exists b
\forall x \in a \exists y \in b \,\, \psi (x,y))$$

The formula
$\psi$ may refer to $a$ and to other sets but not to $b$.
Replacement says that for any function that is a class
the image of a set is a set. If ${\bf F}$
is a function, then for any set $a$ there exists a set $b$ such that
for every $x\in a$ there exists a $y\in b$ such that ${\bf F}(x)=y$.

\prob (von Neumann) Let $(L,\leq)$ be any well-ordering.
Show that the following is a set:
$$\{(x,\alpha): x\in L,\alpha\in\ord, \rmand (L_x,\leq)\isom \alpha\}.$$
Show that every well ordered set is isomorphic to a unique ordinal.

\bigskip
Let \ord denote the class of all ordinals. \sdex{$?ord$}
\par\noindent \dex{Transfinite Recursion}:
\par   If {\bf F} is any function defined on all sets then there exists a
            unique function {\bf G} with domain \ord such that for every
            $\alpha$ in \ord  ${\bf G}(\alpha) =
            {\bf F}( {\bf G}\res\alpha)$.

This is also referred to as a transfinite construction of ${\bf G}$.

\par\bigskip

\prob Suppose ${\bf F}:{\bf V}\to {\bf V}$, i.e., a class function.
Define g (an ordinary set function) to be a good guess iff
$\dom(g)=\alpha\in \ord$, $g(0)={\bf F}(\emptyset)$, and
$g(\beta)={\bf F}(g\res\beta)$ for every $\beta<\alpha$.
Show that if $g$ is a good guess, then $g\res\beta$ is good
guess for any $\beta<\alpha$.

\prob Show that if $g$ and $g^\prime$ are good guesses with the
same domain, then $g=g^\prime$.

\prob Show that for every $\alpha\in \ord$ there exists
a (necessarily unique) good guess $g$ with domain $\alpha$.

\prob (Fraenkel) Prove transfinite recursion.

\prob Explain the proof of WO implies ZL in terms of a
transfinite construction.

\bigskip
For an example, consider the definition of $V_{\alpha}$ for every
ordinal $\alpha$. \sdex{$V_{\alpha}$}
 Let $V_0=\emptyset$,
$V_{\alpha+1}=P(V_{\alpha})$ (power set) for successor
ordinals, and for
limit ordinals $V_{\lambda}=\cup_{\beta<\lambda} V_{\beta}$.
Thus if we define ${\bf F}$ as follows:
$${\bf F}(x)=\left\{
\begin{array}{ll}
    P(x(\alpha))  & \mbox{if $x$ is a function
                     with domain $\alpha+1\in\ord$} \\
    \bigcup_{\alpha<\lambda} x(\alpha)
                  & \mbox{if $x$ is a function
                     with domain limit ordinal $\lambda$} \\
    P(\emptyset)  & \mbox{if $x=\emptyset$} \\
    -\pi          & \mbox{otherwise}\\
\end{array}
\right.$$
then ${\bf G}(\alpha)=V_\alpha$.


\prob Show that if $\alpha\leq\beta$, then $V_\alpha\subseteq V_{\beta}$
and if $\alpha<\beta$, then $V_{\alpha}\in V_\beta$.
Show that each $V_{\alpha}$ is transitive.

\prob Show that every set is included in a transitive set.
Show that for every transitive set $x$ there exists an ordinal
$\alpha$ such that $x\in V_{\alpha}$, i.e.,
${\bf V}=\cup_{\alpha\in \ord}V_{\alpha}$.

\par\bigskip
  \dex{Ordinal arithmetic}: ($\alpha,\beta$ are ordinals, and
$\lambda$ is a limit ordinal.)

\medskip
Addition:

$\alpha + 0 = \alpha$

$\alpha +(\beta+1)=(\alpha+\beta)+1$

$\alpha+\lambda=sup \{ \alpha + \beta : \beta < \lambda \}$

\medskip
Multiplication:

$\alpha   0 =  0$

$ \alpha  ( \beta + 1)  =  (\alpha   \beta) + \alpha$

$\alpha\lambda=  sup \{ \alpha   \beta : \beta < \lambda \}$

\medskip
Exponentiation:

$ \alpha^0=1$

$\alpha^{\beta+1}=\alpha^\beta\alpha$

$\alpha^{\lambda}=sup \{ \alpha^{\beta}: \beta < \lambda \}$

\medskip
 So for example the addition function
$+ : \ord \times \ord \mapsto
\ord$ exists by transfinite recursion.
For each $\alpha \in$ \ord define a function ${\bf F}_{\alpha}$
on all sets as follows:

${\bf F}_{\alpha}(g)=g(\beta)+1$ if
 $g$ is a map with domain an ordinal $\beta+1$,

${\bf F}_{\alpha}(g)= sup\{g(\gamma): \gamma < \lambda\}$ if
 $g$ is a map with domain a limit  ordinal $\lambda$, and

${\bf F}_{\alpha}(g)=\alpha$ otherwise.

\noindent Hence for each $\alpha$ we have a unique
${\bf G}_{\alpha}: \ord \mapsto \ord$
which will exactly be
${\bf G}_{\alpha}(\beta) = \alpha + \beta$. Since each ${\bf G}_{\alpha}$ is
 unique we have defined  the function $+$ on all pairs of ordinals.

Note that more intuitively $\alpha+\beta$ is the unique ordinal isomorphic
to the well-order $(\{0\}\times\alpha)\cup (\{1\}\times\beta)$ ordered
lexicographically.  Similarly $\alpha\cdot\beta$ is the unique ordinal
isomorphic to the well-order $\beta\times\alpha$ ordered
lexicographically.  Exponentiation is much harder to describe.

\bigskip

\prob Show that $\alpha + (\beta +\gamma)=(\alpha + \beta) +\gamma$.

\prob For any ordinals $\alpha$ and $\beta>0$ show there exists
unique ordinals
 $\gamma$ and $\delta$ such that
     $\alpha =  \beta   \gamma   +  \delta$ and $\delta<\beta$.


\prob Show for any $\beta > 0$ there exists unique ordinals
    $\gamma_1,\ldots,\gamma_n, d_1,\ldots,d_n$  such that
    $\gamma_1 >\gamma_2 > \cdots >\gamma_n$ ;
    $ 0 <  d_1,d_2,\ldots,d_n < \omega$ and
$$ \beta = \omega^{\gamma_1}d_1 + \omega^{ \gamma_2}d_2 + \ldots +
       \omega^{ \gamma_n}d_n $$
This is called \dex{Cantor normal form}.


\sector{Cardinal Arithmetic}

An ordinal $\kappa$ is a \dex{cardinal} iff for every $\alpha < \kappa$,
$|\alpha| < | \kappa|$.
The cardinality of a set A is the least cardinal $\kappa$,
$|A|=|\kappa|$ and we write $|A|=\kappa$.
The $\alpha^{th}$ uncountable cardinal is written either
$\aleph_{\alpha}$
or $\omega_{\alpha}$.  \sdex{$\aleph_{\alpha}$}
\sdex{$\omega_{\alpha}$}

\bigskip

\prob Show that for any ordinal $\alpha$ the cardinal
$\aleph_\alpha$ exists.

\prob Is there a cardinal such that $\aleph_{\alpha}=\alpha$ ?

\bigskip

For cardinals $\kappa$ and $\gamma$  we define  $\kappa \gamma$
   to be the cardinality of the
cross product and $\kappa +\gamma$ to be the cardinality of the union
 of $A$ and $B$ where $A$ and $B$ are disjoint and
 $|A|=\kappa$ and $|B|=\gamma$.  \sdex{$\kappa \gamma$}
 \sdex{$\kappa +\gamma$}

\bigskip

\prob Let $\kappa$ be an infinite cardinal.
Define the \dex{lexicographical order} $\leq_l$ on  $\kappa \times \kappa$
by $(x,y) \leq_l  (u,v)$ iff $x<u$ or $(x=u$ and $y\leq v)$.
Define $ \leq^{\prime}$ on $\kappa \times \kappa$ by
$(x,y) \leq^{\prime}  (u,v)$ iff
$max\{x,y\} < max\{u,v\}$  or
$[(max\{x,y\} = max\{u,v\}$ and $(x,y)\leq_l (u,v)]$.
Show that  $( \kappa, \leq ) \isom ( \kappa \times \kappa , \leq^{\prime})$.

\prob Show that for infinite cardinals $\kappa$ and $\gamma$,
  $\kappa +\gamma = \kappa \gamma  = max \{ \kappa,\gamma\}$.

\prob Show that for any infinite cardinal $\kappa$ the union of $\kappa$
 many sets of cardinality $\kappa$ has cardinality $\kappa$.




\bigskip

The \dex{cofinality} of an infinite limit ordinal $\beta$,
$cf(\beta)$,  \sdex{$cf(?beta)$}
 is the least $\alpha\leq\beta$
 such that there
is a map $f:\alpha\to\beta$ whose range is unbounded in $\beta$.

\bigskip

\prob For $\lambda$ a limit ordinal show the following
are all equivalent:

a. $\alpha$ is the minimum ordinal such that
$\exists X \subseteq \lambda$ unbounded in $\lambda$
such that $(X,\leq) \isom (\alpha,\leq)$.

b. $\alpha$ is the minimum ordinal such that
$\exists f:\alpha\to\lambda$ such that
f is one-to-one,  order preserving, and the range of $f$ is
cofinal (unbounded) in $\lambda$.

c.  $cf(\lambda)=\alpha$

\prob For $\kappa$ an infinite cardinal show that
$cf(\kappa)=\alpha$ iff $\alpha$ is the minimum cardinal such that
$\kappa$ is the union of $\alpha$ many sets of cardinality less
than $\kappa$.

\prob Let $\alpha$ and $\beta$ be limit ordinals and suppose $f:\alpha\to
\beta$ is strictly increasing and cofinal in $\beta$.
Show $cf(\alpha)=cf(\beta)$.

\prob $\kappa$ is \dex{regular} iff $cf(\kappa)=\kappa$.
$\kappa$ is \dex{singular} iff $cf(\kappa)<\kappa$.
Show that for any limit ordinal $\beta$,
$cf(\beta)$ is a regular cardinal.

\prob
$\kappa^+$ is the least cardinal greater than $\kappa$. \sdex{$\kappa^+$}
Show that for any infinite cardinal $\kappa$ ,  $\kappa^+$ is a
regular cardinal.

\prob For $\alpha$ a limit ordinal show that
$cf(\aleph_\alpha)=cf(\alpha)$.

\bigskip

$\kappa^{\gamma}$  is the set of all functions from $\gamma$
   to $\kappa$, but we often use it to denote its own cardinality.
   \sdex{$\kappa^{\gamma}$}
  $\kappa^{<\gamma}$ is  $\cup\{\kappa^{\alpha}: \alpha < \gamma\}$,
  but we often use it to denote its own cardinality, i.e.,
  $\kappa^{<\gamma}=|\kappa^{<\gamma}|$. \sdex{$\kappa^{<\gamma}$}
{\bf Note in the section all exponentiation is cardinal exponentiation.}

\bigskip

\prob Show that $|\kappa^{<\omega}|=|[\kappa]^{<\omega}|=\kappa$ for any
infinite cardinal $ \kappa$. $[\kappa]^{<\omega}$ is the set
of finite subsets of $\kappa$. \sdex{$[\kappa]^{<\omega}$}

\prob Show that $\aleph_{\omega} <  \aleph_{\omega}^{\omega}$. Show
that for any cardinal $\kappa$, $\kappa < \kappa^{cf(\kappa)}$.

\prob (K\"{o}nig) Show that $cf(2^{\kappa})>\kappa$.



\end{document}