You are currently browsing the monthly archive for julio 2014.

— 1. Los axiomas de Peano —

Vamos a presentar una manera estándar de definir los números naturales, en términos de los Axiomas de Peano, que fueron propuestos por primera vez por Giuseppe Peano (1858–1932). Esta no es la única manera de definir los números naturales. Por ejemplo, otro enfoque adicional es hablar acerca de la cardinalidad de los conjuntos finitos, por ejemplo, uno podría tomar un conjunto con cinco elementos y definir {5} como el número de elementos en ese conjunto. Vamos a discutir este enfoque alternativo en la Sección ¿?. Sin embargo, vamos seguir con el enfoque axiomático de Peano por ahora.

¿Cómo definimos lo que son los números naturales? Informalmente, podríamos decir

Definición 1. (Informal) Un número natural es cualquier elemento del conjunto

\displaystyle  \mathbb N := \{ 0, 1, 2, 3, 4, \ldots \},

que es el conjunto de todos lo números creados comenzando con 0 y luego contando hacia adelante indefinidamente. Llamaremos {\mathbb N} al conjunto de los números naturales.

Observación 1. En algunos textos, los números naturales comienzan en {1}, en vez de {0}, pero esto es una cuestión de convención en la notación más que cualquier otra cosa. En este texto, nos referiremos al conjunto {\{ 1, 2, 3, \dotso \}} como los enteros positivos {{\mathbf Z}^+} en lugar de los números naturales. Los números naturales a veces son también conocidos como los números completos.

En cierto sentido, esta definición resuelve el problema de los que son los números naturales: un número natural es cualquier elemento del conjunto* {\mathbb N}. Sin embargo, nos es realmente tan satisfactorio, porque plantea la cuestión de qué es {\mathbb N}. Esta definición de “empezar a {0} y contar indefinidamente” parece una definición lo suficientemente intuitiva de {\mathbb N}, pero no es del todo aceptable, debido a que deja muchas preguntas sin respuesta. Por ejemplo: ¿cómo sabemos que podemos seguir contando indefinidamente, sin cíclicamente volver a {0}? Además, ¿cómo se realizan las operaciones como la adición, multiplicación o exponenciación?

(Estrictamente, hay otro problema con esta definición informal: aún no hemos definido lo que es un “conjunto”, o lo que es “elemento de”. Así, para el resto de este capítulo, vamos a evitar la mención de conjuntos y sus elementos tanto como sea posible, excepto en la discusión informal.)

Podemos empezar respondiendo esta última pregunta: podemos definir operaciones complicadas en términos de operaciones más simples. La exponenciación no es más que una multiplicación repetida: {5^3} no es mas que tres cincos multiplicados entre sí. La multiplicación no es más que una adición repetida; {5 \times 3} no es más que tres cincos sumados entre sí. (La sustracción y división no serán cubiertas aquí, debido a que no son operaciones bien-adaptadas a los números naturales; tendrán que esperar por los enteros y racionales, respectivamente.) ¿Y la adición? No es nada más que la operación de contar hacia adelante repetida, o de incremento. Si suma tres a cinco, lo que está haciendo es incrementar cinco tres veces. Por otro lado, el incremento parece ser una operación fundamental, no reducible a cualquier otra operación más simple; en efecto, es la primera operación que uno aprender en números, incluso antes de aprender a sumar.

Así, para definir los números naturales, vamos a utilizar dos conceptos fundamentales, el número cero {0} y la operación de incremento. En deferencia a los lenguajes de programación modernos, usaremos {n\!+\!\!+} para denotar el incremento o sucesor de {n}, así por ejemplo, {3\!+\!\!+ = 4}, {(3\!+\!\!+)\!+\!\!+ = 5}, etc. Se trata de un uso un tanto diferente de lo que se da en los lenguajes de programación como C, donde {n\!+\!\!+}, de hecho, redefine el valor de {n} por su sucesor; sin embargo en matemáticas, no tratamos de definir una variable más de una vez en un entorno determinado, ya que a menudo puede conducir a una confusión; muchas de las afirmaciones que eran verdad para el valor antiguo de la variable, puede llegar a ser falso para el valor actual, y viceversa.

Así, parece que queremos decir que {\mathbb N} consta de {0} y todo aquello que puede ser obtenido de {0} por el incremento: {\mathbb N} debe consistir de los objetos

\displaystyle  0, 0\!+\!\!+, (0\!+\!\!+)\!+\!\!+, ((0\!+\!\!+)\!+\!\!+)\!+\!\!+, \text{etc.}

Si empezamos a escribir los que esto quiere decir acerca de los números naturales, veremos así, que deben tener los siguiente axiomas referentes a {0} y la operación de incremento {\!+\!\!+}:

Axioma 1. {0} es un número natural.

Axioma 2. Si {n} es un número natural, entonces {n\!+\!\!+} es también un número natural.

Así, por ejemplo, del Axioma 1 y dos aplicaciones del Axioma 2, vemos que {(0\!+\!\!+)\!+\!\!+} es un número natural. Por supuesto, esta notación comenzará a ser difícil de manejar, así que adoptaremos una convención para escribir estos números en una notación más familiar:

