Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Por Gabriela Hernández Aguilar

Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia dada un conjunto finito.

Propiedades de los conjuntos finitos

Teorema: Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A\subseteq B$, entonces $A$ es finito. Más aún, $|A|\leq |B|$.

Demostración: (Por inducción sobre $|B|$).

Base de inducción: Supongamos que $|B|=0$. Entonces $B=\emptyset$, por lo que $A=\emptyset$ y así, $A$ es finito y $0=|A|\leq |B|=0$.

Hipótesis de inducción: Supongamos que para $|B|=n$ se cumple que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Paso inductivo: Sea $B$ un conjunto finito, tal que $|B|=n+1$, veamos que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Sea $A\subseteq B$ arbritario.

Si $A=B$, entonces $A$ es finito y $|A|\leq |B|$.

Si $A\not=B$, entonces existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus\set{x}$ y como $|B\setminus \set{x}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\leq |B\setminus \set{x}|=n$. Luego entonces, $A$ es finito y $|A|\leq |B|$.

$\square$

Cardinalidad del conjunto potencia

Teorema: Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.

Nota: $2^{n}=\underbrace{2\cdot 2\cdots 2}_{n-veces}$

Demostración: (Por inducción sobre $|X|$)

Base de inducción: Si $|X|=0$, entonces $X=\emptyset$ y así, $\mathcal{P}(X)=\set{\emptyset}$, por lo que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}=2^0=1$.

Hipótesis de inducción: Supongamos que si $X$ es finito tal que $|X|=n$, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|= 2^{|X|}$.

Paso inductivo: Sea $X$ un conjunto finito tal que $|X|=n+1$. Supongamos que $X=\set{X_1,X_2, \dots, X_n, X_{n+1}}$. Luego, consideremos $X’=X\setminus \set{X_1}$, entonces $|X’|=n$ y así, $|\mathcal{P}(X’)|=2^{|X’|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$, para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Procederemos por doble contención.

$\subseteq$) Sea $Y\in \mathcal{P}(X)$, entonces $Y\subseteq X$. Si $X_1\in Y$, entonces $Y\in \set{Z\in \mathcal{P}(X): X_1\in Z}$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \set{X_1}=X’$, por lo que $Y\in \mathcal{P}(X’)$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

$\supseteq$) Sea $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Caso 1: Si $Y\in \mathcal{P}(X’)$, entonces $Y\subseteq X’$ y como $X’\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.

Caso 2: Si $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$, entonces $Y\in \mathcal{P}(X)$.

Por lo tanto, $\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}\subseteq \mathcal{P}(X)$.

Así, $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X’)$ es finito y $|\mathcal{P}(X’)|=2^n$.

Además, $\set{Z\in \mathcal{P}(X)}$ es finito, más aún, $|\set{Z\in \mathcal{P}(X):X_1\in Z}|=|\mathcal{P}(X’)|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X’)$ y $\set{Z\in \mathcal{P}(X):X_1\in Z}$.

Consideremos $f:\mathcal{P}(X’)\to \set{Z\in \mathcal{P}(X):X_1\in Z}$ dada por $f(Y)=Y\cup \set{X_1}$. Veamos que $f$ es biyectiva.

Inyectividad: Sean $A,B\in \mathcal{P}(X’)$ tales que $f(A)=f(B)$, esto es $A\cup \set{X_1}=B\cup \set{X_1}$. Luego, $A$ y $\set{X_1}$ son ajenos pues $A\subseteq X’=X\setminus \set{X_1}$; asimismo, $B$ y $\set{X_1}$ son ajenos pues $B\subseteq X’=X\setminus \set{X_1}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.

Sobreyectividad: Sea $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$. Entonces $Y\subseteq X$ y $X_1\in Y$.

Veamos que existe $W\subseteq X\setminus \set{X_1}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \set{X_1}$, tenemos que $f(W)=(Y\setminus \set{X_1})\cup \set{X_1}=Y$. Por lo tanto, $f$ es sobreyectiva.

Así, $f$ es biyectiva y $|\set{Z\in \mathcal{P}(X): X_1\in Z}|=2^n$.

Por lo tanto, $|\mathcal{P}(X)|=|\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Lo que concluye nuestra prueba.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:

  • Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
  • Si $A$ y $B$ son conjuntos finitos y ajenos, muestra que $A\cup B$ es finito y $|A\cup B|=|A|+|B|$.
  • Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
  • Demuestra que si $A$ y $B$ son cualesquiera conjuntos finitos, entonces $|A\cup B|+|A\cap B|=|A|+|B|$.

Más adelante

En la siguiente sección abordaremos a los conjuntos infinitos, esto nos acercara a preguntarnos sobre la cardinalidad de dichos conjuntos.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos

Siguiente entrada: Conjuntos infinitos

Teoría de los Conjuntos I: Conjuntos finitos

Por Gabriela Hernández Aguilar

Introducción

Ahora que sabemos el concepto de equipotencia, en esta sección veremos a los conjuntos finitos, los cuales podremos contar según el número natural al que sean equipotentes. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Concepto

Definición: Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n\in \mathbb{N}$ tal que $X\sim n$.

Ejemplo:

El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$; a saber, la función vacía.

$\square$

Ejemplo:

El conjunto $A=\set{2,4,6,8, 10}$ es finito pues $f:A\to 5=\set{0,1,2,3,4}$ definida por medio de $f=\set{(2,0), (4,1), (6,2), (8,3), (10, 4)}$ es una función biyectiva.

$\square$

Es conveniente añadir la siguiente notación para conjuntos finitos, pues hará más fluida la escritura.

Definición: Sea $X$ un conjunto finito y $n\in\mathbb{N}$ tal que $X\sim n$. Definimos el cardinal de $X$ como el número natural al cual $X$ es equipotente, y lo denotaremos por medio del símbolo $|X|$; esto es, $|X|:=n$.

Lema: Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.

Demostración:

Sea $X$ finito tal que $|X|=n$, entonces existe $f:n\to X$ tal que $f$ es biyectiva.

Definimos $f’:s(n)\to X\cup \set{y}$ como

$f'(x)= \left\{ \begin{array}{lcc}
             f(x) &   si  & x \in n \\
             \\ y&  si & x=n \\
             \end{array}
   \right.$

Tenemos que $f$ es biyectiva.

En efecto, primero veamos que $f$ es inyectiva. Sean $x_1, x_2\in s(n)$ tales que $f'(x_1)=f'(x_2)$.

Caso 1: Si $x_1\in n$ y $x_2\in n$, entonces $f(x_1)=f'(x_1)=f'(x_2)=f(x_2)$. Como $f$ es inyectiva, entonces $x_1=x_2$.

Caso 2: Si $x_1= n$ y $x_2= n$, entonces $x_1=x_2$.

No ocurre que $x_1\in n$ y $x_2=n$ pues $f'(x_1)=f(x_1)\in X$ y $f'(x_2)=y\notin X$. De manera análoga, no ocurre que $x_1=n$ y $x_2\in n$.

Por lo tanto, $f’$ es inyectiva.

Veamos ahora que $f’$ es sobreyectiva.

Sea $w\in X\cup \set{y}$. Veamos que existe $x\in s(n)$ tal que $f'(x)=w$.

Caso 1: Si $w\in X$, entonces existe $x\in n$ tal que $f(x)=w$, pues $f:n\to X$ es una función sobreyectiva, así que existe $x\in s(n)$ tal que $f'(x)=f(x)=w$.

Caso 2: Si $w=y$, entonces tomamos al elemento $n\in s(n)$ y se tiene que $f'(n)=w$.

De los casos 1 y 2, concluimos que $f’$ es sobreyectiva.

Por lo tanto, $f’$ es biyectiva y así $X\cup\set{y}$ es finito; más aún, $X\cup\set{y}\sim s(n)$, es decir, $|X\cup \set{y}|=s(n)=n+1=|X|+1$.

$\square$

Teorema: Sean $X$ y $Y$ conjuntos finitos, entonces $X\cup Y$ es finito. Más aún, $|X\cup Y|\leq |X|+|Y|$.

