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

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].)

4 Comments | 305: Abstract Algebra I | Tagged: | Permalink
Posted by andrescaicedo

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.]

4 Comments | 305: Abstract Algebra I | 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

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.

1 Comment | 305: Abstract Algebra I | Tagged: | Permalink
Posted by andrescaicedo

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.

6 Comments | 305: Abstract Algebra I | Tagged: | Permalink
Posted by andrescaicedo

305 -Homework set 3

February 18, 2009

This set is due February 25 at the beginning of lecture. Consult the syllabus for details on the homework policy.

1. Show directly that there is no field of 6 elements. (“Directly” means, among other things, that you cannot use the facts mentioned without proof at the end of lecture 4.3.)

2. Construct a field of size 8. Once you are done, verify that all its elements satisfy the equation x^8-x=0.

3. Solve exercises 36–38 from Chapter 4 of the book.

4. Is the set \{a+b\root 4\of 2 : a,b\in{\mathbb Q}\} a field with the usual +,\times,0,1?

1 Comment | 305: Abstract Algebra I | Tagged: | Permalink
Posted by andrescaicedo

580 -Cardinal arithmetic (5)

February 13, 2009

At the end of last lecture we defined club sets and showed that the diagonal intersection of club subsets of a regular cardinal is club.

Definition 10. Let \alpha be a limit ordinal of uncountable cofinality. The set S\subseteq\alpha is stationary in \alpha iff S\cap C\ne\emptyset for all club sets C\subseteq\alpha. 

For example, let \lambda be a regular cardinal strictly smaller than {\rm cf}(\alpha). Then S^\alpha_\lambda:=\{\beta<\alpha : {\rm cf}(\beta)=\lambda\} is a stationary set, since it contains the \lambda-th member of the increasing enumeration of any club in \alpha. This shows that whenever {\rm cf}(\alpha)>\omega_1, there are disjoint stationary subsets of \alpha. Below, we show a stronger result. The notion of stationarity is central to most of set theoretic combinatorics. 

Fact 11. Let S be stationary in \alpha.

  1. S is unbounded in \alpha.
  2. Let C be club in \alpha. Then S\cap C is stationary. 

Proof. 1. S must meet \kappa\setminus\alpha for all \alpha and is therefore unbounded.

2. Given any club sets C and D, (S\cap C)\cap D=S\cap(C\cap D)\ne\emptyset, and it follows that S\cap C is stationary. {\sf QED}

Read the rest of this entry »

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

305 -Homework set 2

February 9, 2009

This set is due February 20 at the beginning of lecture. Consult the syllabus for details on the homework policy. I do not think this set is particularly difficult, but it is on the longish side of things, so make sure you leave yourself enough time to work on it.

1. Gauß’ fundamental theorem of algebra states that any equation p(x)=0, where p is a polynomial with complex coefficients, has at least one complex root z. This means that z is a complex number and p(z)=0. Show that p has at most n roots, where n is its degree, and that if we count roots up to multiplicity, then it has exactly n roots. Since the multiplicity of a root z is by definition the largest m such that (x-z)^m is a factor of p(x), you may want to verify that p(z)=0 iff (x-z) is a factor of p.  

2. Let p(x) be a polynomial with real coefficients, and let z be a complex root of p. Show that p(\bar z)=0 as well. Conclude that if the degree n of p is odd and the coefficients of p are real, then p has at least one real root. (You may use the fundamental theorem of algebra, if needed.) Conclude also that if p is of degree four and has real coefficients, then p can be factored as the product of two quadratic polynomials with real coefficients. (Does this follow “directly” from the argument described in lecture?)

3. Solve exercises 54-56 from Chapter 3 of the book.

4. Show directly that if a,b,c are real numbers, then at least one of the solutions of x^3+ax^2+bx+c=0 is a real number. What I mean is that, rather than appealing to problem 2, you want to look at the solutions obtained by Cardano’s method as described in lecture, and argue directly from the formulas so obtained that at least one of the solutions must be real. Be careful, since your argument should not give you that all three roots are real, since this is not true in general.

5. Show directly that a quartic with complex coefficients admits only 4 roots. What I mean is that, rather than appealing to problem 1, you want to look at the solutions obtained by Ferrari’s method as described in lecture, and argue directly that they only produce 4 roots, even though, in principle, they produce 24 (since they involve solving a cubic and then taking a square root to obtain parameters from which four solutions are then found).

2 Comments | 305: Abstract Algebra I | Tagged: | Permalink
Posted by andrescaicedo

« Previous Entries