Chuangjie Xu, November 2026
We construct a Spector bar recursor for each bar-continuous control functional.
Following the approach of Paulo Oliva and Silvia Steila in "A direct proof of
Schwichtenberg's bar recursion closure theorem" (2018, Theorem 2.4), we derive
Spector's bar recursion from general bar recursion.
Oliva and Steila construct a System T term for the recursor from a System T
term for the control. Here we construct an Agda term for the recursor from
a witness that the control is bar continuous.
TODO. Investigate whether Spector bar recursors for bar-continuous control
functionals can be obtained more simply from the modified bar recursors
constructed in InductiveBars.ModifiedBarRecursion. Berger and Oliva's
result that Spector's bar recursion is definable from modified bar recursion
("Modified bar recursion", 2006, Theorem 6.5) suggests a possible route.
\begin{code}
{-# OPTIONS --without-K --safe #-}
open import MLTT.Spartan hiding (π€ ; π¦)
open import UF.FunExt using (Fun-Ext ; dfunext)
module InductiveBars.SpectorBarRecursion
(fe : Fun-Ext)
{π€ : Universe}
(A : π€ Μ)
where
open import MLTT.List
open import Naturals.Order
open import InductiveBars.Sequences hiding (pad)
open import InductiveBars.Basics
open import InductiveBars.Continuity A β
\end{code}
A witness of `V controls-recursion-at s` describes the possible recursive
calls starting at s. Along each branch, recursion stops at the first
extension of s that belongs to V.
\begin{code}
data _controls-recursion-at_ {π₯ : Universe} (V : List A β π₯ Μ)
: List A β π€ β π₯ Μ
where
stop : {s : List A}
β s β V
β V controls-recursion-at s
continue : {s : List A}
β s β V
β ((a : A) β V controls-recursion-at (s ++ [ a ]))
β V controls-recursion-at s
\end{code}
For decidable V, if V bars s, then V controls recursion at s.
\begin{code}
bars-implies-controls-recursion-at
: (V : List A β π₯ Μ) β ((s : List A) β is-decidable (s β V))
β (s : List A) β V bars s β V controls-recursion-at s
bars-implies-controls-recursion-at V dec s (hit p) = stop p
bars-implies-controls-recursion-at V dec s (step Ο) =
cases stop (Ξ» q β continue q ih) (dec s)
where
ih : (a : A) β V controls-recursion-at (s ++ [ a ])
ih a = bars-implies-controls-recursion-at V dec (s ++ [ a ]) (Ο a)
\end{code}
We evaluate recursively on a witness of `V controls-recursion-at s`.
The following definition shows how the witness determines when to stop
and when to continue.
\begin{code}
module _ {π¦ : Universe} (X : π¦ Μ) where
eval : {V : List A β π₯ Μ}
β (List A β X) β (List A β (A β X) β X)
β (s : List A) β V controls-recursion-at s β X
eval G H s (stop _) = G s
eval G H s (continue _ Ο) = H s (Ξ» a β eval G H (s ++ [ a ]) (Ο a))
\end{code}
Evaluation is independent of the control witness, even when V is not
proposition-valued, because evaluation does not use the data carried by
stop witnesses. We use this independence to verify the recursion equations.
\begin{code}
eval-witness-independent
: {V : List A β π₯ Μ}
β (G : List A β X) (H : List A β (A β X) β X)
β (s : List A) (c c' : V controls-recursion-at s)
β eval G H s c οΌ eval G H s c'
eval-witness-independent G H s (stop p) (stop q) = refl
eval-witness-independent G H s (stop p) (continue q Ο) = π-elim (q p)
eval-witness-independent G H s (continue p Ο) (stop q) = π-elim (p q)
eval-witness-independent G H s (continue p Ο) (continue q Ο)
= ap (H s) (dfunext fe ih)
where
ih : (a : A)
β eval G H (s ++ [ a ]) (Ο a) οΌ eval G H (s ++ [ a ]) (Ο a)
ih a = eval-witness-independent G H (s ++ [ a ]) (Ο a) (Ο a)
\end{code}
If V controls recursion at every finite sequence, we can construct
a general bar recursor for V in the sense of Oliva and Steila, using
the above evaluation function.
\begin{code}
BarRecursor : π€ β π¦ Μ
BarRecursor = (List A β X) β (List A β (A β X) β X) β List A β X
gbr : {B : List A β π₯ Μ}
β ((s : List A) β B controls-recursion-at s)
β BarRecursor
gbr d G H s = eval G H s (d s)
general-bar-recursor-spec
: {B : List A β π₯ Μ} (d : (s : List A) β B controls-recursion-at s)
β (G : List A β X) (H : List A β (A β X) β X) (s : List A)
β (s β B β gbr d G H s οΌ G s)
Γ (s β B β gbr d G H s οΌ H s (Ξ» a β gbr d G H (s ++ [ a ])))
general-bar-recursor-spec {B = B} d G H s = base-case , step-case
where
unique : (e : B controls-recursion-at s) β gbr d G H s οΌ eval G H s e
unique e = eval-witness-independent G H s (d s) e
base-case : s β B β gbr d G H s οΌ G s
base-case p = unique (stop p)
step-case : s β B β gbr d G H s οΌ H s (Ξ» a β gbr d G H (s ++ [ a ]))
step-case q = unique (continue q (Ξ» a β d (s ++ [ a ])))
\end{code}
Now we switch to Spector's bar recursion.
Spector's recursion, controlled by a functional Y : (β β A) β β, stops at
input s when Y (pad s) < length s. Here pad s extends s to an infinite
sequence by repeating a fixed element aβ : A after its last entry. So we
assume a given aβ : A throughout the development of Spector bar recursion.
\begin{code}
module _ (aβ : A) where
private
pad : List A β β β A
pad = pad-with aβ
stopping-prefixes : ((β β A) β β) β List A β π€β Μ
stopping-prefixes Y s = Y (pad s) <β length s
\end{code}
A bar of determining prefixes gives a bar of stopping prefixes.
This result is due to the fact that, once s determines Y, all extensions
of s by Y (pad s) + 1 entries satisfy the stopping condition.
\begin{code}
determining-prefix-gives-stopping-level
: (Y : (β β A) β β) (s : List A)
β s determines Y
β (t : List A) β length t οΌ succ (Y (pad s))
β (s ++ t) β stopping-prefixes Y
determining-prefix-gives-stopping-level Y s det t l
= transport (_β€β length u) e' r
where
u : List A
u = s ++ t
e : Y (pad u) οΌ Y (pad s)
e = det (pad u) (pad s)
(extends-++ (pad u) s t (pad-extends u)) (pad-extends s)
e' : length t οΌ succ (Y (pad u))
e' = l β (ap succ e) β»ΒΉ
r : length t β€β length u
r = length-++-right s t
determining-bar-implies-stopping-bar
: (Y : (β β A) β β) (s : List A)
β (determining-prefixes Y) bars s β (stopping-prefixes Y) bars s
determining-bar-implies-stopping-bar Y s (hit det)
= bars-from-level (stopping-prefixes Y) s (succ (Y (pad s)))
(determining-prefix-gives-stopping-level Y s det)
determining-bar-implies-stopping-bar Y s (step Ο) = step ih
where
ih : (a : A) β stopping-prefixes Y bars (s ++ [ a ])
ih a = determining-bar-implies-stopping-bar Y (s ++ [ a ]) (Ο a)
\end{code}
If Y is bar continuous, its stopping prefixes control recursion at every
finite sequence.
\begin{code}
bar-continuity-implies-stopping-prefixes-control-recursion
: (Y : (β β A) β β) β is-bar-continuous Y
β (s : List A) β (stopping-prefixes Y) controls-recursion-at s
bar-continuity-implies-stopping-prefixes-control-recursion Y b s =
bars-implies-controls-recursion-at (stopping-prefixes Y) dec s
(determining-bar-implies-stopping-bar Y s
(bar-continuity-implies-bar-continuityβ³ Y b s))
where
dec : (u : List A) β is-decidable (u β stopping-prefixes Y)
dec u = <-decidable (Y (pad u)) (length u)
\end{code}
Instantiate the general recursor and its equations with Spector's
stopping predicate.
\begin{code}
sbr : (Y : (β β A) β β) β is-bar-continuous Y β BarRecursor
sbr Y b = gbr (bar-continuity-implies-stopping-prefixes-control-recursion Y b)
spector-bar-recursor-spec
: (Y : (β β A) β β) (b : is-bar-continuous Y)
β (G : List A β X) (H : List A β (A β X) β X) (s : List A)
β (Y (pad s) <β length s
β sbr Y b G H s οΌ G s)
Γ (length s β€β Y (pad s)
β sbr Y b G H s οΌ H s (Ξ» a β sbr Y b G H (s ++ [ a ])))
spector-bar-recursor-spec Y b G H s
using (base-case , step-case) β
general-bar-recursor-spec
(bar-continuity-implies-stopping-prefixes-control-recursion Y b) G H s
= base-case , step-case'
where
step-case' : length s β€β Y (pad s)
β sbr Y b G H s οΌ H s (Ξ» a β sbr Y b G H (s ++ [ a ]))
step-case' q = step-case (bigger-or-equal-not-less (length s) (Y (pad s)) q)
\end{code}
Moreover, the above Spector bar recursor is independent of the witness
that the control functional is bar continuous.
\begin{code}
sbr-witness-independent
: (Y : (β β A) β β) (b b' : is-bar-continuous Y)
β (G : List A β X) (H : List A β (A β X) β X) (s : List A)
β sbr Y b G H s οΌ sbr Y b' G H s
sbr-witness-independent Y b b' G H s = eval-witness-independent G H s c c'
where
c c' : stopping-prefixes Y controls-recursion-at s
c = bar-continuity-implies-stopping-prefixes-control-recursion Y b s
c' = bar-continuity-implies-stopping-prefixes-control-recursion Y b' s
\end{code}