580 – Topics in Set Theory. ANNOUNCEMENT

March 5, 2012

 This Fall I will be teaching Topics in set theory. The unofficial name of the course is Combinatorial Set Theory.

We will cover diverse topics in combinatorial set theory, depending on time and the interests of the audience, with emphasis on three topics: Choice-free combinatorics, cardinal arithmetic, and partition calculus (a generalization of Ramsey theory).

Time permitting, we can also cover large cardinals, determinacy and infinite games, or cardinal invariants (the study of sizes of sets of reals), among others. I’m open to suggestions for topics, so feel free to email me or to post a comment.

Pre-requisites: Permission by instructor. The recommended background is knowledge of cardinals and ordinals. A basic course on set theory (like 502: Logic and Set Theory) would be ideal but is not required.

Grading: Based on homework.

Textbook: Combinatorial set theory, by Neil H. Williams. Elsevier Science (1977). ISBN-10: 0720407222, ISBN-13: 978-0720407228. The book seems to be out of print.

We will also use:

  • Combinatorial Set Theory: Partition Relations for Cardinals, by Paul Erdös, András Hajnal, Attila Máté, and Richard Rado. Elsevier Science (1984). ISBN-10: 0444861572,  ISBN-13: 978-0444861573. Apparently, this is also out of print.

I will distribute notes on the material of these books, on additional topics, and some papers that we will follow, particularly:

  • András Hajnal and Jean A. Larson. “Partition relations”, in Handbook of set theory, 129–213, Springer, 2010.
  • Jean A. Larson. “Infinite combinatorics”, in Handbook of the history of science, vol. 6, 145-357, Elsevier, 2012.

Leave a Comment » | 580: Topics in set theory | Permalink
Posted by andrescaicedo

580- Specker trees

February 11, 2011

In his proof that the axiom of infinity holds in Quine’s New Foundations, Specker associated to each set {X} a tree, now called the Specker tree of {X}. (The name is due to Randall Holmes.)

In order to make sense of the definition without needing to appeal to the axiom of choice, let us define an equivalence relation {\sim} on subsets of {X} by saying that {A\sim B} iff {|A|=|B|}. The nodes of the tree are equivalence classes of subsets of {X} under {\sim}. Specifically, at the root we have the class of {X}, and the immediate successors of a class {[Y]} are the classes {[Z]} such that {|{\mathcal P}(Z)|=|Y|}.

Of course, under choice we can simply use cardinals {|Y|} as nodes, rather than the classes {[Y]}.

If {X} is a set, let {\aleph(X)}, the Hartogs function of {X}, be the set of all ordinals {\alpha} that inject into {X}, so {\aleph(X)} is the first ordinal that cannot inject. Sierpiński proved that {\aleph(X)\preceq{\mathcal P}^3(X)} and therefore {\aleph(X)<\aleph({\mathcal P}^3(X))}. This observation gives us immediately that the Specker tree of any set {X} is well-founded.

Under choice, it follows that all trees have finite rank. This is because any branch through the tree is finite (its nodes being a strictly decreasing sequence of cardinals). Moreover, the smallest cardinal in a branch is larger than the smallest cardinal in any larger branch. But an infinite-rank tree must have arbitrarily large branches, so there is no smallest cardinal in the tree, which is absurd.

Remarkably, it is still open whether in the absence of choice it is consistent that there is a Specker tree of infinite rank.

Typeset using LaTeX2WP. Here is a printable version of this post.

Leave a Comment » | 580: Topics in set theory | Permalink
Posted by andrescaicedo

Luminy – Coda

October 27, 2010

While at Luminy, David Asperó showed me a quick proof of a nice result on Reinhardt cardinals in {\sf ZF}. It complements Grigor Sargsyan’s result discussed here.

Theorem (Asperó). Work in {\sf ZF}. Suppose j:V\to V is a nontrivial elementary embedding. Then there are a \bar\kappa<{\rm cp}(j) and an ordinal \alpha such that for all \beta there is a \mu and an elementary

\pi:V_\mu\to V_\mu

such that {\rm cp}(\pi)=\bar\kappa and \pi(\alpha)>\beta.

Proof. For \alpha an ordinal, set

