Let $A$ be any set and let $C = \{0, 1, 2\}$. Denote $C^A$ the set of functions from $A$ to $C$. Find a bijection between $C^A$ and the set of all pairs $(X, Y)$ of subsets of $A$ such that $X$ is subset of $Y$.
Find a bijection
4 Answers
Each function $A\to C$ creates a partition of $A$ into three cells.
Each pair $(X,Y)$ creates a chain $X\subseteq Y\subseteq A$.
See if you can prove these two types of things are in bijection. Here is a visual aid:
$\quad$
(I imagine this just illustrates the other two three answers.) Note that the cells labelled by $1$, $2$, and $3$ may be empty, which is why we allow for $X=\emptyset$ and allow for the equalities $X=Y$ &/or $Y=A$.
-
0Very nice illustration ! – 2012-09-01
Suppose that $X$ and $Y$ are subsets of $A$ such that $X\subseteq Y$. We can use $X$ and $Y$ to split the elements of $A$ into three classes:
- Those that are in $X$ (and of course also in $Y$); these elements of $A$ are in $\color{red}2$ of the sets $X$ and $Y$.
- Those that are in $X$ but not in $Y$; these elements of $A$ are in $\color{red}1$ of the sets $X$ and $Y$.
- And those that aren’t in $Y$ (and therefore aren’t in $X$, either), and so are in $\color{red}0$ of the sets $X$ and $Y$.
Each pair $\langle X,Y\rangle$ of subsets of $A$ with $X\subseteq Y$ defines a different division of $A$ into three classes in this way. Can you see how to use the red numbers to define a function from $A$ to $\{0,1,2\}$ that can also be used to identify this particular breakdown of $A$ into three parts? And how to recover the sets $X$ and $Y$ from such a function?
I’ll stop here so as to leave you something to think about; if you get stuck, I can add more.
Any function in $C^A$ is defined by three sets - $f_0 = \{x | f(x) = 0\}$, $f_1 = \{x | f(x) = 1\}$ and $f_2 = \{x | f(x) = 2\}$. As the sets are disjoint and $f_0 \cup f_1 \cup f_2 = A$, only two of them are needed to uniquely represent a function. Take $X_f = f_1 \cup f_2$ and $Y_f = f_2$.
Let $S$ be the set of all pairs $(X, Y)$ of subsets of $A$ such that $X$ is subset of $Y$. Let $f \in C^A$. Then $(f^{-1}(\{1\}),f^{-1}(\{1, 2\})) \in S$. We define a map $\lambda\colon C^A \rightarrow S$ by $\lambda(f) = (f^{-1}(\{1\}),f^{-1}(\{1, 2\}))$.
Conversely, let $(X, Y) \in S$. Define $f \in C^A$ as follows. If $x \in X$, $f(x) = 1$. If $x \in Y - X$, $f(x) = 2$. If $x \in A - Y$, $f(x) = 0$. We denote this $f$ by $\mu((X, Y))$. Then we get a map: $\mu\colon S \rightarrow C^A$.
It's easy to see that $\lambda$ and $\mu$ are inverses of each other.