Math 220C, Mathematical Logic and Set Theory.
Instructor: Itay Neeman.
Office: MS 6334.
Email:
Phone: 7945317.
Office hours: MW 3:00 to 3:50pm and by appointment.
Time and Place: MW 4:00 to 5:40pm, in MS 5117.
Text: Lecture notes will be distributed in class.
Grading: The final grade will be based on homework (roughly 40%),
and a final exam (roughly 60%). Homework will be due every Friday by the end
of the day, preferably submitted as PDF by email.
Homework exercises (all due by the end of the day Friday):
Assignment 1, due Friday 4/13: Exercises 6.4, 6.5, 6.6, 6.7, 6.8, 6.9,
and 6.11 in the notes. (The exercises are at the end of the chapter,
starting page 301.)
Assignment 2, due Friday 4/20:
 Exercise 6.14. (The explanation of what it means to be a successor there is
wrong. Use the right one.)
 Exercise 6.15.
 Exercise 6.16, and prove in addition that if $x$ is an ordinal
and $y\in x$ then $y$ is an ordinal.
 Prove that any two ordinals are comparable, meaning that for any ordinals
$\alpha$ and $\beta$, either $\alpha\in\beta$, or $\alpha=\beta$, or
$\beta\in\alpha$.
 Exercises 6.26. The uniqueness part you should prove only in
the case of wellorders. (For wellfounded relations in general it fails
with the definition of tightness in the notes.)
 Prove that for every wellorder $r$ there is a unique ordinal
$\gamma$ so that $r$ is isomorphic to $(\gamma;\in)$. This
ordinal is called the ordertype of $\gamma$ denoted $ot(\gamma)$.
 Exercise 6.20.
Assignment 3, due Friday 4/27: Exercises 6.19, 6.21, 6.22,
6.23, 6.24, 6.25.
Assignment 4, due Sunday 5/6: Exercises 6.33 and 6.36. In 6.33, ZF stands
for the axioms of ZF except Foundation and Powerset. When answering the
question you should work in ZFFoundation+"the union countably many countable
sets is countable". (This final statement is a weak consequence
of the axiom of choice.)
Assignment 5, due Friday 5/11: Exercises 6.43, 6.46, 6.52, and

Prove that for every ordinal $\alpha$, $\alpha\in V_{\alpha+1}$.

(Uses AC.)
For cardinals $\lambda\leq\kappa$ let ${\mathcal P}_\lambda(\kappa)$ denote
the set $\{x\subseteq\kappa  card(x)=\lambda\}$. Prove, for $\kappa$ infinite,
that ${\mathcal P}_\lambda(\kappa)$ is equinumerous with $\kappa^\lambda$.

(Uses AC.)
Let $a_n$, $n\in\omega$, be a sequence of sets. Suppose that for each $n$,
$a_n\subseteq a_{n+1}$ and $card(a_{n+1}) > card(a_n)$. Let
$a=\bigcup_{n\in\omega} a_n$. Prove that $card(a^\omega) > card(a)$.
Assignment 6, due Friday 5/18:

For a set $x$, let ${\mathcal P}_{WO}(x)$ be the set of all
$z\subseteq x$ so that $z$ can be wellordered. (Assuming the axiom of choice,
this is simply the powerset of $x$. Without the axiom of choice,
${\mathcal P}_{WO}(x)$ may be smaller than the full powerset of $x$.)
Prove, without using the axiom of choice, that ${\mathcal P}_{WO}(x)$ does
not inject into $x$.

(Uses AC.) The cofinality of a limit ordinal $\alpha$,
denoted $cof(\alpha)$, is the least
$\kappa$ so that there is $f\colon \kappa\rightarrow \alpha$ which is
unbounded in $\alpha$. (It is easy to check that $cof(\alpha)$ is a cardinal.)
Prove that for every infinite cardinal $\kappa$, $\kappa^{cof(\kappa)} > \kappa$.
It may be helpful to consider the case that $cof(\kappa)=\omega$ first, as
this case reduces to a previous homework assignment.

(Uses AC) A cardinal $\kappa$ is regular if $cof(\kappa)=\kappa$.
Prove that every infinite successor cardinal is regular.

Prove that for every infinite ordinal $\alpha$, the cardinality of $L_\alpha$
is equal to the cardinality of $\alpha$.

$C\subseteq\kappa$ is club in $\kappa$ if it is unbouned in $\kappa$,
and every $\alpha < \kappa$ which is a limit point of $C$ belongs to $C$.

Prove that if $cof(\kappa) > \omega$ then the intersection of any two clubs in
$\kappa$ is itself club in $\kappa$.

Suppose $\kappa$ is regular and
uncountable. Let $f\colon \kappa\rightarrow\kappa$. Prove that the set
$\{\alpha < \kappa  f''\alpha\subseteq\alpha\}$ is club in $\kappa$.

Question 2 in the Fall 2003 qualifying exam.
Assignment 7, due Friday 5/25:

Let $\kappa > \omega$ be regular. Prove that $L_\kappa$ satisfies ZFPowerset.

(Uses AC.) Question 6 in the Winter 2004 qualifying exam.

Question 7 in the Winter 2004 qualifying exam. $\omega_1$ in the question
refers to $(\omega_1)^L$, the first ordinal which is uncountable in $L$.

