Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.