Chuangjie Xu, November 2026

We prove Brouwer’s thesis for monotone bars with bar-continuous witnesses.

This development is motivated by Jonathan Sterling's "Higher order functions
and Brouwer's thesis" (2021).

\begin{code}

{-# OPTIONS --without-K --safe #-}

open import MLTT.Spartan hiding (𝓤)

module InductiveBars.BrouwersThesis
 {𝓤 : Universe}
 (A : 𝓤 ̇)
 where

open import MLTT.List
open import Naturals.Order

open import InductiveBars.Sequences
open import InductiveBars.Basics
open import InductiveBars.Continuity A ℕ

\end{code}

At an arbitrary root s, we transform a bar of determining prefixes into
a bar in V.

\begin{code}

brouwers-thesis-at-prefix
 : (V : List A → 𝓥 ̇) → is-monotone V
 → (f : (ℕ → A) → ℕ)
 → ((α : ℕ → A) → prefix (f α) α ∈ V)
 → (s : List A) → (determining-prefixes f) bars s → V bars s
brouwers-thesis-at-prefix V m f wit s (hit det) = step φ
 where
  claim₀ : (a : A) → (t : List A) → length t = f (pad-with a s) → (s ++ t) ∈ V
  claim₀ a t e = transport (_∈ V) eq p
   where
    r : List A
    r = s ++ t
    α : ℕ → A
    α = pad-with a r
    e' : f α = f (pad-with a s)
    e' = det α (pad-with a s) (extends-++ α s t (pad-extends r)) (pad-extends s)
    q : f α ≤ℕ length r
    q = transport (_≤ℕ length r) (e ∙ e' ⁻¹) (length-++-right s t)
    decomposition : Σ u ꞉ List A , prefix (f α) α ++ u = r
    decomposition = extends-prefix-decomposition α r (f α) (pad-extends r) q
    u : List A
    u = pr₁ decomposition
    eq : prefix (f α) α ++ u = r
    eq = pr₂ decomposition
    p : (prefix (f α) α ++ u) ∈ V
    p = m (prefix (f α) α) u (wit α)
  claim₁ : A → V bars s
  claim₁ a = bars-from-level V s (f (pad-with a s)) (claim₀ a)
  φ : (a : A) → V bars (s ++ [ a ])
  φ a = monotone-bars-extend V m s a (claim₁ a)
brouwers-thesis-at-prefix V m f wit s (step φ)
 = step (λ a → brouwers-thesis-at-prefix V m f wit (s ++ [ a ]) (φ a))

\end{code}

Then we obtain Brouwer’s thesis for monotone bars with bar-continuous witnesses.

\begin{code}

brouwers-thesis-for-bar-continuous-witnesses″
 : (V : List A → 𝓥 ̇) → is-monotone V
 → (f : (ℕ → A) → ℕ) → is-bar-continuous″ f
 → ((α : ℕ → A) → prefix (f α) α ∈ V)
 → (s : List A) → V bars s
brouwers-thesis-for-bar-continuous-witnesses″ V m f bc wit s
 = brouwers-thesis-at-prefix V m f wit s (bc s)

brouwers-thesis-for-bar-continuous-witnesses
 : (V : List A → 𝓥 ̇) → is-monotone V
 → (f : (ℕ → A) → ℕ) → is-bar-continuous f
 → ((α : ℕ → A) → prefix (f α) α ∈ V)
 → is-inductive-bar V
brouwers-thesis-for-bar-continuous-witnesses V m f bc wit
 = bars-root-implies-inductive-bar V
    (brouwers-thesis-for-bar-continuous-witnesses″ V m f
      (bar-continuity-implies-bar-continuity″ f bc)
      wit [])

\end{code}