2.2 Codificacion de infinituplas de numeros

Usaremos ${\omega }^N$ para denotar el conjunto de todas las infinituplas con coordenadas en $\omega$. Es decir $${\omega }^N=\left\{\right(s_1,s_2,...):s_i\in \omega \text{, para cada}i\ge 1\}\text{.}$$ Definamos el siguiente subconjunto de ${\omega }^N$ $${\omega }^{\left[N\right]}=\left\{\right(s_1,s_2,...)\in {\omega }^N:\text{hay un}n\in N\text{tal que}{s}_i=0,\text{para}i\ge n\}\text{.}$$ Notese que ${\omega }^N\ne {\omega }^{\left[N\right]}$, por ejemplo las infinituplas $$\begin{array}{cc}& (10,20,30,40,50,...)\\ & (1,0,1,0,1,0,1,0,...)\end{array}$$ no pertenecen a ${\omega }^{\left[N\right]}$. Notese que $(s_1,s_2,...)\in {\omega }^{\left[N\right]}$ si y solo si solo una cantidad finita de coordenadas de $(s_1,s_2,...)$ son no nulas (i.e. $\{i:s_i\ne 0\}$ es finito).

Definamos $$\begin{array}{ccc}pr:N& \to & \omega \\ n& \to & n\text{-esimo numero primo}\end{array}$$ Nótese que $pr\left(1\right)=2$, $pr\left(2\right)=3$, $pr\left(3\right)=5$, etc.

Es bien conocido que todo numero natural es expresable como producto de primos. Por ejemplo si tomamos $x=57596$ tenemos que $x=\mathrm{2.2.7.11.11.17}$. Tambien es un hecho conocido que dicha representacion en producto de primos es unica, si escribimos a los factores primos de menor a mayor, tal como lo hicimos recien con el numero $57596$. El Teorema Fundamental de la Aritmetica justamente acevera esta propiedad de factorisacion unica de todo numero natural. Trataremos de escribir este teorema de una forma un poco mas "cheta".

Ya que $57596=\mathrm{2.2.7.11.11.17}$, podemos escribir $$57596=pr(1{)}^2.pr(4{)}^1.pr(5{)}^2.pr(7{)}^1$$ Notese que ahora cada primo que interviene en la factorizacion de $57596$ figura con un exponente que nos dice cuantas veces ocurre en dicha factorizacion. Hay muchos primos que no ocurren en esta factorizacion, es decir ocurren $0$ veces en la misma. Pero podemos escribir $$57596=pr(1{)}^2.pr(2{)}^0.pr(3{)}^0.pr(4{)}^1.pr(5{)}^2.pr(6{)}^0.pr(7{)}^1.pr(8{)}^0.pr(9{)}^0.pr(10{)}^0....$$ y la igualdad no se altera ya que agregamos factores iguales a $1$ (una cantidad infinita!). De esta manera cada primo interviene en la factorizacion. Ademas si vemos la infinitupla de exponentes de dicha factorizacion, es decir $$(2,0,0,1,2,0,1,0,0,0,...)$$ obtenemos un elemento de ${\omega }^{\left[N\right]}$.

Por supuesto esto lo podemos hacer con cualquier numero natural y siempre la infinitupla de exponentes sera un elemento de ${\omega }^{\left[N\right]}$. Ademas es facil notar que estas representaciones "chetas" tambien resultan unicas.

Para probar nuestra version del Teorema Fundamental de la Aritmetica necesitaremos el siguiente lema el cual aceptaremos sin demostracion.

Proof. Primero probaremos la existencia por induccion en $x$. Claramente $1=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^0$, con lo cual tomando $(s_1,s_2,...)=(0,0,0,...)$ el caso $x=1$ esta probado. Fijemos ahora un $x>1$ y supongamos la existencia vale para cada $y$ menor que $x$. Veremos que entonces vale para $x$. Si $x$ es primo, entonces $x=pr\left(i_0\right)$ para algun $i_0$ por lo cual tenemos que $x=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i}$, tomando $s_i=0$ si $i\ne i_0$ y $s_{i_0}=1$. Si $x$ no es primo, entonces $x=y_1.y_2$, con $y_1,y_2<x$. Por hipotesis inductiva tenemos que hay $(s_1,s_2,...),(t_1,t_2,...)\in {\omega }^{\left[N\right]}$ tales que $y_1=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i}$ y $y_2=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{t_i}$. Tenemos entonces que $x=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i+t_i}$ lo cual concluye la prueba de la existencia.

Veamos ahora la unicidad. Suponganos que las infinituplas $(s_1,s_2,...),(t_1,t_2,...)\in {\omega }^{\left[N\right]}$ son tales que $$\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i}=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{t_i}$$ y ademas $s_i\ne t_i$ para algun $i$. Si $s_i>t_i$ entonces dividiendo ambos miembros por $pr(i{)}^{t_i}$ obtenemos que $pr\left(i\right)$ divide a un producto de primos todos distintos de el, lo cual es absurdo por el lema anterior. Analogamente llegamos a un absurdo si suponemos que $t_i>s_i$, lo cual nos dice que vale la unicidad.  

Como podra notarse la existencia en el teorema anterior es facil e intuitivamente clara de probar. En realidad la potencia del Teorema Fundamental de la Aritmética radica en el hecho de que dicha factorizacion es unica.

A continuacion un poco de notacion. Dada una infinitupla $(s_1,s_2,...)\in {\omega }^{\left[N\right]}$ usaremos $⟨s_1,s_2,...⟩$ para denotar al numero $\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i}$. Dado $x\in N$, usaremos $\left(x\right)$ para denotar a la unica infinitupla $(s_1,s_2,...)\in {\omega }^{\left[N\right]}$ tal que $$x=⟨s_1,s_2,...⟩=\underset{i=1}{\stackrel{\infty }{\Pi }}pr(i{)}^{s_i}$$ Ademas para $i\in N$, usaremos $(x{)}_i$ para denotar a $s_i$ de dicha unica infinitupla. Es decir que

1. (1) $\left(x\right)=\left(\right(x{)}_1,(x{)}_2,...)$

2. (2) $(x{)}_i$ es el exponente de $pr\left(i\right)$ en la (unica posible) factorizacion de $x$ como producto de primos

Claramente entonces

1. (3) $⟨(x{)}_1,(x{)}_2,...⟩=x$, para cada $x\in N$

2. (4) Para cada $(s_1,s_2,...)\in {\omega }^{\left[N\right]}$, se tiene que $$(⟨s_1,s_2,...⟩{)}_i=s_i\text{, para}i\in N$$ Es decir que $$\left(⟨s_1,s_2,...⟩\right)=(s_1,s_2,...)$$

(Justifique con palabras las propiedades (3) y (4)). Tenemos entonces el siguiente resultado fundamental

Proof. Llamemos $f$ a la funcion de la izquierda y $g$ a la de la derecha. Notese que el Lema 1.2 nos dice que basta con probar que $f\circ g=I{d}_{{\omega }^{\left[N\right]}}$ y $g\circ f=I{d}_N$. Pero (3) justamente nos dice que $g\circ f=I{d}_N$ y (4) nos dice que $f\circ g=I{d}_{{\omega }^{\left[N\right]}}$.  

Tal como se hace en la escuela primaria, el siguiente lema nos permite calcular $(x{)}_i$.

Proof. Ejercicio (aplique el Lema 2.8).  

Definamos la funcion $Lt:N\to \omega$ de la siguiente manera: $$Lt\left(x\right)=\{\begin{array}{ccc}{max}_i(x{)}_i\ne 0& & \text{si}x\ne 1\\ 0& & \text{si}x=1\end{array}$$ Se tienen las siguientes propiedades basicas