Set theory seminar – Marion Scheepers: Coding strategies (I)

September 25, 2010

This semester, the seminar started with a series of talks by Marion. The first talk happened on September 14.

We consider two games relative to a (proper) ideal J\subset{\mathcal P}(S) for some set S. The ideal J is not assumed to be \sigma-complete; we denote by \left< J\right> its \sigma-closure, i.e., the collection of countable unions of elements of J. Note that \left< J\right> is a \sigma-ideal iff \left< J\right> is an ideal iff S\notin\left< J\right>.

The two games we concentrate on are the Random Game on J, RG(J), and the Weakly Monotonic game on J, WMG(J).

In both games, players I and II alternate for \omega many innings, with I moving first, moving as follows:

\begin{array}{cccccc} I&O_0\in\left< J\right>&&O_1\in\left< J_2\right>&&\cdots\\ II&&T_0\in J&&T_1\in J \end{array}

In RG(J) we do not require that the O_i relate to one another in any particular manner (thus “random”), while in WMG(J) we require that O_1\subseteq O_2\subseteq\dots (thus “weakly”, since we allow equality to occur).

In both games, player II wins iff \bigcup_n T_n\supseteq\bigcup_n O_n. Obviously, II has a (perfect information) winning strategy, with = rather than the weaker \supseteq.

However, we are interested in an apparently very restrictive kind of strategy, and so we will give some leeway to player II by allowing its moves to over-spill if needed. The strategies for II we want to consider we call coding strategies. In these strategies, II only has access to player I’s latest move, and to its own most recent move. So, if F is a coding strategy, and II follows it in a run of the game, then we have that for every n,

T_n=F(T_{n-1},O_n),

with T_{-1}=\emptyset.

The underlying goal is to understand under which circumstances player II has a winning coding strategy in WMG(J). Obviously, this is the case if II has a winning coding strategy in RG(J).

Theorem 1. For an ideal J\subset{\mathcal P}(S), the following are equivalent:

  1. II has a winning coding strategy in RG(J).
  2. {\rm cf}(\left< J\right>,{\subset})\le|J|.

Corollary. {\sf GCH} implies that for any ideal J\subset{\mathcal P}(S), II has a winning strategy in WMG(J).

We can reformulate our goal as asking how much one can weaken {\sf GCH} in the corollary.

Let’s denote by {\sf wSCH}, the weak singular cardinals hypothesis, the statement that if \kappa is singular strong limit of uncountable cofinality, then for no cardinal \lambda of countable cofinality, we have \kappa<\lambda<2^\kappa.

By work of Gitik and Mitchell, we know that the negation of {\sf wSCH} is equiconsistent with the existence of a \kappa of Mitchell order o(\kappa)=\kappa^{+\omega}+\omega_1.

Theorem 2. The following are equivalent:

  1. {\sf wSCH}.
  2. For each ideal J on a singular strong limit \kappa of uncountable cofinality, II has a winning strategy in RG(J).

We now begin the proof of Theorem 1.

(1.\Rightarrow2.) Suppose II has a winning coding strategy F in RG(J). We want to show that {\rm cf}(\left< J\right>,{\subset})\le|J|. For this, we will define a map f:J\to\left< J\right> with \subset-cofinal range, as follows: Given X\in J, let T_0=X and T_{n+1}=F(T_n,\emptyset) for all n. Now set

f(X)=\bigcup_n T_n.

To see that f is cofinal, given O\in\left< J\right>, let X=F(\emptyset,O), so that the T_n are II’s responses using F in a run of the game where player I first plays O and then plays \emptyset in all its subsequent moves. Since F is winning, we must have f(X)\supseteq O.

Next talk.

2 Comments | Set theory seminar | 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 (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