Demostración: (Por inducción sobre $|Y|$.

Base de inducción: Si $|Y|=0$, entonces $Y=\emptyset$, así $X\cup Y=X\cup \emptyset=X$ y por lo tanto, $|X\cup Y|=|X|=|X|+0=|X|+|\emptyset|$.

Hipótesis de inducción: Ahora supongamos que si $X$ y $Y$ son finitos tales que $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$.

Paso inductivo: Veamos que si $|Y|=n+1$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$. Si para todo $y\in Y$, $y\in X$, entonces $Y\subseteq X$, por lo que $X\cup Y=X$ y, por tanto, $X\cup Y$ es finito; además, como $n\leq n+t$ para cualesquiera naturales $n$ y $t$, entonces $|X\cup Y|=|X|\leq |X|+|Y|$.

Supongamos ahora que existe $y\in Y\setminus X$. Luego, sea $Y’=Y\setminus \set{y}$. Tenemos que $|Y’|=n$ por lo que, por hipótesis de inducción, se tiene que $X\cup Y’$ es finito y $|X\cup Y’|\leq |X|+|Y’|$.

Luego, dado que $y\notin Y’$ y $y\notin X$, entonces, $y\notin X\cup Y’$, y así por el lema anterior, tenemos que $(X\cup Y’)\cup\set{y}$ es finito y

\begin{align*}
|(X\cup Y’)\cup \set{y}|&=|X\cup Y’|+1\\
&\leq |X|+|Y’|+1\\
&=|X|+n+1=|X|+|Y|.
\end{align*}

Por lo tanto, $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$, siempre que $X$ y $Y$ son conjuntos finitos.

$\square$

Teorema: Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$, $X$ es finito. Entonces $\bigcup\mathcal{F}$ es finito.

Demostración: (Por inducción sobre la cardinalidad de $\mathcal{F}$).

Base de inducción: Si $|\mathcal{F}|=0$, entonces $\mathcal{F}=\emptyset$. Así, se cumple por vacuidad, que si cualquier $X\in \mathcal{F}$ es finito, entonces $\bigcup \mathcal{F}$ es finito. Más aún, $\bigcup \mathcal{F}=\emptyset$ y $|\bigcup \mathcal{F}|=0$.

Hipótesis de inducción: Supongamos que si $|\mathcal{F}|=n$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, se cumple que $\bigcup\mathcal{F}$ es finito.

Paso inductivo: Veamos que si $|\mathcal{F}|=n+1$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Sea $X\in\mathcal{F}$ y definamos $\mathcal{F’}:=\mathcal{F}\setminus X$. Tenemos que cualquier elemento de $\mathcal{F’}$ es finito y que $|\mathcal{F}’|=n$, por lo que por hipótesis de inducción se cumple que $\bigcup\mathcal{F’}$ es finito.

Ahora, por el lema, tenemos que $\bigcup\mathcal{F}’\cup X$ es finito.

Afirmación: $\bigcup\mathcal{F}=\bigcup\mathcal{F}’\cup X$.

Demostración de la afirmación:

Sea $x\in\bigcup \mathcal{F}$, entonces existe $Y\in \mathcal{F}$ tal que $x\in Y$.

Caso 1: Si $Y=X$, entonces $x\in X$ y por lo tanto, $x\in \bigcup\mathcal{F}’\cup X$.

Caso 2: Si $Y\not=X$, entonces $Y\in \mathcal{F}’$ y así, $x\in \bigcup\mathcal{F}’$, lo cual implica que $\bigcup\mathcal{F}\subseteq \bigcup\mathcal{F}’\cup X$.

Ahora, como $\mathcal{F’}\subseteq\mathcal{F}$ y $X\in\mathcal{F}$, entonces $\bigcup\mathcal{F’}\cup X\subseteq\mathcal{F}$.

Así, $\bigcup \mathcal{F}=\bigcup\mathcal{F}’\cup X$. Por lo tanto, $\bigcup\mathcal{F}$ es finito. Lo que concluye nuestra prueba.

$\square$

,

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección.

  • Sea $X$ un conjunto finito y $x\in X$. Si $|X|=n+1$, demuestra que $X\setminus\set{x}$ es finito y que $|X\setminus\set{x}|=n$.
  • Prueba que si $X$ y $Y$ son conjuntos finitos, entonces $X\cap Y$ también es finito.
  • Si $A$ y $B$ son conjuntos finitos, prueba que $A\setminus B$ también es finito.

Más adelante

En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Equipotencia

Siguiente entrada: Conjuntos finitos (parte II)

Teoría de los Conjuntos I: Equipotencia

Por Gabriela Hernández Aguilar

Introducción

En esta nueva unidad comenzaremos a hablar acerca de conjuntos infinitos, para ello necesitamos hablar acerca de la cantidad de elementos que poseen estos conjuntos. En esta sección comenzaremos a entablar una relación entre los elementos de un conjunto y otro, veremos que si podemos establecer una función biyectiva entre dos conjuntos diremos que tales conjuntos son equipotentes.

Equipotencia

Definición: Sean $A$ y $B$ conjuntos. Decimos que $A$ y $B$ son equipotentes si existe una función $f:A\to B$ tal que $f$ es biyectiva. Denotaremos $A$ equipotente a $B$ como $A\sim B$.

Ejemplo:

Sea $A=\mathbb{N}$ y $B=\set{x: x=2k\ \text{para algún}\ k\in\mathbb{N}}$.

Afirmación: $A$ y $B$ son equipotentes.

Demostración de la afirmación:

Sea $f:\mathbb{N}\to B$ dada por $f(n)=2n$ para todo $n\in \mathbb{N}$. Primero veamos que $f$ es función.

Sean $(a,b), (a,c)\in f$, entonces $(a,b)=(x, 2x)$ y $(a,c)=(y, 2y)$ para algunos $x,y\in\mathbb{N}$. Como $(a,b)=(x,2x)$, entonces $a=x$ y $b=2x$; asimismo, como $(a,c)=(y,2y)$, entonces $a=y$ y $c=2y$. Así, $x=y$, pues $a=x$ y $a=y$. Luego, $b=2x=2y=c$. Por lo tanto, $f$ es función.

Ahora veamos que $f$ es biyectiva.

  1. Inyectividad:
    Sean $x,y\in \mathbb{N}$ tales que $f(x)= f(y)$, esto es $2x=2y$. Luego, por ley de la cancelación para el producto tenemos que $x=y$ y, por tanto, $f$ es inyectiva.
  2. Sobreyectividad:
    Si $y\in B$, entonces $y=2k$ para algún $k\in \mathbb{N}$. Así, existe $k\in \mathbb{N}$ tal que $f(k)=2k=y$ y, por consiguiente, $f$ es sobreyectiva.

Por lo tanto, $f$ es biyectiva, de modo que $A\sim B$.

$\square$

Teorema: Sean $A,B$ y $C$ conjuntos. Entonces se satisfacen los siguientes enunciados

  1. $A$ es equipotente a $A$.
  2. Si $A$ es equipotente a $B$, entonces $B$ es equipotente a $A$.
  3. Si $A$ es equipotente a $B$ y $B$ es equipotente a $C$, entonces $A$ es equipotente a $C$.

Demostración:

  1. La función $Id_A$ es una función biyectiva, por lo que podemos concluir que $A\sim A$.
  2. Supongamos que $A\sim B$, entonces existe $f:A\to B$ tal que $f$ es una función biyectiva. Luego, $f^{-1}:B\to A$ es una función biyectiva y por lo tanto, $B\sim A$.
  3. Supongamos que $A\sim B$ y $B\sim C$, esto es, existe $f:A\to B$ biyectiva y $g:B\to C$ biyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son biyectivas, entonces $g\circ f$ es biyectiva.
    Así, $A\sim C$.

$\square$

Dominación

Hemos visto que para que un conjunto sea equipotente a otro se requiere que exista una función biyectiva, por lo que podemos preguntarnos si hay una forma en que los conjuntos se comparen si solo existe una función inyectiva pero no sobreyectiva. Así va a ser y viene descrito en la siguiente definición:

Definición: Sean $A$ y $B$ conjuntos. Decimos que $B$ domina a $A$ si existe $f: A\to B$ tal que $f$ es inyectiva. Lo denotaremos como $A\lesssim B$.

Ejemplo:

Sean $A=\set{1,2,3}$ y $B=\mathbb{N}$. Tenemos que $A\lesssim B$ pues existe $f=\set{(1,1), (2,2), (3,3)}$ tal que $f$ es función inyectiva. Sin embargo, no existe $h:A\to B$ tal que $h$ sea sobreyectiva.

$\square$

Teorema: Sean $A,B$ y $C$ conjuntos. Entonces se satisfacen los siguientes enunciados

  1. $A\lesssim A$.
  2. Si $A\lesssim B$ y $B\lesssim C$, entonces $B\lesssim C$.

Demostración:

  1. La función $Id_A$ es una función biyectiva, en paticular es una función inyectiva por lo que podemos concluir que $A\lesssim A$.
  2. Supongamos que $A\lesssim B$ y $B\lesssim C$, esto es, existe $f:A\to B$ inyectiva y $g:B\to C$ inyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son inyectivas, entonces $g\circ f$ es inyectiva.
    Así, $A\sim C$.

$\square$

Lo siguiente que podemos probar es que si $A$ y $B$ son conjuntos tales que $A\lesssim B$ y $B\lesssim A$, entonces $A\sim B$. Este resultado corresponde al teorema de Cantor-Schröder-Bernstein que demostraremos en la próxima entrada.  

Tarea moral

  • Demuestra que si $n$ y $m$ son números naturales, entonces, o bien $n$ domina a $m$ o bien $m$ domina a $n$.
  • Demuestra que si $A$ es un conjunto, entonces su conjunta potencia lo domina; esto es, muestra que existe una función inyectiva de $A$ en $P(A)$.
  • Si $A$, $B$, $C$ y $D$ son conjuntos tales que $A\sim B$ y $C\sim D$, ¿será cierto que $A\cup C\sim B\cup D$? Argumenta tu respuesta.
  • Demuestra que si $A\subseteq B$, entonces $B$ domina a $A$.

Más adelante

En la siguiente entrada abordaremos el tema de conjuntos finitos. Probaremos el teorema de Cantor-Schröder-Bernstein.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Producto en los naturales

Siguiente entrada: Conjuntos finitos

Teoría de los Conjuntos I: Producto en los naturales

Por Gabriela Hernández Aguilar

Ahora que hemos definido a la suma en el conjunto de los naturales, podemos definir el producto, pues este se refiere a sumar cierta cantidad de veces un número. De modo que el producto se definirá con ayuda de la suma.

Producto

Utilizando el teorema de recursión se puede mostrar, al igual que con la operación suma, que existe una única función $\cdot: \mathbb{N}\times\mathbb{N}\to \mathbb{N}$, denotada por $\cdot(m,n)=m\cdot n$, que satisface las siguientes condiciones:

  1. $0\cdot n=0$ para cualquier $n\in \mathbb{N}$,
  2. $s(m)\cdot n= (m\cdot n)+m$.

Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad tal como lo hace el producto cartesiano y la suma en los naturales. Además veremos que esta operación se distribuye con la suma. (Ver suma en los naturales).

Distributividad del producto sobre la suma

Teorema: Para cualesquiera $m,n,k\in \mathbb{N}$, $m\cdot(n+k)=m\cdot n+ m\cdot k$.

Demostración: Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción: Si $m=0$, $0\cdot(n+k)=0=0+0=(0\cdot n)+(0\cdot k)$.

Hipótesis de inducción: Supongamos que se cumple para $m$, es decir, $m\cdot(n+k)= (m\cdot n)+(m\cdot k)$.

Paso inductivo: Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n+k)=(m+1)\cdot n+(m+1)\cdot k$.

