3  Functions and cardinality

Important

This chapter is here because it is about basic mathematical notions, but for the moment you can skip it and go directly to the next chapter. You will need to come back here later in the course, when we will use these notions to prove some results about languages. All exercises in later chapters about showing that some set is countable or uncountable will require you to understand the notions in this chapter. You can come back to them on a second read.

The cardinality is an inherent property of sets which defines their size, roughly meaning the number of individual objects they contain.

For finite sets, cardinality recovers the usual concept of size as “number of elements”. A system of cardinal numbers can be developed to extend the role of natural numbers in answering “how many” elements for infinite set.

Definition 3.1 (cardinality) Two sets A and B have the same cardinality (and we write |A|=|B|) if there exists a one-to-one correspondence f: A\to B.

Definition 3.2 (countable) A set S is finite if it has the same cardinality of some set A\subsetneq \mathbb{N}. A set is countably infinite if it has the same cardinality of \mathbb{N}. A set is countable if it is either finite or countably infinite.

The cardinality of \mathbb{N} is called \aleph_0 (aleph nought or aleph zero).

Exercise 3.1 Show that the following sets are countable:

  1. \mathbb{N}\setminus\{0\}.
  2. 2\mathbb{N}.
  3. \mathbb{Z}.
  4. \mathbb{N}\times \mathbb{N}.
  5. \mathscr{P}^{\mathrm{fin}}(\mathbb{N}), the set of all finite subsets of \mathbb{N}.
  6. \mathbb{Q}.
  7. (🔥) all the algebraic real numbers, i.e. the real numbers which are roots of a polynomial (in a single variable) with coefficients in \mathbb{Z}.

After Exercise 3.1, a natural question arises. Is there any set which is not countable? …Yes! (see Theorem 3.1 below).

Exercise 3.2 Show that \mathbb{R} and \mathbb{R}\cap (0,1), i.e. the real numbers betwen 0 and 1, have the same cardinality.

Trigonometric functions are not just useful for trigonometry.

Theorem 3.1 (Cantor’s Theorem) \mathbb{R} is not countable.

Thanks to Exercise 3.2 it is enough to show that \mathbb{R}\cap (0,1) is not countable. By contradiction suppose it is countable, in other words suppose that there is a one-to-one correspondence f :\mathbb{N}\to \mathbb{R}\cap (0,1). Let f(n)_i be the i-th digit in the decimal expansion of f(n). Consider the “diagonal” f(n)_n and construct a digit different from f(n)_n, for example d_n=f(n)_n +1 \pmod{10}. The number r=0.d_1d_2d_3\dots is a real number, but it cannot be in the image of f: it cannot be f(1) because the first digit d_1 by construction difers from the first digit of f(1), similarly it cannot be f(2), etc.

Georg Cantor (1845–1918)

Georg Cantor (1845–1918)

The argument above is called diagonalization and it is a very powerful tool that we will revise later in the course.

Exercise 3.3 Show that \mathscr{P}(\{0,1\}) is not countable either by

  1. showing it has the same cardinality as \mathbb{R}, or
  2. adapting the diagonalization argument to this case.

The cardinality of \mathbb{R} is the cardinality of the continuum (denoted as \mathfrak{c}).

NoteThe continuum hypothesis

The continuum hypothesis is the following statement:

for every set S s.t. \mathbb{N}\subseteq S\subseteq \mathbb{R} either S is countably infinite or it has the cardinality of the continuum, that is either there is a one-to-one correspondence between S and \mathbb{N} or a one-to-one correspondence between S and \mathbb{R}.

The continuum hypothesis is independent from the usually accepted axioms of mathematics (aka ZFC, the Zermelo-Frankel set theory plus the Axiom of Choice): ZFC (if consistent) cannot prove that continuum hypothesis is false (Gödel 1940) and ZFC cannot prove that the continuum hypothesis is true (Cohen 1963, 1964).