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$?

  • 3
    Didn't you mean mod 2?2012-06-19
  • 1
    Also, what do you mean by "what are the implications"?2012-06-19
  • 0
    When you write or edit a post, the result is shown below. you don't need to save the edit each time to see what happens...2012-06-19
  • 0
    @tomasz I'm on my mobile browser... And yes I did want to say mod 2 :)2012-06-19
  • 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".

  • 0
    Should your $f^{-1}$ be in quotes or something since it doesn't map 0 to anything?2012-06-19
  • 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