Definición 2. Definimos 1 como el número {0\!+\!\!+}, 2 como el número {(0\!+\!\!+)\!+\!\!+}, 3 como el número {((0\!+\!\!+)\!+\!\!+)\!+\!\!+}, etc. (En otras palabras, {1 := 0\!+\!\!+}, {2 := 1\!+\!\!+}, {3 := 2\!+\!\!+}, etc. En este texto, usaré “{x := y}” para denotar la afirmación de que {x} se define igual a {y}.)

Así, por ejemplo, tenemos

Proposición 3. {3} es un número natural.

Demostración. Por el Axioma 1, {0} es un número natural. Por el Axioma 2, {0\!+\!\!+ = 1} es un número natural. Por el Axioma 2, una vez más, {1\!+\!\!+ = 2} es un número natural. Por el Axioma 2, otra vez, {2\!+\!\!+ = 3} es un número natural. \Box

Esto puede parecer que es suficiente para describir los números naturales. No obstante, no tenemos establecido completamente el comportamiento de {\mathbb N}:

Ejemplo 1. Considerar un sistema numérico que consiste de los números {0, 1, 2, 3}, en el cual la operación de incremento vuelve de {3} a {0}. Precisando más, {0\!+\!\!+} es igual a {1}, {1\!+\!\!+} es igual a {2}, {2\!+\!\!+} es igual a {3}, pero {3\!+\!\!+} es igual a {0} (y, también, igual a {4}, por la definición de {4}). Este tipo de cosas, de hecho suceden en la vida real, cuando uno utiliza una computadora para tratar de almacenar un número natural: si uno empieza en {0} y ejecuta la operación de incremento repetidamente, eventualmente la computadora desbordará su memoria y el número volverá de nuevo a {0} (aunque esto puede tomar una cantidad bastante grande de operaciones de incremento; por ejemplo, una representación de un entero a dos-bytes volverá solamente después de {65, 536} incrementos). Notar que este tipo de sistemas numéricos obedecen el Axioma 1 y el Axioma 2, a pesar de que claramente no corresponde con lo que intuitivamente creemos que son similares a los números naturales.

Para prevenir este tipo de “incidencia de volver de nuevo”, impondremos otro axioma:

Axioma 3. {0} no es el sucesor de ningún número natural; i.e., tenemos {n\!+\!\!+ \ne 0} para todo número natural {n}.

Luego, podemos mostrar que ciertos tipos de vueltas no ocurren: por ejemplo, ahora podemos descartar el tipo de comportamiento en el Ejemplo 1, usando

Proposición 4. {4} no es igual a {0}.

¡No se ría! Debido a cómo hemos definido {4} —esto es, el incremento del incremento del incremento del incremento de {0}— no es necesariamente cierto, a priori, que este número no es lo mismo que cero, incluso si es “evidente”. (“a priori” en latín significa “de antemano” —se refiere a lo que ya se sabe o supone cierto antes de empezar una demostración o un argumento. Lo opuesto es “a posteriori” —lo que se sabe que es verdad después de que la demostración o argumento es concluido.) Notar, por ejemplo, que en el Ejemplo 1, {4} era de hecho igual a {0}, y que en un computadora, la representación estándar de dos bytes de un número natural, por ejemplo, 65536 es igual a {0} (usando nuestra definición de 65536 como igual a {0} incrementado sesenta y cinco mil, quinientos treinta y seis veces.)

Demostración. Por definición, {4 = 3\!+\!\!+}. Por los Axiomas 1 y 2, {3} es un número natural. En consecuencia por el Axioma 3, {3\!+\!\!+ \ne 0}, i.e., {4 \ne 0}. \Box

Sin embargo, incluso con nuestro nuevo axioma, todavía es posible que nuestro sistema numérico se comporte de otras maneras patológicas:

Ejemplo 2. Considere el sistema numérico que consiste de cinco números {0, 1, 2, 3, 4}, en el que la operación de incremento tiene un “techo” en {4}. Precisando más, supongamos que {0\!+\!\!+ = 1}, {1\!+\!\!+ = 2}, {2\!+\!\!+ = 3}, {3\!+\!\!+ = 4}, pero {4\!+\!\!+ = 4} (o, en otras palabras, que {5 = 4}, y por lo tanto {6 = 4}, {7 = 4}, etc.). Esto no es contradictorio con los Axiomas 1, 2, 3. Otro sistema numérico con un problema similar es aquel en el cual el incremento da vueltas, pero no a cero, e.g., supongamos que {4\!+\!\!+ = 1} (de modo que {5 = 1}, entonces {6 = 2}, etc.).

Hay muchas maneras de prohibir los tipos de comportamientos mencionados antes, evitando que ocurran, pero uno de las más simples es asumir el siguiente axioma:

Axioma 4. Números naturales distintos deben tener sucesores distintos; i.e., si {n}, {m} son números naturales y {n \ne m}, entonces {n\!+\!\!+ \ne \!+\!\!+}. Equivalentemente*, si {n\!+\!\!+ = m\!+\!\!+}, entonces debemos tener {n = m}.

