1

this question may seem like a duplicate of another one that I asked, but it is not. In this question, I am not allowed to use the Theorem which states: Every infinite subset of a denumerable set is denumerable.

The Problem:

Prove that $S=\{(a,b): a,b\in N, a\geq b\}$ is denumerable without using Theorem 10.4, but directly define a bijection $f:S\rightarrow N$ or $g:N\rightarrow S$.

Work: I defined a function $f: S\rightarrow N$ by $f(a,b)=a-b$. Next, I will show that such a function is injective and surjective, thereby proving that it is bijective. To prove that $f(a,b)$ is injective, I set $f(a,b)=f(x,y)$ and get$a-b=x-y$. However, from here I don't know how to prove $a=x$ and $b=y$. Maybe I need another function.

mrQWERTY
  • 595

2 Answers2

2

The canonical way to do this is to pick two distinct primes. The primes $2, 3$ are good choices. Then use $2^{a}3^{b}$. Since $2, 3$ are prime, you will have an injection. This is actually sufficient to show countability- mapping a set to $\mathbb{N}$ with an injection. It doesn't have to be onto.

I'll add more on one-to-one to address your comment about why we don't need an explicit bijection. Consider sets $A = \{a, b, c\}$ and $B = \{1, 2\}$. How many injections can we have from $A \to B$? How many injections can we have from $B \to A$? To answer these questions, it is important to understand what an injection gives us. The definition states that no two distinct elements in the domain map to the same element in the codomain. So there are no injections from $A \to B$, because at two elements would have to map to either $1$ or $2$. However, we can have an injection from $B \to A$. Why is this? It's because we can uniquely map $1$ and $2$ to elements in $A$. Injectivity from $X \to Y$ holds up to the point where $|X| = |Y|$. Otherwise, we see a case like trying to map $A \to B$. So an injective function gives us $|X| \leq |Y|$.

Here you are mapping $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$. You want to show that $|\mathbb{N} \times \mathbb{N}|$ is countable. This means that $|\mathbb{N} \times \mathbb{N}| \leq |\mathbb{N}|$. If we wanted a strict equality (ie., $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$), then we would need to show a bijection. However, an injection into $\mathbb{N}$ suffices for countability.

Does that clear things up?

ml0105
  • 14,674
  • Isn't this using the theorem the OP mentions? –  Apr 18 '14 at 03:42
  • No. Well, at least I don't think so. Theorem 10.4 isn't a theorem I'm familiar with (especially since I don't know the book he is using). I simply used the definition of countable (cardinality no bigger than $\mathbb{N}$), and the fact that an injection from $S \to \mathbb{N}$ gives $|S| \leq |\mathbb{N}|$. But the bijection counting rule he mentioned uses this anyways. So if I'm using anything potentially off-limits, it would be the primality. If this is the case, I hope the OP mentions something and I'll be happy to rework my example. – ml0105 Apr 18 '14 at 03:45
  • Hi, I don't think this uses the Theorem so I think that this is good. – mrQWERTY Apr 18 '14 at 03:53
  • Hi, I don't quite understand why it does not have to be onto. I think my textbook says that for N and NxN to be numerically equivalent, there has to be a bijective function from N to NxN or vice versa. Sorry if I don't make sense, I just began learning the subject recently. – mrQWERTY Apr 18 '14 at 18:57
  • I've edited my post. I hope this clears things up some. – ml0105 Apr 18 '14 at 20:56
1

Your function is not injective since $f(a,a)=0$ for all $a\in N$.

You may want to try with $f:S\to N$ defined by $f(a,b)=\dfrac{a(a+1)}{2}+b$.

  • Thanks, but how would I prove that it is injective. I don't know how to show a=x and b=y for instance. – mrQWERTY Apr 18 '14 at 03:33
  • Suppose $f(a,b)=f(x,y)$. If $a=x$, then $b=y$ and we're done. Assume $a<x$ and recall $\frac{a(a+1)}{2}=1+2+\cdots +a$. We have $$\dfrac{a(a+1)}{2}+b=\dfrac{x(x+1)}{2}+y\implies b=(a+1)+(a+2)+\cdots +x+y,$$ but this is not possible since $b\le a$. –  Apr 18 '14 at 03:47
  • Wow, thanks. That was a great way of proving it. – mrQWERTY Apr 18 '14 at 03:55
  • @Froggy You're welcome. –  Apr 18 '14 at 03:57