1

In the solutions, the proof begins by defining the function $f : S \rightarrow \mathbb{N}$ by $f(x,y)=x$ and goes on to show that $f$ is a one to one correspondence from $\mathbb{N}$ to $S$. However, I don't really understand why the solutions chose the function $f(x,y)=x$? How should I go about choosing a function with a one to one correspondence from $\mathbb{N}$ to the set in order to prove that the set is denumerable?

Adrian
  • 1,976

4 Answers4

2

The set in question is the graph of a function from ${\bf N}^+$ to ${\bf R}$.

In general context, whenever you have a function $f\colon X\to Y$, there's a natural bijection between the domain and the graph which is $x\mapsto (x,f(x))$ with the inverse $(x,f(x))\mapsto x$.

That those are bijections follows from the fact that they are one another's inverses (since a function is a bijection if and only if it has a left inverse which is also a right inverse).

(Furthermore, this bijection is actually a homeomorphism if $X,Y$ are topological spaces and $f$ is continuous.)

tomasz
  • 35,474
0

The inverse function (which, I agree, would have been more natural — haha) is $g\colon \Bbb N \to S$, $g(n)=\big(n,1/n\big)$.

Ted Shifrin
  • 115,160
0

If you've proved it's a bijection then you're done. So let's prove that.

First of all, it is clear that it is a surjection. This is because for any natural number $x$, we have the tuple $(x,1/x)$ which maps to $x$.

Next, we know that it is an injection. This is also apparent because if $x = y$, then $(x,1/x) = (y, 1/y)$. This is because for every natural number $x$, there is only one real number $y$ satisfying $xy = 1$.

0

Any bijection between $S$ and $\mathbb{N}$ would have worked. A set $S$ is denumerable exactly when a bijection exists between $S$ and $\mathbb{N}$—this is typically a definition of "denumerable". So when you're tasked with showing that a set $S$ is denumerable, the strategy is going to be to look for a function $f:S\to \mathbb{N}$, and then to show that $f$ is a bijection.

Functions $f: S\to \mathbb{N}$ have the nice property that they look really good in a table of values. So if you suspect that a set is countable, a good thing to start with is to make a list of the "first" few elements and see if there's a way to turn that into a well defined function for all elements in $S$. Often, figuring out the best way to list out the elements is the real trick of the proof—see the proof that $\mathbb{Q}$ is countable, for instance.

Here, once we list out a few elements, it becomes more obvious:

  1. $(1,1)$
  2. $(2,1/2)$
  3. $(3,1/3)$
  4. $(4,1/4)$
    ...

It's not hard to see on the surface that this is countable, and now the only trick is to formalize it. Notice that we can specify any element of this set just by its $x$ value—it's obvious that the only element with $x=4593$ is $(4593,1/4593)$. So $f(x,y)=x$ seems like a natural choice, although you could just as well use $f(x,y)=y$ and show that it is a bijection from $S\to \{\frac{1}{n}|n\in\mathbb{N}\}\subseteq\mathbb{Q}$, and $\mathbb{Q}$ is countable.

crf
  • 5,551