Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
You might find it easier to show (by diagonalization) that the set of functions from $\mathbb{N}$ to ${1,2,3}$ is uncountable. Since there's a bijection between $\mathbb{N}$ and $\mathbb{Q}$, this proves your result. –  Chris Eagle Jan 24 '11 at 16:39
3  
@Sivaram: Only if you are assuming CH. –  Arturo Magidin Jan 24 '11 at 16:40

5 Answers 5

up vote 7 down vote accepted

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

share|improve this answer

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).

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.