\begin{align*}
(m+1)\cdot (n+ k)&=m\cdot (n+ k)+(n+ k) \tag{Definición $\cdot$}\\
&= (m\cdot n+m\cdot k)+(n+ k) \tag{Hipótesis de inducción}\\
&= ((m\cdot n)+n)+((m\cdot k)+k)\tag{Conmutatividad y asociatividad de $+$}\\
&= (m+1)\cdot n+(m+1)\cdot k \tag{Definición $\cdot$}
\end{align*}

Por lo tanto, $m\cdot(n+k)=m\cdot n+m\cdot k$ para cualesquiera $m, n, k\in \mathbb{N}$.

$\square$

Conmutatividad del producto

Para demostrar que el producto es conmutativo primero vamos a demostrar los siguientes lemas:

Lema 1: Para cualquier $n\in \mathbb{N}$, $n\cdot 0=0$.

Demostración:

Procederemos por inducción sobre $n$.

Base de inducción: Si $n=0$, tenemos que $0\cdot 0=0$.

Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 0=0$.

Paso de inductivo: Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 0=0$.

\begin{align*}
(k+1)\cdot 0 &=(k\cdot 0)+0\tag{Definición $\cdot$}\\
&= 0+0\tag{Hipótesis de inducción}\\
&= 0\tag{Propiedad $+$}
\end{align*}

