1.5 Infinite sets

Editorial note

The proof of Theorem 1.5 below retains the book’s binary-expansion argument and its known ambiguity; Problem 1.11 asks you to repair it. Choice is asserted for nonempty sets. Countable choice is also an additional axiom over ZF; it does not follow merely from finiteness of individual selections. The independence statements are relative to consistency of the relevant axiomatic system.

A set S is said to be finite if there is a natural number n such that S is in one-to-one correspondence with the set $N=\{1,2,3,\dots ,n\}$ consisting of the first n natural numbers. We call n the cardinality of the set S, written $n=\mathrm{Card}(S)$

Example 1.9

For any two sets S and T the set of all maps $\phi :S\to T$ will be denoted by $T^S$ . Justification for this notation is provided by the fact that if S and T are both finite and $s=\mathrm{Card}(S),t=\mathrm{Card}(T)$ then $\mathrm{Card}(T^S)=t^s$ . In Example 1.7 it was shown that for any set S, the power set $2^S$ is in one-to-one correspondence with the set of characteristic functions on $\{0,1{\}}^S$ . As shown in Example 1.1, for a finite set S both sets have cardinality $2^s$.

Infinite sets

A set is said to be infinite if it is not finite. The concept of infinity is intuitively quite difficult to grasp, but the mathematician Georg Cantor (1845–1918) showed that infinite sets could be dealt with in a completely rigorous manner. He even succeeded in defining different ‘orders of infinity’ having a transfinite arithmetic that extended the ordinary arithmetic of the natural numbers.

Countable sets

The lowest order of infinity is that belonging to the natural numbers. Any set S that is in one-to-one correspondence with the set of natural numbers $\mathbb{N}=\{1,2,3,\dots \}$ is said to be countably infinite, or simply countable. The elements of S can then be displayed as a sequence, $s_1,s_2,s_3,\dots$ on setting $s_i=f^{-1}(i)$

Example 1.10

The set of all integers $\mathbb{Z}=\{0,\pm 1,\pm 2,...\}$ is countable, for the map $f:\mathbb{Z}\to \mathbb{N}$ defined by $f(0)=1\mathrm{and}f(n)=2n,f(-n)=2n+1$ for all $n>0$ is clearly a bijection,

$$f(0)=1,f(1)=2,f(-1)=3,f(2)=4,f(-2)=5,\dots$$

Referenced 1 time

• 1.5 Infinite setsA rational number is a fraction n/m where m is a natural number (positive integer) and n is an integ…

Theorem 1.1

Every subset of a countable set is either finite or countable.

Referenced 1 time

• 1.5 Infinite setsThe set [0, 1] is therefore uncountable since it is in one-to-one correspondence with the power set …

Proof

Let S be a countable set and $f:S\to \mathbb{N}$ a bijection, such that $f(s_1)=1,f(s_2)=$ $2,\dots$ . Suppose $S^{\prime }$ is an infinite subset of S. Let $s_1^{\prime }$ be the first member of the sequence $s_1,s_2,...$ . that belongs to $S^{\prime }$ . Set $s_2^{\prime }$ to be the next member, etc. The map $f^{\prime }:S^{\prime }\to \mathbb{N}$

defined by

$$f^{\prime }(s_1^{\prime })=1,f^{\prime }(s_2^{\prime })=2,\dots$$

is a bijection from $S^{\prime }$ to $\mathbb{N}$.

Theorem 1.2

The cartesian product of any pair of countable sets is countable.

Referenced 1 time

• 1.5 Infinite setsA rational number is a fraction n/m where m is a natural number (positive integer) and n is an integ…

Proof

Let S and T be countable sets. Arrange the ordered pairs $(s_i,t_j)$ that make up the elements of $S\times T$ in an infinite rectangular array and then trace a path through the array as depicted in Fig. 1.1, converting it to a sequence that includes every ordered pair. -

Figure 1.1 Product of two countable sets is countable

Corollary 1.3

The rational numbers $\mathbb{Q}$ form a countable set.

Referenced 1 time

• Chapter 1 · Sets and structuresEnglish source text with OCR repairs and explicit editorial notes. All 7 sections, 15 examples, 6 nu…

Proof

A rational number is a fraction n/m where m is a natural number (positive integer) and n is an integer having no common factor with m. The rationals are therefore in one-to-one correspondence with a subset of the product set $\mathbb{Z}\times \mathbb{N}.$ . By Example 1.10 and Theorem 1.2, $\mathbb{Z}\times \mathbb{N}$ is a countable set. Hence the rational numbers Q are countable. -

