## 116c- Lecture 18

May 30, 2008

We briefly discussed relative constructibility and compared the models $L[x]$ where $x$ is exclusively treated as a predicate with the models $L(x)$ where $x$ is an element. In particular, $L[x]$ is a model of choice but $L(x)$ may fail to be.

An amusing application of the fact that $L[x]models{sf AC}$ is that the result of Exercise 3 from Homework 7 holds in ${sf ZF}$, although the proof I wrote there uses choice. Namely, work in ${sf ZF}$ and consider two well-orderings of a set $X$. We can assume that $X$ is an ordinal $alpha$ and the first well-ordering is $in$. Let $prec$ be the second well-ordering. Then $precin L[prec]$ (since $prec$ is a set of ordered pairs of ordinals). In $L[prec]$, where choice holds, (and therefore also in $V$) there is a subset of $alpha$ of the same size as $alpha$ and where $prec$ coincides with $in$.

Question. Find a choice-free’ argument for Exercise 3.

The main example we will consider of a model of the form $L(x)$ is $L({mathbb R})$, due to its connection with determinacy.

We introduced the setting to discuss determinacy, namely infinite 2-person games with perfect information. We proved the Gale-Stewart theorem that open games are determined and discussed Martin’s extension to Borel games. A nice reference for the proof of Martin’s result (using the idea of unraveling‘, which reduces any Borel game to an open game in a different space) is Kechris’s book on descriptive set theory.

## 116c- Homework 8

May 29, 2008

Homework 8

Due Thursday, June 5 at 2:30 pm.

## 116c- Lecture 17

May 29, 2008

We verified that the sets $L_alpha$ form a continuous increasing sequence and are transitive. It follows that the reflection theorem holds for the $L_alpha$ and $L$. Arguing in ${sf ZF}$, we proved that $L$ is a model of ${sf ZF}$, and the reflection theorem allowed us to simplify the proof in a few points.

We then proceeded to argue that $L$ is also a model of choice. In fact, there is a globally definable well-ordering of $L$. It is worth emphasizing that the well-ordering is a very natural one, as we simply proceed to enumerate the sets in $L$ in the order in which their membership is verified. The definitions of the sequence of sets $L_alpha$ and of this well-ordering are absolute, and we used this to prove that $L$ is a model of the statement “$V=L$,” and so is any $L_alpha$, for $alpha$ limit. Moreover, the well-ordering of $L$, when restricted to $L_alpha$, coincides with its interpretation inside $L_alpha$.

An easy induction shows that for $alpha$ infinite, $|L_alpha|=|alpha|$. An argument using the Mostowski collapsing theorem allowed us to prove Gödel’s condensation lemma: If $Xprec L_alpha$ for $alpha$ a limit ordinal, then $X$ is isomorphic to some $L_beta$. These two facts combine to provide a proof that ${sf GCH}$ holds in $L$.

Remark. These arguments prove that ${rm Con}({sf ZF})$ implies ${rm Con}({sf ZFC})$, but they also indicate that showing that ${rm Con}({sf ZF})$ implies ${rm Con}({sf ZF}+lnot{sf AC})$ ought to be more complicated. The reason is that the absoluteness of the construction of $L$ implies that if $M$ is a transitive proper class model of ${sf ZF}$, then $Lsubseteq M$ and in fact $L^M=L$, i.e., the result of running the construction of $L$ from the point of view of $M$ is $L$ itself. But, since $V=L$ holds in $L$, we cannot prove in ${sf ZF}$ that there is a non-constructible set. If we tried to establish the consistency of ${sf ZF}$ with the negation of choice by a similar method, namely, the construction of a transitive class model $M$ of ${sf ZF}+lnot{sf AC}$, then running the construction inside $L$ would give us that $L=L^{M^L}subseteq M^Lsubseteq L$, so $M^L=L$, which would be a contradiction, since we are assuming that (provably in ${sf ZF}$) $M$ is a model of $lnot{sf AC}$ but $L$ is a model of choice.