Por lo tanto, $n\cdot 0=0$, para cualquier $n\in \mathbb{N}$.

$\square$

Lema 2: Para cualquier $n\in \mathbb{N}$, $n\cdot 1=n$.

Demostración:

Procederemos por inducción sobre $n$.

Base de inducción: Si $n=0$, tenemos que $0\cdot 1= 0$ por la definición de $\cdot$.

Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 1=k$.

Paso de inductivo: Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 1=k+1$.

\begin{align*}
(k+1)\cdot 1&=(k\cdot 1)+1\tag{Definición $\cdot$}\\
&= k+1 \tag{Hipótesis de Inducción}
\end{align*}

Por lo tanto, para cualquier $n\in \mathbb{N}$, $n\cdot 1=n$.

$\square$

Teorema: Para cualesquiera $m,n\in \mathbb{N}$, $n\cdot m=m\cdot n$.

Demostración:

Por inducción sobre $n$.

Base de inducción: Si $n=0$, entonces $0\cdot n=0=n\cdot 0$. (Lo probamos por inducción en el lema 1).

Hipótesis de inducción: Supongamos que para $k$ se cumple que $n\cdot k=k\cdot n$.

Paso inductivo: Veamos que para $k+1$ se satisface que $n\cdot (k+1)= (k+1)\cdot n$.

\begin{align*}
(k+1)\cdot n&= (k\cdot n)+n\tag{Definición $+$}\\
&= (n\cdot k)+n\tag{Hipótesis de Inducción}\\
&= (n\cdot k)+(n\cdot 1) \tag{Lema 2}\\
&= n\cdot (k+1) \tag{Distributividad}
\end{align*}

Por lo tanto, $\cdot$ es conmutativo.

$\square$

Asociatividad del producto

Teorema: Para cualesquier $m,n,k\in \mathbb{N}$, $m\cdot(n\cdot k)=(m\cdot n)\cdot k$.

Demostración: Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción: Si $m=0$, $0\cdot(n\cdot k)=0=(0\cdot n)\cdot k$.

Hipótesis de inducción: Supongamos que se cumple para $m$, es decir, $m\cdot(n\cdot k)= (m\cdot n)\cdot k$

Paso inductivo: Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n\cdot k)=((m+1)\cdot n)\cdot k$.

\begin{align*}
(m+1)\cdot (n\cdot k)&=(m\cdot (n\cdot k))+(n\cdot k) \tag{Definición $\cdot$}\\
&= ((m\cdot n)\cdot k)+(n\cdot k) \tag{Hipótesis de inducción}\\
&=(k\cdot(m\cdot n))+(k\cdot n) \tag{Conmutatividad del producto}\\
&=k\cdot(m\cdot n+n) \tag{Distributividad}\\
&= (m\cdot n+n)\cdot k\tag{Conmutatividad del producto}\\
&= ((m+1)\cdot n)\cdot k\tag{Definición $\cdot$}
\end{align*}

Por lo tanto, $\cdot$ es asociativa.

$\square$

Antes de continuar con el siguiente resultado sobre producto de naturales, es importante hacer la siguiente observación, sencilla pero útil.

Observación: Si $n\in\mathbb{N}$ es un natural distinto de cero, entonces $n+m$ es un natural distinto de $0$ para todo $m\in\mathbb{N}$.

Ley de cancelación

En álgebra, cuando tenemos una ecuación como la siguiente:

$x\cdot z=y\cdot z$,

siempre que $z\not=0$, decimos que $x=y$, esto tiene una justificación y la llamaremos ley de cancelación para el producto. El teorema dice lo siguiente:

Teorema: Sean $n, m, k\in \mathbb{N}$ tal que $k\not=0$. Si $n\cdot k=m\cdot k$, entonces $n=m$.

Para probar dicho teorema utilizaremos la siguiente serie de resultados:

Proposición: Si $n,m\in\mathbb{N}$ son tales que $n\leq m$, entonces, existe $t\in\mathbb{N}$ tal que $n+t=m$.

Demostración (Proposición):

Mostraremos por inducción sobre $m$, que para todo $n\leq m$, existe $t_n\in \mathbb{N}$ tal que $n+t_n=m$.

Base de inducción: $k=0$. Si $n\leq 0$, entonces $n=0$, pues recordemos que dos números naturales $n$ y $m$ satisfacen $n\leq m$ si, y sólo si, $n\in m$ o $n=m$. Así, si $n\leq 0$, entonces $n\in 0$ o $n=0$, pero dado que el enunciado $n\in 0$ no puede ser cierto pues $0=\emptyset$ no tiene elementos, se sigue que $n=0$ tiene que ser verdadero. De este modo, si $n\leq 0$, entonces $n=0$ y tomando $t=0$ se tiene que $n+t=0+0=0$. Por lo tanto, para todo $n\leq 0$ existe $t_n\in\mathbb{N}$ tal que $n+t_n=0$. Por lo tanto, la proposición es cierta para $k=0$.

Hipótesis de inducción: Supongamos que para algún $k\in\mathbb{N}$ se satisface que para todo $n\leq k$, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$.

