(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota deduciremos el resultado conocido como Principio del producto que nos garantiza que la cardinalidad del producto cartesiano de dos conjuntos finitos (ver nota 6) es igual al producto de las cardinalidades de cada conjunto. Así mismo probaremos que cuando se tiene una función entre conjuntos finitos de la misma cardinalidad, son equivalentes ser inyectiva, suprayectiva o biyectiva.

Empecemos probando un lema que nos ayudará a probar el principio del producto.

Lema 1

Sea $A$ un conjunto finito, $b$ un objeto, entonces $A\times \set{b}$ es finito y $\# (A\times \set{b})=\#A$.

Demostración

Sea $A$ un conjunto finito, $b$ un objeto, $n=\#A$, y $f:\set{1,\dotsc,n}\to A$ una biyección.

Sea $g:A\to A\times \set{b}$ dada por $g(a)=(a,b)$ $\forall a\in A$.

Observemos que la función $h:A\times \set{b}\to A$ dada por $h((a,b))=a\,\,\forall (a,b)\in A\times \set{b}$ es la inversa de g, pues:

$h\circ g(a)=h(g(a))=h((a,b))=a\,\,\forall a\in A$.

$g\circ h((a,b))=g(h((a,b)))=g(a)=(a,b)\,\,\forall (a,b)\in A\times \set{b}$.

Así $g$ es invertible y por tanto biyectiva.

Como $f$ y $g$ son biyectivas, entonces $g\circ f:\set{1,\dotsc,n}\to A\times \set{b} $ es biyectiva.

Así $\# (A\times \set{b})=n$ y por lo tanto $\# (A\times \set{b})=\#A$.

$\square$

Teorema. Principio del producto

Sean $A,B$ conjuntos finitos, entonces $A\times B$ es finito y $\#(A\times B)=\#A\cdot \#B$.

Demostración

Sean $A,B$ conjuntos finitos, $n=\#A$, $m=\#B$.

Entonces $B=\set{b_1,\dotsc,b_m}$ con $b_i\neq b_j\,\,\forall i,j.$

Observemos que $A\times B= (A\times \set{b_1})\cup (A\times \set{b_2})\cup\dotsc\cup (A\times \set{b_m})$ donde $ (A\times \set{b_i})\cap (A\times \set{b_j})=\emptyset\,\,\forall i\neq j$.

Así por el principio generalizado de la suma visto en la nota anterior.

$\#(A\times B)= \#(A\times \set{b_1})+ \# (A\times \set{b_2})+\dotsc+\# (A\times \set{b_m}).$

Por el lema previo $\forall i$ $ \#(A\times \set{b_i})=\#A$, entonces tenemos que:

$\#(A\times B)=m\cdot \#A$, y como $m=\#B$. Sustituyendo:

$\#(A\times B)=\#A\cdot \#B.$

$\square$

Nota

Este resultado se puede generalizar, si $A_1,\dotsc,A_t$ son conjuntos finitos, entonces $A_1\times\cdots\times A_t$ es finito y $\#(A_1\times\cdots\times A_t)=\#A_1\cdots \#A_t $, y se conoce como el principio generalizado del producto.

Veamos ahora qué información podemos obtener acerca de la cardinalidad de dos conjuntos finitos, a partir de las características de alguna función definida entre ellos.

Lema 2

Sean $A,B$ conjuntos finitos

i) Si existe $f:A\to B$ inyectiva, entonces $\#A= \#Im f$ y $ \#A\leq \#B$.

ii) Si existe $f:A\to B$ suprayectiva, entonces $ \#A\geq \#B$.

Demostración de i)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f:A\to B$ inyectiva.

Consideremos la función $F:A\to Imf$ tal que $F(a)=f(a)\,\,\forall a\in A$.

Como $f$ es inyectiva $F$ también lo es, y por construcción $F$ es suprayectiva.

Así $F$ es biyectiva y entonces $\#A= \#Imf$.

Como $Imf\subseteq B$, entonces $ \#Imf\leq \#B$, de donde $ \#A = \#Imf\leq \#B$.

Demostración de ii)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f:A\to B$ suprayectiva.

Sea $B=\set{b_1,\dotsc,b_m}$ con $m=\#B$ y $b_i\neq b_j\,\,\,\forall i,j$.

Como $f$ es suprayectiva, para cada $b_i\in B$ existe un elemento de $A$ que bajo $f$ va a dar a $b_i$, elijamos uno de ellos, digamos $a_i\in A$ tal que $f(a_i)=b_i$.

Definamos la función $g:B\to A$ con $g(b_i)=a_i\,\,\,\forall i\in \set{1,\dotsc, m}.$ Veamos que $g$ es invectiva.

Si $i,j\in \set{1,\dotsc, m}$ son tales que $g(b_i)=g(b_j)$ entonces $a_i=g(b_i)=g(b_j)=a_j$, de manera que $a_i=a_j$ y en consecuencia:

$b_i=f(a_i)=f(a_j)=b_j,$

por lo cual $b_i=b_j$, así $g$ es inyectiva.

Por el inciso $i)$ tenemos entonces que el dominio de $g$ tiene cardinalidad menor o igual a su condominio, es decir $\#B\leq \#A$.

$\square$

Observaciones

• Sea $A$ un conjunto finito. Si $A\neq \emptyset$, entonces $\#A\geq 1 $. De modo equivalente si $\#A=0$ entonces $A=\emptyset$.
• Sean $A,B$ conjuntos finitos con $A\subseteq B$. Si $\#A=\#B$, entonces $A=B$.

Teorema

Sean $A,B$ conjuntos finitos com $\#A= \#B$, $f:A\to B$.

Las siguientes afirmaciones son equivalentes:

a) $f$ es inyectiva.

b) $f$ es suprayectiva.

c) $f$ es biyectiva.

Demostración

Sean $A,B$ conjuntos finitos con $\#A= \#B$, $f:A\to B$.

a) $\Longrightarrow$b)

Supongamos que $f$ es inyectiva.

Por demostrar que $f$ es suprayectiva.

Como $f$ es inyectiva, por el Lema 2 $\#A= \#Imf $, tenemos entonces que

$\#B= \#A= \#Imf$

Así $Imf\subseteq B$ con $ \#Imf= \#B$, y por lo tanto $Imf=B$ y así $f$ es suprayectiva.

b) $\Longrightarrow$a)

Supongamos que $f$ es suprayectiva, es decir que $Imf=B$.

Por demostrar que $f$ es inyectiva.

Sea $n=\#A= \#B$, $A=\set{a_1,\dotsc,a_n}$ con $a_i\neq a_j\,\,\,\forall i\neq j$.

Como $Imf=B$, entonces $\#Imf= \#B=n$.

Supongamos por reducción al absurdo que $f$ no es inyectiva, entonces existen dos elementos de $A$ que bajo $f$ son iguales, sin pérdida de generalidad supongamos que $f(a_{n-1})=f(a_n)$, entonces:

$Imf=\set{f(a_1),\dotsc,f(a_{n-1})}$

La función $h:\set{1,\dotsc,n-1}\to Imf$ con $h(i)=f(a_i)\,\,\,\forall i$ sería entonces suprayectiva, así aplicando el Lema 2 tenemos que:

$n-1=\#\set{1,\dotsc,n-1}\geq \#Imf=\#B=n$, y entonces tendriamos que $n-1\geq n$, pero eso es una contradicción y por lo tanto $f$ es inyectiva.

Hemos probado entonces que, bajo nuestras hipótesis, $f$ es inyectiva si y sólo si es suprayectiva, así que si se cumple a) se tiene también b) y entonces $f$ es biyectiva y se cumple c). Análogamente si se cumple b) se tiene también a) y entonces $f$ es biyectiva y se cumple c). Además, si se cumple c) se tiene que $f$ es biyectiva y por lo tanto es inyectiva y suprayectiva, así que se cumplen a) y b).

Por lo tanto las condiciones a), b) y c) son equivalentes.

$\square$

Tarea moral

1. Sean $A$ y $B$ conjuntos finitos. Demuestra o da un contraejemplo:

i) Si $\#A\leq \#B$ y $f$ es una función $f:A\to B$, entonces $f$ es inyectiva.

ii) Si $\#A\geq \#B$ y $f$ es una función $f:A\to B$, entonces $f$ es suprayectiva.

iii) Si $\#A=\#B$ y $f$ es una función $f:A\to B$, entonces $f$ es biyectiva.

2. Para acceder a una aplicación se requiere una contraseña de 3 dígitos que pueden ser 0,1,2,3,4,5,6,7,8,9.
i) Describe a cada contraseña como una terna ordenada y al conjunto de contraseñas como un producto cartesiano
ii) ¿Cuántas contraseñas hay?
iii) Si ahora la contraseña puede ser de 3 o de cuatro dígitos ¿Cuántas contraseñas habrá?

3. Ve el siguiente vídeo y elabora tus propias observaciones, coméntalas con tus colegas.

Mas adelante

En las siguientes notas haremos énfasis en el estudio de las técnicas de conteo, ordenaciones, ordenaciones con repetición, y combinaciones serán objeto de nuestro estudio.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 19. Conjuntos equivalentes y cardinalidad.

Enlace a la nota siguiente. Nota 21. Conteo, ordenaciones con repetición.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En ésta y la siguiente nota analizaremos el tamaño de los conjuntos, los vamos a comparar mediante funciones, veremos que son equivalentes si existe una función biyectiva entre ellos, hablaremos de la cardinalidad o número de elementos de un conjunto. Probaremos el principio de la suma que nos habla de la cantidad de elementos que se obtienen cuando unes dos conjuntos finitos y ajenos, con este resultado demostraremos un importante corolario que nos habla de la cantidad de elementos en la unión cuando los conjuntos no son ajenos.

Definición

Sean $A$ y $B$ conjuntos. Decimos que $A$ tiene la misma cardinalidad que $B$ o que $A$ es equipotente con $B$ si existe una función biyectiva de $A$ en $B$ y lo denotaremos por:

$A\sim B$

Ejemplos.

1. $A=\set{1,2,3,4}$, $B=\set{1,\frac{1}{2}, \frac{1}{3}, \frac{1}{4}}$ son equipotentes ya que $f:A\to B$ con $f(n)=\frac{1}{n}$ $\forall n\in A$ es una función biyectiva.

2. $\mathbb N=\set{0,1,2,3,\dotsc}$ y $\mathbb N^+=\set{1,2,3,\dotsc}$.

¿Son $\mathbb N$ y $\mathbb N^+$ conjuntos equipotentes?, ¿ $\mathbb N\sim \mathbb N^+$?

La función $f:\mathbb N \to \mathbb N^+$ dada por $f(n)=n+1$ $\forall n\in\mathbb N$ es inyectiva, pues si $n,m\in \mathbb N$ son tales que $f(n)=f(m),$ entonces $n+1=m+1$ y así $n=m$.

Además es suprayectiva pues si $n\in \mathbb N^+$, $n>0$, así $n-1\geq 0$ y entonces $n-1\in \mathbb N$ y $f(n-1)=(n-1)+1=n$.

Y así $\mathbb N\sim \mathbb N^+$.

3. Sea $P=\set{n\in \mathbb N\mid n\, \, es \, \, par}=\set{2m\mid m\in \mathbb N}$

¿Los naturales son equipotentes a $P$?

La función $f:\mathbb N \to P$ dada por $f(m)=2m$ $\forall m\in \mathbb N$ es una biyección así $\mathbb N\sim P.$

