# How to show that the following sets are equinumerous

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

• An injection a->b: given a pair of sets of naturals, we need to make a unique set of pairs of naturals. If the two sets are known to be the same size, it's easy: just pair off the elements. But they might not be the same size; so in general you'll need to pad out one of the sets somehow. I'd recommend multiplying everything by $$2$$ so that you have infinitely many (odd) numbers with which to pad.
• Using Cantor's pairing function which I'll call $\phi$, show that the set of all sets of pairs of integers is in bijection with the set of all sets of integers. Specifically, $\{(a_1, b_1), (a_2, b_2), \dots \} \mapsto \{ \phi(a_1, b_1), \phi(a_2, b_2), \dots \}$. – Patrick Stevens Oct 21 '18 at 14:49