Real InductionMatthew W. Thomas Real Induction
Conventional proof by induction allows you to prove that a statement applies to an infinite sequence. The argument is that if a property holds on the first element, and always holds on the next element, then it must hold on all elements.
But what do you do when there is no next element?
Some notes on the arXiv show that there is an analogous version to proof by induction that can apply to uncountable sets like the Real numbers. Conventional induction cannot work on uncountable set because, by definition, you cannot reach all elements by iteratively stepping through them.
In the real induction, we get around this issue by breaking the space into countably many intervals. Formally, let be real numbers. We want to show that . That is, we want all elements of the interval to “satisfy” property . We define the subset to be inductive if:
- If , then for some .
- If and , then .
The result is that a subset is inductive if and only if . So, if conditions 1-3 hold, then property is satisfied on .
Intuition and alternative
Most people do not know what real induction is. However, the logic behind it is very easy to understand. So, applying real induction directly is usually not the clearest way to write a proof. The underlying idea behind real induction can be found in many proofs. However, it is rarely referred to as real induction. Typically, people use a proof by contradiction that goes something like this:
Suppose, by way of contradiction, that there exists an element in that is not in . Then, there must be a first switching point. That is, there must be a minimal such that either or for some . Then, we need to prove
- (using 1 and 2 from real induction). Therefore, because is the first switching point.
- If then, (using 3 from real induction). Therefore, for some .
- There exists a such that (using 2 from real induction).
Therefore, any point such that , , and is both in and not in . This is a contradiction.
Proving statements directly in this way is clearer to people unfamiliar with real induction. This is especially true when you express the above argument in terms of your problem.
As an example, we will apply this method to prove a lemma in my current working paper. The proof in the paper does not use real induction directly. It instead uses the direct argument expressed in the previous section. In this section, we will apply real induction in order to demonstrate the method.
In this paper, we show that a particular candidate probability density is the distribution for the Nash equilibrium for a class of auctions. In this lemma, we want to prove that this candidate can be a probability density – i.e. it’s positive and integrates to one.
Consider the following assumptions on two functions (the value of the prize) and (the cost of bidding). In the auction context, these assumptions basically say that bids are costly (A2), the prize attracts bids that are greater than zero and less than infinity (A3), and you would prefer to win the prize than lose it (A4).
Assumption 1 (A1, Smoothness)
The function and are continuously differentiable in and continuous in for all and .
Assumption 2 (A2, Monotonicity)
holds a.e., where we define .
Assumption 3 (A3, Interiority)
Assumption 4 (A4, Positive value on the margin)
Statement of the lemma
Lemma (Probability density) The solution, , to
is a probability density on some interval .
The finite definite integral cannot diverge because the function is continuous and .
We still need to confirm that on the relevant interval . We will define the probability density to be zero outside this interval so that it integrates to one.
We show this by real induction on the interval where can be any value such that . We must prove the following statements:
- For any $, if for all $, then there exists a such that for all .
- For any $, if for all $, then .
The first statement is true because . The second statement proceeds by continuity of (A1). The third statement comes from:
Therefore, for any such that .
To complete the lemma, we must show that it is not possible for . We can do this in one step with Holder’s inequality.
so which is assumed to be greater than one as approaches infinity (A3). By continuity, there exists an such that (A1).