Paso inductivo: Veamos que se cumple para $s(k)$. Sea $n\leq s(k)$. Luego, $n\in s(k)$ o $n=s(k)$. Si $n=s(k)$, entonces tomamos $t=0$ y se tiene que $n+t=s(k)+0=s(k)$. Supongamos ahora que $n\in s(k)$.

Como $n\in s(k)$, entonces $n=k$ o $n\in k$, es decir, $n\leq k$. Luego, por hipótesis de inducción, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$. De este modo, si tomamos $s(t_n)\in\mathbb{N}$ se tiene que $n+s(t_n)=s(t_n)+n=s(t_n+n)=s(k)$.

En cualquier caso para $n$ hemos concluido que existe $t_n\in\mathbb{N}$ tal que $n+t_n=s(k)$.

Por lo tanto, la proposición es verdadera.

$\square$

Proposición. Si $n\in\mathbb{N}$, entonces $n\leq n+t$ para todo $t\in\mathbb{N}$.

Demostración (Proposición).

Sea $n\in\mathbb{N}$. Probaremos por inducción sobre $t$ que $n\leq n+t$ para todo $t\in\mathbb{N}$.

Base: $t=0$. Para $t=0$ tenemos que $n+t=n+0=n$, por lo que es verdad que $n\leq n+t$.

Hipótesis de inducción: supongamos que para algún $t\in\mathbb{N}$, $n\leq n+t$.

Bajo esta hipótesis veamos que $n\leq n+s(t)$. Primero, notemos que $n+s(t)=s(t)+n$ por la conmutatividad de la suma. Luego, por definición de la suma, $s(t)+n=s(t+n)$. Dado que $s(t+n)=(t+n)\cup\set{t+n}$, entonces $n+t\in s(t+n)$. Ahora bien, por hipótesis de inducción, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n\in s(n+t)$, ya que $n+t\in s(n+t)$, por lo que $n\leq s(n+t)=n+s(t)$.

Ahora, si $n\in n+t$, entonces, $n\in s(n+t)$ por transitividad de la pertenencia en los naturales, por lo que también se cumple que $n\leq n+s(t)$.

En cualquier caso concluimos que $n\leq n+s(t)$, lo que concluye la prueba de la proposición.

$\square$

El último resultado que veremos, antes de iniciar con la demostración de la ley de la cancelación del producto, dice lo siguiente:

Corolario: Si $n\in\mathbb{N}$ es distinto de $0$, entonces $n+t$ es distinto de $0$ para todo $t\in\mathbb{N}$.

Demostración (Corolario):

Sea $n\in\mathbb{N}$ distinto de $0$ y supongamos que $t\in\mathbb{N}$ es arbitrario. Por la proposición anterior, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n+t$ es distinto de $0$ por la hipótesis sobre $n$. Si ahora $n\in n+t$, entonces $n+t$ es distinto de $0$, pues $n+t$ tiene un elemento, el cual es $n$, mientras que el $0$ no tiene elementos. Esto concluye la prueba.

$\square$

Ya que contamos con esta serie de resultados previos podemos dar la demostración de la ley de cancelación del producto.

Demostración: (ley de cancelación del producto)

Probaremos por inducción sobre $k$ (asumiendo $k\geq1$), que si $n$ y $m$ son dos naturales tales que $n\cdot k=m\cdot k$, entonces $n=m$.

Base: $k=1$. Si $n$ y $m$ son dos naturales tales que $n\cdot 1=m\cdot 1$, entonces $n=m$, ya que $n\cdot 1=n$ para cualquier $n\in\mathbb{N}$ por un resultado visto con anterioridad.

Hipótesis de inducción: supongamos que para algún $k\in\mathbb{N}$, con $k\geq1$, si $n$ y $m$ son naturales tales que $n\cdot k=m\cdot k$, entonces $n=m$.

Veamos ahora que si $n$ y $m$ son naturales tales que $n\cdot s(k)= m\cdot s(k)$, entonces $n=m$. Supongamos pues que $n$ y $m$ son naturales tales que $n\cdot s(k)=m\cdot s(k)$. Sin pérdida de generalidad supongamos que $n\leq m$. Luego, por una proposición anterior, existe $t\in\mathbb{N}$ tal que $n+t=m$.

Tomemos al natural $t$ tal que $n+t=m$ y retomemos la igualdad $n\cdot s(k)=m\cdot s(k)$. Luego, $n\cdot s(k)+t=(n\cdot k+n)+t$ por definición de producto y, por asociatividad y conmutatividad de la suma, tenemos que $(n\cdot k+n)+t=n\cdot k+(n+t)=n\cdot k+m$. Así pues, como $n\cdot s(k)+t=m\cdot s(k)+t$, entonces $m+n\cdot k=m\cdot s(k)+t=(m\cdot k+m)+t=m+(m\cdot k+t)$ y, utilizando la ley de cancelación de la suma, tenemos que $n\cdot k=m\cdot k+t$. Luego, ya sabemos que $n\cdot k=m\cdot k+t$, por lo que $n\cdot k+t\cdot k=(m\cdot k+t)+t\cdot k$, de donde $(n+t)\cdot k=m\cdot k+(t\cdot k+t)$ por distributividad del producto con respecto a la suma. En consecuencia, $m\cdot k+0=m\cdot k=m\cdot k+t\cdot k+t$ y, utilizando nuevamente la ley de la cancelación de la suma, tenemos que $0=t\cdot k+t$.

