Content deleted Content added
No edit summary |
Tom.Reding (talk | contribs) m →Technical Definition: Fix Category:CS1 maint: Uses authors parameter: vauthors/veditors or enumerate multiple authors/editors; WP:GenFixes on, enum'd 3 author/editor WLs, using AWB |
||
Line 10:
Here "cat" is the [[concatenation]] function, sending ''p'', ''x'' to the sequence which starts with ''p'', and has ''x'' as its last term.
(This definition is based on the one by Escardó and Oliva.<ref>{{cite journal|
Provided that for every sufficiently long function (λα)''r'' of type '''V'''<sup>''i''</sup> → '''R''', there is some ''n'' with ''L''<sub>''n''</sub>(''r'') = ''B''<sub>''n''</sub>((λα)''r'', (λ''x'':'''V''')''L''<sub>''n''+1</sub>(''r'')), the bar induction rule ensures that ''f'' is well-defined.
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|
==References==
| |||