\kappa^\alpha=\min\{\kappa\mid\exists\mu\exists i:V_\mu\to V_\mu such that {\rm cp}(i)=\kappa and {\rm ot}(\{\beta<\mu\mid i(\beta)=\beta\})\ge\alpha\}.

Note that suitable fragments of j witness that \kappa^\alpha is defined for all \alpha. Moreover, \alpha<\beta implies that \kappa^\alpha\le\kappa^\beta\le{\rm cp}(j), and therefore there is a \bar\kappa\le{\rm cp}(j) such that \kappa^\beta=\bar\kappa for all \beta sufficiently large. Moreover, since it is definable, we actually have \bar\kappa<{\rm cp}(j).

Let \alpha be least with \kappa^\beta=\bar\kappa for \beta\ge\alpha. We claim that \bar\kappa and \alpha are as wanted. For this, consider some \beta>\alpha, and pick i:V_\mu\to V_\mu witnessing that \bar\kappa=\kappa^\beta. All we need to do is to check that i(\alpha)\ge\beta.

But note that if \gamma\in[\alpha,\beta), then V_\mu\models\kappa^\gamma=\bar\kappa Hence, if i(\alpha)<\beta, we have

V_\mu\models \kappa^{i(\alpha)}=\bar\kappa.

But \kappa^{i(\alpha)}=i(\kappa^\alpha)=i(\bar\kappa)>\bar\kappa. Contradiction. \Box

Leave a Comment » | 580: Topics in set theory, Luminy | Tagged: , | Permalink
Posted by andrescaicedo

580 -Partition calculus (7)

May 6, 2009

 
Updates

Let me begin with a couple of updates.

In the last Corollary of the Appendix to lecture I.5, I indicate that in {{\sf ZF},} we have that

\displaystyle \aleph(X)<\aleph({\mathcal P}^2(X))

whenever {\aleph(X)} is not {\aleph_\alpha} for some infinite limit ordinal {\alpha<\aleph_\alpha.} In fact,

\displaystyle {\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)

holds.

This result is best possible in terms of positive results. In Theorem 11 of the paper by John Hickman listed at the end, it is shown that for any such {\alpha} it is consistent with {{\sf ZF}} that there is an {X} with {\aleph(X)=\aleph_\alpha} for which {\aleph(X)=\aleph({\mathcal P}^2(X)).}

I also want to give an update on the topics discussed in lecture III.3.

{\mbox{Erd\H os}} and Hajnal asked whether it is possible to have infinite cardinals {\tau,\lambda,\kappa} such that

\displaystyle \tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}.

Galvin and Prikry showed (see Corollaries 16 and 18 of lecture III.3) that any such {\tau} must be larger than {\lambda^\kappa} and that {\kappa<\lambda.}

Following a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot hold.

The key is the following:

Lemma 1 If there are infinite cardinals {\tau,\lambda,\kappa} such that {\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa},} then for every sufficiently large {\gamma} there is an elementary embedding {j:M\rightarrow V_\gamma} such that {|M|=\lambda^\kappa,} {{\rm cp}(j)<\lambda,} {j(\lambda)=\lambda,} and {{}^\kappa M\subseteq M.}

 
Here is a brief sketch:

Proof: By Corollary 20 from lecture III.3, the given relation is equivalent to {\tau\rightarrow[\lambda]^\kappa_\lambda.} Consider a {\kappa}-Skolem function {F:[V_\gamma]^\kappa\rightarrow V_\gamma} so that any {Y\subset V_\gamma} closed under {F} is both closed under {\kappa}-sequences and an elementary substructure of {V_\gamma.}

Use {F} to define a coloring {G:[\tau]^\kappa\rightarrow\lambda} by setting {G(x)=F(x)} whenever {F(x)\in\lambda,} and {G(x)=0} otherwise. By assumption, there is {H\in[\tau]^\lambda} with {G''[H]^\kappa\ne\lambda.} Note that if {Y} is the closure of {H} under {F,} then {Y\cap\lambda=G''[H]^\kappa\cap\lambda\ne\lambda.} But we can assure that {|H\cap\lambda|=\lambda,} and the result follows by taking as {M} the transitive collapse of {H.} \Box

