Prove,that there exists bijection between the sets $\{0,1\}^$ and $\{0,1,2\}^$

Question

Should I show, that both of the sets are countable by mapping initial words to natural numbers?

Yes, demonstrating that each is countably infinite is a very reasonably approach. — Brian M. Scott, Feb 05 '21 at 07:33

score 2 · Accepted Answer · answered Feb 05 '21 at 07:39

There are several ways to show that, with different "pre-requisites".

One first idea is to actually explicit a bijection between the two sets. This is somewhat tedious.

Another idea is to find another set - e.g. $\mathbb N$ - which is in bijection with your two sets. Depending on how you prove that $\mathbb N$ and $\{0, 1\}^\ast$ are in bijection, this might lead to an "un-constructive" proof, meaning that you will know that some bijection exists, but with no way of actually computing it explicitly.

Finally, you can also use various theorems and find:

An injection and a surjection from one set to the other.
Two injections (one in each sense)

Both of these will give the existence of a bijection between the two sets.

To be fair, the simplest way would be to show that they are both countable, and claim that this is enough to guarantee the existence of a bijection between the two sets.

Prove,that there exists bijection between the sets $\{0,1\}^*$ and $\{0,1,2\}^*$

1 Answers1

Prove,that there exists bijection between the sets $\{0,1\}^$ and $\{0,1,2\}^$