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.

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 »

305 -Homework set 7

April 3, 2009

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

1. Let R be a commutative ring with identity. Let I be an ideal of R, and let i be a unit of R. Show that I=R iff i\in I. Conclude that the only ideals of a field {\mathbb F} are \{0\} and {\mathbb F}. Also conclude that {\mathbb F}[x]/I\cong\{0\} if I is the ideal of {\mathbb F}[x] generated by a constant nonzero polynomial.

2. Suppose p(x)\in{\mathbb F}[x] is a nonconstant, not irreducible polynomial, and let I=(p) be the ideal generated by p. Show that {\mathbb F}[x]/I has zero divisors.

3. Find an irreducible polynomial p(x) in {\mathbb Z}_2[x] of degree 3, and explicitly show that {\mathbb Z}_2[x]/(p) coincides with (i.e., is isomorphic to) the field of 8 elements built in a previous homework set.

4. Either build a field of 9 elements using the kinds of arguments in the previous problems; or determine a subfield of {\mathbb C} isomorphic to {\mathbb Q}[x]/(x^3+3x+3). (You may assume that x^3+3x+3 is irreducible in {\mathbb Q}[x].)

305 -Homework set 6

March 21, 2009

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

1. Find {\mathbb Q}^{p(x)} where p(x)=x^3-2, and determine all its subfields. Make sure you justify your answer. For example, if you state that two subfields {\mathbb F}_1 and {\mathbb F}_2 are different, you need to prove that this is indeed the case. 

2. Do the same for p(x)=x^4+x^3+x^2+x+1. 

[Updated, April 2: I guess the hint I gave for problem 2 makes no sense, sorry about that. Rather, you may want to begin by looking at how x^5-1 factors. Then, to compute \cos(72^\circ), it may be helpful to look at a triangle with angles \measuredangle 72^\circ, \measuredangle 72^\circ, and \measuredangle 36^\circ.]

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 »

305 -Homework set 5

March 4, 2009

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

Solve exercises 7, 35, 40, 43, 44, 45 from Chapter 6 of the book.

305 -Homework set 4

February 22, 2009

I am not happy with the solutions I received for problems 4 and 5 of Homework set 2 so, for this new set, due March 2 at the beginning of lecture, you must redo these two problems correctly. As usual, the homework policy is detailed in the syllabus. However, there are a few points I want to emphasize:

  • Although I have so far allowed collaboration, each student should write their own solutions. If a group of students collaborate in a problem, they should indicate so at the beginning of their solutions. 

Let me explain this a bit. I do not simply mean that each of you has to write or type your own set of solutions. Of course I expect that, but I expect more than that. When you write your solutions, you should do this on your own. I do not want to see exactly the same mistakes in different people, exactly the same notation, exactly the same equations. If I see it ever again, even if it is not intentional, I will not allow collaboration any longer. Collaboration means that you work together and help one another and give suggestions to one another. Once you have come up with a solution, then collaboration stops and you should write your own version of what was found. 

  • Also, if references are consulted, they should be listed. This means you should mention the books you look at that gave you ideas. This means you should give the name of the book, the author, the edition, the theorem you are using or quoting or being inspired by. Similarly, if you find ideas online, mention the webpage where you found them. 

Now, and this is very important: Your solutions are your own. It may be that by accident in some book you run into the solution of a problem I assigned. This is fine, as long as it is not done intentionally, and I trust your honesty in this regard. Remember that you are bound by an honor code. It is not acceptable to copy the solution the book gives, not even if you give a complete reference that makes it clear that the solution is not your own. If you find a useful idea in a book, make sure you understand it before you use it. Just copying it down will not be acceptable, even if you change notation or the order in which the idea is presented. If you find a solution in a book, and you do not understand it, you will be better off not attempting to use it.  

If I see that the two points above (or any of the details of the homework policy) are not followed, I may change the grading policy and increase the number of quizzes we will have and the percentage they contribute to your total grade. 

Please make sure your solutions are reasonably self contained. If you use a result we have not shown in class you need to provide a proof. Please make sure you turn in your homework on time. This means at the beginning of lecture, not at the end of lecture or in the middle of lecture.