Partiti

February 1, 2019

Partiti is a puzzle created by Thinh Van Duc Lai, a Vietnamese puzzle enthusiast most of whose puzzles involve mathematics in some form. His work has been featured in The New York Times, see here. Partiti puzzles appeared on Mathematics Magazine throughout 2018.

Brittany Shelton and I coauthored a short piece introducing the puzzle to the Magazine readers at the invitation of Michael Jones, the magazine editor and a colleague at Mathematical Reviews. It is titled Of puzzles and partitions. Introducing Partiti, and can be found on the arXiv or through my papers page.

Advertisements

The fourteen Victoria Delfino problems and their status in the year 2019

February 1, 2019

The Cabal seminar in southern California was instrumental to the development of determinacy. The Delfino problems were suggested as a way to measure progress on this area. Fourteen problems were suggested in total through the years. Some were solved very quickly after their proposal, a few remain open.

Benedikt Löwe and I wrote a survey of their current status, cleverly titled The fourteen Victoria Delfino problems and their status in the year 2019. The cleverness has forced us to keep changing its title as its publication date kept being postponed. It is scheduled to appear in the fourth volume of the reissued Cabal volumes, which I am told is expected to finally be published this year. The volumes are being published by the Association for Symbolic Logic and Cambridge University Press as part of the Lecture Notes in Logic series.

The survey can be accessed through the Hamburger Beiträge zur Mathematik preprint server; it is paper 770 there. It can also be found through my papers page (currently under notes, and later on, once it appears, under papers).


Smullyan

August 11, 2016

I have just posted on my papers page a preprint of a review of

MR3379889
Smullyan, Raymond
Reflections—the magic, music and mathematics of Raymond Smullyan.
World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. x+213 pp.
ISBN: 978-981-4644-58-7; 978-981-4663-19-9

that I have submitted to Mathematical Reviews.


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.


Mathematical Ancestry

September 13, 2010

This 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.