>>185874435Obviously it's enough to prove that the third set is uncountable, because it is a subset of each of the other ones. We define a set of functions s_Q, where Q is a (possibly infinite) set of integers, through the relations:

s_Q (2i) = 2i+1 and s_Q (2i+1) = 2i for all i in Q

s_Q (i) = i otherwise

Effectively, s_Q flips 2i and 2i+1 for all the i in Q. All these functions are clearly bijections (even more, they're involutions), and since Q can be an arbitrary set of integers, the cardinality of the set of s_Q is the same as that of the power set of N (which is uncountable).

QED