# Equivalences of $\diamondsuit$-principle.

I'm working on exercises from Kunen and I'm stuck. I must proof that the following are equivalent:

1. There exists a sequence $\langle A_\alpha:\alpha<\omega_1\rangle$ such that $\forall\alpha(A_\alpha\subset\alpha)$ and for all $A \subset \omega_1$ the set $\{\alpha \in \omega_1:A\cap\alpha=A_\alpha\}$ is stationary. ($\diamondsuit$-principle)
2. There exists a sequence $\langle A_\alpha:\alpha<\omega_1\rangle$ such that $\forall\alpha(A_\alpha\subset\alpha\times\alpha)$ and for all $A \subset \omega_1\times\omega_1$ the set $\{\alpha \in \omega_1:A\cap\alpha\times\alpha=A_\alpha\}$ is stationary.
3. There exists a sequence $\langle f_\alpha:\alpha<\omega_1\rangle$ such that $\forall\alpha(f_\alpha:\alpha\rightarrow\alpha)$ and for all $f : \omega_1\rightarrow\omega_1$ $\exists\alpha(f|\alpha=f_\alpha\wedge\alpha>0)$
4. There exists a sequence $\langle f_\alpha:\alpha<\omega_1\rangle$ such that $\forall\alpha(f_\alpha:\alpha\rightarrow\alpha)$ and for all $f : \omega_1\rightarrow\omega_1$ the set $\{\alpha \in \omega_1:f|\alpha=f_\alpha\}$ is stationary.

I have proved that $1\implies 2\implies 4\implies 3$ and that $4\implies 1,$ but I'm having problems on proving that $3\implies$ "something", because it only talks about one $\alpha$. Can someone help me?

• You may want to take a look at Variations on $\diamondsuit$, by K. Devlin, The Journal of Symbolic Logic, 44 (1), (1979), 51-58. Jul 24, 2013 at 5:43
• @AndresCaicedo I'm surprised. Don't people have a "name" for $\diamondsuit$?
– Pedro
Jul 24, 2013 at 6:02
• @PeterTamaroff I'm not sure I understand. Jul 24, 2013 at 6:07
• @AndresCaicedo I mean, is it called the "Diamond Principle" or something like that?
– Pedro
Jul 24, 2013 at 6:13
• @PeterTamaroff Oh, I see. Yes, it is the diamond principle. (There is also a $\square$ (square) principle, though some people call it box.) Terrible notation in both cases, obviously. Jul 24, 2013 at 6:15

Okay, I think I've made it.

Let $\langle f_\alpha: \alpha < \omega_1\rangle$ be a sequence satisfying $(3)$. For each $\alpha$, let $U_\alpha=ran(f_\alpha)$. We will show that if $A\subset \omega_1$ e $|A|\geq\omega$ then $\{\alpha \in \omega_1:A\cap\alpha=U_\alpha \}$ is stationary. Now we let $B_\alpha=[\alpha]^{<\omega}\cup\{A_\alpha\}$, and we have that $\langle B_\alpha: \alpha < \omega_1\rangle$ is clearly a $\diamondsuit^-$-sequence, and therefore $\diamondsuit$ holds.

First we suppose that $|A|=\omega_1$. We can write $A=\{a_\alpha: \alpha<\omega_1\}$ Let $D=\{d_\alpha:\alpha<\omega_1\}$ c.u.b., written in the increasing order. First we construct a subset $C$ of $D$. We want every two consecutive elements of $C$ to have $\omega$ elements between them, and before the first element of $C$ we want $\omega$ elements. We also want $C$ to be c.u.b. We construct $C=\{c_\alpha:\alpha<\omega_1\}$ by induction: We let $c_0$ be some element of $D$ greater than $a_\omega$. Chosen $c_\alpha$, there exists $b_\beta>c_\alpha$. We let $c_{\alpha+1}$ be some element of $D$ greater than $b_{\beta+\omega}$. If $\gamma$ is a limit, we let $c_\gamma=\sup_{\alpha<\gamma}c_\alpha$. This way $C$ is what we want.

We show that $C$ intersects $\{\alpha<\omega_1:A\cap\alpha=ran(f_\alpha)\}$, and, since $D$ is arbitrary, this set is stationary. We construct a function $f:\omega_1\rightarrow\omega_1$ satisfying:

1. If $\xi>0$ and $\xi\neq c_\gamma$, $\gamma$ limit, then $f_\xi\neq f|\xi$
2. If $\gamma$ is a limit then $ran(f|c_\gamma)=A\cap c_\gamma$

After constructing $f$, by the hypothesis, there exists $c_\gamma\in C$, $\gamma$ limit such that $f|c_\gamma=f_{c_\gamma}$. Then, taking the image on both sides, we have $A\cap c_\gamma=A_{c_\gamma}$, therefore $C$ intersects our set. Let us construct such function.