In the set of real numbers ordered by the usual $\le$, the rationals have the property that for any pair of real numbers x and y such that $x<y$ , there exists a rational number q such that $x<q<y$ . Any subset, such as the rationals Q, having this property is called a dense set in R. The real numbers thus have a countable dense subset; yet, as we will now show, the entire set of real numbers turns out to be uncountable.

Uncountable sets

A set is said to be uncountable if it is neither finite nor countable; that is, it cannot be set in one-to-one correspondence with any subset of the natural numbers.

Theorem 1.4

The power set $2^S$ of any countable set $s$ is uncountable.

Referenced 1 time

• 1.1 Sets and logicThe constants … . may themselves be sets and, indeed, some formulations of set theory require them t…

Proof

We use Cantor’s diagonal argument to demonstrate this theorem. Let the elements of S be arranged in a sequence $\mathcal{S}=\{s_1,s_2,\dots \}$ . Every subset $U\subseteq S$ defines a unique sequence of 0’s and 1’s

$$x=\{{ϵ}_1,{ϵ}_2,{ϵ}_3,\dots \}$$

where

$${ϵ}_i=\{\begin{array}{ll}0& \text{ if }{s}_i\notin U,\\ 1& \text{ if }{s}_i\in U.\end{array}$$

The sequence x is essentially the characteristic function of the subset $U$ , discussed in Example 1.7. If $2^S$ is countable then its elements, the subsets of $S,$ can be arranged in sequential form, $U_1,U_2,U_3,\dots$ , and so can their set-defining sequences,

$$\begin{array}{l}{x}_1={ϵ}_{11},{ϵ}_{12},{ϵ}_{13},\dots \\ x_2={ϵ}_{21},{ϵ}_{22},{ϵ}_{23},\dots \\ x_3={ϵ}_{31},{ϵ}_{32},{ϵ}_{33},\dots \\ \text{ etc. }\end{array}$$

Let $x^{\prime }$ be the sequence of 0’s and 1’s defined by

$$x^{\prime }={ϵ}_1^{\prime },{ϵ}_2^{\prime },{ϵ}_3^{\prime },\dots$$

where

$${ϵ}_i^{\prime }=\{\begin{array}{ll}0& \text{ if }{ϵ}_{ii}=1,\\ 1& \text{ if }{ϵ}_{ii}=0.\end{array}$$

The sequence $x^{\prime }$ cannot be equal to any of the sequences $x_i$ above since, by definition, it differs from $x_i$ in the ith place, ${ϵ}_i^{\prime }\ne {ϵ}_{ii}$ . Hence the set of all subsets of $S$ cannot be arranged in a sequence, since their characteristic sequences cannot be so arranged. The power set $2^S$ cannot, therefore, be countable.

Theorem 1.5

The set of all real numbers $\mathbb{R}$ is uncountable

Referenced 3 times

• 1.1 Sets and logicThe constants … . may themselves be sets and, indeed, some formulations of set theory require them t…
• 1.5 Infinite setsThe proof of Theorem 1.5 below retains the book’s binary-expansion argument and its known ambiguity;…
• 1.5 Infinite setsThere is a technical flaw in the proof of Theorem 1.5, since a decimal number ending in an endless s…

Proof

Each real number in the interval [0, 1] can be expressed as a binary decimal

$$0.{ϵ}_1{ϵ}_2{ϵ}_3\dots \text{ where }\text{ each }{ϵ}_i=0\text{ or }1(i=1,2,3,\dots ).$$

The set [0, 1] is therefore uncountable since it is in one-to-one correspondence with the power set $2^{\mathbb{N}}$ . Since this set is a subset of R, the theorem follows at once from Theorem 1.1.

Example 1.11

We have seen that the rational numbers form a countable dense subset of the set of real numbers. A set is called nowhere dense if it is not dense in any open interval $(a,b)$ . Surprisingly, there exists a nowhere dense subset of R called the Cantor set, which is uncountable – the surprise lies in the fact that one would intuitively expect such a set to be even sparser than the rationals. To define the Cantor set, express the real numbers in the interval [0, 1] as ternary decimals, to the base 3,

Figure 1.2 The Cantor set (after the four subdivisions)

$$x=0.{ϵ}_1{ϵ}_2{ϵ}_3\dots \text{ where }{ϵ}_i=0,1\text{ or }2,\forall i.$$

Consider those real numbers whose ternary expansion contains only 0’s and 2’s. These are clearly in one-to-one correspondence with the real numbers expressed as binary expansions by replacing every 2 with 1.

Geometrically one can picture this set in the following way. From the closed real interval [0, 1] remove the middle third (1/3, 2/3), then remove the middle thirds of the two pieces left over, then of the four pieces left after doing that, and continue this process ad infinitum. The resulting set can be visualized in Fig. 1.2.

This set may appear to be little more than a mathematical curiosity, but sets displaying a similar structure to the Cantor set can arise quite naturally in non-linear maps relevant to physics.

The continuum hypothesis and axiom of choice

All infinite subsets of R described above are either countable or in one-to-one correspondence with the real numbers themselves, of cardinality $2^{\mathbb{N}}$ . Cantor conjectured that this was true of all infinite subsets of the real numbers. This famous continuum hypothesis proved to be one of the most challenging problems ever postulated in mathematics. In 1938 the famous logician Kurt Gödel (1906–1978) showed that it would never be possible to prove the converse of the continuum hypothesis – that is, no mathematical inconsistency could arise by assuming Cantor’s hypothesis to be true. While not proving the continuum hypothesis, this meant that it could never be proved using the time-honoured method of reductio ad absurdum. The most definitive result concerning the continuum hypothesis was achieved by Cohen [7], who demonstrated that it was a genuinely independent axiom, neither provable, nor demonstrably false.

In many mathematical arguments, it is assumed that from any family of sets it is always possible to create a set consisting of a representative element from each set. To justify this seemingly obvious procedure it is necessary to postulate the following proposition:

Axiom of choice

Given a family of nonempty sets $\mathcal{S}=\{S_i|i\in I\}$ labelled by an indexing set I, there exists a choice function $f:I\to \bigcup \mathcal{S}$ such that $f(i)\in S_i$ for all $i\in I$

While correct for finite and countably infinite families of sets, the status of this axiom is much less clear for uncountable families. Cohen in fact showed that the axiom of choice was

an independent axiom and was independent of the continuum hypothesis. It thus appears that there are a variety of alternative set theories with differing axiom schemes, and the real numbers have different properties in these alternative theories. Even though the real numbers are at the heart of most physical theories, no truly challenging problem for mathematical physics has arisen from these results. While the axiom of choice is certainly useful, its availability is probably not critical in physical applications. When used, it is often invoked in a slightly different form:

Theorem 1.6

(Zorn’s lemma) Let $\{P,\le \}$ be a nonempty partially ordered set (poset) with the property that every totally ordered subset is bounded above. Then P has a maximal element.

Some words of explanation are in order here. Recall that a subset Q is totally ordered if for every pair of elements x, $y\in Q$ either $x\le y\mathrm{or}y\le x$ . A subset Q is said to be bounded above if there exists an element $x\in P$ such that $y\le x$ for all $y\in \mathcal{Q}$ . A maximal element of P is an element z such that there is no $y\ne z$ such that $z\le y$ . The proof that Zorn’s lemma is equivalent to the axiom of choice is technical though not difficult; the interested reader is referred to Halmos [4] or Kelley [6].

Proof note · not given in this chapter

The book does not prove Zorn’s lemma here. It refers the reader to Halmos [4] or Kelley [6] for its equivalence to the axiom of choice.

Problems

Problem 1.11

There is a technical flaw in the proof of Theorem 1.5, since a decimal number ending in an endless sequence of 1’s is identified with a decimal number ending with a sequence of 0’s, for example,

$$.011011111\cdots =.0111000000\dots$$

Remove this hitch in the proof.

Referenced 1 time

• 1.5 Infinite setsThe proof of Theorem 1.5 below retains the book’s binary-expansion argument and its known ambiguity;…

Problem 1.12

Prove the assertion that the Cantor set is nowhere dense.

Problem 1.13

Prove that the set of all real functions $f:\mathbb{R}\to \mathbb{R}$ has a higher cardinality than that of the real numbers by using a Cantor diagonal argument to show it cannot be put in one-to-one correspondence with R.

Problem 1.14

If $f:[0,1]\to \mathbb{R}$ is a non-decreasing function such that $f(0)=0,f(1)=1$ , show that the places at which f is not continuous form an at most countable subset of [0, 1].

Referenced 2 times

• 1.1 Sets and logicThe constants … . may themselves be sets and, indeed, some formulations of set theory require them t…
• Chapter 1 · Sets and structuresThe idea of sets as collections of objects has a non-rigorous, or ‘naive’ quality, although it is th…