# Is there a bijection between $\mathbb{N}^2$ and the set of subsets of $\mathbb{N}$ with 2 elements?

I was wondering if the set $T$ of subsets of the naturals with 2 elements is countable... We know that $\mathcal{P}(\mathbb{N})$ is certainly not, but maybe this could be a countably infinite subset of it. If so, can anyone give an explicit bijection $f: \mathbb{N}^2 \to T$? Any ideas?

Thank you!

• @AWertheim Yes, but I'd like to know exactly how he could associated the ordered pairs to sets. – José Siqueira Jul 29 '13 at 22:11

## 3 Answers

A simple bijection sends $(m,n)\in\mathbb N^2$ to $\{m,m+n+1\}\in T$. This assumes $0\in\mathbb N$. If $1$ is the initial element of $\mathbb N$, then use $(m,n)\to\{m,m+n\}$.

• Can't believe this one "escaped" me...Thanks. – José Siqueira Jul 29 '13 at 22:35

Note there is a natural injection from $[\Bbb N]^2$ into $\Bbb N^2$ (the former being the set of all unordered pairs). Simply map $\{m,n\}$ to $\langle m,n\rangle$ if and only if $m<n$.

In the other direction note there is an injection from $\Bbb N^2$ into $[\Bbb N]^2$ defined by $\langle m,n\rangle\mapsto\{5,2^m3^n\}$.

Now using Cantor-Bernstein we have a bijection.

• True, thank you, was trying it the hardest way... – José Siqueira Jul 29 '13 at 22:14

One explicit bijection, avoiding having to appeal to the Bernstein-Schroeder theorem, is the function $f:[\mathbb N]^2\to\mathbb N^2$ that, for any $a\in\mathbb N$, given $n>0$, maps $\{a,a+2n\}$ to $(a,a+n)$ and, given $n\ge 0$, maps $\{a,a+2n+1\}$ to $(a+n,a)$.

• Nice one, thanks. – José Siqueira Jul 29 '13 at 22:23