Countability

JaneFairfax · 2009-01-20 12:33:14

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-20 23:21:53)

JaneFairfax · 2009-01-20 12:54:32

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.

JaneFairfax · 2009-01-20 23:20:55

In fact, the mapping

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

Math Is Fun Forum