Finite, Countable, and Uncountable Sets
2.1 Rudin Definition.
Consider two sets $A$ and $B,$
whose elements may be any objects
whatsoever, and suppose that with
each element $x$ of $A$ there is
associated, in some manner, an
element of $B,$ which we denote
by $f(x).$ Then $f$ is said to be
a function from $A$ to $B$,
(or
a mapping of $A$ into
$B$.)
The set $A$ is called the
domain of $f$.
(We also say
$f$ is defined on $A$),
and the elements $f(x)$ are called
the values of $f$.
The set of all values of $f$ is called
the range of $f$.
2.2 Rudin Definition.
Let $A$ and $B$ be two sets and
let $f$ be a mapping of $A$ into
$B.$ If $E \subset A,$ $f(E)$ is
defined to be the set of all
elements $f(x),$ for $x \in E.$
We call $f(E)$ the
image of $E$ under $f$.
In this notation, $f(A)$ is the
range of $f.$ It is clear that
$f(A) \subset B.$ If $f(A) = B,$
we say that
$f$ maps $A$ onto $B$.
(Note that, according to this
usage, onto is more specific
than into.)
If $E \subset B,$ $f^{-1}(E)$
denotes the set of all $x\subset A$
such that $f(x) \in E.$ We call
$f^{-1}(E)$
the inverse image of $E$ under
$f$.
If $y \in B,$ $f^{-1}(y)$ is the
set of all $x \in A$ such that
$f(x) = y.$ If, for each $y\in B,$
$f^{-1}(y)$ consists of at most one
element of $A,$ then $f$ is said to be
a one-to-one mapping of $A$
into $B$.
This may also be expressed as
follows: $f$ is a one-to-one mapping
of $A$ into $B$ provided that
$f(x_1) \ne f(x_2)$ whenever
$x_1\ne x_2,$
$x_1 \in A,$
$x_2 \in A.$
(The notation $x_1 \ne x_2$ means that
$x_1$ and $x_2$ are distinct elements;
otherwise we write $x_1 = x_2.$)
2.3 Rudin Definition.
If there exists a one-to-one
mapping of $A$ onto $B,$ we say
that $A$ and $B$ can be put in
one-to-one correspondence,
or that $A$ and $B$ have the same
cardinal number,
or, briefly, that $A$ and $B$ are
equivalent,
and we write $A \sim B.$ This
relation clearly has the following
properties:
-
reflexive:
$A \sim A$
-
symmetric:
If $A \sim B,$ then $B \sim A.$
-
transitive:
If $A \sim B$ and $B \sim C,$
then $A \sim C.$
Any relation with these three
properties is called an
equivalence relation.
2.4 Rudin Definition.
For any positive integer $n,$
let $J_n$ be the set whose elements
are the integers $1, 2, \ldots, n.$
Let $J$ be the set consisting of
all positive integers. For any set
$A,$ we say:
-
$A$ is
finite
if $A \sim J_n$ for some $n$
(the empty set is also
considered to be finite).
-
$A$ is
infinite
if $A$ is not finite.
-
$A$ is
countable
if $A \sim J.$
-
$A$ is
uncountable
if $A$ is neither finite
nor countable.
-
$A$ is
at most countable
if $A$ is finite or countable.
Countable sets are sometimes called
enumerable,
or
denumerable.
For two finite sets $A$ and $B,$
we evidently have $A \sim B$ if
and only if $A$ and $B$ contain
the same number of elements. For
infinite sets, however, the idea of
"having the same number of elements"
becomes quite vague, whereas the
notion of one-to-one correspondence
retains its clarity.
2.5 Rudin Example.
Let $A$ be the set of all integers.
Then $A$ is countable. For, consider
the following arrangement of the
sets $A$ and $J$:
\[
A:0,1,–1,2,–2,3,–3,\ldots
\]
\[
J:1,2,3,4,5,6,7,\ldots
\]
Then ...
2.6 Rudin Remark.
A finite set cannot be equivalent
to one of its proper subsets. That
this is, however, possible for
infinite sets, is shown by
Rudin 2.5,
in which $J$ is a proper subset of $A.$
In fact, we could replace
Rudin 2.4(b)
by the statement: $A$ is infinite
if $A$ is equivalent to one of its
proper subsets.
2.7 Rudin Definition.
By a
sequence,
we mean a function $f$ defined on the set
$J$ of all positive integers. If $f(n)=x_n$
for $n \in J,$ it is customary to denote
the sequence $f$ by the symbol $\{x_n\},$
or sometimes by $x_1, x_2, x_3, \ldots$ The
values of $f,$ that is, the elements $x_n,$
are called the terms of the sequence.
If $A$ is a set and if $x_n\in A,\forall n\in J,$
then $\{x_n\}$ is said to be
a sequence in $A$,
or a sequence of elements of $A.$ Note that
the terms $x_1,x_2,x_3,\ldots$ of a sequence
need not be distinct. Since every countable
set is the range of a one-to-one function
defined on $J,$ we may regard every countable
set as the range of a sequence of distinct
terms. Speaking more loosely, we may say that
the elements of any countable set can be
arranged in a sequence.
Sometimes it is convenient to replace $J$ in
this definition by the set of all nonnegative
integers, i.e., to start with $0$ rather
than with $1.$
2.8 Rudin Theorem.
Every infinite subset of a countable
set is countable.
Proof.
Suppose $E \subset A,$ and $E$ is
infinite. Arrange the elements $x$
of $A$ in a sequence $\{x_n\}$ of
distinct elements. Construct a
sequence $\{n_k\}$ as follows:
Let $n_1$ be the smallest positive
integer such that $x_{n_1}\in E.$
Having chosen $n_1,\ldots,n_k–1$
and $k = 2, 3, 4, \ldots,$ let $n_k$
be the smallest integer greater than
$n_{k}–1$ such that $x_{n_k}\in E.$
Putting $f(k) = x_{n_k}$ where
$k=1,2,3,\ldots,$ we obtain a
one-to-one correspondence between
$E$ and $J.$
The theorem shows that, roughly
speaking, countable sets represent
the "smallest" infinity: No
uncountable set can be a subset of
a countable set.
2.9 Rudin Definition.
Let $A$ and $\Omega$ be sets, and
suppose that with each element $\alpha$
of $A$ there is associated a subset of
$\Omega$ which we denote by $E_\alpha.$
The set whose elements are the set
$E_\alpha$ will be denoted by
$\{E_\alpha\}.$ Instead of speaking of
sets of sets, we shall sometimes speak
of a collection of sets, or a family
of sets.
The
union
of the sets $E_\alpha$ is defined to be
the set $S$ such that $x\in S$ if and
only if $x\in E_\alpha$ for at least one
$\alpha\in A.$ We use the notation
\begin{equation}
S = \bigcup\limits_{\alpha\in A}{E_\alpha}
\end{equation}
If $A$ consists of the integers
$1,2,\ldots,n,$ one usually writes
\begin{equation}
S=\bigcup\limits_{m=1}^{n}{E_m}
\end{equation}
or
\begin{equation}
S=E_1\cup E_2\cup\cdots\cup E_n
\end{equation}
If $A$ is the set of all positive
integers, the usual notation is
\begin{equation}
S=\bigcup\limits_{m=1}^{\infty}{E_m}
\end{equation}
The symbol $\infty$ in (4) merely
indicates that the union of a countable
collection of sets is taken, and should
not be confused wit the symbols
$+\infty,$ $–\infty,$ introduced in
Rudin 1.23.
The
intersection
of the sets $E_\alpha$ is defined to be the
set $P$ such that $x\in P$ if and only if
$x\in E_\alpha$ for every $\alpha$ in $A.$
We use the notation
\begin{equation}
P = \bigcap\limits_{\alpha \in A}{E_\alpha}
\end{equation}
or
\begin{equation}
P = \bigcap\limits_{m = 1}^{n}{E_m}
= E_1 \cap E_2 \cap \cdots \cap E_n
\end{equation}
or
\begin{equation}
P = \bigcap\limits_{m = 1}^{\infty}{E_m}
\end{equation}
as for unions. If $A \cap B$ is not empty,
we say that $A$ and $B$
intersect;
otherwise they are
disjoint.
2.10 Rudin Example.
2.11 Rudin Definition.
2.12 Rudin Definition.
Let $\{E_n\}$ be a sequence of countable sets.
Then $S = \cup E_n $ is countable.
2.12.1 Rudin Definition.
Suppose $A$ is at most countable, and, for
every $\alpha \in A,$ $B_\alpha$ is at most
countable. Then
$T=\cup_{\alpha\in A}{B_\alpha}$
is at most countable.
2.13 Rudin Definition.
Let $A$ be a countable set, and let
$B_n$ be the set of all
$n$-tuples
$(a_1,\ldots,a_n),$ where $a_k \in A$ and the
elements $a_1,\ldots,a_n$ need not be distinct.
Then $B_n$ is countable.
2.13.1 Rudin Corollary.
The set of all rational numbers is countable.
2.14 Rudin Theorem.
The set $A$ of all sequences whose
elements are the digits $0$ and $1$
is uncountable.
Metric Spaces
2.15 Rudin Definition.
A set $X,$ whose elements we shall call
points,
is said to be a
metric space
if with any two points $p$ and $q$ of $X$
there is associated a real number $d(p,q),$
called
the distance from
$p$ to $q$,
such that:
-
\(
d(p,q)\gt0\text{ if }p\ne q;d(p,p)=0
\)
-
\(
d(p,q)=d(q,p)
\)
-
\(
d(p,q)\le d(p,r)+d(r,q)
\text{ for any } r\in X
\)
Any function with these three
properties is called a
distance function,
or a
metric.
2.15.1 Rudin Example.
2.16 Rudin Definition.
The
distance in $R^k$
is defined by
$d(x,y)=\abs{x–y}$
where $x,y\in R^k$
2.17 Rudin Definition.
Let $a,$ $b,a_i,b_i,r,\lambda \in R.$
Then
-
A
segment
is a set
$(a,b)=\{x\in R:a\lt x\lt b\}.$
-
An
interval
is a set
$[a,b]=\{x\in R:a\le x\le b \}.$
-
A
half-open interval
is a set $(a,b]$ or $[a,b).$
-
A
$k$-cell
is a set
\(
\{(x_1,\ldots,x_k)\in R^k:a_i\le x_i\le b_i\}.
\)
E.g. a
$1$-cell
is an interval, a $2$-cell is a
rectangle, etc.
-
An
open ball
is a set
\(
\{y\in R^k:\abs{y–x}\lt r,r\gt0\}
\)
-
A
closed ball
is a set
$\{y\in R^k:\abs{y–x}\le r,r\gt0\}$
-
$E\in R^k$ is
convex
if $\lambda x+(1–\lambda) y\in E$
whenever $x,y\in E$ and
$0\lt\lambda\lt1.$
For example, balls and
$k$-cells
are convex.
2.18 Rudin Definition.
Let $(X,d)$ be a metric space,
$E\subset X,r\inR,p,q\in X$
-
neighborhood
of $p$:
For any $r\in R, r \gt0,$ the set
$N_r(p)=\{q:d(p,q)\lt r\}.$
In $R,$ neighborhoods are segments,
in $R^2,$ circles, in $R^3,$ spheres,
etc.
-
radius:
The number $r$ in the
definition of neighborhood.
-
limit point
of $E$: A point $p\in E$ such that
for every $N=N_r(p)$ there is a
$q\ne p$ such that $q\in N \cap E.$
-
isolated point
of $E$: A point $p \in E$ such that
$p$ is not a limit point of $E.$
-
closed set:
A set $E$ such that every limit point
$p$ of $E$ is in $E.$
-
interior point:
A point $p\in E$ such that there is
a neighborhood $N$ of $p$ such that
$N\in E.$
-
open set:
A set $E$ such that every point
$p\in E$ is an interior point.
-
perfect set:
A closed set $E$ such that every
point of $E$ is a limit point of $E.$
-
bounded set:
A set $E$ such that there is an $M\in R$
and $q\in X$ such that $d(p,q)\lt M$ for
all $p\in E.$
-
dense:
$E$ is dense in $X$ if every point of $X$
is a limit point of $E,$ or a point of $E,$
or both.
2.19 Rudin Theorem.
Every neighborhood is an open set.
2.20 Rudin Theorem.
If $p$ is a limit point of a set $E,$
then every neighborhood of $p$ contains
infinitely many points of $E.$
2.20.1 Rudin Corollary.
A set with a finite number of
points has no limit points.
2.21 Rudin Example.
The following are examples of sets
that are one or more of closed, open,
perfect, bounded.
| Set |
Closed |
Open |
Perfect |
Bounded |
| $\{z \in C: |z| \lt 1\}$ |
No |
Yes |
No |
Yes |
| $\{z \in C: |z| \le 1 \}$ |
Yes |
No |
Yes |
Yes |
| A nonempty finite set |
Yes |
No |
No |
Yes |
| $Z$ |
Yes |
No |
No |
No |
| $\left\{\frac{1}{n}\right\}_{n=1}^\infty$ |
No |
No |
No |
Yes |
| $C (=R^2)$ |
Yes |
Yes |
Yes |
No |
| $(a, b)$ |
No |
- |
No |
Yes |
2.22 Rudin Theorem.
Let $\{E_\alpha\}$ be a (finite or infinite)
collection of sets $E_\alpha.$ Then
\(
(\cup_\alpha{E_\alpha})^c
=\cap_\alpha E_\alpha^c.
\)
2.23 Rudin Definition.
A set $E$ is
open
if and only if its complement is closed.
2.23.1 Rudin Corollary.
A set $F$ is closed if and only if
its complement is open.
2.24 Rudin Theorem.
-
For any collection
$\{G_\alpha\}$ of open sets,
$\cup_\alpha G_\alpha$
is open.
-
For any collection
$\{G_\alpha\}$ of closed sets,
$\cap_\alpha G_\alpha$ is closed.
-
For any finite collection
$G_1,\ldots,G_n$ of open sets,
$\cap_{i=1}^n G_i$ is open.
-
For any finite collection
$F_1,\ldots,F_n$ of closed sets,
$\cup_{i=1}^n F_i $ is closed.
2.25 Rudin Example.
For the segment
\(
G_n=\left(-\frac{1}{n},\frac{1}{n}\right),
\)
$\{G_n\}$ is a collection of open
subsets of $R,$ yet is not an open
subset of $R.$
2.26 Rudin Definition.
If $X$ is a metric space, if
$E\subset X,$ and if $E'$
denotes the set of all limit
points of $E$ in $X,$ then
the closure of $E$
is the set $\overline E=E\cup E'.$
2.27 Rudin Theorem.
If $X$ is a metric space and
$E\subset X,$ then
-
$\overline E$ is closed
-
$E=\overline E$ if and only if
$E$ is closed
-
$\overline E\subset F$ for every
closed set $F\subset X$ such that
$E\subset F.$
By (a) and (c), $\overline E$ is
the smallest closed subset of $X$
that contains $E.$
2.28 Rudin Theorem.
Let $E$ be a nonempty set of real
numbers which is bounded above.
Let $y=\sup E.$ Then $y\in\overline E.$
Hence, $y\in E$ if $E$ is closed.
2.29 Rudin Remark.
2.30 Rudin Theorem.
Suppose $Y \subset X.$ A subset
$E$ of $Y$ is open relative to $Y$
if and only if $E=Y\cap G$ for some
open subset $G$ of $X.$
Alex Notes