This question has now been published in a math journal, see update at the bottom.

I posted the following question more than two years ago on MO (and then reposted on MSE), but the answer remains incomplete, so I thought I would rephrase it a bit (to make the statement clearer) and try again.

Let $\omega_1$ be the first uncountable ordinal, same as the set of all countable ordinals.
$\omega_1=\{\alpha:0\le\alpha<\omega_1\} = \{\alpha:\alpha$ is a countable ordinal$\}$.
Let $\mathcal F$ be the set of all functions $f:\omega_1\to\omega_1$ that are:
(a) regressive i.e. $f(\alpha) < \alpha$ for all $0 < \alpha < \omega_1$, and
(b) non-decreasing (same as $\le$-order-preserving), i.e.,
if $0\le\alpha \leq \beta<\omega_1$ then $f(\alpha)\leq f(\beta)$ .
Define a partial order $\sqsubseteq$ on $\mathcal F$ by $f \sqsubseteq g$ if $f(\alpha) \leq g(\alpha)$ for all $\alpha < \omega_1$.
Let $\mathcal K$ be the subset of $\mathcal F$, consisting of functions with a finite range.
Formally $\mathcal K=\{f\in\mathcal F: |\{f(\alpha):\alpha<\omega_1\}|<\aleph_0\}$.

Is there a $\sqsubseteq$-order-preserving map (same as a $\sqsubseteq$-non-decreasing map)
$\psi : \mathcal F \to \mathcal K$, i.e if $f \sqsubseteq g$ then $\psi(f) \sqsubseteq \psi(g)$, and with
the additional property that $\psi(f) \sqsupseteq f$ for all $f\in \mathcal F$ ?

Let me summarize some comments made at MO, clarifying certain partial answers.

Partial answer (A). Since every $f\in\mathcal F$ is regressive and non-decreasing, it must be eventually constant and reach its maximal value $\mu_f=\max\{f(\alpha):\alpha < \omega_1\}$. One is tempted to define $\psi(f)(\alpha)=\mu_f$ for all $\alpha$. The problem is that this is not regressive: We have $\psi(f)(\alpha)<\alpha$ only when $\alpha>\mu_f$, but I insist that $\psi(f)(\alpha)<\alpha$ whenever $0<\alpha<\omega_1$.

Partial answer (B). If we drop the requirement that $\psi$ be a $\sqsubseteq$-non-decreasing map then the answer by @NoahS below works, as well as one of my comments below, which I move here. As above let $\mu_f=\max\{f(\alpha):\alpha < \omega_1\}$ and let $\gamma_f=\min\{\alpha:f(\alpha)=\mu_f\}$. (Then $f(\alpha)=\mu_f$ for $\alpha\ge\gamma_f$, and $f(\alpha)<\mu_f$ for $\alpha<\gamma_f$. Usually $\mu_f<\gamma_f$ unless $\mu_f=0=\gamma_f$.) Let $\alpha_{0,f}=\mu_f$. If $\mu_f\ge1$ then let $\alpha_{1,f}=f(\alpha_{0,f})<\alpha_{0,f}$. There is a non-negative integer $n_f$ such that $\alpha_{k+1,f}=f(\alpha_{k,f})<\alpha_{k,f}$ for $k<n_f$, and $\alpha_{n_f,f}=0$. Define $\psi(f)$ as follows. If $\alpha>\alpha_{0,f}$ then let $\psi(f)(\alpha)=\alpha_{0,f}=\mu_f$. If $\alpha_{k+1,f}<\alpha\le\alpha_{k,f}$ then let $\psi(f)(\alpha)=\alpha_{k+1,f}$. (Formally also $\psi(f)(0)=0$, but in general each function in $\mathcal F$ being regressive must take value $0$ at $1$, and being non-decreasing must take value $0$ at $0$ as well.) Then $\psi(f)\in\mathcal K$ and $\psi(f)\sqsupseteq f$.

