2
$\begingroup$

Prove that the set of functions $f: \mathbb{Q} \rightarrow \{1,2,3\}$ is uncountably infinite.

I'm totally stuck on this one. We have just been shown Georg Cantor's diagonalization argument in class for why $\mathbb{R}$ is uncountably infinite (and I for the most part understand it---assemble an enumeration for the reals, then proceed down the diagonal changing the number in that position to create a number that will not be on the list, since the number will differ from the i-th number in the i-th position), so I'm assuming we're going to have to assemble some sort of similar argument for this.

Anyone able to prod me in the right direction perhaps? This is homework so I'd like to not get an answer (until maybe after the deadline), but maybe a starting point or reference (which I can cite) to get me thinking about it the right way.

Thanks!

  • 3
    @Sivaram: Only if you are assuming CH.2011-01-24

5 Answers 5

7

Hint: Try to map each function to a real number, written in base-3.

6

The set of subsets of $\mathbf Q$ is uncountable and is (equivalent to) the set of functions $\mathbf Q \to \{1,2\}$, which is a subset of the set in question.

5

Use Cantor's Diagonal argument to show that set of functions $f\colon\mathbb{N}\to\{1,2,3\}$ is uncountably infinite. Then show that you have at least that many functions $\mathbb{Q}\to\{1,2,3\}$ (say, by "extending" functions).

4

We have obvious injective inclusions $2^\mathbb{N} \hookrightarrow 2^\mathbb{Q} \hookrightarrow 3^\mathbb{Q}$ and the first set - i.e. the set of functions from the positive integers to ${0,1}$, or if you will the indicator functions on $\mathbb{N}$ or the powerset of $\mathbb{N}$ - is uncountably infinite by a standard diagonal argument.

1

A slightly more direct approach:

  • Create a function g such that g(x) = 1 for all x in Q except the natural numbers.

  • Now, for contradiction, assume you can count these functions, and have them listed as f1, f2, f3, etc.

  • Set g(1) to be different from f1(1) [you have exactly two choices for g(1)]

  • In general, set g(i) to be different from fi(i)

g now maps Q to {1,2,3}, but differs from all the listed fi, since fi(i) != g(i)