Tarea moral, demuéstralo.

4. ¿Qué dices de los números naturales y los enteros?, ¿$\mathbb N\sim \mathbb Z$?

Considera la siguiente función $f:\mathbb N \to \mathbb Z$:

$f(n)= \left\{ \begin{array}{lcc}
             \frac{n}{2} &   si  & n\,\,es\,\,par \\
             \\ \frac{-n+1}{2} &  si & n\,\,es\,\,impar
             \end{array}
   \right.$

$f$ es biyectiva, así $\mathbb N\sim \mathbb Z$.

Tarea moral, demuéstralo.

5. El intervalo $(-\frac{\pi}{2}, \frac{\pi}{2})$ es equipotente a $\mathbb R$.

Considera la función tangente, la función tangente es biyectiva en ese intervalo.

Tarea moral, demuéstralo.

Definición

Si $A$ es un conjunto, decimos que $A$ es finito si $A=\emptyset$ o existe $n\in\mathbb N^+$, tal que $A\sim \set{1,\dotsc,n}$. El cardinal o número de elementos de $A$ es cero en el primer caso y $n$ en el segundo caso.

Si $A$ no es finito decimos que $A$ es infinito.

Notación

$\#\emptyset=\mid\emptyset\mid=0$, $\#A=\mid A\mid=n.$

En este caso si $f:\set{a,\dotsc,n}\to A$ denotamos a $f(i)$ por $a_i$ y así $A=\set{a_1,\dotsc,a_n}$ con $a_i\neq a_j$ $\forall i\neq j$.

Nota

Lo anterior está bien definido ya que se puede probar que:

Si $n\in\mathbb N^+$, todo subconjunto de $\set{1,\dotsc,n}$ es finito y tiene a lo más $n$ elementos.

Si $A$ es un conjunto finito con $n$ elementos, entonces todo subconjunto de $A$ es finito y tiene a lo más $n$ elementos.

La demostración puede verse en el libro de Avella y Campero mencionado en la bibliografía, corolario 6.9 y corolario 6.12

Observación

Dados $A$ y $B$ conjuntos finitos: $A\sim B$ si y sólo si $\#A= \#B$.

Teorema: principio de la suma.

Sean $A$ y $B$ conjuntos finitos con $A\cap B=\emptyset$, entonces $A\cup B$ es finito y $\#A\cup B=\#A+\#B$.

Demostración

Sean $A$ y $B$ conjuntos finitos con $A\cap B=\emptyset$. Sean $n=\#A$ y $m=\#B$, $f:\set{1,\dotsc,n}\to A$, $g:\set{1,\dotsc,m}\to B$ biyecciones.

Definimos:

$h:\set{1,2,\dotsc,n,n+1,n+2,\dotsc,n+m }\to A\cup B$

con

$h(i)= \left\{ \begin{array}{lcc}
             f(i) &   si  & i\in\set{1,\dotsc,n} \\
             \\ g(k) &  si & i=n+k\,\,con\,\,k\in\set{1,\dotsc,m}
             \end{array}
   \right.$

Veamos que $h$ es suprayectiva.

Sea $c\in A\cup B$, entonces $c\in A$ o $c\in B$.

Caso 1 $c\in A$

Como $f$ es suprayectiva existe $i\in \set{1,\dotsc,n}$, tal que $f(i)=c$, así $h(i)=f(i)=c.$

Caso 2 $c\in B$

Como $g$ es suprayectiva existe $k\in \set{1,\dotsc,m}$, tal que $g(k)=c$, así $h(n+k)=g(k)=c$.

Y por lo tanto $h$ es suprayectiva

Veamos que $h$ es inyectiva.

Sean $i,j\in \set{1,\dotsc,n+m}$, tales que $h(i)=h(j)$

Por demostrar que $i=j$

Caso 1

$i,j\in \set{1,\dotsc,n}.$

Por definición de $h$ tenemos que:

$f(i)=h(i), f(j)=h(j)$

Por hipótesis tenemos que

$h(i)=h(j)$

y por lo tanto

$f(i)=f(j).$

Como $f$ es inyectiva tenemos que $i=j.$

Caso 2

$i,j\in \set{n+1,\dotsc,n+m}.$

En este caso tenemos que $i=n+k$ y $j=n+q$ para algunos $k,q\in \set{1,\dotsc,m}.$

Por hipótesis tenemos que

$h(i)=h(j),$

así obtenemos las siguientes igualdades

$h(n+k)=h(i)=h(j)=h(n+q)$

Por definición de $h$ tenemos que

$h(n+k)=g(k)$ y $h(n+q)=g(q)$

De lo que se deduce que

$g(k)=h(n+k)=h(i)=h(j)=h(n+q)=g(q).$

Entonces $g(k)=g(q)$, y como $g$ es inyectiva entonces $k=q$ y por lo tanto $i=n+k=n+q=j. Así $i=j$.

Caso 3

$i\in \set{1,\dotsc,n}$ y $j\in \set{n+1,\dotsc,n+m}$

En este caso $j=n+k$ para algún $k\in \set{1,\dotsc,m}.$

Observa que:

$h(i)=f(i)\in A$ y que $h(j)=f(n+k)=g(k)\in B.$

Como $h(i)=h(j)$ entonces $h(i)\in A\cap B$ pero esto es una contradicción a nuestra hipótesis de que $\emptyset =A\cap B$, por lo tanto no ocurre este caso.

Caso 4

$j\in \set{1,\dotsc,n}$ y $i\in \set{n+1,\dotsc,n+m}$

Es similar al caso anterior y por lo tanto tampoco ocurre.

Por lo tanto $h$ es inyectiva y así $A\cup B$ es finito y $\#A\cup B=\#A+\#B$, que es lo que queríamos probar.

$\square$

Nota

La generalización del resultado anterior, llamado principio generalizado de la suma, se enuncia como sigue:

Si $A_1,\dotsc,A_t$ son conjuntos finitos tales que $A_i\cap A_j=\emptyset$ $\forall i\neq j$, entonces su unión es finita y $\#A_1\cup\dotsc \cup A_t= \#A_1+\dotsc +\#A_t$.

Corolario

Sean $A,B$ conjuntos finitos, entonces $A\cup B$ es finito y $\#A\cup B=\#A+\#B- \#A\cap B$.

Demostración

Sean $A$ y $B$ conjuntos finitos, y sean $n=\#A$ y $m=\#B.$

Observemos que

$A\cup B=A\cup(B\setminus A)$ con $A\cap(B\setminus A)=\emptyset$

y que

$B=(B\setminus A)\cup (A\cap B)$ con $ (B\setminus A)\cap (A\cap B)=\emptyset$.

Así por el teorema anterior tenemos que:

$\#A\cup B=\#A+\#(B\setminus A)$

y

$\#B=\#(B\setminus A)+\# (A\cap B)$

Despejando $ \#(B\setminus A)$ de la expresión anterior tenemos que

$\#(B\setminus A)=\#B -\# (A\cap B).$

Sustituyendo $\#B\setminus A$ en $\#A\cup B=\#A+\#(B\setminus A)$ tenemos lo que buscábamos.

$\#A\cup B=\#A+\#B- \#A\cap B.$

$\square$

Tarea Moral

1. Realiza la prueba de la equipotencia entre conjuntos para los ejemplos 3, 4 y 5 de la definición de equipotencia.

2. En cada inciso demuestra que los siguientes conjuntos $A$ y $B$ son equipotentes:

i) $A=\mathbb N$ y $B=\set{3,9,27,\dotsc}$.

ii) $A=\mathbb N$ y $B=\set{\dotsc,-5,-4,-3}$.

