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

You are not logged in.

## #1 2009-01-20 12:33:14

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

### 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

(ii) If

, then
. Then

Hence, it must be that

and ∴
.

Last edited by JaneFairfax (2009-01-20 23:21:53)

Offline

## #2 2009-01-20 12:54:32

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

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

Offline

## #3 2009-01-20 23:20:55

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

### Re: Countability

In fact, the mapping

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

Offline