Bar induction

Bar induction

Bar induction is a reasoning principle used in intuitionistic mathematics, introduced by L.E.J. Brouwer.It is useful in giving constructive versions of classical 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 sequences 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.


* S.C. Kleene, R.E. Vesley, "The foundations of intuitionistic mathematics: especially in relation to recursive functions" , North-Holland (1965)
* Michael Dummett, "Elements of intuitionism", Clarendon Press (1977)
* A. S. Troelstra, "Choice sequences", Clarendon Press (1977)
* [ Bar induction] , article on "Encyclopaedia of Mathematics", Edited by Michiel Hazewinkel, Springer-Verlag (2002)

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Induction forging — refers to the use of induction heating to pre heat metals prior to deformation using a press or hammer. Typically metals are heated to between 1100˚C and 1200˚C to increase their malleability and aid flow in the forging die.Induction Forging… …   Wikipedia

  • Induction hardening — is a form of heat treatment in which a metal part is heated by induction heating and then quenched. The quenched metal undergoes a martensitic transformation, increasing the hardness and brittleness of the part. Induction hardening is used to… …   Wikipedia

  • induction — Magnetic Mag*net ic, Magnetical Mag*net ic*al, a. [L. magneticus: cf. F. magn[ e]tique.] 1. Pertaining to the magnet; possessing the properties of the magnet, or corresponding properties; as, a magnetic bar of iron; a magnetic needle. [1913… …   The Collaborative International Dictionary of English

  • induction hardening — a widely used process for the surface hardening of steel. The components are heated by means of an alternating magnetic field to a temperature within or above the transformation range followed by immediate quenching. The core of the component… …   Mechanics glossary

  • Faraday's law of induction — For the relationship between a time varying magnetic field and an induced electric field, see Maxwell s equations. Electromagnetism …   Wikipedia

  • El Farol Bar problem — El Farol in Santa Fe The El Farol bar problem is a problem in game theory. Based on a bar in Santa Fe, New Mexico, it was created in 1994 by W. Brian Arthur. The problem is as follows: There is a particular …   Wikipedia

  • Problème du bar d'El Farol — Le problème du bar d El Farol a été créé en 1994 par l économiste Brian Arthur, chercheur à l Institut de Santa Fe, pour étudier la modélisation de systèmes économiques où les agents ont une rationalité limitée et utilisent un raisonnement par… …   Wikipédia en Français

  • flinders bar — “ noun Usage: usually capitalized F Etymology: after Matthew Flinders died 1814 English mariner : a soft iron bar or bundle of soft iron rods placed vertically near a ship s compass to counteract deviation due to magnetic induction from the earth …   Useful english dictionary

  • Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.