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?

  • 3
    $\begingroup$ You may want to take a look at Variations on $\diamondsuit$, by K. Devlin, The Journal of Symbolic Logic, 44 (1), (1979), 51-58. $\endgroup$ Jul 24, 2013 at 5:43
  • $\begingroup$ @AndresCaicedo I'm surprised. Don't people have a "name" for $\diamondsuit$? $\endgroup$
    – Pedro
    Jul 24, 2013 at 6:02
  • 1
    $\begingroup$ @PeterTamaroff I'm not sure I understand. $\endgroup$ Jul 24, 2013 at 6:07
  • $\begingroup$ @AndresCaicedo I mean, is it called the "Diamond Principle" or something like that? $\endgroup$
    – Pedro
    Jul 24, 2013 at 6:13
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 24, 2013 at 6:15

1 Answer 1


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

Ps: sorry for bad english.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.