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}