(Esto es un ejemplo de re-formular una implicación usando su contrapositivo (o recíproco); ver la Sección ¿? para más detalles.)

Así, por ejemplo, tenemos

Proposición 5. {6} no es igual a {2}.

Demostración. Supongamos, en pos de la contradicción, que {6 = 2}. Entonces {5\!+\!\!+ = 1\!+\!\!+}, y por el Axioma 4 tenemos {5 = 1}, y así {4\!+\!\!+ = 0\!+\!\!+}. Por el Axioma 4 de nuevo tenemos {4 = 0}, lo que contradice nuestra proposición previa. \Box

Como se puede ver de esta proposición, ahora parece que podemos mantener todos los números naturales distintos unos de los otros. Hay, sin embargo, aún otro problema más: mientras que los axiomas (particularmente los Axiomas 1 y 2) nos permiten confirmar que {0, 1, 2, 3, \dotso} son distintos elementos de {\mathbb N}, existe el problema de que puede haber otros elementos “incontrolados” en nuestro sistema numérico que no son de esta forma:

Ejemplo 3. (Informal) Supongamos que nuestro sistema numérico {\mathbb N} consistió de la siguiente colección de enteros y enteros-mitad:

\displaystyle  \mathbb N := \{0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, \dotso \}.

(Este ejemplo está marcado como “informal” ya que estamos usando números reales, los cuales no deberían ser usados aún.) Uno puede verificar que los Axiomas 14 todavía son satisfechos para este conjunto.

Lo que queremos es algún axioma que diga que los únicos números en {\mathbb N} son aquellos que pueden ser obtenidos desde el {0} y la operación de incremento —con el fin de excluir elementos como {0.5}. Pero es difícil de cuantificar lo que entendemos por “poder ser obtenido desde” sin estar ya utilizando los números naturales. Afortunadamente, existe una solución ingeniosa para tratar de capturar este hecho:

Axioma 5 (Principio de inducción matemática). Sea {P(n)} cualquier propiedad perteneciente a un número natural {n}. Supongamos que {P(0)} es cierto, y supongamos que siempre que {P(n)} es cierto, {P(n\!+\!\!+)} también es cierto. Entonces {P(n)} es cierto para todo número natural {n}.

Observación 2. Somos un poco vagos en los que “propiedad” significa en este punto, pero algunos posibles ejemplos de {P(n)} pueden ser “{n} es par”; “{n} es igual a {3}”, “{n} resuelve la ecuación {(n + 1)^2 = n^2 + n + 1}”; y así sucesivamente. Por supuesto, no hemos definido muchos de estos conceptos aún, pero cuando lo hagamos, el Axioma ¿? aplicará a estas propiedades. (Una observación lógica: Debido a que este axioma se refiere no sólo a variables, sino también a sus propiedades, es de una naturaleza diferente de los otros cuatro axiomas; en efecto, el Axioma 5 técnicamente debería ser llamado un esquema de axioma, más que axioma —es una plantilla para producir un número (infinito) de axiomas, en lugar de ser un solo axioma en sí mismo. La discusión de esta distinción va mucho más allá del alcance de este texto, aunque, y cae en el terreno de la lógica.)

La intuición informal detrás este axioma es el siguiente. Supongamos que {P(n)} es tal que {P(0)} es cierto, y tal que siempre que {P(n)} es cierto, entonces {P(n\!+\!\!+)} es cierto. Entonces, ya que {P(0)} es verdadero, {P(0\!+\!\!+) = P(1)} es verdadero. Ya que {P(1)} es verdadero, {P(1\!+\!\!+) = P(2)} es verdadero. Repitiendo esto indefinidamente, vemos que {P(0)}, {P(1)}, {P(2)}, {P(3)}, etc. son todos verdaderos —sin embargo, esta línea de razonamiento nunca nos permitirá concluir que {P(0.5)}, por ejemplo, es cierto. Así el Axioma 5 no debería ser aplicable a sistemas numéricos que contengan elementos “innecesarios” como {0.5}. (En efecto, uno pude dar una “demostración” de este hecho. Aplicando el Axioma 5 a la propiedad {P(n) = n} “no es un entero más mitad”, i.e., un entero más {0.5}. Entonces {P(0)} es verdadero, y si {P(n)} es cierto, entonces {P(n\!+\!\!+)} es cierto. Así, el Axioma 5 asegura que {P(n)} es cierto para todos los números naturales {n}, i.e., ningún número natural puede ser un entero más mitad. En particular, {0.5} no puede ser un número natural. Esta “demostración” no es del todo genuina, debido a que aún no hemos definido las nociones de “entero”, “entero más mitad” y “{0.5}”, pero debería dar alguna idea de cómo el principio de inducción debería prohibir cualesquiera otros números que no sean los números naturales “verdaderos” que aparecen en {\mathbb N}.)

El principio de inducción nos da una manera de probar que una propiedad {P(n)} es verdadera para todo número natural {n}. Así, en el

Proposición 6. Una cierta propiedad {P(n)} es cierta para cada número natural {n}.

