Bijection between sets, whose size depends on another set.

Question

Assume that we have an arbitrary set $X$ and the a set of alphabets, $\Sigma = \{a,b,c\}$. If we define $Y$ to be the set of all the possible combinations of $\Sigma$ of length $|X|$ and $Z$ as the set of all $2$-colorings of $X$, how can we show that there is a bijection between them?

First I start with the definition of bijection: "A function is said to be bijective or have a bijection when it is both injective and surjective". Therefore first you check for injection. We know that set $Z$ depends on the size of the set $X$ and $|X|$ determines the size of $Y$. I tried to visualize this. So let's say that $X = \{10,85\}$, then we have $|X| = 2$. From $X$ we can say that if we have $2$ elements then there are $4$ ways of coloring them in $2$-colors $(|Z|=4)$, a combination of $red, blue$. From $|X|=2$ we can say that $Y=\{aa,ab,ba,bb\} \implies |Y|=2^{|X|}=4$. Therefore $|Y|=|Z|$ which means that there is a bijection between them and I don't need to show that there is an injection and surjection between them.

Is my understanding correct? Discrete mathematics is one of my worst subjects and I'm trying to take some time in the holidays to really grasp what it's all about. If you have any hints or suggestions of what I could look at to solve a problem like this, please comment!

Answer 1

Cardinality needs a notion of bijection already.

When you say that a set $X$ has $|X| = 2$, what this is implicitly saying is that there is a bijection from $X \rightarrow \{0,1\}$. So what your argument is stating is that there is a bijection from $|Y|$ to $\{1,2,3,4\}$ and a bijection from $|Z|$ to $\{1,2,3,4\}$ and thus there is a bijection from $|Y|$ to $|Z|$.

Otherwise, you could explicitly show a bijection straight from $Y$ to $Z$ to show that they have the same cardinality.

Answer 2

You're example isn't sufficient as a proof: you would need to show that this works for all sets $X$. For finite sets $X$ you could just do it by arithmetic, setting the size of $X$ as $n$ and showing that both sets have the same size via arithmetic on the natural numbers. However, I believe it is instructive to see if we can construct the bijection in a natural way.

A large part of questions like this is just interpreting what the various constructions are asking you in order to translate them into pure set theory. For instance, what is a 'colouring' of a set $X$? Well, that's just a method where I can pick out any element of $X$ and you can tell me what colour it is: i.e. it's a function $X \rightarrow \{red, blue\}$.

What's a combination from $\Sigma$ of length $|X|$? Well, 'length $|X|$' means you have a bijection between $X$ and some initial section of the natural numbers, $X \xrightarrow{\cong} \{1,2,...,|X|\}$. And then a combination from $\Sigma$ is just a method where I can ask for any give place in the sequence - say, the $n$th place - and you can tell me which element of $\Sigma$ is in the $n$th place. I.e. it's a function $\{1,2,...,|X|\} \rightarrow \Sigma$.

And, finally, you have a bijection $\{red, blue\} \xrightarrow{\cong} \Sigma$. (You can pick either one, as long as you do it consistently.

Can you use the two bijections $X \xrightarrow{\cong} \{1,2,...,|X|\}$ and $\{red, blue\} \xrightarrow{\cong} \Sigma$ to construct a method of turning functions $X \rightarrow \{red, blue\}$ into functions $\{1,2,...,|X|\} \rightarrow \Sigma$? Once you do, you can show that that method is invertible, and you have the bijection you need.