(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 frecuente 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 la 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 los 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 $n\in A$, entonces $n^+=n+1\in A$ (llamado paso Inductivo (PI), para ello supondremos que $n\in A$, hipótesis que se conoce comúnmente como la hipótesis de inducción (HI), y probaremos que $n+1\in A$).

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 justificamos a partir de la definición de los números naturales.

Ejemplos

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

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

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) Base de inducción. Por demostrar que $0\in A.$

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

ii) Paso Inductivo. (PI).

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

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

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

Demostración de que $n^+=n+1\in A$ usando la HI.

Por demostrar que el sucesor de $n$ también está en $A$, es decir por demostrar que $n^+=n+1\in A,$ o de modo equivalente por demostrar 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.

Para los siguientes ejemplos requerimos la definición de potencia de un natural:

Definición. Potencia en $\mathbb N$

Dado $a\in \mathbb N$ definimos:

$a^0=1,$

para todo $m\in \mathbb N$, $a^{m+1}=a(a^m).$

Observación

Notemos que de acuerdo a la definición anterior, dado $a\in \mathbb N$ se tiene que $a^1=a^{0+1}=a(a^0)=a(1)=a$. Así, $a^1=a$.

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

i) Base de inducción. Veamos que el cero cumple la fórmula

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

ii) Paso Inductivo. (PI).

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.

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$. Usando la hipótesis de inducción

$(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. Para todo $n\in \mathbb N$ con $n\geq 2$, $1+2n<3^{n}.$ $\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:

Para todo $n\in\mathbb{N}$, $1+2(m+2)<3^{m+2}.$ $\quad\quad\quad **$

Para ello basta ver que

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

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

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) Para todo $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) Base de inducción. La propiedad * se cumple para $n=2$,

ii) Paso Inductivo. (PI).

Para todo $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:

i) Base de inducción. Para $n=2$

$1+2(0+2)<3^{(0+2)}$ es verdadero pues

$1+2(0+2)=5<9=3^2.$

ii) Paso Inductivo. (PI).

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

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

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$, es decir mostremos que $1+2(n+1)<3^{n+1}.$

Multiplicando la HI por $3$ tenemos que

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

Basta ver que $1+2(n+1)<3+6n$. Como $n\geq 2$, entonces $0<4n$ pero:

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

Así, $1+2(n+1)<3+6n$.

Tenemos entonces que $1+2(n+1)<3+6n$ y que $3+6n<3^{n+1}$ por lo que concluimos que:

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

que es lo que queríamos probar.

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 para todo $m<n$, $m\in A$, implica que $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 para todo $a\in A$ $m\leq 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,$

para todo $n\in \mathbb{N}$, $F_{n+2}=F_n+F_{n+1}.$

Veamos que para todo $n\in\mathbb{N}$, $F_n\leq 2^n$.

Sea $n\in \mathbb N.$ Supongamos que para todo $n\in\mathbb{N}$ con $m<n,$ $F_m\leq 2^m.$

Por demostrar que

$F_n\leq 2^n.$

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

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

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:

\begin{align*}F_n=F_{2+k}&=F_k+F_{k+1}\leq 2^k+2^{k+1}=1(2^k)+2(2^k) =2^k(1+2)= 2^k(3)\\&< 2^k(4)=2(2(2^k))=2(2^{k+1})=2^{(k+1)+1}=2^{k+2}=2^n.\end{align*}

Por lo tanto para todo $n\in\mathbb{N}$, $F_n\leq 2^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$.

5. Sean $a,b,n,m\in\mathbb{N}$. Demuestra que por inducción que:

i) $a^nb^n=(ab)^n,$

ii) $a^na^m=a^{n+m}.$

Sugerencia: En el inciso $ii$ considera $n$ fija y realiza inducción sobre $m$.

Más Adelante

Ahora que ya estamos más familiarizados con las pruebas por inducción, en la siguiente nota continuaremos usando el quinto Axioma de Peano para realizar demostraciones y probaremos de esta forma las propiedades de la suma y el producto de los números naturales.

