1. Other
  2. Other
  3. theorem 1411 i the set q is countable ii the...

Question: theorem 1411 i the set q is countable ii the...

Question details

Theorem 1.4.11. (i) The set Q is countable. (ii) The set R is uncountable. Proof (i) For each n є N, let An be the set given by An- : where p,0€ N are in lowest terms with p+ q-n The first few of these sets look like 1-1 2 -2 A4,-,-,-,ー>, 3 31 1 and A,-,-,-,-,-,-,-,-, 4 4 33 2 2 1 1 The crucial observation is that each An is finite and every rational number appears in exactly one of these sets. Our 1-1 correspondence with N is then achieved by consecutively listing the elements in each An N: 1 23 45 6 78910 11 12 .- 1 2 3 1 3 Admittedly, writing an explicit formula for this correspondence would be an awkward task, and attempting to do so is not the best use of time. What matters is that we see why every rational number appears in the correspondence exactly once. Given, say, 22/7, we have that 22/7 E A29. Because the set of elements in Ai,... ,A2s is finite, we can be confident that 22/7 eventually gets included in the sequence. The fact that this line of reasoning applies to any rational number p/q is our proof that the correspondence is onto. To verify that it is 1-1, we observe that the sets An were constructed to be disjoint so that no rational number appears twice. This completes the proof of (i)2. In the proof of theorem 1.4.11 (i), we use that each set An is finite. Find an upper bound for the number of elements in each An. (Some notation: we use A, to denote the number of elements of a set, so 2,4,6,8, 10 5. We want some number (possibly in terms of n) so that An! 〈 this number. Such a bound guarantees that An is finite for each n 3. We know from part (i) that the rational numbers, Q, are countable, so that there is a way to list all of the rationals numbers in an infinite list ri,T2,r3, ...^. What happens if we go through the proof of theorem 1.4.11 part (ii) using the rational numbers instead of the real numbers? Why does this not produce a proof that the rationals are uncountable? 4. Let X,-In, n +1,n + 2,...^ C N. Give two proofs that for each n, X, is countable; one direct proof (i.e. build a 1-1 and onto function), and one using theorems from the chapter. 5. Let Q+ be the set of positive rational numbers. Prove that is countable.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution