502 – Ultraproducts of finite sets

October 2, 2009

I want to sketch here the proof that if {(M_n\mid n\in{\mathbb N})} is a sequence of finite nonempty sets, and {\lim_n |M_n|=\infty,} then {\prod_nM_n/{\mathcal U}} has size {|{\mathbb R}|} for any nonprincipal ultrafilter {{\mathcal U}} on {{\mathbb N}.}

The argument I present is due to Frayne, Morel, Scott, Reduced direct products, Fundamenta Mathematica, 51 (1962), 195–228.

The topic of the size of ultraproducts is very delicate and some open questions remain. For ultraproducts of finite structures, this is continued in Keisler, Ultraproducts of finite sets, The Journal of Symbolic Logic, 32 (1967), 47–57, and finally in Shelah, On the cardinality of ultraproduct of finite sets, The Journal of Symbolic Logic, 35 (1) (Mar., 1970), 83–84. Shelah shows that if an ultraproduct of finite sets is infinite, say of size {\kappa,} then {\kappa^{\aleph_0}=\kappa.} His argument is a very nice application of non-standard analysis. The case that interests us is easier.

Clearly,

\displaystyle |\prod_nM_n/{\mathcal U}|\le|\prod_n M_n|\le|{\mathbb N}^{\mathbb N}|=|{\mathbb R}|,

so it suffices to show that {|{\mathbb R}|\le|\prod_nM_n/{\mathcal U}|.}

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: , , , , , | Permalink
Posted by andrescaicedo

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 »

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

580 -Cardinal arithmetic (9)

March 7, 2009

2. The ultrapower construction

 

The study of ultrapowers originates in model theory, although it has found applications both in algebra and in analysis. However, it is accurate to say that it is mainly exploited in set theory. Here I present the basic idea, showing its close connection to the study of measurable cardinals, defined last lecture.

Suppose first that {{\mathcal U}} is an ultrafilter over a set {X.} We want to define the ultrapower of the universe {V} of sets by {{\mathcal U}.} The basic idea is to consider the product of {X} many copies of the structure {(V,\in).} We want to “amalgamate” them somehow into a new structure {(\tilde V,\tilde\in).} For this, we look for the “typical” properties of the elements {\{f(x): x\in X\}} of each “thread” {f:X\rightarrow V,} and add an element {\tilde f} to {\tilde V} whose properties in {(\tilde V,\tilde\in)} are precisely these typical properties. We use {{\mathcal U}} to make this precise, by saying that a property {\varphi} is typical of the range of {f} iff {\{x\in X:\varphi(f(x))\}\in{\mathcal U}.} This leads us to the following definition, due to Dana Scott, that adapts the ultrapower construction to the context of proper classes:

Definition 1 Let {{\mathcal U}} be an ultrafilter over a nonempty set {X.} We define the ultrapower {(V^X/{\mathcal U},\hat\in)} of {V} by {{\mathcal U}} as follows:

For {f,g:X\rightarrow V,} say that

\displaystyle f=_{\mathcal U} g\mbox{ iff }\{x\in X:f(x)=g(x)\}\in{\mathcal U}.

This is easily seen to be an equivalence relation. We would like to make the elements of {V^X/{\mathcal U}} to be the equivalence classes of this relation. Unfortunately, these are all proper classes except for the trivial case when {X} is a singleton, so we cannot within the context of our formal theory form the collection of all equivalence classes.

Scott’s trick solves this problem by replacing the class of {f} with

\displaystyle [f]:=\{g:X\rightarrow V: g=_{\mathcal U}f\mbox{ and }{\rm rk}(g)\mbox{ is least possible}\}.

Here, as usual, {{\rm rk}(g)={\rm min}\{\alpha:g\in V_{\alpha+1}\}=\sup\{{\rm rk}(x)+1:x\in g\}.} All the “classes” {[f]} are now sets, and we set {V^X/{\mathcal U}=\{[f]: f:X\rightarrow V\}.}

We define {\hat\in} by saying that for {f,g:X\rightarrow V} we have

\displaystyle [f]\hat\in[g]\mbox{ iff }\{x\in X:f(x)\in g(x)\}\in{\mathcal U}.

(It is easy to see that {\hat\in} is indeed well defined, i.e., if {f=_{\mathcal U}f'} and {g=_{\mathcal U}g'} then {\{x\in X:f(x)\in g(x)\}\in{\mathcal U}} iff {\{x\in X:f'(x)\in g'(x)\}\in{\mathcal U}.})

 

(The ultrapower construction is more general than as just defined; what I have presented is the particular case of interest to us.) The remarkable observation, due to \mbox{\L o\'s,} is that this definition indeed captures the typical properties of each thread in the sense described above:

Read the rest of this entry »

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