Enlaces relacionados.

Página principal del curso.

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

Nota siguiente. Nota 18b. Demostraciones por inducción de las propiedades de las operaciones de los números naturales.

(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 un número natural es más grande que otro, es decir daremos un orden en el conjunto de los números naturales que acabamos de construir, a partir del cual podremos decir cuándo un número natural 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$).

En ambos casos, le llamaremos al natural $x$ la diferencia de $m$ con $n$ y lo denotaremos por $m-n$.

Observación 1

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

Demostración: Si $n\in \mathbb N$ y $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$ , como $n+1=n^+$ (por la observación 3 de la nota previa) con $1\in \mathbb N$ (por el tercer Axioma de Peano), $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: De acuerdo a un ejercicio de la tarea moral de la nota previa, 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$ para alguna $m\in \mathbb N$ y se concluye que $n\geq 1$.

Notación

Denotaremos por $\mathbb{N}^+$ al conjunto de números naturales distintos de cero, es decir $\mathbb{N}^+=\{n\in\mathbb{N}\mid n\geq 1\}.$

Notación

En ocasiones simplificaremos la notación del producto de los naturales y escribiremos $nm$ en lugar de $n\cdot m$, para cualesquiera $n,m\in\mathbb{N}.$

Propiedades de Orden en $\mathbb N$

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

1. Si $n<m$ y $m<l$, entonces $n<l$. Esta es la propiedad transitiva.
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$. Además, por las propiedades de la suma de los naturales, como $x\neq 0$ y $y\neq 0$ se tiene que $x+y\neq 0$. 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

Por demostrar que si $n<m$ y $l\neq 0$, entonces $nl<ml$.

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$. Además, debido a las propiedades del producto de los naturales, como $x\neq 0$ y $l\neq 0$ tenemos que $xl\neq0$. Por lo tanto $nl<ml$.

Demostración de 4

La prueba se realiza por inducción pero en la nota 18b se dejará revisarla a manera de ejercicio debido a que preferimos estudiar primero 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 se tiene que $n+l=m+l$, lo cual contradice nuestra hipótesis.

Si $n>m$, entonces por la propiedad $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$ y $l=0$ tendríamos que $nl=ml$, por otro lado si $n>m$ y $l>0$, tendríamos que $nl<ml$ por la propiedad $3$. En cualquier caso 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 explicaremos con detalle cómo aplicar el quinto axioma de Peano para hacer pruebas por inducción. En dichas pruebas se garantiza que un subconjunto de los números naturales es de hecho el de todos los naturales y con ello se justifica que alguna propiedad se cumple para todos los números 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 hablaremos de 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. Finalizaremos esta nota con un lema que nos permitirá establecer en la nota siguiente la relación que hay entre las particiones y las relaciones de equivalencia.

Observación

En los contextos en los que sea importante construir conjuntos que tengan por elementos a subconjuntos de conjuntos con los que se está trabajando, se acostumbra llamar a los conjuntos construidos de esta forma familias 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}$

Si $\mathscr F\neq \emptyset$, 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$, entonces $\mathscr F$ tiene algún $C\in \mathscr F $, así,

$\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.

De forma más general, si $\mathscr{F}$ es una clase no vacía de conjuntos, digamos con $C\in \mathscr{F}$, entonces podemos considerar la colección $\set{x\in C\mid x\in A\,\,para \,\, toda\,\, A\in \mathscr{F}}$, que será un conjunto por el axioma de separación, incluso si $\mathscr{F}$ es una clase propia. Denotaremos a este conjunto por $\bigcap \mathscr{F}$ y le llamaremos la intersección de la colección $\mathscr{F}$.

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, es decir, $B_i$ para $1\leq i\leq 50$.

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$

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$. Dado que $\overline{x}\cap \overline{y}\neq \emptyset$, 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 veremos que toda relación de equivalencia induce una partición, y toda 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

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

Introducción

