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 .
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 this method, but the method can be applied nonetheless.
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).