Using the bijection rule to count binary strings with even parity.

Let B = {0, 1}. Bn is the set of binary strings with n bits. Define the set En 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.

(a) Show a bijection between B9 and E10. Explain why your function is a bijection.

Lets denote c the concatenation of strings. For a binary string a in B9, we define the element f (a) in E10 this way:

f (a) = a c {1} if a has an odd number of 1's f (a) = a c {0} if a has an even number of 1's

Step-by-step explanation:

To show that the function f defined above is a bijective function, we need to prove that f is well defined, injective and surjective.

f is well defined:

To see this, we need to show that f sends elements fromo b9 to elements of E10. first note that f (a) has 1 more binary integer than a, thus, it has 10. if a has an even number of 1's, then f (a) also has an even number because a 0 was added. On the other hand, if a has an odd number of 1's, then f (a) has one more 1, as a consecuence it will have an even number of 1's. This shows that, independently of the case, f (a) is an element of E10. Thus, f is well defined.

f is injective (or one on one):

If a and b are 2 different binary strings, then f (a) and f (b) will also be different because the first 9 elements of f (a) form a and the first elements of f (b) form b, thus f (a) is different from f (b). This proves that f in injective.

f is surjective:

Let y be an element of E10, Let x be the first 9 elements of y, then f (x) = y:

If x has an even number of 1's, then the last digit of y has to be 0, and f (x) = x c {0} = y If x has an odd number of 1's, then the last digit of y has to be a 1, otherwise it wont be an element of E10, and f (x) = x c {1} = y

This shows that f is well defined from B9 to E10, injective, and surjective, thus it is a bijection.