Real Analysis Home

Subsets of $\mathbb R$ and Cardinality

    


Beside $\mathbb N, \; \mathbb Z$, and $\mathbb Q$, the following are frequently used subsets of $\mathbb R$ in Real Analysis:

Open interval: $(a,b)=\{x\in \mathbb R\;|\; a < x < b\}$.
Closed interval: $[a,b]=\{x\in \mathbb R\;|\; a\leq x\leq b\}$.
Half-open/ half-closed interval: $$(a,b]=\{x\in \mathbb R\;|\; a < x\leq b\}, \text{\;and}$$ $$[a,b)=\{x\in \mathbb R\;|\; a\leq x < b\}.$$

Example. The domain and range of the function $f$ defined by $f(x)=1/\sqrt{1-x^2}$ are $(-1,1)$ and $[1,\infty)$ respectively.

The preceding sets are all infinite sets. Infinite sets may be of different kinds in terms of counting their elements.

Definition (Countable set). An infinite countable set is called an enumerable set. By definition an enumerable set has a bijection with $\mathbb N$. Therefore a countable set is either finite or enumerable.

Example.

  1. $\mathbb N$ is countable because of the identity map $I:\mathbb N\to \mathbb N$ defined by $I(n)=n$.

  2. To show $\mathbb Z$ is countable, define $f:\mathbb N\to \mathbb Z$ by $$f(n)=\begin{cases} \frac{n}{2} & \text{if } n \text{ is even}\\ \frac{1-n}{2} & \text{if } n \text{ is odd} \end{cases}$$ To show one-to-oneness of $f$, let $f(m)=f(n)$ for some $m,n\in \mathbb N$. Note that if both $m$ and $n$ are not even or both $m$ and $n$ are not odd, then $f(m)=f(n)\implies m+n=1$, a contradiction. So when $m$ and $n$ are even, $$f(m)=f(n)\implies \frac{m}{2}=\frac{n}{2} \implies m=n.$$ Similarly when $m$ and $n$ are odd, $$f(m)=f(n)\implies \frac{1-m}{2}=\frac{1-n}{2} \implies m=n.$$ To show ontoness of $f$, let $k\in \mathbb Z$. If $k>0$, then $f(2k)=\frac{2k}{2}=k$ where $2k\in \mathbb N$. If $k\leq 0$, then $f(1-2k)=\frac{1-(1-2k)}{2}=k$ where $1-2k\in \mathbb N$.

Theorem. $\mathbb Q$ is countable.
Since $\mathbb Z$ is countable, $S_q=\{\frac{p}{q}\;|\; p\in \mathbb Z\}$ is countable for all $q\in\mathbb N$. Note that $$\mathbb Q=\bigcup_{q=1}^{\infty} S_q.$$ Since countable union of countable sets is countable (long exercise), $\mathbb Q$ is countable.

Theorem. The interval $(0,1)$ is uncountable.
(Cantor's diagonal argument, 1891) Suppose $(0,1)$ is uncountable. Let $(0,1)=\{x_n \;|\; n\in \mathbb N\}$ where each $x_n$ has a decimal expansion (not necessarily finite): $$\begin{array}{ccl} x_1&=&0.{\bf a_{11}}a_{12}a_{13}a_{14}\cdots\\ x_2&=&0.a_{21}{\bf a_{22}}a_{23}a_{24}\cdots\\ x_3&=&0.a_{31}a_{32}{\bf a_{33}}a_{34}\cdots\\ &\vdots&\hspace{55pt} \ddots \end{array}$$ Now construct a number $b=0.b_{1}b_{2}b_{3}b_{4}\cdots \in (0,1)$ by choosing $b_i\neq a_{ii}$ as follows: $$b_i=\begin{cases} 6 & \text{if } a_{ii}=5\\ 5 & \text{if } a_{ii}\neq 5 \end{cases}$$ Then $b\neq x_i$ for all $i\in \mathbb N$ but $b\in (0,1)$ contradicting that $(0,1)=\{x_n \;|\; n\in \mathbb N\}$.

By the preceding theorem, $(0,1)\setminus \mathbb Q$ is uncountable and so are $\mathbb R$ and $\mathbb R\setminus \mathbb Q$. Thus $\mathbb Q$ is a countably infinite set where $\mathbb R\setminus \mathbb Q$ is an uncountably infinite set.

To distinguish the sizes (cardinality) of infinite sets such as $\mathbb N$ and $\mathbb R$, Georg Cantor introduced cardinal numbers such as $\aleph_0$ (read aleph-naught or aleph-zero) $<\aleph_1<\aleph_2<\cdots$ where $\aleph_0$ is the cardinality of $\mathbb N$. The cardinality of $\mathbb R$ is denoted by $\mathfrak{c}$. By the preceding theorem, $\aleph_0<\mathfrak{c}$. The continuum hypothesis states that $\mathfrak{c}=\aleph_1$, i.e., there is no set whose cardinality is strictly between that of $\mathbb N$ and that of $\mathbb R$.


Last edited by Dr. Mallik on