Normally, in my experience, induction is only used when n, or whatever variable you are using, is an integer. Is there an analogous technique that you can use when n is a real? In fact, is there an inductive technique used for proofs on any set other than the integers, i.e. the complex numbers etc.?
(My terminology may not be correct, please forgive me).
The general notion of induction is related to sets which are constructed by some small number of rules from some small number of basic cases. The induction you’re thinking about actually doesn’t work over the integers, but over the natural numbers. Here’s how it works.
Every natural number is either zero or the successor of another natural number. Thus if something is true for zero (the base case) and is preserved by the operation of taking the successor then it’s true for all natural numbers (since each one eventually gets back to zero by looking at the number it’s the successor of).
Here’s another example: lambda-expressions, which come up in computability theory. Variables (like x, y, x’, x[sub]3[/sub],…) are valid lambda-expressions. Given two valid lambda-expressions M and N, then (M)N is a valid lambda-expression. Given a valid lambda-expression M and a variable x then ^x.M (^ should be a lowercase lambda) is a valid lambda-expression.
Now, what this means is unimportant. The idea, though, is that one can prove statements about all valid lambda-expressions by proving them for variables and proving that if they’re true for M and N then they’re true for (M)N and ^x.M as well. Since every expression decomposes eventually to variables under these rules, the proposition will be true for all valid lambda-expressions.
A related thread where this question is answered.
There are forms of induction that could work for R, although I’m not aware of any that are in common usage. Here’s one that might work:
Suppose P(x) is a statement which satisfies the following properties:[ol][li]P(x) is true for 0 < x < 1.P(x) iff P(x + 1).[/ol]Then P(x) is true for any real number.[/li]
I’ve used a form of induction over the nodes of a tree, which goes like this:
Let T be a tree with the following properties:[ol][li]Every leaf of T has the property P.Whenever all the children of a node n have the property P, then n has the property P.[/ol]Then every node in T has the property P.[/li]
As Mathochist mentions, induction works over sets that have a property that’s probably best described as self-similarity, by analogy of how fractals behave.
Actually, induction works over any well-founded partial order. A partially ordered set is well-founded if and only if there is no infinite descending chain. Suppose S is a well-founded partial order and P(x) is a proposition in which x ranges over the elements of S. Assume that whenever P(y) is true for all y < x, then P(x) holds. Then you conclude that P(x) is true for all x in S.
The proof goes as follows. Under the hypotheses, if P(x) is false there is at least one y_1 < x for which P(y_1) is false. But then there must be at least one y_2 < y_1 with P(y_2) false. You must be able to continue in this way to construct an infinite descending chain y_ > y_2 > y_3 > …, which contradicts the well-foundedness. QED
Someone is bound to complain that maybe y_n has no predecessors so you cannot continue the chain. Well if y has no predecessor, then P(z) is vacuoulsy true for all z < y and so P(y) must be true assuming the hypotheses.
Of course the positive integers are well-ordered (that is they are a well-founded total order), but so are all the ordinals up to any fixed ordinal, such as the first uncountable ordinal. I have published at least one paper in which I carried out an induction over a well-founded partial order.