Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Didn't you mean mod 2? – tomasz Jun 19 '12 at 21:56
Also, what do you mean by "what are the implications"? – tomasz Jun 19 '12 at 21:59
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... – tomasz Jun 19 '12 at 22:03
@tomasz I'm on my mobile browser... And yes I did want to say mod 2 :) – idonutunderstand Jun 19 '12 at 22:06
I just saw a silver notification indicating there was a suggested edit but it said "rejected" at the bottom? – idonutunderstand Jun 19 '12 at 22:12
up vote 1 down vote accepted

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".

share|cite|improve this answer
Should your $f^{-1}$ be in quotes or something since it doesn't map 0 to anything? – idonutunderstand Jun 19 '12 at 22:38
@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$. – Ross Millikan Jun 19 '12 at 22:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.