   Go backward to 6.1 Further NotionsGo up to 6 More on FunctionsGo forward to 6.3 Embedding Sets ## 6.2 Counting Set Elements

The notions introduced in Chapter Sets, Functions, and Relations do not yet allow us to talk about the number of elements in a set. This concept is usually introduced in the following (inconstructive) way:

Definition 73 (Number of Set Elements) A set is  finite (endlich) if it is empty or there exists a bijection to Nn for some n in N>0. We then call 0 respectively n the  size (Größe) or  cardinality (Kardinalität) of the set:
 S is finite : <=> S = 0 \/ (exists n in N>0, f: f: Nn ->bijective S); |S| := if S = 0 then 0 else (such n in N>0: exists f: f: Nn ->bijective S).
A set is  infinite (unendlich) if is not finite:
S is infinite : <=> ~S is finite.

Sometimes the set size |S| is also denoted as #S. Please note that |S| is only defined, if S is finite. In this case, however, it is uniquely defined because the number of elements is independent of the order in which we count them, i.e., independent of the particular bijection chosen.

Proposition 73 (Unicity of Bijection) If S is not empty and both f: Nn -> S and g: Nm -> S are bijections, then n = m:
 (forall S != 0, n in N, m in N, f: Nn ->bijective S, g: Nm ->bijective S: m = n).

Proof  Take arbitrary S != 0, n in N, m in N, f: Nn ->bijective S, g: Nm ->bijective S and assume m != n. We show a contradiction.

Assume m < n (the case m > n proceeds analogously). We know f o g-1: Nn ->bijective Nm. However, since Nn has n elements, Nm has m elements, and m < n, f o g-1 cannot be injective (pigeonhole principle, a fact that has to be proved separately).

Example
• The set S := {0, 2, 4} is finite; its size is 3 because we can define a function f: N3 ->bijective S as
 f(0) := 0 f(1) := 2 f(2) := 4
i.e., f = [0, 2, 4]. The length of f is the same as the length of [0, 4, 2], [4, 2, 0] or of any other bijection to S.
• The set N is infinite. If it were finite, we had some n in N and some f: Nn ->bijective N. Take k := 1+max{f(i): i in Nn}. Then, by construction, k in N but forall i in Nn: f(i) != k, i.e., f is not surjective on N.

A constructive way to determine the number of elements of a set is shown by the following recursive definition:

 size(S) := if S = 0 then 0 else let e = (such x: x in S): 1+size(S-e)

We then have |S| = size(S), for every finite set S. However, to show that above recursive definition indeed defines a function itself relies on the termination term |S|: therefore we give a constructive definition in terms of set reduction:

 |S| := reduce(count, S, 0); count(e, i) := i+1.

Logic Evaluator  The constructive definitions introduced above can be implemented as follows:

We sometimes count the number of values for which a proposition holds.

Definition 74 (Number Quantifier) For every variable x and formula F, the phrase
#x: F
is a term where x is bound and whose value equals
|{x: F}|.

Please note that the value of such a "number" term is only defined if the base formula is true for a finite number of assignments for the bound variable.

We state the following facts (whose proofs can be easily given by induction).

Proposition 75 (Set Sizes) If A and B are disjoint with sizes m and n, respectively, then the size of their union is m+n:
 forall A, B, m in N, n in N: (A intersection B = 0 /\  |A| = m /\  |B| = n) => |A union B| = m+n.
The size of the Cartesian product of two sets is the product of their sizes:
 forall A, B, m in N, n in N: (|A| = m /\  |B| = n) => |A x B| = m*n.
If A and B have size m and n, respectively, then the size of the set of functions from A to B is nm:
 forall A, B, m in N, n in N: (|A| = m /\  |B| = n) => |A -> B| = nm.
If A is of size n, then A has 2n subsets:
 forall A, n in N: |A| = n => |{S in P(S): T}| = 2n.

It may seem surprising, but we are able to distinguish between different kinds of "infinity", i.e., some sets are "more infinite" than others.

Definition 75 (Countable Sets) A set is  countable (abzählbar unendlich) if it has an  enumeration (Aufzählung), i.e., a bijective mapping from N:
S is countable : <=> exists f: f: N ->bijective S.

Example
• The set Z is infinite but it is countable because we can define a function f: N ->bijective Z as
 f(x) := if x is even then -x/2 else (x+1)/2
i.e.,
 f = [0, 1, -1, 2, -2, 3, -3, ...].
• The set Q is infinite but countable; we sketch the construction of a corresponding enumeration. We can list all positive rationals in an infinite matrix that holds at position <i, j> the rational i+1/j+1:
 1/1 1/2 1/3 1/4 ... / / / 2/1 2/2 2/3 ... ... / / 3/1 3/2 ... ... ... / 4/1 ... ... ... ... ... ... ... ... ...
We can enumerate all elements in this matrix by first traversing all fractions x/y with x+y=2, then all fractions with x+y=3, then all fractions with x+y=4, and so on (always enumerating the fractions x+y=c in the order of increasing x).

From this sequence, we have to remove all "doubles" (such as 2/2 which has already appeared previously as 1/1) constructing a corresponding sequence f': N -> Q that contains each positive rational number in exactly one position. Finally we can define an enumeration of the rationals by g: N ->bijective Q defined as

 g(x) := if x = 0 then 0 else if x is even then -f'(x/2) else f'((x-1)/2)
i.e.,
g = [0, 1, -1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, ...].
• The set of all infinite sequences over {0, 1} is not countable: if it were, we had some f: N ->bijective (N -> {0,1}). Take s: N -> {0, 1} defined as
s(i) := f(i)i
where d := 1-d. Then s differs from f(i) in the i-th digit (for every i in N), thus s is not contained in f.
 f(0) = f(1) = f(2) = f(3) = ...
 [f(0)_0 f(0)1 f(0)2 f(0)3 ...] [f(1)0 f(1)_1 f(1)2 f(1)3 ...] [f(2)0 f(2)1 f(2)_2 f(2)3 ...] [f(3)0 f(3)1 f(3)2 f(3)_3 ...] ... ... ... ... ...
s := [f(0)0,f(1)1,f(2)2,f(3)3,...]
The argument called  diagonalization (Diagonalisierung) has been invented by Cantor to show the following result.
• The set R is not countable: every infinite sequence d of decimal digits represents a real number 0.d0d1d2.... Since the set of all infinite sequences is not countable (and every real number is represented by a countable set of such sequences), also R is not countable.

Above example shows us that there exists a bijection between N and Z, i.e., there is one distinct natural number for every integer number and vice versa. It is therefore natural to consider N and Z of the same size4. The concept of bijections can therefore be used to compare the size of sets.

Proposition 76 (Set Cardinalities) Two sets have  same size or  same cardinality, if there is a bijection between them:
A and B are of same size : <=> exists f: f: A ->bijective B.
One set is not larger than another set, if there exists an injection from the first set into the second set:
A is not larger than B : <=> exists f: f: A ->injective B.
One set is smaller than another set, if they are not of same size and the second one is not larger than the first one.
 A is smaller than B : <=> (A is not larger than B) /\  ~(A and B have same size).

For finite sets, above notions clearly coincide with the definition of | |.

Proposition 77 (Finite Sets) For all finite sets A and B, the following holds:
 |A| = |B| => A and B have same size; |A| <= |B| => A is not larger than B; |A| < |B| => A is smaller than B.

However the new notions also allow us to compare the sizes of infinite sets.

Example  By the arguments given in the previous example, we have the following results:
• N has the same size as Z.
• Z has the same size as Q.
• Q is smaller than R.
One can also easily show
• R has the same size as C.
The number domains introduced in Section Numbers therefore fall into two classes:
1. N, Z, Q (the enumerable ones),
2. R, C (the not enumerable ones).

The hierarchy of "infiniteness" is not limited, because we can construct for every (also infinite) set a still larger set.

Proposition 78 (Size of Powerset) Every set is smaller than its powerset:
 forall S: S is smaller than P(S).

Proof  Take arbitrary S. S is not larger than P(S) because we can define
 f: S ->injective P(S) f(x) := {x}.
Assume that S and P(S) are of the same size, i.e., there exists some f: S ->bijective P(S). We show a contradiction.

Take A := {x in S: x not  in f(x)}. Since f is surjective and A subset S, i.e., A in P(S), we have some a in S with f(a) = A. But then we know

 a in A <=> a not  in f(a) <=> a not  in A.

Consequently, we know that N is smaller than P(N) which is smaller than P(P(N)) which is smaller than P(P(P(N))) which is ....

We also have the following result.

Proposition 80 (Size of Function Space) Every set is smaller than the set of all functions into it:
 forall A, B: B is smaller than A -> B.

Permutations  Bijections on subsets of N also of importance for sorting elements in a particular order.

Definition 76 (Permutation) A  permutation (Permutation) of length n is a bijective function from Nn to Nn:
p is permutation of length n : <=> p: Nn ->bijective Nn.

Example  Take the sequence s = [a, b, c, d, e] and the permutation p=[1,0,4,3,2]. Then we have
p o s = [b, a, e, d, c].

Logic Evaluator  Permutations can be easily implemented as follows.

Example  The problem of  sorting (Sortieren) a sequence of elements can be specified as follows:
• Input:
• A ...the element domain,
• <= subset A x A ...a reflexive, antisymmetric, and transitive relation,
• n in N ...the length of the sequence,
• s: Nn -> A ...a sequence of length n on A.
• Output: t: Nn -> A such that
• t is permutation of s,
• t is sorted with respect to <= .
with the following auxiliary predicates:
 t is permutation of s : <=> let n = length(t): n = length(s) /\ exists p: p is permutation of length n /\  p o s = t; t is sorted with respect to <= : <=> forall 0 <= i < length(t): ti <= ti+1.

The set of permutations is closed under function composition.

Proposition 81 (Composition of Permutations) The composition of two permutations of the same length is also a permutation of this length:
 forall n in N, p0, p1: (p0 is permutation of length n /\ p1 is permutation of length n) => p0 o p1 is permutation of length n.
The inverse of a permutation is a permutation of the same length:
 forall n in N, p: p is permutation of length n => p-1 is permutation of length n.

Example  Take the permutations p=[1,0,4,3,2] and q=[2,1,3,4,0]. Then
p o q = [1,2,0,4,3],
e.g., (p o q)(2) = q(p(2)) = q(4) = 0. We also have
 p-1 = [2,0,1,4,3]
e.g., p-1(2) = 1 because p(1)=2, and thus
 p o p-1 = p-1 o p = [0,1,2,3,4].

The following establishes some basic combinatorial knowledge.

Proposition 82 (Number of Permutations) The number of permutations of length n is 2n:
forall n in N: |{f: f is permutation of length n}| = 2n.

Proof  We proceed by induction on n.

If n=0, then the only permutation is p = [ ].

Assume |{f: f is permutation of length n}| = 2n.

We define

 insert(x, i, f) := such s: length(s) = 1+length(f) /\ forall j in Nn+1: j < i => s(j) = f(j) /\ j = i => s(j) = x /\ j > i => s(j) = f(j-1)
which returns the sequence constructed from f by inserting element x at position i.

Then we have

 |{f: f is permutation of length n+1}| = |{insert(n+1, i, f): i in Nn+1 /\  f is permutation of length n}| = (n+1)*|{f: f is permutation of length n}| = (n+1)*n = (n+1)!

Author: Wolfgang Schreiner
Last Modification: October 4, 1999   