Here, we want to generalise the notion of induction.
Mathematical induction (simple and complete) works by exploiting the well-ordering principle (of the natural numbers). A first (natural) generalisation would be to extend the notion to any well-ordered set, that is: a totally ordered set (a set with a total order) such that any non-empty subset of it has a smallest element. This generalisation is called Transfinite Induction, and it works by exploiting the well-orderedness of a set (furthermore, both are equivalent - the same way mathematical induction is equivalent to the well-ordering principle).
I suppose that the name derives from its most useful / original purpose: induction on transfinite numbers, such as transfinite ordinals (infinite numbers that describe position) and transfinite cardinals (infinite numbers that describe size, such as aleph_naught = |N| that we mentioned last time). Together ordinals and cardinals form a (set-theoretic) extension of the natural numbers (to describe 'relative positioning of elements' and size of infinite sets); and whereas mathematical induction works on finite ordinals (= finite cardinals = natural numbers), it fails on infinite ords and cards.
Most proofs by transfinite induction are thus limited to the realm of set theory, but there are some non set-theoretic proofs too! Check out http://www.mathnerds.com/best/Mazurkiewicz/index.aspx to learn if it is possible to construct a subset of the plane such that every line intersects that subset exactly twice!
Another way to extend the principle of induction would be to look at a stronger (= broader) notion of well-ordering. Since a well-order is a well-founded total order, we might want to include well-founded partial orders as part of our generalisation. This generalisation is called Well-founded Induction (and is the most general we can get). This is a quote from Wikipedia about it:
"As an example, consider the well-founded relation (N, S), where N is the set of all natural numbers, and S is the graph of the successor function x → x + 1. Then induction on S is the usual mathematical induction, and recursion on S gives primitive recursion. If we consider the order relation (N, <), we obtain complete induction, and course-of-values recursion. The statement that (N, <) is well-founded is also known as the well-ordering principle.
There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction. When the well-founded relation is set membership on the universal class, the technique is known as epsilon-induction. See those articles for more details." -- http://en.wikipedia.org/wiki/Well-founded
Hence, Structural Induction is concerned by a subset of that generalisation, namely structures with a well-founded partial order (coming from the fact they are recursively defined, e.g. the Fibonacci numbers). Thus, in structural induction, we prove that a property holds for the smallest structure, and that it holds for a greater structure when it holds for its substructures, to prove that it holds for any structure of that type.
Further self-questioning: which generalisation seems the most natural to you? why does transfinite induction seem like a more natural generalisation than structural induction even though SI is clearly more intuitive then TI? does a total order exist on the set of all generalisations of induction such that in any subset of them there is a least 'natural' element?
Mathematical induction (simple and complete) works by exploiting the well-ordering principle (of the natural numbers). A first (natural) generalisation would be to extend the notion to any well-ordered set, that is: a totally ordered set (a set with a total order) such that any non-empty subset of it has a smallest element. This generalisation is called Transfinite Induction, and it works by exploiting the well-orderedness of a set (furthermore, both are equivalent - the same way mathematical induction is equivalent to the well-ordering principle).
I suppose that the name derives from its most useful / original purpose: induction on transfinite numbers, such as transfinite ordinals (infinite numbers that describe position) and transfinite cardinals (infinite numbers that describe size, such as aleph_naught = |N| that we mentioned last time). Together ordinals and cardinals form a (set-theoretic) extension of the natural numbers (to describe 'relative positioning of elements' and size of infinite sets); and whereas mathematical induction works on finite ordinals (= finite cardinals = natural numbers), it fails on infinite ords and cards.
Most proofs by transfinite induction are thus limited to the realm of set theory, but there are some non set-theoretic proofs too! Check out http://www.mathnerds.com/best/Mazurkiewicz/index.aspx to learn if it is possible to construct a subset of the plane such that every line intersects that subset exactly twice!
Another way to extend the principle of induction would be to look at a stronger (= broader) notion of well-ordering. Since a well-order is a well-founded total order, we might want to include well-founded partial orders as part of our generalisation. This generalisation is called Well-founded Induction (and is the most general we can get). This is a quote from Wikipedia about it:
"As an example, consider the well-founded relation (N, S), where N is the set of all natural numbers, and S is the graph of the successor function x → x + 1. Then induction on S is the usual mathematical induction, and recursion on S gives primitive recursion. If we consider the order relation (N, <), we obtain complete induction, and course-of-values recursion. The statement that (N, <) is well-founded is also known as the well-ordering principle.
There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction. When the well-founded relation is set membership on the universal class, the technique is known as epsilon-induction. See those articles for more details." -- http://en.wikipedia.org/wiki/Well-founded
Hence, Structural Induction is concerned by a subset of that generalisation, namely structures with a well-founded partial order (coming from the fact they are recursively defined, e.g. the Fibonacci numbers). Thus, in structural induction, we prove that a property holds for the smallest structure, and that it holds for a greater structure when it holds for its substructures, to prove that it holds for any structure of that type.
Further self-questioning: which generalisation seems the most natural to you? why does transfinite induction seem like a more natural generalisation than structural induction even though SI is clearly more intuitive then TI? does a total order exist on the set of all generalisations of induction such that in any subset of them there is a least 'natural' element?
No comments:
Post a Comment