En esta nota veremos el concepto de relación de equivalencia, útil en distintas áreas de la matemática, como el álgebra, la teoría de los números, el análisis, la topología, etc. Sería conveniente que revisaras el concepto de relación que vimos en la Nota 7. Relaciones y funciones .

Recuerda que dado un conjunto $A$, una relación $\mathcal R$ en $A$ es un subconjunto de $A\times A$, se llamará relación de equivalencia cuando cumpla tres condiciones que llamaremos reflexividad, simetría y transitividad.

Definición

Sea $A$ un conjunto, $\mathcal R\subseteq A\times A$ una relación. Decimos que $\mathcal R$ es una relación de equivalencia si y sólo si:

1. $\forall a\in A\,\,\,\,(a,a)\in R$, es decir es reflexiva.
2. $\forall a,b\in A$, si $(a,b)\in \mathcal R$, entonces $(b,a)\in \mathcal R$, es decir es simétrica.
3. $\forall a,b,c\in A$, si $(a,b)\in \mathcal R$ y $(b,c)\in \mathcal R$, entonces $(a,c)\in \mathcal R$, es decir es transitiva.

Ejemplos

1. $\mathcal R\subseteq \mathbb R\times \mathbb R$ con $\mathcal R=\set {(a,b)\in \mathbb R\times \mathbb R\mid a=b}$

$\forall a\in \mathbb R$ la pareja $(a,a)\in \mathcal R$ ya que $a=a$, y por lo tanto es reflexiva.

$\forall a,b\in \mathbb R$, si $(a,b)\in \mathcal R$ entonces $a=b$, en consecuencia $b=a$ y por lo tanto $(b,a)\in \mathbb R$, así la relación es simétrica.

$\forall a,b,c\in \mathbb R$, si $(a,b)\in \mathcal R$ y $(b,c)\in \mathcal R$ entonces $a=b$ y $b=c$, así $a=c$ y entonces $(a,c)\in \mathcal R$, así la relación es transitiva.

2. $\mathcal R\subseteq \mathbb Z\times \mathbb Z$ con $(a,b)\in \mathcal R$ si y sólo si $a<b$.

Veamos que esta relación es transitiva: dados $a,b,c\in \mathbb Z$ si $(a,b)\in \mathcal R$ y $(b,c)\in \mathcal R$, entonces $a<b$ y $b<c$, de donde concluimos que $a<c$ y así $(a,c)\in \mathcal R$.

No es reflexiva pues $1\nless1$, así $(1,1)\notin \mathcal R$.

No es simétrica ya que $1<2$, pero $2\nless 1$, así $(1,2)\in \mathcal R$ pero $(2,1)\notin \mathcal R$.

Por lo tanto la relación $\mathcal R$ no es una relación de equivalencia.

3. Sea $\mathcal R$ una relación en $\mathbb Z$, dada por $(a,b)\in \mathcal R$ si y sólo si $a$ y $b$ tienen la misma paridad, es decir si y sólo si ambos son pares o ambos son impares.

Notemos que:

$(a,b)\in \mathbb R$ si y sólo si $a-b$ es par.

Tenemos entonces que $(a,a)\in \mathbb R$ pues $a-a=0=2(0)$, así la relación es reflexiva.

Si $(a,b)\in \mathcal R$, entonces $a-b$ es par, por lo cual $a-b=2k$, con $k\in \mathbb Z$. Así, $b-a=2(-k)$ con $-k\in \mathbb Z$, lo que nos permite concluir que $b-a$ también es par y entonces $(b,a)\in \mathcal R$. Así, la relación es simétrica.

Para mostrar que $\mathcal R$ es transitiva, sean $(a,b)\in \mathcal R$ y $(b,c)\in \mathcal R$, entonces $a-b$ y $b-c$ son pares es decir:

$a-b=2k$ y $b-c=2q$ con $k,q\in \mathbb Z$.

Así, $a-c=(a-b)+(b-c)=2k+2q=2(k+q)$ con $k+q\in \mathbb Z.$

Esto nos muestra que $a-c$ es par y entonces $(a,c)\in \mathcal R$. Así, $\mathcal R$ es transitiva.