We shall construct $f$ by induction, defining $f|c_\alpha$ in each inductive step. Let $A_0=\{a\in A:a<c_0\}$ and for every successor $\beta+1$ we let $A_{\beta+1}=\{a\in A: c_\beta\leq a<c_{\beta+1}\}$. Each of these sets are countable. We can enumerate each of them, writing $A_\beta=\{a^\beta_n: n \in \omega\}$, and letting $a^\beta_0$ be the smallest element of this set. Now we begin the construction:

Step $0$: We let $f(a^0_n)=a^1_n$ for each $n$, and $f(\xi)=a^1_0$ if $\xi\notin A_0, \xi < c_0$. Then of course if $\alpha<c_0$ then $f_\alpha\neq f|\alpha$, since each $f_\alpha\in \alpha^\alpha$. Therefore $(a)$ is satisfied. Since there is no $c_\gamma$ wih $\gamma$ limit in this interval, $(b)$ is satisfied.

Successor step: Having defined $f|c_\beta$ satisfying $(a)$ and $(b)$, we extend it's definition to $f|c_{\beta+1}$ as follows: If $\beta$ is successor or $0$, we let, for all $n \in \omega$, $f(a^{\beta+1}_{2n})=a^{\beta+2}_n$, $f(a^{\beta+1}_{2n+1})=a^{\beta}_n$ and $f(\xi)=a^{\beta+2}_0$ if $\xi \notin A_{\beta+1}$ and $c_\beta\leq \xi < c_{\beta+1}$. If $\beta$ is limit we act like on step 0: We let $f(a^{\beta+1}_n)=a^{\beta+2}_n$ and $f(\xi)=a^{\beta+2}_0$ for $\xi\notin A_0, \xi < c_0$. $(b)$ is satisfied because we didn't add any $c_\gamma$ with $\gamma$ limit in this extension, in both cases. $(a)$ is satisfied because $f(c_\beta)\geq c_{\beta+1}$ in both cases.

Limit step: Let $\gamma$ be limit. We let $f|c_\gamma=\bigcup_{\alpha<\gamma}f|c_\alpha$, a union of compatible functions. For this step we must only check $(b)$ is satisfied. If $\delta \in \omega_1\cap c_\gamma$ then $\delta \in A_\beta$ for some $\beta<\gamma$ and $\delta=a^\beta_n$ for some $n$. We have $f(a^{\beta+1}_{2n+1})=\delta$, by construction, and $a^{\beta+1}_{2n+1}<c_{\beta+1}<c_\gamma$, then $\delta \in ran(f|c_\gamma)$. On the other hand, if $\delta \in ran(f|c_\gamma)$ then there exists $\xi<\gamma$ such that $f(\xi)=\delta$. We have constructed the function so that $ran(f|c_\gamma)\subset A$. There exists $\beta<\gamma$ such that $\xi < c_{\beta}$ By construction, $\delta=f(\xi)<c_{\beta+1}<c_\gamma$, and therefore $A\cap c_\gamma=U_\gamma$.

Now lets finish with the case $|A|=\omega$. Let $\beta=\sup A$. We shall show that the set $\{\alpha<\omega_1:A\cap\alpha=ran(f_\alpha)\}$ is stationary. Given $D$ c.u.b., there exists a subset $C=\{c_\alpha: \alpha < \omega_1\}$ of $D$ also c.u.b. with a shift of $\omega$ elements between each two elements of $C$ (just use $A=\omega_1$ in the construction of the $\omega_1$ case). We can also suppose that between $\beta$ and $\min C$ there exists $\omega$ limit ordinals, since $D-(\beta+\omega.\omega)$ is c.u.b.

We will construct a function $f: \omega_1 \rightarrow \omega_1$ such that $f|\alpha\neq f_\alpha$ if $\alpha \notin C$ e $\alpha>0$ and such that $ran(f|\alpha)=A\cap \alpha$ whenever $\alpha \in C$. Therefore, by our hypothesis, there exists $\alpha \in C$ such that $A\cap \alpha = U_\alpha$, and, since $D$ is arbitrary, our set is stationary.

We split in two cases: $|\{x \in A: x<\omega\}|=\omega$ and $|\{x \in A: x<\omega\}|< \omega$. We shall first work in the first case, which is more complicated. We shall adopt the following strategy: we construct the function by induction until $f|c_0$. Later we will use another recursion to construct the remaining.

Let $B=\{x \in A: x<\omega\}$. We can write $B=\{b_n: n \in \omega\}$. Let $L=\{\alpha < c_0: \alpha \text{ is limit}\}$. Since this set is countable, we can write $L=\{l_n: n \in \omega\}$. Let $M=\{\alpha < c\_0: \alpha>\beta\}$ if $supA \in A$ or $M=\{\alpha < c\_0: \alpha\geq \beta\}$ otherwises. In both cases $M=\{m_n: n \in \omega\}$.

