(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 el número de elementos del producto cartesiano de dos conjuntos finitos (ver nota 6) es igual al producto del número de elementos de cada conjunto. Así mismo, probaremos que para una función entre conjuntos finitos de la misma cardinalidad, las nociones de ser inyectiva, suprayectiva o biyectiva son equivalentes.
Empecemos probando un lema que nos ayudará a probar el principio del producto.
Lema 1
Sean $A$ un conjunto finito y $\{b\}$ un conjunto unitario, entonces $A\times \set{b}$ es finito y $\# (A\times \set{b})=\#A$.
Demostración
Sean $A$ un conjunto finito y $\{b\}$ un conjunto unitario, con $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 lo 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})$ es un conjunto finito con $\# (A\times \set{b})=n$. 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 con $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$.
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 obtenemos que:
$\#(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$ y $B$ es finito, entonces $Imf$ también es finito y $ \#Imf\leq \#B$ (ver la nota anterior), 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 inyectiva.
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 menor o igual número de elementos que 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 con $\#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 un ejercicio de la nota anterior sabemos que $Imf=B$. Por lo tanto $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. Considera que para acceder a una aplicación se requiere una contraseña de tres dígitos que pueden ser $0,1,2,3,4,5,6,7,8$ o $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 posibles hay?
iii) Si ahora la contraseña puede ser de tres o de cuatro dígitos ¿cuántas contraseñas habrá?
3. Ve el siguiente vídeo para que conozcas otro importante principio de conteo, el principio del palomar.
Más adelante
En las siguientes notas haremos énfasis en el estudio de las técnicas de conteo. Estudiaremos las ordenaciones, las ordenaciones con repetición y las combinaciones.
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.