Here, we examine a fundamental property of discrete mathematics.
At the heart of theoretical CS and discrete math is the set of natural numbers. A core structural aspect of the set is the principle of well-ordering, that is that every non-empty subset has a smallest element. It is thus possible to define a total order over the natural numbers, and this leads us to mathematical induction: we can use the ordering to prove statements inductively.
Simple induction consists of proving a property for a base case (initial subset) and for an inductive step (if a property holds at a given subset, it will hold for a subset one increment greater). Using the fact that the sizes of these subsets are ordered, we can deduce properties on a countably infinite set!
Complete induction is similar but requires considering every subset smaller than the given subset in the inductive step.
We can prove very interesting (structural) properties thanks to mathematical induction, such as the cardinality of a powerset:
for all n in N, P(n): "for all s, |s| = n => Power(s) = 2^n"
> Base case: Power({}) = |{{}}| = 1 = 2^0 => P(0)
> Inductive step:
Assume n in N.
Assume P(n)
Assume S such that |S| = n+1
Let X and t such that X = S\{t} (i.e. S = X U {t})
Then |X| = n
Partition Power(S) as follows: (1)
Let S- = {S in Power(S)| t not in S}
Let S+ = {S in Power(S)| t in S}
Then S- = Power(X)
Then |S-| = |Power(X)| = 2^n (2)
# because of the induction hypothesis
Let f: S- -> S+
x |-> x U {t}
We can easily show that this function is a bijection by
proving by contradiction that it is one-to-one and by
contradiction that it is onto
Then f(S-) = S+
Then |S-| = |S+| (3)
From (1), (2) and (3): Power(S) = |S-| + |S+| = 2^n+1
We generalize: for all s, |s| = n+1 => Power(s) = 2^n+1
Thus P(n) => P(n+1)
We generalize: for all n, P(n) => P(n+1)
> Conclusion: By the principle of SI:
[P(0) and P(n)=>P(n+1)] => for all n, P(n)
This result can be applied to finite sets as well as countably infinite sets. For instance, Cantor showed that the cardinality of R is the same as the cardinality of the power set of N (there is a bijection from one to the other), hence we can get a superficial idea of how big the continuum is in relation to the cardinality of N: |R|=2^|N|
At the heart of theoretical CS and discrete math is the set of natural numbers. A core structural aspect of the set is the principle of well-ordering, that is that every non-empty subset has a smallest element. It is thus possible to define a total order over the natural numbers, and this leads us to mathematical induction: we can use the ordering to prove statements inductively.
Simple induction consists of proving a property for a base case (initial subset) and for an inductive step (if a property holds at a given subset, it will hold for a subset one increment greater). Using the fact that the sizes of these subsets are ordered, we can deduce properties on a countably infinite set!
Complete induction is similar but requires considering every subset smaller than the given subset in the inductive step.
We can prove very interesting (structural) properties thanks to mathematical induction, such as the cardinality of a powerset:
for all n in N, P(n): "for all s, |s| = n => Power(s) = 2^n"
> Base case: Power({}) = |{{}}| = 1 = 2^0 => P(0)
> Inductive step:
Assume n in N.
Assume P(n)
Assume S such that |S| = n+1
Let X and t such that X = S\{t} (i.e. S = X U {t})
Then |X| = n
Partition Power(S) as follows: (1)
Let S- = {S in Power(S)| t not in S}
Let S+ = {S in Power(S)| t in S}
Then S- = Power(X)
Then |S-| = |Power(X)| = 2^n (2)
# because of the induction hypothesis
Let f: S- -> S+
x |-> x U {t}
We can easily show that this function is a bijection by
proving by contradiction that it is one-to-one and by
contradiction that it is onto
Then f(S-) = S+
Then |S-| = |S+| (3)
From (1), (2) and (3): Power(S) = |S-| + |S+| = 2^n+1
We generalize: for all s, |s| = n+1 => Power(s) = 2^n+1
Thus P(n) => P(n+1)
We generalize: for all n, P(n) => P(n+1)
> Conclusion: By the principle of SI:
[P(0) and P(n)=>P(n+1)] => for all n, P(n)
This result can be applied to finite sets as well as countably infinite sets. For instance, Cantor showed that the cardinality of R is the same as the cardinality of the power set of N (there is a bijection from one to the other), hence we can get a superficial idea of how big the continuum is in relation to the cardinality of N: |R|=2^|N|