Demostración. Usaremos inducción. Primero verificaremos el caso base {n = 0}, i.e., demostraremos {P(0)}. (Insertar la demostración de {P(0)} aquí). Ahora suponemos inductivamente que {n} es un número natural y que {P(n)} ya ha sido demostrada. Tenemos que demostrar {P(n\!+\!\!+)}. (Insertar demostración de {P(n\!+\!\!+)}, asumiendo que {P(n)} es cierto, aquí). Esto cierra la inducción y así {P(n)} es cierto para todos los números {n}. \Box

Por supuesto, no es necesario seguir la plantilla exacta, redacción u orden en el tipo de prueba anterior, pero las pruebas usando inducción generalmente serán algo parecidas a la forma anterior. Hay algunas otra variantes de la inducción que encontraremos luego, como la inducción hacia atrás (Ejercicio 6), la inducción fuerte (Proposición 22) y la inducción transfinita (Lema ¿?).

Los Axiomas 15 son conocidos como los axiomas de Peano para los números naturales. Todos son muy plausibles y por lo que vamos a hacer la

(Informal) Existe un sistema numérico {\mathbb N}, cuyos elementos llamaremos números naturales, para los cuales los Axiomas 15 son verdaderos.

Haremos esta suposición un tanto más precisa una vez tengamos establecido nuestra notación para conjuntos funciones en el siguiente capítulo.

Observación 3. Nos referiremos a este sistema numérico {\mathbb N} como el sistema de los números naturales. Por supuesto, podríamos considerar la posibilidad que existan más de un sistema de números naturales, e.g., podríamos tener el sistema numérico Hindú-Arábico {\{0, 1, 2, 3, \dotso \}} y el sistema número Romano {\{ O, I, II, III, IV, V, VI, \dotso \}}, y si de verdad querríamos molestarnos, podríamos ver estos sistemas numéricos como diferentes. Pero estos sistemas numéricos son claramente equivalentes (el término técnico es isomorfismo), debido a que uno puede crear una correspondencia uno a uno {0 \leftrightarrow O}, {1 \leftrightarrow I}, {2 \leftrightarrow II}, etc. que asigna el cero del sistema Hindú-Arábico con el cero del sistema Romano, y que es preservado por la operación de incremento (e.g., si {2} corresponde a {II}, entonces {2\!+\!\!+} corresponderá a {II\!+\!\!+}). Para una afirmación más precisa de este tipo de equivalencia, ver el Ejercicio ¿?. Ya que todas las versiones del sistema de los números naturales son equivalentes, no hay razón para tener distintos sistemas de números naturales; y nos limitaremos a utilizar un único sistema de números naturales para hacer matemáticas.

No probaremos la Suposición 1 (aunque eventualmente la incluiremos en nuestros axioma para la teoría de conjuntos, ver Axioma ¿?), y será la único suposición que tendremos que hacer sobre nuestros números. Un logro notable del análisis moderno es que a partir de estos cinco axiomas muy primitivos, y algunos axiomas de la teoría de conjuntos, podemos construir todos los otros sistemas numéricos, crear funciones y hacer todo el álgebra y cálculo que estamos acostumbrados.

Observación 4. (Informal) Una característica de interés de los números naturales es que mientras cada número natural individual es finito, el conjunto de los números naturales es infinito, i.e., {\mathbb N} es infinito pero consiste de elementos finitos individuales. (El todo es mayor que cualquiera de sus partes.) No hay números naturales infinitos; incluso uno puede probar esto usando el Axioma 5, siempre y cuando se sienta cómodo con las nociones de finito e infinito. (Claramente {0} es finito. Además, si {n} es finito, entonces claramente {n\!+\!\!+} es también finito. Por lo tanto, por el Axioma 5, todos los números naturales son finitos.) Así, los números naturales pueden acercarse al infinito, pero en realidad nunca lo alcanzan; infinito no es uno de los número naturales. (Hay otros sistemas numéricos que admiten números “infinitos”, como los cardinales, ordinales y {p}-ádicos, pero no obedecen el principio de inducción, en todo caso, están más allá del alcance de este texto.)

Observación 5. Notar que nuestra definición de los números naturales es axiomático en lugar de constructivo. No hemos dicho que son los números naturales (por lo que no abordamos preguntas tales como de qué están hecho los números, si son objetos físicos, qué es lo que miden, etc.) —sólo hemos listado algunas cosas que podemos hacer con ellos (de hecho, la única operación que hemos definido en ellos, hasta el momento, es únicamente el incremento) y algunas de las propiedades que tienen. Así es como las matemáticas trabajan —trata con objetos abstractamente, que atiende sólo acerca de las propiedades que estos objetos tienen, no qué son estos objetos o qué significan. Si uno quiere hacer matemáticas, no importa si un número natural significa un cierto arreglo de cuentas en un ábaco, o una cierta organización de bits en la memoria de una computadora, o algún concepto más abstracto sin sustancia física; siempre y cuando se les pueda incrementar, si dos de ellos son iguales, y luego hacer otras operaciones aritméticas tales como la adición y multiplicación, calificarlos como números para propósitos matemáticos (siempre y cuando obedezcan los axiomas requeridos, por supuesto). Es posible construir los números naturales desde otros objetos matemáticos —de conjuntos, por ejemplo— pero hay múltiples maneras de construir un modelo funcional de los números naturales, y es inútil, al menos desde el punto de vista matemático, como discutir sobre qué modelo es el único “verdadero” —con tal que obedezca todos los axiomas y hacer las cosas bien, eso es suficientemente bueno para hacer matemáticas.

