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

(ii) If
, then
. Then

Hence, it must be that
and ∴
.

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

Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

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

Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

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

Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?