3
$\begingroup$

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!

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

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\}$.

$\endgroup$
1
  • $\begingroup$ Can't believe this one "escaped" me...Thanks. $\endgroup$ – José Siqueira Jul 29 '13 at 22:35
7
$\begingroup$

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.

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

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)$.

$\endgroup$
1
  • $\begingroup$ Nice one, thanks. $\endgroup$ – José Siqueira Jul 29 '13 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.