1
$\begingroup$

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 ?

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

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Harald Apr 13 '15 at 5:42
  • $\begingroup$ I guess then that, for this to work, you have to use all rationals, not just those in lowest terms. $\endgroup$ – marty cohen Apr 13 '15 at 20:08
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

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