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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

First I prove this:

Proof:

Given

there exist natural numbers such that .Let

be the smallest such natural number. ThenIf 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-20 23:21:53)*

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

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

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

In fact, the mapping

is a bijection. This also proves that the Cartesian product of a countable set with itself is countable.

Offline

Pages: **1**