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

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

580 -Cardinal arithmetic (10)

March 9, 2009

Let me begin with a couple of comments that may help clarify some of the results from last lecture.

First, I want to show a different proof of Lemma 21.2, that I think is cleaner than the argument I gave before. (The argument from last lecture, however, will be useful below, in the proof of Kunen’s theorem.)

Lemma 1 If {\kappa} is measurable, {{\mathcal U}} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa,} and {j_{\mathcal U}:V\rightarrow M} is the corresponding ultrapower embedding, then {{}^\kappa M\subset M.}

 

Proof: Recall that if {\pi} is Mostowski’s collapsing function and {[\cdot]} denotes classes in {V^\kappa/{\mathcal U},} then {M=\{\pi([f]):f\in{}^\kappa V\}.} To ease notation, write {\langle f\rangle} for {\pi([f]).}

Let {h:\kappa\rightarrow M.} Pick {f:\kappa\rightarrow V} such that for all {\alpha<\kappa,} {h(\alpha)=\langle f(\alpha)\rangle.}

Lemma 2 With notation as above, {\langle f\rangle=j_{\mathcal U}(f)(\langle{\rm id}\rangle)} for any {f:\kappa\rightarrow V.}

 

Proof: For a set {X} let {c_X:\kappa\rightarrow V} denote the function constantly equal to {X.} Since {\pi} is an isomorphism, {\mbox{\L o\'s}}‘s lemma gives us that the required equality holds iff

\displaystyle \{\alpha<\kappa : f(\alpha)=((c_f)(\alpha))({\rm id}(\alpha))\}\in{\mathcal U},

but this last set is just {\{\alpha<\kappa:f(\alpha)=f(\alpha)\}=\kappa.} \Box

From the nice representation just showed, we conclude that {\langle f(\alpha)\rangle=j_{\mathcal U}(f(\alpha))(\langle{\rm id}\rangle)} for all {\alpha<\kappa.} But for any such {\alpha,} {j_{\mathcal U}(f(\alpha))=j_{\mathcal U}(f)(\alpha)} because {{\rm cp}(j_{\mathcal U})=\kappa} by Lemma 21 from last lecture. Hence, {h=(j_{\mathcal U}(f)(\alpha)(\langle{\rm id}\rangle):\alpha<\kappa),} which is obviously in {M,} being definable from {j_{\mathcal U}(f),} {\langle{\rm id}\rangle,} and {\kappa.} \Box

The following was shown in the proof of Lemma 20, but it deserves to be isolated.

Lemma 3 If {{\mathcal U}} is a normal nonprincipal {\kappa}-complete ultrafilter over the measurable cardinal {\kappa,} then {{\mathcal U}=\{X\subseteq\kappa:\kappa\in i_{\mathcal U}(X)\},} i.e., we get back {{\mathcal U}} when we compute the normal measure derived from the embedding induced by {{\mathcal U}.} {\Box}

 

Finally, the construction in Lemma 10 and preceeding remarks is a particular case of a much more general result.

Definition 4 Given {f:I\rightarrow J} and an ultrafilter {{\mathcal D}} over {I,} the projection {f_*({\mathcal D})} of {{\mathcal D}} over {J} is the set of {X\subseteq J} such that {f^{-1}(X)\in{\mathcal D}.}

 

Clearly, {f_*({\mathcal D})} is an ultrafilter over {J.}

Notice that if {\kappa={\rm add}({\mathcal D}),} {(X_\alpha:\alpha<\kappa)} is a partition of {I} into sets not in {{\mathcal D},} and {f:I\rightarrow\kappa} is given by {f(x)=} the unique {\alpha} such that {x\in X_\alpha,} then {f_*({\mathcal D})} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa.} (Of course, {\kappa=\omega} is possible.)

For a different example, let {{\mathcal U}} be a {\kappa}-complete nonprincipal ultrafilter over the measurable cardinal {\kappa,} and let {f:\kappa\rightarrow\kappa} represent the identity in the ultrapower by {{\mathcal U},} {\langle f\rangle=\kappa.} Then {f_*({\mathcal U})} is the normal ultrafilter over {\kappa} derived from the embedding induced by {{\mathcal U}.}

Definition 5 Given ultrafilters {{\mathcal U}} and {{\mathcal V}} (not necessarily over the same set), say that {{\mathcal U}} is Rudin-Keisler below {{\mathcal V},} in symbols, {{\mathcal U}\le_{RK}{\mathcal V},} iff there are sets {S\in{\mathcal U},} {T\in{\mathcal V},} and a function {f:T\rightarrow S} such that {{\mathcal U}\upharpoonright S=f_*({\mathcal V}\upharpoonright T).}

 

Theorem 6 Let {{\mathcal U}} be an ultrafilter over a set {X} and {{\mathcal V}} an ultrafilter over a set {Y.} Suppose that {{\mathcal U}\le_{RK}{\mathcal V}.} Then there is an elementary embedding {j:V^X/{\mathcal U}\rightarrow V^Y/{\mathcal V}} such that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

 

Proof: Fix {T\in{\mathcal U}} and {S\in{\mathcal V}} for which there is a map {f:S\rightarrow T} such that {{\mathcal U}\upharpoonright T=f_*({\mathcal V}\upharpoonright S).} Clearly, {V^X/{\mathcal U}\cong V^T/({\mathcal U}\upharpoonright T)} as witnessed by the map {[f]_{\mathcal U}\mapsto[f\upharpoonright T]_{{\mathcal U}\upharpoonright T},} and similarly {V^Y/{\mathcal V}\cong V^S/({\mathcal V}\upharpoonright S),} so it suffices to assume that {S=Y} and {T=X.}

Given {h:X\rightarrow V,} let {h_*:Y\rightarrow V} be given by {h_*=h\circ f.} Then {j([h]_{\mathcal U})=[h_*]_{\mathcal V}} is well-defined, elementary, and {j\circ i_{\mathcal U}=i_{\mathcal V}.}

In effect, {h=_{\mathcal U}h'} iff {\{x\in X:h(x)=h'(x)\}\in{\mathcal U}} iff {\{y\in Y:h\circ f(y)=h'\circ f(y)\}\in{\mathcal V}} iff {h_*=_{\mathcal V}h'_*,} where the second equivalence holds by assumption, and it follows that {j} is well-defined.

If {c_B^A} denotes the function with domain {A} and constantly equal to {B,} then for any {x,} {j\circ i_{\mathcal U}(x)=j([c^X_x]_{\mathcal U})=[(c^X_x)_*]_{\mathcal V}=[c^Y_x]_{\mathcal V}=i_{\mathcal V}(x)} since {(c^X_x)_*=c^Y_x} by definition of the map {h\mapsto h_*.} This shows that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

Elementarity is a straightforward modification of the proof of Lemma 10 from last lecture. \Box

One can show that Theorem 6 “very nearly” characterizes the Rudin-Keisler ordering, see for example Proposition 0.3.2 in Jussi Ketonen, Strong compactness and other cardinal sins, Annals of Mathematical Logic 5 (1972), 47–76.

Read the rest of this entry »

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

580 -Cardinal arithmetic (9)

March 7, 2009

2. The ultrapower construction

 

The study of ultrapowers originates in model theory, although it has found applications both in algebra and in analysis. However, it is accurate to say that it is mainly exploited in set theory. Here I present the basic idea, showing its close connection to the study of measurable cardinals, defined last lecture.

Suppose first that {{\mathcal U}} is an ultrafilter over a set {X.} We want to define the ultrapower of the universe {V} of sets by {{\mathcal U}.} The basic idea is to consider the product of {X} many copies of the structure {(V,\in).} We want to “amalgamate” them somehow into a new structure {(\tilde V,\tilde\in).} For this, we look for the “typical” properties of the elements {\{f(x): x\in X\}} of each “thread” {f:X\rightarrow V,} and add an element {\tilde f} to {\tilde V} whose properties in {(\tilde V,\tilde\in)} are precisely these typical properties. We use {{\mathcal U}} to make this precise, by saying that a property {\varphi} is typical of the range of {f} iff {\{x\in X:\varphi(f(x))\}\in{\mathcal U}.} This leads us to the following definition, due to Dana Scott, that adapts the ultrapower construction to the context of proper classes:

Definition 1 Let {{\mathcal U}} be an ultrafilter over a nonempty set {X.} We define the ultrapower {(V^X/{\mathcal U},\hat\in)} of {V} by {{\mathcal U}} as follows:

For {f,g:X\rightarrow V,} say that

\displaystyle f=_{\mathcal U} g\mbox{ iff }\{x\in X:f(x)=g(x)\}\in{\mathcal U}.

This is easily seen to be an equivalence relation. We would like to make the elements of {V^X/{\mathcal U}} to be the equivalence classes of this relation. Unfortunately, these are all proper classes except for the trivial case when {X} is a singleton, so we cannot within the context of our formal theory form the collection of all equivalence classes.

Scott’s trick solves this problem by replacing the class of {f} with

\displaystyle [f]:=\{g:X\rightarrow V: g=_{\mathcal U}f\mbox{ and }{\rm rk}(g)\mbox{ is least possible}\}.

Here, as usual, {{\rm rk}(g)={\rm min}\{\alpha:g\in V_{\alpha+1}\}=\sup\{{\rm rk}(x)+1:x\in g\}.} All the “classes” {[f]} are now sets, and we set {V^X/{\mathcal U}=\{[f]: f:X\rightarrow V\}.}

We define {\hat\in} by saying that for {f,g:X\rightarrow V} we have

\displaystyle [f]\hat\in[g]\mbox{ iff }\{x\in X:f(x)\in g(x)\}\in{\mathcal U}.

(It is easy to see that {\hat\in} is indeed well defined, i.e., if {f=_{\mathcal U}f'} and {g=_{\mathcal U}g'} then {\{x\in X:f(x)\in g(x)\}\in{\mathcal U}} iff {\{x\in X:f'(x)\in g'(x)\}\in{\mathcal U}.})

 

(The ultrapower construction is more general than as just defined; what I have presented is the particular case of interest to us.) The remarkable observation, due to \mbox{\L o\'s,} is that this definition indeed captures the typical properties of each thread in the sense described above:

Read the rest of this entry »

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

580 -Cardinal arithmetic (8)

March 5, 2009

 

4. Large cardinals and cardinal arithmetic

 

In section 3 we saw how the powers of singular cardinals (or, at least, of singulars of uncountable cofinality) satisfy strong restrictions. Here I show that similar restrictions hold at large cardinals. There is much more than one could say about this topic, and the results I present should be seen much more like an invitation than a full story. Also, for lack of time, I won’t motivate the large cardinals we will discuss. (In the ideal world, one should probably say a few words about one’s beliefs in large cardinals, since their existence and even their consistency goes beyond what can be done in the standard system {{\sf ZFC}.} I’ll however take their existence for granted, and proceed from there.)

 

1. Measurable cardinals

 

Definition 1 {\kappa} is a measurable cardinal iff {\kappa>\omega} and there is a nonprincipal {\kappa}-complete ultrafilter over {\kappa.}

 

Read the rest of this entry »

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