Bar recursion: Difference between revisions

Revision as of 15:32, 24 September 2012

Revision as of 19:35, 18 February 2013

Line 16:

The idea is that one extends the sequence arbitrarily, using the recursion term ''B'' to determine the effect, until a sufficiently long node of the tree of sequences over '''V''' is reached; then the base term ''L'' determines the final value of ''f''. The well-definedness condition corresponds to the requirement that every infinite path must eventually pass though a sufficiently long node: the same requirement that is needed to invoke a bar induction.

The principles of bar induction and bar recursion are the intuitionistic equivalents of the axiom of [[dependent choice]]s.<ref>{{cite book|authors=[[Jeremy Avigad]], [[Solomon Feferman]]|chapter=VI: GodelGödel's functional ("Dialectica") interpretation|title=''Handbook of Proof Theory''|editor=[[S. R. Buss]]|year=1999|url=http://math.stanford.edu/~feferman/papers/dialectica.pdf}}</ref>

==References==