Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °
You are not logged in.
#1 2009-01-21 11:33:14
- JaneFairfax
- Legendary Member
Offline
Countability
First 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 (2009-01-21 22:21:53)
#2 2009-01-21 11:54:32
- JaneFairfax
- Legendary Member
Offline
Re: Countability
Now 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 2009-01-21 22:20:55
- JaneFairfax
- Legendary Member
Offline
Re: Countability
In fact, the mapping
is a bijection. This also proves that the Cartesian product of a countable set with itself is countable.