0
$\begingroup$

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?

  • 0
    Ahhhh, ok thank you very much2012-03-22

2 Answers 2

0

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:

enter image description here

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.

  • 0
    @mixedmath: Ooh... missed that. Sorry.2012-03-23
0

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$