Chuangjie Xu and Martin Escardo, December 2013
Revised in November 2026

We study two formulations of inductive bars on finite sequences over an
arbitrary type A and show that they are logically equivalent.

\begin{code}

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

module InductiveBars.Basics where

open import MLTT.Spartan
open import MLTT.List
open import Naturals.Order

open import InductiveBars.Sequences

\end{code}

We work with type-valued predicates.

\begin{code}

_∈_ : {X : 𝓀 Μ‡} β†’ X β†’ (X β†’ π“₯ Μ‡) β†’ π“₯ Μ‡
x ∈ V = V x

_βˆ‰_ : {X : 𝓀 Μ‡} β†’ X β†’ (X β†’ π“₯ Μ‡) β†’ π“₯ Μ‡
x βˆ‰ V = x ∈ V β†’ 𝟘 {𝓀₀}

_βŠ†_ : {X : 𝓀 Μ‡}
    β†’ (X β†’ π“₯ Μ‡) β†’ (X β†’ 𝓦 Μ‡)
    β†’ 𝓀 βŠ” π“₯ βŠ” 𝓦 Μ‡
V βŠ† W = βˆ€ x β†’ x ∈ V β†’ x ∈ W

infix 50 _∈_ _βˆ‰_
infix 40 _βŠ†_

\end{code}

The first expresses that a predicate V inductively bars a finite sequence s.

A witness of `V bars s` can be viewed as a well-founded tree. Each internal
node has one outgoing edge labelled a for each a : A. The edge labels along
a path from the root to a leaf form a finite sequence t. That leaf carries
a proof that s ++ t belongs to V.

Different trees may witness the same barring assertion, so `V bars s`
need not be a proposition.

\begin{code}

data _bars_ {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) : List A β†’ 𝓀 βŠ” π“₯ Μ‡ where
 hit  : {s : List A} β†’ s ∈ V β†’ V bars s
 step : {s : List A} β†’ ((a : A) β†’ V bars (s ++ [ a ])) β†’ V bars s

\end{code}

A generalization of `step` to any finite depth.

\begin{code}

bars-from-level : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s : List A) (n : β„•)
                β†’ ((t : List A) β†’ length t = n β†’ (s ++ t) ∈ V)
                β†’ V bars s
bars-from-level V s 0 p = hit v'
 where
  v : (s ++ []) ∈ V
  v = p [] refl
  v' : s ∈ V
  v' = transport (_∈ V) (([]-right-neutral s) ⁻¹) v
bars-from-level V s (succ n) p = step ih
 where
  ih : βˆ€ a β†’ V bars (s ++ [ a ])
  ih a = bars-from-level V (s ++ [ a ]) n pα΅’
   where
    pα΅’ : βˆ€ t β†’ length t = n β†’ ((s ++ [ a ]) ++ t) ∈ V
    pᡒ t refl = transport (_∈ V) ((++-assoc s [ a ] t) ⁻¹) (p (a ∷ t) refl)

\end{code}

We say a predicate on finite sequences is monotone if membership is preserved
by appending any finite sequence.  For a monotone predicate V, if V bars the
empty sequence, then V bars every finite sequence.

\begin{code}

is-monotone : {A : 𝓀 Μ‡} β†’ (List A β†’ π“₯ Μ‡) β†’ 𝓀 βŠ” π“₯ Μ‡
is-monotone {A = A} V = (s u : List A) β†’ s ∈ V β†’ (s ++ u) ∈ V

monotone-bars-extend
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) β†’ is-monotone V
 β†’ (s : List A) (a : A)
 β†’ V bars s
 β†’ V bars (s ++ [ a ])
monotone-bars-extend V m s a (hit v) = hit (m s [ a ] v)
monotone-bars-extend V m s a (step Ο†) = Ο† a

monotone-bars-append
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) β†’ is-monotone V
 β†’ (s t : List A)
 β†’ V bars s
 β†’ V bars (s ++ t)
