I have the following problem:
How can I solve this problem, I have no clue.
Of course I know the properties of an bijection and I belief I have to use the induction to solve this, because we have an finite set , and this smells like induction for me. But the main problem is, that I do not know how to write it down mathematically correct. A professor told me, that I should copy as many proofs I can, and the understanding will come, hope so.
P.S. This is no homework, its only an old problem from a test paper
P.P.S. I'm not a real student yet, just very interested, hope this is not a reason for not helping:)
Best regards
Justin
Let $\Bbb{A}_n$ be the set of possible bichromatic colorations of $A$ with $|A|=n$, and $\Bbb{B}_n$ the set of binary numbers of lenght $n$. Let's call the colours $c_1$ and $c_0$. We can create a function from $\Bbb{A}_n$ to $\Bbb{B}_n$:
$$f: \Bbb{A}_n \to \Bbb{B}_n $$
Clearly:
$$a \in \Bbb{A}_n \iff a=\{c_{i_1},...,c_{i_n}\} \ \ \ {i_j}=0,1 \ \ \forall j $$ $$b \in \Bbb{B}_n \iff a=\{{i_1},...,{i_n}\} \ \ \ {i_j}=0,1 \ \ \forall j $$
So we can construct $f$ this way:
$$f(\{c_{i_1},...,c_{i_n}\})=\{{i_1},...,{i_n}\}$$
Suppose for absurd that this function wasn't injective. This means that there exist two colorations $\{c_{i_1},...,c_{i_n}\} , \{c_{k_1},...,c_{i_n}\}$ with $i_1 \neq k_1 $ such that:
$$f(\{c_{i_1},...,c_{i_n}\})=\{{i_1},...,{i_n}\}$$ $$f(\{c_{k_1},...,c_{i_n}\})=\{{i_1},...,{i_n}\}$$
But for the construction of the function:
$$f(\{c_{k_1},...,c_{i_n}\})=\{{k_1},...,{i_n}\}$$
So: $$\{{k_1},...,{i_n}\}=\{{i_1},...,{i_n}\}$$
But this means that $k_1=i_1$ and this is absurd. Since $f$ is injective and $|\Bbb{A}_n|=|\Bbb{B}_n|=2^n$ , $f$ is also surjective. So $f$ is a bijection.
:)