I Enumerating a Large Ordinal

AplanisTophet

Summary
Assistance is requested. An understanding of Fodor's Lemma, club sets, and normal functions is required.
The following assertion quoted from the paper below seems as though it couldn’t be true. It is the issue that I would like some help addressing please:

“The restriction of $g(A)$ to $A \cap \omega_1$ ensures that $B$ remains countable for this particular $T$ sequence.”
...

Define $t(\alpha)$ for any ordinal $\alpha \geq 2$:
Let $t(\alpha)$ equal a doublet of variables $(a,b)$ if $\alpha = 2$, a triplet of variables $(a,b,c)$ if $\alpha = 3$, a quadrulplet of variables $(a,b,c,d)$ if $\alpha = 4$, and so on, for any ordinal $\alpha$. Note that this notation is used to avoid confusion as $a=b$ does not imply $(a,b) = (b,a) = (a) = (b)$, whereas it does imply $\{a,b\} = \{b,a\} = \{a\} = \{b\}$ in general.

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

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

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

3) $\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) = \phi_{t^{-1}(x)}^{-1}(x)$$
Define $k(\alpha)$ for any ordinal $\alpha$:
$$k(\alpha) = \{ x : f(x) = \alpha \}$$
Define $h(\alpha)$ for any ordinal $\alpha$:
$$h(\alpha) = min\{ t^{-1}(x) : x \in k(\alpha) \text{ and } \forall y \in x(y < \alpha) \}$$
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$.
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 \{ x \in g(A) : t^{-1}(x) > h(f(x))\} ) \}$. 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| \neq \aleph_0$, then set $t_n = c_1, t_{n+1} = c_2, t_{n+2} = c_3, \dots$.
f) If $|C| = \aleph_0$, then 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.

Last edited by a moderator:
Related Set Theory, Logic, Probability, Statistics News on Phys.org

SSequence

Some older threads that are relevant:

==========

At any rate, let me add that if we are trying to "enumerate" an "initial segment of ordinals" in a mechanical way (without the occurrence of any jump or gap) then we would be using recursive sets***. This implicitly means that either we are using (i) some fixed finite alphabet OR (ii) $\mathbb{N}$.

*** In some senses, I suppose it is more complicated than that, but that's a good approximation of sorts.

AplanisTophet

At any rate, let me add that if we are trying to "enumerate" an "initial segment of ordinals" in a mechanical way (without the occurrence of any jump or gap) then we would be using recursive sets***. This implicitly means that either we are using (i) some fixed finite alphabet OR (ii) $\mathbb{N}$.

*** In some senses, I suppose it is more complicated than that, but that's a good approximation of sorts.
Something like the Church-Kleene ordinal is quite countable but not recursive. If it can be bijected with $\omega$, then I'm not sure what you mean by implying that it cannot be enumerated "in a mechanical way (without the occurrence of any jump or gap)."

The OP adds something to the sequence on each iteration (that was the tricky part). From there we just need to compile the $T$ sequence over $\omega_1$ iterations in a manner where the sequence never turns into a transfinite one. It happens to not have any gaps when the enumeration is all said and done (so the above $T$ enumerates an ordinal as opposed to merely being a sequence that is unbounded in some ordinal), but I digress...

The question is whether $B$ remains countable on each iteration. On any given iteration where the iteration counter $m$ is countable, there is provably an ordinal in $\omega_1$ that is greater than any that may be inserted into $B$. That is why $B$ remains countable if my understanding is correct.

SSequence

Something like the Church-Kleene ordinal is quite countable but not recursive. If it can be bijected with $\omega$, then I'm not sure what you mean by implying that it cannot be enumerated "in a mechanical way (without the occurrence of any jump or gap)."
Any such bijection with $\omega$ isn't mechanized. That is, the well-order relation (on $\omega$) corresponding to such a bijection will not be a recursive/computable function.

AplanisTophet

