0
$\begingroup$

Given the set $S_0$ of finite binary strings whose digit sum is congruent to 0 mod 2 and the set $S_1$ of finite binary strings whose digit sum is congruent to 1 mod 2,

what are the implications of the fact that $F: \{s_1 \in S_1 : s_1 \mbox{ends in 1} \} \to S_0$ that removes the trailing 1 from $s_1$ is onto $S_0$ but $“F^{-1}” : \{s_0 \in S_0 \} \to S_1$ that appends a 1 to the end of $s_0$ is not onto $S_1$?

  • 0
    I just saw a silver notification indicating there was a suggested edit but it said "rejected" at the bottom?2012-06-19

1 Answers 1

1

In a sense, this shows that you can add or subtract a single element from an infinite set and still have a bijection between the domain and range. This is not true for finite sets. If we allow $0 \in \mathbb N$, consider $f(x)=x+1$ on $\mathbb N$. $f$ is not onto, but $f^{-1}$ is. This is equivalent to your example, but may be less surprising. One's view of the implications can range from "trivial" to "the base of all the theory of infinite sets".

  • 1
    @AbstractionOfMe: $f^-1$ has a domain of $\mathbb N \setminus \{0\}$, it is true. It is still a fine function. This is similar to the fact that your $F$ does not have a domain of all of $S_1$, which you made explicit. It maps "half of $S_1$" onto $S_0$.2012-06-19