What is $\{0,1\}^8$?

Question

1. Recall the parity-bit error detecting method, which uses the function f : B8 → B9 , where B = {0, 1}, defined by f(b1, b2, . . . , b8) = (b1, b2, . . . , b8, b9) where b9 is the sum of the previous 8 bits modulo 2:

$b_9 = 0$ if $(b_1+b_2...b_8)$ is even

$b_9 = 1$ if $(b_1+b_2...b_8)$ is odd

(a) Is f injective? Justify your answer.

(b) Is f surjective? Justify your answer.

I am having trouble trying to prove if f is injective/surjective. I don't know how to approach the question. Mostly, i'm really confused at $B^8$ where B = {0,1} as I don't know how to raise the set $\{0,1\}$ to the power of $8$

Answer 1

$B^8$ is the Cartesian product of eight copies of $B$: $B \times B \times \dots \times B$. It is the set of all sequences $(b_1, \dots, b_8)$ with all $b_i \in B$.

So, $f$ is a function that takes as argument a sequence of $8$ bits and produces a sequence of $9$ bits. The first $8$ bits of the result are the same as the argument and the $9$th bit is defined in the question.

(Hint: the way the $9$th bit is defined is irrelevant for both (a) and (b)).

Answer 2

$\{0,1\}^8=\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}=\{\langle a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8 \rangle:a_i\in \{0,1\}\}$.

This is all eight-element sequences, with the value of each element either $0$ or $1$. For example $\langle 1,0,0,1,0,0,1,1 \rangle$ and $\langle 1,0,1,1,1,0,0,1 \rangle$ belong to $\{0,1\}^8$. The sequence $\langle 1,0,1,1,1,-4,0,1 \rangle$ does not belong to $\{0,1\}^8$ since one of its elements (or coordinates), namely $-4$ does not belong to $\{0,1\}$. The sequence $\langle 1,0,1,1,1 \rangle$ does not belong to $\{0,1\}^8$ since it has only $5$ elements, not $8$, even if each element belongs to $\{0,1\}$. This sequence belongs to $\{0,1\}^5$.

You did not specify the range of the function, but I will assume that it is $\{0,1\}^9$. That is, $f$ takes a a sequence of $0$'s and $1$'s with $8$ elements, and returns a sequence of $0$'s and $1$'s with $9$ elements, where tha last element is the sum of the first eight elements $\mod2$. For example $f(\langle 1,0,1,1,1,0,0,1 \rangle)= \langle 1,0,1,1,1,0,0,1,1 \rangle$, whereas $\langle 1,1,0,0,1,1,0,0 \rangle= \langle 1,1,0,0,1,1,0,0,0 \rangle$. Notice the last coordinate of the result is $0$ if there is an even number of $1$'s in the eight element sequence at which $f$ is evaluated, and the last coordinate of the result is $1$ if there is an odd number of $1$'s in the eight element sequence at which $f$ is evaluated.

(a) $f$ is injective, since if two sequences differ at at least one of their eight coordinates, then the respective values under $f$ would differ at the same coordinate. For example, $\langle 1,0,1,1,1,0,0,1 \rangle$ and $\langle 1,0,1,1,0,0,0,1 \rangle$ differ at the $5$-th coordinate, and $f(\langle 1,0,1,1,1,0,0,1,1 \rangle)=\langle 1,0,1,1,1,0,0,1,1,0 \rangle$ and $f(\langle 1,0,1,1,0,0,0,1 \rangle)=\langle 1,0,1,1,0,0,0,1,1,1 \rangle$ also differ at the $5$th coordinate.

(b) $f$ is not surjective. For example, there is no sequence such that the result under $f$ would be the sequence $\langle 0,0,0,0,0,0,0,0,1 \rangle$. Indeed since the first eight coordinates do not change under $f$, the only choice for such a sequence would be $\langle 0,0,0,0,0,0,0,0, \rangle $. But $f(\langle 0,0,0,0,0,0,0,0 \rangle)=\langle 0,0,0,0,0,0,0,0,0 \rangle$, not $\langle 0,0,0,0,0,0,0,0,1 \rangle$.