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!

  • 1
    $\begingroup$ Did you mean for the alphabet $\Sigma$ to only have two letters: $a$ and $b$? That seems to be what you are using in you're example. $\endgroup$ Jun 26, 2019 at 18:02
  • $\begingroup$ Oh yes, sorry that's a typo. $\endgroup$
    – user685004
    Jun 26, 2019 at 18:03
  • $\begingroup$ If you show the sets have the same cardinality, then by definition there is a bijection between them. $\endgroup$
    – saulspatz
    Jun 26, 2019 at 18:04
  • $\begingroup$ Yes, that's what I'm trying to show. If I argue that since the cardinality of $Y$ depends on the number of elements in $X$ and the cardinality of $Z$ also depends on the number of elements in $X$ since both their cardinalities can be expressed by $2^{|X|}$, therefore $|Y|=|Z| \implies$ bijection. $\endgroup$
    – user685004
    Jun 26, 2019 at 18:17

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

  • $\begingroup$ So you're saying that to actually prove that there is a bijection, we need a function which can take the two bijections and turn $X→\{red,blue\}$ into $\{1,2,...,|X|\}→Σ$? $\endgroup$
    – user685004
    Jun 26, 2019 at 18:42
  • $\begingroup$ Don't think of the bijections as inputs to the function: they're just tools to help us construct the bijection. You've got, as the one single input, a function $X \rightarrow \{red, blue\}$. What can you do to it to make it (more like) a function $\{1,2,...,|X|\} \rightarrow \Sigma$? $\endgroup$ Jun 26, 2019 at 18:55
  • $\begingroup$ Oh I see what you mean. Then I think that we can have $f: \to 2^{|X|}$ which take assign a color to any $\Sigma$. $\endgroup$
    – user685004
    Jun 26, 2019 at 19:17

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.

  • $\begingroup$ How would I show a bijection straight from $Y$ to $Z$? $\endgroup$
    – user685004
    Jun 26, 2019 at 18:15
  • $\begingroup$ You define a map $f$ that sends the null set to the null set, you set $\{10\}$ to $\{\text{red}\}$, $\{85\}$ to $\{\text{blue}\}$ and $\{10, 85\}$ to $\{\text{red}, \text{blue}\}$ and then check injection and surjection. $\endgroup$
    – twnly
    Jun 26, 2019 at 18:19

You must log in to answer this question.