Hablando informalmente, la buena ordenación combinada con la capacidad de ir "exactamente un paso atrás" (es decir, "restar uno") implica que la contabilidad de la estructura; y las propiedades del semigrupo naturalmente ordenado lo implican.
En un entorno más formal (y posiblemente no en la demostración más eficiente), dejemos que $(S,\circ,\preceq)$ sea un semigrupo naturalmente ordenado. Entonces:
-
Podemos hacer una simple observación que no es válida para los semigrupos ordenados generales, pero que se hace cierta una vez que tenemos la propiedad de cancelación de los naturalmente ordenados: Si $a\prec b$ entonces $(a\circ c)\prec (b\circ c)$ para cualquier $a,b,c\in S$ , donde $x \prec y$ significa $x \preceq y \wedge x\not=y$ (es decir, ser estrictamente más pequeño).
-
La propiedad de buen ordenamiento nos dice que hay algún elemento $\bar{0} \in S$ que es más pequeño que todos los demás elementos. Como sugiere la etiqueta, se comporta igual que cero en números naturales; $\bar{0}\circ x=x$ para cualquier $x$ en el semigrupo.
Para ver por qué, consideremos la propiedad de "sustracción" de los semigrupos naturalmente ordenados: Nos dice que como $\bar{0}\preceq\bar{0}$ tenemos $\bar{0}=\bar{0}+z$ para algunos $z\in S$ . Según la definición de $\bar{0}$ tenemos $\bar{0}\preceq z$ . Si la desigualdad fuera estricta, es decir, si tuviéramos $\bar{0}\prec z$ también tendríamos $\bar{0}+\bar{0} \prec \bar{0}+z = \bar{0}$ una imposibilidad. Por lo tanto, $\bar{0}+\bar{0}=\bar{0}$ .
Por último, para cualquier $x\in S$ tenemos $\bar{0}+x = \bar{0}+\bar{0}+x$ y la cancelación simplifica esto a $x = \bar{0}+x$ .
-
Desde $S$ tiene al menos dos elementos diferentes, el conjunto de elementos que difiere de $\bar{0}$ es no vacía y el ordenamiento nos da su elemento más pequeño, $\bar{1}$ que es estrictamente mayor que $\bar{0}$ pero más pequeño que todos los demás elementos. No es muy sorprendente que se comporte de forma similar al número un entre los naturales; siendo el bloque de construcción para construir (todos) los restantes.
-
Definamos $p_0=\bar{0}$ y $p_{i+1}=p_i\circ\bar{1}$ para que $p_1=\bar{1}$ , $p_2=(\bar{1}\circ\bar{1})$ y así sucesivamente. Como $\bar{0}\prec \bar{1}$ se puede utilizar una inducción fácil para demostrar que $p_i\prec p_j$ siempre que $i<j$ . Por lo tanto, el mapeo $i\mapsto p_i$ es en realidad un isomorfismo entre los semigrupos ordenados $(\mathbb{N},+,\leq)$ y $(\{p_0,p_1,\ldots\},\circ,\preceq)$ .
-
Hasta aquí todo bien; pero ¿qué pasa con los elementos de $S$ que son no de la forma $p_i$ para cualquier número natural $i$ ? Bueno, si hay alguno, el conjunto de todos esos extraño es no vacía y por lo tanto, utilizando la propiedad de buen ordenamiento una vez más, tiene el elemento más pequeño que llamaremos $s$ .
Tenemos $\bar{1}\preceq s$ , por lo que según las propiedades de los semigrupos naturalmente ordenados, $s$ puede expresarse como $s=1\circ t$ para algunos $t$ . Desde $\bar{0}\prec \bar{1}$ tenemos $t=\bar{0}\circ t\prec \bar{1}\circ t=s$ . Pero esto significa que $t$ debe ser igual a $p_i$ para algunos $i$ ya que $s$ era el elemento no expresable más pequeño. Pero entonces, $s=1\circ p_i=p_{i+1}$ y $s$ también sería expresable, lo que contradice su elección como no expresable.
-
En definitiva, hemos demostrado que el mapeo $i\mapsto p_i$ es un isomorfismo entre $(\mathbb{N},+,\leq)$ y $(S,\circ,\preceq)$ . Al ser un isomorfismo simétrico y transitivo, implica que todos los semigrupos naturalmente ordenados son isomorfos a $(\mathbb{N},+,\leq)$ y por lo tanto todos ellos deben ser contablemente infinitos también.
