Proving injectivity of a function that modifies binary strings

57 Views Asked by At

"$f : \{ 0, 1 \}^3 \rightarrow \{ 0, 1 \}^4$ is given by adding a copy of the first bit to the end of the binary string."

An example would be $f(abc) = abca$, and I am asked to prove whether or not this function is injective.

I initially considered using an "If $f(a) = f(b)$ then $a = b$" proof but this is a different kind of function so it (probably) warrants a different kind of proof.

Then I went back to the $f(abc) = abca$ example to think about this problem on a more intuitive level; are there any other inputs such that $f$ generates $abca$? How do I even prove that two binary strings are equal other than telling the reader to just look at it?

I've thought a lot about this problem but haven't been able to formulate any of my ideas into a coherent proof thus far. Any help is greatly appreciated.