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 »

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

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

Update (Dec. 3, 2009). The pdf file still contains an error that was pointed out to me recently. In the third lecture on choiceless results, the correct argument is given.

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\mid q} and, more generally, {[q]_\sim=[r]_\sim} (or, equivalently, {q\sim r} or, equivalently, {r\in[q]_\sim}) iff {p\mid (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

305 -Extension fields revisited (2)

April 15, 2009

Most of our work from now on depends on the following simple, but very useful observation:

Theorem 1 Let {{\mathbb F}:{\mathbb K}} be a field extension. Then {{\mathbb F}} with its usual addition is a vector space over {{\mathbb K},} where multiplication of elements of {{\mathbb F}} by elements of {{\mathbb K}} is just the usual product of {{\mathbb F}}.

Read the rest of this entry »

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{\bf 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ński) {\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-ordering 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 »

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

« Previous Entries