iii) $A=\set{x\in \mathbb R\mid x>0}$ y $B=\set{x\in \mathbb R\mid x<0}$.

3. Demuestra que $\mathbb Z$ es equipotente con el conjunto $\set{\dotsc,-12,-8,-4,0,4,8,12, \dotsc}$.

4. Sea $f:\mathbb N\to \mathbb Z$ dada por:

$f(n)= \left\{ \begin{array}{lcc}
             \frac{n}{2} &   si  & n\,\,es \,\, par \\
             \\ \frac{-n+1}{2} &  si & n\,\,es \,\, impar
             \end{array}
   \right.$

Prueba que $f$ es biyectiva y por lo tanto $\mathbb N\sim \mathbb Z$.

5. Prueba que los siguientes intervalos de recta real son equipotentes:

• $(0,1)$ y $(0,4)$
• $(0,4)$ y $(-6,-2)$
• $(0,1)$ y $(0,\pi)$
• $(0,\pi)$ y $(-\frac{\pi}{2},\frac{\pi}{2})$
  Reflexiona
  ¿El intervalo $(0,1)$ es equipotente con cualquier intervalo $(a,b)$ con $a<b$?
  ¿Cualesquiera dos intervalos abiertos de la recta son equipotentes?

6. Prueba las siguientes propiedades de la equipotencia:

• Sea $A$ un conjunto, entonces $A\sim A$.
• Sean $A$ y $B$ conjuntos, si $A\sim B$ entonces $B\sim A.$
• Sean $A,B,C$ conjuntos, si $A\sim B$ y $B\sim C$ entonces $A\sim C.$

7. Sean $A$ y $B$ conjuntos finitos. Prueba que $A\sim B$ si y sólo si $\#A=\#B$.

8. Sean $A$ y $B$ conjuntos finitos. Demuestra que:

• Si $\#A=0$, entonces $A=\emptyset.$
• Si $A\subseteq B$ y $\#A=\#B$ entonces $A=B.$

9. Ve el siguiente video sobre el cuento de los hoteles infinitos del matemático David Hilbert.

Más adelante

En la siguiente nota probaremos de qué tamaño es el producto cartesiano de dos conjuntos finitos, veremos también que las funciones inyectivas entre dos conjuntos finitos de la misma cardinalidad hacen de estas funciones suprayectivas, y por lo tanto biyectivas.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 18. El principio de inducción matemática.

Nota siguiente. Nota 20. Principio del producto, funciones entre conjuntos finitos.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota usaremos el quinto axioma de Peano para hacer un tipo de prueba muy usada en matemáticas cuando se quiere constatar que un subconjunto $A$ de los números naturales es de hecho igual que los números naturales, es decir que $A=\mathbb N$. Nosotros obtuvimos el quinto axioma de Peano de una definición conjuntista de los números naturales (ver nota 16), que nos dice que si en un conjunto cualquiera de los números naturales: se cumple que el cero está y que para cualquier elemento del conjunto su sucesor también está, entonces, ese conjunto es el de los números naturales. Hay muchísimos ejemplos donde queremos garantizar que cierta propiedad se cumple para todos los números naturales, así que una forma de hacerlo es considerar la colección de todos los números naturales que cumplen dicha propiedad y usar el quinto axioma de Peano para ver que esa colección es de hecho el conjunto de todos lo números naturales.

Procedamos a dar una basta serie de ejemplos donde se usa este principio, en todos ellos probaremos que un subconjunto $A$ de naturales es igual a $\mathbb N$, para ello veremos que

$i)\, 0\in A$ (llamada la base de inducción), y que

$ii)$ si $x\in A$, entonces $x+1\in A$ (para ello supondremos que $x\in A$, hipótesis que se conoce comúnmente como hipótesis de inducción).

Con estas dos condiciones satisfechas podemos asegurar que $A=\mathbb N$ en virtud del quinto Axioma de Peano.