Any such bijection with $\omega$ isn't mechanized. That is, the well-order relation (on $\omega$) corresponding to such a bijection will not be a recursive/computable function.
Specifically, are you are saying that $\omega_1^{CK} = sup(b)$ where $\phi^{-1}_{\omega_1^{CK}}(b) = min\{ \phi^{-1}_{\omega_1^{CK}}(b) : \exists k \in b \text{ where } k \geq \phi^{-1}_{\omega_1^{CK}}(b)\}$? I'm not sure if that's true, but we can assume it is I suppose for the sake of argument if that helps.

The OP considers $(\phi_{\alpha})_{2 \leq \alpha < \omega_1}$. We know $\omega_1^{CK} < min\{ \phi^{-1}_{\omega_1^{CK}+1}(b) : \exists k \in b \text{ where } k \geq \phi^{-1}_{\omega_1^{CK}+1}(b)\}$, so I don't see how we are hung up on ordinals that are not recursive. That said, if you are implying something, I must not be seeing it.

I personally will keep coming back to whether or not $B$ is countable at the moment... I've stated that it seems as though it can't be, but then I recognize we should always be able to find an element of $\omega_1$ for a given iteration that should be greater than any element of $B$ for that iteration. To me, it all hinges on that. I've been through this a bit and it's easy to not see something with respect to your own work though. I appreciate the extra set of eyes. I assume a yes or no answer is possible for my question perhaps?

Last edited:

SSequence

Though generally speaking, this may possibly be relevant. So if we start off from some base iteration $i=0$ (where $i \in Ord$) and some set, say $A_0$. At $0$-th iteration we use $A_0$ to form $B_0$. This (in some way) gives us $A_1$. So at $1$-th iteration we can again use $A_1$ to form $B_1$ (which gives us $A_2$).

More generally at $i$-th iteration we use $A_i$ to form $B_i$. This (in some way) gives us $A_{i+1}$. With this the $i+1$-th iteration begins.

One thing with this kind of process will be that to give a precise description of the process you would need to specify what to do when we are at a limit iteration $i$ (that is, how you will obtain $A_i$). Because smaller values $j<i$ only give us $A_j$ or $B_j$. And any $B_j$ will only lead to $A_{j+1}$ (but $j+1$ isn't a limit).

=====================

[If one isn't giving a definition at limit, it might be that it is being assumed that new ordinals will be introduced unconditionally at every iteration in any case (and hence the limit-case is being defined implicitly so to speak). The paragraph below is related to that]

In-case the move from $A_i$ to $A_{i+1}$ introduces some new ordinal(s) $\alpha$ such that $\alpha>\beta$ (for all $\beta \in A_i$), the qualitative problem is that at some countable "limit iteration" no new ordinal will be introduced.
In fact, with most usual "powerful" functions (exponentiation, some variation of arrow notation etc.) this will happen well below $\omega_{CK}$ (unless $A_0$ already contains elements $\geq \omega_{CK}$).

=====================

Another thing is that at any stage $i<\omega_1$ all ordinals in sets $A_i$ and $B_i$ will be countable (unless your definition just introduces elements $\geq \omega_1$ out of the blue. That's because in a bottom-up manner one doesn't reach $\omega_1$ in countable iterations.
This is true in standard set-theoretic framework. If one isn't working within that then one needs to be more clear (or explanatory) as to what one is doing.

Last edited:

AplanisTophet

I confess that I expected someone to just assert that $B$ is uncountable. I would at least know they made sense of my work at that point. I do believe everything you wrote above is extremely helpful too though SSequence. I completely understand what you are saying.

I might at that point say, "let's just make $B$ countable then (that is, well order $B$ on each iteration and proceed to add only the first $\omega$ elements of $B$ to $T$ on each iteration)." There are $\omega_1$ iterations, so we'll get there anyways as each iteration will be adding elements to $T$ despite $T$ being a sequence of only order type $\omega$ after all $\omega_1$ iterations. This is possible because every element of $\omega_1$ may be approached from below given the right function, and there is precisely such a first function $\phi_{\alpha}$ for each ordinal. Spooky perhaps... Happy Halloween!

Before I tweak the OP just a little more to make sure $B$ remains countable on each iteration, contemplate it, and go running off frantically to StackExchange (that is an attempt at humor), which I'll only do if you or someone else tells me $B$ isn't already countable on each iteration (I suspect it may be) and why, I'm afraid I'm at a bit of an impass.

AplanisTophet

I assume the whole thing is too much for anyone to want to read, so I'll try to make it easier. Does anyone see a problem with the following definitions for function $t$ and the functions $(\phi_{\alpha})_{2\leq\alpha<\omega_1}$ quoted from the OP?

Does anyone familiar with Fodor's lemma care to discuss whether there must be a minimum element $\kappa \in \omega_1$ where $\kappa \in \phi_{\omega}(\kappa)$? Note that there is clearly a $\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).

Define $t(\alpha)$ for any ordinal $\alpha \geq 2$:
Let $t(\alpha)$ equal a doublet of variables $(a,b)$ if $\alpha = 2$, a triplet of variables $(a,b,c)$ if $\alpha = 3$, a quadrulplet of variables $(a,b,c,d)$ if $\alpha = 4$, and so on, for any ordinal $\alpha$. Note that this notation is used to avoid confusion as $a=b$ does not imply $(a,b) = (b,a) = (a) = (b)$, whereas it does imply $\{a,b\} = \{b,a\} = \{a\} = \{b\}$ in general.

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

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

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

3) $\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)\}$.

