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

For the first talk, see here. The second talk took place on September 21.

We want to prove of Theorem 1, that if , then II has a winning coding strategy in .

The argument makes essential use of the following:

Coding Lemma.Let be a poset such that for all ,

Suppose that . Then there is a map such that

Proof. Note that is infinite. We may then identify it with some infinite cardinal . It suffices to show that for any partial ordering on as in the hypothesis, there is a map such that for any , there is a with such that .

Well-order in type , and call this ordering. We define by transfinite recursion through . Given , let be the set of its -predecessors,

.

Our inductive assumption is that for any pair , we have chosen some with , and defined . Let us denote by the domain of the partial function we have defined so far. Note that . Since has size , it must meet . Take to be least in this intersection, and set , thus completing the stage of this recursion.

At the end, the resulting map can be extended to a map with domain in an arbitrary way, and this function clearly is as required.

Back to the proof of . Fix a perfect information winning strategy for II in , and a set cofinal in of least possible size. Pick a such that for all we have .

Given , let . Now we consider two cases, depending on whether for some we have or not.

Suppose first that for all . Then the Coding Lemma applies with in the role of , and as chosen. Let be as in the lemma.

We define as follows:

Given , let be such that , and set .

Given with , let be such that , and set .

Clearly, is winning: In any run of the game with II following , player II’s moves cover their responses following , and we are done since is winning.

The second case, when there is some with , will be dealt with in the next talk.

This entry was posted on Monday, September 27th, 2010 at 11:31 am and is filed under math.LO, Set theory seminar. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

4 Responses to Set theory seminar – Marion Scheepers: Coding strategies (II)

This is a very interesting question (and I really want to see what other answers you receive). I do not know of any general metatheorems ensuring that what you ask (in particular, about consistency strength) is the case, at least under reasonable conditions. However, arguments establishing the proof theoretic ordinal of a theory $T$ usually entail this. You […]

This is false; take a look at https://en.wikipedia.org/wiki/Analytic_set for a quick introduction. For details, look at Kechris's book on Classical Descriptive Set Theory. There you will find also some information on the history of this result, how it was originally thought to be true, and how the discovery of counterexamples led to the creation of desc […]

This is open. In $L(\mathbb R)$ the answer is yes. Hugh has several proofs of this, and it remains one of the few unpublished results in the area. The latest version of the statement (that I know of) is the claim in your parenthetical remark at the end. This gives determinacy in $L(\mathbb R)$ using, for example, a reflection argument. (I mentioned this a wh […]

A classical reference is Hypothèse du Continu by Waclaw Sierpiński (1934), available through the Virtual Library of Science as part of the series Mathematical Monographs of the Institute of Mathematics of the Polish Academy of Sciences. Sierpiński discusses equivalences and consequences. The statements covered include examples from set theory, combinatorics, […]

There is a new journal of the European Mathematical Society that seems perfect for these articles: EMS Surveys in Mathematical Sciences. The description at the link reads: The EMS Surveys in Mathematical Sciences is dedicated to publishing authoritative surveys and high-level expositions in all areas of mathematical sciences. It is a peer-reviewed periodical […]

You may be interested in the following paper: Lorenz Halbeisen, and Norbert Hungerbühler. The cardinality of Hamel bases of Banach spaces, East-West Journal of Mathematics, 2, (2000) 153-159. There, Lorenz and Norbert prove a few results about the size of Hamel bases of arbitrary infinite dimensional Banach spaces. In particular, they show: Lemma 3.4. If $K\ […]

You just need to show that $\sum_{\alpha\in F}\alpha^k=0$ for $k=0,1,\dots,q-2$. This is clear for $k=0$ (understanding $0^0$ as $1$). But $\alpha^q-\alpha=0$ for all $\alpha$ so $\alpha^{q-1}-1=0$ for all $\alpha\ne0$, and the result follows from the Newton identities.

Nice question. Let me first point out that the Riemann Hypothesis and $\mathsf{P}$-vs-$\mathsf{NP}$ are much simpler than $\Pi^1_2$: The former is $\Pi^0_1$, see this MO question, and the assertion that $\mathsf{P}=\mathsf{NP}$ is a $\Pi^0_2$ statement ("for every code for a machine of such and such kind there is a code for a machine of such other kind […]

For brevity's sake, say that a theory $T$ is nice if $T$ is a consistent theory that can interpret Peano Arithmetic and admits a recursively enumerable set of axioms. For any such $T$, the statement "$T$ is consistent" can be coded as an arithmetic statement (saying that no number codes a proof of a contradiction from the axioms of $T$). What […]

[…] Scheepers: Coding strategies (III) For the second talk (and a link to the first one), see here. The third talk took place on September […]

[…] Next talk. 43.614000 -116.202000 […]

[…] the second talk (and a link to the first one), see here. The third talk took place on September […]

[…] Set theory seminar – Marion Scheepers: Coding strategies (II) « A kind of library says: August 28, 2012 at 12:15 pm […]