Biyecciones
En esta entrada estudio varias biyecciones entre conjuntos que aparecen en diferentes partes de las matemáticas.
Empezaremos por varias de la teoría de conjuntos, después pasaremos a teoría de números, después.... ¿quién sabe?
Empezamos:
PRIMER EJEMPLO:
Sea $$ N_k = \{ 1,2,...,k \} $$ Define una biyección de $$ N_k \times N_l $$ a $$ N_{kl} $$
Respuesta: Estudiamos un caso sencillo para obtener por abstracción o generalización una fórmula que valga en general:
Vamos a estudiar la biyección entre $$ N_2 \times N_3 $$ y $$ N_6 $$
Llamamos f a la biyección que vamos a establecer
f(1,1)=1 f(2,1)=4
f(1,2)=2 f(2,2)=5
f(1,3)=3 f(2,3)=6
Hay que fijarse en que la imagen del par $$(m,n) $$ la obtengo sumando a n el producto $$(m-1) \cdot 3 $$
Así la imagen de $$(1,2)$$ es $$ 2+(1-1) \cdot 3 = 2+ 0 \cdot 3 =2+0=2
$$ y la imagen $$ (2,1) $$ es $$ 1+ (2-1) \cdot 3 = 1+1 \cdot 3 =1+3 =4
$$
En el caso general que aparece en el enunciado, tenemos que hallar la
imagen de un par cualquiera $$ (m,n) $$ donde m varía entre 1 y k y en
cambio n varía entre 1 y l, es decir $$1 \leq m \leq k $$ y $$ 1 \leq n
\leq l $$
Entonces la imagen de $$(m,n)$$ se obtiene sumando a n el producto de $$
m-1 $$ por $$ l $$, Por tanto la fórmula de la biyección sería $$f(m,n)
= n+(m-1) \cdot l $$
Para comprobar que no nos hemos equivocado hallaremos la imagen de (1,1)
, que debe ser 1 y la imagen de (k,l) que debe ser $$ k \cdot l $$
Vamos a verlo:
$$ f(1,1) = 1+ (1-1) \cdot k = 1 +0 \cdot l = 1+0 =1 $$
$$ f(k,l) = l+(k-1) \cdot l = l+k \cdot l - 1 \cdot l = l+ k \cdot l -l = k \cdot l $$
¡Sale bien!
Para ver que la aplicación es inyectiva, supongamos que $$ f (m_1 , n_1 )
= f (m_2 , n_2 ) $$ Vamos a probar que $$ (m_1 , n_1) = (m_2 , n_2 ) $$
es decir, $$ m_1 = m_2 $$ y $$n_1 = n_2 $$
Suponiendo que $$ f (m_1 , n_1 ) = f (m_2 , n_2 ) $$ entonces $$ n_1 +
(m_1 -1) \cdot l = n_2 + (m_2 -1) \cdot l $$. De ahí deduzco que $$ n_1 -
n_2 = (m_2 -m_1) \cdot l $$
Esto quiere decir que $$ n_2 - n_1 $$ es múltiplo de $$ l $$
Pero tanto $$ n_1$$ como $n_2$ son números comprendidos entre $$1$$ y
$$l$$, su diferencia también, y la única manera de que esa diferencia
sea múltplo de $$l$$ es que sea igual a $$0$$
Imponiendo a la fórmula esta condición $$n_1 = n_2$$ llegamos a $$m_1 = m_2$$
Ahora, para ver que es sobre, partimos de un número $$t$$ comprendido entre $$1$$ y $$k \cdot l $$
Al dividir $$t$$ entre $$l$$ entonces obtenemos un cociente $$q$$ y un resto $$r$$. La antiimagen de t es $$ (q+1, r)$$ .
Imaginemos que estamos trabajando la biyección $$ N_8 \times N_6 \rightarrow N_{48} $$
Así por ejemplo, la antiimagen de 40 es (40 entre 6 da cociente 6 y resto 4) Por tanto la antiimagen es (7,4)
Para comprobar, hallamos la imagen de (7,4) es 4+(7-1)6 = 4+36=40
Colorín colorado, este razonamiento se ha acabado.
Pero si notáis algún fallo o algún paso que no comprendéis, rápido, a reflejarlo en los comentarios.
SEGUNDO EJEMPLO
El conjunto potencia de un conjunto X, que se representa $$2^X$$ es el
conjunto cuyos elementos son los subconjuntos de X, en símbolos $$ 2^X =
\{S/ S \subseteq X \} $$ . Prueba que no existe ninguna biyección $$
f:: X \longrightarrow 2^X $$
La prueba de esta afirmación es muy bonita porque se parece a la paradoja del barbero (http://es.wikipedia.org/wiki/Paradoja_de_Russell, http://www.taringa.net/posts/ciencia-educacion/8258710/La-paradoja-del-barbero-teoria-de-conjuntos.html, http://es.wikipedia.org/wiki/Metamatem%C3%A1tica, http://thales.cica.es/rd/Recursos/rd97/Biografias/17-1-b-paradoja.html)
Se trata de una demostración por reducción al absurdo: supongamos que existe una biyección $$ f:: X \longrightarrow 2^X $$
Entonces habrá elementos $$x \in X $$ tales que se cumpla $$ x \in f(x) $$ y otros para lo cuales $$ x \notin f(x) $$
Veremos que al menos existe un $$x \in X $ tal que $ x \notin f(x) $$
En realidad esa última afirmación es lo que en matemáticas se conoce
como Lema: una afirmación que se demuestra, pero cuya importancia no
radica en lo que afirma, sino en que se aplica para probar alguna otra
afirmación. Es lo que se llama un resultado auxiliar. Así si expresamos
más formalmente lo que llevamos dicho escribiremos:
Teorema: no existe biyección $$ f:: X \longrightarrow 2^X $$ para cualquier conjunto $$ X $$
Lema: Si existiese una biyección f entre los conjuntos $$ X $ y $ 2^X $$
entonces existe algún elemento $$ x \in X $$ tal que $$ x \notin f(x)
$$
La prueba de este lema es muy sencilla: como $$ \emptyset $$ es un
subconjunto de X, es imagen por f de algún elemento $$x \in X $$. Ese
elemento cumple $$x \notin f(x) = \emptyset $$ Esto prueba el lema.
(Por otra parte, si X contiene dos o más elementos diferentes, entonces
como f es biyección, existe x en X tal que f(x) contiene al menos otro
elemento diferente y , es decir $$ f(x) \neq \{ x \} $$ . Ahora bien el
conjunto $$ \{x \} $$ es imagen de algún $$ z \in X $$ y se cumple $$ z
\notin f(z) = \{ x \} $$ )
Ahora continuamos razonando para demostrar el teorema.
Recordamos que estamos razonando por reducción al absurdo, suponiendo que existe una biyección $$ f:: X \longrightarrow 2^X $$
Formamos el conjunto $$S = \{x \in X / x \notin f(x) \} $$
Por el Lema anterior, $$ S \neq \emptyset $$
Como S es un subconjunto de X, existe $$ s \in X $$ tal que $$ f(s) = S $$
Nos planteamos si s pertenece o no a f(s) = S
si s pertenece a S=f(s) entonces por la propia definición de S se tiene
que $$ s \notin S$$ Pero si s no pertenece a S, según la definición de S
debe cumplirse $$ s \in S $$
Eso es una contradicción, a la que hemos llegado suponiendo que existe
la aplicación biyectiva entre X y el conjunto de las partes de X. Por
tanto no existe tal biyección.
Y colorín colorado, la prueba se ha acabado.
NOTA: en el transcurso de la demostración descartamos que $$S =
\emptyset $$. Pero si ocurre todo lo contrario, $$ S = X $$ todos los
argumentos siguen siendo válidos.
TERCER EJEMPLO
Sea $ N_k =\{1,2,...,k\}$. Establece una biyección entre el conjunto de
las partes de $N_k$ que se representa $ 2^{N_k}$ (o bien $\textit{P}$)
y $ N_{2^k}$
RESPUESTA:
No pude resolver este problema, así que recurrí al foro de matemáticas,
donde obtuve la respuesta de Carlos Ivorra, que puede encontrarse en este enlace
Encontré la solución fascinante porque jamás se me hubiera ocurrido y sin embargo tenía un par de indicios, que comentaré.
Ahora vamos con la demostración. Intentaré elaborar la prueba de la respuesta que recibí completando los detalles.
La biyección $ f:: 2^{N_k} \rightarrow N_{2^k}$ está dada por $ f(\{n_1 ,
n_2 ,..., n_m \} = 2^{n_1 -1} + 2^{n_2 -1} + ... + 2^{n_m -1} $
(donde $1 \leq n_1 < n_2 < ...< n_m \leq k $ )
Así por ejemplo si k=10 entonces $ N_{10} = \{ 1,2,3,4,5,6,7,8,9,10 \} $
la imagen de $ \{1,2,7,9 \} $ es $ 2^0 + 2^1 + 2^6 + 2^8 = 1+2+64+256 =
323 $ Observemos que $ 323 = 101000011_{(2} $
Esta idea nos permite encontrar la antiimagen cualquier $k$ comprendido
entre 1 y $2^{10}$. Lo que hacemos es pasar el número a base dos, y
sumando uno a los exponentes de 2, encontramos el subconjunto
antiimagen. Por ejemplo, para hallar la antiimagen de 200, paso 200 a
base dos, obteniendo $ 200= 11001000_{(2} = 2^7 + 2^6 + 2^3 $
Por tanto la antiimagen de 200 es el subconjunto $ \{ 4, 7, 8 \} $
Ahora es fácil dar una prueba de que la aplicación que hemos definido es una biyección
Probemos que es sobre. Sea t un número cualquiera de $ N_{2^k} $
Entonces lo expreso en base dos, obteniendo $ t= 2^{n_1} + 2^{n_2} + ...
+ 2^{n_m} $ con $ 0 \leq n_1 < n_2 < .... < n_m \leq k-1 $
El subconjunto de $ N_{2^k} $ $ S_t = \{ n_1 +1, n_2 +1, .... , n_m +1 \} $ es la antiimagen de t
Como, todo número puede expresarse de una única manera en base 2, entonces la antiimagen existe y es única.
Para ver que es inyectiva imaginemos que $ f(\{n_1 , n_2 ,..., n_m \}) = f(\{r_1 , r_2 ,...,r_p \}) $
Entonces $ 2^{n_1 -1} + 2^{n_2 -1} + ... + 2^{n_m -1} = 2^{r_1 -1} +
2^{rr_2 -1} + ... + 2^{r_p -1} $ y como la expresión en base dos de
cualquier número es única, los exponentes son iguales, y por tanto los
conjuntos coinciden
FIN DE LA PRUEBA
¿Cuales eran los indicios de que hablé antes?
Cuando se demuestra que el conjunto de las partes de un conjunto de k
elementos tiene $ 2^k $ elementos, se razona de la siguiente manera: el
primer elemento del conjunto puede pertenecer o no a un subconjunto
arbitrario, lo cual me da dos posibilidades. El segundo elemento también
puede pertenecer o no, lo cual me da $ 2 \cdot 2 = 4 $ posibilidades.
Si razono igual para todos lo elementos, obtengo $ 2 . 2
. \underbrace{......}_{k veces} ... 2 = 2^k $
Por eso podría haber sospechado que se puede asociar a cada subconjunto
un número en base 2, poniendo 0 en el lugar que corresponde a un
elemento concreto que no esté y uno cuando sí esté
CUARTO EJEMPLO
Se trata de probar que es biyectiva 
dada por 
+n
Tampoco fuí capaz de resolver este problema y recurrí al foro La respuesta que encontré está en este enlace
Fue
una respuesta de Carlos Ivorra, que no sólo demostraba la cuestión,
sino que la relacionaba con la prueba "clásica" de que $ N \times N $ es
numerable
COMENTARIO (antes de la prueba)
Antes de pasar a la prueba, diré un par de cosillas.
Yo conocía la prueba de que $ N \times N $ es numerable. Puede encontrarse aquí, aunque en inglés la prueba que consiste en escribir los pares de $ N \times N $ en un cuadro que ordenamos según sus diagonales
(1,1) (1,2) (1,3) (1,4) (1,5) ....
(2,1) (2,2) (2,3) 2,4) (2,5) ....
(3,1) (3,2) (3,3).... ... ....
(4,1) (4,2) (4.3).... ... ....
(5,1) .... .... .... ... ....
..
..
..
.
.
.
.
Primera diagonal: (1,1)
Segunda diagonal (2,1), (1,2)
Tercera diagonal (3,1) (2,2) (1,3)
Cuarta diagonal (4,1) (3,2) (2,3) (1,4)
y así sucesivamente.
De esta forma puedo ordenar todos los pares y establecer así la
biyección: a cada par le corresponde el número que indica el lugar que
ocupa en esta ordenación y viceversa.
A veces me había preguntado si se podría dar con una fórmula explícita para esta biyección ¡y resulta que es ésta!
Tengo que decir antes de continuar, que hay varias maneras de probar que
$ N \times N $ es numerable y que el asunto también se trató en el foro
de matemáticas aquí
Bueno, pues ahora veamos como se comprueba esto y después la prueba.
Copio parte de la respuesta de Carlos Ivorra en el foro de matemáticas:
La idea de fondo se ve al considerar los pares de números naturales así:
(Hay que tener en cuenta que en la respuesta del foro de matemáticas,
Carlos Ivorra considera al 0 como parte de los naturales, lo cual
simplifica los cálculos. Se requieren modificaciones relativamente
"leves", aunque molestas, para rehacer el razonamiento empezando con 1)
Si los numeras diagonalmente, empezando por 
, luego 
, luego 
, etc., entonces la primera diagonal está formada por todos los pares con 
, la segunda tiene los pares con 
, la tercera los pares con 
, etc.
Luego, dado un par cualquiera 
, aparecerá en la diagonal 
, y el número de pares en las diagonales anteriores es
( Aquí 
)
y, dentro de su diagonal, ocupa el lugar 
(empezando a contar en 0) luego se trata del par 
-simo de la enumeración.
Por lo tanto, la función 
enumera biunívocamente todos los pares de números naturales.
En
nuestro problema, el cuadro empieza en (1,1) y cualquier par (m,n) está
en una diagonal que deja por detrás m+n-2 diagonales ya completadas y
el número de pares que contienen esas diagonales enteras es $ 1+2+3+...+
m+n-2 = \frac {(m+n-2)(m+n-1)}{2} $
Como
dentro de la diagonal en la que está, el par (m,n) ocupa el lugar n, ya
que (m+n-1,1) es el primero, (m+n-2, 2) es el segundo.... ....
(m+n-n,n), es decir (m,n) es el nésimo.
Por tanto la fórmula que nos da el lugar que ocupa el par (m,n) es $ f(m,n) = n+\frac{(m+n-2)(m+n-1)}{2} $
Con este razonamiento me basta.
Un razonamiento más técnico estaba, al igual que este, en la respuesta del foro de matemáticas, que copio a continuación:
es inyectiva.
Puedes adaptarlo para el caso en que se extirpa el cero de los números naturales.
Considera la función . Como es estrictamente creciente (en particular inyectiva) y 
, para cada número natural 
existe un único 
tal que 
.
Considera la aplicación 
que a cada le asigna ese único , de modo que si se cumple entonces 
.
, luego 
Por lo tanto, si 
, entonces 
, luego 
, luego 
.
Como tenemos que 
, esto implica que 
, luego 
.
HASTA AQUÍ LA RESPUESTA DEL FORO DE MATEMÁTICAS
Si quiero adaptarlo al caso en que no consideramos el cero como número
natural. Tenemos que considerar la función $ p: N-\{2\} \rightarrow N $
definida por $ p(z) = \frac{(z-2)(z-1)}{2} $ de manera que ahora $
p(m+m) = \frac{(m+n-2)(m+n-1)}{2} $ y tenemos $ f(m,n) = p(m+n) + n $
Como p es estrictamente creciente y $p(2)=0$ entonces para cada número
natural mayr o igual que 2, x existe un úmico número natural z tal que $
p(z) \leq x \leq p(z+1) $. Definimos h como la función que a cada
número natural mayor o igual que 2 le hace corresponder el único z tal
que $ p(z) \leq x \leq p(z+1) $.
Y seguimos igual que antes, en la respuesta del foro de matemáticas copiada parcialmente más arriba.
QUINTO EJEMPLO
Una vez más, utilizaremos el foro de matemáticas. No comentaré nada, sólo pondré el enlace a un hilo sobre biyecciones: http://rinconmatematico.com/foros/index.php?topic=5576.20
CONTINUARÁ
TO BE CONTINUED
Comentarios
Publicar un comentario
Los comentarios son bienvenidos siempre que sean respetuosos y corteses y traten del asunto de la entrada.
Dirige un correo a martinjaime80@hotmail.com informando de que deseas publicar un comentario