AplanisTophet

Above, Andrés E. Caicedo helps clarify the notation and points out that an assumption as to CH may be necessary for determining whether there must be some minimum $\kappa \in \omega_1$ where $\kappa \in \phi_{\omega}(\kappa)$.

To understand the use of function $t$ within the definition of each function $\phi_{\alpha}$, consider first $\phi_2$. The set of all doublets, where each element of each doublet is an element of $\omega_1$, is the English translation for: $$\{ t(2) : a,b,c,\dots \in t(2) \implies a,b,c,\dots < \omega_1 \} = \{ (a,b) : a,b \in \omega_1 \}$$

The function $\phi_2$ therefore bijects $\omega_1 \setminus \{0\}$ onto $\{(0,0),(0,1),(1,0),(1,1),(0,2),(a \in \omega_1, b \in \omega_1),...\}$.

The function $t^{-1}(x)$ will return $2$ for any doublet $x$, 3 for any triplet $x$, $4$ for any quadruplet $x$, and so on depending on the order type of $x$.

AplanisTophet

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

https://math.stackexchange.com/questions/3420874/question-involving-strength-of-fodors-lemma

Question:

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

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

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 sets $P$ and $P'$:

$$P = \{ t(\omega) : a,b,c,\dots \in t(\omega) \implies a,b,c,\dots \, \text{is a computable sequence}, a \neq b \neq c \neq \dots, \, \text{and } a,b,c,\dots \in \omega \} \equiv P' = \{ p \in \mathcal{P}(\omega) : |p| = \aleph_0 \, \text{and } p \, \text{is computable} \}$$

Define the functions $(v_{\alpha})_{\alpha \in \omega_1}$ over index $P'$:

$$v_{\alpha}(p) = \{ \omega \cdot \alpha + p' : p' \in p \}, \text{ for any } p \in P', \alpha \in \omega_1$$

Define the set $Q$:

$$Q = \{ v_{\alpha}(p) : p \in P' \, \text{and } \alpha \in \omega_1 \}$$

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

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

Define 'Likewise Computable':

Let $t(\alpha) = ((\omega \cdot \beta + a)_0, (\omega \cdot \beta + b)_1, (\omega \cdot \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 \}$ 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}\}$ 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 \{ x \in g(A) : t^{-1}(x) > h(f(x))\} ) \}$. 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.

AplanisTophet

