Skip to main content
Fixed to match composition scheme in the question
Source Link
C7X
  • 2k
  • 1
  • 9
  • 31

According to Jeremy Avigad's "An ordinal analysis of admissible set theory using recursion on ordinal notations" (corollary 4.2), if $\alpha$ is closed under the primitive recursive ordinal functions, $\alpha=\omega$ or $\alpha$ is an output of the Veblen function $\varphi_\omega$. But to get a result about the $\mathcal{PR}_\omega$-reachable ordinals, we need a few more things:

Avigad's formulation of the prim. rec. ordinal functions is a bit different than the one in this question. However, they are equivalent, since both schemataschemes used are equivalent: The composition schemataschemes are equivalent, since Avigad's $f(\vec x)=h(g_1(\vec x),\ldots,g_k(\vec x))$ corresponds to the following repeated application of your question's composition scheme:

$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h\_{i-1}(y_1,\ldots,y_{i-1},g_i(y_i),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h_{i-1}(y_1,\ldots,y_{i-1},g_i(P^i_i(y_1,\ldots,y_i)),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$

And the primitive recursion schemataschemes are equivalent, since $\textrm{sup}_{\gamma<\beta}f(\alpha_1,\ldots,\alpha_m,\gamma)$ is equivalent to Avigad's $\bigcup\{f(u,\vec x)\mid u\in z\}$ (I believe there is a typo in the original - $x$ instead of $\vec x$.) Also, while in this question we have a constant function outputting $\omega$, in Avigad's paper we do not, and in fact $\omega$ is closed under Avigad's prim. rec. ordinal functions.

We can convert this result about closure under prim. rec. ordinal functions into one about $\mathcal{PR}_\omega$-reachability, since if there are prim. rec. ordinal functions $h$, $g$ such that $h(g(0))=\alpha$ for some ordinal $\alpha$, we have a prim. rec. ordinal function with $f(0)=\alpha$ by composition. Also if $\alpha=\omega$, while it's closed under Avigad's prim. rec. ordinal functions, $\mathcal{PR}_\omega$-reachability includes the function $\Omega$, so the least ordinal that's not $\mathcal{PR}_\omega$-reachable is $\varphi_\omega(0)$.

According to Jeremy Avigad's "An ordinal analysis of admissible set theory using recursion on ordinal notations" (corollary 4.2), if $\alpha$ is closed under the primitive recursive ordinal functions, $\alpha=\omega$ or $\alpha$ is an output of the Veblen function $\varphi_\omega$. But to get a result about the $\mathcal{PR}_\omega$-reachable ordinals, we need a few more things:

Avigad's formulation of the prim. rec. ordinal functions is a bit different than the one in this question. However, they are equivalent, since both schemata used are equivalent: The composition schemata are equivalent, since Avigad's $f(\vec x)=h(g_1(\vec x),\ldots,g_k(\vec x))$ corresponds to the following repeated application of your question's composition scheme:

$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h\_{i-1}(y_1,\ldots,y_{i-1},g_i(y_i),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$

And the primitive recursion schemata are equivalent, since $\textrm{sup}_{\gamma<\beta}f(\alpha_1,\ldots,\alpha_m,\gamma)$ is equivalent to Avigad's $\bigcup\{f(u,\vec x)\mid u\in z\}$ (I believe there is a typo in the original - $x$ instead of $\vec x$.) Also, while in this question we have a constant function outputting $\omega$, in Avigad's paper we do not, and in fact $\omega$ is closed under Avigad's prim. rec. ordinal functions.

We can convert this result about closure under prim. rec. ordinal functions into one about $\mathcal{PR}_\omega$-reachability, since if there are prim. rec. ordinal functions $h$, $g$ such that $h(g(0))=\alpha$ for some ordinal $\alpha$, we have a prim. rec. ordinal function with $f(0)=\alpha$ by composition. Also if $\alpha=\omega$, while it's closed under Avigad's prim. rec. ordinal functions, $\mathcal{PR}_\omega$-reachability includes the function $\Omega$, so the least ordinal that's not $\mathcal{PR}_\omega$-reachable is $\varphi_\omega(0)$.

According to Jeremy Avigad's "An ordinal analysis of admissible set theory using recursion on ordinal notations" (corollary 4.2), if $\alpha$ is closed under the primitive recursive ordinal functions, $\alpha=\omega$ or $\alpha$ is an output of the Veblen function $\varphi_\omega$. But to get a result about the $\mathcal{PR}_\omega$-reachable ordinals, we need a few more things:

Avigad's formulation of the prim. rec. ordinal functions is a bit different than the one in this question. However, they are equivalent, since both schemes used are equivalent: The composition schemes are equivalent, since Avigad's $f(\vec x)=h(g_1(\vec x),\ldots,g_k(\vec x))$ corresponds to the following repeated application of your question's composition scheme:

$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h_{i-1}(y_1,\ldots,y_{i-1},g_i(P^i_i(y_1,\ldots,y_i)),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$

And the primitive recursion schemes are equivalent, since $\textrm{sup}_{\gamma<\beta}f(\alpha_1,\ldots,\alpha_m,\gamma)$ is equivalent to Avigad's $\bigcup\{f(u,\vec x)\mid u\in z\}$ (I believe there is a typo in the original - $x$ instead of $\vec x$.) Also, while in this question we have a constant function outputting $\omega$, in Avigad's paper we do not, and in fact $\omega$ is closed under Avigad's prim. rec. ordinal functions.

We can convert this result about closure under prim. rec. ordinal functions into one about $\mathcal{PR}_\omega$-reachability, since if there are prim. rec. ordinal functions $h$, $g$ such that $h(g(0))=\alpha$ for some ordinal $\alpha$, we have a prim. rec. ordinal function with $f(0)=\alpha$ by composition. Also if $\alpha=\omega$, while it's closed under Avigad's prim. rec. ordinal functions, $\mathcal{PR}_\omega$-reachability includes the function $\Omega$, so the least ordinal that's not $\mathcal{PR}_\omega$-reachable is $\varphi_\omega(0)$.

Source Link
C7X
  • 2k
  • 1
  • 9
  • 31

According to Jeremy Avigad's "An ordinal analysis of admissible set theory using recursion on ordinal notations" (corollary 4.2), if $\alpha$ is closed under the primitive recursive ordinal functions, $\alpha=\omega$ or $\alpha$ is an output of the Veblen function $\varphi_\omega$. But to get a result about the $\mathcal{PR}_\omega$-reachable ordinals, we need a few more things:

Avigad's formulation of the prim. rec. ordinal functions is a bit different than the one in this question. However, they are equivalent, since both schemata used are equivalent: The composition schemata are equivalent, since Avigad's $f(\vec x)=h(g_1(\vec x),\ldots,g_k(\vec x))$ corresponds to the following repeated application of your question's composition scheme:

$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h\_{i-1}(y_1,\ldots,y_{i-1},g_i(y_i),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$

And the primitive recursion schemata are equivalent, since $\textrm{sup}_{\gamma<\beta}f(\alpha_1,\ldots,\alpha_m,\gamma)$ is equivalent to Avigad's $\bigcup\{f(u,\vec x)\mid u\in z\}$ (I believe there is a typo in the original - $x$ instead of $\vec x$.) Also, while in this question we have a constant function outputting $\omega$, in Avigad's paper we do not, and in fact $\omega$ is closed under Avigad's prim. rec. ordinal functions.

We can convert this result about closure under prim. rec. ordinal functions into one about $\mathcal{PR}_\omega$-reachability, since if there are prim. rec. ordinal functions $h$, $g$ such that $h(g(0))=\alpha$ for some ordinal $\alpha$, we have a prim. rec. ordinal function with $f(0)=\alpha$ by composition. Also if $\alpha=\omega$, while it's closed under Avigad's prim. rec. ordinal functions, $\mathcal{PR}_\omega$-reachability includes the function $\Omega$, so the least ordinal that's not $\mathcal{PR}_\omega$-reachable is $\varphi_\omega(0)$.