This is my first question on this website, so please do give me feedback where nessecary.
I got stuck on a question in Computability and Logic 5th edition by Boole i.a.
It's question 2.10 and the question is as follows:
2.10 Show that the following sets are equinumerous:
a) the set of all pairs of sets of positive integers
b) the set of all sets of pairs of positive integers
c) the set of all sets of positive integers.
It has been shown that the set of all sets of positive integers is not enumerable and since the sets in a) and b) contain more elements, these must be non-enumerable too. But I don't think that is enough to show that the sets in a), b) and c) are equinumerous.
What would prove it, is if I could find two bijections between two unequal pairs of these three sets. But I couldn't think of any.
Also, I could show that all of these three sets are equinumerous with the real numbers. For c), this was already shown in the text. a) is clearly equinumerous with R^2 and R^2 is equinumerous with R, as is explained well in this post: Examples of bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$. So a) must be equinumerous with c). But then how do I find a bijection between b) and either a) or c)?
Thanks in advance.
Best Answer
To answer your specific question "how do I biject the second set with anything", notice that there is a bijection between "pairs of positive integers" and "positive integers" given by the Cantor pairing function.
A neat way to answer the entire exercise is to provide injections a->b, b->c, c->a. Then you're done by Cantor-Schröder-Bernstein. I'll provide hints for every one of those.