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
    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...)2012-03-22
  • 0
    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).2012-03-22
  • 0
    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.2012-03-22
  • 1
    Various questions which essentially answer this one: [this one](http://math.stackexchange.com/questions/107708) and [that one](http://math.stackexchange.com/questions/91220/) (which is a duplicate of [this one](http://math.stackexchange.com/questions/7643)) and also [this one from the front page at time of posting this question](http://math.stackexchange.com/questions/123319).2012-03-22
  • 0
    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)2012-03-22
  • 0
    Silver, in the various links on my previous comment the discussion revolves around *bijections* between the two sets. That is a function from $\mathbb Q$ to $\mathbb N$ which is injective and onto $\mathbb N$, therefore its inverse is injective and onto $\mathbb Q$.2012-03-22
  • 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
    oooooo, tricky!2012-03-22
  • 0
    @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.2012-03-23
  • 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$$