This version of the question is meant to avoid assuming the continuum hypothesis (as is done in the link below) and clarify the notation.

Question Involving Strength of Fodor's Lemma, CH Assumption


Must there be a minimum element $\kappa \in \omega_1$ where $\kappa \in \phi_{\omega}(\kappa)$ given the definitions below?

Note that there is some $\kappa \in \omega_1$ where $\kappa \in \phi_{\alpha}(\kappa)$ for each $\alpha < \omega$ due Fodor's lemma (Fodor would have each element of $\{ \kappa : \kappa \in \phi_{\alpha}(\kappa) \}$ map to a constant for each $\alpha$ in $\omega$ should $\phi_{\alpha}$ be fully regressive instead of just almost regressive. The comments in the above link address the meaning of almost regressive and fully regressive).

Optional Second Question:

Is $C$ both countable and non-empty on each iteration ($C$ is defined as a local variable within the definition of sequence $T$, step 2, sub-step d)?

Where $a,b$ are ordinals:

1) $a=b$ does not imply $(a,b) = (a) = (b)$. 2) $a \neq b$ does not imply $(a,b) = (b,a)$.

Define $t(\alpha)$ and $t^{-1}(\alpha)$ for any ordinal $\alpha \geq 2$:

Let $t(\alpha)$ equal a doublet of ordinals $(a,b)$ if $\alpha = 2$, a triplet of ordinals $(a,b,c)$ if $\alpha = 3$, a quadruplet of ordinals $(a,b,c,d)$ if $\alpha = 4$, and so on, for any ordinal $\alpha$. Similarly, let $t^{-1}(x)$ equal $2$ for any doublet of ordinals $x$, $3$ for any triplet of ordinals $x$, $4$ for any quadruplet of ordinals $x$, and so on, as determined by the order type of $x$.

Use of set builder notation:

Consider the set of all doublets of ordinals such that each element of each doublet is a member of $\omega_1$. It will become helpful to use set-builder notation in the following manner to define such a set: $$\{t(2) : a,b \in t(2) \implies a,b \in \omega_1 \} = \{ (a,b) : a,b \in \omega_1 \} = \{(0,0),(0,1),(1,0),(a \in \omega_1,b \in \omega_1),\dots\}$$

Define the set $P$:

$$P = \{ t(\omega) : a,b,c,\dots \in t(\omega) \implies a,b,c,\dots \, \text{is a computable sequence} \, \text{and } a,b,c, \dots \in \{0,1\} \} \equiv \, \text{the set of computable binary sequences}$$

Define the functions $(r_{\alpha})_{\omega \leq \alpha < \omega_1}$:

Let $r_{\alpha} : \alpha \rightarrow \omega$ be bijective.

Define 'Likewise Computable':

Let $t(\alpha) = ((\beta + a)_0, (\beta + b)_1, (\beta + c)_2, \dots)$ be likewise computable for any ordinal $\alpha$ if and only if $\omega \leq \alpha < \omega_1$, $\beta \in \omega_1$, and an $\omega$-type ordering by index $( (\gamma)_{r_{\alpha}^{-1}(0)}, (\zeta)_{r_{\alpha}^{-1}(1)}, (\mu)_{r_{\alpha}^{-1}(2)},\dots )$ of the $\alpha$-type ordering $( a_{r_{\alpha}(0)}, b_{r_{\alpha}(1)}, c_{r_{\alpha}(2)},\dots )$ is an element of $P$.

Define the functions $(\phi_{\alpha})_{2 \leq \alpha < \omega_1}$:

Let each element of $(\phi_{\alpha})_{2 \leq \alpha < \omega_1}$ be almost regressive such that:

1) $$\alpha < \omega \implies \phi_{\alpha} : \omega_1 \setminus \{0\} \rightarrow \{ t(\alpha) : a,b,c,\dots \in t(\alpha) \implies a,b,c,\dots \in \omega_1 \} \text{ is bijective},$$

2) $$\alpha \geq \omega \implies \phi_{\alpha} : \omega_1 \setminus \{0\} \rightarrow \{ t(\alpha) : a,b,c,\dots \in t(\alpha) \implies a,b,c,\dots \in \omega_1 \, \text{and } t(\alpha) \, \text{is likewise computable}\} \text{ is bijective},$$