Dado que $0=t\cdot k+t$, entonces, necesariamente debe ocurrir que $t\cdot k=0$, pues de lo contrario aplicamos el Corolario anterior y tenemos que $t\cdot k+t\not=0$ lo cual es una contradicción. Por tanto, $t\cdot k=0$.

Dado que $t\cdot k=k\cdot t$ y $0\cdot t=0$, entonces $0\cdot k=t\cdot k$ y, aplicando la hipótesis de inducción, tenemos que $0=t$, por lo que $m=n+t=n+0=n$ como queríamos probar.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:

  • Demuestra que para cualesquiera $m,n,l\in \mathbb{N}$ tal que $l\not=0$, si $m<n$, entonces $l\cdot m<l\cdot n$.
  • Demuestra que para cualesquiera $m,n\in \mathbb{N}$, si $m\cdot n=0$, entonces $m=0$ o $n=0$.
  • Usa el teorema de recursión para probar la existencia y unicidad de una función que satisfaga lo siguiente:
    $0!=1$,
    $1!=1$,
    $2!=2\cdot 1$,
    $\vdots$
    $n!=n\cdot (n-1)\cdots 2\cdot 1$

Más adelante

Con esta entrada concluimos el contenido acerca de números naturales, pero todos estos nuevos conocimientos nos permitirán construir nuevos conjuntos como el de los enteros y los racionales. Además, hablaremos acerca de cardinalidad y nos será de gran ayuda conocer al conjunto de los números naturales.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Suma en los naturales

Siguiente entrada: Equipotencia

Teoría de los Conjuntos I: Suma en los naturales

Por Gabriela Hernández Aguilar

Introducción

Como lo dijimos en la entrada anterior buscamos la manera de definir a la suma en el conjunto de los naturales y esto nos lo permitirá el teorema de recursión. En esta nueva entrada presentaremos la definición formal de la suma y demostraremos algunas de las propiedades que satisface.

Suma

Definición: Dado $n\in \mathbb{N}$ fijo pero arbitrario y $g:\mathbb{N}\to \mathbb{N}$ dada por $g(m)=s(m)$ para cualquier $m\in \mathbb{N}$, existe una única función (esto lo podemos asegurar por el teorema de recursión) tal que $f_n(0)=n$ y $f_n(s(k))=g(f_n(k))=s(f_n(k))$ para cualquier $k\in \mathbb{N}$.

Está definición nos dice como sumar a un número natural con un $n$ fijo, por lo que requerimos definir una operación binaria que nos diga como sumar a dos números naturales cualesquiera.

Definición: Sea $g:\mathbb{N}\to \mathbb{N}$ dada por $g(m)=s(m)$ para cualquier $m\in \mathbb{N}$. Definimos a la suma de los naturales como la función $+: \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ tal que $+(m,n)=m+n=f_n(m)$ para cualesquiera $n,m\in \mathbb{N}$.

La función $+$ satisface las siguientes condiciones:

  1. $0+n=n$ para cualquier $n\in \mathbb{N}$,
  2. $s(m)+n=s(m+n)$ para cualesquiera $m,n\in \mathbb{N}$.

Esto último se sigue de que $+(m,n)=f_n(m)$ y $f_n$ satisface tales condiciones.

Teorema: La función $+$ es única.

Demostración:

Sea $+$ la función que definimos arriba y supongamos que existe $h:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ que satisface $h(0,n)=n$ y $h(s(m), n)= s(h(m,n))$. Veamos que $+=h$.

Definamos para cada $n\in\mathbb{N}$ la función $h_n:\mathbb{N}\to\mathbb{N}$ por medio de $h_n(0)=h(0,n)$ y $h_n(m)=h(m,n)$. Notemos que para todo $n\in\mathbb{N}$, $h_n(0)=n$ y $h_n(s(m))=h(s(m),n)=s(h(m,n))=s(h_{n}(m))$, y por el teorema de recursión se sigue que $h_n=f_n$.

Así, para $n,m\in\mathbb{N}$ arbitrarios, $+(m,n)=f_n(m)=h_n(m)=h(m,n)$ y en consecuencia, $+=h$.

$\square$

Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad tal como lo hace el producto cartesiano. Notaremos que para demostrar estas propiedades ocuparemos en todo momento el principio de inducción.

Asociatividad de la suma

Teorema: Para cualesquier $m,n,k\in \mathbb{N}$, $m+(n+k)=(m+n)+k$.

Demostración: Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción: Si $m=0$, $0+(n+k)=n+k=(0+n)+k$.

Hipótesis de inducción: Supongamos que se cumple para $m$, es decir, $m+(n+k)= (m+n)+k$

Paso inductivo: Veamos que se cumple para $s(m)$, es decir, $s(m)+(n+k)=(s(m)+n)+k$.

\begin{align*}
s(m)+(n+k)&=s(m+(n+k)) \tag{Definición $+$}\\
&= s((m+n)+k) \tag{Hipótesis de inducción}\\
&= s(m+n)+k\tag{Definición $+$}\\
&= (s(m)+n)+k\tag{Definición $+$}
\end{align*}

Por lo tanto, $+$ es asociativa.

$\square$

Conmutatividad de la suma

