Dedekind infinite power sets

November 15, 2012

Write A\preceq B to indicate that there is an injection from A into B, and A\preceq^* B to mean that either A=\emptyset, or else there is a surjection from B onto A. It is a result of Kuratowski that (provably in \mathsf{ZF}) if \omega\preceq\mathcal P(X), then in fact \omega\preceq^* X, and therefore \mathcal P(\omega)\preceq \mathcal P(X). This appears as Théorème B in pages 94-95 of

Alfred Tarski. Sur les ensembles finis, Fund. Math. 6 (1924), 45–95.

To prove this result, note that it suffices to find a countably infinite family of disjoint subsets of X. Suppose (m_n\mid n<\omega) is an injection of  \omega into \mathcal P(X). These sets induce a partition of X: Consider the equivalence classes of the relation x\sim y iff

\forall n(x\in m_n\Longleftrightarrow y\in m_n).

It is natural to attempt to show that these equivalence classes can be enumerated. Of course, the class of x is completely specified by the list of values of n such that x\in m_n, but this list may be “wasteful” in the sense that it may contain redundant information. For example, if m_3\subsetneq m_{27}, and we know that x\in m_3, then we automatically know that x\in m_{27}, and there is no need to include 27 in our list if we already included 3. (On the other hand, if all we know is that x\in m_{27}, then including 3 in the list is certainly providing us with more information.) This suggests to assign to each x\in X the set F(x)=\{n_0,n_1,\dots\}\subseteq\omega defined recursively as follows: Let n_0 be least such that x\in m_{n_0}, if it exists. If n_0 is defined, let n_1>n_0 be least such that x\in m_{n_1} and m_{n_1}\not\supset m_{n_0}, if it exists, and note that this is the same as requiring that m_{n_1}\cap m_{n_0}\subsetneq m_{n_0}. Similarly, if n_1 is defined, let n_2>n_1 be least such that x\in m_{n_2}, and m_{n_2}\cap m_{n_1}\cap m_{n_0}\subsetneq m_{n_1}\cap m_{n_0}, if it exists, etc.

Clearly, for any x,y\in X, x\sim y iff F(x)\sim F(y). There are now two possibilities:

  • Case 1. For some x, the set F(x) is infinite.

In this case, we are done (and we do not even need to bother enumerating the classes), because the sequence

m_{n_0}\setminus m_{n_1}, (m_{n_0}\cap m_{n_1})\setminus m_{n_2},(m_{n_0}\cap m_{n_1}\cap m_{n_2})\setminus m_{n_3},\dots

is a countably infinite collection of non-empty disjoint subsets of X.

  • Case 2. All sets F(x) are finite.

In this case we are done as well, because there is a (canonical) bijection between \omega and \text{Fin}(\omega), which means that we have enumerated the equivalence classes (and, of course, there are infinitely many, since the sets m_n are all distinct, and each is a union of equivalence classes).

Read the rest of this entry »

Advertisement

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

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

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 »

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