Dado que $\mathcal R$ es reflexiva, simétrica y transitiva concluimos que $\mathcal R$ es una relación de equivalencia.

Notación:

Si $\mathcal R$ es una relación de equivalencia:

$(a,b)\in \mathcal R$ se denota por $a\sim b$.

$(a,b)\notin \mathcal R$ se denota por $a\nsim b$.

Definición

Sea $A$ un conjunto, $\mathcal R$ una relación de equivalencia en $A$. Para cada $x\in A$ definimos la clase de equivalencia de $x$ como:

$[x]=\overline{x}=\set{y\in A\mid y\sim x},$

a cada $y\in \overline{x}$ se le llama un representante de la clase $\overline{x}$.

Ejemplos:

4. $\mathcal R$ la relación en $\mathbb R^2$ dada por $(p,q)\in \mathcal R$ si y sólo si $\|p\|=\|q\|$. (Recordemos que la norma de un vector en $x\in \mathbb R^2$, denotada por $\|x\|$, es la distancia de ese punto al origen).

$\mathcal R$ es una relación de equivalencia (quedará como ejercicio en la tarea moral).

Dado $p\in \mathbb R^2$

$\overline{p}=\set{q\in \mathbb R^2\mid q\sim p}=\set{q\in \mathbb R^2\mid \|p\|=\|q\|}.$

Por ejemplo:

$\overline{(2,2)}=\set{ q\in \mathbb R^2\mid \|q\|=\|(2,2)\|}=\set{ q\in \mathbb R^2\mid \|q\|=2\sqrt{2}}.$

Claramente $(2,2)$ es un representante de $\overline{(2,2)}$, pero no es el único. Por ejemplo $(2\sqrt{2},0)\in \overline{(2,2)}$, entonces $(2\sqrt{2},0)$ es otro representante de $\overline{(2,2)}$.

5. $\mathcal R$ la relación en $\mathbb Z$ dada por $a,b\in \mathbb Z$, $(a,b)\in \mathcal R$ si y sólo si $b-a$ es múltiplo de 3.

$\mathcal R$ es una relación de equivalencia (quedará como ejercicio en la tarea moral).

$\overline{a}=\set{b\in \mathbb Z\mid b\sim a}$

$\phantom{\overline{a}}=\set{b\in \mathbb Z\mid b-a\,\,\,es \,\,\,múltiplo\,\,\,de\,\,\,3}$

$\phantom{\overline{a}}=\set{b\in \mathbb Z\mid b-a=3k\,\, k\in Z}$

$\phantom{\overline{a}}=\set{3k+a\mid k\in \mathbb Z}$

Así:

$\overline{0}= \set{3k+0\mid k\in \mathbb Z}= \set{3k\mid k\in \mathbb Z}=\set{\dotsi,-6,-3,0,3,6,\dotsi}$

$\overline{1}= \set{3k+1\mid k\in \mathbb Z}=\set{\dotsi,-5,-2,1,4,7,\dotsi}$

$\overline{2}= \set{3k+2\mid k\in \mathbb Z}=\set{\dotsi,-4,-1,2,5,8,\dotsi}$

Tarea Moral

1. Determina si las siguientes relaciones en el conjunto $A$ son reflexivas, simétricas y transitivas:

i) $A=\set{2,3,4,\dotsi}$, $\mathcal R$ la relación en $A$ dada por $(a,b)\in \mathcal R$ si y sólo si $a$ y $b$ tienen un factor común distinto de $1$ o $-1.$

ii) $A=\set{t\mid t \, \,es \, \, un \, \, triángulo \, \, en \, \, \mathbb R^2}$

$\mathcal R$ la relación en $A$ dada por $(a,b)\in \mathcal R$ si y sólo si $a$ es semejante a $b$.

iii) $A=\mathbb R^2$, $\mathcal R$ es la relación en $A$ dada por $(a,b)\in \mathcal R$ si y sólo si $a$ y $b$ están sobre la misma recta horizontal.

