# Find a bijection

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$.

-

## 4 Answers

1. Each function $A\to C$ creates a partition of $A$ into three cells.

2. 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$.

-
Very nice illustration ! –  Georges Elencwajg Sep 1 '12 at 19:18

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.

-