Let $M\subseteq WF$ be transitive and satisfy (enough of) ZFPowerset.
Prove that wellfoundedness is absolute for $M$. Precisely, prove that
the formula `$r$ is a wellfounded relation' is absolute for $M$.

Exercise 6.53.

Exercise 6.54.

Exercise 7.8.
Assignment 8, due Friday 6/1:

Question 3 in the Winter 2004 qualifying exam.

Let $\kappa > \omega$ be regular. Let $\delta < \kappa$ and let $C_\xi$
($\xi < \delta$) be a collection of $\delta$ clubs in $\kappa$. Prove
that $\bigcap_{\xi < \delta} C_\xi$ is club in $\kappa$.

Let $\kappa > \omega$ be regular. Let $C_\xi$ ($\xi < \kappa$) be clubs
in $\kappa$. Prove that the set $\{\alpha < \kappa  (\forall \xi < \alpha)
\alpha\in C_\xi\}$ is club in $\kappa$. This set is called the diagonal
intersection of the clubs $C_\xi$.

Let $\kappa > \omega$ be regular, and let $S\subseteq\kappa$ be stationary.
Let $f : S\rightarrow\kappa$ be a pressing down function, meaning
that for all $\alpha\in S$, $f(\alpha) < \alpha$. Prove that there is a
stationary set $\bar{S}\subseteq S$ so that $f$ is constant on $\bar{S}$.

Let $\kappa > \omega$ be regular. Prove that $\diamond_\kappa$ is equivalent
to the existence of $B_\alpha\subseteq \alpha\times\alpha$ ($\alpha < \kappa$)
so that for every $B\subseteq\kappa\times\kappa$, the set
$\{\alpha < \kappa  B\cap(\alpha\times\alpha)=B_\alpha\}$ is stationary.

(Uses AC.)
Let $\kappa > \omega$ be regular. Prove that $\diamond_\kappa$ is equivalent to
the following seemingly weaker statement: there is a sequence
$F_\alpha$ ($\alpha < \kappa$) so that each $F_\alpha$ is a family of
subsets of $\alpha$, $F_\alpha\leq\alpha$, and for each $A\subseteq\kappa$,
the set $\{\alpha < \kappa  A\cap\alpha\in F_\alpha\}$ is stationary. (If all
$F_\alpha$ had cardinality 1, this would be exactly $\diamond_\kappa$.)
HintHint (hide): First translate in the manner of Question 5, to families $G_\alpha$
of $\alpha$ subsets of $\alpha\times\alpha$. Say $G_\alpha=\{B_\alpha^\xi 
\xi < \alpha\}$, and consider for each $\xi$ the sequence $A_\alpha^\xi$
($\alpha < \kappa$) where $A_\alpha^\xi\subseteq\alpha$ is the $\xi$th fiber of
$B_\alpha^\xi\subseteq\alpha\times\alpha$.
Assignment 9, due Friday 6/8:

Question 3 in the Fall 2003 qualifying exam. ($\alpha$ and $\beta$ in the question
should be taken to be $\geq\omega$ throughout.)

Question 5 in the Spring 2010 qualifying exam.

(Uses AC.)
Let $(L; < )$ be a c.c.c. linear order. Define an equivalence relation on
$L$ by $x\sim y$ iff the interval $(x,y)_L$ is countable. The
induced relation $[x] < [y]$ iff $x < y \land x\not\sim y$
on the set $L/\mathord{\sim}$
of equivalence classes is welldefined and continues to be a
linear order. Prove that it is dense, meaning that between any
two points there is a third. Prove in addition that it continues to be c.c.c.

(Uses AC.)
Continuing under the assumptions of question 3, prove that if $(L; < )$ is
not separable, then neither is $(L/\mathord{\sim}; < )$. In particular then
$(L/\mathord{\sim}; < )$ is not a single point, and indeed not countable.

(Uses AC.)
Let $(L; < )$ be a c.c.c. dense linear order with no endpoints. Let $(L^*; < )$
be the countable sequence
completion of $(L; < )$, defined as follows: First let $L'$
be the set of bounded nondecreasing functions $f\colon \omega\rightarrow
L$. Set $f\leq g$ iff $(\forall n)(\forall x < f(n))(\exists m) x< g(m)$. Set $f\sim g$
iff $f\leq g \land g\leq f$. Let $L^*=L'/\mathord{\sim}$
and let $ < $ be the linear order
on $L^*$ given by $[f] < [g]$ iff $f\leq g \land g\not\leq f$. Abusing
notation slightly we identify $x\in L$ with the equivalence class
$[n\mapsto x]\in L^*$ of the constantly $x$ function.
This allows us to view $L$ as a subset of $L^*$.
Prove that $L$ is dense in $(L^*; < )$, that $(L^*; < )$
continues to be c.c.c., that $(L^*; < )$ has no end points,
and that if $(L, < )$ is not separable then
neither is $(L^*; < )$.

(Uses AC.)
Under the assumptions of question 5, prove that $(L^*; < )$ is connected
in the order topology.

(Uses AC.)
Prove that if there is a c.c.c. linear order which is not separable,
then there is a Suslin line.