Specific Question about $\omega_1$ hierarchies

Question

Consider a $\omega_1$ hierarchy of increasing functions such that whenever we have $\alpha<\beta$, we get $f_\alpha < f_\beta$. The $<$ symbol denotes (eventual) domination.

All functions below are from $\mathbb{N}$ to $\mathbb{N}$. Now consider the following propositions/statements:

$(p)$ There is no function $F$ such that $F>f_\alpha$ for all $\alpha<\omega_1$. Edit:(as was pointed out in the answer a stronger condition was intended here. And that was that for any function $F$ there must exist some $\alpha<\omega_1$ so that $f_\alpha > F$ End

$(q)$ $\mathbb{R}$ can be well-ordered (I don't have enough understanding here, but just in case this doesn't suffice, then possibly a more powerful(?) assumption such as AC can be assumed)

$(r)$ CH is true

Now is it true that the truth of $p$ and $q$ implies $r$?

If the above is false, then there is one way it seems possible to me. Consider some arbitrary function $r:\mathbb{N} \rightarrow \{0,1\}$. And now denote $A_r$ as set of all those increasing functions $g$ such that $g \le_T r$. But now there must exist some $p<\omega_1$ such that $f_p > A_r$ (meaning $f_p$ dominates every function in the collection $A_r$) and yet $r \nleq_T f_p$. And neither is $r$ computationally reducible to any function (in the given hierarchy) that dominates $f_p$.

Is the reading in above paragraph correct or incorrect. If it is incorrect, then where does the error lie? And in case it is correct, can one give example of such a function $r$?

Answer 1

Let's dispense with your $(q)$ by working in ZFC (so everything can be well-ordered). Also, "function" will mean "function from $\omega$ to $\omega$."

The existence of a family $F$ of the type you describe is implied by $\mathfrak{d}=\omega_1$, where $\mathfrak{d}$ is the dominating number: the minimal cardinality of any set of functions such that every function is dominated by one in the set. This is not too hard: given any sequence $D=(g_\eta)_{\eta<\omega_1}$ of $\omega_1$-many functions, we can construct a sequence of functions $(f_\eta)_{\eta<\omega_1}$ such that $f_\eta>f_\beta+g_\beta$ for every $\beta<\eta<\omega_1$; now just let $D$ be a dominating family of size $\omega_1$.

The equality $\mathfrak{d}=\omega_1$ is strictly weaker than CH, so in fact $(p)$ and $(q)$ together do not imply $(r)$.

---

So what about your analysis? (Fix such an $F$ and assume $(q)$ but $\neg(r)$.)

Incidentally, note that the only thing you're using about Turing reducibility is that there are only countably many functions Turing reducible to a given one. That doesn't play a direct role, but removing the computability-theoretic aspects - until they become necessary, if ever - will make things less mysterious.

Your claim that there is some $f_p$ dominating every function computable from a fixed real $r$ is not justified unless we assume a stronger hypothesis on $F$: namely, that every function is dominated (not merely escaped) by some function in $F$. This is still consistent with $\neg$CH, though, so let's assume it. It does of course justify the existence of an $f_p$ dominating every $r$-computable function.

However, you then claim

And neither is $r$ computationally reducible to any function (in the given hierarchy) that dominates $f_p$.

This will be false in general (what if $r$ is computable?). What is true is that no function dominating $f_p$ (in the given hierarchy or not) is $\le_Tr$, but that's the opposite of what you've written. However, if CH fails then what you've written will sometimes be true: there are only $\omega_1$-many reals Turing reducible to some function in $F$, so (assuming $\neg$CH) there will be some real $r$ which is not Turing reducible to any of the functions in $F$ at all.

Proof: The set of functions computable relative to some $f\in F$ has cardinality $\omega_1\cdot\omega=\omega_1$ (since only countably many things are computable in a given function, and there are $\omega_1$-many functions in $F$). So since CH fails, we can find some $r$ not computable from any member of $F$. Indeed, this means that most reals will not be computable from any member in $F$.

I think this is what you actually mean, given your question "And in case it is correct, can one give example of such a function $r$?" So perhaps this is a typo rather than a genuine error. To that question, the answer is that practically any $r$ can have this property. Perhaps counterintuitively, if $\mathfrak{d}=\omega_1$, there is lots of flexibility in constructing the family $F$, and for almost any $r$ we can construct an appropriate $F$. Precisely:

Assume $\mathfrak{d}=\omega_1$. The following are equivalent: $(i)$ $r$ is not hyperarithmetic. $(ii)$ There is a dominating family $(f_\alpha)_{\alpha<\omega_1}$ such that $f_\alpha<f_\beta$ whenever $\alpha<\beta$ and $r$ is not Turing reducible to any of the $f_\alpha$s.

The proof is a bit technical, but is basically an iterated limited forcing argument. ("Limited" in the sense that we're not performing full forcing, but rather just building a "sufficiently generic" object inside our set-theoretic universe.) It's a small tweak on a theorem of Solovay, that the reals computable from fast-enough growing functions are precisely the hyperarithmetic reals.