For $n \in \omega$ we define a sequence $d_n$ as follows:\ Chosen $d_p: (p<n)$, let $j=f_{m_n+1}(m_n)$. There exists $k \in \omega$ com $b_k \neq j$ and $b_k \neq b_{d_p}$ if $p <n$. We let $d_n=k$. We define, for each $n$, $f(d_n)=\text{"some element of a distinct from} f_{l_n}(d_n) \text{ and from} f_{d_n+1}(d_n)\text{"}$. For the $\xi<\omega$ different from all $d_n$, and $\notin A$ we let $f(\xi)\in A$ distinct from $f_{\xi+1}(\xi)$. For $\alpha\in A$ smaller $\omega$ different from all $d_n$, we let $f(\alpha)=\alpha$. We also let $f(m_n)=b_n$. Note that now, there is no chance for $f_\gamma=f|\gamma$ if $\gamma<c_0$ is a limit, because both will be different in a natural number. Besides that, by now, the function only assumes values on $A$ and assumes every ordinal of de $A \cap \omega$, and for all positive natural $n$, $f_n\neq f|n$ since $f_n(n-1)\neq f(n-1)$, because $f_n: n\rightarrow n$. As a last observation, notice that $f$ is already defined between $\beta$ e $c_0$ and that for the ordinals $\xi$ in this interval, $f(\xi)\neq f_{\xi+1}(\xi)$.

Following the idea of the preceding paragraph, for all $\omega\leq\xi<\beta$ (or $\leq$, in case $\beta \in A$), we let $f(\xi)=\xi$ if $\xi \in A$ and let $f(\xi)$ be some $x$ such that $x \in A$ e $x \neq f_{\xi+1}(\xi)$. By the same argument, the function is defined until $c_0$ so that $f_\alpha\neq f|\alpha$ if $0<\alpha<c_0$. Notice that $ran(f|c_0)=A$.

Now, by induction, we shall construct $f|c_\alpha$ in each inductive step. Before we begin, let $A_\alpha=\{\delta \in A: c_\alpha<\delta<c_\alpha+1\wedge \delta \text{ is limit}\}$. In words, $A_\alpha$ is the set of all limits between $c_\alpha$ and it's successor in $C$. We can write $A_\alpha={a^\alpha_n: n \in \omega}$ with $a^\alpha_0=\min A_\alpha$. Ps: if $A_\alpha$ is finite, It's enumeration has repetitions.

Step 0: Written above.

Successor step: Suppose $f|c_\alpha$ is already constructed. If $A_\alpha$ is empty, We simply let $f(\delta)$ be some element of $A$ different from $f_{\delta+1}(\delta)$ for each $\delta$ such that $c_\alpha \leq \delta <c_{\alpha+1}$. Otherwises, let $B=\{\xi<a^{\alpha}_0:\xi\geq c_\alpha\}$. This set is countable. We can write $B=\{d_n: n \in \omega\}$. for each $n$, we let $f(d_n)$ be an element of $A$ distinct from $f_{d_n+1}(d_n)$ and from $f_{a^{\alpha}_n}(d_n)$. For those $\delta$ such that $a^{\alpha}_0 \leq \delta <c_{\alpha+1}$, we let $f(\delta)$ be an element of $A$ different from $f_{\delta+1}(\delta)$.\ Notice that the range of our function is the same as before after this step, and that if $c_\alpha<\delta<c_\alpha+1$ then $f|\delta\neq f_\delta$ since if $\delta=\gamma+1$ is a successor we have $f_{\gamma+1}(\gamma)\neq f(\gamma)$ and if $\delta$ is limit, $\delta=a^\alpha_n$ for some $n$, therefore $f(d_n)\neq f_{a^\alpha_n}(d_n)$, as we wanted.\

Limit step: If $f|c_\alpha$ is already constructed for all $\alpha<\gamma$, a limit, we let $f|c_\gamma$ be the union of all $f|c_\alpha$, which are compatible.

This way we treat case 1. For case 2, we only need to change the 0 step of the induction. The successor case and the limit case will be the same, and therefore omited.

Step 0: If $|\{\alpha \in A: \alpha < \omega\}|<\omega$, then $|\{\alpha \in \omega_1 - A: \alpha < \omega\}|=\omega$. We enumerate this set and call it $B=\{b_n: n \in \omega\}$. Let $L$ be as in the first case. We let, for each $b_n$, $f(b_n)$ be some element of $A$ different $f_{b_n+1}(b_n)$ and from $f_{l_n}(b_n)$. for all $\alpha \in A$ we let $f(\alpha)=\alpha$ and for each $\alpha \notin A$ with $\omega\leq \alpha < c_0$ we let $f(\alpha)$ be an element from $A$ different from $f_{\alpha+1}(\alpha)$. This way, if $0<\delta<c_0$ then $f|\delta\neq f_\delta$ since if $\delta=\gamma+1$ is a successor, $f_{\gamma+1}(\gamma)\neq f(\gamma)$, and if it's a limit, e.g. $\delta =l_n$, then $f(b_n)\neq f_{l_n}(b_n)$. Notice that $ran(f|c_0)=A$.