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{.}\] Nótese 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]}\). Nótese 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 número primo} \end{array}\] Nótese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Es bien conocido que todo número natural es expresarle como producto de primos. Por ejemplo si tomamos \(x=57596\) tenemos que \(x=2.2.7.11.11.17\). También es un hecho conocido que dicha representación en producto de primos es única, si escribimos a los factores primos de menor a mayor, tal como lo hicimos recién con el número \(57596\). El Teorema Fundamental de la Aritmética justamente asevera esta propiedad de factorización única de todo número 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}\] Nótese que ahora cada primo que interviene en la factorización de \(57596\) figura con un exponente que nos dice cuantas veces ocurre en dicha factorización. Hay muchos primos que no ocurren en esta factorización, 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 factorización. Además si vemos la infinitupla de exponentes de dicha factorización, 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 número natural y siempre la infinitupla de exponentes será un elemento de \(\omega^{[\mathbf{N}]}\). Además es fácil notar, basándose en el Teorema Fundamental de la Aritmética, que estas representaciones "chetas" también resultan únicas. O sea que tenemos el siguiente teorema:
2.1 (Teorema Fundamental de la Aritmética Versión Cheta). Para cada \(x\in\mathbf{N}\), hay una única 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 usando la Regla de Inducción Completa a partir de \(1\). Para cada \(x\in\mathbf{N}\) sea \(\mathrm{Enu}_{x}\) el siguiente enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{x}\): hay una infinitupla \((s_{1},s_{2},...)\in\omega^{\left[\mathbf{N}\right]}\) tal que \(x=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\)
Claramente \(1=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{0}\), con lo cual tomando \((s_{1},s_{2},...)=(0,0,0,...)\) probamos que \(\mathrm{Enu}_{1}\) es verdadero. Fijemos ahora un \(x\geq1\) y supongamos que \(\mathrm{Enu}_{y}\) es verdadero para cada \(y\) menor o igual que \(x\). Probaremos que entonces \(\mathrm{Enu}_{x+1}\) es verdadero. Supongamos primero que \(x+1\) es primo. Entonces \(x=pr(i_{0})\) para algún \(i_{0}\) por lo cual tenemos que \[x+1=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\] tomando \(s_{i}=0\) si \(i\neq i_{0}\) y \(s_{i_{0}}=1\). Es claro que entonces \(\mathrm{Enu}_{x+1}\) es verdadero. Supongamos ahora que \(x+1\) no es primo. Entonces \(x+1=y_{1}.y_{2}\), con \(y_{1},y_{2}<x+1\). Ya que \(y_{1},y_{2}\leq x\) tenemos que \(\mathrm{Enu}_{y_{1}}\) y \(\mathrm{Enu}_{y_{2}}\) son verdaderos. O sea 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+1=\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}+t_{i}}\] lo cual nos dice que \(\mathrm{Enu}_{x+1}\) es verdadero. O sea que la Regla de Inducción Completa a partir de \(1\) nos asegura que \(\mathrm{Enu}_{x}\) es verdadero para cada \(x\in\mathbf{N}\).
Para completar la demostración debemos probar la unicidad para lo cual basta con probar la siguiente afirmación:
adhocprefix(1)adhocsufix Si \((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}}\] entonces \((s_{1},s_{2},...)=(t_{1},t_{2},...)\).
Usaremos el siguiente resultado el cual aceptaremos sin demostración.
adhocprefix(2)adhocsufix Si \(p,p_{1},...,p_{n}\) son números primos y \(p\) divide a \(p_{1}.p_{2}.\ldots.p_{n}\), entonces \(p=p_{i}\), para algún \(i\).
Supongamos que \((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 además \((s_{1},s_{2},...)\neq(t_{1},t_{2},...)\). Llegaremos a un absurdo. Sea \(i_{0}\) tal que \(s_{i_{0}}\neq t_{i_{0}}\). Si \(s_{i_{0}}>t_{i_{0}}\) entonces dividiendo ambos miembros de la igualdad por \(pr(i_{0})^{t_{i}}\) obtenemos que \(pr(i_{0})\) divide a un producto de primos todos distintos de él, lo cual es absurdo por (2). Análogamente llegamos a un absurdo si suponemos que \(t_{i_{0}}>s_{i_{0}}\). Concluimos así la prueba de (1) y también la del teorema.
Como podrá notarse la existencia en el teorema anterior es fácil e intuitivamente clara de probar. En realidad la potencia del Teorema Fundamental de la Aritmética radica en el hecho de que la factorización es única, lo cual demanda mas trabajo matemático para su demostración.
A continuación un poco de notación. 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 número \(\underset{i=1}{\overset{\infty}{\Pi}}pr(i)^{s_{i}}\). Dado \(x\in\mathbf{N}\), usaremos \((x)\) para denotar a la única 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}}\] Además para \(i\in\mathbf{N}\), usaremos \((x)_{i}\) para denotar la \(i\)-ésima coordenada de \((x)\). Es decir que
adhocprefix(1)adhocsufix \((x)=((x)_{1},(x)_{2},...)\)
adhocprefix(2)adhocsufix \((x)_{i}\) es el exponente de \(pr(i)\) en la (única posible) factorización de \(x\) como producto de primos
Se le suele llamar la "bajada \(i\)-ésima de \(x\)" al número \((x)_{i}\). La idea de este nombre es que para obtener \((x)_{i}\) debemos bajar el exponente de \(pr(i)\) en la factorización de \(x\). 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 )=(s_{1},s_{2},...)\] Es decir que \((\left\langle s_{1},s_{2},...\right\rangle )_{i}=s_{i}\text{, para }i\in\mathbf{N}\).
(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 función de la izquierda y \(g\) a la de la derecha. Nótese que el Lema 1.3 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]}}\).
El siguiente resultado nos permite calcular \((x)_{i}\), tal como se hace en la escuela primaria.
2.10. 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 resultado establecido en el punto (1) de la prueba del Teorema Fundamental de la Aritmética Versión Cheta).
Definamos la función \(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 básicas
2.11. Para cada \(x\in\mathbf{N}\):
adhocprefix(1)adhocsufix \(Lt(x)=0\) sii \(x=1\)
adhocprefix(2)adhocsufix \(x=\prod\nolimits_{i=1}^{Lt(x)}pr(i)^{(x)_{i}}\)
2.1. Pruebe que si \(x,y\in\mathbf{N}\), entonces
adhocprefix(a)adhocsufix \((x)_{i}\leq x\), para cada \(i\in\mathbf{N}\)
adhocprefix(b)adhocsufix \((x.y)_{i}=(x)_{i}+(y)_{i}\), para cada \(i\in\mathbf{N}\)
adhocprefix(c)adhocsufix \(x|y\) si y solo si \((x)_{i}\leq(y)_{i}\), para cada \(i\in\mathbf{N}\)