One concludes the proof by noting that it is impossible to have such embeddings. For this, it suffices that {{}^\omega M\subseteq M} and that {M} admits a fixed point past its critical point. One then obtains a contradiction just as in Kunen’s proof that there are no embeddings {j:V\rightarrow V,} see Corollary 9 in lecture III.3.

Similarly, Matthew Foreman has shown that there are no embeddings {j:M\rightarrow V} with {M} closed under {\omega}-sequences. The reason is that any such embedding must admit a fixed point past its critical point, as can be argued from the existence of scales. See the paper by Vickers and Welch listed at the end for a proof of this result.

On the other hand, it is still open whether one can have embeddings {j:M\rightarrow V} such that {M} computes cofinality {\omega} correctly.

1. The Baumgartner-Hajnal theorem

In Theorem 2 of lecture III.5 we showed the {\mbox{Erd\H os}}-Rado result that

\displaystyle \kappa\rightarrow_{top}(Stationary,\omega+1)^2

whenever {\kappa} is regular. It is natural to wonder whether stronger results are possible. We restrict ourselves here to the case {\kappa=\omega_1.} Due to time constraints, we state quite a few results without proof.

Read the rest of this entry »

11 Comments | 580: Topics in set theory | Tagged: , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (6)

April 24, 2009

 

1. The {\mbox{Erd\H os}}-Rado theorem

 