Ejemplos de demostraciones que usan el principio de inducción

En los siguientes ejemplos veremos cómo se usa el principio de inducción o quinto axioma de Peano, que derivamos de nuestra definición de números naturales. Recordemos que probamos lo siguiente:

Si $A\subseteq \mathbb N$ es tal que:

$i)$ $0\in A.$

$ii)$ $\forall n$, si $n\in A$, entonces $n^+\in A.$

Entonces se tiene que $\mathbb N\subseteq A$ y así $A=\mathbb N$.

Ejemplos

1. La suma de los primeros $n$ naturales está dada por la fórmula:

$0+1+\dotsc +n=\frac{n(n+1)}{2}$ $\forall n\in \mathbb N.$

Queremos ver que la fórmula anterior se cumple para toda $n$ natural, pero hasta el momento no sabemos que así sea. Podemos entonces considerar el conjunto de naturales para los que sí se cumpla la fórmula, digamos

$A=\set{ n\in \mathbb N \mid 0+1+\dotsc +n=\frac{n(n+1)}{2} }.$

Si logramos probar que en $A$ están todos los naturales, entonces habremos probado que la fórmula se cumple para todos los naturales. Una forma de hacerlo es usando el principio de inducción:

Por demostrar que $A=\mathbb N.$

i) Por demostrar que $0\in A.$

$0=\frac{0(0+1)}{2}$. Por lo tanto, $0\in A.$

ii) Sea $n\in A$, es decir supondremos que

$0+1+\dotsc +n=\frac{n(n+1)}{2}$

y a esta hipótesis le llamaremos la hipótesis de inducción y la abreviaremos como HI.

Por demostrar que el sucesor de $n$ también está en $A$, es decir por demostrar que $n^+=n+1\in A.$

Veamos que $0+1+\dotsc +(n+1)=\frac{(n+1)((n+1)+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Usando la hipótesis de inducción sabemos que $(0+1+\dotsc +n)+(n+1)=\frac{n(n+1)}{2}+(n+1)= \frac{(n)(n+1)+2(n+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Así $n^+=n+1\in A$ y por el principio de inducción $A=\mathbb N.$

$\square$

Observemos que probar que $0\in A$ fue equivalente a probar que la fórmula que queríamos probar se cumplía para $n=0$. Por otro lado suponer que $n\in A$ fue equivalente a suponer que la fórmula se cumplía para $n$, y demostramos a partir de ello que $n+1\in A$ verificando que la fórmula se cumplía para $n+1$. Así, comúnmente se omite el conjunto $A$ que consiste de todos los naturales que cumplen la propiedad que queremos verificar para todos los naturales y directamente se verifican los siguientes puntos:

$i)$ La propiedad se cumple para $n=0$,

$ii)$ $\forall n\in\mathbb{N}$, si $n$ cumple la propiedad , entonces $n+1$ también la cumple,

y con ello demostramos que todos los números naturales cumplen la propiedad. Veamos más ejemplos.

2. La suma de las potencias consecutivas de dos $2^0+2^1+\dotsc+2^n=2^{n+1}-1$, $\forall n\in \mathbb N.$

Base de inducción HI

Veamos que el cero cumple la fórmula

$2^0=1=2^{0+1}-1$, por lo tanto la formula se cumple para $n=0.$

Hipótesis de inducción

Sea $n\in \mathbb N$.

Supongamos que el resultado se cumple para $n$ es decir supongamos que:

$2^0+2^1+\dotsc+2^n=2^{n+1}-1.$

Ésta es nuestra hipótesis de inducción.

Veamos ahora que se cumple para $n+1$.

Tenemos que

$(2^0+2^1+\dotsc+2^n)+2^{n+1}=(2^{n+1}-1)+2^{n+1}=2( 2^{n+1} )-1= 2^{(n+1)+1}-1. $

Por lo tanto

$2^0+2^1+\dotsc+2^n=2^{n+1}-1$, $\forall n\in \mathbb N.$

$\square$

3. Prueba de que $1+2n<3^{n}$ $\forall n\in \mathbb N$, $n\geq 2$.$\quad\quad\quad *$

Observa que, dado que $n\geq 2$ tenemos que $n=m+2$ para alguna $m\in\mathbb{N}$, así que lo que debemos probar es equivalente a demostrar que:

$1+2(m+2)<3^{m+2}$ $\forall m\in \mathbb N$.$\quad\quad\quad **$

Para ello basta ver que

$i)$ La propiedad ** se cumple para $m=0$,

$ii)$ $\forall m\in\mathbb{N}$, si $m$ cumple la propiedad **, entonces $m+1$ también la cumple.

Pero el que ** se cumpla para $m+1$ significa que $1+2((m+1)+2)<3^{(m+1)+2}$, es decir que $1+2((m+2)+1)<3^{(m+2)+1}$. Así, debemos ver que

$i)$ La propiedad ** se cumple para $m=0$,

$ii)$ $\forall m\in\mathbb{N}$, si $1+2(m+2)<3^{m+2}$, entonces $1+2((m+2)+1)<3^{(m+2)+1}$,

y como $n=m+2,$ escribiendo todo en términos de $n$ esto es equivalente a probar que

$i)$ La propiedad * se cumple para $n=2$,

$ii)$ $\forall n\in\mathbb{N}$ con $n\geq 2$, si $1+2n<3^{n}$, entonces $1+2(n+1)<3^{n+1}.$

Así, cuando queramos probar una afirmación para todos los naturales a partir de un valor $k$, bastará con realizar el proceso de inducción de la manera usual sólo que la base de inducción se trabajará con $n=k$ en vez de $n=0$.

Escribamos ahora sí la prueba del ejercicio:

Base de inducción

$n=2$