3) $a,b,c,\dots \leq \kappa$ for each $a,b,c,\dots \in \phi_{\alpha}(\kappa)$, and

4) $\zeta < \alpha \implies \min\{ \phi_{\zeta}^{-1}(b) : \exists k \in b \text{ where } k \geq \phi_{\zeta}^{-1}(b)\} < \min\{ \phi_{\alpha}^{-1}(b) : \exists k \in b \text{ where } k \geq \phi_{\alpha}^{-1}(b)\}$.

Define function $f$:

$$f(x) = \begin{cases} \phi_{t^{-1}(x)}^{-1}(x) & \text{if, given } x \, \text{has order type } \alpha, 2 \leq \alpha < \omega \, \text{or } x \, \text{is likewise computable} \\ \text{empty string} & \text{otherwise} \\ \end{cases}$$

Define $k(\alpha)$ for any ordinal $\alpha \in \omega_1$:

$$k(\alpha) = \{ x : f(x) = \alpha \}$$

Define function $h$:

$$h(\alpha) = \begin{cases} min\{ t^{-1}(x) : x \in k(\alpha) \text{ and } \forall y \in x(y < \alpha) \} & \text{if } \alpha \in \omega_1 \\ 1 & \text{otherwise} \\ \end{cases}$$

Define function $g$:

For any set of ordinals, $A$, let $g(A)$ be the set of all ordered doublets, triplets, quadruplets, and so on, that can be comprised from the elements of $\omega_1 \cap A$: $$g(A) = \{ t(\alpha) : t(\alpha) \setminus (A \cap \omega_1) = \emptyset \text{ and } 2 \leq \alpha < \omega_1 \}$$

Define the sequence $T$:

Define a (potentially transfinite) sequence $T = t_1, t_2, t_3, \dots$ over $\omega_1$ iterations where:

Step 1) Let $t_1 = 0, t_2 = 1, t_3 = 2$, and iteration counter $m = 1$.

Step 2) Each $t_n$, where $n \geq 4$, is defined by the previous elements of the sequence. Starting with $n = 4$:

a) If $m$ is a countable limit ordinal and $T$ is of order type $\omega$, free up space in $T$ by first letting $(s_n)_{n \in \mathbb{N}}$ be defined for odd indexes and undefined for even indexes: $s_{n \cdot 2 - 1} = t_{n}$. Then, set $t_1 = s_1, t_2 = s_2, t_3 = s_3, \dots$. Finally, if $m = \omega$, set $t_j$ undefined for any index $j > i$ where $t_j = t_i$ and $i,j < \omega$.

b) Let $A = \{ t_i \in T : i < n \}$. E.g., $A = \{0, 1, 2 \}$ on the first iteration.

c) Let $B = \{ f(x) : x \in (g(A) \setminus \{ y \in g(A) : t^{-1}(y) \neq h(f(y))\} ) \}$. Using the previous elements of the sequence $A$, this step creates a set $B$ of all the new ordinals implied by letting function $f$ range over $g(A)$. The restriction of $g(A)$ to $A \cap \omega_1$ ensures that $B$ remains countable for this particular $T$ sequence.

d) Let $C = B \setminus A$ and let $c_1, c_2, c_3, \dots$ be an enumeration of $C$ that is also well ordered if $|C| \neq \aleph_0$. This step removes any redundant elements from $B$ before potentially well ordering them so that we can add them to $T$.

e) If $|C| < \aleph_0$ or if a transfinite $T$ is desired, set $t_n = c_1, t_{n+1} = c_2, t_{n+2} = c_3, \dots$ and then proceed to step 3. If a transfinite $T$ is not desired, proceed to sub-step f.

f) Let $T’ = t’_1, t’_2, t’_3, \dots$ be a subsequence of the remaining undefined elements of $T$ and set $t’_1 = c_1, t’_3 = c_2, t’_5 = c_3, \dots$.

