Dejemos que $A$ sea un conjunto cualquiera y que $C = \{0, 1, 2\}$ . Denote $C^A$ el conjunto de funciones de $A$ a $C$ . Encuentre una biyección entre $C^A$ y el conjunto de todos los pares $(X, Y)$ de subconjuntos de $A$ tal que $X$ es un subconjunto de $Y$ .
Respuestas
¿Demasiados anuncios?
riza
Puntos
170
-
Cada función $A\to C$ crea una partición de $A$ en tres celdas.
-
Cada par $(X,Y)$ crea una cadena $X\subseteq Y\subseteq A$ .
A ver si puedes demostrar que estos dos tipos de cosas están en biyección. Aquí tienes una ayuda visual:
$\quad$ 
(Me imagino que esto sólo ilustra la otra dos tres respuestas). Obsérvese que las casillas marcadas con $1$ , $2$ y $3$ puede ser vacío por lo que permitimos $X=\emptyset$ y permitir las igualdades $X=Y$ y/o $Y=A$ .
DiGi
Puntos
1925
Supongamos que $X$ y $Y$ son subconjuntos de $A$ tal que $X\subseteq Y$ . Podemos utilizar $X$ y $Y$ para dividir los elementos de $A$ en tres clases:
- Los que están en $X$ (y por supuesto también en $Y$ ); estos elementos de $A$ están en $\color{red}2$ de los conjuntos $X$ y $Y$ .
- Los que están en $X$ pero no en $Y$ Estos elementos de $A$ están en $\color{red}1$ de los conjuntos $X$ y $Y$ .
- Y los que no están en $Y$ (y por lo tanto no están en $X$ tampoco), y por eso están en $\color{red}0$ de los conjuntos $X$ y $Y$ .
Cada par $\langle X,Y\rangle$ de subconjuntos de $A$ con $X\subseteq Y$ define una división diferente de $A$ en tres clases de esta manera. ¿Puedes ver cómo utilizar los números rojos para definir una función de $A$ a $\{0,1,2\}$ que también se puede utilizar para identificar este desglose particular de $A$ en tres partes? Y cómo recuperar los conjuntos $X$ y $Y$ de dicha función?
Me detengo aquí para dejarte algo en lo que pensar; si te atascas, puedo añadir más.
Rakesh
Puntos
108
Cualquier función en $C^A$ se define por tres conjuntos - $f_0 = \{x | f(x) = 0\}$ , $f_1 = \{x | f(x) = 1\}$ y $f_2 = \{x | f(x) = 2\}$ . Como los conjuntos son disjuntos y $f_0 \cup f_1 \cup f_2 = A$ Sólo se necesitan dos de ellos para representar una función de forma única. Tomemos $X_f = f_1 \cup f_2$ y $Y_f = f_2$ .
kubi
Puntos
20607
Dejemos que $S$ sea el conjunto de todos los pares $(X, Y)$ de subconjuntos de $A$ tal que $X$ es un subconjunto de $Y$ . Dejemos que $f \in C^A$ . Entonces $(f^{-1}(\{1\}),f^{-1}(\{1, 2\})) \in S$ . Definimos un mapa $\lambda\colon C^A \rightarrow S$ por $\lambda(f) = (f^{-1}(\{1\}),f^{-1}(\{1, 2\}))$ .
A la inversa, dejemos que $(X, Y) \in S$ . Definir $f \in C^A$ de la siguiente manera. Si $x \in X$ , $f(x) = 1$ . Si $x \in Y - X$ , $f(x) = 2$ . Si $x \in A - Y$ , $f(x) = 0$ . Denotamos esto como $f$ por $\mu((X, Y))$ . Entonces tenemos un mapa: $\mu\colon S \rightarrow C^A$ .
Es fácil ver que $\lambda$ y $\mu$ son inversos entre sí.