$1+2*2<3^{2}$ es verdadero pues

$1+2*2=5<9=3^2.$

Hipótesis de inducción

Supongamos que el resultado se cumple para $n\geq 2$, es decir supongamos que $1+2n<3^n$.

Veamos ahora que se cumple para $n+1.$

Por demostrar que $1+2(n+1)<3^{n+1}.$

Multiplicando la HI por 3

$3+6n=3(1+2n)<3*3^n=3^{n+1}.$

Como $1+2(n+1)<3+6n$ pues $n\geq 2$ y entonces $0<4n$ pero:

$0<4n\Longleftrightarrow 2n<6n \Longleftrightarrow 3+2n<6n+3 \Longleftrightarrow 1+2(n+1)<6n+3.$

Y entonces como $3+6n<3^{n+1}$ concluimos que:

$1+2(n+1)<3^{n+1}.$

Que es lo que queríamos probar, y por lo tanto $1+2(n+1)<3^{n+1}$ $\forall n\in \mathbb N$, $n\geq 2$.

$\square$

A continuación enunciaremos el segundo principio de inducción y su equivalente el principio de buen orden.

Segundo principio de inducción (inducción fuerte o modificada)

Si $A\subseteq \mathbb N$ es tal que:

Para toda $n$, si $m\in A$ para toda $m<n$, entonces $n\in A.$

Concluimos que $A=\mathbb N$.

Principio del buen orden PBO

Si $A$ es un subconjunto no vacío de $\mathbb N$, entonces $A$ tiene un elemento menor o igual a los demás. Es decir si $A\subseteq \mathbb N$, $A\neq \emptyset$, entonces existe $m\in A$, tal que $m\leq a$ $\forall a\in A$.

Nota. El segundo principio de inducción y el principio del buen orden son equivalentes y ambos se pueden probar con el principio de inducción.

Ejemplo del segundo principio de inducción

Considera la sucesión de Fibonacci:

$1,1,2,3,5,8,\dotsc $

dada por

$F_0=F_1=1$

$F_{n+2}=F_n+F_{n+1} \,\forall n\in\mathbb{N}$

Veamos que $F_n\leq 2^n$ $\forall n\in \mathbb N$.

Sea $n\in \mathbb N.$ Supongamos que $F_m\leq 2^m$ $\forall m\in \mathbb N$ con $m<n.$

Por demostrar que

$F_n\leq 2^n.$

Si $n=0$ o $n=1$

$F_0=1=2^0$, $F_1=1<2^1=2$.

Podemos suponer entonces que $n>1$, así $n\geq 2.$

Entonces $n=2+k$, con $k\in \mathbb N$ y así

$F_n=F_{2+k}=F_k+F_{k+1}$ que por hipótesis de inducción es menor que $2^k+2^{k+1}$. Concluimos que:

$F_n=F_{2+k}=F_k+F_{k+1}\leq 2^k+2^{k+1} =2^k(1+2)= 2^k(3)< 2^k(4)= 2^k(2^2)=2^{k+2}=2^n.$

Y por lo tanto $F_n\leq 2^n$ $\forall n\in \mathbb N.$

Tarea Moral

1. Prueba que para toda $n\in \mathbb N$

$\sum_{k=0}^{n}k^2=\frac{n(n+1)(2n+1)}{6}.$

2. Prueba que para toda $n\in \mathbb N$, $n<2^n.$

3. Prueba que la suma de los ángulos internos de un polígono de $n$ lados es $(n-2)180$ usando inducción sobre $n$.

4. Considera la secuencia definida de manera recursiva como:

$f_0=1$, $f_{n+1}=f_n+\dotsc+f_0+1.$

Prueba que $f_n=2^n$ para toda $n\in \mathbb N$.

Más Adelante

En la siguiente nota haremos un estudio del tamaño de los conjuntos, usando funciones para medirlas. Veremos que la noción intuitiva de que dos conjuntos sean del mismo tamaño se formalizará pidiendo que exista una función biyectiva entre ambos.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 17. El orden en los números naturales.

Nota siguiente. Nota 19. Conjuntos equivalentes y cardinalidad.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota continuaremos con el estudio de las propiedades de los números naturales, y desarrollaremos formalmente el concepto de cuándo una magnitud es más grande que otra, es decir daremos un orden al conjunto de números naturales que acabamos de construir, y a partir de él podremos decir cuándo un elemento es más grande que otro.

Procedamos a dar la definición formal del orden en los números naturales.

Definición. Orden en $\mathbb N$ .

Sean $n,m\in \mathbb N$.

Decimos que $n$ es menor que $m$, si existe $x\in \mathbb N$, $x\neq 0$, tal que:

$n+x=m.$

Lo denotaremos por $n<m$ (o por $m>n$).

Decimos que $n$ es menor o igual que $m$, si existe $x\in \mathbb N$, tal que:

$n+x=m.$

Lo denotaremos por $n\leq m$ (o por $m\geq n$).

Observación 1

Si $n\in \mathbb N$, $n\neq 0$, entonces $n>0$.

Demostración: Si $n\in \mathbb N$, $n\neq 0$ tenemos que $0+n=n$, con $n\in \mathbb N$, $n\neq 0$, por lo tanto $0<n$.

Observación 2

Para toda $n\in \mathbb N$, $n<n^+$.

Demostración: Dada $n\in \mathbb N$ , $n+1=n^+$ con $1\in \mathbb N$, $1\neq 0$, por lo tanto $n<n^+$.

Observación 3

Si $n\in \mathbb N$, con $n\neq 0$, entonces $n\geq 1$.

Demostración: Se prueba por inducción que si $n\in \mathbb N$, entonces $n=0$ o $n=m^+$ con $m\in \mathbb N$. De esta forma si $n\in \mathbb N$ y $n\neq 0$, entonces $n=m^+=m+1$ con $m\in \mathbb N$, y se concluye que $n\geq 1$.