iv) $A=\set{1,2,3,4}$, $\mathcal R$ la relación en $A$ dada por:

$\mathcal R=\set{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(4,3),(3,4)}$

2. Sean $A$ un conjunto y $\mathcal R$ una relación simétrica y transitiva en $A$. Sea $(x,y)\in \mathcal R$, por ser $\mathcal R$ simétrica $(y,x)\in \mathcal R$ y por transitividad concluimos que $(x,x)\in \mathcal R$. ¿Podemos entonces decir que la simetría y la transitividad implican la reflexividad?

3. Numerando las propiedades:

$1$ reflexividad

$2$ simetría

$3$ transitividad

Da relaciones, si es que existen, tales que:

Cumpla $1$ y $2$ pero no $3$.

Cumpla $1$ y $3$ pero no $2$.

Cumpla $2$ y $3$ pero no $1$.

Cumpla $1$ pero no $2$ y $3$.

Cumpla $2$ pero no $1$ y $3$.

Cumpla $3$ pero no $1$ y $2$.

4. En los incisos del ejercicio 1 en los que se tenga una relación de equivalencia describe las distintas clases de equivalencia.

5. Prueba que las relaciones dadas en los ejemplos 4 y 5 son relaciones de equivalencia.

Más adelante

En la siguiente nota describiremos qué es una partición. Veremos cómo es que dada una relación de equivalencia en un conjunto $A$ ésta nos genera una partición del conjunto, y también al revés, cómo dada una partición en $A$ tendremos asociada una relación de equivalencia a esa partición.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 12. Teoremas de la composición de funciones inyectivas, suprayectivas y biyectivas.

Enlace a la nota siguiente. Nota 14. Familia de Conjuntos y particiones.

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

Introducción

En la nota anterior definimos cuándo una función es inyectiva, suprayectiva y biyectiva. En esta nota daremos cinco resultados referentes a la composición de funciones inyectivas, suprayectivas y biyectivas, de forma que es conveniente que se tengan muy claras las definiciones de estos conceptos.

Teorema

La composición de funciones inyectivas es inyectiva.

Demostración

Consideraremos cualesquiera dos funciones inyectivas y vamos a mostrar que su composición es inyectiva.

Sean $A$, $B$, $C$ conjuntos $f:A\to B$, $g:B\to C$ funciones inyectivas.

Por demostrar que $g\circ f$ es inyectiva.

Para mostrar que la composición es inyectiva se tiene que ver que si $g\circ f(x_1)= g\circ f(x_2)$, entonces $x_1=x_2$.

Sean $x_1,x_2\in A$ tales que $g\circ f(x_1)= g\circ f(x_2)$

por definición de composición se tiene que

$g(f(x_1))= g(f(x_2)),$

al ser $g$ inyectiva esto implica que $f(x_1)=f(x_2)$

y como $f$ también es inyectiva concluimos que $x_1=x_2$.

Por lo tanto $g\circ f$ es inyectiva, así la composición de funciones inyectivas es inyectiva.

$\square$

Teorema

La composición de funciones suprayectivas es suprayectiva

Demostración

Sean $A$, $B$, $C$ conjuntos $f:A\to B$, $g:B\to C$ funciones suprayectivas.

Por demostrar que $g\circ f$ es suprayectiva.

Para probar que $g\circ f:A\to C$ es suprayectiva , dado $c\in C$, tenemos que exhibir $a\in A$ tal que $g\circ f(a)=c$.

Sea $c\in C$.

Como $g$ es suprayectiva, existe $b\in B$ tal que $g(b)=c$.

Como $f$ es suprayectiva, existe $a\ A$ tal que $f(a)=b$.

Entonces

$g\circ f(a)=g(f(a))=g(b)=c.$

Así, para cada $c\in A$ existe $a\in A$ tal que $g\circ f(a)=c$. Por lo tanto, $g\circ f$ es suprayectiva.

$\square$

Corolario

La composición de funciones biyectivas es biyectiva.

Demostración

Sean $A$, $B$, $C$ conjuntos $f:A\to B$, $g:B\to C$ funciones biyectivas.

Como $f$ y $g$ son biyectivas, en particular son inyectivas y por lo demostrado anteriormente $g\circ f$ es inyectiva.

Como $f$ y $g$ son biyectivas, en particular son suprayectivas y por lo demostrado anteriormente $g\circ f$ es suprayectiva.

Así, $g\circ f$ es inyectiva y suprayectiva y por lo tanto biyectiva, que es lo que queríamos probar.

$\square$

Teorema

Sean $A$, $B$, $C$ conjuntos $f:A\to B$, $g:A\to B$, $h:B\to C$ funciones, con $h$ inyectiva. Si $h\circ f=h\circ g$, entonces $f=g$.

Demostración

Consideremos $A$, $B$, $C$ conjuntos $f:A\to B$, $g:A\to B$, $h:B\to C$ funciones. Tomemos como hipótesis que $h$ es inyectiva y que $h\circ f=h\circ g$. Debemos probar que $f=g$.

Notemos que $f$ y $g$ tienen el mismo dominio y el mismo codominio. Veamos ahora que $f$ y $g$ tienen la misma regla de correspondencia. Sea $a\in A$, como $h\circ f=h\circ g$ tenemos que $h\circ f(a)=h\circ g(a).$

Por definición de composición lo anterior implica que:

$h(f(a))=h(g(a)),$

y al ser $h$ inyectiva:

$f(a)=g(a).$

Por lo tanto $f$ y $g$ tienen la misma regla de correspondencia.

Concluimos que $f=g$, que es lo que queríamos demostrar.

$\square$

Teorema

Sean $A$, $B$, $C$ conjuntos $f:A\to B$, $g:B\to C$, $h:B\to C$ funciones, con $f$ suprayectiva. Si $g\circ f=h\circ f$, entonces $g=h$.

Demostración

Consideremos $A$, $B$, $C$ conjuntos, $f:A\to B$, $g:B\to C$, $h:B\to C$ funciones. Supongamos que $f$ es suprayectiva y que $g\circ f=h\circ f$. Tenemos que demostrar que $g=h.$

Veamos que $g$ y $h$ tienen la misma regla de correspondencia. Para ello consideremos un elemento cualquiera de su dominio, es decir, un $b\in B.$ Como $f$ es suprayectiva sabemos que existe $a\in A$ tal que $f(a)=b$.

Además $g\circ f=h\circ f$ por hipótesis, así que $g\circ f(a)=h\circ f(a).$ Entonces por la definición de composición de funciones se tiene que:

$g(f(a))=h(f(a)).$

Pero $a$ es tal que $f(a)=b$, así que podemos reescribir lo anterior de la siguiente forma:

$g(b)=h(b).$

De este modo para cualquier $b\in B$ se tiene que $g(b)=h(b)$ y entonces $g$ y $h$ tienen la misma regla de correspondencia.

Como además $g$ y $h$ tienen el mismo dominio y el mismo codominio concluimos que $g=h$, que es lo que queríamos demostrar.

$\square$

Tarea Moral

1. En cada inciso determina si existen, y en su caso encuentra, conjuntos $A,B$ y $C$, y funciones $f$ y $g$ con las siguientes características:

i) $f:A\to B$, $g:B\to C$ tales que $f$ es inyectiva, $g$ suprayectiva pero $g\circ f$ no es inyectiva, ni suprayectiva.

ii) $f:A\to B$, $g:B\to C$ tales que $f$ es no es suprayectiva, $g$ no es inyectiva pero $g\circ f$ es biyectiva.

Más adelante

En la siguiente entrada, estudiaremos un tipo especial de relaciones: las relaciones de equivalencia. Este concepto es ampliamente utilizado en distintas áreas de las matemáticas.

Enlaces relacionados

Página principal del curso.

Enlace a la entrada anterior. Nota 11. Funciones inyectivas, suprayectivas y biyectivas.

Enlace a la entrada siguiente. Nota 13. Relación de equivalencia.