Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

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


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

A: Click here for answer.
 

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


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

A: Click here for answer.
 

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

A: Click here for answer.
 

Board footer

Powered by FluxBB