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|
Do you have some intuition for what |N| seems like compared to 2^|N|? I'm asking because I don't know that I do. If I looked out the window and saw a countable infinity to the west, and an uncountable infinity to the east, could I tell them apart?
ReplyDeleteActually that's right. That's why |R| = 2^|N| = |N|^|N| etc.
DeleteI just thought it was interesting to see that the relationship between the cardinality of a set and that of its powerset scales up to N and R, and that even if the powerset of a countably infinite set is not countable, we can still have a number describing this uncountability (with finite or countable entities: 2^|N|). I think it's just something fun to think about!
Sorry, I just reread your question and realized I answered only the first part.
DeleteIf I looked out the window and saw those two infinities lying about, I would definitely try to show that there is no possible bijection from one to another and that we need an infinite amount of the infinities to the west to make up an infinity as big as that to the east.