Observación 6. Históricamente, la comprensión de que los números naturales podrían ser tratados axiomáticamente es muy reciente, no más de cien años. Antes de eso, los número generalmente fueron entendidos por estar conectados inextricablemente a algún concepto externo, tales como contar las cardinalidad de un conjunto, la medición de la longitud de un segmento de línea, o la masa de un objeto físico, etc. Esto funcionó razonablemente bien, hasta que uno se vio obligado a pasar de un sistema numérico a otro; por ejemplo, la compresión de los números en términos de contar granos, por ejemplo, es ideal para la conceptualización de lo s números {3} y {5}, pero no funciona bien para {-3} o {1/3} o {\sqrt{2}} o {3 + 4i}; así, cada gran avance en la teoría de los números —números negativos, números irracionales, números complejos, incluso el número cero— dio lugar a una gran cantidad de angustia filosófica innecesaria. El gran descubrimiento de fines del siglo diecinueve fue que los números pueden ser comprendidos de manera abstracta vía axiomas, sin necesitar necesariamente un modelo concreto; pro supuesto, un matemático puede usar cualquiera de estos modelos cuando es conveniente, para asistir su intuición y comprensión, pero los puede descartar fácilmente cuando empieza a ponerse en camino.

Una consecuencia de estos axiomas juntos es que podemos definir secuencias recursivamente. Supongamos que queremos construir una secuencia {a_0, a_1, a_2, \dotso} de números, definiendo primero {a_0} con un valor base, e.g., {a_0 := c} para algún número {c}, y luego a {a_1} como alguna función de {a_0}, {a_1 := f_0(a_0)}, {a_2} como alguna función de {a_1}, {a_2 := f_1(a_1)}, y así sucesivamente. En general, fijamos {a_{n\!+\!\!+} := f_n(a_n)} para alguna función {f_n} de {\mathbb N} a {\mathbb N}. Mediante el uso de todos los axiomas ahora vamos a concluir que este procedimiento dará un valor único al elemento {a_n} de la secuencia para cada número natural {n}. Precisando más (estrictamente, esta proposición requiere tener definida la noción de función, que se verá en el . Sin embargo, no será circular, dado que el concepto de función no requiere de los axiomas de Peano. La Proposición 7 puede ser formalizada rigurosamente en el lenguaje de la teoría de conjuntos; ver Ejercicio ¿?.):

Proposición 7 (Definiciones recursivas). Suponiendo que para cada número natural {n} tengamos alguna función {f_n \colon \mathbb N \rightarrow \mathbb N} de los números naturales a los número naturales. Sea {c} un número natural. Entonces podemos asignar un único número natural {a_n} a cada número natural {n}, tal que {a_0 = c} y {a_{n\!+\!\!+} = f_n(a_n)} para cada número natural {n}.

Demostración. (Informal) Usaremos inducción. Observemos que este procedimiento da un único valor a {a_0}, a saber {c}. (Ninguna de las otras definiciones {a_{n\!+\!\!+} := f_n(a_n)} puede redefinir el valor de {a_0}, debido al Axioma 3.) Luego, supongamos inductivamente que el procedimiento provee un único valor a {a_n}. Entonces esto asigna un único valor a {a_{n\!+\!\!+}}, a saber {a_{n\!+\!\!+} := f_n(a_n)}. (Ninguna de las otras definiciones {a_{m\!+\!\!+} := f_m(a_m)} puede redefinir el valor de {a_{m\!+\!\!+}}, debido al Axioma 4.) Esto completa la inducción, así {a_n} está definido para cada número natural {n}, con un único valor asignado a cada {a_n}. \Box

Notar cómo todos loa axiomas han sido usados aquí. En un sistema que tiene alguna especia de vuelta-atrás, las definiciones recursivas no funcionarían debido a que algunos elementos de la secuencia constantemente se redefinen. Por ejemplo, en el Ejemplo 1, en el cual {3\!+\!\!+ = 0}, entonces habría (al menos) dos definiciones conflictivas para {a_0} ({c} o {f_3(a_3)}). En un sistema que tiene elementos superfluos tales como {0.5}, el elemento {a_{0.5}} nunca sería definido.

— 2. Adición —

Definición 8 (Adición de números naturales). Sea {m} un número natural. Para sumar cero a {m}, definimos {0 + m := m}. Luego, suponemos inductivamente que tenemos definido cómo sumar {n} a {m}. Entonces podemos sumar {n\!+\!\!+} a {m} mediante la definición {(n\!+\!\!+) + m := (n + m)\!+\!\!+}.

Lema 9. Para cualquier número natural {n}, {n + 0 = n}.

