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 a<ba < b be real numbers. We want to show that [a,b]=S[a, b] = S. That is, we want all elements of the interval to “satisfy” property SS. We define the subset S[a,b]S \subseteq [a,b] to be inductive if:

  1. aSa \in S.
  2. If ax<ba \leq x < b, then xS    [x,y]Sx \in S \implies [x,y] \subset S for some y>xy > x.
  3. If a<xba < x \leq b and [a,x)S[a,x) \subset S, then xSx \in S.

The result is that a subset S[a,b]S \subset [a,b] is inductive if and only if S=[a,b]S = [a,b].

Example

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.

Assumptions

Consider the following assumptions on two functions v:R2Rv: \mathbb{R}^2 \to \mathbb{R} (the value of the prize) and c:RRc: \mathbb{R} \to \mathbb{R} (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 v(s;y)v(s; y) and c(s)c(s) are continuously differentiable in ss and continuous in yy for all ss and ysy \leq s.

Assumption 2 (A2, Monotonicity)

v(s;y)<c(s)v'(s; y) < c'(s)

holds a.e., where we define v(s;y):=v(s;y)sv'(s; {y}) := \frac{\partial v(s; {y})}{\partial s}.

Assumption 3 (A3, Interiority)

v(0,0)>c(0)=0v(0, 0) > c(0) = 0 and limssupysv(s;y)<limsc(s).\lim_{s \to \infty} \sup_{y \leq s} v(s; {y}) < \lim_{s \to \infty} c(s).

Assumption 4 (A4, Positive value on the margin)

v(s;s)>0v(s; s) > 0

Statement of the lemma

Lemma (Probability density) The solution, g(s)g(s), to

g(s)=1v(s;s)(c(s)0sv(s,y)g(y)dy)g(s) = \frac{1}{v(s; s)} \left( c'(s) - \int_0^{s} v'(s , y) \lvert g(y) \rvert dy \right)

is a probability density on some interval [0,sˉ][0, \bar{s}].

Proof

The finite definite integral cannot diverge because the function is continuous and g(0)=c(0)v(0;0)>0g(0) = \frac{c'(0)}{v(0; 0)} > 0.

We still need to confirm that g(s)>0g(s) > 0 on the relevant interval {s:0sg(y)dy1}\{ s : \int_0^s \lvert g(y) \rvert dy \leq 1 \}. 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 [0,T][0,T] where TT can be any value such that 0Tg(y)dy1\int_0^T \lvert g(y) \rvert dy \leq 1. We must prove the following statements:

  1. g(0)>0g(0) > 0.
  2. For any s[0,T]s \in [0,T], if g(y)>0g(y) > 0 for all y[0,s]y \in [0,s], then there exists a z>sz > s such that g(y)>0g(y) > 0 for all y[s,z)y \in [s,z).
  3. For any s[0,T]s \in [0,T], if g(y)>0g(y) > 0 for all y[0,s)y \in [0,s), then g(s)>0g(s) > 0.

The first statement is true because g(0)=c(0)v(0;0)>0g(0) = \frac{c'(0)}{v(0; 0)} > 0. The second statement proceeds by continuity of gg (A1). The third statement comes from:

g(s)=1v(s;s)(c(s)0sv(s,y)g(y)dy)g(s) = \frac{1}{v(s; s)} \left( c'(s) - \int_0^{s} v'(s , y) \lvert g(y) \rvert dy \right) g(s)1v(s;s)[c(s)maxy[0,s]v(s;y)(0sg(y)dy)1]g(s) \geq \frac{1}{v(s; s)} \bigg[ c'(s) - \lvert \max_{y\in[0,s]} v'(s; y) \rvert \underbrace{\left( \int_0^{s} \lvert g(y) \rvert dy \right)}_{\leq 1} \bigg] g(s)1v(s;s)[c(s)maxyv(s;y)]>0(A2)>0.g(s) \geq \frac{1}{v(s; s)} \underbrace{\left[c'(s) - \lvert \max_y v'(s; y) \rvert \right]}_{>0 \text{(A2)}} > 0.

Therefore, g(s)>0g(s) > 0 for any ss such that 0sg(y)dy1\int_0^s \lvert g(y) \rvert dy \leq 1.

To complete the lemma, we must show that it is not possible for 0g(y)dy1\int_0^\infty \lvert g(y) \rvert dy \leq 1. We can do this in one step with Holder’s inequality.

c(s)=0sv(s;y)g(y)dy(0sg(y)dy)(maxy[0,s]v(s;y))c(s) = \int_0^s v(s; y) g (y) dy \leq \left(\int_0^s \lvert g(y) \rvert dy\right) \left( \max_{y \in [0,s]} v(s; y) \right)

so 0sg(y)dyc(s)maxv(s;y)\int_0^s \lvert g(y) \rvert dy \geq \frac{c(s)}{\max v(s; y)} which is assumed to be greater than one as ss approaches infinity (A3). By continuity, there exists an sˉ\bar{s} such that 0sˉg(y)dy=1\int_0^{\bar{s}} \lvert g (y) \rvert dy = 1 (A1).


github mail linkedin gscholar pdf slides