(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
Enlace a la nota anterior. Nota 19. Conjuntos equivalentes y cardinalidad.
Enlace a la nota siguiente. Nota 21. Conteo, ordenaciones con repetición.