Demostración. Usando inducción. El caso base {0 + 0 = 0} se sigue de {0 + m = m} para todo número natural {m}, y {0} es un número natural. Supongamos inductivamente que {n + 0 = n}. Queremos mostrar que {(n\!+\!\!+) + 0 = n\!+\!\!+}. Pero por definición de la adición, {(n\!+\!\!+) + 0} es igual a {(n + 0)\!+\!\!+}, que es igual a {n\!+\!\!+} ya que {n + 0 = n}. Esto cierra la inducción. \Box

Lema 10. Para cualesquiera números naturales {n} y {m}, {n + (m\!+\!\!+) = (n + m )\!+\!\!+}.

Demostración. Por inducción sobre {n} (manteniendo {m} fijo). Empezamos considerando el caso base {n = 0}. En este caso tenemos que probar {0 + (m\!+\!\!+) = (0 + m)\!+\!\!+}. Por definición de la adición, {0 + (m\!+\!\!+) = m\!+\!\!+} y {0 + m = m}, así que ambos lados son iguales a {m\!+\!\!+} y por lo tanto iguales entre sí. Ahora asumimos inductivamente que {n + (m\!+\!\!+) = (n + m)\!+\!\!+}; ahora tenemos que demostrar que {(n\!+\!\!+) + (m\!+\!\!+) = ((n\!+\!\!+) + m)\!+\!\!+}. El lado izquierdo es {(n + (m\!+\!\!+))\!+\!\!+} por la definición de adición, que es igual a {((n + m)\!+\!\!+)\!+\!\!+} por la hipótesis inductiva. Similarmente, tenemos {(n\!+\!\!+) + m = (n + m)\!+\!\!+} por la definición de adición, y por lo que el lado derecho es igual a {((n + m)\!+\!\!+)\!+\!\!+}. Así, ambas partes son iguales entre sí, y tenemos cerrada la inducción. \Box

Corolario 11. Del Lema 9 y Lema 10, vemos que {n\!+\!\!+ = n + 1}.

Proposición 12 (La adición es conmutativa). Para cualesquiera números naturales {n} y {m}, {n + m = m + n}.

Demostración. Vamos a usar inducción en {n} (con {m} fijo). Primero verificamos el caso base {n = 0}, i.e., mostramos que {0 + m = m + 0}. Por la definición de adición, {0 + m = m}, mientras por el Lema 9, {m + 0 = m}. Así, el caso base está hecho. Ahora suponemos inductivamente que {n + m = m + n}, y tenemos que demostrar que {(n\!+\!\!+) + m = m + (n\!+\!\!+)} para cerrar la inducción. Por la definición de adición, {(n\!+\!\!+) + m = (n + m)\!+\!\!+}. Por el Lema 10, {m + (n\!+\!\!+) = (m + n)\!+\!\!+}, pero esto es igual a {(n + m)\!+\!\!+} por la hipótesis de inducción {n + m = m + n}. En consecuencia {(n\!+\!\!+) + m = m + (n\!+\!\!+)} y hemos concluido la inducción. \Box

Proposición 13 (La adición es asociativa). Para cualesquiera números naturales {a}, {b}, {c}, tenemos {(a + b) + c = a + (b + c)}.

Demostración. Ver Ejercicio 1. \Box

Proposición 14 (Ley de cancelación). Sean {a, b, c} números naturales tales que {a + b = a + c}. Entonces tenemos {b = c}.

Demostración. Por inducción en {a}. Veamos el caso base {a = 0}. Tenemos {0 + b = 0 + c}, que por definición de adición implica que {b = c} como se deseaba. Luego, suponemos inductivamente que tenemos la ley de cancelación para {a} (de modo que {a + b = a + c} implica {b = c}); ahora tenemos que probar la ley de cancelación para {a\!+\!\!+}. En otras palabras, asumimos que {(a\!+\!\!+) + b = (a\!+\!\!+) + c} y necesitamos mostrar que {b = c}. Por la definición de adición, {(a\!+\!\!+) + b = (a + b)\!+\!\!+} y {(a\!+\!\!+) + c = (a + c)\!+\!\!+} y por eso tenemos {(a + b)\!+\!\!+ = (a + c)\!+\!\!+}. Por el Axioma 4, tenemos {a + b = a + c}. Ya que tenemos la ley de cancelación para {a}, en consecuencia {b = c}. Esto cierra la inducción. \Box

Veamos como la adición interactúa con los positivos.

Definición 15 (Números naturales positivos). Un número natural {n} es positivo syss no es igual a {0}.

Proposición 16. Si {a} es un positivo y {b} un número natural, entonces {a + b} es positivo (y por lo tanto {b + a} también, por la Proposición 12).

Demostración. Usaremos inducción en {b}. Si {b = 0}, entonces {a + b = a + 0 = a}, que es positivo; esto prueba el caso base. Ahora suponemos inductivamente que {a + b} es positivo. Entonces {a + (b\!+\!\!+) = (a + b)\!+\!\!+}, que no puede ser cero por el Axioma 3, y es por lo tanto positivo. Esto cierra la inducción. \Box

Corolario 17. Si {a} y {b} son número naturales tales que {a + b = 0}, entonces {a = 0} y {b = 0}.

