Introducción
En esta entrada hablaremos acerca del principio de inducción, este principio nos permitirá demostrar propiedades que cumple los números naturales. Será de gran importancia pues emplearemos este teorema como método de demostración en el conjunto de los naturales.
Principio de inducción
Teorema: Sea $P(x)$ una propiedad. Supongamos que:
- $P(0)$,
- Para cualquier $n\in \mathbb{N}$, si $P(n)$ se satisface, entonces $P(s(n))$ se cumple.
Entonces, $\set{n\in \mathbb{N}:P(n)}=\mathbb{N}$.
Demostración:
Sea $P(x)$ una propiedad. Supongamos que se satisfacen 1) y 2), entonces
$A=\set{n\in \mathbb{N}: P(n)}$
es un conjunto inductivo.
En la entrada anterior probamos que cualquier conjunto inductivo contiene a los naturales. Así, $\mathbb{N}\subseteq A$.
Además, $A\subseteq \mathbb{N}$ pues para cualquier $n\in A$, $n\in \mathbb{N}$ y por lo tanto, $A=\mathbb{N}$.
$\square$
Para entender este teorema podemos imaginar que apilamos una cantidad infinita de fichas de dominó de tal manera que al caer una vayan cayendo todas como se muestra en la imagen.
De este modo, podemos interpretar al teorema como sigue: $P(x): x\ \text{cae}$ donde $x$ es una ficha de dominó. Luego, estamos suponiendo que se cae la primer ficha de dominó y que si se cae la ficha $n$, entonces se cae la siguiente ficha.
Por lo que si asociamos a las fichas con los números naturales, podemos decir que cada ficha cumplirá la propiedad, o bien, que cada número natural lo hará.
Orden de los naturales
Ahora que hemos visto que la colección de los naturales es un conjunto podemos darle un orden a este conjunto.
Definición: Sean $n,m\in \mathbb{N}$. Decimos que $n\leq m$ si y sólo si $n\in m$ o $n=m$.
Ejemplos:
- $0=\emptyset$ y $1=\set{\emptyset}$ son números naturales. Luego, $0\leq 1$ pues $\emptyset\in \set{\emptyset}$.
- $0=\emptyset$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $0\leq 2$ pues $\emptyset\in \set{\emptyset, \set{\emptyset}}$.
- $1=\set{\emptyset}$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $1\leq 2$ pues $\set{\emptyset}\in \set{\emptyset, \set{\emptyset}}$.
$\square$
A continuación demostraremos el siguiente lema que nos dice que la intersección de dos números naturales resulta ser un número natural.
Lema: Si $n,m\in \mathbb{N}$, entonces $n\cap m\in \mathbb{N}$.
Demostración:
Sean $n,m\in \mathbb{N}$. Tenemos los siguientes casos:
Caso 1: Si $n\cap m=\emptyset$, entonces $n\cap m\in \mathbb{N}$.
Caso 2: $n\cap m\not=\emptyset$.
$n\cap m$ es un conjunto transitivo: Sea $z\in n\cap m$, entonces $z\in n$ y $z\in m$, dado que $n,m\in \mathbb{N}$, entonces $n$ y $m$ son conjuntos transitivos, por lo que $z\subseteq n$ y $z\subseteq m$ y así, $z\subseteq n\cap m$, lo que demuestra que $n\cap m$ es un conjunto transitivo.
$n\cap m$ es un orden total con la pertenencia:
–Asimetría de $\in$ en $n\cap m$:
Sean $z,w\in n\cap m$, tales que $z\in_{n\cap m} w$. Veamos que $w\notin_{n\cap m} z$. Dado que $z,w\in n\cap m$, entonces $z,w\in n$ y $z,w\in m$. Así, al ser $n$ un número natural, sabemos que $(n, \in_n)$ es un orden total, por lo que $\in_n$ es una relación asimetrica y por lo tanto, no puede ocurrir que $w\in_n z$. Además, como $(m, \in_m)$ es un orden total, $\in_m$ es una relación asimétrica en $m$ y por lo tanto, no puede ocurrir que $w\in_m z$. Por lo tanto, $w\notin_{n\cap m} z$.
–Transitividad de $\in$ en $n\cap m$:
Sean $z,w,y\in n\cap m$, tales que $z\in_{n\cap m} w$ y $w\in_{n\cap m} y$. Veamos que $z\in_{n\cap m} y$. Dado que $z,w,y\in n\cap m$, entonces $z,w,y\in n$ y $z,w,y\in m$. Así, al ser $n$ un número natural, sabemos que $(n, \in_n)$ es un orden total, por lo que $\in_n$ es una relación transitiva y por lo tanto, $z\in_n y$. Además, como $(m, \in_m)$ es un orden total, $\in_m$ es una relación transitiva en $m$ y por lo tanto, $w\in_m y$. Por lo tanto, $w\in_{n\cap m} y$.
$\in_{n\cap m}$-comparables:
Sean $z,w\in n\cap m$, entonces $z,w\in n$ y $z,w\in m$. Luego, como $n$ es un número natural, sabemos que $(n, \in_n)$ es un orden total, por lo que los elementos de $n$ son $\in_n$-comparables y por lo tanto, $z\in_n w$ o $w\in_n z$ o $w=z$. Además, como $(m, \in_m)$ es un orden total, los elementos de $m$ son $\in_m$-comparables y por lo tanto, $z\in_m w$ o $w\in_m z$ o $w=z$. Por lo tanto, los elementos de $n\cap m$ son $\in_{n\cap m}$-comparables.
Finalmente, veamos que para cualquier subconjunto $b$ no vacío de $n\cap m$, $b$ tiene elemento mínimo y máximo.
Dado que $b\subseteq n\cap m$, entonces $b\subseteq n$ y $b\subseteq m$. Dado que $n$ y $m$ son números naturales y $b$ es un subconjunto no vacío de $n$ y $m$, se tiene que $b$ tiene mínimo con respecto a $\in_n$ y $b$ tiene mínimo con respecto a $\in_m$, respectivamente.
Sea $a=\min(b)$ con respecto a $\in_n$ y $x=\min(b)$ con respecto a $\in_m$. Luego, como $b\subseteq n$ y $b\subseteq m$, se tiene que $a,x\in n$ y $a,x\in m$. Por lo tanto, $a,x\in n\cap m$.
Luego, sea $\alpha=\min(\set{a, x})$. Supongamos sin pérdida de la generalidad que $\alpha=a$.
Afirmación: $\alpha=\min(b)$ con respecto a la pertenencia en $n\cap m$.
Demostración de la afirmación:
Sea $k\in b\setminus \set{\alpha}$, entonces $k\in b$ y $k\notin \set{\alpha}$. Luego, $k\in n$, pues $b\subseteq n$ y por tanto, $\alpha\in k$ pues $\alpha=a=\min(b)$ con respecto a $\in_n$.
Por lo tanto, $\alpha=\min(b)$ con respecto a $\in_{n\cap m}$.
$\square$
Por lo tanto, si $n,m\in \mathbb{N}$, entonces $n\cap m\in \mathbb{N}$.
$\square$
En la tarea moral verás que te corresponde probar que cualquier subconjunto no vacío de $n\cap m$ tiene elemento máximo.
Tarea moral
La siguiente lista te ayudará a reforzar el contenido de esta entrada:
- Sea $X$ un subconjunto no vacío de $\mathbb{N}$, demuestra que $\bigcap X\in \mathbb{N}\cap X$. (Nota que esta es una generalización del lema que probamos en la parte de arriba).
Más adelante…
En la siguiente entrada probaremos que el conjunto de los naturales con el orden que hemos definido en esta entrada es un buen orden, para esta demostración nos será de gran utilidad el lema que probamos en esta sección.
Enlaces
Entrada relacionada: Álgebra Superior II: Principio de inducción y teoremas de recursión
Entrada anterior: Teoría de los Conjuntos I: Conjuntos inductivos y axioma del infinito
Siguiente entrada: Teoría de los Conjuntos I: Buen orden en los naturales