580 -Partition calculus (7)

May 6, 2009


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)


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 »


305 -Homework set 9

May 2, 2009

[Update: I added an additional assumption to question 3.]

This set is due May 13 at 10:30 am. Remember that we will have an additional meeting that day. Details of the homework policy can be found on the syllabus and here. This set is extra credit.

Let {X} be a finite set and let {G} be a subgroup of the group {S_X} of permutations of the elements of {X.} Define a relation {\sim} on {X} by saying that {x\sim y} iff either {x=y} or {(x,y)\in G.}

  • Begin by showing that {\sim} is an equivalence relation.

For each {x\in X,} denote by {E_x} the equivalence class of {x,} i.e.,

\displaystyle E_x=\{y\in X : x\sim y\}.

Suppose now that in addition, for any {x,y\in X} there is some permutation {\pi\in G} such that {\pi(x)=y.}

  • Show that all the equivalence classes have the same size: {|E_x|=|E_y|} for all {x,y.}

Now assume as well that {|X|=p} is a prime number, and that G contains at least one transposition {(x,z)} for some {x,z\in X} with {x\ne z.}

  • Conclude that {G=S_X.}

As an application, suppose that {p} is a prime number and {f\in{\mathbb Q}[x]} is irreducible and of degree {{}p.} Assume that {f} has exactly {p-2} real roots and 2 complex (non-real) roots.

  • Conclude that

    \displaystyle {\rm Gal}({\mathbb Q}^{f(x)}/{\mathbb Q})\cong S_p.

In particular, let {f(x)=x^5-4x+2.}

  • Show that {{\rm Gal}({\mathbb Q}^{f(x)}/{\mathbb Q})\cong S_5.}

Now suppose that {2r+3} is prime, and let

\displaystyle f_r(x)=(x^2+4)x(x^2-4)(x^2-16)\dots(x^2-4r^2).

  • Show that if {k} is an odd integer then {|f_r(k)|\ge5.} Let {g(x)=f_r(x)-2,} and show that {g} is irreducible over {{\mathbb Q}.} Now find {{\rm Gal}({\mathbb Q}^{g(x)}/{\mathbb Q}).}

Typeset using LaTeX2WP.