Demostración. Supongamos por contradicción que {a \ne 0} o {b \ne 0}. Si {a \ne 0} entonces {a} es positivo, y por lo tanto {a + b = 0} es positivo por la Proposición 16, una contradicción. Similarmente si {b \ne 0} entonces {b} es positivo, y otra vez {a + b = 0} es positivo por la Proposición 16, una contradicción. En consecuencia, {a} y {b} deben ser ambos cero. \Box

Lema 18. Sea {a} un número positivo. Entonces existe exactamente un único número natural {b} tal que {b\!+\!\!+ = a}.

Demostración. Ver Ejercicio 2. \Box

Con la noción de adición, podemos empezar a definir la noción de orden.

Definición 19 (Ordenamiento de los números naturales). Sean {n} y {m} números naturales. Diremos que {n} es mayor que o igual a {m}, y escribimos {n \ge m} o {m \le n}, syss tenemos {n = m + a} para algún número natural {a}. Decimos que {a} es estrictamente mayor que {m}, y escribimos {n > m} o {m < n}, syss {n \ge m} y {n \ne m}.

Observación 7. Además, notemos que {n\!+\!\!+ > n} para cualquier {n}; por eso no existe el mayor número natural {n}, porque el siguiente número {n\!+\!\!+} es más grande todavía.

Proposición 20 (Propiedades básicas del orden para los números naturales). Sean {a, b, c} números naturales. Entonces

  1. (El orden es reflexivo) {a \ge a}.
  2. (El orden es transitivo) Si {a \ge b} y {b \ge c}, entonces {a \ge c}.
  3. (El orden es anti-simétrico) Si {a \ge b} y {b \ge a}, entonces {a = b}.
  4. (La adición preserva el orden) {a \ge b} si y sólo si {a + c \ge b + c}.
  5. {a < b} si y sólo si {a\!+\!\!+ \le b}.
  6. {a < b} si y sólo si {b = a + d} para algún número positivo {d}.

Demostración. Ver Ejercicio 3. \Box

Proposición 21 (Tricotomía del orden para los números naturales). Sean {a} y {b} números naturales. Entonces exactamente una de las siguientes afirmaciones es cierta: {a < b}, {a = b}, o {a > b}.

Demostración. Esto es sólo un esquema, el resto queda para el Ejercicio 4. Primero mostraremos que no podemos tener más que una las afirmaciones {a < b}, {a = b}, {a > b} al mismo tiempo. Si {a < b} entones {a \ne b} por definición, y si {a > b} entonces {a \ne b} por definición. Si {a > b} y {a < b} entonces por la Proposición 20 tenemos {a = b}, una contradicción. Así, no mas que una afirmación es verdadera.

Ahora veremos que al menos una de las afirmaciones es verdadera. Con {b} fijo e inducción en {a}. Cuando {a = 0} tenemos {0 \le b} para todo {b} (?) , por lo tanto tenemos {0 = b} o {0 < b}, que prueba el caso base. Ahora suponemos que tenemos demostrada la proposición para {a}, y ahora probamos la proposición para {a\!+\!\!+}. De la tricotomía para {a}, hay tres casos: {a < b}, {a = b}, y {a > b}. Si {a > b}, entonces {a\!+\!\!+ > b} (?). Si {a = b}, entonces {a\!+\!\!+ > b} (?). Ahora suponemos que {a < b}. Entonces por la Proposición 20, tenemos {a\!+\!\!+ \le b}. En consecuencia, {a\!+\!\!+ = b} o {a\!+\!\!+ < b}, y en ambos casos hemos comprobado. Esto cierra la inducción. \Box

Las propiedades de orden nos permiten obtener una versión más fuerte del principio de inducción.