So partial answer (A) above achieves that $\psi(f)$ has a finite range, and $\psi(f) \sqsubseteq \psi(g)$ whenever $f \sqsubseteq g$, and also $\psi(f) \sqsupseteq f$. It almost achieves that $\psi(f)$ is regressive, but not quite, and it follows that $\psi(f)$ is not in $\mathcal K$ unless $\mu_f=0$. (One could perhaps say that $\psi(f)$ is "regressive on a tail" only, which might in a different context be good enough, but the requirement in my question is that $\psi(f)(\alpha)<\alpha$ whenever $0<\alpha<\omega_1$.) On the other hand, partial answer $B$ achieves that $\psi(f)\in\mathcal K$ (in particular both that $\psi(f)$ is regressive and has a finite range), and $\psi(f) \sqsupseteq f$ for all $f\in \mathcal F$, but not necessarily that $\psi(f) \sqsubseteq \psi(g)$ whenever $f\sqsubseteq g$. It is not clear to me if we could achieve all conditions simultaneously. Edit. Following a comment, let me clarify why in partial answer $B$ we need not have $\psi(f) \sqsubseteq \psi(g)$ whenever $f\sqsubseteq g$. Fix any ordinals $0<\beta<\delta<\nu<\omega_1$. Let $f(\alpha)=g(\alpha)=0$ if $0\le\alpha<\nu$. Let $f(\alpha)=\beta$ and $g(\alpha)=\delta$ if $\alpha\ge\nu$. Clearly $f\sqsubseteq g$. Then $\psi(f)(\alpha)=\beta$ if $\alpha>\beta$, and $\psi(f)(\alpha)=0$ if $0\le\alpha\le\beta$ (where $\psi$ is as in partial answer $B$). While $\psi(g)(\alpha)=\delta$ if $\alpha>\delta$, and $\psi(g)(\alpha)=0$ if $0\le\alpha\le\delta$. In particular, if $\beta<\alpha\le\delta$ then $\psi(g)(\alpha)=0<\beta=\psi(f)(\alpha)$, so $\psi(f)\not\sqsubseteq \psi(g)$.

If I were to make a guess, I would say the answer is no. This question is an order-theoretic restatement of a question from general topology that a co-author and I considered: Whether $\omega_1$ has a monotone interior-preserving open operator $r$, that is, if $\mathcal U$ is any open cover of $\omega_1$, with the order topology, then $r(\mathcal U)$ is an interior-preserving open refinement that covers $\omega_1$, and if $\mathcal U$ refines $\mathcal V$ then $r(\mathcal U)$ refines $r(\mathcal V)$. As usual we would write $\mathcal U\preceq \mathcal V$ if $\mathcal U$ refines $\mathcal V$. In this context $f$ is intended to encode an open cover $\mathcal U(f)=\{0\}\cup\{(f(\alpha),\alpha]:\alpha<\omega_1\}$. Note that if $f\sqsubseteq g$ then $\mathcal U(g)\preceq \mathcal U(f)$.

Thank you!

Original version of this post:

Let $\omega_1$ be the first uncountable ordinal, same as the set of all countable ordinals. Let $F$ be the set of all functions $f$ from $\omega_1$ minus singleton $0$ into $\omega_1$ that are (a) regressive i.e. $f(\alpha) < \alpha$ for $0 < \alpha < \omega_1$, and (b) order-preserving (same as non-decreasing) i.e. $f(\alpha)\leq f(\beta)$ if $\alpha \leq \beta$. Define a partial order on $F$ by $f \leq g$ if $f(\alpha) \leq g(\alpha)$ for all $0<\alpha < \omega_1$. Let $K$ be the subset of $F$, of functions with a finite range.

Question: Is there an order-preserving homomorphism $h : F \to K$, i.e if $f \le g$ then $h(f) \le h(g)$, and with the additional property that $f \le h(f)$ ?

(I had dropped (b) in my first post, but comments below show that it is essential. Also, I did mean the functions $f$ must be regressive, when I had imprecisely said decreasing, in the original statement. I added the gn tag since the question stated is an order-theoretic translation of a question from general topology: Whether $\omega_1$ has a monotone interior-preserving open operator.)

Edit April 28, 2014: The answer by Noah S below is correct but incomplete (for each $f\in F$ it finds $h(f)\in K$ with $f \le h(f)$ but does not consider whether $h(f) \le h(g)$ when $f\le g \in F$). The question is open. Thank you

Edit April 12, 2015. I reposted at MSE

