Теорема рекурсии на ω

[gefest_md]

В одном учебнике встречаю две теоремы рекурсии, вторая в задачах:

Теорема 1. Пусть $A$ множество и $a\in A.$ Пусть $f\colon A\to A.$ Тогда существует единственная функция $h\colon \omega \to A$ такая, что
(1) $h(0)=a,$
(2) $h(n^+)=f(h(n))$, для любого $n\in\omega.$

Теорема 2. Пусть $A$ множество и $a\in A.$ Пусть $f\colon\omega\times A\to A.$ Тогда существует единственная функция $h\colon \omega \to A$ такая, что
(1) $h(0)=a,$
(2) $h(n^+)=f(n, h(n))$, для любого $n\in\omega.$

Позже приводится одно замечание, которое относится к доказательству счётности множества ${ }^{\in\omega}\!A$ (множество всех функций из некоторого $n\in\omega$ в $A$). Поэтому цитирую только часть, которая касается моего вопроса.

Цитата:

Suppose that $\ell\colon A\to\omega$ and $p\colon\omega\times\omega\to\omega$ are one-to-one functions. By the Recursion theorem 4.2.1. (Теорема 1), one obtains the indexed function $\langle h_n : n\in\omega\rangle,$ where $h_n\colon { }^{n}\!A\to\omega$ for all $n\in\omega,$ such that
(1) $h_n(\varnothing)=0$ (recall that ${ }^{0}\!A=\{\varnothing\}$);
(2) $h_{n^+}(f)=p(h_n(f\upharpoonright n), \ell( f(n)))$ for all $f\in { }^{n^{+}}\!\!A.$

Пытаясь понять это замечание, а именно как из теоремы рекурсии (1 или 2) следует существование функции $\langle h_n : n\in\omega\rangle,$ я сформулировал следующее предложение.

Предложение. Пусть $A$ множество, $\ell\colon A\to\omega$ и $p\colon\omega\times\omega\to\omega.$ Тогда существует функция $h\colon\omega\to\mathcal{P}\left({ }^{\in\omega}\!A\times\omega\right)$ такая, что
(1) $h(0)=\{\langle\varnothing, 0\rangle\},$
(2) $h(n^+)=\{\langle f,y\rangle\in {}^{n^+}\!\!A\times A\mid \forall x [\langle f\upharpoonright n, x\rangle\in h(n)\Rightarrow y=p(x,\ell(f(n)))]\}.$

Вопрос в том, следует ли предложение из замечания из теоремы рекурсии или из другой известной теоремы?

[dgwuqtj]

Вроде из теоремы 2 следует. У вас ведь $h(n^{+})$ определяется через $n$ и $h(n)$.

[gefest_md]

gefest_md в сообщении #1641833 писал(а):

(2) $h(n^+)=\{\langle f,y\rangle\in {}^{n^+}\!\!A\times A\mid \forall x [\langle f\upharpoonright n, x\rangle\in h(n)\Rightarrow y=p(x,\ell(f(n)))]\}.$

Должно быть

$h(n^+)=\{\langle f,y\rangle\in {}^{n^+}\!\!A\times \omega\mid \forall x [\langle f\upharpoonright n, x\rangle\in h(n)\Rightarrow y=p(x,\ell(f(n)))]\}.$

($\omega$ вместо $A$)

dgwuqtj в сообщении #1641859 писал(а):

Вроде из теоремы 2 следует. У вас ведь $h(n^{+})$ определяется через $n$ и $h(n)$.

В теореме 2 есть функция $f,$ внешняя. В моём предложении такой функции по-моему нет. А в замечании из учебника функция $h_{n^+}(f)$ от двух аргументов, чего нет в теореме 2.

Этот учебник Daniel Cunningham, Set theory: a first course. Замечание на стр. 122. Учебник напоминает учебник Herbert Enderton, Elements of set theory, но задачи более лёгкие.

[dgwuqtj]

Ну так $h(n^{+}) = F(n, h(n))$, где $F(n, X) = \{\langle f,y\rangle\in {}^{n^+}\!\!A\times \omega\mid \forall x [\langle f\upharpoonright n, x\rangle\in X\Rightarrow y=p(x,\ell(X))]\}$. Эта $F$ является функцией из $\omega \times \mathcal{P}\left({ }^{\in\omega}\!A\times\omega\right)$ в $\mathcal{P}\left({ }^{\in\omega}\!A\times\omega\right)$.

[gefest_md]

dgwuqtj
Спасибо. Полегчало.