580 -Cardinal arithmetic (7)

March 4, 2009

[This document was typeset using Luca Trevisan‘s LaTeX2WP. I will refer to result n (or definition n) from last lecture as 3.n.]

A. The Galvin-Hajnal rank and an improvement of Theorem 3.1

Last lecture, I covered the first theorem of the Galvin-Hajnal paper and several corollaries. Recall that the result, Theorem 3.1, states that if {\kappa} and {\lambda} are uncountable regular cardinals, and {\lambda} is {\kappa}-inaccessible, then {\prod_{\alpha<\kappa}\kappa_\alpha<\aleph_\lambda} for any sequence {(\kappa_\alpha:\alpha<\lambda)} of cardinals such that {\prod_{\alpha<\beta}\kappa_\alpha<\aleph_\lambda} for all {\beta<\kappa.}

In particular (see, for example, Corollary 3.7), if {{\rm cf}(\xi)>\omega} and {\aleph_\xi} is strong limit, then {2^{\aleph_\xi}<\aleph_{(|\xi|^{{\rm cf}(\xi)})^+}.}

The argument relied in the notion of an almost disjoint transversal. Assume that {\kappa} is regular and uncountable, and recall that if {{\mathcal A}=(A_\alpha:\alpha<\kappa)} is a sequence of sets, then {T({\mathcal A})=\sup\{|{\mathcal F}|:{\mathcal F}} is an a.d.t. for {{\mathcal A}\}.} Here, {{\mathcal F}} is an a.d.t. for {{\mathcal A}} iff {{\mathcal F}\subseteq\prod{\mathcal A}:=\prod_{\alpha<\kappa}A_\alpha} and whenever {f\ne g\in{\mathcal F},} then {\{\alpha<\kappa:f(\alpha)=g(\alpha)\}} is bounded.

With {\kappa,\lambda} as above, Theorem 3.1 was proved by showing that there is an a.d.t. for {(\prod_{\beta<\alpha}\kappa_\beta:\alpha<\kappa)} of size {\prod_{\alpha<\kappa}\kappa_\alpha,} and then proving that, provided that {|A_\alpha|<\aleph_\lambda} for all {\alpha<\kappa,} then {T({\mathcal A})<\aleph_\lambda.}

In fact, the argument showed a bit more. Recall that if {f:\kappa\rightarrow{\sf ORD},} then {\aleph_f=(\aleph_{f(\alpha)}:\alpha<\kappa).} Then, for any {f:\kappa\rightarrow\lambda}, {T(\aleph_f)<\aleph_\lambda.}

The proof of this result was inductive, taking advantage of the well-foundedness of the partial order {<_{b,\kappa}} defined on {{}^\kappa{\sf ORD}} by {f<_{b,\kappa}g} iff {\{\alpha:f(\alpha)\ge g(\alpha)\}} is bounded in {\kappa.} That {<_{b,\kappa}} is well-founded allows us to define a rank {\|f\|_b} for each {f:\kappa\rightarrow{\sf ORD},} and we can argue by considering a counterexample of least possible rank to the statement from the previous paragraph.

In fact, more precise results are possible. Galvin and Hajnal observed that replacing the ideal of bounded sets with the nonstationary ideal (or, really, any normal ideal), results in a quantitative improvement of Theorem 3.1. Read the rest of this entry »

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

580 -Cardinal arithmetic (5)

February 13, 2009

At the end of last lecture we defined club sets and showed that the diagonal intersection of club subsets of a regular cardinal is club.

Definition 10. Let \alpha be a limit ordinal of uncountable cofinality. The set S\subseteq\alpha is stationary in \alpha iff S\cap C\ne\emptyset for all club sets C\subseteq\alpha. 

For example, let \lambda be a regular cardinal strictly smaller than {\rm cf}(\alpha). Then S^\alpha_\lambda:=\{\beta<\alpha : {\rm cf}(\beta)=\lambda\} is a stationary set, since it contains the \lambda-th member of the increasing enumeration of any club in \alpha. This shows that whenever {\rm cf}(\alpha)>\omega_1, there are disjoint stationary subsets of \alpha. Below, we show a stronger result. The notion of stationarity is central to most of set theoretic combinatorics. 

Fact 11. Let S be stationary in \alpha.

  1. S is unbounded in \alpha.
  2. Let C be club in \alpha. Then S\cap C is stationary. 

Proof. 1. S must meet \kappa\setminus\alpha for all \alpha and is therefore unbounded.

2. Given any club sets C and D, (S\cap C)\cap D=S\cap(C\cap D)\ne\emptyset, and it follows that S\cap C is stationary. {\sf QED}

Read the rest of this entry »

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

580 -Cardinal arithmetic (4)

February 11, 2009

2. Silver’s theorem.

From the results of the previous lectures, we know that any power \kappa^\lambda can be computed from the cofinality and gimel functions (see the Remark at the end of lecture II.2). What we can say about the numbers \gimel(\lambda) varies greatly depending on whether \lambda is regular or not. If \lambda is regular, then \gimel(\lambda)=2^\lambda. As mentioned on lecture II.2, forcing provides us with a great deal of freedom to manipulate the exponential function \kappa\mapsto 2^\kappa, at  least for \kappa regular. In fact, the following holds:

Theorem 1. (Easton). If {\sf GCH} holds, then for any definable function F from the class of infinite cardinals to itself such that:

  1. F(\kappa)\le F(\lambda) whenever \kappa\le\lambda, and
  2. \kappa<{\rm cf}(F(\kappa)) for all \kappa,

there is a class forcing {\mathbb P} that preserves cofinalities and such that in the extension by {\mathbb P} it holds that 2^\kappa=F^V(\kappa) for all regular cardinals \kappa; here, F^V is the function F as computed prior to the forcing extension. \Box

For example, it is consistent that 2^\kappa=\kappa^{++} for all regular cardinals \kappa (as mentioned last lecture, the same result is consistent for all cardinals, as shown by Foreman and Woodin, although their argument is significantly more elaborate that Easton’s). There is almost no limit to the combinations that the theorem allows: We could have 2^\kappa=\kappa^{+16} whenever \kappa=\aleph_\tau is regular and \tau is an even ordinal, and 2^\kappa=\kappa^{+17} whenever \kappa=\aleph_\tau for some odd ordinal \tau. Or, if there is a proper class of weakly inaccessible cardinals (regular cardinals \kappa such that \kappa=\aleph_\kappa) then we could have 2^\kappa= the third weakly inaccessible strictly larger than \kappa, for all regular cardinals \kappa, etc.

Morally, Easton’s theorem says that there is nothing else to say about the gimel function on regular cardinals, and all that is left to be explored is the behavior of \gimel(\lambda) for singular \lambda. In this section we begin this exploration. However, it is perhaps sobering to point out that there are several weaknesses in Easton’s result.

Read the rest of this entry »

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

580 -Some choiceless results (2)

January 25, 2009

There are a few additional remarks on the Schröder-Bernstein theorem worth mentioning. I will expand on some of them later, in the context of descriptive set theory.

The dual Schröder-Bernstein theorem (dual S-B) is the statement “Whenever A,B are sets and there are surjections from A onto B and from B onto A, then there is a bijection between A and B.”

* This follows from the axiom of choice. In fact, {\sf AC} is equivalent to: Any surjective function admits a right inverse. So the dual S-B follows from choice and the S-B theorem. 

* The proofs of S-B actually show that if one has injections f:A\to B and g:B\to A, then one has a bijection h:A\to B contained in f\cup g^{-1}. So the argument above gives the same strengthened version of the dual S-B. Actually, over {\sf ZF}, this strengthened version implies choice. This is in Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375-381. 

* If j : {}x \to y is onto, then there is k:{\mathcal P}(y)\to {\mathcal P}(x) 1-1, so if there are surjections in both directions between A and B, then {\mathcal P}(A) and {\mathcal P}(B) have the same size. Of course, this is possible even if A and B do not.

Open question. ({\sf ZF}) Does the dual Schröder-Bernstein theorem imply the axiom of choice?

* The dual S-B is not a theorem of {\sf ZF}.

Read the rest of this entry »

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