previous up next
Go backward to 6.1 Further Notions
Go up to 6 More on Functions
Go forward to 6.3 Embedding Sets
RISC-Linz logo

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).


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):

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.


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: One can also easily show 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:

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 =

Author: Wolfgang Schreiner
Last Modification: October 4, 1999

previous up next