Bar induction is a reasoning principle used in intuitionistic mathematics

Intuitionism

In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...

, introduced by L.E.J. Brouwer.
It is useful in giving constructive versions of classical

Classical logic

Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...

 results.
It is based on an inductive argument.

The goal of the principle is to prove properties of infinite streams of natural numbers, called choice sequence

Choice sequence

In intuitionistic mathematics, a choice sequence is a constructive formulation of a sequence. Since the Intuitionistic school of mathematics, as formulated by L. E. J...

s in intuitionistic terminology, by inductively reducing them to decidable properties of finite lists.

Given two predicates R and S on finite lists of natural numbers, assume the following conditions hold:

• R is decidable;
• Every choice sequence has a finite prefix satisfying R (this is expressed by saying that R is a bar);
• Every list satisfying R also satisfies S;
• If all extensions of a list by one element satisfy S, then that list also satisfies S.

Then we can conclude that S holds for the empty list.