Recall Jensen’s diamond principle over a stationary subset $S$ of a regular uncountable cardinal $\kappa$: there exists a sequence $\langle A_\alpha\mid \alpha\in S \rangle$ such that $\{\alpha\in S\mid A\cap\alpha=A_\alpha\}$ is stationary for every $A\subseteq\kappa$. Equivalently, there exists a sequence $\langle f_\alpha:\alpha\rightarrow\alpha\mid \alpha\in S\rangle$ such that $\{\alpha\in S\mid f\restriction\alpha=f_\alpha\}$ is stationary for every function $f:\kappa\rightarrow\kappa$.

It is clear that $\diamondsuit(S)$ implies $\diamondsuit(T)$ whenever $S\subseteq T\subseteq\kappa$. Shelah proved that it is consistent that $\diamondsuit(S)$ holds, and at the same time $\diamondsuit(\omega_1\setminus S)$ fails, for some stationary co-stationary subset $S$ of $\omega_1$. Somewhat complimentary to the latter, Devlin proved that if $\diamondsuit(\kappa)$ holds, then there exists a sequence $\langle S_i\mid i<\kappa\rangle$ of pairwise disjoint subsets of $\kappa$ such that $\diamondsuit(S_i)$ holds for each $i<\kappa$.

Devlin’s gem has two surprising features. The first feature is that — for an unclear reason — many people are unaware of Devlin’s finding.

The second surprising feature is that Devlin’s proof is not entirely trivial:

Devlin defines the ideal $ND(\kappa)$ of all subsets $S$ of $\kappa$ on which $\diamondsuit(S)$ fails, proves that it is $\kappa$-complete (via Kunen’s trick for proving that $\diamondsuit^-(S)$ entails $\diamondsuit(S)$), and recalls that a $\kappa$-complete prime ideal on $\kappa$ cannot be second-order definable. Altogether, $ND(\kappa)$ is not $\kappa$-saturated.

In this short post, I’ll give a sincerely trivial proof.

**Proof of Devlin’s gem.** Let $\langle f_\alpha:\alpha\rightarrow\alpha\mid \alpha<\kappa\rangle$ be s.t. $G(f)=\{\alpha<\kappa\mid f\restriction\alpha=f_\alpha\}$ is stationary for every function $f:\kappa\rightarrow\kappa$. Write $S_i:=\{\alpha<\kappa\mid f_\alpha(0)=i\}$ for all $i<\kappa$. For every $\alpha<\kappa$, let $g_\alpha:=\bigcup\{ f_{f_\alpha(\beta)}\mid 0<\beta<\alpha\}$.

We claim that $\langle g_\alpha\mid \alpha\in S_i\rangle$ witnesses $\diamondsuit(S_i)$ for each $i<\kappa$. To see this, let $i<\kappa$ and $f:\kappa\rightarrow\kappa$ be arbitrary.

Define $g:\kappa\rightarrow\kappa$ by letting $g(0):=i$, and $g(\beta):=\min(G(f)\setminus\beta)$ whenever $0<\beta<\kappa$. As $G(g)$ is a stationary subset of $S_i$, it suffices to show that $f\restriction\alpha=g_\alpha$ for all limit $\alpha\in G(g)$. Let $\alpha\in G(g)$ be a limit ordinal. Then for all nonzero $\beta<\alpha$, $g(\beta)=f_\alpha(\beta)<\alpha$, and hence $f\restriction\beta\subseteq f_{f_\alpha(\beta)}\subseteq f\restriction\alpha$. That is, $g_\alpha=f\restriction\alpha$. $\square$

Note that the same proof shows that if $\diamondsuit(T)$ holds, then there exists a sequence $\langle S_i\mid i<\kappa\rangle$ of pairwise disjoint subsets of $T$ such that $\diamondsuit(S_i)$ holds for each $i<\kappa$.

Note also that unlike Devlin’s proof, the above proof does not build on the fact that $\kappa$ may be partitioned into $\kappa$ many pairwise disjoint stationary sets.

Gems, diamonds, it’s a good thing we don’t have a typeset of rubies, emeralds and whatnots, or else combinatorial set theory would have been filled with them!

1 likes

Combinatorial candy crush. Sweet!

0 likes

I dare you to write an expository paper with this title. 😀

0 likes

This reminds me of the various jokes about what mathematicians call “trivial”. I stared at this on the screen for hours before I eventually figured out what’s going on here.

The problem is that $g_\alpha$ is not necessarily a well-defined function for every $\alpha$. Even if it is a function, its domain may not be $\alpha$. Subtly included in the last part of the proof is the derivation that for sufficiently many $\alpha$, the relation $g_\alpha$ is in fact a function with domain $\alpha$. Maybe this should be explained.

Actually the claim that $\langle g_\alpha\mid\alpha\in S_i\rangle$ witnesses $\diamondsuit (S_i)$ is therefore not correct, since to be diamond sequence requires that for every $\alpha$, $g_\alpha$ should be a function $\alpha \to \alpha$. The definition of $g_\alpha$ should be modified by appending “… if this is a function with domain $\alpha$, and an arbitrary function from $\alpha$ to $\alpha$ otherwise.” This modification would have the dual effect of making the claim technically correct and also alerting the reader to the correct understanding of what is happening in the proof.

1 likes

You are right, though the subtly is actually in what I mean by “witnesses $\diamondsuit$” (as opposed to “is a $\diamondsuit$-sequence”).

Generally speaking, I tend to define diamond as a sequence that guesses a particular type of object (e.g., a subset of $\omega_1$), without putting additional requirements on the sequence (e.g., that the $\alpha_{th}$ member of the sequence be a subset of $\alpha$). See here.

0 likes