something that looks sort of symmetrical but also not

81 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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