Proposición 22 (Principio de inducción fuerte). Sea {m_0} un número natural, y sea {P(m)} una propiedad perteneciente a un número natural arbitrario {m}. Suponemos que por cada {m \ge m_o}, tenemos la siguiente implicación: si {P(m')} es cierto para todos los números naturales {m_0 \le m' < m}, entonces {P(m)} es también cierto. (En particular, esto significa que {P(m_0)} es cierto, ya que en este caso la hipótesis es vacua.) Entonces podemos concluir que {P(m)} es cierto para todos los números naturales {m \ge m_0}.

Observación 8. Usualmente aplicaremos este principio con {m_0 = 0} o {m_0 = 1}.

Demostración. Ver Ejercicio 5. \Box

 

Ejercicio 1. Demostrar la Proposición 13. (Consejo: fijar dos variables y aplicar la inducción en la tercera.)

Ejercicio 2. Demostrar el Lema 18. (Consejo: usar inducción.)

Ejercicio 3. Demostrar la Proposición 20. (Consejo: se necesitara muchas de las proposiciones, corolarios y lemas precedentes.)

Ejercicio 4. Justificar las tres afirmaciones marcadas con (?) en la demostración de la Proposición 21.

Ejercicio 5. Demostrar la Proposición 22. (Consejo: definir {Q(n)} como la propiedad que {P(m)} es cierto para todo {m_0 \le m < n}; observar que {Q(n)} es vacuamente cierta cuando {n < m_0}.)

Ejercicio 6. Sea {n} un número natural y sea {P(m)} una propiedad perteneciente a los números naturales tal que cuando {P(m\!+\!\!+)} es cierta, entonces {P(m)} es cierta. Supongamos que {P(n)} es también cierto. Demostrar que {P(m)} es cierto para todos los números naturales {m \le n}; esto es conocido como el principio de inducción hacia atrás. (Consejo: aplicar inducción a la variable {n}.)

— 3. Multiplicación —

Definición 23 (Multiplicación de números naturales). Sea {m} un número natural. Para multiplicar cero a {m}, definimos {0 \times m := 0}. Suponemos inductivamente que tenemos definido como multiplicar {n} a {m}. Entonces podemos multiplicar {n\!+\!\!+} a {m} definiendo {(n\!+\!\!+) \times m := (n \times m)\!+\!\!+}.

Lema 24 (La multiplicación es conmutativa). Sean {n, m} números naturales. Entonces {n \times m = m \times n}.

Demostración. Ver Ejercicio 7. \Box

Abreviaremos {n \times m} con {nm}.

Lema 25 (Los números naturales no tienen divisores cero). Sean {n, m} números naturales. Entonces {n \times m = 0} si y sólo si al menos uno de los {n, m} es igual a cero. En particular, si {n} y {m} son ambos positivos, entonces {nm} también lo es.

Demostración. Ver Ejercicio 8. \Box

Proposición 26 (Ley distributiva). Para cualquier número natural {a, b, c}, tenemos {a(b + c) = ab + ac} y {(b + c)a = ba + ca}.

Demostración. Dado que la multiplicación es conmutativa, sólo necesitamos mostrar la primera identidad {a(b + c) = ab + ac}. Con {a} y {b} fijos, usamos inducción en {c}. Vamos a probar el caso base {c = 0}, i.e., {a(b + 0) = ab + a0}, El lado izquierdo es {ab}, mientras que el derecho es {ab + 0 = ab}, así hemos probado el caso base. Ahora, suponiendo inductivamente que {a(b + c) = ab + ac}, vamos a probar que {a(b + (c\!+\!\!+)) = ab + a(c\!+\!\!+)}. El lado izquierdo es {a((b + c)\!+\!\!+) = a(b + c) + a}, mientras que el lado derecho es {ab + ac + a = a(b + c) + a}, por la hipótesis inductiva, por lo tanto podemos cerrar la inducción. \Box

Proposición 27 (La multiplicación es asociativa). Para cualesquiera números naturales {a, b, c}, tenemos {(a \times b) \times c = a \times (b \times c)}.

Demostración. Ver Ejercicio 9. \Box

Proposición 28 (La multiplicación preserva el orden). Si {a, b} son números naturales, tales que {a < b}, y {c} es positivo, entonces {ac < bc}.

Demostración. Ya que {a < b}, tenemos {b = a + d} para algún positivo {d}. Multiplicando por {c} y usando la ley distributiva obtenemos {bc = ac + dc}. Como {d} es positivo, y {c} es positivo, {dc} es positivo, y por lo tanto {ac < bc} como se esperaba. \Box

Corolario 29 (Ley de cancelación). Sean {a, b, c} números naturales tales que {ac = bc} y {c} es distinto de cero. Entonces {a = b}.

Demostración. Por la tricotomía de orden (Proposición 21), tenemos tres casos: {a < b}, {a = b}, {a > b}. Suponemos primero que {a < b}, entonces por la Proposición 28 tenemos {ac < bc}, una contradicción. Obtenemos una contradicción similar cuando {a > b}. Así, la única posibilidad es que {a = b}, como se deseaba. \Box

Demostración. Ver Ejercicio 10. \Box

Proposición 30 (Algoritmo euclídeo). Sea {n} un número natural, y sea {q} un número positivo. Entonces existen los números naturales {m, r} tales que {0 \le r < q} y {n = mq + r}.

Demostración. Ver Ejercicio 11. \Box

Al igual que usamos la operación de incremento para definir recursivamente la adición, y la adición para definir recursivamente la multiplicación, podemos usar la multiplicación para definir recursivamente la exponenciación:

Definición 31 (Exponenciación para los números naturales). Sea {m} un número natural. Para elevar {m} a la potencia {0}, definimos {m^0 := 1}. Suponemos recursivamente que {m^n} ha sido definido para algún número natural {n}, entonces podemos definir {m^{n++} := m^n \times m}.

 

Ejercicio 7. Demostrar el Lema 24. (Consejo: modificar las demostraciones de los Lemas 9, 10 y la Proposición 12.)

Ejercicio 8. Demostrar el Lema 25. (Consejo: demostrar la segunda afirmación primero.)

Ejercicio 9. Demostrar la Proposición 27. (Consejo: modificar la demostración de la Proposición 13 y usar la ley distributiva.)

Ejercicio 10. Demostrar la identidad {(a + b)^2 = a^2 + 2ab + b^2} para todos los números naturales {a, b}.

Ejercicio 11. Demostrar la Proposición 30. (Consejo: fijar {q} y usar inducción en {n}.)

\displaystyle \zeta (s) = \sum_{n=1}^\infty n^{-s}  = \prod_{p \in \mathbb{P}} \frac {1} {1 - p^{-s}}