Qustion: Determine whether f is a function from the set of all bit strings to the set of integers if
(a) f(S) is the position of a 0 bit in S.
(b) f(S) is the number of 1 bits in S.
(c) f(S) is the smallest integer i such that the ith bit of S is 1 and f(S) = 0 when S is the empty string, the string with no bits.
I did managed to solve this, but the similar solutions for all three questions make me quite unsure about my responses.
The following are my approaches:
(a) f(S) is either a surjective or onto function, as there always is an integer matching with the location of 0 in a bit string, and 0s may have same locations despite the overall bit string being different. Though, it's unsure whether all integers will having a matching value. It is still a function as it is a surjection.
(b) f(S) is either a surjective or onto function, as there always is an integer matching with the number of 1 bits in a bit string, and different bit strings may share the same number of 1 bits. Though, is unsure whether all integers will have a matching value. It is still a function as it is a surjection.
(c) f(S) is either a surjective or onto function, as there always is an integer matching with the "earliest" location of 1 bit in a string, and different bit strings may contain the "earliest" 1 bit on the same location. Though, it is unsure whether all integers will have a matching value. It is still a function as it is a surjection.
All questions seem to have similar responses with a slightly different supporting reason. Did I make a correct approach? What is the proper way of solution, and how should I correct my errors?
Best Answer
No, in (a), $f$ is not a function. We expect a function $f : A \to B$ to be a subset of $A \times B$ (also known as a relation between $A$ and $B$) that satisfies two conditions:
When both the above conditions hold, we can use function notation. Instead of writing $(a, b) \in f$, we can write $f(a) = b$ instead. The first condition means that $f(a)$ always means something when $a$ lies in the domain $A$. The second condition means that $f(a)$ means only one thing, so it's valid to conclude that if $f(a) = b$ and $f(a) = b'$, then $b$ and $b'$ are the same thing.
In part (a), you do not have a well-defined function from the set of bitstrings (let's assume they are finite in length, just for the sake of clarity) to the set of integers. Indeed, both conditions are violated. Condition 1 is violated, as $f(1111)$ has no value; $0$ does not appear in any position of $1111$, so $f(1111)$ has no value according to the given definition.
Condition $2$ is violated too, as $f(010)$ has multiple values. We would have $f(010) = 1$ and $f(010) = 3$. Both $1$ and $3$ are positions in $010$ that contain $0$s, so the definition given of $f$ does not produce a unique value. Our $f$ is not well-defined.
Either reason alone would be sufficient to conclude $f$ is not a function. Compare and contrast with part (c), which is much like part (a), except dealing with $1$s instead, and also dealing with the above problems. By choosing the earliest instance of a $1$, we avoid the problems with the second case. Instead of $f(101)$ having two values $1$ and $3$, it now just has the value $1$. Also, by defining $f(S)$ to have the value $0$ when $S$ has no $1$s, it deals with the problems of the first case, so that $f(S)$ always has a value. That's why $f$ is a function in case (c).
Part (b) is also a function, indeed for the reason that "there always is an integer matching with the number of $1$ bits in a bit string". That satisfies the first property. It's also worth noting that this number is unique (you can't have, for example $1$ and $5$ instances of $1$ in your string!). That satisfies the second property. This makes (b) a function.
Finally, I just want to talk about surjections. Given the functions above are defined to the set of integers (including negative integers), and there is no way for these functions to take negative values, the functions are not surjections.