monotone-bars-append V m s [] = transport (V bars_) ([]-right-neutral s)
monotone-bars-append V m s (a ∷ t) b = transport (V bars_) p ih
 where
  claim : V bars (s ++ [ a ])
  claim = monotone-bars-extend V m s a b
  ih : V bars ((s ++ [ a ]) ++ t)
  ih = monotone-bars-append V m (s ++ [ a ]) t claim
  p : (s ++ [ a ]) ++ t = s ++ a ∷ t
  p = ++-assoc s [ a ] t

monotone-bars-root-implies-bars-all
 : {A : 𝓀 Μ‡}  (V : List A β†’ π“₯ Μ‡) β†’ is-monotone V
 β†’ V bars []
 β†’ (s : List A) β†’ V bars s
monotone-bars-root-implies-bars-all V m b s
 = monotone-bars-append V m [] s b

monotone-bars-root-iff-bars-all
 : {A : 𝓀 Μ‡}  (V : List A β†’ π“₯ Μ‡) β†’ is-monotone V
 β†’ (V bars []) ↔ ((s : List A) β†’ V bars s)
monotone-bars-root-iff-bars-all V m
 = monotone-bars-root-implies-bars-all V m , Ξ» b β†’ b []

\end{code}

If V bars the empty sequence, we call V an inductive bar.

We now give an equivalent formulation without an explicit root sequence.
For this, we consider sections of predicates on finite sequences.

Concatenation associates to each predicate V a binary type-valued relation

    Rⱽ s t = (s ++ t) ∈ V.

Fixing its first argument s gives the section of V at s:

    section V s t = (s ++ t) ∈ V

For a singleton prefix [ a ], we write section₁ V a.

\begin{code}

section : {A : 𝓀 Μ‡} β†’ (List A β†’ π“₯ Μ‡) β†’ (List A) β†’ List A β†’ π“₯ Μ‡
section V s t = V (s ++ t)

section₁ : {A : 𝓀 Μ‡} β†’ (List A β†’ π“₯ Μ‡) β†’ A β†’ List A β†’ π“₯ Μ‡
section₁ V a s = section V [ a ] s

∈-implies-[]∈-section
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s : List A)
 β†’ s ∈ V β†’ [] ∈ section V s
∈-implies-[]∈-section V [] v = v
∈-implies-[]∈-section V (a ∷ s) v = ∈-implies-[]∈-section (section₁ V a) s v

section-append
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s t : List A)
 β†’ section V (s ++ t) = section (section V s) t
section-append V [] t = refl
section-append V (a ∷ s) t = section-append (section₁ V a) s t

\end{code}

As an alternative formulation, the predicate `is-inductive-bar V` is generated
by the following two rules:
 - if V contains the empty sequence, then V is an inductive bar;
 - if the section of V at each a : A is an inductive bar, then so is V.

The type `is-inductive-bar V` need not be a proposition.

\begin{code}

data is-inductive-bar {π“₯ : Universe} {A : 𝓀 Μ‡}
 : (List A β†’ π“₯ Μ‡) β†’ (𝓀 βŠ” π“₯) ⁺ Μ‡
 where
 base : {V : List A β†’ π“₯ Μ‡}
      β†’ [] ∈ V
      β†’ is-inductive-bar V
 step : {V : List A β†’ π“₯ Μ‡}
      β†’ ((a : A) β†’ is-inductive-bar (section₁ V a))
      β†’ is-inductive-bar V

inductive-bar-section-append
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s t : List A)
 β†’ is-inductive-bar (section V (s ++ t))
 β†’ is-inductive-bar (section (section V s) t)
inductive-bar-section-append V s t
 = transport is-inductive-bar (section-append V s t)

inductive-bar-respects-inclusion
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (W : List A β†’ 𝓦 Μ‡)
 β†’ V βŠ† W
 β†’ is-inductive-bar V
 β†’ is-inductive-bar W
inductive-bar-respects-inclusion V W ΞΈ (base v) = base (ΞΈ [] v)
inductive-bar-respects-inclusion V W ΞΈ (step Ο†) = step ψ
 where
  ψ : βˆ€ a β†’ is-inductive-bar (section₁ W a)
  ψ a = inductive-bar-respects-inclusion
         (section₁ V a)
         (section₁ W a)
         (Ξ» s β†’ ΞΈ (a ∷ s))
         (Ο† a)

