Empezaremos por varias de la teoría de conjuntos, después pasaremos a teoría de números, después.... ¿quién sabe?
ESTA ENTRADA CONTIENE MUCHAS FÓRMULAS QUE NO CONSIGO QUE SE VEAN BIEN EN ESTE BLOG. POR ELLO ACCEDE EN ESTE ENLACE A LA MISMA ENTRADA, PERO VIENDO LAS FÓRMULAS CORRECTAMENTE
Antes de empezar, repasemos la definición de biyección
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
No hay comentarios:
Publicar un comentario
Tu opinión respetuosa con elementales normas de cortesía y convivencia, será siempre bienvenida