I worked the kinks out as to the definitions ($\phi_{\omega}$ and above aren't bijective as written here in this forum) and I got someone to go over my definitions some at Stackexchange, but the properly formatted question now remains open there, so I will stop posting here and just leave this link to SE:

I find this all interesting and I hope you do too.

If anyone wants to assert that $\omega_1$ is countable using the non-transfinite $T$ option, I would of course agree! That is, I hope this leads to a solution to the continuum hypothesis, but I wouldn't want to be so presumptuous without mathematicians much more qualified than me acknowledging so.

SSequence

One thing that might be relevant to mention is that if we have a function $f:\omega_1 \rightarrow \omega_1$ such that:
(1) $f$ is non-decreasing.
(2) For all $x \in \omega_1$, $f(x)<x$

Then for any such function $f$ satisfying properties (1) and (2) above there will always exist an $N<\omega_1$ such that for all $x>N$ we have $f(x)=f(N)$. In other words, after a certain value $N<\omega_1$ any function $f$ [satisying (1) and (2) above] will have to become constant.

Edit: What I mentioned above is true in ZFC for sure.

AplanisTophet

One thing that might be relevant to mention is that if we have a function $f:\omega_1 \rightarrow \omega_1$ such that:
(1) $f$ is non-decreasing.
(2) For all $x \in \omega_1$, $f(x)<x$

Then for any such function $f$ satisfying properties (1) and (2) above there will always exist an $N<\omega_1$ such that for all $x>N$ we have $f(x)=f(N)$. In other words, after a certain value $N<\omega_1$ any function $f$ [satisying (1) and (2) above] will have to become constant.

Edit: What I mentioned above is true in ZFC for sure.
As mentioned in the OP here and the current version of this over at SE, yes, people should be familiar with Fodor's lemma. Your description of the lemma could perhaps use some clarification. What you mean is that if $f$ is regressive (condition 2) and from $\omega_1 \setminus \{0\}$ onto $\omega_1$ (you need to remove the 0...), there is a stationary subset $S_0$ of $\omega_1$ that maps to a constant. See the actual lemma:

Fodor's lemma is applied to much more interesting structures too (see Caicedo's answer):

Please note that my SE thread directly addresses the relationship of Fodor's lemma to the questions being posed. They are not easy questions!!:

Thank you!

Last edited:

SSequence

Your description of the lemma could perhaps use some clarification. What you mean is that if $f$ is regressive (condition 2) and from $\omega_1 \setminus \{0\}$ onto $\omega_1$ (you need to remove the 0...), ........
Yes, you are right. It should be $f:\omega_1- \{0\} \rightarrow \omega_1$ in the first line of post#12. Other than that, it should be pretty clear.

Regarding your mention of whether $f$ should be onto(surjective) or not [maybe it was a typo], it doesn't matter. That's why I didn't place any such condition. The only conditions that are needed in post#12 are (1) and (2) mentioned there. Any function $f:\omega_1- \{0\} \rightarrow \omega_1$ satisfying those will become constant after a while (as mentioned in post#12). Another way to put it would be $range(f) \subseteq \alpha$ (for some $\alpha<\omega_1$).

Last edited:

AplanisTophet

Yes, you are right. It should be $f:\omega_1- \{0\} \rightarrow \omega_1$ in the first line of post#12. Other than that, it should be pretty clear.
Actually no, because you are not interpreting "stationary" correctly either.

Here is your post 12, so let's take a look at what is wrong here (there is a lot, sorry).

One thing that might be relevant to mention is that if we have a function $f:\omega_1 \rightarrow \omega_1$ such that:
(1) $f$ is non-decreasing.
(2) For all $x \in \omega_1$, $f(x)<x$

Then for any such function $f$ satisfying properties (1) and (2) above there will always exist an $N<\omega_1$ such that for all $x>N$ we have $f(x)=f(N)$. In other words, after a certain value $N<\omega_1$ any function $f$ [satisying (1) and (2) above] will have to become constant.

Edit: What I mentioned above is true in ZFC for sure.
Condition 2 means that $f$ is regressive. You can just say that $f$ is a regressive function that [...insert condition 1...].

I believe non-decreasing and regressive are mutually exclusive conditions.

We corrected the domain of $f$ to be $\omega_1 \setminus \{0\}$ so as to allow it to be regressive.

Any function $f$ that is regressive in this context (from a stationary subset of a regular, uncountable cardinal $\kappa$ to the cardinal $\kappa$), will generally not produce the $N < \omega_1$ that you describe. A stationary subset of $\omega_1$ in this case is a completely different thing:

You are trying to replace Fodor's stationary set $S_0$, where $S_0 \subseteq S \subseteq \omega_1$ from the Wiki proof linked to above, and replace it with {all x greater than a particular N, where N in $\omega_1$}. This is a huge gap in understanding, but the diagonal intersection of some club sets is itself a club set (closed and unbounded, so uncountable too) that is also stationary. It's a very tricky thing that took me, and plenty of others too, some time to grasp.

SSequence

Actually no, because you are not interpreting "stationary" correctly either.

Here is your post 12, so let's take a look at what is wrong here (there is a lot, sorry).
......
I didn't use the word "stationary" at all in post#12. So I don't know what you mean.

Condition 2 means that $f$ is regressive. You can just say that $f$ is a regressive function that [...insert condition 1...].
OK

We corrected the domain of $f$ to be $\omega_1 \setminus \{0\}$ so as to allow it to be regressive.
Correct.

==========

I don't understand what you are trying to say in the rest of the post. So I can't follow you here. I just mentioned a certain statement in post#12 and said that its true in ZFC (which it is).

You can post my post#12 on MSE as a question if you want (exactly as it is, just replacing $f:\omega_1 \rightarrow \omega_1$ with $f:\omega_1-\{0\} \rightarrow \omega_1$). People there will also confirm that what I am saying is indeed correct.

AplanisTophet

The problem was that you didn't use the word stationary as you admit. You should have.

ZFC has little to do with this given $\omega_1$ is regular (ie., has cofinality $\omega_1$, which may be assumed given the axiom of choice I believe).

It's easy to show you are mistaken in post 12:

Let $f(x) = x - 1$ for all $x$ that are not limit ordinals and let $f(x) = 0$ otherwise. My $f$ is now regressive where $f : \omega_1 \setminus \{0\} \rightarrow \omega_1$ and disproves your claims in statement 12 because there is no $N \in \omega_1$ where $f(x) = f(N)$ for all $x > N$ as you assert must be true.

SSequence

Let $f(x) = x - 1$ for all $x$ that are not limit ordinals and let $f(x) = 0$ otherwise. My $f$ is now regressive where $f : \omega_1 \setminus \{0\} \rightarrow \omega_1$ ......
But now $f$ is no longer non-decreasing and hence doesn't satisfy condition-(1) in post#12.

AplanisTophet

But now $f$ is no longer non-decreasing and hence doesn't satisfy condition-(1) in post#12.
I did mention that I believe non-decreasing (ie, increasing) and regressive (decreasing) to be mutually exclusive. Are they not?

SSequence

I did mention that I believe non-decreasing (ie, increasing) and regressive (decreasing) to be mutually exclusive. Are they not?
Assuming $\omega_1-\{0\}$ to be the domain (we can fix any ordinal as a domain if we like ..... and excluding $0$):

By non-decreasing I mean that for any arbitrary $x_1,x_2 \in \omega_1-\{0\}$:
$x_1<x_2$ implies $f(x_1) \leq f(x_2)$

Regressive means (based on what you said) that for any arbitrary $x \in \omega_1-\{0\}$:
$f(x)<x$

Both can hold simultaneously for a function.

Edit:
fixed for $0$

AplanisTophet

Assuming $\omega_1-\{0\}$ to be the domain (we can fix any ordinal as a domain if we like ..... and excluding $0$):

By non-decreasing I mean that for any arbitrary $x_1,x_2 \in \omega_1-\{0\}$:
$x_1<x_2$ implies $f(x_1) \leq f(x_2)$

Regressive means (based on what you said) that for any arbitrary $x \in \omega_1-\{0\}$:
$f(x)<x$

Both can hold simultaneously for a function.
This makes more sense now, thank you. I will think about it some.

AplanisTophet

This is a draft that I have to step back from and consider some yet, but I believe that I may have managed to answer the first question posed here. Any feedback here before I attempt to answer my own question on StackExchange might be nice:

Incorporate the definitions from my SE thread.

Proof that there must exist a minimum element $k \in \omega_1$ where $k \in \phi_{\omega}(k)$:

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