Archivo de la etiqueta: conjuntos finitos

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)