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 »

6 Comments | 580: Topics in set theory | 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

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 »

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

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.

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

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.

Recall:

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 »

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

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 »

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

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 »

1 Comment | 580: Topics in set theory | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Cardinal arithmetic (10)

March 9, 2009

Let me begin with a couple of comments that may help clarify some of the results from last lecture.

First, I want to show a different proof of Lemma 21.2, that I think is cleaner than the argument I gave before. (The argument from last lecture, however, will be useful below, in the proof of Kunen’s theorem.)

Lemma 1 If {\kappa} is measurable, {{\mathcal U}} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa,} and {j_{\mathcal U}:V\rightarrow M} is the corresponding ultrapower embedding, then {{}^\kappa M\subset M.}

 

Proof: Recall that if {\pi} is Mostowski’s collapsing function and {[\cdot]} denotes classes in {V^\kappa/{\mathcal U},} then {M=\{\pi([f]):f\in{}^\kappa V\}.} To ease notation, write {\langle f\rangle} for {\pi([f]).}

Let {h:\kappa\rightarrow M.} Pick {f:\kappa\rightarrow V} such that for all {\alpha<\kappa,} {h(\alpha)=\langle f(\alpha)\rangle.}

Lemma 2 With notation as above, {\langle f\rangle=j_{\mathcal U}(f)(\langle{\rm id}\rangle)} for any {f:\kappa\rightarrow V.}

 

