I am working on showing a bijection between two sets: $B^6$ and $E_{10}$.
Here is the problem:
Let $B = {0, 1}$. $B^n$ is the set of binary strings with $n$ bits. Define the set $E_n$ to be the set of binary strings with $n$ bits that have an even number of 1's. Note that zero is an even number, so a string with zero 1's (i.e., a string that is all 0's) has an even number of 1's.
Show a bijection between $B^9$ and $E_{10}$. Explain why your function is a bijection.
Here is my answer:
Suppose $x \in B^9$. We know an odd number is the result of an even number plus an odd number. Since there are only 9 digits for each $x \in B^9$, and 9 is an odd number, this means that if there are an odd number of 1’s in x then there will be an even number of 0’s in x. Further, if there are an even number of 1’s in x then there will be an odd number of 0’s in x. Therefore, each $x \in B^9$ will have either an odd or even amount of 1’s.
We could write a function f to say that if x has an odd number of 1’s, then append a 1, which would give us an even number of 1’s. We could also say that if x has an even number of 1’s than append a 0, which would then keep the number of 1’s even.
Assuming each $x \in B^9$ is unique, according to our function we will be adding either a 1 or a 0 to the end of the string, which would produce a new unique string with 10 bits. For example, $f(100011000)=1000110001$. This means that the function is injective (one-to-one) function because each element in the domain is mapped to 1 distinct element in the codomain.
We can also have an inverse function $f^{-1}$ which removes the last binary digit from each $y \in E_{10}$. $E_{10}$ is defined to be the set where each element from $B^9$ has a 1 or 0 appended to it, and thus producing a distinct element. Removing the end 1 or 0 from this new string produces the distinct unique element that was in $B^9$. For example, $f^{-1}(1000110001)=100011000$. This means each element in $E_{10}$ can be mapped to at least one unique $x \in B^9$, meaning the function is onto
Since the function is both one-to-one and onto, then it is a bijection.
I feel like there is a much simpler way of showing this, and not really sure if I made a good case in the first place. I was hoping someone could provide a different way to think about this problem or provide some insight so that I can formulate a better answer.
Thank you all so much!
Best Answer
Your method is the simplest way of showing the bijection, but the wording can be drastically simplified. The function from $B^9$ to $E^{10}$ adds a parity bit to the word from $B^9$, while the inverse transformation removes it.