Math 220C, Mathematical Logic and Set Theory.

Instructor: Itay Neeman.
Office: MS 6334.
Email: Phone: 794-5317.
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 ZF-Foundation+"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:

1. 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$.
2. (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.
3. (Uses AC) A cardinal $\kappa$ is regular if $cof(\kappa)=\kappa$. Prove that every infinite successor cardinal is regular.
4. Prove that for every infinite ordinal $\alpha$, the cardinality of $L_\alpha$ is equal to the cardinality of $\alpha$.
5. $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$.
1. Prove that if $cof(\kappa) > \omega$ then the intersection of any two clubs in $\kappa$ is itself club in $\kappa$.
2. 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$.
6. Question 2 in the Fall 2003 qualifying exam.
Assignment 7, due Friday 5/25:
1. Let $\kappa > \omega$ be regular. Prove that $L_\kappa$ satisfies ZF-Powerset.
2. (Uses AC.) Question 6 in the Winter 2004 qualifying exam.
3. 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$.
4. Let $M\subseteq WF$ be transitive and satisfy (enough of) ZF-Powerset. Prove that wellfoundedness is absolute for $M$. Precisely, prove that the formula `$r$ is a wellfounded relation' is absolute for $M$.
5. Exercise 6.53.
6. Exercise 6.54.
7. Exercise 7.8.

Assignment 8, due Friday 6/1:

1. Question 3 in the Winter 2004 qualifying exam.
2. 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$.
3. 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$.
4. 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}$.
5. 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.
6. (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$.) Hint:

Assignment 9, due Friday 6/8:

1. Question 3 in the Fall 2003 qualifying exam. ($\alpha$ and $\beta$ in the question should be taken to be $\geq\omega$ throughout.)
2. Question 5 in the Spring 2010 qualifying exam.
3. (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 well-defined 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.
4. (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.
5. (Uses AC.) Let $(L; < )$ be a c.c.c. dense linear order with no end-points. Let $(L^*; < )$ be the countable sequence completion of $(L; < )$, defined as follows: First let $L'$ be the set of bounded non-decreasing 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^*; < )$.
6. (Uses AC.) Under the assumptions of question 5, prove that $(L^*; < )$ is connected in the order topology.
7. (Uses AC.) Prove that if there is a c.c.c. linear order which is not separable, then there is a Suslin line.