hmm... I'll have a look after I deal with that irrational cover question...
Meanwhile I need to figure out how to make Asaf more weird, cause past experience told me that I often have trouble explaining what I am doing to non weird people
I don't understand what you are doing, or why you expect the limit to be an open set. But in any case, writing $\lim_{k\to\aleph_0}$ is making me cringe. — Asaf Karagila7 hours ago
In any case, I don't like writing $\to \infty$ unless the set of indices is only linearly ordered. If I can well order it, I will make sure to make it clear that no one dared to count to uncountable
@SimplyBeautifulArt I suspect the more general case will be: let $f$ be any nondecreasing function of the ordinals. Then an OCF including $f$ and all functions that strictly grows slower than $f$ will produce everything before $f^2(n)$ and $\psi(n) \geq \sup (g < f : g^2(n))$
e.g. $2,k+2,k^2,k^k, \epsilon_{\epsilon_{k}}, \phi (\phi (n,k)), \Gamma_{\Gamma_k}...$
and I suspect that will also work even if $f$ is $\alpha$-uncomputable
however, unless $f$ has a growth rate comparable to $x \to \omega_1 + x$, none of these OCFs can reach $\omega_1$
We can prove $\sup (f(n))$ is computable by induction since for all $n < \omega$, $f(n)$ is a finite sequence of computable function and successors, thus the result is computable. Then for $\omega = \sup (n)$, since all finite cases are computable, and the $\omega$th case is just a union of them all, it follows $f(\omega)$ should be computable, even if we don't have a way to write it down
While each $g_n$ is computable hence terminate in finite steps, the whole sequence is countable, thus by definition is the same as not terminating. Therefore $f(\omega)$ will run forever unless given countable steps. Thus $f(\omega)$ is uncomputable
Which means...:
$$f(\omega) = \omega_1^{CK}$$
looks like we just found a function that can shoot past that $\omega_1^{CK}$ barrier
After this point, things get a bit vague...
$f(\omega + 1) = \sup (g_{\omega} \omega_1^{CK}) + 1$ Two obvious choice for $g_{\omega}$ will be:
But the top one seems more suitable as it grows faster and $g_{n}$ is required to be a function that grows faster than the one in the previous stage
In fact, even a tower of $\omega_{\cdot}^{CK}$ is not fast enough,as after finite number of steps, it will get stuck
To be fast enough so that it does not get stuck in finite number of steps, we need something like $f(\omega_1^{CK})$. This is well defined as having $\omega_1^{CK}$, we can collapse it down to obtain all the countable ordinals (which will be given by some finite sequence of computable functions)
Hmm...
($+,\times, \wedge$) choose $\wedge$
because $\times = \sum +$ while $\wedge = \prod \cdots \prod (\sum +)$
hmm...
Ah I see now...
The reason I can get to $\omega_1^{CK}$ despite using only computable functions is because it is the function hierarchy $\{g_0,g_1,g_2,..\}$ is uncomputable.
Suppose we instead define the hierarchy to be one which adds two levels of $\Omega$ into the $\psi$ for each n, then the nth stage will be the notation $\psi ({}^{n}\Omega)$ which is computable and thus supremum can easily bring it to the $\omega$th level with the notation $\psi ({}^{\omega}\Omega) = BHO$ and be computable (thus never reaching $\omega_1^{CK})$
I was wondering whether there exists a (computable) sequence of numbers, for which it can be proven that no closed form can exist.
Edit: By closed form I mean an expression involving only a constant number of elementary functions. So something like a sum can not occur in the expression.
It is always easy to forge recurrence relations. E.g.
$$a_{n+1}=2a_n+\dfrac{1}{a_n}, a_0=1$$
But it is always hard to find the general closed form expression. And it is even harder to prove that there is no such expression.
Another example is here. And I highly suspect sequences like
$$a_n = \...
so, for the case of sequences, it is in general not known whether there always exists a theory that can check if a closed form (i.e. there exists a computable function that can enumerate all the elements of the sequence) exists
This means, it is not known whether we can construct $\{g_{\alpha}\}$ in such a way that it has no closed form as a function of $\alpha$, but nevertheless, computable
Python 3, ~ fε0(999)
N=9**9**9
def f(a,n):
if a[0]==[]:return a[1:]
if a[0][0]==[]:return[a[0][1:]]*n+a[1:]
return [f(a[0],n)]+a[1:]
a=eval("["*N+"]"*N)
n=2
while a:a=f(a,n);n+=1
print(n)
Try it online!
It is always easy to forge recurrence relations. E.g.
$$a_{n+1}=2a_n+\dfrac{1}{a_n}, a_0=1$$
But it is always hard to find the general closed form expression. And it is even harder to prove that there is no such expression.
Another example is here. And I highly suspect sequences like
$$a_n = \...
