# Functions involving infinite set -> infinite set and one-to-one and/or onto

Two true or false questions:

$\mathbb{Q}^+$ means the positive rational numbers (no 0)

$\mathbb{N}$ means all natural numbers

1. Every function $f\colon \mathbb{Q}^+ \to \mathbb{N}$ is not one-to-one
2. Every function $f\colon \mathbb{N} \to \mathbb{Q}^+$ is not onto

The textbook says each of these questions are false, but doesn't explain why.

The first one kind of makes sense to me, because it seems like $\mathbb{Q}^+$ has a bigger cardinality than $\mathbb{N}$. However, if that was the case, wouldn't #2 be true? I think of $\mathbb{Q}^+$ as... infinite in two dimensions (1,2,3,4,5.... AND 1.1, 1.01, 1.001, 1.0001....).

Can anyone help me get some intuitive grasp one why these two questions are false?

-
Actually, $\mathbb{Q}^+$ has the same cardinality as $\mathbb{N}$. To show they are false, construct a function $f\colon\mathbb{Q}^+\to\mathbb{N}$ that is one-to-one, and construct a function $g\colon\mathbb{N}\to\mathbb{Q}^+$ that is onto. (HINT: If you can do one, you can do the other...) – Arturo Magidin Mar 22 '12 at 17:22
I am not sure what do you mean, both $\mathbb{Q}^+$ and $\mathbb{N}$ has cardinality $\aleph_0$ (and so, there exists a bijection, i.e. function one-to-one and onto). – dtldarek Mar 22 '12 at 17:24
Don't think of $\mathbb Q$ through decimal representations; that makes it difficult to work with the important difference between rationals and reals. Think of $\mathbb Q$ as the set of all fractions instead. – Henning Makholm Mar 22 '12 at 17:27
Various questions which essentially answer this one: this one and that one (which is a duplicate of this one) and also this one from the front page at time of posting this question. – Asaf Karagila Mar 22 '12 at 17:27
Thanks for the edit :) Can you give me an example of a function g: N->Q+ that is onto? Also, no idea what a bijection is (googling) – user13327 Mar 22 '12 at 17:28

So, they have the same cardinality. Let's rationalize this by enumerating the rationals.

Note that we can 'count' all the rationals like in this picture:

There is a small detail about removing repetition, but that's okay. Here, for example, we might count $1, 1/2, 2, 3,$ (skip $2/2$), $1/3 ,$ ...

This describes a function from $\mathbb{N} \to \mathbb{Q}^+$. In fact, it's a bijection, so it serves as a counterexample to both.

-
oooooo, tricky! – user13327 Mar 22 '12 at 17:34
@Arturo: you might note that I explicitly said to skip $2/2$. It's true that I didn't do much explicitly, but I thought it was at the appropriate level. – mixedmath Mar 23 '12 at 15:01
@mixedmath: Ooh... missed that. Sorry. – Arturo Magidin Mar 23 '12 at 15:02

The point is that ${\mathbb Q}^+$ has exactly the same cardinality as $\mathbb N$. For example, you can enumerate the members of ${\mathbb Q}^+$ by first taking those where the numerator and denominator (in lowest terms) sum to $2,3,4,\ldots$: $$1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, \ldots$$

-