1
$\begingroup$

Let $\alpha$ denote the ordinal described in section 2.24 of the book “A zoo of ordinals” [David A. Madore]:

2.24. The smallest ordinal $\alpha$ such that $L_{\alpha} \models {\text{ZFC}}$ (assuming it exists), i.e., the height of the minimal model of ZFC.

I have found Quote 1 ( source ):

one can philosophically accept the notion of ordinalhood as somehow describing the "well-definedness" of concepts -- that is, an ordering of the integers is said to be an ordinal if any recursive definition (in a particular formal language) of a function $f:\mathbb N\to\mathbb N$ of the form $$f(n) = F(f\upharpoonleft \{m : m < n\})$$ determines a well-defined total function $f:\mathbb N\to\mathbb N$.

The question is: if we assume that $\alpha$ exists and use this ordinal as the base of Slow-growing hierarchy, can we assume that $g_{\alpha}(n)$ will, in fact, represent a total function that evaluates to a finite natural number for all $n$? If no (or yes), what is the mathematical explanation? And if the answer is “No”, does this contradict Quote 1?

$\endgroup$

1 Answer 1

2
$\begingroup$

Well, first of all you're making a mistake re: the slow-growing hierarchy - it's not indexed by ordinals, but rather families of fundamental sequences of ordinals (or copies of ordinals, or etc.). This is an unavoidable difference, since there is in general no good way to assign a fundamental sequence (or copy) to every countable ordinal.

  • Incidentally, this can be made precise in various ways - for example, it's consistent with ZF (= set theory without the axiom of choice) that there is no function assigning each countable ordinal a fundamental sequence at all, and "lower down" there are computability-theoretic obstacles to assigning fundamental sequences to each computable ordinal simultaneously. (And this is really a general point about hierarchies through the countable ordinals, not the slow-growing hierarchy specifically.)

  • The slow- or fast-growing hierarchies we care about are for this reason not defined through all the countable ordinals, but rather only up to some fixed countable ordinal leading up to which we've already defined a family of fundamental sequences ($\epsilon_0$ is a common stopping point). I've certainly never seen such a hierarchy continued even through all the computable ordinals, and $\alpha$ is far, far greater than any computable ordinal.


Having said that, the answer to your question is yes. For any countable ordinal $\mu$ whatsoever, there is an assignment $\mathfrak{S}$ of fundamental sequences to every limit ordinal $\le\mu$ (this $\mathfrak{S}$ wont' be unique, but such a thing will exist). Using any such $\mathfrak{S}$ we can assign a slow-growing function to each ordinal $\le\mu$ in the usual way. But note that the dependence on the specific choice of $\mathfrak{S}$, coupled with the lack of a general way to pick a specific $\mathfrak{S}$, means that in general there is no specific function deserving to be called "the $\mu$th slow-growing function."

In particular, the special properties of $\alpha$ are completely irrelevant here. Any countable ordinal (including $\alpha$ if it exists) has fundamental-sequence-families,$^*$ and with respect to each such family there will be an $\alpha$th corresponding slow-growing function.


$^*$Why is this? Well, perhaps surprisingly in light of the weird ZF fact mentioned above, this has an easy proof! And one which makes use of the notion of a copy of an ordinal.

Specifically, suppose $\theta$ is a countable limit ordinal. Since it's countable, there's a well-ordering $R$ of $\omega$ with order-type $\theta$. (Note that this $R$ isn't unique - and in fact there's no way to "canonically" pick $R$, and this is why this proof doesn't contradict the weird ZF fact mentioned above!) I'm going to use $R$ to get a fundamental sequence for every limit ordinal $\le \theta$.

Each $n\in\omega$ has, via $R$, a corresponding ordinal $[n]_R<\theta$: namely, the ordinal corresponding to the ordertype of the set $\{m\in\omega: mRn\}$ ordered by (the restriction of) $R$. For example, taking $\theta=\omega+\omega$ and $R$ to be the ordering $$1\prec 3\prec 5\prec 7\prec ...\prec 0\prec 2\prec 4\prec 6\prec ...,$$ we have $[6]_R=\omega+3$. Now for $\eta\le\theta$ a limit:

  • We first define a sequence $(n^\eta_i)_{i\in\omega}$ of natural numbers given by $$n^\eta_i=\min\{m\in\omega: [m]_R<\eta, m>n^\eta_j\mbox{ for all $j<i$}\}.$$ Importantly, the first "$<$" there refers to the usual ordering on the ordinals, while the "$\min$," the "$>$," and the second "$<$" refer to the usual ordering on the naturals.

  • We now use this to define a sequence of ordinals $(\gamma_i^\eta)_{i\in\omega}$ of ordinals $\le\eta$ given by $\gamma^\eta_i=([n^\eta_i]_R)_{i\in\omega}$.

It's now easy to check that for each limit ordinal $\eta\le\theta$ the sequence $(\gamma_i^\eta)_{i\in\omega}$ is a fundamental sequence for $\eta$.

For example, taking $R$ as above and $\eta=\theta=\omega+\omega$, we get $$(n_i^\eta)_{i\in\omega}=(1,2,4,6,8,10,...),$$ and this gives the fundamental sequence $$0,\omega+1,\omega+2,\omega+3,...$$

(because $[1]_R=0,[2]_R=\omega+1,[4]_R=\omega+2$, ...).

$\endgroup$
12
  • 1
    $\begingroup$ @lyricallywicked Note that $[m]_R$ is an ordinal and $n^\eta_j$ is just some number (even if we think of $n^\eta_j$ as a finite ordinal the comparison $[m]_R>n^\eta_j$ will always return true when $[m]_R>\omega$). For your second question, if you go exactly by the def. given in the answer, you wouldn't pick the number corresponding to zero ordinal (or the next one). You will select the smallest number $m$ such that $[m]_R<\eta$ (the second condition in def. of $n^\eta_i$ will be vacuously true when $i=0$). Also answer has very minor typo for sequence $n^\eta_i$. It should be $(0,2,4,6,...)$ $\endgroup$
    – SSequence
    Commented Sep 12, 2018 at 8:47
  • 1
    $\begingroup$ @lyricallywicked Yes you are right that $[1]_R<\eta$ . But it is also true that $[0]_R<\eta$. And when we are trying to find $n^\eta_0$, the second condition ($m>n^\eta_j $$\mbox{ for all $j<i$}$) will be vacuously true (one can plug in $i=0$ in that second condition and check). So the number $0$ is the smallest one that satisfies both the conditions. $\endgroup$
    – SSequence
    Commented Sep 12, 2018 at 9:46
  • 1
    $\begingroup$ For example, in this specific case, we will get $n^\eta_0=\min\{0,1,2,3,4,....\}=0$. That's because for any given number $m$ the first condition $[m]_R<\eta$ will always be true (the second condition condition will turn out to be vacuously true anyway). $\endgroup$
    – SSequence
    Commented Sep 12, 2018 at 9:55
  • 2
    $\begingroup$ @lyricallywicked I believe the second condition has a typo and should be $[m]_R>[n^\eta_j]_R$ $\mbox{ for all $j<i$}$. I hope that clarifies any confusions. $\endgroup$
    – SSequence
    Commented Sep 12, 2018 at 11:27
  • 1
    $\begingroup$ (I think I am adding way too many comments ... but anyway)...... Also you might find it interesting to show that given the def. of $n^\eta_i$, the sequence of natural numbers $(n^\eta_i)_{i\in\omega}$ is strictly increasing. $\endgroup$
    – SSequence
    Commented Sep 12, 2018 at 12:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .