Ordinales (II)

Abstract. This is the second post about ordinals. In the first one I discussed well-orders and some countable examples. Now we’ll get an eagle’s view on induction and recursion.

Inducción y recursión en conjuntos bien ordenados.    La principal utilidad de los conjuntos bien ordenados es que para ellos valen los principios de inducción y de definición por recursión:

Teorema 1. Sea $\langle X,\preceq\rangle $ bien ordenado no vacío, con $0 := \min X$, y sea $P(\cdot)$ una propiedad que tenga sentido para elementos de $X$. Luego, $\bigl(\forall x\in X : P(x)\bigr)$ es equivalente a que se den:

  1. (caso base) $P(0)$, y

  2. (caso inductivo) Para todo $x\in X$, $\bigl(\forall y\in X : y \prec x \Rightarrow P(y)\bigr)$ implica $P(x)$.

Prueba. Sea $Y:=\{x\in X : P(x)\}$; probaremos que $Y=X$. Para ello, primero vemos que por el ítem 1 (caso base), $0\in Y$. Supongamos por el absurdo que $Y\neq X$. Luego, el conjunto $X\setminus Y =\{x\in X : \text{no se da }P(x)\}$ no es vacío así que tiene elemento mínimo $x_0$ según $\preceq$. Por minimalidad de $x_0$, obtenemos $\forall y \prec x_0 : P(y)$. Pero esto implica por 1 (caso inductivo) que $P(x_0)$, una contradicción. Entonces $X\setminus Y=\varnothing$ y luego $Y=X$. $\Box$
Observación 1. Notar que en la prueba anterior, considerar el caso base aparte es superfluo.

Las construcciones recursivas sobre ${\mathbb N}$ son muy útiles; un ejemplo paradigmático es la sucesión de Fibonacci, definida por las siguientes ecuaciones:

$\displaystyle \begin{array}{rlrl} \mathit{Fib}(0) &:= 0\\ \mathit{Fib}(1) &:= 1\\ \mathit{Fib}(n+2) &:= \mathit{Fib}(n+1) + \mathit{Fib}(n). \end{array} $

Se puede pensar que $\mathit{Fib}(n+2)$ está definida definida en términos de la restricción de la función $\mathit{Fib}$ al conjunto $\{n,n+1\}$.

Podemos imaginarnos un esquema mucho más general, donde usamos no sólo los últimos dos valores definidos sino todos los restantes. En ese caso, si estoy definiendo $F(n)$ podría suponer dada su restricción $f:=F|\{0,\dots,n-1\}$, y el paso recursivo sería una función $G$ que tome el dato $f$ y el dato $n$ y devuelva $F(n)$.

$\displaystyle F(n):= G(F|\{0,\dots,n-1\},n).$

En el caso de que $F$ es nuestra Fibonacci $\mathit{Fib}$, tendríamos:

$\displaystyle G(f,n):=\begin{cases} 0 &\text{si }n=0 \\ 1 &\text{si }n=1 \\ f(n-1)+ f(n-2) &\text{en otro caso.} \end{cases}$

En general, fijemos un conjunto bien ordenado $\langle X,\preceq\rangle $ y un conjunto de imagen $R$. Llamemos $I_\prec(x)$ a la segmento inicial determinado por $x$, $\{y\in X : y\prec x\}$ . Diremos que $G$ es una regla recursiva si para cada $x\in X$ y cada función $f:I_\prec(x) \rightarrow R$ nos devuelve un elemento de $R$.

Teorema 2 (definición por recursión). Sea $\langle X,\preceq\rangle $ bien ordenado. Entonces, para cada regla recursiva $G$ existe una única función $F$ que cumple

$\displaystyle F(x) = G(F|I_\prec(x),x)$

para todo $x\in X$.

Observación 2. En realidad, no es necesario fijar un conjunto $R$ de antemano. El Axioma de Reemplazo dice específicamente esto. Aunque este axioma no participa de los resultados elementales del álgebra y del análisis, sí es relevante, por ejemplo, para entender la estructura de los conjuntos borelianos.

El hallazgo que hace extremadamente útiles y potentes a estos teoremas, es el siguiente:

Teorema 3 (de Buena Ordenación). Para todo conjunto $X$ existe una relación $\preceq$ que lo bien-ordena.

Es bien sabido que el Teorema de Buena Ordenación es equivalente al Axioma de Elección (Reflexión: ¿cómo definir un buen orden sobre ${\mathbb R}$?). Con este resultado, ya tenemos un panorama muy jugoso de posibilidades de trabajo: se pueden definir y demostrar propiedades de manera “constructiva”, asumiendo un buen orden sobre el conjunto que estamos trabajando.

Sin embargo, se puede ir más allá y generalizar las operaciones aritméticas de ${\mathbb N}$ y por ende hablar de números transfinitos. Para ello necesitaremos abstraernos de buenos órdenes particulares y trabajar con sus tipos de isomorfismo. Lo haremos en el siguiente post.

Leave a Reply

Your email address will not be published. Required fields are marked *