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 »

5 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 »

2 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

580 -Partition calculus (2)

April 1, 2009

 

1. Infinite exponents

 

Last lecture we showed that {\omega\rightarrow(\omega)^m_n} for any {m,n<\omega.} Later, we will see that for any {\lambda,\rho} and any {m<\omega} there is {\kappa} such that {\kappa\rightarrow(\lambda)^m_\rho.} On the other hand (recall we are assuming choice), there are no nontrivial positive partition relations {\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}} with {\tau} infinite.

(To avoid vacuously true statements, we are always assuming implicitly that {\kappa\rightarrow(\lambda_i)^\tau_{i<\rho}} requires {\kappa\ge\lambda_i\ge\tau} for at least one {i<\rho.})

Theorem 1 ({\mbox{Erd\H os}}-Rado) For all {\kappa} and all infinite {\tau,} {\kappa\not\rightarrow(\tau)^\tau.}

 

Proof: It is enough to show that {\kappa\not\rightarrow(\aleph_0)^{\aleph_0}.} In effect, if {\kappa\rightarrow(\tau)^\tau} holds and {\tau>\aleph_0,} we may assume that {\kappa>\tau} is regular, so any countable subset {X} of {\kappa} is bounded, and the ordinal {\sup(X)+\tau} is still strictly below {\kappa.}

For {x\in[\kappa]^\tau,} let {{}_\omega x} denote the subset of {x} consisting of its first {\omega} many members.

Now, given {f:[\kappa]^{\aleph_0}\rightarrow2,} let {g:[\kappa]^\tau\rightarrow2} be the function {g(x)=f({}_\omega x).} If {H} is homogeneous for {g} and of size {\tau,} then {{}_\omega H} is homogeneous for {f.} In effect, let {H'=H\setminus{}_\omega H,} so {|H'|=\tau.} If {x\in[{}_\omega H]^{\aleph_0},} then {f(x)=g(x\cup H')=g(H),} by homogeneity of {H.}

This shows that {\kappa\rightarrow(\tau)^\tau} for {\tau} infinite implies that there is some {\kappa'} such that {\kappa'\rightarrow(\aleph_0)^{\aleph_0},} so it is enough to show that the latter never holds. In fact, we cannot even have {\kappa\rightarrow(\omega)^\omega.} (Recall our convention that {\omega} denotes the order type and {\aleph_0} the size.)

For this, let {\kappa} be an arbitrary infinite cardinal, and let {<} be a well-ordering of {[\kappa]^\omega.} Define {f:[\kappa]^\omega\rightarrow 2} by {f(s)=0} iff {s} is the {<}-least member of {[s]^\omega,} and {f(s)=1} otherwise.

If {x\in[\kappa]^\omega} is homogeneous for {f} and {y} is the {<}-least member of {[x]^\omega,} then {f(y)=0,} so {x} is {0}-homogeneous. Now consider any infinite sequence {x_0\subsetneq x_1 \subsetneq\dots\subseteq x} of infinite subsets of {x.} Since {f(x_n)=0} for all {n,} we must have that {\dots<x_1<x_0,} contradicting that {<} is a well-order. \Box

In the presence of the axiom of choice, Theorem 1 completely settles the question of what infinite exponent partition relations hold. Without choice, the situation is different.

Read the rest of this entry »

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

580 -III. Partition calculus

March 21, 2009

 

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the {\mbox{Erd\H os}}-Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
  • Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
  • Neil Hindman, Dona Strauss, Algebra in the Stone-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} Birkhäuser (2005), 121–257.
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.

Read the rest of this entry »

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

580 -Cardinal arithmetic (12)

March 13, 2009

5. PCF theory

 

To close the topic of cardinal arithmetic, this lecture is a summary introduction to Saharon Shelah’s pcf theory. Rather, it is just motivation to go and study other sources; there are many excellent references available, and I list some below. Here I just want to give you the barest of ideas of what the theory is about and what kinds of results one can achieve with it. All the results mentioned are due to Shelah unless otherwise noted. All the notions mentioned are due to Shelah as far as I know.

Some references:

  • Maxim Burke, Menachem Magidor, Shelah’s pcf theory and its applications, Annals of pure and applied logic, 50, (1990), 207–254.
  • Thomas Jech, Singular cardinal problem: Shelah’s theorem on {2^{\aleph_\omega}}, Bulletin of the London Mathematical Society, 24, (1992), 127–139.
  • Saharon Shelah, Cardinal arithmetic for skeptics, Bulletin of the American Mathematical Society, 26 (2), (1992), 197–210.
  • Saharon Shelah, Cardinal arithmetic, Oxford University Press, (1994).
  • Menachem Kojman, The ABC of pcf, unpublished notes, available (as of this writting) at his webpage.
  • Uri Abraham, Menachem Magidor, Cardinal arithmetic, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.
  • Todd Eisworth, Successors of singular cardinals, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.

Read the rest of this entry »

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

« Previous Entries