Usaremos \(\omega^{\mathbf{N}}\) para denotar el conjunto de todas las infinituplas con coordenadas en \(\omega\). Es decir \[\omega^{\mathbf{N}}=\left\{ (s_{1},s_{2},...):s_{i}\in\omega\text{, para cada }i\geq1\right\} \text{.}\] Definamos el siguiente subconjunto de \(\omega^{\mathbf{N}}\) \[\omega^{\left[\mathbf{N}\right]}=\left\{ (s_{1},s_{2},...)\in\omega^{\mathbf{N}}:\text{ hay un }n\in\mathbf{N}\text{ tal que }s_{i}=0,\text{para }i\geq n\right\} \text{.}\] Notese que \(\omega^{\mathbf{N}}\neq\omega^{\left[\mathbf{N}\right]}\), por ejemplo las infinituplas \[\begin{aligned} & (10,20,30,40,50,...)\\ & (1,0,1,0,1,0,1,0,...) \end{aligned}\] no pertenecen a \(\omega^{\left[\mathbf{N}\right]}\). Notese que \((s_{1},s_{2},...)\in\omega^{\left[\mathbf{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}\neq0\}\) es finito).
Definamos \[\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo numero primo} \end{array}\] Nótese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Es bien conocido que todo numero natural es expresable como producto de primos. Por ejemplo si tomamos \(x=57596\) tenemos que \(x=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=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^{[\mathbf{N}]}\).
Por supuesto esto lo podemos hacer con cualquier numero natural y siempre la infinitupla de exponentes sera un elemento de \(\omega^{[\mathbf{N}]}\). 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.
2.6. Si \(p,p_{1},...,p_{n}\) son numeros primos y \(p\) divide a \(p_{1}.p_{2}.\ldots.p_{n}\), entonces \(p=p_{i}\), para algun \(i\).
2.1. Para cada \(x\in\mathbf{N}\), hay una unica infinitupla \((s_{1},s_{2},...)\in\omega^{\left[\mathbf{N}\right]}\) tal que \[x=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\] (Tiene sentido escribir \(\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\), ya que en esta productoria solo una cantidad finita de factores son no iguales a \(1\).)
Proof. Primero probaremos la existencia por induccion en \(x\). Claramente \(1=\underset{i=1}{\overset{\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(i_{0})\) para algun \(i_{0}\) por lo cual tenemos que \(x=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\), tomando \(s_{i}=0\) si \(i\neq 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[\mathbf{N}\right]}\) tales que \(y_{1}=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\) y \(y_{2}=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{t_{i}}\). Tenemos entonces que \(x=\underset{i=1}{\overset{\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[\mathbf{N}\right]}\) son tales que \[\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{t_{i}}\] y ademas \(s_{i}\neq t_{i}\) para algun \(i\). Si \(s_{i}>t_{i}\) entonces dividiendo ambos miembros por \(pr(i)^{t_{i}}\) obtenemos que \(pr(i)\) 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[\mathbf{N}\right]}\) usaremos \(\left\langle s_{1},s_{2},...\right\rangle\) para denotar al numero \(\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\). Dado \(x\in\mathbf{N}\), usaremos \((x)\) para denotar a la unica infinitupla \((s_{1},s_{2},...)\in\omega^{\left[\mathbf{N}\right]}\) tal que \[x=\left\langle s_{1},s_{2},...\right\rangle =\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\] Ademas para \(i\in\mathbf{N}\), usaremos \((x)_{i}\) para denotar a \(s_{i}\) de dicha unica infinitupla. Es decir que
adhocprefix(1)adhocsufix \((x)=((x)_{1},(x)_{2},...)\)
adhocprefix(2)adhocsufix \((x)_{i}\) es el exponente de \(pr(i)\) en la (unica posible) factorizacion de \(x\) como producto de primos
Claramente entonces
adhocprefix(3)adhocsufix \(\left\langle (x)_{1},(x)_{2},...\right\rangle =x\), para cada \(x\in\mathbf{N}\)
adhocprefix(4)adhocsufix Para cada \((s_{1},s_{2},...)\in\omega^{\left[\mathbf{N}\right]}\), se tiene que \[(\left\langle s_{1},s_{2},...\right\rangle )_{i}=s_{i}\text{, para }i\in\mathbf{N}\] Es decir que \[(\left\langle s_{1},s_{2},...\right\rangle )=(s_{1},s_{2},...)\]
(Justifique con palabras las propiedades (3) y (4)). Tenemos entonces el siguiente resultado fundamental
2.2. Las funciones \[\begin{array}{lll} \mathbf{N} & \rightarrow & \omega^{\left[\mathbf{N}\right]}\\ x & \rightarrow & (x)=((x)_{1},(x)_{2},...) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \omega^{\left[\mathbf{N}\right]} & \rightarrow & \mathbf{N}\\ (s_{1},s_{2},...) & \rightarrow & \left\langle s_{1},s_{2},...\right\rangle \end{array}\] son biyecciones una inversa de la otra.
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=Id_{\omega^{\left[\mathbf{N}\right]}}\) y \(g\circ f=Id_{\mathbf{N}}\). Pero (3) justamente nos dice que \(g\circ f=Id_{\mathbf{N}}\) y (4) nos dice que \(f\circ g=Id_{\omega^{\left[\mathbf{N}\right]}}\).
Tal como se hace en la escuela primaria, el siguiente lema nos permite calcular \((x)_{i}\).
2.7. Dados \(x,i\in\mathbf{N}\), se tiene que \[(x)_{i}=\max_{t}\left(pr(i)^{t}\text{ divide a }x\right)\]
Proof. Ejercicio (aplique el Lema 2.6).
Definamos la funcion \(Lt:\mathbf{N}\rightarrow\omega\) de la siguiente manera: \[Lt(x)=\left\{ \begin{array}{lll} \max_{i}\;(x)_{i}\neq0 & & \text{si }x\neq1\\ 0 & & \text{si }x=1 \end{array}\right.\] Se tienen las siguientes propiedades basicas
2.8. Para cada \(x\in\mathbf{N}\):
\(Lt(x)=0\) sii \(x=1\)
\(x=\prod\nolimits_{i=1}^{Lt(x)}pr(i)^{(x)_{i}}\)