Update Oct 19, 2018 (and May 21, 2019):
This questions has been included in the following paper:
Serdica Math. J. 44 (2018) (dedicated to the memory
of Professor Stoyan Nedev (1942−2015))
S.G. Popvassilev, J.E. Porter
Here is a temporary link from the editors:

  • 1
    $\begingroup$ Do you mean decreasing or regressive? (You wrote the former but the definition you give is the latter.) $\endgroup$ – François G. Dorais Mar 19 '14 at 17:50
  • 2
    $\begingroup$ Since there are regressive functions with unbounded range but every function in $K$ has bounded range, you can't always have $f \leq h(f)$. (Assuming regressive is what you meant.) $\endgroup$ – François G. Dorais Mar 19 '14 at 17:58
  • 1
    $\begingroup$ @Francois, you're right, I read the requirement as "$h(f)\le f$," since (as you point out) the other inequality is trivially unsatisfiable if "regressive" is meant; and if "decreasing" is meant, then all such functions have finite range, so the question is trivial in the other direction. $\endgroup$ – Noah Schweber Mar 19 '14 at 18:19
  • 1
    $\begingroup$ @Mirko I didn’t read all the thread, so my question may be stupid, but I don’t see why the function $\psi$ constructed in Partial answer B is not $\sqsubseteq$-non-decreasing map. As for me, its $\sqsubseteq$-non-decreasity should easlily follow from the construction of $\psi(f)$. Can you provide a counterexample or it is already provided somewhere in the thread? $\endgroup$ – Alex Ravsky May 29 '17 at 0:51
  • 1
    $\begingroup$ @AlexRavsky I added an edit: Fix any ordinals $0\le\beta<\delta<\nu<\omega_1$. Let $f(\alpha)=g(\alpha)=0$ if $0\le\alpha<\nu$. Let $f(\alpha)=\beta$ and $g(\alpha)=\delta$ if $\alpha\ge\nu$. Clearly $f\sqsubseteq g$. Then $\psi(f)(\alpha)=\beta$ if $\alpha>\beta$, and $\psi(f)(\alpha)=0$ if $0\le\alpha\le\beta$ (where $\psi$ is as in partial answer $B$). While $\psi(g)(\alpha)=\delta$ if $\alpha>\delta$, and $\psi(g)(\alpha)=0$ if $0\le\alpha\le\delta$. In particular, if $\beta<\alpha\le\delta$ then $\psi(g)(\alpha)=0<\beta=\psi(f)(\alpha)$, so $\psi(f)\not\sqsubseteq \psi(g)$. $\endgroup$ – Mirko May 29 '17 at 5:14

OK, third time's the charm, hopefully:

First, a lemma:

Fix an arbitrary successor ordinal $\beta$ and a nondecreasing regressive map $f$ with domain $\beta-\{0\}$. Then there is a nondecreasing regressive map $d_f$ with the same domain such that $f\le d_f$ and $d_f$ takes on only finitely many values.

The proof is by induction on $\beta$. The base case $\beta=2$ is trivial, as is the successor-of-a-successor case.

Now suppose the proof holds for all non-limit $\gamma<\lambda+1$ for $\lambda$ a limit, and take $\beta=\lambda+1$. Fix some successor ordinal $\chi$ with $\chi<\lambda$ and $\chi>f(\lambda)$; such a $\chi$ must exist since $\lambda$ is limit and $f$ is regressive.

But now consider the map $F=f\upharpoonright \chi$. Since $\lambda$ is limit and $\chi<\lambda$ is a successor ordinal, we may apply the induction hypothesis to get a $d_{F}$. But now consider the map $d_f$ with domain $\lambda-\{0\}$ extending $d_{F}$ and taking on the value $max\{f(\lambda), d_F(\epsilon)\}$ (where $\epsilon+1=\chi$) on all inputs $\theta$ with $\chi<\theta \le\lambda$. This function has the desired properties - in particular, it is regressive by choice of $\chi$ - so we are done. QED

Now, to answer the actual question: fix a nondecreasing regressive $f$ defined on $\omega_1-\{0\}$. By Fodor's lemma + nondecreasingness, $f$ is eventually constant; fix some countable successor ordinal $\alpha$ such that for all $\beta>\alpha$, $f(\beta)=f(\alpha)=\gamma$.

Apply the lemma to $f\upharpoonright \alpha$ to get a function $d_0$; now extend $d_0$ to a function $d$ defined on all of $\omega_1-\{0\}$ by setting $d(\theta)=max\{f(\alpha), d_0(\epsilon)\}$ (where $\epsilon+1=\alpha$) for all $\theta\ge\alpha$.

