To my mind, one of the most beautifully elegant ideas of mathematics. It carries on where bog-standard
mathematical induction leaves off, generalising the idea to sets "larger"
1 than the
natural numbers. Here's how it works. It's really very simple once you get past the definitions, which are in themselves
intuitive enough once decoded, so please hold on even if you're not
of a mathematical bent.
First, you'll need to know what a well-ordering on a set is.
First, you'll need to know what a linear ordering on a set is.
First, you'll need to know what a partial ordering on a set is.
First, you'll need to know what a set is. If you're going to to this properly, it gets a bit complicated 2, but to understand this all you really need is the simple idea of a set as "a bunch of things". So examples include the set of all noders, the set of real numbers, and so on.
A partial ordering on a set gives it some structure, by allowing you to (in whatever possibly highly abstract way) compare pairs of elements of the set. An ordering has to be "a bit like" the ordering given by comparing numbers in terms of size, in the senses that nothing can be "less than" (in our abstract sense) itself, and if a is "less than" b, and if b is "less than" c, then a is "less than" c3.
A standard example is the partial ordering on the set of natural numbers (that's the set containing 1, 2, 3 and so on) given by whether one strictly divides into another, as 2 divides into 6 (written 2|6). It's pretty easy to see that a|b & b|c => a|c, and that "strictly" I used in the definition means that a never divides a.
Now, a linear ordering (also known as a total ordering) gets a bit closer to our idea of "less than", by adding a requirement known as trichotomy, which is just that any two distinct elements in the set are comparable. So for any a and b in our set, we have either that a is "less than" b, a is equal to b, or b is "less than" a.
So the division example above is not a linear ordering, since for example 3 doesn't divide 5, but nor does 5 divide 3 and most definitely 3 doesn't equal 5. Examples of linear orderings are all those times you would use the < symbol when talking about numbers - so the real numbers are ordered linearly by <, and the set of noders are linearly ordered by < according to XP.
If you think about it a little, you should see that any linearly ordered set can be imagined as being layed out along a (possibly infinite) line4.
So we're back up to well-orderings. A well-ordering is linear ordering with one extra special property, which allows us to use induction. The property is this - any non-empty subset of a well-ordered set has a
least element. That is, if you choose from the bunch of things which comprise your set another bunch of things, and then apply the same ordering to these as was to the original set, then you'll find a particular element of the subset such that it is "less than" every other element of the subset.
So for example, the rational numbers (the set of fractions) are not well-ordered by <. For example, I could take the subset consisting of all rationals strictly greater than zero. Now suppose this has a least element. Than I can just take half of it, and of course this will still be a rational greater than zero and hence in the subset, but it will also clearly be less than our supposed least element. Similarly, the set of integers (both positive and negative) is not well-ordered by <, since I can always think of an integer less than any candidate for leastness you might give me.
However, I can give the integers a well-ordering, it's just that it won't be that given by <. One neat way of doing this is by "putting the positive integers first", saying that 0 is the least element, then 1, then 2, then... (where that "..." goes on for all the positive integers), then -1, then -2, then ... (for all the negative integers). So in this ordering every positive integer is "less than" every negative integer (you see, those quotation marks are important). It's quite easy to see that this is a well-ordering5.
That's the definition over, now for the transfinite induction itself. The idea is this. We have a well-ordered set, and we want to show that some proposition (let's call it P) is true for every element of it. First, we show that for every element of the set (I'll call it S), if P is true for every element less than it, then P is true for it. This is the equivalent of the inductive step on the natural numbers, but here we make no mention of "+1".
Now, suppose P isn't true for all elements of S. Then consider the subset consisting of those elements for which P is not true. We're supposing this is non-empty. But since the original set is well-ordered, this subset must then have a least element, let's call it l. But then for each element of S less than l, it can't be in the subset (by the leastness of l), so P must be true for it. But that's precisely what we need according to the inductive hypothesis to show that P is true for l. So we have a contradiction, and so we've shown that P is true for every member of the set.
That's it. One of the simplest proofs of one of the most powerful concepts a mathematician will ever have the honour to read. From this comes a huge swathe of set theory - in particular it allows us to properly define and study the ordinals, and hence also the cardinals, and generally to get a grip on the infinite.
1 - Perhaps "longer" would be a better word to use... that is, the difference between mathematical and transfinite induction isn't really one of cardinality, but of order type. Mathematical induction works for orders with ordinals of ω or less, for the rest you need transfinite induction. But note that by the Well Ordering Theorem, any set can have an appropriate ordering imposed on it, and then the question does boil down to one of whether the set is countable or not.
2 - Though also very interesting. See, for example, the first two write-ups on set theory
3 - Note that I'm using strict orderings here, because they make the induction proof simpler. Sometimes these concepts are presented with non-strict orderings, which are like "less than or equal to" rather than "less than". This is very much a meaningless technicality. Note also that the concept of a well-order applies not just to linear orderings - see ariels's writeup on well-ordered.
4 - Hence the name.
5 - In fact, not just the integers but any set can be given a well-ordering, as guaranteed by the Well Ordering Theorem, though that uses the Axiom of Choice and in general doesn't give orderings anywhere near as neat as this one (or indeed ones about which anything can be determined at all).