Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20090121 11:33:14
CountabilityFirst I prove this: Proof: Given there exist natural numbers such that . Let be the smallest such natural number. Then If we set , then . This proves existence. For uniqueness, suppose with . (i) Suppose . Then Since is the least natural number such that we must have . a contradiction. (ii) If , then . Then , another contradiction. Hence, it must be that and ∴ . Last edited by JaneFairfax (20090121 22:21:53) #2 20090121 11:54:32
Re: CountabilityNow let , where . Then the mapping is injective, by the previous result with and , Hence is a bijection from to a subset of – proving that the positive rationals are countable. Then the negative rationals are also countable since the mapping is a bijection between and . Hence the rationals are countable. #3 20090121 22:20:55
Re: CountabilityIn fact, the mapping is a bijection. This also proves that the Cartesian product of a countable set with itself is countable. 