| cite | improve this answer | |
  • $\begingroup$ And, as the comments by Francois and me above showed: (1) if you drop the requirement that $f$ be nondecreasing, the answer is "no"; (2) if you drop the requirement that $f$ be nondecreasing and demand $h(f)\le f$ instead of $f\le h(f)$, the answer is trivially "yes"; (3) if you replace "regressive" with "nondecreasing," then your two classes of functions are identical and so the answer is trivially "yes". I believe this question is now completely answered. $\endgroup$ – Noah Schweber Mar 19 '14 at 21:29
  • $\begingroup$ @NoahS, what do you mean by (3)? The set of nondecreasing functions is not equal to the set of nondecreasing functions with finite range. Perhaps "non increasing?" $\endgroup$ – Monroe Eskew Mar 19 '14 at 21:49
  • 2
    $\begingroup$ @MonroeEskew: The OP had originally written decreasing instead of regressive. Noah was just a bit too non-happy when he wrote his comment. $\endgroup$ – François G. Dorais Mar 19 '14 at 21:51
  • 1
    $\begingroup$ @Francois, it took me a couple passes to parse "non-happy" correctly. At first, I thought you were saying I was too sad to type correctly. :P $\endgroup$ – Noah Schweber Mar 19 '14 at 21:53
  • 2
    $\begingroup$ @NoahS Thank you for several relevant answers. As I understand the proof of your lemma for regressive maps on successor $\beta$ (with a minor simplification) you use the induction hypothesis for $\chi = f(\lambda)+1$ to define $d_f$ on $\chi = [0,\chi)$, and define $d_f$ to map $[\chi,\lambda]$ onto $\{f(\lambda)\}$. Your lemma is correct, the rest of your answer shows one could define $d=h(f)\in K$ with $h(f)\ge f$ (see an alternative proof of this in my previous comment). You do not seem to address the question whether $h$ is order-preserving (i.e. $h(f)\le h(g)$ if $f\le g$). Thank you $\endgroup$ – Mirko Mar 20 '14 at 15:55

I have been thinking about this question since it was bumped up. I am burned out now, so I thought I would post a few basic things that I noted.

First, as you noted that any function $f \in \mathcal F$ would reach a constant value after some point. Also that value will obviously be the maximum value of the function. So suppose that $f:\omega_1 \rightarrow \omega_1$ maximises at a value $v_f$. Now it seems to me that this variable $v_f$ may be of some significance for the given question.

For example, let $\mathcal F_\alpha \subset \mathcal F$ ($\alpha<\omega_1$) denote the collection of functions $f \in \mathcal F$, which satisfy the additional property the $v_f < \alpha$. Your original question was (A) Giving a function $\psi : \mathcal F \to \mathcal K$ (satisfying certain properties of course). Now I think we can also consider a sub-question: (B) Can one give a function $\psi_\alpha : \mathcal F_\alpha \to \mathcal K$ for any arbitrary $\alpha < \omega_1$ ($\psi_\alpha$ and $\mathcal K$ satisfying properties as described in question).

For example, here is an example of a function $\psi_{\omega^2} : \mathcal F_{\omega^2} \to \mathcal K$. I think, I can give a similar description for $\psi_{\omega^3} : \mathcal F_{\omega^3} \to \mathcal K$. I have not added it for the sake of brevity, but if you think the example for $\psi_{\omega^2}$ is not illustrative enough, then I will add it.

An example for $\psi_{\omega^2}$. Given a function $f \in \mathcal F_{\omega^2}$, first determine the maximum value $v_f$ of the function. Now suppose that the maximum value $v_f$ is of the form $\omega \cdot a+b$ (with $a \in \mathbb{N}^+$, $b \in \mathbb{N}$). Denote $\psi_{\omega^2} (f)$ as $F$. Now define $F$ as follows: $$F(x)=\omega \cdot a+b=v_f \qquad \mathrm{for} \quad x > \omega \cdot(a+1)$$ $$F(x)=\omega \cdot a \qquad \mathrm{for} \quad \omega\cdot a < x \leq \omega \cdot (a +1)$$ $$F(x)=\omega \cdot n \qquad \mathrm{for} \quad \omega\cdot n < x \leq \omega \cdot (n+1)$$ $$F(x)=f(x) \qquad \mathrm{for} \quad x \leq \omega $$ In the third line, we have $1 \leq n < a$. (EDIT : Made a correction in the first and second equation)

One line of thinking is to see whether we can keep giving the function $\psi_\alpha$ or not. If no, then what is the point at which we can no longer do that (the answer to (A), the question in OP, would be negative in that case). If yes, in that case the answer to (B) would be positive. Also, in that case, what would be the general requirements/obstacles at each level (to determine whether (B) implies (A) or not). Anyway, just a suggestion that might perhaps be useful (and, to be fair, possibly not useful).


Regarding the description of $\psi_{\omega^2} (f)=F$, it was rightly mentioned in comments that it is only guaranteed to work for those functions $f \in \mathcal F_{\omega^2}$ which increase smoothly. In other words, if $v_f$ is the maximum value of $f$, then $f$ satisfies the condition $\mathrm{range}(f)=v_f+1$.

