Definition. A set is called countable (or denumerable) if
. In particular, all finite sets are countable. If
is countable but not finite, then
is countably infinite.
Proposition. a. If and
are countable, so is
.
b. If is countable and
is countable for every
, then
is countable.
c. If is countably infinite, then
.
Proof. a. If suffices to prove that is countable. Define a bijection from $\mathbb N$ to $\mathbb N^2$ by listing, for
successively equal to 2, 3, 4, …, those elements
such that
in order of increasing
, thus:
(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1), …
b. For each $\exists$ a surjective
, and then the map
defined by
is surjective.
c. is an infinite subset of $\mathbb N$. Lef
be the smallest element of
, and define
inductively to be the smallest element of
. Then
is a bijection from
to
.
Corollary. and
are countable.
Proof. is the union of the countable sets
,
, and
, and one can define a surjection
by
if
and
.
Definition. A set is said to have the cardinality of the continuum if
. We use letter $latex\mathfrak c$ as an abbreviation for
:
iff
Proposition. .
Proof. If , define
to be
if
is infinite and
if
is finite. Then
is injective. On the other hand, define
by
if
is bounded below and
otherwise. Then
is surjective since every positive real number has a base-2 decimal expansion. Since
, the result follows from the Schroder-Bernstein Theorem.
Corollary. If , then
is uncountable.
Proposition. a. If and
, then
.
b. If and
for all
, then
.
Proof. It suffices to take . Define
by
and
. Then
defined by
is bijective. $\Box$
” Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow.” ~ Melody Beattie
To be continued tomorrow 🙂
References
[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 8-9.
[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.