4.4.
Más Recursión IV Recursión para ω
4.4. Más Recursión para ω .
−
Hay muchas versiones o variantes de Recursión para ω, aquí en ZF , veamos
algunas de las más utilizadas. Antes de empezar, recordemos lo que nos dice el
Esquema de Recursión para ω.
Si A es una clase, G : A −→ A y a ∈ A, entonces hay una única función f tal, que
r
f : ω −→ A
f (0) = a
I)
Ba
II) ∀n ∈ ω f n + = G f (n)
Daremos 4 variantes, cada uno con una sugerencia para su justificación y un
ejemplo.
A). Si A es una clase, a ∈ A y G1 : A × ω −→ A, entonces hay una única función
f 1 tal, que
f 1 : ω −→ A
I) f 1 (0) = a
Ro
II) ∀n ∈ ω f 1 n + = G1 f 1 (n) , n
Observación:
f 1 (0) = a
f 1 (1) = G1 f 1 (0) , 0 = G1 (a, 0)
f 1 (2) = G1 f 1 (1) , 1 = G1 (G1 (a, 0) , 1)
f 1 (3) = G1 f 1 (2) , 2 = G1 G1 (G1 (a, 0) , 1) , 2
Ra
Para una prueba de A), hay que rehacer la prueba original.
Ejemplo: El factorial de un natural:
! : ω −→ ω
I) 0! = 1
II) n + ! = n! · n +
En este caso: A = ω, a = 1 y G1 : ω×ω −→ ω, con G1 p, q = p · q + para toda p, q ∈ ω.
12 15 Prof. Raf ael Rojas Barbachano
IV Recursión para ω 4.4. Más Recursión
B). Versión Paramétrica.
Si P es un conjunto, A una clase, H : P −→ A y G2 : P × A × ω −→ A, entonces hay
una única función f 2 tal que
f 2 : P × ω −→ A
I) ∀p ∈ P f 2 p, 0 = H p
r
II) ∀p ∈ P ∀n ∈ ω f 2 p, n + = G2 p, f 2 p, n , n
Para la prueba de B) se puede usar I).
Ba
Sugerencia: Define por recursión
una función f 1 : ω −→ P A como sigue, sean
f 1 (0) = H p y f1 n + = G1 f 1 (n) , n ; donde G1 : P A × ω −→
P
A y cuya regla
es
G1 (i , n) p = G2 p, i p , n . Finalmente ∀p ∈ P ∀m ∈ ω f 2 p, m = f 1 (m) p .
Ejemplo: La Suma entre Naturales:
+ : ω × ω −→ ω
I) ∀m ∈ ω m + 0 = m
II) ∀m ∈ ω m + n + = (m + n)+
Ro
Eneste caso:
P = ω, A = ω, H : ω −→ ω, con H = Id ω y G2 : ω × ω × ω −→ ω, con
G2 p, q, r = q + para todos p, q, r ∈ ω.
C). Recursión en función de valores tomados previamente.
Si a es un conjunto, denotamos el conjunto de todas las sucesiones finitas de
ω
elementos de a por, a. Formalmente,
ω
n
a= a
Ra
n∈ω
ω
Si a es un conjunto y g : a −→ a, entonces hay una única función f 3 tal, que
f 3 : ω −→ a
∀n ∈ ω f 3 (n) = g f 3 n
Observación:
f 3 (0) = g f 3 0 = g f 3 ∅ = g ∅ = g (0)
f 3 (1) = g f 3 1 = g 0, g (0)
Prof. Raf ael Rojas Barbachano 13 15
4.4. Más Recursión IV Recursión para ω
Para la prueba de C) se puede usar A).
Sugerencia: Sea G1 :S ×ω −→ A, G1 (x, n) = x ∪ n, g (x) , Por a), hay f 1 : ω −→ S
tal que f 1 (0) = ∅ y f 1 n + = G f 1 (n) , n . Finalmente, sea f 3 = f 1 .
Ejemplo: La Sucesión de Fibonacci es, 1,1,2,3,5,8,13,. . .
Para obtener la función que nos da la sucesión de Fibonacci, basta aplicar C) al
caso particular siguiente:
r
ω
Sean a = ω y g : ω −→ ω, definida como sigue:
⎧
⎪
⎨ 1 si DOM (t ) = 0
ω
Ba
Para t ∈ ω, sea g (t ) = 1 si DOM (t ) = 1
⎪
⎩
t (n) + t (n + 1) si DOM (t ) = n + 2, para algún n ∈ ω
por c) tendríamos que hay una única F : ω −→ ω tal que ∀n ∈ ω, F (n) = g F n .
Así,
F (0) = g (0) = 1
F (1) = g F 1 = 1
F (2) = g F 2 = F 2 (0) + F 2 (1) = F (0) + F (1) = 1 + 1 = 2
F (3) = g F 3 = F 2 (1) + F 2 (2) = F (1) + F (2) = 1 + 2 = 3
Ro
F (4) = F (2) + F (3) = 2 + 3 = 5
Podríamos decir, hay una única función F : ω −→ ω tal que
1. F (0) = 1 y F (1) = 1
2. ∀n ∈ ω F (n + 2) = F (n) + F (n + 1)
D) Recursión hasta un determinado número.
Si A es un conjunto, a ∈ A y g una función con DOM g ⊆ A×ω e IMG g ⊆ A,
Ra
entonces hay una única función f 4 tal, que
0) DOM f 4 = ω o DOM f 4 = k 0+ donde
k 0 = mi n k ∈ ω f (k), k ∉ DOM g
00) IMG f 4 ⊆ A
I) f 4 (0) = a
+
+
II) ∀n n ∈ DOM f 4 → f 4 n = g f 4 (n) , n
Para la prueba de D), se puede usar A).
Sugerencia: Sea A∗ = A ∪ {a ∗ }, donde a ∗ ∉ A. Define g ∗ : A∗ × ω −→ A∗ , como
sigue,
14 15 Prof. Raf ael Rojas Barbachano
IV Recursión para ω 4.4. Más Recursión
⎧
⎨ g (x, n) si (x, n) ∈ DOM g
g ∗ (x, n) =
⎩ a∗ en otro caso
con a) obtendrás f ∗ . Si f ∗ (i ) = a ∗ para algún i ∈ ω, considera f ∗ i para el menor
de tales i .
Ejemplo: Si X ⊆ ω , entonces hay una función inyectiva f con IMG f = X y tal
r
que DOM f = ω o DOM f ∈ ω.
Ba
Ro
Ra
Prof. Raf ael Rojas Barbachano 15 15