Somewhat briefly, I just wanted to point out how this can be rectified somewhat easily (though it seems it would be at the cost of doubling the number of equations above). Suppose we had some function $f \in \mathcal F_{\omega^2}$ so that $f(\omega \cdot 2)=\omega+2$ and $f(\omega \cdot 3)=\omega.2+4$. Further suppose the max. value for $f$ is: $v_f=f(\omega \cdot 3)$.

Now we define $\psi_{\omega^2} (f)=F$ as follows:

(1) For $x \leq \omega$, set $F(x)=f(x)$

(2) Set $F(\omega+1)=\omega$, $F(\omega+2)=\omega+1$

(3) For $\omega+3 \leq x \leq \omega \cdot 2$, set $F(x)=f(\omega \cdot 2)$

(4) Set $F(\omega \cdot 2+1)=\omega \cdot 2$, $F(\omega \cdot 2+2)=\omega \cdot 2+1$, $F(\omega \cdot 2+3)=\omega \cdot 2+2$, $F(\omega \cdot 2+4)=\omega \cdot 2+3$

(5) For $\omega \cdot 2+5 \leq x \leq \omega \cdot 3$, set $F(x)=f(\omega \cdot 3)$

(6) For $x > \omega \cdot 3$, set $F(x)=f(\omega \cdot 3)$

| cite | improve this answer | |
  • $\begingroup$ Sorry I think there is a mistake in the specific construction that needs correction. I will edit it soon. $\endgroup$ – SSequence Oct 28 '18 at 13:12
  • $\begingroup$ thank you for your answer. I believe that $\psi_\alpha$ would exist, I may have thought of this, don't remember anything specific, but tend to believe the answer for $\psi_\alpha$ is yes. There are other ways to partition $\mathcal F$, e.g. $\mathcal F_n=\{f\in\mathcal F:n_f=n\}$, $n_f$ as in Partial Answer (B), one could show there is $\psi$ that works for $\mathcal F_0\cup \mathcal F_1$ (thanks to Lynne for def $\mathcal F_n$). A vague idea, that I feel since yesterday, might be relevant, if $\psi$ exists for all of $\mathcal F$ try to relate to ordinal subtraction and get a contradiction $\endgroup$ – Mirko Oct 28 '18 at 19:15
  • $\begingroup$ I think I follow your description of $\psi_{\omega^2}$ (if $a=0$ take $F=f$). Would $\psi_{\omega^3}$ agree with $\psi_{\omega^2}$ on $\mathcal F_{\omega^2}$? Would $\psi_{\omega^\omega}$ agree with them? We could redefine $\psi_{\omega^n}$ to make it agree with $\psi_{\omega^\omega}$, but would we have to redefine $\psi_\alpha$ infinitely often? Unrelated: Let $\mathcal G_1=\{f\in\mathcal F:f(v_f)=0\}$. If $f\in\mathcal G_1$ let $\beta_f=\min\{\alpha:f(\alpha)>0\}$. Let $F(\alpha)=v_f$ if $\alpha\ge\beta_f$, else $F(\alpha)=0$. Works for $\mathcal G_1$. What about $\mathcal G_n=\{f:n_f=n\}$? $\endgroup$ – Mirko Oct 28 '18 at 20:27
  • $\begingroup$ You may need to correct the definition of $F$. If $f(\omega\cdot(n+1))>\omega\cdot n$ then the condition $F(x)\ge f(x)$ fails at $x=\omega\cdot(n+1)$. This problem will be resolved if you define $F(x)$ to be the maximim of $f(x)$ and your current definition of $F(x)$, for each $x$. To illustrate, let $f(n)=0$ if $n<\omega$, $f(\omega+n)=n$, $f(\omega\cdot2)=\omega+5$, $f(\alpha)=\omega+10$ if $\alpha>\omega\cdot2$. Then your $F(\omega\cdot2)=\omega<\omega+5=f(\omega\cdot2)$, but we need $F(x)\ge f(x)$ for all $x$. Again, setting $F(x)=\max\{f(x),current F(x)\}$ resolves this problem. Thank you $\endgroup$ – Mirko Oct 28 '18 at 22:00
  • $\begingroup$ @Mirko You raised many points in the comments. Let me try to address them one by one. Yes, you are absolutely right regarding the issue with my def. of $F$. I think, subconsciously I was taking the additional assumption that the functions $f \in \mathcal F$ (and hence $\mathcal F_{\omega^2}$) increase smoothly (that is, $f$ can't skip on values less than $v_f$). It seemed easier to me to first see what we can do under that assumption. You would note that my definition is correct in that case. If we don't assume that $f$ increases smoothly, then some adjustment to it is needed definitely. $\endgroup$ – SSequence Oct 29 '18 at 2:45

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.