Propiedades de Orden en $\mathbb N$

Sean $n,m,l\in \mathbb N$

1. Si $n<m$ y $m<l$, entonces $n<l$.
2. Si $n<m$, entonces $n+l<m+l$.
3. Si $n<m$ y $l\neq 0$, entonces $nl<ml$.
4. Se cumple una y sólo una de las siguientes condiciones:
   $n<m$, $n=m$ o $n>m$
   A este hecho se le conoce como tricotomía.
5. Si $n+l<m+l$, entonces $n<m$.
6. Si $nl<ml$, entonces $n<m$.

Demostración

Demostración de 1

Por demostrar que si $n<m$ y $m<l$, entonces $n<l$.

Supongamos que $n<m$ y que $m<l$, entonces existen $x,y \in \mathbb N$, $x\neq 0$, $y\neq 0$ tales que:

$n+x=m$

$m+y=l.$

Así $n+(x+y)=(n+x)+y=m+y=l$, con $x,y \in \mathbb N$, $x+y\neq 0$, ya que $x\neq 0$, $y\neq 0$ y por lo tanto $n<l$.

Demostración de 2

Por demostrar que si $n<m$, entonces $n+l<m+l$.

Supongamos que $n<m$, entonces existe $x\in \mathbb N$, $x\neq 0$ tal que $n+x=m$.

Por las propiedades de la suma $(n+l)+x=(n+x)+l=m+l$ con $x \in \mathbb N$, $x\neq 0$ y por lo tanto $n+l<m+l$.

Demostración de 3

Supongamos que $n<m$ y $l\neq 0$. Existe $x \in \mathbb N$, $x\neq 0$ tal que $n+x=m$.

Por las propiedades de las operaciones de los naturales $nl+xl=(n+x)l=ml$ con $xl \in \mathbb N$ y $xl\neq0$ ya que $x\neq 0$, $l\neq 0$, por lo tanto $n+l<m+l$.

Demostración de 4

La prueba se realiza por inducción pero se omitirá debido a que preferimos estudiar las pruebas por inducción en casos más concretos con el fin de que se entiendan con mayor claridad.

Demostración de 5

Por demostrar que si $n+l<m+l$ entonces $n<m$.

Supongamos que $n+l<m+l$

Por la propiedad $4$ sabemos que sólo pasa alguna de estas tres situaciones:

$n<m$, $n=m$ o $n>m.$

Si $n=m$, entonces $n+l=m+l$, lo cual contradice nuestra hipótesis.

Si $n>m$, entonces por $2$ se tiene que $n+l>m+l$, lo cual contradice la hipótesis.

Así la única posibilidad es que $n<m$.

Demostración de 6

Por demostrar que si $nl<ml$ entonces $n<m$.

Supongamos que $nl<ml$, por $4$ sabemos que $n<m$, $n=m$ o $n>m$.

Si $n=m$ entonces $nl=ml$, lo cual contradice la hipótesis.

Si $n>m$, $nl=ml$ si $l=0$, o $nl<ml$ si $l\neq = 0$ por $3$, pero esto es una contradicción a nuestra hipótesis.

Así la única posibilidad es que $n<m$.

$\square$

Tarea Moral

1. Sean $n,m\in \mathbb N$. Prueba que si $n\geq 2$ y $m\geq2$, entonces $n+m\leq nm$.

2. Sea $n,m,l,t\in \mathbb N$, prueba o da un contraejemplo para las siguientes afirmaciones:

i) Si $n<l$ y $m<t$ entonces $n+m<l+t$.

ii) Si $n<l$ y $m<t$ entonces $nm<lt$.

iii) Si $n<l$ y $m<t$ entonces $n+m<lt$.

Más adelante

En la siguiente nota aplicaremos el quinto axioma de Peano para ver un tipo especial de prueba, que se usa cuando se quiere garantizar que un subconjunto de los números naturales de hecho el de todos los naturales.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 16 Los números naturales.

Nota siguiente. Nota 18. El principio de inducción matemática.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En la presente nota veremos lo que es una familia de conjuntos, una familia indexada de conjuntos y usaremos esos conceptos para establecer lo que es una partición de un conjunto dado. En ésta y la siguiente nota estableceremos la relación que hay entre las particiones y las relaciones de equivalencia.

Definición

Un conjunto de conjuntos se llama una familia de conjuntos.

Ejemplo

$\mathscr F=\set{\set{1,4,7},\set{0,2},\mathbb N}.$

Definición

Sea $I$ un conjunto. Para cada $i\in I$ consideremos un conjunto $A_i$. Decimos que: $\mathscr F=\set{A_i\mid i\in I}$ es una familia de conjuntos indexada por $I$, a $I$ se le llama un conjunto de índices.

La unión de $\mathscr F$ es:

$\bigcup\limits_{i\in I} A_{i}=\set{x\mid x\in A_i\,\,para \,\, algún \,\, i\in I}$

La intersección de $\mathscr F$ es:

$\bigcap\limits_{i\in I} A_{i}=\set{x\mid x\in A_i\,\,para \,\, toda\,\, i\in I}$.

Nota. Si $\mathscr F\neq \emptyset$, considerando algún $C\in \mathscr F $, tenemos que

$\bigcap\limits_{i\in I} A_{i}=\set{x\in C\mid x\in A_i\,\,para \,\, toda\,\, i\in I},$

y por el axioma de separación $\bigcap\limits_{i\in I} A_{i}$ es un conjunto. Por otro lado, existe un axioma que asegura que la unión de una familia de conjuntos es un conjunto.

Ejemplos

1. Si $\mathscr F=\set{A_1, A_2, A_3, A_4}=\set{A_i\mid i\in \set{1,2,3,4}}$, con:

$A_1=\set{2,-1,9,3,5}$

$A_2=\set{-2,0,2,4}$

$A_3=\set{2,12}$

$A_4=\set{1,2,3,4,5}$

$\bigcup\limits_{i\in\set{1,2,3,4}}A_i=\set{2,-1,9,3,5,-2,0,4,12,1}$

$\bigcap\limits_{i\in\set{1,2,3,4}}A_i=\set{2}$

2. Sea $I=\set{1,2,3,\dotso}$, $B_i=[0,i]$ $\forall i\in I$

$\mathscr F=\set{B_i\mid i\in I}$

$\bigcup\limits_{i\in I}B_i=[0,\infty)$

$\bigcap\limits_{i\in I}B_i=B_1=[0,1]$

En el siguiente clip se observan los primeros 50 intervalos en el eje x.

3. Sea $I=\mathbb R^+$, $C_r=[-r,r]$ $\forall r\in I$

$\mathscr F=\set{C_r\mid r\in I}$

$\bigcup\limits_{r\in I}C_r=\mathbb R$

$\bigcap\limits_{r\in I}C_r=\set{0}$

En el siguiente clip se observan algunos de esos intervalos.

Definición

Sea $A$ un conjunto. Una partición de $A$ es una familia $P=\set{A_i\mid i\in I}$ de subconjuntos de $A,$ es decir $A_i\subseteq A$ $\forall i\in I$, tal que:

1. $A_i\neq \emptyset$ $\forall i\in I$
2. Si $i,j\in I$ son tales que $A_i\neq A_j$, entonces $A_i\cap A_j=\emptyset$
3. $A=\bigcup\limits_{i\in I}A_i$

Ejemplo

$A=\set{1,2,3}$, veamos las distintas particiones de $A$.

$P_1=\set{\set{1}, \set{2,3} }$

$P_2=\set{\set{3}, \set{1,2} }$

$P_3=\set{\set{2}, \set{1,3} }$

$P_4=\set{\set{1}, \set{2},\set{3} }$

$P_5=\set{\set{1,2,3}}$

Lema

Sea $A$ un conjunto, $\mathcal R$ una relación de equivalencia en $A$. Dados $x,y\in A$. Dados $x,y\in A$.

1. Si $x\sim y$ entonces $\overline{x}=\overline{y}.$
2. Si $x\nsim y$ entonces $\overline{x}\cap \overline{y}=\emptyset$.

Demostración de 1.

Sea $A$ un conjunto , $\mathcal R$ una relación de equivalencia en $A$, $x,y\in A$.

Supongamos que $x\sim y$.

Por demostrar que $\overline{x}=\overline{y}$.

La prueba se hará por doble contención.

$\subseteq $ Primera contención

Por demostrar que $\overline{x}\subseteq \overline{y}$.

Sea $z\in\overline{x}=\set{a\in A\mid a\sim x}$, entonces $z\sim x$ y por hipótesis $x\sim y$, por transitividad de $\mathcal R$ $z\sim y$ y así $z\in\set{a\in A\mid a\sim y}=\overline{y}$. Por lo tanto $\overline{x}\subseteq \overline{y}$.

$\supseteq $ Segunda contención

Por demostrar que $\overline{y}\subseteq \overline{x}$.

Sea $z\in\overline{y}=\set{a\in A\mid a\sim y}$, entonces $z\sim y$ y por hipótesis $x\sim y$, por ser $\mathcal R$ simétrica $y\sim x$. Así, $z\sim y$ y $y\sim x$, entonces por transitividad $z\sim x$, es decir $z\in\set{a\in A\mid a\sim x}=\overline{x}$. Por lo tanto $\overline{y}\subseteq \overline{x}$.

Dado que se cumplen las dos contenciones tenemos que $\overline{x}=\overline{y}$, que es lo que queríamos probar.

$\square$

Demostración de 2.

Queremos probar que si $x\nsim y$, entonces $\overline{x}\cap \overline{y}=\emptyset$.

Supongamos que $x\nsim y$ y supongamos también por reducción al absurdo que $\overline{x}\cap \overline{y}\neq \emptyset$, por lo que existe $z\in \overline{x}\cap \overline{y}$, es decir $z\in \overline{x}$ y $z\in \overline{y}$. Así $z\sim x$ y $z\sim y$, entonces por simetría $x\sim z,$ y como $z\sim y$ por transitividad de la relación de equivalencia tenemos que $x\sim y$, lo cual es una contradicción a nuestra primera hipótesis, por lo tanto $\overline{x}\cap \overline{y}=\emptyset$.

$\square$

Tarea Moral

1. Considera los siguientes conjuntos:

$A_1=\set{1,3,5,7,11}$

$A_2=\set{-5,-3,-1,1,3,5}$

$A_3=\set{1,2,3,4,5,6,7}$

$A_4=\set{-5,-3,1,3,5}$

$A_5=\set{0,3,5,11}$

Encuentra $\bigcup\limits_{i\in\set{1,2,3,4,5}}A_i$ y $\bigcap\limits_{i\in\set{1,2,3,4,5}}A_i$.

2. En cada uno de los siguientes incisos encuentra $\bigcup\limits_{i\in I} B_{i}$ y $\bigcap\limits_{i\in I} B_{i}$.

i) Sea $I=\mathbb Z$, $B_i=[i,i+1]$.

ii) Sea $I=\mathbb N$, $B_i=[-i,i+1]$.

3. Encuentra todas las posibles particiones de $\set{3,6,7,9}$.

Más adelante.

En la siguiente nota terminaremos de ver que una relación de equivalencia induce una partición, y una partición induce una relación de equivalencia.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 13. Relación de equivalencia.

Enlace a la nota siguiente. Nota 15. Relaciones de equivalencia y particiones