Ahora vamos a ver que la suma conmuta, para ello demostraremos los siguientes lemas:

Lema 1: Para cualquier $m\in \mathbb{N}$, $0+m=m+0$.

Demostración:

Procederemos por inducción sobre $n$.

Base de inducción: Si $m=0$, tenemos que $0+0=0+0$.

Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $0+k=k+0$.

Paso de inductivo: Veamos que se cumple para $s(k)$, es decir, $0+s(k)=s(k)+0$.

\begin{align*}
s(k)+0 &=s(k+0)\tag{Definición $+$}\\
&= s(0+k)\tag{Hipótesis de inducción}\\
&= s(k)\tag{Definición $+$}\\
&= 0+s(k)\tag{Definición $+$}\\
\end{align*}

Por lo tanto, $0+m=m+0$, para cualquier $m\in \mathbb{N}$.

$\square$

Lema 2: Para cualesquiera $m,n\in \mathbb{N}$, $s(n)+m=n+s(m)$.

Demostración:

Procederemos por inducción sobre $m$.

Base de inducción: Si $n=0$, tenemos que $s(0)+m=s(0+m)= s(m)=0+s(m)$.

Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $s(k)+m=k+s(m)$.

Paso de inductivo: Veamos que se cumple para $s(k)$, es decir, $s(s(k))+m=s(k)+s(m)$.

\begin{align*}
s(s(k))+m &=s(s(k)+m) \tag{Definición $+$}\\
&= s(k+s(m)) \tag{Hipótesis de Inducción}\\
&= s(k)+s(m) \tag{Definición $+$}
\end{align*}

Por lo tanto, para cualesquiera $m,n\in \mathbb{N}$, $s(n)+m=n+s(m)$.

$\square$

Proposición: Para cualesquiera $m,n\in \mathbb{N}$, $n+m=m+n$.

Demostración:

Por inducción sobre $m$.

Base de inducción: Si $m=0$, entonces $n+0=0+n$. (Lo probamos por inducción en el primer lema 1).

Hipótesis de inducción: Supongamos que para $k$ se cumple que $n+k=k+n$.

Paso inductivo: Veamos que para $s(k)$ se satisface que $n+s(k)= s(k)+n$.

\begin{align*}
s(k)+n&= s(k+n)\tag{Definición $+$}\\
&= s(n+k)\tag{Hipótesis de Inducción}\\
&= s(n)+k\tag{Definición $+$}\\
&= n+s(k)\tag{Lema 2}
\end{align*}

Por lo tanto, $+$ es conmutativa.

$\square$

Ley de cancelación

En álgebra, cuando tenemos una ecuación como la siguiente:

$x+5=y+5$,

dado que $5=5$, entonces ponemos $x=y$, esto tiene una justificación y la llamaremos ley de cancelación de la suma. El teorema dice lo siguiente:

Teorema: Si $n+k=m+k$, entonces $n=m$.

Demostración:

Demostraremos que si $n\not=m$, entonces $n+k\not=m+k$. Procederemos por inducción sobre $k$.

Base de inducción: Supongamos que $n\not=m$. Luego, $n+0=0+n=n$ y $m+0=0+m=m$ y así, $n+0=n\not=m=m+0$.

Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$, se satisface que si $n\not=m$, entonces $n+k\not=m+k$.

Paso inductivo: Veamos que se cumple para $s(k)$, es decir, si $n\not=m$, entonces $n+s(k)\not=m+s(k)$.

Supongamos que $n\not=m$. Luego,

\begin{align*}
n+s(k)&= s(n)+k\tag{Lema 2}\\
&= s(n+k)\tag{Definición $+$}\\
&\not= s(m+k)\tag{Hipótesis de inducción}\\
&= s(m)+k\tag{Definición $+$}\\
&= m+s(k)\tag{Lema 2}
\end{align*}

Por lo tanto, se cumple la ley de cancelación para la suma.

$\square$

A continuación probaremos un resultado que podría parecer natural para todos, $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.

Teorema: Para cualquier $m\in \mathbb{N}$, $s(m)=m+1$.

Demostración:

Procederemos por inducción sobre $m$.

Base de inducción: Si $m=0$, entonces $s(0)=1=0+1$.

Hipótesis de inducción: Supongamos que para $k\in \mathbb{N}$ se cumple que $s(k)=k+1$.

Paso inductivo: Veamos que la propiedad se satisface para $s(k)$, es decir, $s(s(k))= s(k)+1$.

\begin{align*}
s(k)+1&= s(k+1)\tag{Definición $+$}\\
&= s(s(k))\tag{Hipótesis de inducción}
\end{align*}

Por lo tanto, $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.

$\square$

A partir de este momento usaremos el hecho de que $s(m)=m+1$.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido de esta sección:

  • Demuestra que si $n,m\in \mathbb{N}$ tales que $n\not=m$, entonces $s(n)\not= s(m)$.
  • Demuestra usando el principio de inducción que para cualesquiera $m, n \in \mathbb{N}$, $m + n \geq n$.
  • Prueba que para cualesquiera $m,n\in \mathbb{N}$ tales que $m+n=0$, entonces $m=0$ y $n=0$.

Más adelante

En la siguiente entrada definiremos al producto en el conjunto de los números naturales.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Teorema de recursión

Siguiente entrada: Producto en los naturales