# Trying to show that the set of all $2$-element subsets of a denumerable set is denumerable

Suppose $A$ is denumerable and put $X = \{ B : B \subset A, \; \; |B| = 2 \}$. I want to show that $X$ is denumerable as well.

My try: Let $f$ be bijection from $\mathbb{N}$ to $A$.

We know any $B \in X$ is of the form $B = \{a,b \}$ for unique $a,b \in A$. We know there exist elements $n,m \in \mathbb{N}$ such that $a = f(n)$ and $b = f(m)$.

We define $F: X \to \mathbb{N}$ by $F( \{ f(n), f(m) \} ) = 2^{f(n)}3^{f(m)}$.

To show this is injective it is enough to show that if $2^k3^r = 1$, then $k=r=1$

But I am stuck here. I mean it is obvious but how can we prove this rigorously ?

• Don't you mean $k=r=0$? – bof Apr 13 '15 at 4:23
• Too bad $A$ isn't the set of prime numbers, then you could use $\{a,b\}\mapsto ab.$ – bof Apr 13 '15 at 6:50
• Or, if you were so lucky as to have $A=\{1,2,4,8,\dots\}$, you could use $\{a,b\}\mapsto a+b.$ – bof Apr 13 '15 at 6:54
• By the way, if you want your $F$ to be well-defined, you should assume something like $n\lt m.$. – bof Apr 13 '15 at 6:55

As @YuvalFilmus mentioned,$2^k 3^r=1$ if and only if $k= r=0$.

Given $A$ is denumerable, and hence so is $A\times A$, since Cartesian product of denumerable sets is denumerable.

Now, if you notice, $X=\{\{x,y\} : x,y\in A\}$ is equivalent to a subset (say Y) of $A\times A$, removing from $A\times A$

1. $(y,x)$ if $(x,y)\in Y \forall (x,y)\in A\times A$.

2. $(x,x) \forall x\in A$

Subset of a denumerable set is denumerable. Hence X is denumerable.

Edit: continuing what you tried, to show that $F$ is injective, suppose

$F(f(n),f(m))=F(f(p),f(q))$

$\implies 2^{f(n)}3^{f(m)}$=$2^{f(p)}3^{f(q)}$.

Then $f(n)=f(p)$ and $f(m)=f(q)$ since prime factorization is unique.

Hence it is injective.

If $2^k 3^r = 1$ then $k = 0$ since otherwise $2 \mid 1$ and $r = 0$ since otherwise $3 \mid 1$.

If you can use the fact that the rationals are denumerable, use the numerators and denominators as the indices into the set.

• Not sure whether this counts as a proof. There is at least the complication that every rational counts infinitely many pairs, e.g. 3/4 also maps to 6/8, 9/12 and so on – Harald Apr 13 '15 at 5:42
• I guess then that, for this to work, you have to use all rationals, not just those in lowest terms. – marty cohen Apr 13 '15 at 20:08

Instead, simply define $$F(\{f(n),f(m)\})=2^n+2^m.$$ Suppose $$F(\{f(n),f(m)\})=F(\{f(k),f(r)\}),$$ i.e., $$2^n+2^m=2^k+2^r.$$ We may assume that $n\lt m,\$ $k\lt r,\$ and $m\le r.$

Assuming that $m\lt r,$ we have $$2^n+2^m\le2^{r-2}+2^{r-1}\lt2^r\lt2^k+2^r,$$ contradicting the assumption that $2^n+2^m=2^k+2^r.$ Hence $m=r$ and $n=k.$