[Math] Functions involving infinite set -> infinite set and one-to-one and/or onto

discrete mathematicselementary-set-theoryfunctions

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?

Best Answer

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.