Proof: For a set {X} let {c_X:\kappa\rightarrow V} denote the function constantly equal to {X.} Since {\pi} is an isomorphism, {\mbox{\L o\'s}}‘s lemma gives us that the required equality holds iff

\displaystyle \{\alpha<\kappa : f(\alpha)=((c_f)(\alpha))({\rm id}(\alpha))\}\in{\mathcal U},

but this last set is just {\{\alpha<\kappa:f(\alpha)=f(\alpha)\}=\kappa.} \Box

From the nice representation just showed, we conclude that {\langle f(\alpha)\rangle=j_{\mathcal U}(f(\alpha))(\langle{\rm id}\rangle)} for all {\alpha<\kappa.} But for any such {\alpha,} {j_{\mathcal U}(f(\alpha))=j_{\mathcal U}(f)(\alpha)} because {{\rm cp}(j_{\mathcal U})=\kappa} by Lemma 21 from last lecture. Hence, {h=(j_{\mathcal U}(f)(\alpha)(\langle{\rm id}\rangle):\alpha<\kappa),} which is obviously in {M,} being definable from {j_{\mathcal U}(f),} {\langle{\rm id}\rangle,} and {\kappa.} \Box

The following was shown in the proof of Lemma 20, but it deserves to be isolated.

Lemma 3 If {{\mathcal U}} is a normal nonprincipal {\kappa}-complete ultrafilter over the measurable cardinal {\kappa,} then {{\mathcal U}=\{X\subseteq\kappa:\kappa\in i_{\mathcal U}(X)\},} i.e., we get back {{\mathcal U}} when we compute the normal measure derived from the embedding induced by {{\mathcal U}.} {\Box}

 

Finally, the construction in Lemma 10 and preceeding remarks is a particular case of a much more general result.

Definition 4 Given {f:I\rightarrow J} and an ultrafilter {{\mathcal D}} over {I,} the projection {f_*({\mathcal D})} of {{\mathcal D}} over {J} is the set of {X\subseteq J} such that {f^{-1}(X)\in{\mathcal D}.}

 

Clearly, {f_*({\mathcal D})} is an ultrafilter over {J.}

Notice that if {\kappa={\rm add}({\mathcal D}),} {(X_\alpha:\alpha<\kappa)} is a partition of {I} into sets not in {{\mathcal D},} and {f:I\rightarrow\kappa} is given by {f(x)=} the unique {\alpha} such that {x\in X_\alpha,} then {f_*({\mathcal D})} is a {\kappa}-complete nonprincipal ultrafilter over {\kappa.} (Of course, {\kappa=\omega} is possible.)

For a different example, let {{\mathcal U}} be a {\kappa}-complete nonprincipal ultrafilter over the measurable cardinal {\kappa,} and let {f:\kappa\rightarrow\kappa} represent the identity in the ultrapower by {{\mathcal U},} {\langle f\rangle=\kappa.} Then {f_*({\mathcal U})} is the normal ultrafilter over {\kappa} derived from the embedding induced by {{\mathcal U}.}

Definition 5 Given ultrafilters {{\mathcal U}} and {{\mathcal V}} (not necessarily over the same set), say that {{\mathcal U}} is Rudin-Keisler below {{\mathcal V},} in symbols, {{\mathcal U}\le_{RK}{\mathcal V},} iff there are sets {S\in{\mathcal U},} {T\in{\mathcal V},} and a function {f:T\rightarrow S} such that {{\mathcal U}\upharpoonright S=f_*({\mathcal V}\upharpoonright T).}

 

Theorem 6 Let {{\mathcal U}} be an ultrafilter over a set {X} and {{\mathcal V}} an ultrafilter over a set {Y.} Suppose that {{\mathcal U}\le_{RK}{\mathcal V}.} Then there is an elementary embedding {j:V^X/{\mathcal U}\rightarrow V^Y/{\mathcal V}} such that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

 

Proof: Fix {T\in{\mathcal U}} and {S\in{\mathcal V}} for which there is a map {f:S\rightarrow T} such that {{\mathcal U}\upharpoonright T=f_*({\mathcal V}\upharpoonright S).} Clearly, {V^X/{\mathcal U}\cong V^T/({\mathcal U}\upharpoonright T)} as witnessed by the map {[f]_{\mathcal U}\mapsto[f\upharpoonright T]_{{\mathcal U}\upharpoonright T},} and similarly {V^Y/{\mathcal V}\cong V^S/({\mathcal V}\upharpoonright S),} so it suffices to assume that {S=Y} and {T=X.}

Given {h:X\rightarrow V,} let {h_*:Y\rightarrow V} be given by {h_*=h\circ f.} Then {j([h]_{\mathcal U})=[h_*]_{\mathcal V}} is well-defined, elementary, and {j\circ i_{\mathcal U}=i_{\mathcal V}.}

In effect, {h=_{\mathcal U}h'} iff {\{x\in X:h(x)=h'(x)\}\in{\mathcal U}} iff {\{y\in Y:h\circ f(y)=h'\circ f(y)\}\in{\mathcal V}} iff {h_*=_{\mathcal V}h'_*,} where the second equivalence holds by assumption, and it follows that {j} is well-defined.

If {c_B^A} denotes the function with domain {A} and constantly equal to {B,} then for any {x,} {j\circ i_{\mathcal U}(x)=j([c^X_x]_{\mathcal U})=[(c^X_x)_*]_{\mathcal V}=[c^Y_x]_{\mathcal V}=i_{\mathcal V}(x)} since {(c^X_x)_*=c^Y_x} by definition of the map {h\mapsto h_*.} This shows that {j\circ i_{\mathcal U}=i_{\mathcal V}.}

Elementarity is a straightforward modification of the proof of Lemma 10 from last lecture. \Box

One can show that Theorem 6 “very nearly” characterizes the Rudin-Keisler ordering, see for example Proposition 0.3.2 in Jussi Ketonen, Strong compactness and other cardinal sins, Annals of Mathematical Logic 5 (1972), 47–76.

Read the rest of this entry »

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

BOISE EXTRAVAGANZA IN SET THEORY (BEST) -Announcement 3 and Call for papers

March 8, 2009

Announcement 3: Call for papers, Lodging Deadlines.

The 18-th annual meeting of BEST will be hosted at Boise State University during the weekend of March 27 (Friday) – March 29 (Sunday), 2009.

It is organized by Liljana Babinkostova, Andres Caicedo, Stefan Geschke, Richard Ketchersid, and Marion Scheepers.

Contributed and invited talks will be held on Friday, Saturday and Sunday at the Department of Mathematics, Boise State University. The four invited speakers are:

Steve Jackson (University of North Texas)

Ljubisa Kocinac (University of Nis, Republic of Serbia)

Assaf Rinot (Tel Aviv University, Israel)

Grigor Sargsyan (University of California, Berkeley)

Please consult the conference webpage at URL

http://math.boisestate.edu/~best/best18

There are three remaining important deadlines regarding the conference.

CRITICAL DEADLINE: LODGING: The Hampton Inn & Suites is providing rooms at a reduced rate for BEST participants. To take advantage of the reduced rate, reservations must be made online by MARCH 12. Please follow this link to the Hampton Inn’s online reservation site for BEST.

Anyone interested in participating should contact the organizers as soon as possible by sending an email to

best@math.boisestate.edu

DEADLINE 2: Abstracts: Atlas Conferences, Inc. is providing abstract services for BEST 18. The deadline for submitting an abstract for invited or contributed talk is MARCH 25. Links are available at the BEST 18 web site.

DEADLINE 3: Call for papers: The organizers will be editors for a volume in the Contemporary Mathematics series. Research papers on topics related to Set Theory and its Applications will be considered for publication in this volume. All papers will go through a thorough referee process. Former and current participants of the BEST conferences or their collaborators are especially encouraged to consider submitting a research paper. Anyone interested in submitting a paper should contact Marion Scheepers as soon as possible at 

marion@math.boisestate.edu 

with this information. Subsequently information regarding preparation of papers will be sent to contributing authors by Contemporary Mathematics. The deadline for submitting a paper is JULY 21.

On Saturday, March 28, Billy and Kris Hudson will host a social gathering at their home. All participants are cordially invited to ths social event. Kindly inform Billy at e-mail address 

billyhudson@boisestate.edu 

of plans to attend. More information is available at the conference web site.

The conference is supported by a grant from the National Science Foundation. Abstract services are provided by Atlas Conferences, Inc. Contemporary Mathematics is published by the American Mathematical Society. Reduced lodging rate is provided by The Hampton Inn & Suites. Support from these entities is gratefully acknowledged.

Leave a Comment » | BEST | Tagged: | Permalink
Posted by andrescaicedo

305 -Extensions by radicals (3)

March 8, 2009

 

3. Examples

 

Last lecture we defined what it means that a polynomial with coefficients in a field {{\mathbb F}} is solvable by radicals over {{\mathbb F}}. Namely, there is a tower of extensions

\displaystyle {\mathbb F}(t_1,\dots,t_k):{\mathbb F}(t_1,\dots,t_{k-1}):\dots:{\mathbb F}(t_1):{\mathbb F}

where for each {j,} {1\le j\le k,} there is a positive integer {m_j} such that {t_j^{m_j}\in{\mathbb F}(t_1,\dots,t_{j-1}),} and such that {{\mathbb F}^{p(x)}\subseteq{\mathbb F}(t_1,\dots,t_k).}

Read the rest of this entry »

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

« Previous Entries