How to show that the following sets are equinumerous

Question

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.

Answer 1

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.

• 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.
• An injection b->c: given a set of pairs of naturals, you need to make a unique set of naturals. That one's very easy by a standard trick (hint: tag each member of your set of naturals with which set it came from, by using evenness and oddness).
• An injection c->a: given a set of naturals, you need to make a unique pair of sets of naturals. That one's the easiest, and you need to do no work at all for this.