Large homogeneous sets (of size {\omega_1} or larger) can be ensured, at the cost of starting with a larger domain. The following famous result was originally shown by {\mbox{Erd\H os}} and Rado using tree arguments (with {\kappa+1} lowered to {\kappa} in the conclusion). We give instead an elementary substructures argument due to Baumgartner, Hajnal and {\mbox{Todor\v cevi\'c},} which proves the stronger version. For {\kappa} a cardinal let {2^{<\kappa}=\sup_{\lambda<\kappa}2^\lambda.}

Theorem 1 ({\mbox{Erd\H os}}-Rado) Let {\kappa} be a regular cardinal and let {\lambda=(2^{<\kappa})^+.} Then

\displaystyle \lambda\rightarrow(\kappa+1)^2_\mu

for all {\mu<\kappa.}

 

Read the rest of this entry »

1 Comment | 580: Topics in set theory | Tagged: , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (5)

April 21, 2009

1. Larger cardinalities

We have seen that {\omega\rightarrow(\omega)^n_m} (Ramsey) and {\omega\rightarrow[\omega]^n_\omega} ({\mbox{Erd\H os}}-Rado) for any {n,m<\omega.} On the other hand, we also have that {2^\kappa\not\rightarrow(3)^2_\kappa} ({\mbox{Sierpi\'nski}}) and {2^\kappa\not\rightarrow(\kappa^+)^2} ({\mbox{Erd\H os}}-Kakutani) for any infinite {\kappa.}

Positive results can be obtained for larger cardinals than {\omega} if we relax the requirements in some of the colors. A different extension, the {\mbox{Erd\H os}}-Rado theorem, will be discussed later.

Theorem 1 ({\mbox{Erd\H os}}-Dushnik-Miller) For all infinite cardinals {\lambda,} {\lambda\rightarrow(\lambda,\omega)^2.}

This was originally shown by Dushnik and Miller in 1941 for {\lambda} regular, with {\mbox{Erd\H os}} providing the singular case. For {\lambda} regular one can in fact show something stronger:

Theorem 2 ({\mbox{Erd\H os}}-Rado) Suppose {\kappa} is regular and uncountable. Then

\displaystyle \kappa\rightarrow_{top}(\mbox{Stationary},\omega+1)^2,

which means: If {f:[\kappa]^2\rightarrow2} then either there is a stationary {H\subseteq\kappa} that is {0}-homogeneous for {f}, or else there is a closed subset of {\kappa} of order type {\omega+1} that is {1}-homogeneous for {f}.

(Above, top stands for “topological.”)

Read the rest of this entry »

4 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Cardinal Arithmetic

April 20, 2009

Here is a pdf file with the contents of the lectures on cardinal arithmetic. As with the previous chapter, it follows closely the style of the notes. There are fewer typos than in the posts, and once again I made a minuscule tidying up. Please let me know of comments, corrections, and suggestions.

Leave a Comment » | 580: Topics in set theory | Permalink
Posted by andrescaicedo

580 -Some choiceless results

April 16, 2009

I reformatted the posts for the lectures on choiceless results. Here they are as a pdf file. It follows closely the style of the notes. I fixed a couple of typos, and made a minuscule tidying up. Please let me know of comments, corrections, and suggestions.

Update (Dec. 3, 2009). The pdf file still contains an error that was pointed out to me recently. In the third lecture on choiceless results, the correct argument is given.

Leave a Comment » | 580: Topics in set theory | Permalink
Posted by andrescaicedo

580 -Partition calculus (4)

April 9, 2009

 

1. Colorings of pairs. I

 

There are several possible ways in which one can try to generalize Ramsey’s theorem to larger cardinalities. We will discuss some of these generalizations in upcoming lectures. For now, let’s highlight some obstacles.

Theorem 1 ({\mbox{Erd\H os}}-Kakutani) {\omega_1\not\rightarrow(3)^2_\omega.} In fact, {2^\kappa\not\rightarrow(3)^2_\kappa.}

 

Proof: Let {S={}^\kappa\{0,1\}.} Let {F:[S]^2\rightarrow\kappa} be given by

\displaystyle F(\{f,g\})=\mbox{least }\alpha<\kappa\mbox{ such that }f(\alpha)\ne g(\alpha).

Then, if {f,g,h} are distinct, it is impossible that {F(\{f,g\})=F(\{f,h\})=F(\{g,h\}).} \Box

Theorem 2 (Sierpi\’nski) {\omega_1\not\rightarrow(\omega_1)^2.} In fact, {2^\kappa\not\rightarrow(\kappa^+)^2.}

 

Proof: With {S} as above, let {F:[S]^2\rightarrow2} be given as follows: Let {<} be a well-order of {S} in order type {2^\kappa.} Let {<_{lex}} be the lexicographic ordering on {S.} Set

\displaystyle F(\{f,g\})=1\mbox{ iff }<_{lex}\mbox{ and }<\mbox{ coincide on }\{f,g\}.

Lemma 3 There is no {<_{lex}}-increasing or decreasing {\kappa^+}-sequence of elements of {S.}

 

Proof: Let {W=\{f_\alpha\colon\alpha<\kappa^+\}} be a counterexample. Let {\gamma\le\kappa} be least such that {\{f_\alpha\upharpoonright\gamma\colon\alpha<\kappa^+\}} has size {\kappa^+,} and let {Z\in[W]^{\kappa^+}} be such that if {f,g\in Z} then {f\upharpoonright\gamma\ne g\upharpoonright\gamma.} To simplify notation, we will identify {Z} and {W.} For {\alpha<\kappa^+} let {\xi_\alpha<\gamma} be such that {f_\alpha\upharpoonright\xi_\alpha=f_{\alpha+1} \upharpoonright\xi_\alpha} but {f_\alpha(\xi_\alpha)=1-f_{\alpha+1}(\xi_\alpha).} By regularity of {\kappa^+,} there is {\xi<\gamma} such that {\xi=\xi_\alpha} for {\kappa^+} many {\alpha.}

But if {\xi=\xi_\alpha=\xi_\beta} and {f_\alpha\upharpoonright\xi=f_\beta\upharpoonright\xi,} then {f_\beta<_{lex} f_{\alpha+1}} iff {f_\alpha<_{lex} f_{\beta+1},} so {f_\alpha=f_\beta.} It follows that {\{f_\alpha\upharpoonright\xi\colon\alpha<\kappa^+\}} has size {\kappa^+,} contradicting the minimality of {\gamma.} \Box

The lemma implies the result: If {H\subseteq S} has size {\kappa^+} and is {F}-homogeneous, then {H} contradicts Lemma 3. \Box

Now I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. Perhaps surprisingly, strong anti-Ramsey results are possible, even if we restrict ourselves to colorings of pairs.

Read the rest of this entry »

3 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (3)

April 6, 2009

 

1. Infinitary Jónsson algebras

 

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

 

Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

 

Read the rest of this entry »

3 Comments | 580: Topics in set theory | Tagged: , , , , , | Permalink
Posted by andrescaicedo

« Previous Entries