inductive-bar-from-sections
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (m : β„•)
 β†’ ((s : List A) β†’ length s = m β†’ is-inductive-bar (section V s))
 β†’ is-inductive-bar V
inductive-bar-from-sections V 0 Ο† = Ο† [] refl
inductive-bar-from-sections V (succ m) Ο† = step ih
 where
  ih : βˆ€ a β†’ is-inductive-bar (section₁ V a)
  ih a = inductive-bar-from-sections (section₁ V a) m ψ
   where
    ψ : βˆ€ s β†’ length s = m β†’ is-inductive-bar (section (section₁ V a) s)
    ψ s e = Ο† (a ∷ s) (ap succ e)

\end{code}

If V bars the empty sequence, then it is an inductive bar.

\begin{code}

bars-implies-inductive-bar-section
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s : List A)
 β†’ V bars s β†’ is-inductive-bar (section V s)
bars-implies-inductive-bar-section V s (hit v)
 = base (∈-implies-[]∈-section V s v)
bars-implies-inductive-bar-section V s (step Ο†) = step goal
 where
  ih : βˆ€ a β†’ is-inductive-bar (section V (s ++ [ a ]))
  ih a = bars-implies-inductive-bar-section V (s ++ [ a ]) (Ο† a)
  goal : βˆ€ a β†’ is-inductive-bar (section₁ (section V s) a)
  goal a = inductive-bar-section-append V s [ a ] (ih a)

bars-root-implies-inductive-bar
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ V bars [] β†’ is-inductive-bar V
bars-root-implies-inductive-bar V
 = bars-implies-inductive-bar-section V []

\end{code}

If V is an inductive bar, then it bars the empty sequence.

\begin{code}

section₁-bars-implies-bars-cons
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (a : A) (s : List A)
 β†’ (section₁ V a) bars s
 β†’ V bars (a ∷ s)
section₁-bars-implies-bars-cons V a s (hit v) = hit v
section₁-bars-implies-bars-cons V a s (step Ο†) = step ih
 where
  ih : βˆ€ x β†’ V bars (a ∷ s ++ [ x ])
  ih x = section₁-bars-implies-bars-cons V a (s ++ [ x ]) (Ο† x)

inductive-bar-section-implies-bars
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s : List A)
 β†’ is-inductive-bar (section V s)
 β†’ V bars s
inductive-bar-section-implies-bars V [] (base v) = hit v
inductive-bar-section-implies-bars V [] (step Ο†)
 = step (Ξ» a β†’ inductive-bar-section-implies-bars V [ a ] (Ο† a))
inductive-bar-section-implies-bars V (a ∷ s) b
 = section₁-bars-implies-bars-cons V a s
    (inductive-bar-section-implies-bars (section₁ V a) s b)

inductive-bar-section-iff-bars
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡) (s : List A)
 β†’ (is-inductive-bar (section V s)) ↔ (V bars s)
inductive-bar-section-iff-bars V s
 = inductive-bar-section-implies-bars V s
 , bars-implies-inductive-bar-section V s

inductive-bar-implies-bars-root
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ is-inductive-bar V β†’ V bars []
inductive-bar-implies-bars-root V
 = inductive-bar-section-implies-bars V []

inductive-bar-iff-bars-root
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ (is-inductive-bar V) ↔ (V bars [])
inductive-bar-iff-bars-root V
 = inductive-bar-implies-bars-root V , bars-root-implies-inductive-bar V

\end{code}

No monotonicity assumption is needed in the above logical equivalence.

If the inductive bar is monotone, then it bars all finite sequences.

\begin{code}

monotone-inductive-bar-bars-all
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ is-monotone V
 β†’ is-inductive-bar V
 β†’ (s : List A) β†’ V bars s
monotone-inductive-bar-bars-all V m p
 = monotone-bars-root-implies-bars-all V m
    (inductive-bar-implies-bars-root V p)