This also suggests that in order to show that ${sf AC}$ is independent of ${sf ZF}$, one should try first to show that $Vne L$ is consistent with ${sf ZF}$. The remarkable solution found by Paul Cohen in 1963, the method of forcing, allows us to prove the consistency of both statements, and also to do this while working with transitive models. The method of forcing is beyond the scope of this course, but good explanations can be found in a few places, there is for example a book by Cohen himself, or look at Kunen’s book mentioned at the beginning of the course. Richard Zach has compiled in his blog a list of papers providing an introduction to the method (search for `forcing’).

## 116c- Lecture 16

May 24, 2008

We showed that $Delta_1$ formulas are absolute among transitive models of (enough) set theory, and used this to prove that satisfiability for transitive sets is absolute. More precisely, let ${rm Sat}(a,b,c)$ mean that $a$ is a transitive set $M$, $b$ codes a formula $varphi(vec x)$$c$ is a tuple $vec X$ of elements of $M$, and $Mmodelsvarphi(vec X)$. Then ${rm Sat}(a,b,c)$ is $Delta_1$. Using this and the reflection theorem we can conclude that $Delta_1$ is actually the extent of absoluteness in set theory, meaning that whenever there is a finite $S$ such that $phi$ is absolute for transitive models of $S$, then $phi$ is $Delta_1$.

We exhibited a few formulas that are not absolute. For example, “$x$ is a cardinal” and “$x=V_alpha$,” although both are $Pi_1$ and therefore relativize downwards.

The main application of the absoluteness of satisfiability is that it allows us to define the constructible hierarchy and Gödel’s constructible universe $L$.

Remark. On the other hand, we cannot define in general satisfiability for transitive classes, by Tarski’s undefinability of truth theorem. The difference with the case of sets is that with sets the recursive definition of $Mmodels$ involves several bounded quantifiers, ranging over finite powers of $M$. With general proper classes $M$, these quantifiers would be unbounded. An easy inductive argument shows that we can define partial satisfiability predicates (and therefore partial truth predicates), meaning that for each natural number $n$ and each class $M$ we can find a $Sigma_n$ formula that defines satisfiability for $Sigma_n$ formulas with respect to $M$; although we cannot in general find a uniform definition that works simultaneously for all $n$.

## 116c- Lecture 15

May 21, 2008

We presented a list of statements, definable relations, functions, and constants, that are absolute for transitive models of enough set theory. We showed that absolute functions are closed under composition, although $Delta_0$ functions are not. We also verified that being a well-ordering is absolute. The same argument actually shows:

Theorem. The statement “$R$ is a well-founded relation on $A$” is absolute for transitive models of ${sf ZF}-{sf Powerset}$.

This is a key result very useful in a variety of situations. Notice that we are not claiming that being well-orderable is absolute; in fact, it is not. The difference is that in the first case we are given a witness to the well-orderability, and claim that no matter in which transitive model the witness is observed, in all of them it has the property of being a well-ordering. The second case only states that there is a witness, and a given model may very well fail to produce such a witness unless it is a model of the axiom of choice.

## 116c- Homework 7

May 20, 2008

Homework 7

Due Wednesday, May 28 at 2:30 pm.

Update. I present here a quick sketch of the solution of Exercise 3.(b). See Lecture 18, where it is shown that the result actually holds in ${sf ZF}$, although the proof uses choice.

Let $<$ and $prec$ be two well-orderings of a set $X$. We want to find a subset of $X$ of the same size as $X$ where the two well-orderings coincide. Let $kappa=|X|$. By combining with an isomorphism between $(X,<)$ and its order type, we may assume that $X$ is an ordinal and $<=in$. By restricting attention to the subset $kappa$ of $X$, we may assume $prec$ is a well-ordering of $kappa$. By further restricting to the subset of $kappa$ of order type $kappa$ under $prec$, we may assume that ${rm ot}(kappa,prec)=kappa$ as well.

Assume first that $kappa$ is regular. The result follows easily. The desired set $Y$ can be built by a straightforward recursion: Given $beta and $(gamma_alpha:alpha a sequence of elements of $kappa$ increasing under both well-orderings, regularity ensures that the sequence is bounded under both well-orderings, and we can find $gamma_beta$ which is larger than all the previous $gamma_alpha$ under both orderings.

The argument for $kappa$ singular is slightly more delicate. Namely, we may not be able to carry out the construction above since the sequence could be unbounded in one of the orderings when ${rm cf}(beta)={rm cf}(kappa)$. We circunvent the problem by only considering ordinals $beta$ whose cofinality is larger than the cofinality of $kappa$. Notice that if an increasing sequence of order type $beta$  is unbounded in an ordinal of cofinality $gamma$, then ${rm cf}(beta)={rm cf}(gamma)$.

To implement this idea, let $(kappa_i:i<{rm cf}(kappa))$ be an increasing sequence of regular cardinals cofinal in $kappa$, with ${rm cf}(kappa). Consider the subset $kappa_0$. It must contain a subset of size $kappa_0$ where $prec$ coincides with $in$. By the remark above, this subset $B$ is bounded in $(kappa,prec)$. Let $A$ denote the shortest initial segment of $(kappa,prec)$ containing $B$. By removing from $kappa$ the set $kappa_0cup A$, we are left with a set of size $kappa$, and any ordinal there is larger than the elements of $B$ under both orderings. The induction continues this way, by considering at stage $i$ a set of size $kappa_i$.

## Regressive functions on pairs

May 19, 2008

I recently gave a talk at the Claremont Colleges Algebra/Number Theory/Combinatorics Seminar on the topic of this paper, which can be found in my papers page.

For a set $X\subseteq{\mathbb N}^2$ let $X^{[2]}=\{(n,m)\in X^2:n. A function $f:X^{[2]}\to{\mathbb N}$ is regressive iff $f(u_1,u_2) for all $u_1 in $X$ with $0. A set $H\subseteq X$ is min-homogeneous for $f$ iff $f(u,u_1)=f(u,u_2)$ whenever $0 and $u,u_1,u_2\in H$.

Theorem. For all $n$ there exists $m$ such that if $X=\{1,2,\dots,m\}$ and $f:X^{[2]}\to{\mathbb N}$ is regressive, then there is $H\subseteq X$ of size at least $n$ and min-homogeneous for $f$.

The theorem (due to Kanamori and McAloon) states a version of the classical Ramsey theorem for regressive functions. We cannot expect $H$ to be homogeneous, i.e., in general $f\upharpoonright H^{[2]}$ will not be constant. For example, consider $f(u,v)=u-1$. Notice also that without loss of generality $1\in H$, since $f(1,u)=0$. It is natural to try to establish the rate of growth of the function $g$ that to each $n$ assigns the least $m$ as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of $k$ variables, Kanamori and McAloon showed:

Theorem. The function $g$ grows faster than any primitive recursive function.

In my paper I show using finite combinatorics methods that $g$ grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function $g(n,k)$ of two variables, defined as $g$ but with the additional requirement that ${\rm min}(H)\ge k$. Obviously, $g(2,k)=k+1$ and $g(3,k)=2k+1$. The situation for $g(4,k)$ is less clear, although it is of exponential growth.

Theorem. We have:

1. $g(4,1)=5$, $g(4,2)=15$, $g(4,3)=37$, $g(4,4)\le85$.
2. $2g(4,m)+3\le g(4,m+1)$, so $g(4,m)\ge 5\times 2^m-3$ for $m\ge3$.
3. $g(4,m+1)\le 2^m(m+2)-2^{m-1}+1$.

Question. Does $g(4,m)\ge 2^{m-1}m$ hold?

Although I have not been able to prove this, I do not expect it to be particularly difficult.