Math Is Fun Forum
  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

. a contradiction.

(ii) If

, then
. Then

, another contradiction.

Hence, it must be that

and ∴
.

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


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

A: Click here for answer.

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


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

A: Click here for answer.

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.


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

A: Click here for answer.

Offline

Board footer

Powered by FluxBB