This set is due Monday, October 18.
Set theory seminar – Marion Scheepers: Coding strategies (III)
September 28, 2010For the second talk (and a link to the first one), see here. The third talk took place on September 28.
In the second case, we fix an with
. We can clearly assume that
is infinite, and it easily follows that
. This is because any
can be coded by the pair
, and there are only
many possible values for the second coordinate.
In particular, is infinite, and we can fix a partition
of
into countably many pieces, each of size
. Recall that we are assuming that
and have fixed a set
cofinal in
of smallest possible size. We have also fixed a perfect information winning strategy
for II, and an
with
for all
.
For each , fix a surjection
.
We define as follows:
- Given
, let
,
and
such that
,
and set
.
- Suppose now that
, that
, and that there is an
such that
,
, and
. Let
be such that
,
and
and set
.
- Define
in other cases.
A straightforward induction shows that is winning. The point is that in a run of the game where player II follows
:
- Player II’s moves code the part that lies outside of
of player II’s moves in a run
of the game following
where I plays sets covering the sets in the original run. For this, note that at any inning there is a unique index
such that player II’s move covers
, is disjoint from
, and meets
in a set that is neither empty nor all of
, and this
codes the inning of the game, and the piece of player II’s move in
codes the history of the run
played so far.
is eventually covered completely, so in particular the parts inside
of player II’s responses in the run
are covered as well.
This completes the proof of Theorem 1.
By way of illustration, consider the case where is the ideal of finite sets of some set
. Then whether II has a winning coding strategy turns into the question of when it is that
. This certainly holds if
or if
. However, it fails if
.
This example illustrates how player II really obtains an additional advantage when playing in rather than just in
. To see that this is the case, consider the same
as above with
. This is an instance of the countable-finite game. We claim that II has a winning coding strategy in this case. To see this, consider a partition of
into countably many sets
with
. For each
, pick a winning coding strategy
for the countable-finite game on
, and define a strategy in
so that for each
it simulates a run of the game
with II following
, as follows: In inning
, II plays on
for
; player I’s moves in the “
-th board” are the intersection with
of I’s moves in
, and I’s first move occurred at inning
. (II can keep track of
in several ways, for example, noticing that, following the proof of Theorem 1 produces coding strategies that never play the empty set.)
Note that this strategy is not winning in , the difference being that there is no guarantee that (for any
) the first
moves of I in the
-st board are going to be covered by II’s responses. On the other hand, the strategy is winning in
, since, no matter how late one starts to play on the
-th board, player I’s first move covers I’s prior moves there (and so, II having a winning coding strategy for the game that starts with this move, will also cover those prior moves).
The first place where this argument cannot be continues is when . However,
suffices to see that player I has a winning strategy in
in this case, and so we can continue. This illustrates the corollary stated in the first talk, that
suffices to guarantee that II always has a winning coding strategy in
.
The natural question is therefore how much one can weaken the assumption, and trying to address it leads to Theorem 2, which will be the subject of the next (and last) talk.
Set theory seminar – Marion Scheepers: Coding strategies (II)
September 27, 2010For 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.
Set theory seminar – Marion Scheepers: Coding strategies (I)
September 25, 2010This 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 for some set
. The ideal
is not assumed to be
-complete; we denote by
its
-closure, i.e., the collection of countable unions of elements of
. Note that
is a
-ideal iff
is an ideal iff
.
The two games we concentrate on are the Random Game on ,
, and the Weakly Monotonic game on
,
.
In both games, players I and II alternate for many innings, with I moving first, moving as follows:
In we do not require that the
relate to one another in any particular manner (thus “random”), while in
we require that
(thus “weakly”, since we allow equality to occur).
In both games, player II wins iff . Obviously, II has a (perfect information) winning strategy, with
rather than the weaker
.
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 is a coding strategy, and II follows it in a run of the game, then we have that for every
,
,
with .
The underlying goal is to understand under which circumstances player II has a winning coding strategy in . Obviously, this is the case if II has a winning coding strategy in
.
Theorem 1. For an ideal
, the following are equivalent:
- II has a winning coding strategy in
.
.
Corollary.
implies that for any ideal
, II has a winning strategy in
.
We can reformulate our goal as asking how much one can weaken in the corollary.
Let’s denote by , the weak singular cardinals hypothesis, the statement that if
is singular strong limit of uncountable cofinality, then for no cardinal
of countable cofinality, we have
.
By work of Gitik and Mitchell, we know that the negation of is equiconsistent with the existence of a
of Mitchell order
.
Theorem 2. The following are equivalent:
.
- For each ideal
on a singular strong limit
of uncountable cofinality, II has a winning strategy in
.
We now begin the proof of Theorem 1.
Suppose II has a winning coding strategy
in
. We want to show that
. For this, we will define a map
with
-cofinal range, as follows: Given
, let
and
for all
. Now set
.
To see that is cofinal, given
, let
, so that the
are II’s responses using
in a run of the game where player I first plays
and then plays
in all its subsequent moves. Since
is winning, we must have
.
507 – Problem list (I)
September 21, 2010This is the list of “problems of the day” mentioned through the course.
(Thanks Nick Davidson and Summer Hansen.)
- Frankl’s union-closed sets problem: If a finite collection of finite non-empty sets is closed under unions, must there be an element that belongs to at least half of the members of the collection?
- The inverse Galois problem: Is every finite group a Galois group over
?
- 1. Are there infinitely many Mersenne primes? 2. Are there infinitely many Fermat primes?
- For every positive
, is there a prime between
and
?
- Does the dual Schroeder-Bernstein theorem imply the axiom of choice?
- The Schinzel–Sierpiński conjecture: Is every positive rational of the form
for some primes
and
? (The links require a BSU account to access MathSciNet.)
- Are there infinitely many twin primes?
- Are there any odd perfect numbers?
- Is the Euler-Mascheroni constant
irrational?
- Is
a primitive root modulo
for infinitely many primes
? More generally, does Artin’s conjecture hold?
170- Quiz 4
September 20, 2010Quiz 4 is here. Please remember that the first midterm is this Wednesday.
Solutions follow.
Sadness
September 19, 2010A week ago a friend gave us some impossibly sad news. I cannot even imagine what he and his wife are going through, how they are coping. I know I would not be able to do it as publicly as he is. My heart is broken, and I find myself wanting for words. Javier, know that we are here for you.
Mathematical Ancestry
September 13, 2010This thing of beauty was my Father’s day gift this June. The gigantic poster is in my office at home.
Besides its being obviously intimidating and fun, it adds to my usual angst with an odd sense of responsibility. Here is a link to The Mathematics Genealogy Project.