Processing math: 100%

Probability

The Analysis of Data, volume 1

Set Theory: Cardinality

A.3. Cardinality

The most obvious generalization of the size of a set A to infinite sets (see Definition A.1.3) implies the obvious statement that infinite sets have infinite size. A more useful generalization can be made by noticing that two finite sets A,B have the same size if and only if there exists a bijection between them, and generalizing this notion to infinite sets.

Definition A.3.1. Two sets A and B (finite or infinite) are said to have the same cardinality, denoted by AB if there exists a bijection between them.

Note that the cardinality concept above defines a relation that is reflexive (AA) symmetric (ABBA), and transitive (AB and BC implies AC) and is thus an equivalence relation. The cardinality relation thus partitions the set of all sets to equivalence classes containing sets with the same cardinality. For each natural number kN, we have an equivalence class containing all finite sets of that size. But there are also other equivalence classes containing infinite sets, the most important one being the equivalence class that contains the natural numbers N.

Definition A.3.2. Let A be an infinite set. If AN then A is a countably infinite set. If AN then A is a uncountably infinite set.
Proposition A.3.1. Every infinite subset E of a countably infinite set A is countably infinite.
Proof. A is countably infinite, so we can construct an infinite sequence x1,x2, containing the elements of A. We can construct another sequence, y1,y2,, that is obtained by omitting from the first sequence the elements in AE. The sequence y1,y2, corresponds to a bijection between the natural numbers and E.
Proposition A.3.2. A countable union of countably infinite sets is countably infinite.
Proof. Let An,nN be a collection of countably infinite sets. We can arrange the elements of each An as a sequence that forms the n-row of a table with infinite rows and columns. We refer to the element at the i-row and j-column in that table as Aij. Traversing the table in the following order: A11, A21, A12, A31, A22, A13, and so on (traversing south-west to north-east diagonals of the table starting at the north-west corner), we express the elements of A=nNAn as an infinite sequence. That sequence forms a bijection from N to A.
Corollary A.3.1. If A is countably infinite then so is Ad, for dN.
Proof. If A is countably infinite, then A×A corresponds to one copy of A for each element of A, and thus we have a bijection between A2 and a countably infinite union of countably infinite sets. The previous proposition implies that A2 is countably infinite. The general case follows by induction.

It can be shown that countably infinite sets are the "smallest" sets (in terms of the above definition of cardinality) among all infinite sets. In other words, if A is uncountably infinite, then there exists an onto function f:AN but no onto function f:NA.

Proposition A.3.3. Assuming a<b and dN, NZQN[a,b]N(a,b)NRNRd.

We first define the concept of a binary expansion of a number, which will be used in the proof of the proposition below.

Definition A.3.3. The binary expansion of a number r[0,1] is defined as 0.b1b2,b3 where bn{0,1},nN and r=nNbn2n.
Example A.3.1. The binary expansions of 1/4 is 0.01 and the binary expansion of 3/4 is 0.11=1/2+1/4.
Proof of Proposition A.3.3. Obviously there exists a bijection between the natural numbers and the natural numbers. The mapping f:NZ defined as f(n)={(n1)/2n is oddn/2n is even maps 1 to 0, 2 to -1, 3 to 1, 4 to -2, 5 to 2, etc., and forms a bijection between N and Z.

A rational number is a ratio of a numerator and a denominator integers (note however that two pairs of numerators and denominators may yield the same rational number). We thus have that Q is a subset of Z2, which is countably infinite by Proposition A.3.2. Using Proposition A.3.1, we have that Q is countably infinite.

We next show that there does not exist a bijection between the natural numbers and the interval [0,1]. If there was such a mapping f, we could arrange the numbers in [0,1] as a sequence f(n),nN and form a table A with infinite rows and columns where column n is the binary expansion of the real number f(n)[0,1].

We could then create a new real number whose binary expansion is bn,nN with bnAnn for all nN by traversing the diagonal of the table and choosing the alternative digits. This new real number is in [0,1] since it has a binary expansion, and yet it is different from any of the columns of A. We have thus found a real number that is different from any other number in the range of f, contradicting the fact that f is onto. The setup described above is slightly simplified. A rigorous proof needs to resolve the fact that some numbers in [0,1] have two different binary expansions, for example, 0.0111111=0.1. See for example (Rudin, 1976).

Since there is no onto function from the naturals to [0,1] there can be no onto function from the natural numbers to R or its Cartesian products Rd.

We extend below the definition of a Cartesian product (see Definition A.1.10) to an infinite number of sets.

Definition A.3.4. Let A,T be sets. The notation AT denotes a Cartesian product of multiple copies of A, one copy for each element of the set T. In other words, AT is the set of all functions from T to A. The notation A denotes AN, a product of a countably infinite copies of A.
Example A.3.2. The set R is the set of all infinite sequences over the real line R R={(a1,a2,a2,,):anR for all nN} and the set {0,1} is the set of all infinite binary sequences. The set R[0,1] is a Cartesian product of multiple copies of the real numbers --- one copy for each element of the interval [0,1], or in other words the set of all functions from [0,1] to R.
Example A.3.3. The set {0,1}A is the set of all functions from A to {0,1}, each such function implying a selection of an arbitrary subset of A (the selected elements are mapped to 1 and the remaining elements are mapped to 0). A similar interpretation may given to sets of size 2 that are different than {0,1}. Recalling Definition A.1.7, we thus have if |B|=2, then BA corresponds to the power set 2A, justifying its notation.