Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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\}$.
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.
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)$.
