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 »

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

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.

Leave a Comment » | 305: Abstract Algebra I | 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

305 -Homework set 8

April 24, 2009

This set is due May 1 at the beginning of lecture. Details of the homework policy can be found on the syllabus and here.

1. Solve exercises 11, 14, and 24 from Chapter 14 of the textbook.

2. Solve exercises 1, 9, and 17 from Chapter 15 of the textbook.

Leave a Comment » | 305: Abstract Algebra I | Permalink
Posted by andrescaicedo

305 -9. Groups

April 24, 2009

We want to define the notion of group that will be fundamental to determine which polynomials are solvable by radicals. This notion is very important and appears in every area of mathematics.

We motivate the definition through the example that most concerns us: automorphisms of fields. They are particular class of isomorphisms, so we begin with them.

Some of the arguments below have been discussed in previous lectures.

Read the rest of this entry »

Leave a Comment » | 305: Abstract Algebra I | 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

305 -8. Irreducibility

April 20, 2009

In this lecture I want to present a couple of short results that are nevertheless very useful in practice when trying to show that a given polynomial in {{\mathbb Q}[x]} is irreducible. Of course, we may assume that the polynomial actually has integer coefficients. In this case, it turns out that analyzing whether the polynomial factors over {{\mathbb Z}[x]} suffices.

Read the rest of this entry »

Leave a Comment » | 305: Abstract Algebra I | 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.

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

305 -Extension fields revisited (3)

April 15, 2009

1. Isomorphisms

We return here to the quotient ring construction. Recall that if {R} is a commutative ring with identity and {I} is an ideal of {R,} then {R/I} is also a commutative ring with identity. Here, {R/I=\{[a]_\sim:a\in R\},} where {[a]_\sim=\{b:a\sim b\}} for {\sim} the equivalence relation defined by {a\sim b} iff {a-b\in I.}

Since {\sim} is an equivalence relation, we have that {[a]_\sim=[b]_\sim} if {a\sim b} and {[a]_\sim\cap[b]_\sim=\emptyset} if {a\not\sim b.} In particular, any two classes are either the same or else they are disjoint.

In case {R={\mathbb F}[x]} for some field {{\mathbb F},} then {I} is principal, so {I=(p)} for some {p\in{\mathbb F}[x],} i.e., given any polynomial {q\in{\mathbb F}[x],} {[q]_\sim=0} iff {p|q} and, more generally, {[q]_\sim=[r]_\sim} (or, equivalently, {q\sim r} or, equivalently, {r\in[q]_\sim}) iff {p|(q-r).}

In this case, {{\mathbb F}[x]/(p)} contains zero divisors if {p} is nonconstant but not irreducible.

If {p} is 0, {{\mathbb F}[x]/(p)\cong{\mathbb F}.}

If {p} is constant but nonzero, then {{\mathbb F}[x]/(p)\cong\{0\}.}

Finally, we want to examine what happens when {p} is irreducible. From now on suppose that this is the case.

Read the rest of this entry »

Leave a Comment » | 305: Abstract Algebra I | Tagged: , , , , , | Permalink
Posted by andrescaicedo

« Previous Entries