Go backward to 6.1 Further Notions
Go up to 6 More on Functions
Go forward to 6.3 Embedding Sets
|
Go backward to 6.1 Further Notions Go up to 6 More on Functions Go forward to 6.3 Embedding Sets |
|
A set is infinite (unendlich) if is not finite:
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).
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.
(forall S != 0, n in N, m in N, f: Nn ->bijective S, g: Nm ->bijective S: m = n).
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).
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.
f(0) := 0 f(1) := 2 f(2) := 4
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.
#x: Fis 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).
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 intersection B = 0 /\ |A| = m /\ |B| = n) => |A union 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 x B| = m*n.
If A is of size n, then A has 2n subsets:
forall A, B, m in N, n in N: (|A| = m /\ |B| = n) => |A -> B| = nm.
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.
S is countable : <=> exists f: f: N ->bijective S.
i.e.,
f(x) := if x is even then -x/2 else (x+1)/2
f = [0, 1, -1, 2, -2, 3, -3, ...].
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).
1/1 1/2 1/3 1/4 ... / / / 2/1 2/2 2/3 ... ... / / 3/1 3/2 ... ... ... / 4/1 ... ... ... ... ... ... ... ... ...
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
i.e.,
g(x) := if x = 0 then 0 else if x is even then -f'(x/2) else f'((x-1)/2)
g = [0, 1, -1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, ...].
s(i) := f(i)iwhere 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.
The argument called diagonalization (Diagonalisierung) has been invented by Cantor to show the following result.
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,...]
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.
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 | |.
|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.
The hierarchy of "infiniteness" is not limited, because we can construct for every (also infinite) set a still larger set.
forall S: S is smaller than P(S).
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.
f: S ->injective P(S) f(x) := {x}.
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.
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.
p is permutation of length n : <=> p: Nn ->bijective Nn.
p o s = [b, a, e, d, c].
Logic Evaluator Permutations can be easily implemented as follows.
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.
The inverse of a permutation is a permutation of the same 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.
forall n in N, p: p is permutation of length n => p-1 is permutation of length n.
p o q = [1,2,0,4,3],e.g., (p o q)(2) = q(p(2)) = q(4) = 0. We also have
e.g., p-1(2) = 1 because p(1)=2, and thus
p-1 = [2,0,1,4,3]
p o p-1 = p-1 o p = [0,1,2,3,4].
The following establishes some basic combinatorial knowledge.
forall n in N: |{f: f is permutation of length n}| = 2n.
If n=0, then the only permutation is p = [ ].
Assume |{f: f is permutation of length n}| = 2n.
We define
which returns the sequence constructed from f by inserting element x at position i.
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)
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)!