monotone-inductive-bar-sections
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ is-monotone V
 β†’ is-inductive-bar V
 β†’ (s : List A)
 β†’ is-inductive-bar (section V s)
monotone-inductive-bar-sections V m b s =
 bars-implies-inductive-bar-section V s
  (monotone-inductive-bar-bars-all V m b s)

\end{code}

If V is an inductive bar, then every infinite sequence has a finite prefix
belonging to V.

\begin{code}

inductive-bar-meets-every-sequence
 : {A : 𝓀 Μ‡} (V : List A β†’ π“₯ Μ‡)
 β†’ is-inductive-bar V
 β†’ (Ξ± : β„• β†’ A)
 β†’ Ξ£ s κž‰ List A , ((Ξ± extends s) Γ— (s ∈ V))
inductive-bar-meets-every-sequence V (base v) Ξ± = [] , ⋆ , v
inductive-bar-meets-every-sequence V (step Ο†) Ξ±
 using (s , e , p) ←
   inductive-bar-meets-every-sequence (section₁ V (Ξ± 0)) (Ο† (Ξ± 0)) (Ξ± ∘ succ)
 = (α 0 ∷ s) , (refl , e) , p

\end{code}

Each inductive bar meets all infinite sequences bounded pointwise by
a given sequence within a common finite depth.

\begin{code}

inductive-bar-meets-bounded-sequences-uniformly
 : (V : List β„• β†’ π“₯ Μ‡)
 β†’ is-inductive-bar V
 β†’ (Ξ΄ : β„• β†’ β„•)
 β†’ Ξ£ m κž‰ β„• ,
    ((Ξ± : β„• β†’ β„•) β†’ Ξ± ≀¹ Ξ΄
                 β†’ Ξ£ s κž‰ List β„• , (length s ≀ℕ m) Γ— (Ξ± extends s) Γ— s ∈ V)
inductive-bar-meets-bounded-sequences-uniformly V (base v) Ξ΄
 = 0 , (Ξ» _ _ β†’ [] , ⋆ , ⋆ , v)
inductive-bar-meets-bounded-sequences-uniformly V (step Ο†) Ξ΄
 = succ m , goal
 where
  Ξ΄β‚€ : β„•
  Ξ΄β‚€ = Ξ΄ 0
  ihs : (i : β„•)
      β†’ Ξ£ m κž‰ β„• ,
         ((Ξ± : β„• β†’ β„•)
          β†’ Ξ± ≀¹ (Ξ΄ ∘ succ)
          β†’ Ξ£ s κž‰ List β„• , (length s ≀ℕ m) Γ— (Ξ± extends s) Γ— s ∈ section₁ V i)
  ihs i = inductive-bar-meets-bounded-sequences-uniformly
          (section₁ V i) (Ο† i) (Ξ΄ ∘ succ)
  ΞΌ : β„• β†’ β„•
  ΞΌ i = pr₁ (ihs i)
  m : β„•
  m = pr₁ (finite-upper-bound ΞΌ Ξ΄β‚€)
  upper : (i : β„•) β†’ i ≀ℕ Ξ΄β‚€ β†’ ΞΌ i ≀ℕ m
  upper = prβ‚‚ (finite-upper-bound ΞΌ Ξ΄β‚€)
  goal : (Ξ± : β„• β†’ β„•) β†’ Ξ± ≀¹ Ξ΄
       β†’ Ξ£ s κž‰ List β„• , (length s ≀ℕ succ m) Γ— (Ξ± extends s) Γ— s ∈ V
  goal Ξ± r
   using (s , rs , e , v) ← prβ‚‚ (ihs (Ξ± 0)) (Ξ± ∘ succ) (r ∘ succ)
   = s' , rs' , e' , v
   where
    s' : List β„•
    s' = α 0 ∷ s
    rs' : length s' ≀ℕ succ m
    rs' = ≀-trans (length s) (ΞΌ (Ξ± 0)) m rs (upper (Ξ± 0) (r 0))
    e' : Ξ± extends s'
    e' = refl , e

\end{code}