Bar induction

Given two predicates ${\displaystyle R}$ and ${\displaystyle A}$ on finite sequences of natural numbers such that all of the following conditions hold:

• every choice sequence contains at least one initial segment satisfying ${\displaystyle R}$ at some point (this is expressed by saying that ${\displaystyle R}$ is a bar);
• ${\displaystyle R}$ is decidable (i.e. our bar is decidable);
• every finite sequence satisfying ${\displaystyle R}$ also satisfies ${\displaystyle A}$ (so ${\displaystyle A}$ holds for every choice sequence beginning with the aforementioned finite sequence);
• if all extensions of a finite sequence by one element satisfy ${\displaystyle A}$, then that finite sequence also satisfies ${\displaystyle A}$ (this is sometimes referred to as ${\displaystyle A}$ being upward hereditary);

then we can conclude that ${\displaystyle A}$ holds for the empty sequence (i.e. A holds for all choice sequences starting with the empty sequence).

This principle of bar induction is favoured in the works of, A. S. Troelstra, S. C. Kleene and Albert Dragalin.

Given two predicates ${\displaystyle R}$ and ${\displaystyle A}$ on finite sequences of natural numbers such that all of the following conditions hold:

• every choice sequence contains a unique initial segment satisfying ${\displaystyle R}$ at some point (i.e. our bar is thin);
• every finite sequence satisfying ${\displaystyle R}$ also satisfies ${\displaystyle A}$;
• if all extensions of a finite sequence by one element satisfy ${\displaystyle A}$, then that finite sequence also satisfies ${\displaystyle A}$;

then we can conclude that ${\displaystyle A}$ holds for the empty sequence.

This principle of bar induction is favoured in the works of Joan Moschovakis and is (intuitionistically) provably equivalent to decidable bar induction.

Given two predicates ${\displaystyle R}$ and ${\displaystyle A}$ on finite sequences of natural numbers such that all of the following conditions hold:

• every choice sequence contains at least one initial segment satisfying ${\displaystyle R}$ at some point;
• once a finite sequence satisfies ${\displaystyle R}$, then every possible extension of that finite sequence also satisfies ${\displaystyle R}$ (i.e. our bar is monotonic);
• every finite sequence satisfying ${\displaystyle R}$ also satisfies ${\displaystyle A}$;
• if all extensions of a finite sequence by one element satisfy ${\displaystyle A}$, then that finite sequence also satisfies ${\displaystyle A}$;

then we can conclude that ${\displaystyle A}$ holds for the empty sequence.

This principle of bar induction is used in the works of A. S. Troelstra, S. C. Kleene, Dragalin and Joan Moschovakis.

The following results about these schemata can be intuitionistically proved:

${\displaystyle {\begin{aligned}BI_{M}&\vdash BI_{D}\\[3pt]BI_{D}&\vdash BI_{T}\\[3pt]BI_{T}&\vdash BI_{D}\end{aligned}}}$

(The symbol "${\displaystyle \,\vdash \,}$" is a "turnstile".)

An additional schema of bar induction was originally given as a theorem by Brouwer (1975) containing no "extra" restriction on ${\displaystyle R}$ under the name The Bar Theorem. However, the proof for this theorem was erroneous, and unrestricted bar induction is not considered to be intuitionistically valid (see Dummett 1977 pp 94–104 for a summary of why this is so). The schema of unrestricted bar induction is given below for completeness.

Given two predicates ${\displaystyle R}$ and ${\displaystyle A}$ on finite sequences of natural numbers such that all of the following conditions hold:

• every choice sequence contains at least one initial segment satisfying ${\displaystyle R}$ at some point;
• every finite sequence satisfying ${\displaystyle R}$ also satisfies ${\displaystyle A}$;
• if all extensions of a finite sequence by one element satisfy ${\displaystyle A}$, then that finite sequence also satisfies ${\displaystyle A}$;

then we can conclude that ${\displaystyle A}$ holds for the empty sequence.