Step 3) Let $j$ be the first ordinal such that $t_j$ is undefined. If $j>n$, set $n = j$. Increase the iteration counter by letting $m = m + 1$, and then repeat step 2.

  • $\begingroup$ There is a correctable issue in that $\phi_{\omega}$ and higher can't be bijective the way these are defined. This question was posted in too hasty a fashion. I apologize and will fix here shortly. $\endgroup$ – AplanisTophet Nov 9 '19 at 3:08
  • $\begingroup$ I believe it is still confusing. Your $\omega$-type ordering is written down as if it is an $\alpha$-type ordering. I guess you mean that you reorder the terms of the $\alpha$-type according to $r_\alpha$ such that the resulting sequence has order type $\omega$? $\endgroup$ – Vsotvep Nov 9 '19 at 3:34
  • $\begingroup$ Yes, exactly. Once the $\alpha$ type ordering is reordered into an $\omega$ type ordering and the constant $\beta$ is dropped, the sequence can be evaluated as either being in or not in $P$. $\endgroup$ – AplanisTophet Nov 9 '19 at 3:36
  • 2
    $\begingroup$ It helps to see sequences as functions; a sequence $x$ with order-type $\alpha<\omega_1$ is a function $x:\alpha\to\omega_1$. Then we can get a sequence with order type $\omega$ by taking some bijective $r_\alpha:\omega\to\alpha$ and considering the function $x\circ r_\alpha:\omega\to\omega_1$ $\endgroup$ – Vsotvep Nov 9 '19 at 3:36
  • $\begingroup$ I very much appreciate you looking over things some Vsotvep. I see a minor clerical change that I can make to the definition of $B$ by using $y$ instead of $x$. It currently reads $B = \{ f(x) : x \in (g(A) \setminus \{ x \in g(A) : t^{-1}(x) \neq h(f(x))\} ) \}$. I am changing it to $B = \{ f(x) : x \in (g(A) \setminus \{ y \in g(A) : t^{-1}(y) \neq h(f(y))\} ) \}$. If you (anyone) sees anything else that could be clarified further, please let me know and thank you. Otherwise, I do not intend to inconvenience by editing further so please don't hesitate to attempt the question(s)! $\endgroup$ – AplanisTophet Nov 9 '19 at 13:38

As I'm trying to answer my own question here, please feel free to up (down) vote or provide a better answer. I will leave the question open.

Proof Statement: There must exist an element $\kappa \in \omega_1$ such that $\kappa \in \phi_{\omega}(\kappa)$.

Incorporate the definitions from above.

Define the function $\psi(\gamma)$ for $\gamma \in \omega_1 \setminus \{0\}$:

$$\psi(\gamma) = \{ t(\omega) : a,b,c,\dots \in t(\omega) \implies 0 \leq a,b,c,\dots < \gamma \, \text{and } t(\omega) \, \text{is likewise computable}\}$$

Define the ordinal $\upsilon(\gamma)$ for $\gamma \in \omega_1 \setminus \{0\}$:

$$\upsilon(\gamma) = \{ x \in \omega_1 : x < sup\{ \phi_{\omega}^{-1}(y) : y \in \psi(\gamma) \} \}$$

We have $\gamma < \beta \implies \upsilon(\gamma) \leq \upsilon(\beta)$. Also, we have that $\{ \upsilon(\gamma) : \gamma \in \omega_1 \}$ must be unbounded in $\omega_1$. We can consider the set $L$:

$$L = \{ x \in \omega_1 \setminus \{0\} : \forall y \in x (\upsilon(y) < \upsilon(x)) \}$$

Where $|L| = |\omega_1|$ (because $sup\{ \phi_{\omega}^{-1}(y) : y \in \psi(\gamma) \} \in \omega_1$ implies $\upsilon(\gamma) \in \omega_1$ for any $\gamma \in \omega_1$, assuming $\omega_1$ has cofinality $\omega_1$), we can start to wrap up the proof.

Define the function $\varrho$:

$$\varrho(\alpha_i) = \gamma_i, \, \text{given the well orderings } \alpha_i \in (\omega_1, <) \, \text{and }\gamma_i \in (L,<)$$

Define the normal function $\xi$ for $\alpha \in \omega_1$:

$$\xi(\alpha) = \upsilon(\varrho(\alpha))$$

There must be a first fixed point according to the fixed point lemma for normal functions. The fixed points of function $\xi$ are exactly the elements of $\{ x \in \omega_1 : x \in \phi_{\omega}(x) \}$. Therefore, let $\kappa = min\{ x \in\omega_1 : \xi(x) = x \} = min\{ x \in \omega_1 : x \in \phi_{\omega}(x) \}$. $\square$


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.