580 -III. Partition calculus

March 21, 2009

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the {\mbox{Erd\H os}}-Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
  • Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
  • Neil Hindman, Dona Strauss, Algebra in the Stone-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} Birkhäuser (2005), 121–257.
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.

Read the rest of this entry »

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

305 -Rings, ideals, homomorphisms (3)

March 21, 2009

In order to understand the construction of the quotient ring from last lecture, it is convenient to examine some examples in details. We are interested in ideals {I} of {{\mathbb F}[x],} where {{\mathbb F}} is a field. We write {{\mathbb F}[x]/I} for the quotient ring, i.e., the set of equivalence classes {[a]_\sim} of polynomials {a} in {F[x]} under the equivalence relation {a\sim b} iff {a-b\in I.}

  • If {I=\{0\},} then for any {a,} the equivalence class {[a]_\sim} is just the singleton {\{a\}} and the homomorphism map {h:{\mathbb F}[x]\rightarrow{\mathbb F}[x]/I} given by {h(a)=[a]_\sim} is an isomorphism.

To understand general ideals better the following notions are useful; I restrict to commutative rings with identity although they make sense in other contexts as well:

Definition 1 Let {R} be a commutative ring with identity. An ideal {I} is principal iff it is the ideal generated by an element {a} of {R,} i.e., it is the set {(a)} of all products {ab} for {b\in R.}

For example, {\{0\}=(0)} is principal. In {{\mathbb Z}} every subring is an ideal and is principal, since all subrings of {{\mathbb Z}} are of the form {n{\mathbb Z}=(n)} for some integer {n.}

Read the rest of this entry »

305 -Rings, ideals, homomorphisms (2)

March 16, 2009

Let’s begin by verifying:

Theorem 1 If {R,S} are rings and {h:R\rightarrow S} is a homomorphism, then {h^{-1}(0)=\{a\in R: h(a)=0\}} is an ideal of {R.}

Proof: Clearly {0\in h^{-1}(0),} so this set is nonempty. If {a,b\in h^{-1}(0),} then {h(a-b)=h(a)+h(-b)=h(a)-h(b)=0,} so {a-b\in h^{-1}(0).} Finally, if {a\in h^{-1}(0)} and {b\in R} then {h(ab)=h(a)h(b)=0h(b)=0} and {h(ba)=h(b)h(a)=h(b)0=0} so both {ab} and {ba} are in {h^{-1}(0).} \Box

In a sense, this is the only source of examples of ideals. This is shown by means of an abstract construction.

Theorem 2 If {I} is an ideal of a ring {R} then there is a ring {S} and a homomorphism {h:R\rightarrow S} such that {I=h^{-1}(0).}

Proof: The proof resembles what we did to define the rings {{\mathbb Z}_n:} Begin by defining a relation {\sim} on {R} by ({a\sim b} iff {a-b\in I}). Check that {\sim} is an equivalence relation. We can then define {S=R/{\sim} =\{[x]:x\in R\}} where {[x]=[x]_\sim} is the equivalence class of {x,} i.e., {[x]=\{y:x\sim y\}.}

We turn {S} into a ring by defining {[x]+[y]=[x+y],} {[x]\times[y]=[xy]} and {0=[0].} Check that these operations are well defined. Then check that {(S,+,\times,0)} satisfies the axioms of rings.

Finally, let {h:R\rightarrow S} be the quotient map, {h(x)=[x].} Check that this is a homomorphism and that {h^{-1}(0)=I.} \Box

Definition 3 An isomorphism is a bijective homomorphism. If {h:R\rightarrow R} is an isomorphism, we say that it is an automorphism.

Proposition 4 Suppose that {{\mathbb F}} is a field and {I} is an ideal of {{\mathbb F}.} Then either {I=\{0\}} or {I={\mathbb F}.} {\Box}

It will be very important for us to understand the automorphisms of the field extensions {{\mathbb F}^{p(x)}} where {p(x)\in{\mathbb F}[x].} For this, we will need some tools of linear algebra, so it will be useful to review Chapter 12 and Appendix C of the book.

Typeset using LaTeX2WP. Here is a printable version of this post.

305 -6. Rings, ideals, homomorphisms

March 13, 2009

It will be important to understand the subfields of a given field; this is a key step in figuring out whether a field {{\mathbb Q}^{p(x)}} is an extension by radicals or not. We need some “machinery” before we can develop this understanding.


Definition 1 A ring is a set {R} together with two binary operations {+,\times} on {R} such that:

  1. {+} is commutative.
  2. There is an additive identity {0.}
  3. Any {a} has an additive inverse {-a.}
  4. {+} is associative.
  5. {\times} is associative.
  6. {\times} distributes over {+,} both on the right and on the left.

Read the rest of this entry »

580 -Cardinal arithmetic (12)

March 13, 2009

5. PCF theory

To close the topic of cardinal arithmetic, this lecture is a summary introduction to Saharon Shelah’s pcf theory. Rather, it is just motivation to go and study other sources; there are many excellent references available, and I list some below. Here I just want to give you the barest of ideas of what the theory is about and what kinds of results one can achieve with it. All the results mentioned are due to Shelah unless otherwise noted. All the notions mentioned are due to Shelah as far as I know.

Some references:

  • Maxim Burke, Menachem Magidor, Shelah’s pcf theory and its applications, Annals of pure and applied logic, 50, (1990), 207–254.
  • Thomas Jech, Singular cardinal problem: Shelah’s theorem on {2^{\aleph_\omega}}, Bulletin of the London Mathematical Society, 24, (1992), 127–139.
  • Saharon Shelah, Cardinal arithmetic for skeptics, Bulletin of the American Mathematical Society, 26 (2), (1992), 197–210.
  • Saharon Shelah, Cardinal arithmetic, Oxford University Press, (1994).
  • Menachem Kojman, The ABC of pcf, unpublished notes, available (as of this writting) at his webpage.
  • Uri Abraham, Menachem Magidor, Cardinal arithmetic, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.
  • Todd Eisworth, Successors of singular cardinals, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., forthcoming.

Read the rest of this entry »

580 -Cardinal arithmetic (11)

March 12, 2009

4. Strongly compact cardinals and {{sf SCH}}


Definition 1 A cardinal {kappa} is strongly compact iff it is uncountable, and any {kappa}-complete filter (over any set {I}) can be extended to a {kappa}-complete ultrafilter over {I.}


The notion of strong compactness has its origin in infinitary logic, and was formulated by Tarski as a natural generalization of the compactness of first order logic. Many distinct characterizations have been found.

Read the rest of this entry »