Internal polynomial, sized, inductive and coinductive constructions
DefinitionLaarakkerOttenVanDenBerg2026_EncodingRevision2Wild endofunctors have internal object and morphism operations with substitution and internal identity/composition laws. The file constructs literal polynomial functor data, size-indexed arrows and modal actions, full algebra/coalgebra hom types, internally quantified initiality and terminality, the prescribed weak-commutation maps, recursive sized carriers, and their J-transported structure maps. Unsized mu and nu structures use the source quantifier action and the inverse of the specified weak-commutation map. Polynomial laws, initiality/terminality and functorial lifting remain theorem conclusions, not added fields. Homwise equivalence types are distinguished from natural adjunctions; the lifting targets retain full morphism witnesses while stating identity/composition laws for the prescribed underlying arrows.
import Definitions.Def_LaarakkerOttenVanDenBerg2026_TheoryRevision2
/-! Generated from reviewed V2 modules by bundle_v2.py.
See the accompanying manifest for exact input hashes and source order. -/
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingV2 -/
/-!
# Internal functor data in a contextual type theory
Section 3 describes internal terms, rather than arbitrary functions on a Lean
type of decoded elements. Here the object and morphism operations are given in
their substitution-natural contextual form. The generic-specialization theorems
below prove that these operations are determined by their generic terms.
No realizer, tracker transformer, recursive solution, initiality, or terminality
is part of the functor data. The categorical laws, when supplied, are terms of
internal identity types. This file does not claim the encoding theorems.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
/-- An internal arrow between two small types, in a fixed context. -/
abbrev SmallHom (U : Universe C) (P : FunctionTypes C) {Γ : C.Ctx}
(A B : U.Code Γ) := C.Tm Γ (P.arr (U.el A) (U.el B))
namespace SmallHom
variable (U : Universe C) (P : FunctionTypes C)
/-- The substituted type of a small arrow. -/
theorem type_sub {Γ Δ : C.Ctx} (A B : U.Code Γ) (σ : C.Sub Δ Γ) :
C.tySub (P.arr (U.el A) (U.el B)) σ =
P.arr (U.el (U.sub A σ)) (U.el (U.sub B σ)) := by
rw [P.arr_sub, U.el_sub, U.el_sub]
rfl
/-- Substitution of an internal small arrow. -/
def sub {Γ Δ : C.Ctx} {A B : U.Code Γ} (f : SmallHom U P A B) (σ : C.Sub Δ Γ) :
SmallHom U P (U.sub A σ) (U.sub B σ) :=
C.castTm (type_sub U P A B σ) (C.tmSub f σ)
end SmallHom
/-- The contextual form of an internal endofunctor's object and morphism
operations. Naturality is substitution coherence of a term, not an additional
mathematical hypothesis about a source functor. -/
structure InternalFunctorData (U : Universe C) (P : FunctionTypes C) (Γ : C.Ctx) where
obj : {Δ : C.Ctx} → C.Sub Δ Γ → U.Code Δ → U.Code Δ
obj_sub : ∀ {Δ Θ} (σ : C.Sub Δ Γ) (A : U.Code Δ) (τ : C.Sub Θ Δ),
U.sub (obj σ A) τ = obj (C.comp σ τ) (U.sub A τ)
map : {Δ : C.Ctx} → (σ : C.Sub Δ Γ) → (A B : U.Code Δ) →
SmallHom U P A B → SmallHom U P (obj σ A) (obj σ B)
map_sub : ∀ {Δ Θ} (σ : C.Sub Δ Γ) (A B : U.Code Δ)
(f : SmallHom U P A B) (τ : C.Sub Θ Δ),
HEq (SmallHom.sub U P (map σ A B f) τ)
(map (C.comp σ τ) (U.sub A τ) (U.sub B τ) (SmallHom.sub U P f τ))
namespace InternalFunctorData
variable {U : Universe C} {P : FunctionTypes C} {Γ : C.Ctx}
(F : InternalFunctorData U P Γ)
/-- The generic object term in `Γ, A : U`. -/
def genericObject : U.Code (C.ext Γ (U.type Γ)) :=
F.obj C.fst (U.generic Γ)
/-- Every object-operation instance is substitution of its one generic term. -/
theorem object_from_generic {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Δ) :
U.sub F.genericObject (U.extend σ A) = F.obj σ A := by
rw [genericObject, F.obj_sub, U.extend_fst, U.generic_sub_extend]
/-- The closed internal function `F : U → U` determined by the object operation. -/
def objectTerm : C.Tm Γ (P.arr (U.type Γ) (U.type Γ)) :=
P.lam (C.castTm (U.type_sub C.fst).symm F.genericObject)
/-- Congruence of the morphism operation, including external type transports. -/
theorem map_congr {Δ : C.Ctx} {σ τ : C.Sub Δ Γ} (hσ : σ = τ)
{A B A' B' : U.Code Δ} (hA : A = A') (hB : B = B')
{f : SmallHom U P A B} {g : SmallHom U P A' B'} (hf : HEq f g) :
HEq (F.map σ A B f) (F.map τ A' B' g) := by
cases hσ
cases hA
cases hB
cases hf
rfl
end InternalFunctorData
namespace GenericArrow
variable (U : Universe C) (P : FunctionTypes C) (Γ : C.Ctx)
/-- The context of two small-type codes. -/
abbrev codes : C.Ctx := C.ext (C.ext Γ (U.type Γ)) (U.type (C.ext Γ (U.type Γ)))
/-- The first generic code in `Γ, A : U, B : U`. -/
def domain : U.Code (codes U Γ) := U.sub (U.generic Γ) C.fst
/-- The second generic code in `Γ, A : U, B : U`. -/
def codomain : U.Code (codes U Γ) := U.generic (C.ext Γ (U.type Γ))
/-- Forget both generic codes. -/
def base : C.Sub (codes U Γ) Γ := C.comp C.fst C.fst
/-- The context `Γ, A : U, B : U, f : A → B`. -/
abbrev context : C.Ctx :=
C.ext (codes U Γ) (P.arr (U.el (domain U Γ)) (U.el (codomain U Γ)))
/-- The first code weakened into the generic arrow context. -/
def source : U.Code (context U P Γ) := U.sub (domain U Γ) C.fst
/-- The second code weakened into the generic arrow context. -/
def target : U.Code (context U P Γ) := U.sub (codomain U Γ) C.fst
/-- Forget the codes and the arrow. -/
def projection : C.Sub (context U P Γ) Γ := C.comp (base U Γ) C.fst
/-- The generic internal arrow. -/
def term : SmallHom U P (source U P Γ) (target U P Γ) :=
C.castTm (SmallHom.type_sub U P (domain U Γ) (codomain U Γ) C.fst) C.snd
/-- Substitute two small-type codes into their generic context. -/
def codesSub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) : C.Sub Δ (codes U Γ) :=
U.extend (U.extend σ A) B
theorem domain_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) :
U.sub (domain U Γ) (codesSub U Γ σ A B) = A := by
rw [domain, U.sub_comp, codesSub, U.extend_fst, U.generic_sub_extend]
theorem codomain_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) :
U.sub (codomain U Γ) (codesSub U Γ σ A B) = B :=
U.generic_sub_extend _ _
theorem base_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) :
C.comp (base U Γ) (codesSub U Γ σ A B) = σ := by
rw [base, C.assoc, codesSub, U.extend_fst, U.extend_fst]
/-- The generic arrow type specializes to the specified domain and codomain. -/
theorem arrowType_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) :
C.tySub (P.arr (U.el (domain U Γ)) (U.el (codomain U Γ)))
(codesSub U Γ σ A B) = P.arr (U.el A) (U.el B) := by
rw [SmallHom.type_sub, domain_sub, codomain_sub]
/-- Substitute codes and an arrow into the generic arrow context. -/
def specialize {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) (f : SmallHom U P A B) :
C.Sub Δ (context U P Γ) :=
C.pair (codesSub U Γ σ A B) (C.castTm (arrowType_sub U P Γ σ A B).symm f)
theorem source_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ)
(f : SmallHom U P A B) : U.sub (source U P Γ) (specialize U P Γ σ A B f) = A := by
rw [source, U.sub_comp, specialize, C.pair_fst, domain_sub]
theorem target_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ)
(f : SmallHom U P A B) : U.sub (target U P Γ) (specialize U P Γ σ A B f) = B := by
rw [target, U.sub_comp, specialize, C.pair_fst, codomain_sub]
theorem projection_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ)
(f : SmallHom U P A B) :
C.comp (projection U P Γ) (specialize U P Γ σ A B f) = σ := by
rw [projection, C.assoc, specialize, C.pair_fst, base_sub]
/-- Substitution of the generic arrow recovers the supplied arrow. -/
theorem term_sub {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ) (f : SmallHom U P A B) :
HEq (SmallHom.sub U P (term U P Γ) (specialize U P Γ σ A B f)) f := by
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (SmallHom.type_sub U P (domain U Γ) (codomain U Γ) C.fst).symm
(C.castTm_heq _ _) (specialize U P Γ σ A B f)).trans
((C.pair_snd _ _).trans (C.castTm_heq _ _)))
end GenericArrow
namespace InternalFunctorData
variable {U : Universe C} {P : FunctionTypes C} {Γ : C.Ctx}
(F : InternalFunctorData U P Γ)
/-- The one generic morphism-action term in `Γ, A : U, B : U, f : A → B`. -/
def genericMap : SmallHom U P
(F.obj (GenericArrow.projection U P Γ) (GenericArrow.source U P Γ))
(F.obj (GenericArrow.projection U P Γ) (GenericArrow.target U P Γ)) :=
F.map (GenericArrow.projection U P Γ) (GenericArrow.source U P Γ)
(GenericArrow.target U P Γ) (GenericArrow.term U P Γ)
/-- Every morphism-operation instance is substitution of its one generic term.
This is the contextual representability condition missing from an arbitrary
external functor on the set of universe codes. -/
theorem map_from_generic {Δ : C.Ctx} (σ : C.Sub Δ Γ) (A B : U.Code Δ)
(f : SmallHom U P A B) :
HEq (SmallHom.sub U P F.genericMap (GenericArrow.specialize U P Γ σ A B f))
(F.map σ A B f) := by
exact (F.map_sub _ _ _ _ _).trans
(F.map_congr (GenericArrow.projection_sub U P Γ σ A B f)
(GenericArrow.source_sub U P Γ σ A B f)
(GenericArrow.target_sub U P Γ σ A B f)
(GenericArrow.term_sub U P Γ σ A B f))
end InternalFunctorData
/-! The context of three small types and two composable arrows, used to state
the functor composition law as one internal term. -/
namespace GenericComposition
variable (U : Universe C) (P : FunctionTypes C) (Γ : C.Ctx)
abbrev codes : C.Ctx := C.ext (GenericArrow.codes U Γ) (U.type (GenericArrow.codes U Γ))
def firstCode : U.Code (codes U Γ) := U.sub (GenericArrow.domain U Γ) C.fst
def middleCode : U.Code (codes U Γ) := U.sub (GenericArrow.codomain U Γ) C.fst
def lastCode : U.Code (codes U Γ) := U.generic (GenericArrow.codes U Γ)
abbrev firstContext : C.Ctx :=
C.ext (codes U Γ) (P.arr (U.el (firstCode U Γ)) (U.el (middleCode U Γ)))
def firstDomain : U.Code (firstContext U P Γ) := U.sub (firstCode U Γ) C.fst
def firstCodomain : U.Code (firstContext U P Γ) := U.sub (middleCode U Γ) C.fst
def lastCodomain : U.Code (firstContext U P Γ) := U.sub (lastCode U Γ) C.fst
def firstTerm : SmallHom U P (firstDomain U P Γ) (firstCodomain U P Γ) :=
C.castTm (SmallHom.type_sub U P (firstCode U Γ) (middleCode U Γ) C.fst) C.snd
abbrev context : C.Ctx := C.ext (firstContext U P Γ)
(P.arr (U.el (firstCodomain U P Γ)) (U.el (lastCodomain U P Γ)))
def source : U.Code (context U P Γ) := U.sub (firstDomain U P Γ) C.fst
def middle : U.Code (context U P Γ) := U.sub (firstCodomain U P Γ) C.fst
def target : U.Code (context U P Γ) := U.sub (lastCodomain U P Γ) C.fst
def first : SmallHom U P (source U P Γ) (middle U P Γ) :=
SmallHom.sub U P (firstTerm U P Γ) C.fst
def second : SmallHom U P (middle U P Γ) (target U P Γ) :=
C.castTm (SmallHom.type_sub U P (firstCodomain U P Γ) (lastCodomain U P Γ) C.fst) C.snd
def projection : C.Sub (context U P Γ) Γ :=
C.comp (C.comp (C.comp (GenericArrow.base U Γ) C.fst) C.fst) C.fst
end GenericComposition
/-- Internal identity and composition laws for contextual functor data.
The witnesses live in the type theory, rather than in Lean's proof-irrelevant
equality. Each law is one term in its generic context; instances in other
contexts are obtained by substitution, not by an arbitrary family of choices.
The source does not require higher categorical coherence. -/
structure WildEndofunctor (U : Universe C) (P : FunctionTypes C)
(I : IdentityTypes C) (Γ : C.Ctx) extends InternalFunctorData U P Γ where
map_id : C.Tm (C.ext Γ (U.type Γ))
(I.id (P.arr (U.el (obj C.fst (U.generic Γ))) (U.el (obj C.fst (U.generic Γ))))
(map C.fst (U.generic Γ) (U.generic Γ) (P.identity (U.el (U.generic Γ))))
(P.identity (U.el (obj C.fst (U.generic Γ)))))
map_comp : C.Tm (GenericComposition.context U P Γ)
(I.id (P.arr
(U.el (obj (GenericComposition.projection U P Γ) (GenericComposition.source U P Γ)))
(U.el (obj (GenericComposition.projection U P Γ) (GenericComposition.target U P Γ))))
(map (GenericComposition.projection U P Γ)
(GenericComposition.source U P Γ) (GenericComposition.target U P Γ)
(P.compose (GenericComposition.second U P Γ) (GenericComposition.first U P Γ)))
(P.compose
(map (GenericComposition.projection U P Γ)
(GenericComposition.middle U P Γ) (GenericComposition.target U P Γ)
(GenericComposition.second U P Γ))
(map (GenericComposition.projection U P Γ)
(GenericComposition.source U P Γ) (GenericComposition.middle U P Γ)
(GenericComposition.first U P Γ))))
/-- A source algebra in a fixed context. Its carrier and structure map are
internal terms; there is no initiality or recursive solver in this definition. -/
structure Algebra {U : Universe C} {P : FunctionTypes C} {I : IdentityTypes C}
{Γ : C.Ctx} (F : WildEndofunctor U P I Γ) where
carrier : U.Code Γ
structureMap : SmallHom U P (F.obj C.id carrier) carrier
/-- A source coalgebra in a fixed context. -/
structure Coalgebra {U : Universe C} {P : FunctionTypes C} {I : IdentityTypes C}
{Γ : C.Ctx} (F : WildEndofunctor U P I Γ) where
carrier : U.Code Γ
structureMap : SmallHom U P carrier (F.obj C.id carrier)
/-- A morphism of algebras carries an internal identity witness. -/
structure AlgebraHom {U : Universe C} {P : FunctionTypes C} {I : IdentityTypes C}
{Γ : C.Ctx} {F : WildEndofunctor U P I Γ} (A B : Algebra F) where
map : SmallHom U P A.carrier B.carrier
commutes : C.Tm Γ (I.id (P.arr (U.el (F.obj C.id A.carrier)) (U.el B.carrier))
(P.compose map A.structureMap)
(P.compose B.structureMap (F.map C.id A.carrier B.carrier map)))
/-- A morphism of coalgebras carries the source's internal commuting-square witness. -/
structure CoalgebraHom {U : Universe C} {P : FunctionTypes C} {I : IdentityTypes C}
{Γ : C.Ctx} {F : WildEndofunctor U P I Γ} (A B : Coalgebra F) where
map : SmallHom U P A.carrier B.carrier
commutes : C.Tm Γ (I.id (P.arr (U.el A.carrier) (U.el (F.obj C.id B.carrier)))
(P.compose B.structureMap map)
(P.compose (F.map C.id A.carrier B.carrier map) A.structureMap))
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_QuantifierMapsV2 -/
/-! # The source actions of size quantifiers on internal families of arrows -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
{Z : SizeRules C U I}
namespace ExistentialSizeQuantifier
variable (E : ExistentialSizeQuantifier C U I Z) (F : FunctionTypes C)
/-- The source operation `∃ f`, obtained by existential elimination and pairing. -/
def map {Γ : C.Ctx} (A B : U.Code (C.ext Γ (Z.type Γ)))
(f : C.Tm (C.ext Γ (Z.type Γ)) (F.arr (U.el A) (U.el B))) :
C.Tm Γ (F.arr (U.el (E.code A)) (U.el (E.code B))) := by
let σ := @C.fst (C.ext Γ (Z.type Γ)) (U.el A)
exact E.recursor F A (E.code B) (E.pairAt B σ (F.app (F.sub f σ) C.snd))
end ExistentialSizeQuantifier
namespace UniversalSizeQuantifier
variable (Q : UniversalSizeQuantifier C U I Z) (F : FunctionTypes C)
(QS : UniversalSizeSubstitution U I Z Q)
/-- The source operation `∀ f`, formed by universal abstraction and application. -/
def map {Γ : C.Ctx} (A B : U.Code (C.ext Γ (Z.type Γ)))
(f : C.Tm (C.ext Γ (Z.type Γ)) (F.arr (U.el A) (U.el B))) :
C.Tm Γ (F.arr (U.el (Q.code A)) (U.el (Q.code B))) := by
let σ := @C.fst Γ (U.el (Q.code A))
have hin : C.tySub (U.el (Q.code A)) σ = U.el (Q.code (U.sub A (Z.lift σ))) :=
(U.el_sub (Q.code A) σ).trans (congrArg U.el (QS.code_sub A σ))
have hout : C.tySub (U.el (Q.code B)) σ = U.el (Q.code (U.sub B (Z.lift σ))) :=
(U.el_sub (Q.code B) σ).trans (congrArg U.el (QS.code_sub B σ))
let f' := SmallHom.sub U F f (Z.lift σ)
exact F.lam (C.castTm hout.symm (Q.lam (F.app f' (Q.unlam (C.castTm hin C.snd)))))
end UniversalSizeQuantifier
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingSizedV2 -/
/-!
# Size-indexed internal morphisms and modal actions
Objects are contextual terms `Γ, i : Size ⊢ A(i) : U`. Morphisms are terms
of the small universal type `∀ i, A(i) → B(i)`. The modal actions below are the
literal existential-pair and universal-function operations of Section 3.2.
They never replace a size-indexed morphism by an arbitrary external family.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
{P : DependentProducts C} {S : DependentSums C}
(Z : SizeRules C U I) (F : FunctionTypes C) (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z)
/-- The universe code for a size-indexed internal arrow. -/
def homCode {Γ : C.Ctx} (A B : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
Q.code (K.arrow A B)
/-- The source type of a size-indexed morphism. -/
abbrev Hom {Γ : C.Ctx} (A B : U.Code (C.ext Γ (Z.type Γ))) :=
C.Tm Γ (U.el (homCode Z K Q A B))
/-- Evaluate a size-indexed morphism at the generic size. -/
def eval (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))} (f : Hom Z K Q A B) :
C.Tm (C.ext Γ (Z.type Γ)) (F.arr (U.el A) (U.el B)) :=
C.castTm (K.el_arrow FP A B) (Q.unlam f)
/-- Abstract a contextual arrow over sizes. -/
def ofAt (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))}
(f : C.Tm (C.ext Γ (Z.type Γ)) (F.arr (U.el A) (U.el B))) : Hom Z K Q A B :=
Q.lam (C.castTm (K.el_arrow FP A B).symm f)
theorem eval_ofAt (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))}
(f : C.Tm (C.ext Γ (Z.type Γ)) (F.arr (U.el A) (U.el B))) :
eval Z F K Q FP (ofAt Z F K Q FP f) = f := by
unfold eval ofAt
rw [Q.beta]
exact eq_of_heq ((C.castTm_heq _ _).trans (C.castTm_heq _ _))
theorem ofAt_eval (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))} (f : Hom Z K Q A B) :
ofAt Z F K Q FP (eval Z F K Q FP f) = f := by
have h : C.castTm (K.el_arrow FP A B).symm
(C.castTm (K.el_arrow FP A B) (Q.unlam f)) = Q.unlam f :=
eq_of_heq ((C.castTm_heq _ _).trans (C.castTm_heq _ _))
exact (congrArg Q.lam h).trans (Q.eta f)
/-- Identity in the source's category of size-indexed small types. -/
def identity (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
(A : U.Code (C.ext Γ (Z.type Γ))) : Hom Z K Q A A :=
ofAt Z F K Q FP (F.identity (U.el A))
/-- Composition of size-indexed internal arrows. -/
def compose (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
{A B D : U.Code (C.ext Γ (Z.type Γ))} (g : Hom Z K Q B D) (f : Hom Z K Q A B) :
Hom Z K Q A D :=
ofAt Z F K Q FP (F.compose (eval Z F K Q FP g) (eval Z F K Q FP f))
/-- Substitution of size-indexed morphism types. -/
theorem homType_sub (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q)
{Γ Δ : C.Ctx} (A B : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
C.tySub (U.el (homCode Z K Q A B)) σ =
U.el (homCode Z K Q (U.sub A (Z.lift σ)) (U.sub B (Z.lift σ))) :=
(U.el_sub (Q.code (K.arrow A B)) σ).trans
((congrArg U.el (QS.code_sub (K.arrow A B) σ)).trans
(congrArg (fun X => U.el (Q.code X)) (K.arrow_sub KS A B (Z.lift σ))))
/-- Substitution of a size-indexed arrow. -/
def sub (KS : SmallTypeSubstitution U P S I K) (QS : UniversalSizeSubstitution U I Z Q)
{Γ Δ : C.Ctx} {A B : U.Code (C.ext Γ (Z.type Γ))} (f : Hom Z K Q A B)
(σ : C.Sub Δ Γ) : Hom Z K Q (U.sub A (Z.lift σ)) (U.sub B (Z.lift σ)) :=
C.castTm (homType_sub Z K Q KS QS A B σ) (C.tmSub f σ)
/-- The pointwise lift of a source functor on small types. -/
def liftObject {Γ : C.Ctx} (T : WildEndofunctor U F I Γ)
(A : U.Code (C.ext Γ (Z.type Γ))) : U.Code (C.ext Γ (Z.type Γ)) :=
T.obj C.fst A
/-- The pointwise lift of its internal morphism action. -/
def liftMap (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
(T : WildEndofunctor U F I Γ) {A B : U.Code (C.ext Γ (Z.type Γ))}
(f : Hom Z K Q A B) : Hom Z K Q (liftObject Z F T A) (liftObject Z F T B) :=
ofAt Z F K Q FP (T.map C.fst A B (eval Z F K Q FP f))
/-- The source's bounded existential action on size-indexed morphisms. -/
def diamondMap (FP : FunctionProductCompatibility F P)
(E : ExistentialSizeQuantifier C U I Z) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))} (f : Hom Z K Q A B) :
Hom Z K Q (Z.diamond K E A) (Z.diamond K E B) :=
ofAt Z F K Q FP (E.map F
(K.sigma Z.boundCode (U.sub (U.sub A Z.inner) C.fst))
(K.sigma Z.boundCode (U.sub (U.sub B Z.inner) C.fst))
(K.productMap F Z.boundCode (U.sub A Z.inner) (U.sub B Z.inner)
(SmallHom.sub U F (eval Z F K Q FP f) Z.inner)))
/-- The source's bounded universal action on size-indexed morphisms. -/
def boxMap (FP : FunctionProductCompatibility F P)
(QS : UniversalSizeSubstitution U I Z Q) {Γ : C.Ctx}
{A B : U.Code (C.ext Γ (Z.type Γ))} (f : Hom Z K Q A B) :
Hom Z K Q (Z.box K Q A) (Z.box K Q B) :=
ofAt Z F K Q FP (Q.map F QS
(K.arrow Z.boundCode (U.sub A Z.inner))
(K.arrow Z.boundCode (U.sub B Z.inner))
(K.postcompose F FP Z.boundCode (U.sub A Z.inner) (U.sub B Z.inner)
(SmallHom.sub U F (eval Z F K Q FP f) Z.inner)))
/-- A source size-indexed algebra for `T[◇ -]`. -/
structure Algebra (E : ExistentialSizeQuantifier C U I Z)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) where
carrier : U.Code (C.ext Γ (Z.type Γ))
structureMap : Hom Z K Q (liftObject Z F T (Z.diamond K E carrier)) carrier
/-- A source size-indexed coalgebra for `T[□ -]`. -/
structure Coalgebra {Γ : C.Ctx} (T : WildEndofunctor U F I Γ) where
carrier : U.Code (C.ext Γ (Z.type Γ))
structureMap : Hom Z K Q carrier (liftObject Z F T (Z.box K Q carrier))
/-- A size-indexed algebra morphism with the source's internal path witness. -/
structure AlgebraHom (FP : FunctionProductCompatibility F P)
(E : ExistentialSizeQuantifier C U I Z) {Γ : C.Ctx} {T : WildEndofunctor U F I Γ}
(A B : Algebra Z F K Q E T) where
map : Hom Z K Q A.carrier B.carrier
commutes : C.Tm Γ (I.id
(U.el (homCode Z K Q (liftObject Z F T (Z.diamond K E A.carrier)) B.carrier))
(compose Z F K Q FP map A.structureMap)
(compose Z F K Q FP B.structureMap
(liftMap Z F K Q FP T (diamondMap Z F K Q FP E map))))
/-- A size-indexed coalgebra morphism with the source's internal path witness. -/
structure CoalgebraHom (FP : FunctionProductCompatibility F P)
(QS : UniversalSizeSubstitution U I Z Q) {Γ : C.Ctx} {T : WildEndofunctor U F I Γ}
(A B : Coalgebra Z F K Q T) where
map : Hom Z K Q A.carrier B.carrier
commutes : C.Tm Γ (I.id
(U.el (homCode Z K Q A.carrier (liftObject Z F T (Z.box K Q B.carrier))))
(compose Z F K Q FP B.structureMap map)
(compose Z F K Q FP (liftMap Z F K Q FP T (boxMap Z F K Q FP QS map)) A.structureMap))
end LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingFamiliesV2 -/
/-! Internal quantification over small families indexed by the large size type. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C}
namespace InternalFunctorData
variable {F : FunctionTypes C} {Γ : C.Ctx} (T : InternalFunctorData U F Γ)
/-- Reindex the one internal functor term into a different context. -/
def reindex {Δ : C.Ctx} (σ : C.Sub Δ Γ) : InternalFunctorData U F Δ where
obj τ A := T.obj (C.comp σ τ) A
obj_sub τ A υ := by simpa only [C.assoc] using T.obj_sub (C.comp σ τ) A υ
map τ A B f := T.map (C.comp σ τ) A B f
map_sub τ A B f υ := (T.map_sub (C.comp σ τ) A B f υ).trans
(T.map_congr (C.assoc σ τ υ) rfl rfl HEq.rfl)
end InternalFunctorData
namespace DependentProducts
variable (P : DependentProducts C)
/-- Product application after substitution, with an equal presentation of the domain. -/
theorem unlam_sub_as {Γ Δ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ) (A' : C.Ty Δ)
(h : C.tySub A σ = A') :
P.unlam (C.castTm (P.pi_sub_as A B σ A' h) (C.tmSub f σ)) =
C.tmSub (P.unlam f) (C.liftAs σ A A' h) := by
subst A'
exact P.unlam_sub f σ
theorem unlam_congr {Γ : C.Ctx} {A : C.Ty Γ} {B B' : C.Ty (C.ext Γ A)}
(hB : B = B') {f : C.Tm Γ (P.pi A B)} {g : C.Tm Γ (P.pi A B')}
(h : HEq f g) : HEq (P.unlam f) (P.unlam g) := by
subst B'
cases h
rfl
end DependentProducts
namespace SizeRules
variable {I : IdentityTypes C} (Z : SizeRules C U I) (P : DependentProducts C)
/-- Product application commutes with substitution under the source's size binder. -/
theorem unlam_sub {Γ Δ : C.Ctx} {A : C.Ty (C.ext Γ (Z.type Γ))}
(f : C.Tm Γ (P.pi (Z.type Γ) A)) (σ : C.Sub Δ Γ) :
P.unlam (C.castTm (Z.pi_sub P A σ) (C.tmSub f σ)) =
C.tmSub (P.unlam f) (Z.lift σ) := by
have h := P.unlam_sub_as f σ (Z.type Δ) (Z.type_sub σ)
have hL := Z.liftAs_eq_lift σ
have ht (τ υ : C.Sub (C.ext Δ (Z.type Δ)) (C.ext Γ (Z.type Γ))) (e : τ = υ) :
HEq (C.tmSub (P.unlam f) τ) (C.tmSub (P.unlam f) υ) := by
cases e
rfl
apply eq_of_heq
exact (P.unlam_congr (congrArg (C.tySub A) hL.symm)
((C.castTm_heq _ _).trans (C.castTm_heq _ _).symm)).trans
((heq_of_eq h).trans (ht _ _ hL))
end SizeRules
namespace SizedFamily
variable {I : IdentityTypes C} (Z : SizeRules C U I) (P : DependentProducts C)
/-- The large internal type `Π i : Size, U` of small size-indexed families. -/
def type (Γ : C.Ctx) : C.Ty Γ := P.pi (Z.type Γ) (U.type (C.ext Γ (Z.type Γ)))
theorem type_sub {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
C.tySub (type Z P Γ) σ = type Z P Δ := by
rw [type, Z.pi_sub, U.type_sub]
rfl
/-- The context containing a generic size-indexed small family. -/
abbrev context (Γ : C.Ctx) : C.Ctx := C.ext Γ (type Z P Γ)
/-- Evaluate the generic family at the generic size. -/
def generic {Γ : C.Ctx} : U.Code (C.ext (context Z P Γ) (Z.type (context Z P Γ))) :=
P.unlam (C.castTm (type_sub Z P C.fst) C.snd)
/-- Bind an actual contextual family in the generic-family context. -/
def extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ)
(A : U.Code (C.ext Δ (Z.type Δ))) : C.Sub Δ (context Z P Γ) :=
C.pair σ (C.castTm (type_sub Z P σ).symm (P.lam A))
theorem extend_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ)
(A : U.Code (C.ext Δ (Z.type Δ))) :
C.comp C.fst (extend Z P σ A) = σ := C.pair_fst _ _
/-- Specializing the generic family recovers the supplied family pointwise. -/
theorem generic_sub_extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ)
(A : U.Code (C.ext Δ (Z.type Δ))) :
U.sub (generic Z P) (Z.lift (extend Z P σ A)) = A := by
let τ := extend Z P σ A
let f : C.Tm (context Z P Γ) (type Z P (context Z P Γ)) :=
C.castTm (type_sub Z P C.fst) C.snd
have hf : HEq (C.tmSub f τ) (P.lam A) :=
(C.tmSub_heq (type_sub Z P C.fst).symm (C.castTm_heq _ _) τ).trans
((C.pair_snd _ _).trans (C.castTm_heq _ _))
apply eq_of_heq
exact (C.castTm_heq _ _).trans
((heq_of_eq (Z.unlam_sub P f τ)).symm.trans
((P.unlam_congr (U.type_sub (Z.lift τ))
((C.castTm_heq _ _).trans hf)).trans (heq_of_eq (P.beta A))))
end SizedFamily
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingSizedInitialityV2 -/
/-!
# Internal hom types for size-indexed algebras
Algebras and coalgebras can be substituted into any context over the parameters
of their functor. Their hom types are actual internal dependent sums of a
size-indexed arrow and its commuting-square path.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
universe u v w t
variable {C : CwF.{u, v, w, t}} (T : CoreTheory C) {Γ : C.Ctx}
(F : WildEndofunctor T.univ T.functions T.identities Γ)
/-- The pointwise object action over a substitution into the functor's parameters. -/
def liftObjectOver {Δ : C.Ctx} (σ : C.Sub Δ Γ)
(A : T.univ.Code (C.ext Δ (T.size.type Δ))) : T.univ.Code (C.ext Δ (T.size.type Δ)) :=
F.obj (C.comp σ C.fst) A
/-- The corresponding action on internal size-indexed arrows. -/
def liftMapOver {Δ : C.Ctx} (σ : C.Sub Δ Γ)
{A B : T.univ.Code (C.ext Δ (T.size.type Δ))}
(f : Hom T.size T.small T.all A B) :
Hom T.size T.small T.all (liftObjectOver T F σ A) (liftObjectOver T F σ B) :=
ofAt T.size T.functions T.small T.all T.functionProducts
(F.map (C.comp σ C.fst) A B (eval T.size T.functions T.small T.all T.functionProducts f))
theorem liftObjectOver_sub {Δ Θ : C.Ctx} (σ : C.Sub Δ Γ)
(A : T.univ.Code (C.ext Δ (T.size.type Δ))) (τ : C.Sub Θ Δ) :
T.univ.sub (liftObjectOver T F σ A) (T.size.lift τ) =
liftObjectOver T F (C.comp σ τ) (T.univ.sub A (T.size.lift τ)) := by
rw [liftObjectOver, F.obj_sub]
have h : C.comp (C.comp σ C.fst) (T.size.lift τ) = C.comp (C.comp σ τ) C.fst := by
rw [C.assoc, T.size.lift_fst, ← C.assoc]
exact congrArg (fun ρ => F.obj ρ (T.univ.sub A (T.size.lift τ))) h
theorem liftDiamond_sub {Δ Θ : C.Ctx} (σ : C.Sub Δ Γ)
(A : T.univ.Code (C.ext Δ (T.size.type Δ))) (τ : C.Sub Θ Δ) :
T.univ.sub (liftObjectOver T F σ (T.size.diamond T.small T.ex A)) (T.size.lift τ) =
liftObjectOver T F (C.comp σ τ) (T.size.diamond T.small T.ex (T.univ.sub A (T.size.lift τ))) :=
(liftObjectOver_sub T F σ _ τ).trans
(congrArg (liftObjectOver T F (C.comp σ τ))
(T.size.diamond_sub T.small T.ex T.sizeSubstitution T.smallSubstitution T.exSubstitution A τ))
theorem liftBox_sub {Δ Θ : C.Ctx} (σ : C.Sub Δ Γ)
(A : T.univ.Code (C.ext Δ (T.size.type Δ))) (τ : C.Sub Θ Δ) :
T.univ.sub (liftObjectOver T F σ (T.size.box T.small T.all A)) (T.size.lift τ) =
liftObjectOver T F (C.comp σ τ) (T.size.box T.small T.all (T.univ.sub A (T.size.lift τ))) :=
(liftObjectOver_sub T F σ _ τ).trans
(congrArg (liftObjectOver T F (C.comp σ τ))
(T.size.box_sub T.small T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution A τ))
/-- A size-indexed algebra in a context over the parameters of the functor. -/
structure AlgebraOver {Δ : C.Ctx} (σ : C.Sub Δ Γ) where
carrier : T.univ.Code (C.ext Δ (T.size.type Δ))
structureMap : Hom T.size T.small T.all
(liftObjectOver T F σ (T.size.diamond T.small T.ex carrier)) carrier
/-- A size-indexed coalgebra in a context over the functor's parameters. -/
structure CoalgebraOver {Δ : C.Ctx} (σ : C.Sub Δ Γ) where
carrier : T.univ.Code (C.ext Δ (T.size.type Δ))
structureMap : Hom T.size T.small T.all carrier
(liftObjectOver T F σ (T.size.box T.small T.all carrier))
namespace AlgebraOver
variable {T F}
/-- Substitute a size-indexed algebra. -/
def sub {Δ Θ : C.Ctx} {σ : C.Sub Δ Γ} (A : AlgebraOver T F σ) (τ : C.Sub Θ Δ) :
AlgebraOver T F (C.comp σ τ) where
carrier := T.univ.sub A.carrier (T.size.lift τ)
structureMap := C.castTm
(congrArg (fun X => T.univ.el (homCode T.size T.small T.all X
(T.univ.sub A.carrier (T.size.lift τ)))) (liftDiamond_sub T F σ A.carrier τ))
(Sized.sub T.size T.small T.all T.smallSubstitution T.allSubstitution A.structureMap τ)
/-- The full internal type of size-indexed algebra morphisms. -/
def homType {Δ : C.Ctx} {σ : C.Sub Δ Γ} (A B : AlgebraOver T F σ) : C.Ty Δ :=
let H := T.univ.el (homCode T.size T.small T.all A.carrier B.carrier)
let π := @C.fst Δ H
let A' := A.sub π
let B' := B.sub π
let h := C.castTm (homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution
A.carrier B.carrier π) C.snd
T.sums.sigma H
(T.identities.id
(T.univ.el (homCode T.size T.small T.all
(liftObjectOver T F (C.comp σ π) (T.size.diamond T.small T.ex A'.carrier)) B'.carrier))
(compose T.size T.functions T.small T.all T.functionProducts h A'.structureMap)
(compose T.size T.functions T.small T.all T.functionProducts B'.structureMap
(liftMapOver T F (C.comp σ π)
(diamondMap T.size T.functions T.small T.all T.functionProducts T.ex h))))
end AlgebraOver
namespace CoalgebraOver
variable {T F}
/-- Substitute a size-indexed coalgebra. -/
def sub {Δ Θ : C.Ctx} {σ : C.Sub Δ Γ} (A : CoalgebraOver T F σ) (τ : C.Sub Θ Δ) :
CoalgebraOver T F (C.comp σ τ) where
carrier := T.univ.sub A.carrier (T.size.lift τ)
structureMap := C.castTm
(congrArg (fun X => T.univ.el (homCode T.size T.small T.all
(T.univ.sub A.carrier (T.size.lift τ)) X)) (liftBox_sub T F σ A.carrier τ))
(Sized.sub T.size T.small T.all T.smallSubstitution T.allSubstitution A.structureMap τ)
/-- The full internal type of size-indexed coalgebra morphisms. -/
def homType {Δ : C.Ctx} {σ : C.Sub Δ Γ} (A B : CoalgebraOver T F σ) : C.Ty Δ :=
let H := T.univ.el (homCode T.size T.small T.all A.carrier B.carrier)
let π := @C.fst Δ H
let A' := A.sub π
let B' := B.sub π
let h := C.castTm (homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution
A.carrier B.carrier π) C.snd
T.sums.sigma H
(T.identities.id
(T.univ.el (homCode T.size T.small T.all A'.carrier
(liftObjectOver T F (C.comp σ π) (T.size.box T.small T.all B'.carrier))))
(compose T.size T.functions T.small T.all T.functionProducts B'.structureMap h)
(compose T.size T.functions T.small T.all T.functionProducts
(liftMapOver T F (C.comp σ π)
(boxMap T.size T.functions T.small T.all T.functionProducts T.allSubstitution h))
A'.structureMap))
end CoalgebraOver
/-- The structure-map type over the generic size-indexed family. -/
def algebraStructureType : C.Ty (SizedFamily.context T.size T.products Γ) :=
T.univ.el (homCode T.size T.small T.all
(liftObjectOver T F C.fst (T.size.diamond T.small T.ex (SizedFamily.generic T.size T.products)))
(SizedFamily.generic T.size T.products))
/-- The source's generic sized algebra in a context containing its family and
its structure map. -/
def genericAlgebra : AlgebraOver T F
(C.comp (@C.fst Γ (SizedFamily.type T.size T.products Γ))
(@C.fst (SizedFamily.context T.size T.products Γ) (algebraStructureType T F))) where
carrier := T.univ.sub (SizedFamily.generic T.size T.products) (T.size.lift C.fst)
structureMap := C.castTm
(congrArg (fun X => T.univ.el (homCode T.size T.small T.all X
(T.univ.sub (SizedFamily.generic T.size T.products) (T.size.lift C.fst))))
(liftDiamond_sub T F C.fst (SizedFamily.generic T.size T.products) C.fst))
(C.castTm (homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution
(liftObjectOver T F C.fst (T.size.diamond T.small T.ex (SizedFamily.generic T.size T.products)))
(SizedFamily.generic T.size T.products) C.fst) C.snd)
/-- The structure-map type over the generic size-indexed coalgebra family. -/
def coalgebraStructureType : C.Ty (SizedFamily.context T.size T.products Γ) :=
T.univ.el (homCode T.size T.small T.all (SizedFamily.generic T.size T.products)
(liftObjectOver T F C.fst (T.size.box T.small T.all (SizedFamily.generic T.size T.products))))
/-- The generic sized coalgebra, including its internal structure map. -/
def genericCoalgebra : CoalgebraOver T F
(C.comp (@C.fst Γ (SizedFamily.type T.size T.products Γ))
(@C.fst (SizedFamily.context T.size T.products Γ) (coalgebraStructureType T F))) where
carrier := T.univ.sub (SizedFamily.generic T.size T.products) (T.size.lift C.fst)
structureMap := C.castTm
(congrArg (fun X => T.univ.el (homCode T.size T.small T.all
(T.univ.sub (SizedFamily.generic T.size T.products) (T.size.lift C.fst)) X))
(liftBox_sub T F C.fst (SizedFamily.generic T.size T.products) C.fst))
(C.castTm (homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution
(SizedFamily.generic T.size T.products)
(liftObjectOver T F C.fst (T.size.box T.small T.all (SizedFamily.generic T.size T.products)))
C.fst) C.snd)
namespace AlgebraOver
variable {T F}
/-- The full source initiality type for a sized algebra. It quantifies internally
over `B : Size → U` and `k : F[◇ B] →ⁱ B`, then takes internal contractibility
of the complete algebra-morphism type. -/
def initialityType (A : AlgebraOver T F C.id) : C.Ty Γ :=
T.products.pi (SizedFamily.type T.size T.products Γ)
(T.products.pi (algebraStructureType T F)
(contractible T.products T.sums T.identities
(homType (C.id_comp (C.comp C.fst C.fst) ▸ A.sub (C.comp C.fst C.fst))
(genericAlgebra T F))))
/-- An initiality witness is an internal term. -/
abbrev IsInitial (A : AlgebraOver T F C.id) := C.Tm Γ A.initialityType
end AlgebraOver
namespace CoalgebraOver
variable {T F}
/-- The full source terminality type for a sized coalgebra. -/
def terminalityType (A : CoalgebraOver T F C.id) : C.Ty Γ :=
T.products.pi (SizedFamily.type T.size T.products Γ)
(T.products.pi (coalgebraStructureType T F)
(contractible T.products T.sums T.identities
(homType (genericCoalgebra T F)
(C.id_comp (C.comp C.fst C.fst) ▸ A.sub (C.comp C.fst C.fst)))))
/-- A terminality witness is an internal term. -/
abbrev IsTerminal (A : CoalgebraOver T F C.id) := C.Tm Γ A.terminalityType
end CoalgebraOver
end LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingInitialityV2 -/
/-!
# Internal algebra morphisms and universal-property types
The initiality and terminality conditions of Section 3 and Appendix B quantify
internally over a small carrier and its structure map. Their morphism types are
dependent sums of an arrow and an internal identity witness, and contractibility
is the internal `Σ center, Π point, center = point` type. In particular these
definitions do not replace source contractibility by external unique existence.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {P : FunctionTypes C}
{I : IdentityTypes C} {Γ : C.Ctx} (F : WildEndofunctor U P I Γ)
/-- An algebra in a context over the parameter context of the functor. -/
structure AlgebraOver {Δ : C.Ctx} (σ : C.Sub Δ Γ) where
carrier : U.Code Δ
structureMap : SmallHom U P (F.obj σ carrier) carrier
/-- A coalgebra in a context over the parameter context of the functor. -/
structure CoalgebraOver {Δ : C.Ctx} (σ : C.Sub Δ Γ) where
carrier : U.Code Δ
structureMap : SmallHom U P carrier (F.obj σ carrier)
namespace AlgebraOver
variable {F}
/-- Substitute an algebra, using the functor's proved object-operation coherence. -/
def sub {Δ Θ : C.Ctx} {σ : C.Sub Δ Γ} (A : AlgebraOver F σ) (τ : C.Sub Θ Δ) :
AlgebraOver F (C.comp σ τ) where
carrier := U.sub A.carrier τ
structureMap := C.castTm
(congrArg (fun X => P.arr (U.el X) (U.el (U.sub A.carrier τ))) (F.obj_sub σ A.carrier τ))
(SmallHom.sub U P A.structureMap τ)
/-- The type of source algebra morphisms: an internal arrow together with
the internal identity expressing its commuting square. -/
def homType (S : DependentSums C) {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(A B : AlgebraOver F σ) : C.Ty Δ :=
S.sigma (P.arr (U.el A.carrier) (U.el B.carrier))
(I.id (P.arr (U.el (F.obj (C.comp σ C.fst) (U.sub A.carrier C.fst)))
(U.el (U.sub B.carrier C.fst)))
(P.compose
(C.castTm (SmallHom.type_sub U P A.carrier B.carrier C.fst) C.snd)
(A.sub C.fst).structureMap)
(P.compose (B.sub C.fst).structureMap
(F.map (C.comp σ C.fst) (U.sub A.carrier C.fst) (U.sub B.carrier C.fst)
(C.castTm (SmallHom.type_sub U P A.carrier B.carrier C.fst) C.snd))))
end AlgebraOver
namespace CoalgebraOver
variable {F}
/-- Substitution of a coalgebra. -/
def sub {Δ Θ : C.Ctx} {σ : C.Sub Δ Γ} (A : CoalgebraOver F σ) (τ : C.Sub Θ Δ) :
CoalgebraOver F (C.comp σ τ) where
carrier := U.sub A.carrier τ
structureMap := C.castTm
(congrArg (fun X => P.arr (U.el (U.sub A.carrier τ)) (U.el X)) (F.obj_sub σ A.carrier τ))
(SmallHom.sub U P A.structureMap τ)
/-- The source coalgebra-morphism type with its internal commuting-square witness. -/
def homType (S : DependentSums C) {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(A B : CoalgebraOver F σ) : C.Ty Δ :=
S.sigma (P.arr (U.el A.carrier) (U.el B.carrier))
(I.id (P.arr (U.el (U.sub A.carrier C.fst))
(U.el (F.obj (C.comp σ C.fst) (U.sub B.carrier C.fst))))
(P.compose (B.sub C.fst).structureMap
(C.castTm (SmallHom.type_sub U P A.carrier B.carrier C.fst) C.snd))
(P.compose
(F.map (C.comp σ C.fst) (U.sub A.carrier C.fst) (U.sub B.carrier C.fst)
(C.castTm (SmallHom.type_sub U P A.carrier B.carrier C.fst) C.snd))
(A.sub C.fst).structureMap))
end CoalgebraOver
namespace WildEndofunctor
/-- The structure-map type for the generic small algebra carrier. -/
def algebraStructureType : C.Ty (C.ext Γ (U.type Γ)) :=
P.arr (U.el (F.obj C.fst (U.generic Γ))) (U.el (U.generic Γ))
/-- The generic small algebra in `Γ, B : U, k : F B → B`. -/
def genericAlgebra : AlgebraOver F
(C.comp (@C.fst Γ (U.type Γ)) (@C.fst (C.ext Γ (U.type Γ)) F.algebraStructureType)) where
carrier := U.sub (U.generic Γ) C.fst
structureMap := C.castTm
(congrArg (fun X => P.arr (U.el X) (U.el (U.sub (U.generic Γ) C.fst)))
(F.obj_sub C.fst (U.generic Γ) C.fst))
(C.castTm (SmallHom.type_sub U P (F.obj C.fst (U.generic Γ)) (U.generic Γ) C.fst) C.snd)
/-- The structure-map type for the generic small coalgebra carrier. -/
def coalgebraStructureType : C.Ty (C.ext Γ (U.type Γ)) :=
P.arr (U.el (U.generic Γ)) (U.el (F.obj C.fst (U.generic Γ)))
/-- The generic small coalgebra in `Γ, B : U, k : B → F B`. -/
def genericCoalgebra : CoalgebraOver F
(C.comp (@C.fst Γ (U.type Γ)) (@C.fst (C.ext Γ (U.type Γ)) F.coalgebraStructureType)) where
carrier := U.sub (U.generic Γ) C.fst
structureMap := C.castTm
(congrArg (fun X => P.arr (U.el (U.sub (U.generic Γ) C.fst)) (U.el X))
(F.obj_sub C.fst (U.generic Γ) C.fst))
(C.castTm (SmallHom.type_sub U P (U.generic Γ) (F.obj C.fst (U.generic Γ)) C.fst) C.snd)
end WildEndofunctor
namespace Algebra
variable {F}
/-- View a fixed-context algebra as an algebra over the identity substitution. -/
def over (A : Algebra F) : AlgebraOver F C.id := ⟨A.carrier, A.structureMap⟩
/-- The full source initiality type, with internal quantification over carriers,
structure maps, and the complete algebra-morphism type. -/
def initialityType (Q : DependentProducts C) (S : DependentSums C) (A : Algebra F) : C.Ty Γ :=
Q.pi (U.type Γ) (Q.pi F.algebraStructureType
(contractible Q S I
(AlgebraOver.homType S
(C.id_comp (C.comp C.fst C.fst) ▸ A.over.sub (C.comp C.fst C.fst))
F.genericAlgebra)))
/-- A witness of initiality is a term of the source initiality type. -/
abbrev IsInitial (Q : DependentProducts C) (S : DependentSums C) (A : Algebra F) :=
C.Tm Γ (A.initialityType Q S)
end Algebra
namespace Coalgebra
variable {F}
/-- View a fixed-context coalgebra over the identity substitution. -/
def over (A : Coalgebra F) : CoalgebraOver F C.id := ⟨A.carrier, A.structureMap⟩
/-- The full source terminality type, with internal quantification and internal
contractibility of the coalgebra-morphism type. -/
def terminalityType (Q : DependentProducts C) (S : DependentSums C) (A : Coalgebra F) : C.Ty Γ :=
Q.pi (U.type Γ) (Q.pi F.coalgebraStructureType
(contractible Q S I
(CoalgebraOver.homType S F.genericCoalgebra
(C.id_comp (C.comp C.fst C.fst) ▸ A.over.sub (C.comp C.fst C.fst)))))
/-- A witness of terminality is a term of the source terminality type. -/
abbrev IsTerminal (Q : DependentProducts C) (S : DependentSums C) (A : Coalgebra F) :=
C.Tm Γ (A.terminalityType Q S)
end Coalgebra
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_WeakCommutationV2 -/
/-!
# The canonical maps for weak commutation with size quantifiers
The maps are constructed from the functor action and the source quantifier
rules. Their equivalence types therefore refer to these precise arrows.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
{P : DependentProducts C} {S : DependentSums C}
namespace UniversalSizeQuantifier
variable {Z : SizeRules C U I} (Q : UniversalSizeQuantifier C U I Z)
(QS : UniversalSizeSubstitution U I Z Q) (F : FunctionTypes C)
/-- Evaluate an arrow into a universal size type at the generic size. -/
def arrowAtSize {Γ : C.Ctx} {D : U.Code Γ}
{B : U.Code (C.ext Γ (Z.type Γ))} (f : SmallHom U F D (Q.code B)) :
SmallHom U F (U.sub D C.fst) B := by
let π := @C.fst Γ (U.el D)
have hin : C.tySub (U.el (Q.code B)) π = U.el (Q.code (U.sub B (Z.lift π))) :=
(U.el_sub _ _).trans (congrArg U.el (QS.code_sub B π))
let body := Q.unlam (C.castTm hin (F.app (F.sub f π) C.snd))
have hout : C.tySub (U.el (U.sub B (Z.lift π))) (Parametricity.interchange Z D) =
C.tySub (U.el B) C.fst := by
calc
_ = C.tySub (C.tySub (U.el B) (Z.lift π))
(Parametricity.interchange Z D) :=
congrArg (fun X => C.tySub X (Parametricity.interchange Z D))
(U.el_sub B (Z.lift π)).symm
_ = C.tySub (U.el B)
(C.comp (Z.lift π) (Parametricity.interchange Z D)) := C.tySub_comp _ _ _
_ = _ := by
change C.tySub (U.el B)
(C.comp (Parametricity.interchangeSizeMap Z D)
(Parametricity.interchange Z D)) = _
rw [Parametricity.interchangeSizeMap_interchange]
exact F.lam (C.castTm hout (C.tmSub body (Parametricity.interchange Z D)))
/-- Abstract a uniform family of arrows with a size-independent domain. -/
def arrowFromSize {Γ : C.Ctx} {D : U.Code Γ}
{B : U.Code (C.ext Γ (Z.type Γ))}
(f : SmallHom U F (U.sub D C.fst) B) : SmallHom U F D (Q.code B) := by
let π := @C.fst Γ (U.el D)
let swap := Parametricity.interchangeInverse Z D
let body := F.app (F.sub f C.fst) C.snd
have hout : C.tySub (C.tySub (U.el B) C.fst) swap =
U.el (U.sub B (Z.lift π)) := by
rw [C.tySub_comp, Parametricity.interchangeInverse_fst]
exact U.el_sub _ _
have hcode : C.tySub (U.el (Q.code B)) π =
U.el (Q.code (U.sub B (Z.lift π))) :=
(U.el_sub _ _).trans (congrArg U.el (QS.code_sub B π))
exact F.lam (C.castTm hcode.symm (Q.lam (C.castTm hout (C.tmSub body swap))))
end UniversalSizeQuantifier
namespace WeakCommutation
variable (Z : SizeRules C U I) (F : FunctionTypes C)
(K : SmallTypeConstructors C U P S I)
/-- The exact canonical existential map `⟨i,x⟩ ↦ T (φ i) x`. -/
def existsCan (E : ExistentialSizeQuantifier C U I Z)
{Γ : C.Ctx} (T : InternalFunctorData U F Γ)
(A : U.Code (C.ext Γ (Z.type Γ))) :
SmallHom U F (E.code (T.obj C.fst (Z.diamond K E A)))
(T.obj C.id (E.code A)) := by
let D := T.obj C.fst (Z.diamond K E A)
let B := T.obj C.id (E.code A)
let π := @C.fst Γ (Z.type Γ)
let ρ := @C.fst (C.ext Γ (Z.type Γ)) (U.el D)
let f := T.map π (Z.diamond K E A) (U.sub (E.code A) π)
(Parametricity.boundedToExists Z F K E A)
have hB : U.sub B π = T.obj π (U.sub (E.code A) π) := by
dsimp [B]
rw [T.obj_sub, C.id_comp]
have hout : C.tySub (U.el (T.obj π (U.sub (E.code A) π))) ρ =
C.tySub (U.el B) (C.comp π ρ) := by
rw [← hB]
exact (congrArg (fun X => C.tySub X ρ) (U.el_sub B π).symm).trans
(C.tySub_comp _ _ _)
exact E.recursor F D B (C.castTm hout (F.app (F.sub f ρ) C.snd))
/-- Restriction `ψ i : (∀ j, A j) → (∀ j < i, A j)` at the generic size. -/
def allRestriction (Q : UniversalSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q)
{Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) :
SmallHom U F (U.sub (Q.code A) C.fst) (Z.box K Q A) :=
Q.arrowAtSize QS F (Parametricity.allLtMap Z F K Q ZS KS QS A)
/-- The exact canonical universal map `x ↦ λ i, T (ψ i) x`. -/
def allCan (Q : UniversalSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q)
{Γ : C.Ctx} (T : InternalFunctorData U F Γ)
(A : U.Code (C.ext Γ (Z.type Γ))) :
SmallHom U F (T.obj C.id (Q.code A)) (Q.code (T.obj C.fst (Z.box K Q A))) := by
let f := T.map C.fst (U.sub (Q.code A) C.fst) (Z.box K Q A)
(allRestriction Z F K Q ZS KS QS A)
have h : U.sub (T.obj C.id (Q.code A)) (@C.fst Γ (Z.type Γ)) =
T.obj C.fst (U.sub (Q.code A) C.fst) := by
rw [T.obj_sub, C.id_comp]
exact Q.arrowFromSize QS F (C.castTm (congrArg (fun D => F.arr (U.el D) _) h).symm f)
/-- The source hypothesis `Π A : Size → U, isEquiv (can_A)` for existentials. -/
def existsType (J : IdentityElimination C I) (E : ExistentialSizeQuantifier C U I Z)
{Γ : C.Ctx} (T : InternalFunctorData U F Γ) : C.Ty Γ :=
P.pi (SizedFamily.type Z P Γ)
(InternalEquivalence.isEquiv F P I S J
(existsCan Z F K E (T.reindex C.fst) (SizedFamily.generic Z P)))
/-- The source hypothesis `Π A : Size → U, isEquiv (can_A)` for universals. -/
def allType (J : IdentityElimination C I) (Q : UniversalSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q)
{Γ : C.Ctx} (T : InternalFunctorData U F Γ) : C.Ty Γ :=
P.pi (SizedFamily.type Z P Γ)
(InternalEquivalence.isEquiv F P I S J
(allCan Z F K Q ZS KS QS (T.reindex C.fst) (SizedFamily.generic Z P)))
end WeakCommutation
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingAdjunctionV2 -/
/-!
# The object operations in the quantifier adjunctions
Constant carriers use the source extraction and insertion maps. Quantified
carriers use the inverse of the precise weak-commutation map. The hom-equivalence
types retain complete internal morphism sums, including commuting paths. They
do not, by themselves, assert naturality or an adjunction.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
namespace QuantifierAdjunction
variable (T : CoreTheory C)
/-- Erase the irrelevant size from an existential of a constant small type. -/
def forgetSize {Γ : C.Ctx} (A : T.univ.Code Γ) :
SmallHom T.univ T.functions (T.ex.code (T.univ.sub A C.fst)) A := by
let π := @C.fst (C.ext Γ (T.size.type Γ)) (T.univ.el (T.univ.sub A C.fst))
have h : C.tySub (T.univ.el (T.univ.sub A C.fst)) π =
C.tySub (T.univ.el A) (C.comp C.fst π) :=
(congrArg (fun V => C.tySub V π) (T.univ.el_sub A C.fst).symm).trans
(C.tySub_comp _ _ _)
exact T.ex.recursor T.functions (T.univ.sub A C.fst) A (C.castTm h C.snd)
/-- The source `extract_A i ⟨j, a⟩ = a` for a bounded constant family. -/
def extract {Γ : C.Ctx} (A : T.univ.Code Γ) :
SmallHom T.univ T.functions
(T.size.diamond T.small T.ex (T.univ.sub A C.fst)) (T.univ.sub A C.fst) :=
T.functions.compose (SmallHom.sub T.univ T.functions (forgetSize T A) C.fst)
(Parametricity.boundedToExists T.size T.functions T.small T.ex (T.univ.sub A C.fst))
/-- Constant introduction into the universal size type. -/
def repeatAll {Γ : C.Ctx} (A : T.univ.Code Γ) :
SmallHom T.univ T.functions A (T.all.code (T.univ.sub A C.fst)) :=
T.all.arrowFromSize T.allSubstitution T.functions
(T.functions.identity (T.univ.el (T.univ.sub A C.fst)))
/-- The source `insert_A i a = λ j < i, a`. -/
def insert {Γ : C.Ctx} (A : T.univ.Code Γ) :
SmallHom T.univ T.functions (T.univ.sub A C.fst)
(T.size.box T.small T.all (T.univ.sub A C.fst)) :=
T.functions.compose
(WeakCommutation.allRestriction T.size T.functions T.small T.all
T.sizeSubstitution T.smallSubstitution T.allSubstitution (T.univ.sub A C.fst))
(SmallHom.sub T.univ T.functions (repeatAll T A) C.fst)
/-- Extract the inverse of the source existential canonical map from its
single internally quantified half-adjoint-equivalence witness. -/
def existsInverse {Γ : C.Ctx} (D : InternalFunctorData T.univ T.functions Γ)
(h : C.Tm Γ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex D))
(A : T.univ.Code (C.ext Γ (T.size.type Γ))) :
SmallHom T.univ T.functions (D.obj C.id (T.ex.code A))
(T.ex.code (D.obj C.fst (T.size.diamond T.small T.ex A))) := by
let G := SizedFamily.generic T.size T.products (Γ := Γ)
let τ := SizedFamily.extend T.size T.products C.id A
have hin : T.univ.sub ((D.reindex C.fst).obj C.id (T.ex.code G)) τ =
D.obj C.id (T.ex.code A) := by
dsimp [InternalFunctorData.reindex]
rw [D.obj_sub, T.exSubstitution.code_sub, SizedFamily.generic_sub_extend,
C.comp_id, SizedFamily.extend_fst]
have hbase : C.comp (C.comp C.fst C.fst) (T.size.lift τ) =
(@C.fst Γ (T.size.type Γ)) := by
rw [C.assoc, T.size.lift_fst, ← C.assoc, SizedFamily.extend_fst, C.id_comp]
have hout : T.univ.sub (T.ex.code ((D.reindex C.fst).obj C.fst
(T.size.diamond T.small T.ex G))) τ =
T.ex.code (D.obj C.fst (T.size.diamond T.small T.ex A)) := by
dsimp [InternalFunctorData.reindex]
rw [T.exSubstitution.code_sub, D.obj_sub, hbase,
T.size.diamond_sub T.small T.ex T.sizeSubstitution T.smallSubstitution T.exSubstitution,
SizedFamily.generic_sub_extend]
let inverse := T.sums.fst (T.products.unlam h)
exact C.castTm (by
rw [SmallHom.type_sub, hin, hout]) (C.tmSub inverse τ)
/-- Extract the inverse of the source universal canonical map, retaining its
internally quantified provenance. -/
def allInverse {Γ : C.Ctx} (D : InternalFunctorData T.univ T.functions Γ)
(h : C.Tm Γ (WeakCommutation.allType T.size T.functions T.small
T.identityElimination T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution D))
(A : T.univ.Code (C.ext Γ (T.size.type Γ))) :
SmallHom T.univ T.functions (T.all.code (D.obj C.fst (T.size.box T.small T.all A)))
(D.obj C.id (T.all.code A)) := by
let G := SizedFamily.generic T.size T.products (Γ := Γ)
let τ := SizedFamily.extend T.size T.products C.id A
have hout : T.univ.sub ((D.reindex C.fst).obj C.id (T.all.code G)) τ =
D.obj C.id (T.all.code A) := by
dsimp [InternalFunctorData.reindex]
rw [D.obj_sub, T.allSubstitution.code_sub, SizedFamily.generic_sub_extend,
C.comp_id, SizedFamily.extend_fst]
have hbase : C.comp (C.comp C.fst C.fst) (T.size.lift τ) =
(@C.fst Γ (T.size.type Γ)) := by
rw [C.assoc, T.size.lift_fst, ← C.assoc, SizedFamily.extend_fst, C.id_comp]
have hin : T.univ.sub (T.all.code ((D.reindex C.fst).obj C.fst
(T.size.box T.small T.all G))) τ =
T.all.code (D.obj C.fst (T.size.box T.small T.all A)) := by
dsimp [InternalFunctorData.reindex]
rw [T.allSubstitution.code_sub, D.obj_sub, hbase,
T.size.box_sub T.small T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution,
SizedFamily.generic_sub_extend]
let inverse := T.sums.fst (T.products.unlam h)
exact C.castTm (by
rw [SmallHom.type_sub, hin, hout]) (C.tmSub inverse τ)
variable {Γ : C.Ctx} (F : WildEndofunctor T.univ T.functions T.identities Γ)
/-- The constant size-indexed algebra, with structure `k ∘ F(extract)`. -/
def constantAlgebra {Δ : C.Ctx} {σ : C.Sub Δ Γ} (A : AlgebraOver F σ) :
Sized.AlgebraOver T F σ where
carrier := T.univ.sub A.carrier C.fst
structureMap := Sized.ofAt T.size T.functions T.small T.all T.functionProducts
(T.functions.compose
(C.castTm (congrArg (fun X => T.functions.arr (T.univ.el X)
(T.univ.el (T.univ.sub A.carrier C.fst))) (F.obj_sub σ A.carrier C.fst))
(SmallHom.sub T.univ T.functions A.structureMap C.fst))
(F.map (C.comp σ C.fst) (T.size.diamond T.small T.ex (T.univ.sub A.carrier C.fst))
(T.univ.sub A.carrier C.fst) (extract T A.carrier)))
/-- The constant size-indexed coalgebra, with structure `F(insert) ∘ k`. -/
def constantCoalgebra {Δ : C.Ctx} {σ : C.Sub Δ Γ} (A : CoalgebraOver F σ) :
Sized.CoalgebraOver T F σ where
carrier := T.univ.sub A.carrier C.fst
structureMap := Sized.ofAt T.size T.functions T.small T.all T.functionProducts
(T.functions.compose
(F.map (C.comp σ C.fst) (T.univ.sub A.carrier C.fst)
(T.size.box T.small T.all (T.univ.sub A.carrier C.fst)) (insert T A.carrier))
(C.castTm (congrArg (fun X => T.functions.arr
(T.univ.el (T.univ.sub A.carrier C.fst)) (T.univ.el X)) (F.obj_sub σ A.carrier C.fst))
(SmallHom.sub T.univ T.functions A.structureMap C.fst)))
/-- Existentially quantify a size-indexed algebra. Its structure is exactly
`(∃ k) ∘ can⁻¹`, using the inverse supplied by the source weak-commutation term. -/
def existsAlgebra {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex (F.toInternalFunctorData.reindex σ)))
(A : Sized.AlgebraOver T F σ) : AlgebraOver F σ where
carrier := T.ex.code A.carrier
structureMap := by
let inverse := existsInverse T (F.toInternalFunctorData.reindex σ) h A.carrier
have hi : (F.toInternalFunctorData.reindex σ).obj C.id (T.ex.code A.carrier) =
F.obj σ (T.ex.code A.carrier) :=
congrArg (fun ρ => F.obj ρ (T.ex.code A.carrier)) (C.comp_id σ)
let inverse' := C.castTm (congrArg (fun X => T.functions.arr (T.univ.el X)
(T.univ.el (T.ex.code (Sized.liftObjectOver T F σ
(T.size.diamond T.small T.ex A.carrier))))) hi) inverse
exact T.functions.compose
(T.ex.map T.functions _ A.carrier
(Sized.eval T.size T.functions T.small T.all T.functionProducts A.structureMap)) inverse'
/-- Universally quantify a size-indexed coalgebra. Its structure is exactly
`can⁻¹ ∘ (∀ k)`. -/
def allCoalgebra {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.allType T.size T.functions T.small T.identityElimination
T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
(F.toInternalFunctorData.reindex σ)))
(A : Sized.CoalgebraOver T F σ) : CoalgebraOver F σ where
carrier := T.all.code A.carrier
structureMap := by
let inverse := allInverse T (F.toInternalFunctorData.reindex σ) h A.carrier
have hi : (F.toInternalFunctorData.reindex σ).obj C.id (T.all.code A.carrier) =
F.obj σ (T.all.code A.carrier) :=
congrArg (fun ρ => F.obj ρ (T.all.code A.carrier)) (C.comp_id σ)
let inverse' := C.castTm (congrArg (fun X => T.functions.arr
(T.univ.el (T.all.code (Sized.liftObjectOver T F σ
(T.size.box T.small T.all A.carrier)))) (T.univ.el X)) hi) inverse
exact T.functions.compose inverse'
(T.all.map T.functions T.allSubstitution A.carrier _
(Sized.eval T.size T.functions T.small T.all T.functionProducts A.structureMap))
/-- The internal hom-equivalence type used in the proposed existential
adjunction argument. Both sides retain commuting paths; naturality is separate. -/
def existsHomEquivalenceType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex (F.toInternalFunctorData.reindex σ)))
(A : Sized.AlgebraOver T F σ) (B : AlgebraOver F σ) : C.Ty Δ :=
InternalEquivalence.equivalence T.functions T.products T.identities T.sums T.identityElimination
(AlgebraOver.homType T.sums (existsAlgebra T F h A) B)
(Sized.AlgebraOver.homType A (constantAlgebra T F B))
/-- The internal hom-equivalence type used in the universal adjunction argument.
It compares complete coalgebra morphisms, but does not assert naturality. -/
def allHomEquivalenceType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.allType T.size T.functions T.small T.identityElimination
T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
(F.toInternalFunctorData.reindex σ)))
(B : CoalgebraOver F σ) (A : Sized.CoalgebraOver T F σ) : C.Ty Δ :=
InternalEquivalence.equivalence T.functions T.products T.identities T.sums T.identityElimination
(Sized.CoalgebraOver.homType (constantCoalgebra T F B) A)
(CoalgebraOver.homType T.sums B (allCoalgebra T F h A))
end QuantifierAdjunction
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingFixpointsV2 -/
/-!
# The source's recursive codes for inductive and coinductive carriers
Section 3.3 and Appendix B define the sized carriers by recursion into the large
universe type. The recursive input is only defined below the current size. It is
therefore evaluated after introducing both a smaller size and its bound proof;
no arbitrary extension to a total family of universe codes is used.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.EncodingFixpoints
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I) (P : DependentProducts C) (F : FunctionTypes C)
abbrev sizeContext (Γ : C.Ctx) : C.Ctx := C.ext Γ (Z.type Γ)
/-- At the current size, the recursive input has type `Π j, j < i → U`. -/
abbrev recursiveType (Γ : C.Ctx) : C.Ty (sizeContext Z Γ) :=
Z.bounded P F (U.type (sizeContext Z Γ))
abbrev recursiveContext (Γ : C.Ctx) : C.Ctx :=
C.ext (sizeContext Z Γ) (recursiveType Z P F Γ)
abbrev bodyContext (Γ : C.Ctx) : C.Ctx :=
C.ext (recursiveContext Z P F Γ) (Z.type (recursiveContext Z P F Γ))
abbrev recursiveProjection (Γ : C.Ctx) :
C.Sub (recursiveContext Z P F Γ) (sizeContext Z Γ) := C.fst
abbrev bodyProjection (Γ : C.Ctx) :
C.Sub (bodyContext Z P F Γ) (recursiveContext Z P F Γ) := C.fst
/-- The body of the recursive input before its dependent product is formed. -/
abbrev recursiveBody (Γ : C.Ctx) :
C.Ty (C.ext (sizeContext Z Γ) (Z.type (sizeContext Z Γ))) :=
F.arr Z.bound (C.tySub (U.type (sizeContext Z Γ)) Z.inner)
/-- The generic recursive family, reindexed into the context containing it. -/
def genericRecursive (Γ : C.Ctx) :
C.Tm (recursiveContext Z P F Γ)
(P.pi (Z.type (recursiveContext Z P F Γ))
(C.tySub (recursiveBody Z F Γ)
(Z.lift (recursiveProjection Z P F Γ)))) :=
C.castTm (Z.pi_sub P (recursiveBody Z F Γ)
(recursiveProjection Z P F Γ)) C.snd
theorem innerSize_type (Γ : C.Ctx) :
C.tySub (C.tySub (Z.type (sizeContext Z Γ)) (recursiveProjection Z P F Γ))
(bodyProjection Z P F Γ) = Z.type (bodyContext Z P F Γ) :=
(C.tySub_comp _ _ _).trans (Z.type_sub _)
/-- Supply the newly bound size to the reindexed recursive family. -/
def innerSizeSub (Γ : C.Ctx) : C.Sub (bodyContext Z P F Γ)
(C.ext (recursiveContext Z P F Γ)
(C.tySub (Z.type (sizeContext Z Γ)) (recursiveProjection Z P F Γ))) :=
C.pair (bodyProjection Z P F Γ)
(C.castTm (innerSize_type Z P F Γ).symm (Z.generic (recursiveContext Z P F Γ)))
/-- Forget the recursive family while retaining the current and smaller sizes. -/
def boundsSub (Γ : C.Ctx) : C.Sub (bodyContext Z P F Γ)
(C.ext (sizeContext Z Γ) (Z.type (sizeContext Z Γ))) :=
Z.lift (recursiveProjection Z P F Γ)
/-- The actual source bound code `j < i` in the recursive body context. -/
def guardCode (Γ : C.Ctx) : U.Code (bodyContext Z P F Γ) :=
U.sub Z.boundCode (boundsSub Z P F Γ)
theorem recursiveArrow_type (Γ : C.Ctx) :
C.tySub (recursiveBody Z F Γ) (boundsSub Z P F Γ) =
F.arr (U.el (guardCode Z P F Γ)) (U.type (bodyContext Z P F Γ)) := by
rw [recursiveBody, F.arr_sub]
apply congrArg₂ F.arr
· exact U.el_sub Z.boundCode (boundsSub Z P F Γ)
· exact (C.tySub_comp _ _ _).trans (U.type_sub _)
/-- The internal function `X j : (j < i) → U`. -/
def recursiveArrow (Γ : C.Ctx) : C.Tm (bodyContext Z P F Γ)
(F.arr (U.el (guardCode Z P F Γ)) (U.type (bodyContext Z P F Γ))) :=
C.castTm (recursiveArrow_type Z P F Γ) (P.unlam (genericRecursive Z P F Γ))
/-- The universe code `X j p` after the bound proof has been introduced. -/
def recursiveValue (Γ : C.Ctx) :
U.Code (C.ext (bodyContext Z P F Γ) (U.el (guardCode Z P F Γ))) :=
C.castTm (U.type_sub C.fst) (F.app (F.sub (recursiveArrow Z P F Γ) C.fst) C.snd)
/-- Bounded existential packaging of the partial recursive family: `∃ j. Σ p : j < i, X j p`. -/
def existentialPack {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(E : ExistentialSizeQuantifier C U I Z) (Γ : C.Ctx) :
U.Code (recursiveContext Z P F Γ) :=
E.code (K.sigma (guardCode Z P F Γ) (recursiveValue Z P F Γ))
/-- Bounded universal packaging of the partial recursive family: `∀ j. Π p : j < i, X j p`. -/
def universalPack {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) (Γ : C.Ctx) :
U.Code (recursiveContext Z P F Γ) :=
Q.code (K.pi (guardCode Z P F Γ) (recursiveValue Z P F Γ))
/-- The step `λ i X, T (∃ j < i, X j)` used in the source's sized μ definition. -/
def muStep {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(E : ExistentialSizeQuantifier C U I Z) {Γ : C.Ctx} (T : WildEndofunctor U F I Γ) :
C.Tm Γ (P.pi (Z.type Γ)
(F.arr (recursiveType Z P F Γ) (U.type (sizeContext Z Γ)))) :=
P.lam (F.lam (C.castTm (U.type_sub C.fst).symm
(T.obj (C.comp C.fst (recursiveProjection Z P F Γ)) (existentialPack Z P F K E Γ))))
/-- The step `λ i X, T (∀ j < i, X j)` used in the source's sized ν definition. -/
def nuStep {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) {Γ : C.Ctx} (T : WildEndofunctor U F I Γ) :
C.Tm Γ (P.pi (Z.type Γ)
(F.arr (recursiveType Z P F Γ) (U.type (sizeContext Z Γ)))) :=
P.lam (F.lam (C.castTm (U.type_sub C.fst).symm
(T.obj (C.comp C.fst (recursiveProjection Z P F Γ)) (universalPack Z P F K Q Γ))))
/-- The source's sized inductive carrier `μ◇ T`, defined by the primitive size recursor. -/
def sizedMu {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(E : ExistentialSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) : U.Code (sizeContext Z Γ) :=
P.unlam (R.fix (U.type (sizeContext Z Γ)) (muStep Z P F K E T))
/-- The source's sized coinductive carrier `ν□ T`, defined by the primitive size recursor. -/
def sizedNu {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) : U.Code (sizeContext Z Γ) :=
P.unlam (R.fix (U.type (sizeContext Z Γ)) (nuStep Z P F K Q T))
/-- The actual propositional recursor beta witness for the sized μ code. -/
def sizedMu_fix_beta {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(E : ExistentialSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) :
C.Tm Γ (P.pi (Z.type Γ)
(I.id (U.type (sizeContext Z Γ)) (sizedMu Z P F K E R T)
(F.app (P.unlam (muStep Z P F K E T))
(Z.restrict P F (R.fix (U.type (sizeContext Z Γ)) (muStep Z P F K E T)))))) :=
R.beta (U.type (sizeContext Z Γ)) (muStep Z P F K E T)
/-- The actual propositional recursor beta witness for the sized ν code. -/
def sizedNu_fix_beta {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) :
C.Tm Γ (P.pi (Z.type Γ)
(I.id (U.type (sizeContext Z Γ)) (sizedNu Z P F K Q R T)
(F.app (P.unlam (nuStep Z P F K Q T))
(Z.restrict P F (R.fix (U.type (sizeContext Z Γ)) (nuStep Z P F K Q T)))))) :=
R.beta (U.type (sizeContext Z Γ)) (nuStep Z P F K Q T)
/-- The source's unsized inductive carrier `μ T := ∃ i, μ◇ T i`. -/
def mu {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(E : ExistentialSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) : U.Code Γ :=
E.code (sizedMu Z P F K E R T)
/-- The source's unsized coinductive carrier `ν T := ∀ i, ν□ T i`. -/
def nu {S : DependentSums C} (K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) (R : SizeRecursion C U I Z P F)
{Γ : C.Ctx} (T : WildEndofunctor U F I Γ) : U.Code Γ :=
Q.code (sizedNu Z P F K Q R T)
end LaarakkerOttenVanDenBerg2026.V2.Theory.EncodingFixpoints
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingFixpointBetaV2 -/
/-! Unfolding the recursive carrier codes by the source's substitution and beta rules. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
namespace FunctionTypes
variable (F : FunctionTypes C)
theorem sub_congr {Γ Δ : C.Ctx} {A A' B B' : C.Ty Γ}
(hA : A = A') (hB : B = B')
{f : C.Tm Γ (F.arr A B)} {g : C.Tm Γ (F.arr A' B')}
(h : HEq f g) (σ : C.Sub Δ Γ) : HEq (F.sub f σ) (F.sub g σ) := by
cases hA
cases hB
cases h
rfl
/-- Evaluation of a lambda at the generic variable is its contextual body. -/
theorem genericApp_lam {P : DependentProducts C} (FP : FunctionProductCompatibility F P)
{Γ : C.Ctx} {A B : C.Ty Γ} (b : C.Tm (C.ext Γ A) (C.tySub B C.fst)) :
F.app (F.sub (F.lam b) C.fst) C.snd = b := by
have h := (FP.lam_eq (F.app (F.sub (F.lam b) C.fst) C.snd)).symm.trans
((heq_of_eq (F.eta (F.lam b))).trans (FP.lam_eq b))
have h' := congrArg P.unlam (eq_of_heq h)
simpa only [P.beta] using h'
theorem genericApp_sub {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (σ : C.Sub Δ Γ) :
HEq (C.tmSub (F.app (F.sub f C.fst) C.snd) (C.lift σ A))
(F.app (F.sub (F.sub f σ) C.fst) C.snd) := by
have hs (τ υ : C.Sub (C.ext Δ (C.tySub A σ)) Γ) (e : τ = υ) :
HEq (F.sub f τ) (F.sub f υ) := by cases e; rfl
have hB : C.tySub (C.tySub B C.fst) (C.lift σ A) =
C.tySub (C.tySub B σ) C.fst := by
rw [C.tySub_comp, C.lift_fst, C.tySub_comp]
exact (heq_of_eq (F.app_sub (F.sub f C.fst) C.snd (C.lift σ A))).trans
(F.app_congr (C.tySub_lift σ A) hB
((F.sub_comp_heq f C.fst (C.lift σ A)).trans
((hs _ _ (C.lift_fst σ A)).trans (F.sub_comp_heq f σ C.fst).symm))
(C.lift_snd σ A))
theorem genericApp_sub_as {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (σ : C.Sub Δ Γ) (A' B' : C.Ty Δ)
(hA : C.tySub A σ = A') (hB : C.tySub B σ = B')
(g : C.Tm Δ (F.arr A' B')) (hg : HEq (F.sub f σ) g) :
HEq (C.tmSub (F.app (F.sub f C.fst) C.snd) (C.liftAs σ A A' hA))
(F.app (F.sub g C.fst) C.snd) := by
subst A'
subst B'
have e := eq_of_heq hg
subst g
exact F.genericApp_sub f σ
end FunctionTypes
namespace Universe
variable (U : Universe C)
theorem liftElAs_eq_liftAs {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ)
(A' : U.Code Δ) (h : U.sub A σ = A') :
U.liftElAs σ A A' h =
C.liftAs σ (U.el A) (U.el A') ((U.el_sub A σ).trans (congrArg U.el h)) := by
apply C.sub_ext
· exact (U.liftElAs_fst _ _ _ _).trans (C.liftAs_fst _ _ _ _).symm
· exact (U.liftElAs_snd _ _ _ _).trans (C.liftAs_snd _ _ _ _).symm
end Universe
namespace SizeRules
variable (Z : SizeRules C U I)
theorem lift_section {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (τ : C.Sub Γ Δ)
(h : C.comp σ τ = C.id) : C.comp (Z.lift σ) (Z.lift τ) = C.id := by
apply Z.hom_ext
· rw [← C.assoc, Z.lift_fst, C.assoc, Z.lift_fst,
← C.assoc, h, C.id_comp, C.comp_id]
· rw [← Z.sub_comp, Z.generic_sub_lift, Z.generic_sub_lift, Z.sub_id]
end SizeRules
namespace EncodingFixpoints
variable (Z : SizeRules C U I) (P : DependentProducts C) (F : FunctionTypes C)
/-- Substitute the restricted family for the generic recursive argument. -/
abbrev restrictionSub {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
C.Sub (sizeContext Z Γ) (recursiveContext Z P F Γ) :=
C.termSub (Z.restrict P F h)
theorem boundsSub_restriction {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
C.comp (boundsSub Z P F Γ) (Z.lift (restrictionSub Z P F h)) = C.id :=
Z.lift_section C.fst (C.termSub (Z.restrict P F h)) (C.termSub_fst _)
theorem guardCode_restriction {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
U.sub (guardCode Z P F Γ) (Z.lift (restrictionSub Z P F h)) = Z.boundCode := by
rw [guardCode, U.sub_comp, boundsSub_restriction]
exact eq_of_heq ((C.castTm_heq _ _).trans (C.tmSub_id _))
theorem recursiveBody_restriction {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
C.tySub (C.tySub (recursiveBody Z F Γ) (boundsSub Z P F Γ))
(Z.lift (restrictionSub Z P F h)) = recursiveBody Z F Γ := by
rw [C.tySub_comp, boundsSub_restriction, C.tySub_id]
/-- Evaluating the generic recursive argument after substitution gives the restriction. -/
theorem recursiveArrow_restriction {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
HEq (F.sub (recursiveArrow Z P F Γ) (Z.lift (restrictionSub Z P F h)))
(P.unlam (Z.restrict P F h)) := by
let τ := restrictionSub Z P F h
have hf : HEq (C.tmSub (genericRecursive Z P F Γ) τ) (Z.restrict P F h) :=
(C.tmSub_heq (Z.pi_sub P (recursiveBody Z F Γ) C.fst).symm
(C.castTm_heq _ _) τ).trans (C.termSub_snd _)
exact (F.sub_heq _ _).trans
((C.tmSub_heq (recursiveArrow_type Z P F Γ).symm
(C.castTm_heq _ _) (Z.lift τ)).trans
((heq_of_eq (Z.unlam_sub P (genericRecursive Z P F Γ) τ)).symm.trans
(P.unlam_congr (recursiveBody_restriction Z P F h)
((C.castTm_heq _ _).trans hf))))
/-- The bound proof is passed to the recursive family; after restriction the result is `h j`. -/
theorem recursiveValue_restriction (FP : FunctionProductCompatibility F P) {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
U.sub (recursiveValue Z P F Γ)
(U.liftElAs (Z.lift (restrictionSub Z P F h)) (guardCode Z P F Γ) Z.boundCode
(guardCode_restriction Z P F h)) =
U.sub (U.sub (P.unlam h) Z.inner) C.fst := by
let s := Z.lift (restrictionSub Z P F h)
let l := U.liftElAs s (guardCode Z P F Γ) Z.boundCode
(guardCode_restriction Z P F h)
have hA : C.tySub (U.el (guardCode Z P F Γ)) s = Z.bound :=
(U.el_sub _ _).trans (congrArg U.el (guardCode_restriction Z P F h))
have hB : C.tySub (U.type (bodyContext Z P F Γ)) s =
C.tySub (U.type (sizeContext Z Γ)) Z.inner :=
(U.type_sub s).trans (U.type_sub Z.inner).symm
have ha := F.genericApp_sub_as (recursiveArrow Z P F Γ) s Z.bound
(C.tySub (U.type (sizeContext Z Γ)) Z.inner) hA hB
(P.unlam (Z.restrict P F h)) (recursiveArrow_restriction Z P F h)
have hl : l = C.liftAs s (U.el (guardCode Z P F Γ)) Z.bound hA :=
U.liftElAs_eq_liftAs _ _ _ _
have hbody : F.app (F.sub (P.unlam (Z.restrict P F h)) C.fst) C.snd =
C.tmSub (C.tmSub (P.unlam h) Z.inner) C.fst := by
rw [SizeRules.restrict, P.beta]
exact F.genericApp_lam FP _
apply eq_of_heq
refine (C.castTm_heq _ _).trans ?_
refine (C.tmSub_heq (U.type_sub C.fst).symm (C.castTm_heq _ _) l).trans ?_
have ha' : HEq
(C.tmSub (F.app (F.sub (recursiveArrow Z P F Γ) C.fst) C.snd) l)
(C.tmSub (C.tmSub (P.unlam h) Z.inner) (C.fst (A := Z.bound))) := by
rw [hl]
exact ha.trans (heq_of_eq hbody)
refine ha'.trans ?_
exact ((C.tmSub_heq (U.type_sub Z.inner).symm (C.castTm_heq _ _) C.fst).symm.trans
(C.castTm_heq _ _).symm)
theorem existentialPack_restriction {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (E : ExistentialSizeQuantifier C U I Z)
(FP : FunctionProductCompatibility F P) (KS : SmallTypeSubstitution U P S I K)
(ES : ExistentialSizeSubstitution U I Z E) {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
U.sub (existentialPack Z P F K E Γ) (restrictionSub Z P F h) =
Z.diamond K E (P.unlam h) := by
rw [existentialPack, ES.code_sub,
K.sigma_sub_as KS _ _ _ _ (guardCode_restriction Z P F h),
recursiveValue_restriction Z P F FP]
rfl
theorem universalPack_restriction {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (Q : UniversalSizeQuantifier C U I Z)
(FP : FunctionProductCompatibility F P) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q) {Γ : C.Ctx}
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
U.sub (universalPack Z P F K Q Γ) (restrictionSub Z P F h) =
Z.box K Q (P.unlam h) := by
rw [universalPack, QS.code_sub,
K.pi_sub_as KS _ _ _ _ (guardCode_restriction Z P F h),
recursiveValue_restriction Z P F FP]
rfl
/-- The μ step computes to the functor applied to the exact bounded existential. -/
theorem muStep_restriction {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (E : ExistentialSizeQuantifier C U I Z)
(FP : FunctionProductCompatibility F P) (KS : SmallTypeSubstitution U P S I K)
(ES : ExistentialSizeSubstitution U I Z E) {Γ : C.Ctx}
(T : WildEndofunctor U F I Γ)
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
F.app (P.unlam (muStep Z P F K E T)) (Z.restrict P F h) =
T.obj C.fst (Z.diamond K E (P.unlam h)) := by
let b := T.obj (C.comp C.fst (recursiveProjection Z P F Γ))
(existentialPack Z P F K E Γ)
have hb : U.sub b (restrictionSub Z P F h) =
T.obj C.fst (Z.diamond K E (P.unlam h)) := by
dsimp [b]
rw [T.obj_sub, existentialPack_restriction Z P F K E FP KS ES]
congr 1
exact (C.assoc _ _ _).trans
((congrArg (C.comp C.fst) (C.termSub_fst _)).trans (C.comp_id _))
rw [muStep, P.beta]
apply eq_of_heq
exact (F.beta _ (Z.restrict P F h)).trans
((C.tmSub_heq (U.type_sub C.fst) (C.castTm_heq _ _) (restrictionSub Z P F h)).trans
((C.castTm_heq _ _).symm.trans (heq_of_eq hb)))
/-- The ν step computes to the functor applied to the exact bounded universal. -/
theorem nuStep_restriction {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (Q : UniversalSizeQuantifier C U I Z)
(FP : FunctionProductCompatibility F P) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q) {Γ : C.Ctx}
(T : WildEndofunctor U F I Γ)
(h : C.Tm Γ (P.pi (Z.type Γ) (U.type (sizeContext Z Γ)))) :
F.app (P.unlam (nuStep Z P F K Q T)) (Z.restrict P F h) =
T.obj C.fst (Z.box K Q (P.unlam h)) := by
let b := T.obj (C.comp C.fst (recursiveProjection Z P F Γ))
(universalPack Z P F K Q Γ)
have hb : U.sub b (restrictionSub Z P F h) =
T.obj C.fst (Z.box K Q (P.unlam h)) := by
dsimp [b]
rw [T.obj_sub, universalPack_restriction Z P F K Q FP KS QS]
congr 1
exact (C.assoc _ _ _).trans
((congrArg (C.comp C.fst) (C.termSub_fst _)).trans (C.comp_id _))
rw [nuStep, P.beta]
apply eq_of_heq
exact (F.beta _ (Z.restrict P F h)).trans
((C.tmSub_heq (U.type_sub C.fst) (C.castTm_heq _ _) (restrictionSub Z P F h)).trans
((C.castTm_heq _ _).symm.trans (heq_of_eq hb)))
end EncodingFixpoints
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingStructuresV2 -/
/-!
# The source algebra and coalgebra structures on the recursive carriers
The size-recursion equation is normalized to the literal bounded code. Its
identity witness is decoded using J-derived transport. Quantification then
uses the inverse of the canonical weak-commutation map.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
namespace Universe
variable (U : Universe C) (I : IdentityTypes C) (J : IdentityElimination C I)
theorem generic_decode_sub {Γ : C.Ctx} (A : U.Code Γ) :
C.tySub (U.el (U.generic Γ)) (C.termSub A) = U.el A :=
(U.el_sub _ _).trans (congrArg U.el (U.generic_sub_extend C.id A))
/-- Decode an internal equality of universe codes by J-derived transport. -/
def transport {Γ : C.Ctx} {A B : U.Code Γ}
(p : C.Tm Γ (I.id (U.type Γ) A B)) (a : C.Tm Γ (U.el A)) : C.Tm Γ (U.el B) :=
C.castTm (U.generic_decode_sub B)
(InternalPath.transport I J (U.el (U.generic Γ)) p
(C.castTm (U.generic_decode_sub A).symm a))
def pathSub {Γ Δ : C.Ctx} {A B : U.Code Γ}
(p : C.Tm Γ (I.id (U.type Γ) A B)) (σ : C.Sub Δ Γ) :
C.Tm Δ (I.id (U.type Δ) (U.sub A σ) (U.sub B σ)) :=
C.castTm ((I.id_sub A B σ).trans
(I.id_congr (U.type_sub σ) (C.castTm_heq _ _).symm (C.castTm_heq _ _).symm))
(C.tmSub p σ)
/-- The internal arrow induced by a universe path, with no equality reflection. -/
def pathArrow (F : FunctionTypes C) {Γ : C.Ctx} {A B : U.Code Γ}
(p : C.Tm Γ (I.id (U.type Γ) A B)) : SmallHom U F A B :=
F.lam (C.castTm (U.el_sub B C.fst).symm
(U.transport I J (U.pathSub I p C.fst) (C.castTm (U.el_sub A C.fst) C.snd)))
end Universe
namespace EncodingFixpoints
variable (T : CoreTheory C) {Γ : C.Ctx}
(D : WildEndofunctor T.univ T.functions T.identities Γ)
/-- The normalized source equation `μ◇ D i = D (◇ (μ◇ D) i)` in the universe. -/
def sizedMu_path : C.Tm (C.ext Γ (T.size.type Γ))
(T.identities.id (T.univ.type (C.ext Γ (T.size.type Γ)))
(sizedMu T.size T.products T.functions T.small T.ex T.recursion D)
(D.obj C.fst (T.size.diamond T.small T.ex
(sizedMu T.size T.products T.functions T.small T.ex T.recursion D)))) :=
C.castTm (congrArg (T.identities.id _ _)
(muStep_restriction T.size T.products T.functions T.small T.ex
T.functionProducts T.smallSubstitution T.exSubstitution D
(T.recursion.fix _ (muStep T.size T.products T.functions T.small T.ex D))))
(T.products.unlam (sizedMu_fix_beta T.size T.products T.functions
T.small T.ex T.recursion D))
/-- The normalized source equation `ν□ D i = D (□ (ν□ D) i)` in the universe. -/
def sizedNu_path : C.Tm (C.ext Γ (T.size.type Γ))
(T.identities.id (T.univ.type (C.ext Γ (T.size.type Γ)))
(sizedNu T.size T.products T.functions T.small T.all T.recursion D)
(D.obj C.fst (T.size.box T.small T.all
(sizedNu T.size T.products T.functions T.small T.all T.recursion D)))) :=
C.castTm (congrArg (T.identities.id _ _)
(nuStep_restriction T.size T.products T.functions T.small T.all
T.functionProducts T.smallSubstitution T.allSubstitution D
(T.recursion.fix _ (nuStep T.size T.products T.functions T.small T.all D))))
(T.products.unlam (sizedNu_fix_beta T.size T.products T.functions
T.small T.all T.recursion D))
/-- The sized inductive structure, obtained by reversing and decoding its universe equation. -/
def sizedMuAlgebra : Sized.AlgebraOver T D C.id where
carrier := sizedMu T.size T.products T.functions T.small T.ex T.recursion D
structureMap := by
apply Sized.ofAt T.size T.functions T.small T.all T.functionProducts
have hd : D.obj (C.comp C.id C.fst)
(T.size.diamond T.small T.ex
(sizedMu T.size T.products T.functions T.small T.ex T.recursion D)) =
D.obj C.fst (T.size.diamond T.small T.ex
(sizedMu T.size T.products T.functions T.small T.ex T.recursion D)) := by
rw [C.id_comp]
exact C.castTm (congrArg (fun A => T.functions.arr (T.univ.el A) _) hd).symm
(T.univ.pathArrow T.identities T.identityElimination T.functions
(InternalPath.symm T.identities T.identityElimination (sizedMu_path T D)))
/-- The sized coinductive structure, obtained by decoding its universe equation. -/
def sizedNuCoalgebra : Sized.CoalgebraOver T D C.id where
carrier := sizedNu T.size T.products T.functions T.small T.all T.recursion D
structureMap := by
apply Sized.ofAt T.size T.functions T.small T.all T.functionProducts
have hd : D.obj (C.comp C.id C.fst)
(T.size.box T.small T.all
(sizedNu T.size T.products T.functions T.small T.all T.recursion D)) =
D.obj C.fst (T.size.box T.small T.all
(sizedNu T.size T.products T.functions T.small T.all T.recursion D)) := by
rw [C.id_comp]
exact C.castTm (congrArg (fun B => T.functions.arr _ (T.univ.el B)) hd).symm
(T.univ.pathArrow T.identities T.identityElimination T.functions (sizedNu_path T D))
/-- The source algebra on `μ D`, with `In = (∃ In◇) ∘ can⁻¹`. -/
def muAlgebra
(h : C.Tm Γ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex D.toInternalFunctorData)) : Algebra D where
carrier := mu T.size T.products T.functions T.small T.ex T.recursion D
structureMap := T.functions.compose
(T.ex.map T.functions _ _
(T.univ.pathArrow T.identities T.identityElimination T.functions
(InternalPath.symm T.identities T.identityElimination (sizedMu_path T D))))
(QuantifierAdjunction.existsInverse T D.toInternalFunctorData h
(sizedMu T.size T.products T.functions T.small T.ex T.recursion D))
/-- The source coalgebra on `ν D`, with `Out = can⁻¹ ∘ (∀ Out□)`. -/
def nuCoalgebra
(h : C.Tm Γ (WeakCommutation.allType T.size T.functions T.small T.identityElimination
T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
D.toInternalFunctorData)) : Coalgebra D where
carrier := nu T.size T.products T.functions T.small T.all T.recursion D
structureMap := T.functions.compose
(QuantifierAdjunction.allInverse T D.toInternalFunctorData h
(sizedNu T.size T.products T.functions T.small T.all T.recursion D))
(T.all.map T.functions T.allSubstitution _ _
(T.univ.pathArrow T.identities T.identityElimination T.functions (sizedNu_path T D)))
theorem muAlgebra_carrier
(h : C.Tm Γ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex D.toInternalFunctorData)) :
(muAlgebra T D h).carrier = mu T.size T.products T.functions T.small T.ex T.recursion D :=
rfl
theorem nuCoalgebra_carrier
(h : C.Tm Γ (WeakCommutation.allType T.size T.functions T.small T.identityElimination
T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
D.toInternalFunctorData)) :
(nuCoalgebra T D h).carrier =
nu T.size T.products T.functions T.small T.all T.recursion D := rfl
end EncodingFixpoints
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_PolynomialV2 -/
/-!
# Internal polynomial operations
The object operation is the source code `Σ a : A, (B(a) → X)`. The morphism
operation is constructed by dependent pairing and postcomposition.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
namespace Universe
variable (U : Universe C)
theorem sub_id {Γ : C.Ctx} (A : U.Code Γ) : U.sub A C.id = A := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans (C.tmSub_id A)
theorem sub_generic_heq {Γ Δ : C.Ctx} (σ : C.Sub Δ (C.ext Γ (U.type Γ))) :
HEq (U.sub (U.generic Γ) σ) (C.tmSub C.snd σ) :=
(C.castTm_heq _ _).trans
(C.tmSub_heq (U.type_sub C.fst).symm (C.castTm_heq _ _) σ)
/-- The base substitution and its last universe code determine a context map. -/
theorem hom_ext {Γ Δ : C.Ctx} {f g : C.Sub Δ (C.ext Γ (U.type Γ))}
(hfst : C.comp C.fst f = C.comp C.fst g)
(hsnd : U.sub (U.generic Γ) f = U.sub (U.generic Γ) g) : f = g :=
C.sub_ext hfst ((U.sub_generic_heq f).symm.trans
((heq_of_eq hsnd).trans (U.sub_generic_heq g)))
theorem extend_comp {Γ Δ Θ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Δ)
(τ : C.Sub Θ Δ) :
C.comp (U.extend σ A) τ = U.extend (C.comp σ τ) (U.sub A τ) := by
apply U.hom_ext
· rw [← C.assoc, U.extend_fst, U.extend_fst]
· rw [← U.sub_comp, U.generic_sub_extend, U.generic_sub_extend]
theorem extend_generic {Γ : C.Ctx} : U.extend C.fst (U.generic Γ) = C.id := by
apply U.hom_ext
· rw [U.extend_fst, C.comp_id]
· rw [U.generic_sub_extend, U.sub_id]
/-- Composition of lifts through a decoded type, with its code substitution
equality made explicit in the intermediate context. -/
theorem liftEl_comp_as {Γ Δ Θ : C.Ctx} (A : U.Code Γ)
(σ : C.Sub Δ Γ) (τ : C.Sub Θ Δ) :
C.comp (U.liftEl σ A)
(U.liftElAs τ (U.sub A σ) (U.sub A (C.comp σ τ)) (U.sub_comp A σ τ)) =
U.liftEl (C.comp σ τ) A := by
apply C.sub_ext
· rw [← C.assoc, U.liftEl_fst, C.assoc, U.liftElAs_fst,
← C.assoc, U.liftEl_fst]
· exact (C.tmSub_comp C.snd (U.liftEl σ A) _).symm.trans
((C.tmSub_heq (U.liftEl_snd_type σ A) (U.liftEl_snd σ A) _).trans
((U.liftElAs_snd τ (U.sub A σ) _ _).trans (U.liftEl_snd _ A).symm))
end Universe
namespace GenericArrow
variable (U : Universe C) (F : FunctionTypes C) (Γ : C.Ctx)
/-- Specializing a generic arrow commutes with another substitution. -/
theorem specialize_comp {Δ Θ : C.Ctx} (σ : C.Sub Δ Γ) (X Y : U.Code Δ)
(f : SmallHom U F X Y) (τ : C.Sub Θ Δ) :
C.comp (specialize U F Γ σ X Y f) τ =
specialize U F Γ (C.comp σ τ) (U.sub X τ) (U.sub Y τ) (SmallHom.sub U F f τ) := by
apply C.sub_ext
· rw [← C.assoc, specialize, C.pair_fst, specialize, C.pair_fst, codesSub,
U.extend_comp, U.extend_comp]
rfl
· have ht : C.tySub
(C.tySub (F.arr (U.el (domain U Γ)) (U.el (codomain U Γ))) C.fst)
(specialize U F Γ σ X Y f) = F.arr (U.el X) (U.el Y) := by
rw [C.tySub_comp, specialize, C.pair_fst]
exact arrowType_sub U F Γ σ X Y
have hh : HEq (C.tmSub C.snd (specialize U F Γ σ X Y f)) f :=
(C.pair_snd _ _).trans (C.castTm_heq _ _)
exact (C.tmSub_comp C.snd (specialize U F Γ σ X Y f) τ).symm.trans
((C.tmSub_heq ht hh τ).trans
((C.castTm_heq _ _).symm.trans
((C.castTm_heq _ _).symm.trans (C.pair_snd _ _).symm)))
/-- The generic arrow specializes to itself by the identity context map. -/
theorem specialize_generic :
specialize U F Γ (projection U F Γ) (source U F Γ) (target U F Γ) (term U F Γ) = C.id := by
have hbase : U.extend (base U Γ) (domain U Γ) = C.fst := by
apply U.hom_ext
· rw [U.extend_fst]
rfl
· rw [U.generic_sub_extend]
rfl
have hcodes : codesSub U Γ (base U Γ) (domain U Γ) (codomain U Γ) = C.id := by
dsimp [codesSub]
rw [hbase]
exact U.extend_generic
have hfst : codesSub U Γ (projection U F Γ) (source U F Γ) (target U F Γ) = C.fst := by
dsimp [codesSub, projection, source, target]
rw [← U.extend_comp, ← U.extend_comp]
change C.comp (codesSub U Γ (base U Γ) (domain U Γ) (codomain U Γ)) C.fst = C.fst
rw [hcodes, C.id_comp]
apply C.sub_ext
· rw [specialize, C.pair_fst, hfst, C.comp_id]
· exact (C.pair_snd _ _).trans ((C.castTm_heq _ _).trans
((C.castTm_heq _ _).trans (C.tmSub_id C.snd).symm))
end GenericArrow
namespace Polynomial
variable {U : Universe C} {P : DependentProducts C} {S : DependentSums C}
{I : IdentityTypes C} (K : SmallTypeConstructors C U P S I)
/-- The literal source polynomial `Σ a : A, (B(a) → X)`. -/
def code {Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(X : U.Code Γ) : U.Code Γ :=
K.sigma A (K.arrow B (U.sub X C.fst))
/-- Polynomial object action in any context over the parameter context. -/
def obj {Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (X : U.Code Δ) : U.Code Δ :=
code K (U.sub A σ) (U.sub B (U.liftEl σ A)) X
/-- The polynomial object code is stable under contextual substitution. -/
theorem obj_sub (KS : SmallTypeSubstitution U P S I K) {Γ Δ Θ : C.Ctx}
(A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (X : U.Code Δ) (τ : C.Sub Θ Δ) :
U.sub (obj K A B σ X) τ = obj K A B (C.comp σ τ) (U.sub X τ) := by
dsimp [obj, code]
rw [K.sigma_sub_as KS _ _ τ _ (U.sub_comp A σ τ), K.arrow_sub KS,
U.sub_comp B, U.liftEl_comp_as, U.sub_comp X, U.liftElAs_fst, ← U.sub_comp X]
/-- The source morphism action `(a, h) ↦ (a, f ∘ h)` at given parameters. -/
def action (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
{Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(X Y : U.Code Γ) (f : SmallHom U F X Y) :
SmallHom U F (code K A B X) (code K A B Y) := by
let BX := K.arrow B (U.sub X C.fst)
let BY := K.arrow B (U.sub Y C.fst)
let ph := @C.fst (C.ext Γ (U.el A)) (U.el BX)
let σ := C.comp C.fst ph
let a := C.castTm (C.tySub_comp (U.el A) C.fst ph) (C.tmSub C.snd ph)
have hpair : C.pair σ a = ph :=
(C.pair_unique σ a ph rfl (C.castTm_heq _ _).symm).symm
have htype (T : U.Code Γ) :
C.tySub (U.el (K.arrow B (U.sub T C.fst))) ph =
F.arr (C.tySub (U.el B) ph) (C.tySub (U.el T) σ) := by
exact (congrArg (fun V => C.tySub V ph) (K.el_arrow FP B (U.sub T C.fst))).trans
((F.arr_sub _ _ ph).trans
(congrArg (F.arr (C.tySub (U.el B) ph))
((congrArg (fun V => C.tySub V ph) (U.el_sub T C.fst).symm).trans
(C.tySub_comp _ _ _))))
let h := C.castTm (htype X) C.snd
let value := F.compose (F.sub f σ) h
let b := C.castTm (congrArg (C.tySub (U.el BY)) hpair.symm)
(C.castTm (htype Y).symm value)
let paired := K.sigmaPairAt A BY σ a b
let split := K.sigmaSplit A BX
have hbase : C.tySub (C.tySub (U.el (code K A B Y)) σ) split =
C.tySub (U.el (code K A B Y)) C.fst :=
(C.tySub_comp _ σ split).trans
(congrArg (C.tySub (U.el (code K A B Y))) (K.sigmaSplit_base A BX))
exact F.lam (C.castTm hbase (C.tmSub paired split))
/-- The one generic polynomial action term, with parameters, both codes, and
the input function as contextual variables. -/
def genericMap (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
{Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) :
SmallHom U F
(obj K A B (GenericArrow.projection U F Γ) (GenericArrow.source U F Γ))
(obj K A B (GenericArrow.projection U F Γ) (GenericArrow.target U F Γ)) :=
action K F FP (U.sub A (GenericArrow.projection U F Γ))
(U.sub B (U.liftEl (GenericArrow.projection U F Γ) A))
(GenericArrow.source U F Γ) (GenericArrow.target U F Γ) (GenericArrow.term U F Γ)
/-- The generic action has the required polynomial function type after
specializing its two codes and input arrow. -/
theorem genericMap_type_sub (F : FunctionTypes C)
(KS : SmallTypeSubstitution U P S I K)
{Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (X Y : U.Code Δ) (f : SmallHom U F X Y) :
C.tySub (F.arr
(U.el (obj K A B (GenericArrow.projection U F Γ) (GenericArrow.source U F Γ)))
(U.el (obj K A B (GenericArrow.projection U F Γ) (GenericArrow.target U F Γ))))
(GenericArrow.specialize U F Γ σ X Y f) =
F.arr (U.el (obj K A B σ X)) (U.el (obj K A B σ Y)) := by
rw [SmallHom.type_sub, obj_sub K KS, obj_sub K KS,
GenericArrow.projection_sub, GenericArrow.source_sub, GenericArrow.target_sub]
/-- The internal polynomial map is substitution of the one literal generic
term `(a, h) ↦ (a, f ∘ h)`. -/
def map (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
(KS : SmallTypeSubstitution U P S I K)
{Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (X Y : U.Code Δ) (f : SmallHom U F X Y) :
SmallHom U F (obj K A B σ X) (obj K A B σ Y) :=
C.castTm (genericMap_type_sub K F KS A B σ X Y f)
(C.tmSub (genericMap K F FP A B) (GenericArrow.specialize U F Γ σ X Y f))
/-- Substitution naturality follows from generic specialization, rather than
being supplied as an extra law about the polynomial action. -/
theorem map_sub (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
(KS : SmallTypeSubstitution U P S I K)
{Γ Δ Θ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (X Y : U.Code Δ) (f : SmallHom U F X Y) (τ : C.Sub Θ Δ) :
HEq (SmallHom.sub U F (map K F FP KS A B σ X Y f) τ)
(map K F FP KS A B (C.comp σ τ) (U.sub X τ) (U.sub Y τ) (SmallHom.sub U F f τ)) := by
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (genericMap_type_sub K F KS A B σ X Y f).symm
(C.castTm_heq _ _) τ).trans
((C.tmSub_comp (genericMap K F FP A B) (GenericArrow.specialize U F Γ σ X Y f) τ).trans
((congr_arg_heq (fun ρ => C.tmSub (genericMap K F FP A B) ρ)
(GenericArrow.specialize_comp U F Γ σ X Y f τ)).trans
(C.castTm_heq _ _).symm)))
/-- The polynomial's genuine internal object and morphism data. The two
functor laws are not assumed by this construction. -/
def data (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
(KS : SmallTypeSubstitution U P S I K)
{Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) :
InternalFunctorData U F Γ where
obj := obj K A B
obj_sub := obj_sub K KS A B
map := map K F FP KS A B
map_sub := map_sub K F FP KS A B
/-- The generic map of the assembled data is exactly the literal polynomial
action, up to the explicitly recorded code transports. -/
theorem data_genericMap (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
(KS : SmallTypeSubstitution U P S I K)
{Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) :
HEq (data K F FP KS A B).genericMap (genericMap K F FP A B) := by
change HEq (map K F FP KS A B _ _ _ _) _
apply (C.castTm_heq _ _).trans
rw [GenericArrow.specialize_generic]
exact C.tmSub_id _
end Polynomial
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingLawsV2 -/
/-! Exact functor-law conclusions for the modal operations of Propositions 4 and 5.
They are predicates to prove about the constructed operations, not assumed fields. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
universe u v w t
variable {C : CwF.{u,v,w,t}} (T : CoreTheory C) {Γ : C.Ctx}
/-- Equality of size-indexed morphisms is an internal identity term. -/
def HasPath {A B : T.univ.Code (C.ext Γ (T.size.type Γ))}
(f g : Hom T.size T.small T.all A B) : Prop :=
Nonempty (C.Tm Γ (T.identities.id (T.univ.el (homCode T.size T.small T.all A B)) f g))
/-- The source's two functor laws for a specified size-indexed action. -/
def PreservesIdComp
(obj : T.univ.Code (C.ext Γ (T.size.type Γ)) →
T.univ.Code (C.ext Γ (T.size.type Γ)))
(map : ∀ {A B}, Hom T.size T.small T.all A B → Hom T.size T.small T.all (obj A) (obj B)) :
Prop :=
(∀ A, HasPath T (map (identity T.size T.functions T.small T.all T.functionProducts A))
(identity T.size T.functions T.small T.all T.functionProducts (obj A))) ∧
(∀ A B D (g : Hom T.size T.small T.all B D) (f : Hom T.size T.small T.all A B),
HasPath T (map (compose T.size T.functions T.small T.all T.functionProducts g f))
(compose T.size T.functions T.small T.all T.functionProducts (map g) (map f)))
/-- The constructed bounded-existential action satisfies the source functor laws. -/
def DiamondFunctorLaws (Γ : C.Ctx) : Prop :=
PreservesIdComp T (T.size.diamond T.small T.ex (Γ := Γ))
(diamondMap T.size T.functions T.small T.all T.functionProducts T.ex)
/-- The constructed bounded-universal action satisfies the source functor laws. -/
def BoxFunctorLaws (Γ : C.Ctx) : Prop :=
PreservesIdComp T (T.size.box T.small T.all (Γ := Γ))
(boxMap T.size T.functions T.small T.all T.functionProducts T.allSubstitution)
/-- The literal composite action `F[◇ -]` on morphisms. -/
def liftDiamondMap (F : WildEndofunctor T.univ T.functions T.identities Γ)
{A B : T.univ.Code (C.ext Γ (T.size.type Γ))}
(f : Hom T.size T.small T.all A B) :
Hom T.size T.small T.all
(liftObject T.size T.functions F (T.size.diamond T.small T.ex A))
(liftObject T.size T.functions F (T.size.diamond T.small T.ex B)) :=
liftMap T.size T.functions T.small T.all T.functionProducts F
(diamondMap T.size T.functions T.small T.all T.functionProducts T.ex f)
/-- The literal composite action `F[□ -]` on morphisms. -/
def liftBoxMap (F : WildEndofunctor T.univ T.functions T.identities Γ)
{A B : T.univ.Code (C.ext Γ (T.size.type Γ))}
(f : Hom T.size T.small T.all A B) :
Hom T.size T.small T.all
(liftObject T.size T.functions F (T.size.box T.small T.all A))
(liftObject T.size T.functions F (T.size.box T.small T.all B)) :=
liftMap T.size T.functions T.small T.all T.functionProducts F
(boxMap T.size T.functions T.small T.all T.functionProducts T.allSubstitution f)
/-- Functor laws for the prescribed composite `F[◇ -]`. -/
def LiftDiamondFunctorLaws (F : WildEndofunctor T.univ T.functions T.identities Γ) : Prop :=
PreservesIdComp T (fun A ↦ liftObject T.size T.functions F (T.size.diamond T.small T.ex A))
(liftDiamondMap T F)
/-- Functor laws for the prescribed composite `F[□ -]`. -/
def LiftBoxFunctorLaws (F : WildEndofunctor T.univ T.functions T.identities Γ) : Prop :=
PreservesIdComp T (fun A ↦ liftObject T.size T.functions F (T.size.box T.small T.all A))
(liftBoxMap T F)
end LaarakkerOttenVanDenBerg2026.V2.Theory.Sized
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingConclusionsV2 -/
/-! The source encoding conclusions. These predicates are targets to prove;
none is a field of the theory, a functor, or a size recursor. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace CoreTheory
variable {C : CwF.{u,v,w,t}} (T : CoreTheory C) {Γ : C.Ctx}
(D : WildEndofunctor T.univ T.functions T.identities Γ)
/-- The source existential weak-commutation hypothesis is one internal term
quantifying over every size family and inverting the prescribed canonical map. -/
abbrev WeaklyCommutesExists :=
C.Tm Γ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex D.toInternalFunctorData)
/-- The dual internally quantified weak-commutation hypothesis. -/
abbrev WeaklyCommutesAll :=
C.Tm Γ (WeakCommutation.allType T.size T.functions T.small
T.identityElimination T.all T.sizeSubstitution T.smallSubstitution
T.allSubstitution D.toInternalFunctorData)
/-- Theorem 11's specified algebra is initial, and its specified structure map
is an internal half-adjoint equivalence. -/
def InductiveEncoding (h : T.WeaklyCommutesExists D) : Prop :=
let A := EncodingFixpoints.muAlgebra T D h
Nonempty (A.IsInitial T.products T.sums) ∧
Nonempty (C.Tm Γ (InternalEquivalence.isEquiv T.functions T.products T.identities
T.sums T.identityElimination A.structureMap))
/-- The dual conclusion for the specified coinductive coalgebra. -/
def CoinductiveEncoding (h : T.WeaklyCommutesAll D) : Prop :=
let A := EncodingFixpoints.nuCoalgebra T D h
Nonempty (A.IsTerminal T.products T.sums) ∧
Nonempty (C.Tm Γ (InternalEquivalence.isEquiv T.functions T.products T.identities
T.sums T.identityElimination A.structureMap))
/-- The polynomial corollary constructs the functor-law witnesses for the
literal polynomial object and morphism data, then proves weak commutation and
the canonical inductive encoding. No polynomial functor laws are assumed. -/
def PolynomialInductiveEncodings : Prop :=
∀ (Γ : C.Ctx) (A : T.univ.Code Γ) (B : T.univ.Code (C.ext Γ (T.univ.el A))),
∃ D : WildEndofunctor T.univ T.functions T.identities Γ,
D.toInternalFunctorData = Polynomial.data T.small T.functions
T.functionProducts T.smallSubstitution A B ∧
∃ h : T.WeaklyCommutesExists D, T.InductiveEncoding D h
/-- The corresponding polynomial coinductive corollary, for every small
branching family, including empty and infinitely branching signatures. -/
def PolynomialCoinductiveEncodings : Prop :=
∀ (Γ : C.Ctx) (A : T.univ.Code Γ) (B : T.univ.Code (C.ext Γ (T.univ.el A))),
∃ D : WildEndofunctor T.univ T.functions T.identities Γ,
D.toInternalFunctorData = Polynomial.data T.small T.functions
T.functionProducts T.smallSubstitution A B ∧
∃ h : T.WeaklyCommutesAll D, T.CoinductiveEncoding D h
end CoreTheory
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingFunctorialityV2 -/
/-!
# Prescribed morphism lifting and underlying-arrow functor laws
The lift types retain the full internal sigma type of algebra morphisms,
including its commuting-square path. They prescribe the underlying arrow by
an internal pointwise identity. Identity and composition laws below concern
the prescribed underlying arrows. They do not identify arbitrary choices of
commuting-square witnesses, or assert higher coherence absent from the paper's
wild-functor interface.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
namespace ArrowLifting
variable (T : CoreTheory C)
/-- The first-projection function of an internal dependent sum. -/
def firstProjection {Γ : C.Ctx} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) :
C.Tm Γ (T.functions.arr (T.sums.sigma A B) A) :=
T.functions.lam (T.sums.fst (C.castTm (T.sums.sigma_sub A B C.fst) C.snd))
/-- A full morphism map with its prescribed underlying action. The pointwise
identity is itself an internal dependent product, rather than external equality. -/
def liftType {Γ : C.Ctx} (H₁ H₂ A₁ A₂ : C.Ty Γ)
(forget₁ : C.Tm Γ (T.functions.arr H₁ A₁))
(forget₂ : C.Tm Γ (T.functions.arr H₂ A₂))
(action : C.Tm Γ (T.functions.arr A₁ A₂)) : C.Ty Γ :=
let L := T.functions.arr H₁ H₂
let p := @C.fst Γ L
let l := C.castTm (T.functions.arr_sub H₁ H₂ p) C.snd
let q := @C.fst (C.ext Γ L) (C.tySub H₁ p)
T.sums.sigma L (T.products.pi (C.tySub H₁ p)
(T.identities.id (C.tySub (C.tySub A₂ p) q)
(T.functions.app (T.functions.sub (T.functions.sub forget₂ p) q)
(T.functions.app (T.functions.sub l q) C.snd))
(T.functions.app (T.functions.sub (T.functions.sub action p) q)
(T.functions.app (T.functions.sub (T.functions.sub forget₁ p) q) C.snd))))
/-- The internal identity law for a fixed underlying-arrow action. -/
def identityType {Γ : C.Ctx} {A B : C.Ty Γ}
(action : C.Tm Γ (T.functions.arr A B)) (sourceId : C.Tm Γ A) (targetId : C.Tm Γ B) :
C.Ty Γ := T.identities.id B (T.functions.app action sourceId) targetId
/-- Substitute a curried binary operation, normalizing both arrow constructors. -/
def subBinary {Γ Δ : C.Ctx} {A B D : C.Ty Γ}
(f : C.Tm Γ (T.functions.arr A (T.functions.arr B D))) (σ : C.Sub Δ Γ) :
C.Tm Δ (T.functions.arr (C.tySub A σ) (T.functions.arr (C.tySub B σ) (C.tySub D σ))) :=
C.castTm (congrArg (T.functions.arr (C.tySub A σ)) (T.functions.arr_sub B D σ))
(T.functions.sub f σ)
/-- The internal composition law for a fixed action, on two generic arrows.
Both composition operations are supplied by named source constructions below. -/
def compositionType {Γ : C.Ctx} (A₁ B₁ D₁ A₂ B₂ D₂ : C.Ty Γ)
(actionAB : C.Tm Γ (T.functions.arr A₁ A₂))
(actionBD : C.Tm Γ (T.functions.arr B₁ B₂))
(actionAD : C.Tm Γ (T.functions.arr D₁ D₂))
(compose₁ : C.Tm Γ (T.functions.arr B₁ (T.functions.arr A₁ D₁)))
(compose₂ : C.Tm Γ (T.functions.arr B₂ (T.functions.arr A₂ D₂))) : C.Ty Γ :=
let p := @C.fst Γ B₁
let q := @C.fst (C.ext Γ B₁) (C.tySub A₁ p)
let g := C.tmSub (@C.snd Γ B₁) q
let f := @C.snd (C.ext Γ B₁) (C.tySub A₁ p)
let comp₁ := subBinary T (subBinary T compose₁ p) q
let comp₂ := subBinary T (subBinary T compose₂ p) q
T.products.pi B₁ (T.products.pi (C.tySub A₁ p)
(T.identities.id (C.tySub (C.tySub D₂ p) q)
(T.functions.app (T.functions.sub (T.functions.sub actionAD p) q)
(T.functions.app (T.functions.app comp₁ g) f))
(T.functions.app (T.functions.app comp₂
(T.functions.app (T.functions.sub (T.functions.sub actionBD p) q) g))
(T.functions.app (T.functions.sub (T.functions.sub actionAB p) q) f))))
/-- Actual curried composition of ordinary internal functions. -/
def functionComposition {Γ : C.Ctx} (A B D : C.Ty Γ) :
C.Tm Γ (T.functions.arr (T.functions.arr B D)
(T.functions.arr (T.functions.arr A B) (T.functions.arr A D))) := by
let p := @C.fst Γ (T.functions.arr B D)
let q := @C.fst (C.ext Γ (T.functions.arr B D)) (C.tySub (T.functions.arr A B) p)
let g := T.functions.sub (C.castTm (T.functions.arr_sub B D p) C.snd) q
have hf : C.tySub (C.tySub (T.functions.arr A B) p) q =
T.functions.arr (C.tySub (C.tySub A p) q) (C.tySub (C.tySub B p) q) :=
(congrArg (fun X => C.tySub X q) (T.functions.arr_sub A B p)).trans (T.functions.arr_sub _ _ q)
have ho : C.tySub (C.tySub (T.functions.arr A D) p) q =
T.functions.arr (C.tySub (C.tySub A p) q) (C.tySub (C.tySub D p) q) :=
(congrArg (fun X => C.tySub X q) (T.functions.arr_sub A D p)).trans (T.functions.arr_sub _ _ q)
let body := T.functions.compose g (C.castTm hf C.snd)
exact T.functions.lam (C.castTm
(T.functions.arr_sub (T.functions.arr A B) (T.functions.arr A D) p).symm
(T.functions.lam (C.castTm ho.symm body)))
/-- Actual curried composition of size-indexed arrows. -/
def sizedComposition {Γ : C.Ctx}
(A B D : T.univ.Code (C.ext Γ (T.size.type Γ))) :
C.Tm Γ (T.functions.arr (T.univ.el (Sized.homCode T.size T.small T.all B D))
(T.functions.arr (T.univ.el (Sized.homCode T.size T.small T.all A B))
(T.univ.el (Sized.homCode T.size T.small T.all A D)))) := by
let AB := T.univ.el (Sized.homCode T.size T.small T.all A B)
let BD := T.univ.el (Sized.homCode T.size T.small T.all B D)
let AD := T.univ.el (Sized.homCode T.size T.small T.all A D)
let p := @C.fst Γ BD
let q := @C.fst (C.ext Γ BD) (C.tySub AB p)
let σ := C.comp p q
let g := C.castTm (Sized.homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution B D σ)
(C.castTm (C.tySub_comp BD p q) (C.tmSub C.snd q))
let f := C.castTm (Sized.homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution A B σ)
(C.castTm (C.tySub_comp AB p q) C.snd)
let result := Sized.compose T.size T.functions T.small T.all T.functionProducts g f
let body := C.castTm (C.tySub_comp AD p q).symm
(C.castTm (Sized.homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution A D σ).symm result)
exact T.functions.lam (C.castTm (T.functions.arr_sub AB AD p).symm (T.functions.lam body))
end ArrowLifting
namespace QuantifierAdjunction
variable (T : CoreTheory C)
/-- The prescribed existential action as one internal higher-order term. -/
def existsArrowAction {Γ : C.Ctx} (A B : T.univ.Code (C.ext Γ (T.size.type Γ))) :
C.Tm Γ (T.functions.arr (T.univ.el (Sized.homCode T.size T.small T.all A B))
(T.functions.arr (T.univ.el (T.ex.code A)) (T.univ.el (T.ex.code B)))) := by
let σ := @C.fst Γ (T.univ.el (Sized.homCode T.size T.small T.all A B))
let f := C.castTm (Sized.homType_sub T.size T.small T.all
T.smallSubstitution T.allSubstitution A B σ) C.snd
let result := T.ex.map T.functions (T.univ.sub A (T.size.lift σ)) (T.univ.sub B (T.size.lift σ))
(Sized.eval T.size T.functions T.small T.all T.functionProducts f)
have hout : C.tySub (T.functions.arr (T.univ.el (T.ex.code A)) (T.univ.el (T.ex.code B))) σ =
T.functions.arr (T.univ.el (T.ex.code (T.univ.sub A (T.size.lift σ))))
(T.univ.el (T.ex.code (T.univ.sub B (T.size.lift σ)))) := by
rw [SmallHom.type_sub, T.exSubstitution.code_sub, T.exSubstitution.code_sub]
exact T.functions.lam (C.castTm hout.symm result)
/-- The prescribed universal action as one internal higher-order term. -/
def allArrowAction {Γ : C.Ctx} (A B : T.univ.Code (C.ext Γ (T.size.type Γ))) :
C.Tm Γ (T.functions.arr (T.univ.el (Sized.homCode T.size T.small T.all A B))
(T.functions.arr (T.univ.el (T.all.code A)) (T.univ.el (T.all.code B)))) := by
let σ := @C.fst Γ (T.univ.el (Sized.homCode T.size T.small T.all A B))
let f := C.castTm (Sized.homType_sub T.size T.small T.all
T.smallSubstitution T.allSubstitution A B σ) C.snd
let result := T.all.map T.functions T.allSubstitution
(T.univ.sub A (T.size.lift σ)) (T.univ.sub B (T.size.lift σ))
(Sized.eval T.size T.functions T.small T.all T.functionProducts f)
have hout : C.tySub (T.functions.arr (T.univ.el (T.all.code A)) (T.univ.el (T.all.code B))) σ =
T.functions.arr (T.univ.el (T.all.code (T.univ.sub A (T.size.lift σ))))
(T.univ.el (T.all.code (T.univ.sub B (T.size.lift σ)))) := by
rw [SmallHom.type_sub, T.allSubstitution.code_sub, T.allSubstitution.code_sub]
exact T.functions.lam (C.castTm hout.symm result)
/-- Reindexing a constant size family is again the constant reindexed family. -/
theorem constantFamily_sub {Γ Δ : C.Ctx} (A : T.univ.Code Γ) (σ : C.Sub Δ Γ) :
T.univ.sub (T.univ.sub A (@C.fst Γ (T.size.type Γ))) (T.size.lift σ) =
T.univ.sub (T.univ.sub A σ) (@C.fst Δ (T.size.type Δ)) := by
rw [T.univ.sub_comp, T.univ.sub_comp, T.size.lift_fst]
/-- The prescribed constant-family action `f ↦ λ i, f`. -/
def constantArrowAction {Γ : C.Ctx} (A B : T.univ.Code Γ) :
C.Tm Γ (T.functions.arr (T.functions.arr (T.univ.el A) (T.univ.el B))
(T.univ.el (Sized.homCode T.size T.small T.all
(T.univ.sub A C.fst) (T.univ.sub B C.fst)))) := by
let σ := @C.fst Γ (T.functions.arr (T.univ.el A) (T.univ.el B))
let f := C.castTm (SmallHom.type_sub T.univ T.functions A B σ) C.snd
let result := Sized.ofAt T.size T.functions T.small T.all T.functionProducts
(SmallHom.sub T.univ T.functions f C.fst)
have hout : C.tySub (T.univ.el (Sized.homCode T.size T.small T.all
(T.univ.sub A C.fst) (T.univ.sub B C.fst))) σ =
T.univ.el (Sized.homCode T.size T.small T.all
(T.univ.sub (T.univ.sub A σ) C.fst) (T.univ.sub (T.univ.sub B σ) C.fst)) := by
rw [Sized.homType_sub T.size T.small T.all T.smallSubstitution T.allSubstitution,
constantFamily_sub, constantFamily_sub]
exact T.functions.lam (C.castTm hout.symm result)
/-- The existential action preserves the underlying identity arrow. -/
def existsIdentityType {Γ : C.Ctx} (A : T.univ.Code (C.ext Γ (T.size.type Γ))) : C.Ty Γ :=
ArrowLifting.identityType T (existsArrowAction T A A)
(Sized.identity T.size T.functions T.small T.all T.functionProducts A)
(T.functions.identity (T.univ.el (T.ex.code A)))
/-- The universal action preserves the underlying identity arrow. -/
def allIdentityType {Γ : C.Ctx} (A : T.univ.Code (C.ext Γ (T.size.type Γ))) : C.Ty Γ :=
ArrowLifting.identityType T (allArrowAction T A A)
(Sized.identity T.size T.functions T.small T.all T.functionProducts A)
(T.functions.identity (T.univ.el (T.all.code A)))
/-- The constant-family action preserves the underlying identity arrow. -/
def constantIdentityType {Γ : C.Ctx} (A : T.univ.Code Γ) : C.Ty Γ :=
ArrowLifting.identityType T (constantArrowAction T A A)
(T.functions.identity (T.univ.el A))
(Sized.identity T.size T.functions T.small T.all T.functionProducts (T.univ.sub A C.fst))
/-- The existential action preserves pointwise composition of underlying arrows. -/
def existsCompositionType {Γ : C.Ctx}
(A B D : T.univ.Code (C.ext Γ (T.size.type Γ))) : C.Ty Γ :=
ArrowLifting.compositionType T _ _ _ _ _ _
(existsArrowAction T A B) (existsArrowAction T B D) (existsArrowAction T A D)
(ArrowLifting.sizedComposition T A B D)
(ArrowLifting.functionComposition T (T.univ.el (T.ex.code A))
(T.univ.el (T.ex.code B)) (T.univ.el (T.ex.code D)))
/-- The universal action preserves pointwise composition of underlying arrows. -/
def allCompositionType {Γ : C.Ctx}
(A B D : T.univ.Code (C.ext Γ (T.size.type Γ))) : C.Ty Γ :=
ArrowLifting.compositionType T _ _ _ _ _ _
(allArrowAction T A B) (allArrowAction T B D) (allArrowAction T A D)
(ArrowLifting.sizedComposition T A B D)
(ArrowLifting.functionComposition T (T.univ.el (T.all.code A))
(T.univ.el (T.all.code B)) (T.univ.el (T.all.code D)))
/-- The constant-family action preserves composition of underlying arrows. -/
def constantCompositionType {Γ : C.Ctx} (A B D : T.univ.Code Γ) : C.Ty Γ :=
ArrowLifting.compositionType T _ _ _ _ _ _
(constantArrowAction T A B) (constantArrowAction T B D) (constantArrowAction T A D)
(ArrowLifting.functionComposition T (T.univ.el A) (T.univ.el B) (T.univ.el D))
(ArrowLifting.sizedComposition T (T.univ.sub A C.fst)
(T.univ.sub B C.fst) (T.univ.sub D C.fst))
variable {Γ : C.Ctx} (F : WildEndofunctor T.univ T.functions T.identities Γ)
/-- The existential action lifts to full algebra morphisms. Both source and
target retain their commuting-square witnesses. -/
def existsMorphismLiftType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex (F.toInternalFunctorData.reindex σ)))
(A B : Sized.AlgebraOver T F σ) : C.Ty Δ :=
ArrowLifting.liftType T (Sized.AlgebraOver.homType A B)
(AlgebraOver.homType T.sums (existsAlgebra T F h A) (existsAlgebra T F h B))
_ _ (ArrowLifting.firstProjection T _ _) (ArrowLifting.firstProjection T _ _)
(existsArrowAction T A.carrier B.carrier)
/-- The universal action lifts to full coalgebra morphisms, including the
commuting-square witnesses. -/
def allMorphismLiftType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(h : C.Tm Δ (WeakCommutation.allType T.size T.functions T.small T.identityElimination
T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
(F.toInternalFunctorData.reindex σ)))
(A B : Sized.CoalgebraOver T F σ) : C.Ty Δ :=
ArrowLifting.liftType T (Sized.CoalgebraOver.homType A B)
(CoalgebraOver.homType T.sums (allCoalgebra T F h A) (allCoalgebra T F h B))
_ _ (ArrowLifting.firstProjection T _ _) (ArrowLifting.firstProjection T _ _)
(allArrowAction T A.carrier B.carrier)
/-- Constant-family formation lifts full algebra morphisms with prescribed
underlying action `f ↦ λ i, f`. -/
def constantAlgebraMorphismLiftType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(A B : AlgebraOver F σ) : C.Ty Δ :=
ArrowLifting.liftType T (AlgebraOver.homType T.sums A B)
(Sized.AlgebraOver.homType (constantAlgebra T F A) (constantAlgebra T F B))
_ _ (ArrowLifting.firstProjection T _ _) (ArrowLifting.firstProjection T _ _)
(constantArrowAction T A.carrier B.carrier)
/-- Constant-family formation lifts full coalgebra morphisms with prescribed
underlying action `f ↦ λ i, f`. -/
def constantCoalgebraMorphismLiftType {Δ : C.Ctx} {σ : C.Sub Δ Γ}
(A B : CoalgebraOver F σ) : C.Ty Δ :=
ArrowLifting.liftType T (CoalgebraOver.homType T.sums A B)
(Sized.CoalgebraOver.homType (constantCoalgebra T F A) (constantCoalgebra T F B))
_ _ (ArrowLifting.firstProjection T _ _) (ArrowLifting.firstProjection T _ _)
(constantArrowAction T A.carrier B.carrier)
end QuantifierAdjunction
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingInfrastructureV2 -/
/-! The source's modal laws, sized universal properties and prescribed
morphism-lifting conclusions. Full morphisms retain their square witnesses;
identity/composition laws here concern their prescribed underlying arrows. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.CoreTheory
universe u v w t
variable {C : CwF.{u,v,w,t}} (T : CoreTheory C)
open QuantifierAdjunction
/-- Identity and composition equations for the actual constant-family action. -/
def ConstantArrowLaws : Prop :=
(∀ (Γ : C.Ctx) (A : T.univ.Code Γ), Nonempty (C.Tm Γ (constantIdentityType T A))) ∧
(∀ (Γ : C.Ctx) (A B D : T.univ.Code Γ),
Nonempty (C.Tm Γ (constantCompositionType T A B D)))
/-- Identity and composition equations for the actual existential action. -/
def ExistsArrowLaws : Prop :=
(∀ (Γ : C.Ctx) (A : T.univ.Code (C.ext Γ (T.size.type Γ))),
Nonempty (C.Tm Γ (existsIdentityType T A))) ∧
(∀ (Γ : C.Ctx) (A B D : T.univ.Code (C.ext Γ (T.size.type Γ))),
Nonempty (C.Tm Γ (existsCompositionType T A B D)))
/-- Identity and composition equations for the actual universal action. -/
def AllArrowLaws : Prop :=
(∀ (Γ : C.Ctx) (A : T.univ.Code (C.ext Γ (T.size.type Γ))),
Nonempty (C.Tm Γ (allIdentityType T A))) ∧
(∀ (Γ : C.Ctx) (A B D : T.univ.Code (C.ext Γ (T.size.type Γ))),
Nonempty (C.Tm Γ (allCompositionType T A B D)))
/-- Proposition 4, Lemmas 7–8 and the concrete lifting assertion of Proposition 10.
No natural adjunction or higher coherence of chosen square proofs is silently
identified with these specified morphism-lifting and underlying-arrow laws. -/
def InductiveInfrastructure : Prop :=
(∀ Γ : C.Ctx, Sized.DiamondFunctorLaws T Γ) ∧
(∀ (Γ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ),
Sized.LiftDiamondFunctorLaws T D ∧
Nonempty (EncodingFixpoints.sizedMuAlgebra T D).IsInitial) ∧
T.ConstantArrowLaws ∧
(∀ (Γ Δ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ)
(σ : C.Sub Δ Γ) (A B : AlgebraOver D σ),
Nonempty (C.Tm Δ (constantAlgebraMorphismLiftType T D A B))) ∧
T.ExistsArrowLaws ∧
(∀ (Γ Δ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ)
(σ : C.Sub Δ Γ)
(h : C.Tm Δ (WeakCommutation.existsType T.size T.functions T.small
T.identityElimination T.ex (D.toInternalFunctorData.reindex σ)))
(A B : Sized.AlgebraOver T D σ),
Nonempty (C.Tm Δ (existsMorphismLiftType T D h A B)))
/-- The corresponding bounded-universal laws, sized terminality and concrete
constant/universal morphism lifts in Proposition 5, Lemmas 19–20 and Proposition 22. -/
def CoinductiveInfrastructure : Prop :=
(∀ Γ : C.Ctx, Sized.BoxFunctorLaws T Γ) ∧
(∀ (Γ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ),
Sized.LiftBoxFunctorLaws T D ∧
Nonempty (EncodingFixpoints.sizedNuCoalgebra T D).IsTerminal) ∧
T.ConstantArrowLaws ∧
(∀ (Γ Δ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ)
(σ : C.Sub Δ Γ) (A B : CoalgebraOver D σ),
Nonempty (C.Tm Δ (constantCoalgebraMorphismLiftType T D A B))) ∧
T.AllArrowLaws ∧
(∀ (Γ Δ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ)
(σ : C.Sub Δ Γ)
(h : C.Tm Δ (WeakCommutation.allType T.size T.functions T.small
T.identityElimination T.all T.sizeSubstitution T.smallSubstitution T.allSubstitution
(D.toInternalFunctorData.reindex σ)))
(A B : Sized.CoalgebraOver T D σ),
Nonempty (C.Tm Δ (allMorphismLiftType T D h A B)))
end LaarakkerOttenVanDenBerg2026.V2.Theory.CoreTheory
Read-back
What the Lean code literally says, in plain math · Codex / GPT-6 (independent fresh-context read-back)
Blind literal read-back of Def_LaarakkerOttenVanDenBerg2026_EncodingRevision2.lean.
Encoding input SHA256: 70c7fa2dc1b3b372845fbe763197c9a53b6b8e4cc8b5a76ffd10e4b5ead4da0a.
Imported theory input SHA256: d3fa3c4567a0c8574ca523a6420469ba5d6ff7d5cbcffb943b6735d5a5013ce1.
Scope: one paragraph for each of the 246 explicit public mathematical declarations in the encoding file, in source order. The imported theory supplies the meanings of the interfaces. I read the auditor protocol, these two Lean files, and the user-required general contributor manual; I did not consult mathematical sources, mission descriptions, previous reviews/read-backs, or implementation agents. Comments claiming source intent are not evidence for this read-back. This is a source-level reading, not a compilation or model-existence verification.
Notation and common parameters: every declaration is parametrized by an arbitrary category-with-families record , with contexts, substitutions, context extension , types, and contextual terms in arbitrary universes . Its record includes categorical identity/composition laws, substitution laws, a terminal empty context, and the comprehension pairing/projection/universal-property laws. Write and for reindexing, for a context projection, and for its newest variable. A universe consists of a substitution-stable type of codes and a substitution-stable decoding ; a code is a contextual term, not an external set. or used as a function interface supplies contextual arrows, lambda abstraction, application, beta/eta, and substitution laws. When is the dependent-product interface it supplies internal products , abstraction/unabstraction, beta/eta, and substitution laws; supplies internal dependent sums with their projections and beta/eta laws. is internal identity formation/reflexivity/substitution, and is based identity elimination with its reflexivity computation rule. An internal path is a type of the object theory; it is not external equality of terms. External equalities in theorem paragraphs are Lean equalities; heterogeneous equality means equality allowing the displayed term types to differ. All transport casts below use external equalities of types and do not introduce internal identity reflection.
Size and small-type notation: supplies a substitution-stable size type, zero, successor, a small code , terms for zero being below each size, successor increase, reflexivity, transitivity, and an internal path between any two proofs of the same inequality. Write only as an abbreviation for the decoded code . No irreflexivity, antisymmetry, well-foundedness, or separation of zero/successor is assumed by this notation. supplies universe codes for dependent products, dependent sums, and identities with their decoding equations. denotes the small existential size code: its interface has pairing and dependent elimination to small motives with a beta equation. denotes the small universal size code: its interface has contextual abstraction/unabstraction with beta/eta equations. Thus and ; these are codes built with the selected operations, not external set quantifiers. is the context substitution lifting under an unchanged size variable. Compatibility of function and dependent-product interfaces means both arrow types and their abstraction operations agree. Named substitution interfaces impose the corresponding code/term substitution equations.
A core theory includes all the preceding interfaces, function/product compatibility, empty/unit/boolean codes with contextual elimination/computation rules, their substitution laws, identity elimination and its substitution law, size substitution laws, a size recursor with an internal beta witness and substitution laws, both small size quantifiers and their stated substitution laws, and function extensionality asserting that the identity-elimination map from equality of dependent functions to pointwise equality is an internal half-adjoint equivalence, with substitution stability. It does not include the separate four-parametricity-axiom record or a consistency assertion. Here an internal half-adjoint equivalence structure on is precisely , where is built by ; the type of equivalences also includes as its first component. Internal contractibility of is . Neither notion here is external unique existence.
SmallHom. For a universe , function interface , context , and codes in , this is the external type of contextual terms of the internal arrow .
SmallHom.type_sub. For , contexts , codes in , and substitution , reindexing gives exactly .
SmallHom.sub. For , contexts , codes in , an internal arrow , and , this returns the reindexed arrow, transported to .
InternalFunctorData. For , this record supplies, for every , an operation on codes in and an operation sending each internal to . For every further , it requires and heterogeneous equality between and . The record contains no identity-preservation or composition-preservation witness.
InternalFunctorData.genericObject. Given and substitution-natural object/arrow data over , this is the code in , where is the generic code and forgets it.
InternalFunctorData.object_from_generic. Given such , every context , substitution , and code in , substituting into the generic code yields exactly.
InternalFunctorData.objectTerm. Given , this constructs the contextual term by abstracting the generic code over .
InternalFunctorData.map_congr. Given , a context , equal substitutions , codes and in , and heterogeneously equal arrows and , the arrows and are heterogeneously equal.
GenericArrow.codes. For and , this is the twice-extended context .
GenericArrow.domain. For , this is the first generic code , weakened into .
GenericArrow.codomain. For , this is the second generic code in .
GenericArrow.base. For , this is the composite projection forgetting both codes.
GenericArrow.context. For , function interface , and , this is .
GenericArrow.source. For , this is the generic code in the context .
GenericArrow.target. For , this is the generic code in the context .
GenericArrow.projection. For , this is the projection forgetting all three added variables.
GenericArrow.term. For , this is the last variable in , transported to the arrow between the weakened code decodings.
GenericArrow.codesSub. For , , and codes in , this is the substitution into .
GenericArrow.domain_sub. For universe , contexts , , and codes in , substituting into the first generic code yields .
GenericArrow.codomain_sub. For universe , contexts , , and codes in , substituting into the second generic code yields .
GenericArrow.base_sub. For universe , contexts , , and codes in , composing with the projection forgetting the codes yields .
GenericArrow.arrowType_sub. For , , and codes in , the generic arrow type reindexed along equals .
GenericArrow.specialize. For , , codes in , and an internal arrow , this returns the substitution into the generic-arrow context.
GenericArrow.source_sub. For universe , function interface , contexts , , codes in , and arrow , the generic source code specialized along equals .
GenericArrow.target_sub. For universe , function interface , contexts , , codes in , and arrow , the generic target code specialized along equals .
GenericArrow.projection_sub. For universe , function interface , contexts , , codes in , and arrow , projecting the specialization back to equals .
GenericArrow.term_sub. For universe , function interface , contexts , , codes in , and arrow , the reindexed generic arrow along is heterogeneously equal to .
InternalFunctorData.genericMap. For , this is in the context , with forgetting these three variables.
InternalFunctorData.map_from_generic. For , any , substitution , codes in , and arrow , reindexing the one generic mapped arrow along is heterogeneously equal to .
GenericComposition.codes. For , this is the context .
GenericComposition.firstCode. For , this is the first generic code in .
GenericComposition.middleCode. For , this is the middle generic code in .
GenericComposition.lastCode. For , this is the last generic code in .
GenericComposition.firstContext. For , this is .
GenericComposition.firstDomain. For , this is weakened into .
GenericComposition.firstCodomain. For , this is weakened into .
GenericComposition.lastCodomain. For , this is weakened into .
GenericComposition.firstTerm. For , this is the generic arrow in the context containing the three codes and .
GenericComposition.context. For , this is .
GenericComposition.source. For , this is the code in the context containing the three codes and the two composable arrows.
GenericComposition.middle. For , this is the code in the context containing the three codes and the two composable arrows.
GenericComposition.target. For , this is the code in the context containing the three codes and the two composable arrows.
GenericComposition.first. For , this is weakened under the second generic arrow .
GenericComposition.second. For , this is the last generic arrow in the context containing .
GenericComposition.projection. For , this is the substitution forgetting from their joint generic context back to .
WildEndofunctor. For , function interface , identity interface , and , this extends the substitution-natural object/arrow data by two internal terms: in , a path in the arrow type ; and in , a path in . These are chosen terms in the generic contexts, without additional higher coherence fields.
Algebra. For and a wild endofunctor over , this record consists of a code in and an internal arrow .
Coalgebra. For and a wild endofunctor over , this record consists of a code in and an internal arrow .
AlgebraHom. For and algebras , this record consists of an internal arrow and an internal path in the type .
CoalgebraHom. For and coalgebras , this record consists of an internal arrow and an internal path in the type .
ExistentialSizeQuantifier.map. For , a function interface , a context , codes over , and a contextual arrow , this constructs by existential elimination with branch .
UniversalSizeQuantifier.map. For , a function interface , substitution stability of , a context , codes , and a contextual arrow , this constructs by , using contextual abstraction and the supplied substitution transports.
Sized.homCode. For , dependent products , dependent sums , small constructors , a universal size quantifier , context , and code families , this is the code , with weakened under .
Sized.Hom. For , context , and code families over , this is the external type of contextual terms in of the decoded small code ; its elements are not arbitrary metatheoretic size-indexed collections of arrows.
Sized.eval. Given and a function interface compatible with , context , code families , and a term , this unapplies the universal quantifier and transports the small arrow decoding to obtain an internal arrow in the generic-size context.
Sized.ofAt. Given with function/product compatibility, context , code families , and an internal arrow in the generic-size context, this transports it to the decoded small arrow and universally abstracts it, yielding a term of .
Sized.eval_ofAt. For , function/product compatibility, , and every contextual arrow , evaluating its universal abstraction returns exactly .
Sized.ofAt_eval. For with function/product compatibility, context , and code families , and every term , universally abstracting its generic evaluation returns exactly .
Sized.identity. For with function/product compatibility, context , and family , this constructs the sized arrow .
Sized.compose. For with function/product compatibility, context , families , and sized arrows and , this constructs the sized arrow by evaluation and universal abstraction.
Sized.homType_sub. For , small-constructor substitution stability and universal-quantifier substitution stability, contexts , families over , and , the decoded sized-arrow type reindexed by equals the decoded type .
Sized.sub. For with small-constructor and universal-quantifier substitution stability, contexts , families , a sized arrow , and , this returns its contextual reindexing transported to the sized-arrow type between and .
Sized.liftObject. For , function interface , context , a wild endofunctor over , and family , this returns the code family , where .
Sized.liftMap. For with function/product compatibility, context , wild endofunctor , families , and sized arrow , this constructs the sized arrow between the pointwise images.
Sized.diamondMap. For with function/product compatibility and an existential size quantifier , context , families , and sized arrow , this constructs with generic branch . Here is preserved, and .
Sized.boxMap. For , compatibility and universal-quantifier substitution stability, context , families , and sized arrow , this constructs by , where .
Sized.Algebra. For , context , and wild endofunctor , this record consists of a code family and a term of .
Sized.Coalgebra. For , context , and wild endofunctor , this record consists of a code family and a term of .
Sized.AlgebraHom. For with function/product compatibility, a context , a wild endofunctor , and sized algebras , this record consists of a sized arrow and an internal path between the complete sized arrows and , from to . The path is in the decoded universal arrow type, not merely a family of external equalities.
Sized.CoalgebraHom. For with function/product compatibility and universal-quantifier substitution stability, context , wild endofunctor , and sized coalgebras , this record consists of a sized arrow and an internal path in the decoded sized-arrow type from to .
InternalFunctorData.reindex. For , function interface , contexts , substitution-natural object/arrow data over , and , this constructs such data over by assigning to each the original object and arrow operations at ; substitution coherence is inherited using associativity.
DependentProducts.unlam_sub_as. For dependent products , contexts , a type in , a type over , a term , , a type in , and equality , unabstracting the transported reindexing of equals the body of reindexed along the lift of under .
DependentProducts.unlam_congr. For dependent products , context , type , equal types over , and heterogeneously equal terms and , their unabstracted bodies are heterogeneously equal.
SizeRules.unlam_sub. For , dependent products , contexts , a type family over , a term , and , unabstracting the transported reindexing equals the body of reindexed along .
SizedFamily.type. For , dependent products , and context , this forms the internal, possibly large, type of contextual small-code families.
SizedFamily.type_sub. For , contexts , and , the type in reindexed to equals that same internally formed family type in .
SizedFamily.context. For , this is the context extension by one generic contextual code family.
SizedFamily.generic. For , this is the code obtained by unabstracting the generic family variable, in the context .
SizedFamily.extend. For , contexts , substitution , and code in , this constructs the context map into .
SizedFamily.extend_fst. For , , and code family over , projecting onto the original context equals .
SizedFamily.generic_sub_extend. For , , and code family over , reindexing the generic code along the size lift of returns exactly .
Sized.liftObjectOver. For a core theory , context , wild endofunctor over , context , , and code family over , this constructs in .
Sized.liftMapOver. For core theory , wild over context , context , and , code families over , and a sized arrow , this constructs the sized arrow between their pointwise images.
Sized.liftObjectOver_sub. For core theory , wild over , contexts , , , and code family over , as codes.
Sized.liftDiamond_sub. For core theory , wild over , , , and code family over , , where .
Sized.liftBox_sub. For core theory , wild over , , , and code family over , , where .
Sized.AlgebraOver. For core theory , wild over , context , and , this record consists of a code family over and a sized arrow , with .
Sized.CoalgebraOver. For core theory , wild over , context , and , this record consists of a code family and a sized arrow , with .
Sized.AlgebraOver.sub. For core theory , wild over , contexts , , a sized algebra over , and , this constructs a sized algebra over with carrier and reindexed structure arrow , transported using substitution of .
Sized.AlgebraOver.homType. For core theory , wild over , , and sized algebras over , this forms in the internal type . Its second component is identity in the full sized-arrow type , with all data weakened under the bound .
Sized.CoalgebraOver.sub. For core theory , wild over , contexts , , a sized coalgebra over , and , this constructs a sized coalgebra over with carrier and transported reindexed structure arrow .
Sized.CoalgebraOver.homType. For core theory , wild over , , and sized coalgebras over , this forms in . The identity type compares full sized arrows from to and retains the square witness as a dependent-sum component.
Sized.algebraStructureType. For core theory and wild over , in this forms the decoded code , where the two projections forget the size and family variables and .
Sized.genericAlgebra. For core theory and wild over , this constructs the sized algebra over the projection from to , with carrier the weakened generic and structure the last generic variable , transported to its substituted type.
Sized.coalgebraStructureType. For core theory and wild over , in this forms the decoded code , with and the composite projection to .
Sized.genericCoalgebra. For core theory and wild over , this constructs the sized coalgebra over the projection from to , using the generic carrier and the last variable as structure.
Sized.AlgebraOver.initialityType. For core theory , wild over , and sized algebra over , this forms the internal type , where . The carrier and structure binders are internal dependent products, and contractibility concerns the pair of an arrow and its square proof. This constructs the type, not a term of it.
Sized.AlgebraOver.IsInitial. For core theory , wild over , and sized algebra over , this is the external type of contextual terms of the internal product over all and of , where is the internal dependent sum of a sized arrow and its algebra-square path.
Sized.CoalgebraOver.terminalityType. For core theory , wild over , and sized coalgebra over , this forms the internal type , where . This is a type-valued definition, with the full incoming coalgebra morphism and its path retained.
Sized.CoalgebraOver.IsTerminal. For core theory , wild over , and sized coalgebra over , this is the external type of contextual terms of the internal product over code families and structures of contractibility of the full incoming morphism type .
AlgebraOver. For , function interface , identity interface , wild endofunctor over , context , and , this record consists of a code in and an internal arrow .
CoalgebraOver. For , wild over , context , and , this record consists of a code in and an internal arrow .
AlgebraOver.sub. For , wild over , contexts , , an algebra over , and , this constructs the algebra over with carrier and structure , transported using .
AlgebraOver.homType. For , dependent sums , wild over , , and algebras over , this forms the internal type in . The arrow and square are internal, and the square type is formed after weakening both algebras under the generic arrow.
CoalgebraOver.sub. For , wild over , , a coalgebra over , and , this constructs the coalgebra over with carrier and the appropriately transported structure .
CoalgebraOver.homType. For , dependent sums , wild over , , and coalgebras over , this forms as an internal type in , retaining the internal square witness.
WildEndofunctor.algebraStructureType. For , context , and wild , this forms in the internal arrow type .
WildEndofunctor.genericAlgebra. For , context , and wild , this constructs the algebra over whose carrier is the generic code and whose structure is the generic arrow after the required weakening transports.
WildEndofunctor.coalgebraStructureType. For , context , and wild , this forms in the internal arrow type .
WildEndofunctor.genericCoalgebra. For , context , and wild , this constructs the coalgebra over the projection from whose carrier is and whose structure is the generic arrow .
Algebra.over. For , wild over , and an algebra in , this gives the algebra over with exactly the same carrier and structure.
Algebra.initialityType. For , dependent products , dependent sums , wild over , and algebra , this forms , with and all parameter data reindexed into the binder contexts. No inhabitant is constructed here.
Algebra.IsInitial. For , wild over , and algebra , this is the external type of terms in of , where is the internal dependent sum of an arrow and its algebra-square identity witness.
Coalgebra.over. For , wild over , and coalgebra , this gives the coalgebra over with the same carrier and structure.
Coalgebra.terminalityType. For , dependent products , dependent sums , wild over , and coalgebra , this forms , where . It constructs the internal type of terminality, not an inhabitant.
Coalgebra.IsTerminal. For , wild over , and coalgebra , this is the external type of contextual terms giving internal contractibility of the incoming full coalgebra-morphism type , internally for every code and structure .
UniversalSizeQuantifier.arrowAtSize. For , substitution stability of , function interface , context , code in , family , and internal arrow , this constructs the generic-size arrow by applying to a generic element and unabstracting its universal output, exchanging the independent size and element binders.
UniversalSizeQuantifier.arrowFromSize. For , substitution stability of , function interface , context , code in , family , and contextual arrow in , this constructs by , using the inverse binder interchange.
WeakCommutation.existsCan. For , function interface , products , sums , small constructors , existential size quantifier , context , substitution-natural data over , and family , this constructs . Its existential branch is , where discards the bound proof while retaining . No functor-law or weak-commutation witness is an argument.
WeakCommutation.allRestriction. For and size, small-constructor, and universal-quantifier substitution stability, context , and family , this constructs at generic the arrow sending to .
WeakCommutation.allCan. For and size, small-constructor, and universal-quantifier substitution stability, context , substitution-natural data , and family , this constructs by , where and .
WeakCommutation.existsType. For , context , and substitution-natural data , this forms internally, where is the explicit branch map with . Each equivalence component comprises an inverse, two pointwise inverse paths, and the path . The definition does not supply a term of this product.
WeakCommutation.allType. For , size/small/universal substitution stability, context , and substitution-natural data , this forms internally for , . Its equivalence type contains an inverse, both inverse homotopies, and their half-adjoint coherence, without asserting inhabitation.
QuantifierAdjunction.forgetSize. For core theory , context , and code in , this constructs the internal arrow by existential elimination with branch ; may depend on but not on the added size.
QuantifierAdjunction.extract. For core theory , context , and code , this constructs at generic the arrow by forgetting the bound proof and then the existential size, with branch .
QuantifierAdjunction.repeatAll. For core theory , context , and code , this constructs the arrow sending an element to the constant universal family.
QuantifierAdjunction.insert. For core theory , context , and code , this constructs at generic the arrow sending to , by constant universal introduction followed by restriction.
QuantifierAdjunction.existsInverse. For core theory , context , substitution-natural data , a contextual term for the canonical maps , and a particular family , this extracts the inverse component of at , giving . The chosen inverse depends on ; this definition does not separately return the homotopies.
QuantifierAdjunction.allInverse. For core theory , context , substitution-natural data , a contextual term for , and a particular family , this extracts from the inverse arrow .
QuantifierAdjunction.constantAlgebra. For core theory , wild over , , and algebra over , this constructs the constant sized algebra with carrier and structure , where sends to .
QuantifierAdjunction.constantCoalgebra. For core theory , wild over , , and coalgebra over , this constructs the constant sized coalgebra with carrier and structure , where is constant introduction.
QuantifierAdjunction.existsAlgebra. For core theory , wild over , , a contextual weak-existential-commutation term for the reindexed data , and sized algebra over , this constructs an algebra over with carrier and structure , where is selected from .
QuantifierAdjunction.allCoalgebra. For core theory , wild over , , a contextual weak-universal-commutation term for , and sized coalgebra over , this constructs a coalgebra over with carrier and structure , using the inverse selected from .
QuantifierAdjunction.existsHomEquivalenceType. For core theory , wild over , , a weak-existential-commutation term for , sized algebra , and ordinary algebra over , this forms the internal half-adjoint-equivalence type between full algebra morphisms from the quantified algebra to and full sized algebra morphisms from to the constant algebra . Both morphism types are dependent sums of underlying arrows and square paths. It chooses neither an equivalence term nor any naturality witnesses.
QuantifierAdjunction.allHomEquivalenceType. For core theory , wild over , , a weak-universal-commutation term for , ordinary coalgebra , and sized coalgebra , this forms the internal half-adjoint-equivalence type from full sized coalgebra morphisms to full ordinary coalgebra morphisms . Each morphism retains its square path; the declaration is type formation, without an equivalence inhabitant or naturality requirement.
EncodingFixpoints.sizeContext. For and context , this is .
EncodingFixpoints.recursiveType. For , dependent products , function interface , and context , this is the internal type over , with the code universe reindexed to the context.
EncodingFixpoints.recursiveContext. For , this is .
EncodingFixpoints.bodyContext. For , this is the context with arbitrary further size ; it does not yet include a proof that .
EncodingFixpoints.recursiveProjection. For , this is the projection forgetting the variable .
EncodingFixpoints.bodyProjection. For , this is the projection forgetting .
EncodingFixpoints.recursiveBody. For , function interface , and context , this is the type in , with the universe pulled back along the substitution retaining and forgetting .
EncodingFixpoints.genericRecursive. For , this is the generic variable in , transported to the type whose body is pulled back from along the lifted projection forgetting .
EncodingFixpoints.innerSize_type. For , pulling the size type of back first to and then to equals the selected size type in the latter context.
EncodingFixpoints.innerSizeSub. For , this constructs from the substitution into the extension of by the pulled-back size type, pairing the projection forgetting with the generic , transported along size-type stability.
EncodingFixpoints.boundsSub. For , this is the substitution obtained by lifting the projection forgetting under a size binder; it retains and .
EncodingFixpoints.guardCode. For , this is the code of in , obtained by reindexing the two-size bound code along the map forgetting .
EncodingFixpoints.recursiveArrow_type. For , the type from , pulled back along the map forgetting , equals the arrow from the decoded guard code to the universe type in .
EncodingFixpoints.recursiveArrow. For , this unabstracts the generic recursive variable at the generic and transports its type, yielding the internal arrow in .
EncodingFixpoints.recursiveValue. For , in the further context , this applies the weakened internal arrow to the generic bound proof , yielding the universe code . The code may depend on ; no equality eliminating that dependence is asserted here.
EncodingFixpoints.existentialPack. For , dependent sums , small constructors , existential size quantifier , and , this constructs the code in . It uses the recursive value only in a context containing its bound proof.
EncodingFixpoints.universalPack. For , universal size quantifier , and , this constructs the code in .
EncodingFixpoints.muStep. For , context , and wild endofunctor over , this constructs the internal step of type . The functor's parameter substitution forgets and ; its object operation is applied to the code built in their context.
EncodingFixpoints.nuStep. For , context , and wild , this constructs the internal step of type .
EncodingFixpoints.sizedMu. For , a size-recursion interface , context , and wild , this is the code family obtained by unabstracting at universe-valued family and step . The interface supplies a fixed term and an internal beta path for every contextual family and step of the indicated bounded-recursion shape; this definition does not claim initiality or uniqueness.
EncodingFixpoints.sizedNu. For , context , and wild , this is the code family obtained by unabstracting the recursor at universe family and step . It defines a family without claiming terminality or uniqueness.
EncodingFixpoints.sizedMu_fix_beta. For , this returns the recursor's term of in the universe identity type, where is the displayed existential step and is its selected fixed family. The right-hand side is syntactically step application to restriction; it is not an external equality of codes.
EncodingFixpoints.sizedNu_fix_beta. For , this returns the recursor's internal term of , with and its selected fixed family.
EncodingFixpoints.mu. For , context , and wild , this is the code , where is the universe-valued recursive family selected by the existential step. Its definition supplies a code only.
EncodingFixpoints.nu. For , context , and wild , this is the code , where is the universe-valued recursive family selected by the universal step.
FunctionTypes.sub_congr. For function interface , contexts , types in , equalities and , heterogeneously equal arrows and , and , the reindexed arrows are heterogeneously equal.
FunctionTypes.genericApp_lam. For a function interface , dependent products , compatibility of their function types and abstractions, context , types , and a contextual body in of weakened type , applying the weakening of to the generic returns exactly .
FunctionTypes.genericApp_sub. For function interface , contexts , types in , arrow , and , the generic application reindexed along the lift of under is heterogeneously equal to the generic application of in .
FunctionTypes.genericApp_sub_as. For function interface , , types , arrow , , types with and , and arrow heterogeneously equal to , generic application of pulled back along the corresponding lift under is heterogeneously equal to generic application of .
Universe.liftElAs_eq_liftAs. For universe , contexts , , codes in and in , and equality , the universe-specific context lift under decoded equals the ordinary context lift under , using the decoding-substitution equality.
SizeRules.lift_section. For , contexts , substitutions and , and equality , their size lifts satisfy . No equation for is assumed or concluded.
EncodingFixpoints.restrictionSub. For , context , and term , this is the context section assigning ; the supplied recursive argument ignores the bound proof .
EncodingFixpoints.boundsSub_restriction. For and , the size lift of the section followed by forgetting is the identity substitution on .
EncodingFixpoints.guardCode_restriction. For and , substituting into the guard code in returns exactly the two-size code .
EncodingFixpoints.recursiveBody_restriction. For and , pulling the body type to and then substituting returns exactly the original body type in .
EncodingFixpoints.recursiveArrow_restriction. For and , the generic arrow , reindexed along the lifted section assigning the restricted family of , is heterogeneously equal to the unabstracted restriction .
EncodingFixpoints.recursiveValue_restriction. For with function/product compatibility, context , and , substituting into the code , with the context lift preserving the guard proof, gives exactly weakened under .
EncodingFixpoints.existentialPack_restriction. For , function/product compatibility, small-constructor substitution stability, existential-code substitution stability, context , and , substituting into gives exactly as a code.
EncodingFixpoints.universalPack_restriction. For , function/product compatibility, small-constructor substitution stability, universal-quantifier substitution stability, context , and , substituting into gives exactly as a code.
EncodingFixpoints.muStep_restriction. For , function/product compatibility, small-constructor and existential-code substitution stability, context , wild , and , the existential step at generic applied to equals externally as a universe code.
EncodingFixpoints.nuStep_restriction. For , function/product compatibility, small-constructor and universal-quantifier substitution stability, context , wild , and , the universal step at generic applied to equals the code externally.
Universe.generic_decode_sub. For universe , context , and code in , decoding the generic code in and then substituting gives exactly the type .
Universe.transport. For , context , codes , an internal path in , and a contextual term , this produces a term of by identity elimination in the family decoding the generic code. It does not produce an external equality .
Universe.pathSub. For , contexts , codes in , an internal universe path , and , this returns the transported reindexing of as a path in the universe of .
Universe.pathArrow. For , a function interface , context , codes , and internal universe path , this constructs an internal arrow by abstracting identity-elimination transport along the weakened path.
EncodingFixpoints.sizedMu_path. For core theory , context , and wild , this constructs in the internal universe path , where is the selected existential recursive family. It obtains the term from recursor beta and the external step-normalization equality.
EncodingFixpoints.sizedNu_path. For core theory , context , and wild , this constructs the internal universe path for the selected universal recursive family .
EncodingFixpoints.sizedMuAlgebra. For core theory , context , and wild , this constructs a sized algebra over with carrier and structure obtained by reversing the internal universe path , decoding it by identity-elimination transport, and universally abstracting the resulting arrows. It constructs no initiality witness.
EncodingFixpoints.sizedNuCoalgebra. For core theory , context , and wild , this constructs a sized coalgebra over with carrier and structure by decoding the forward internal universe path and universally abstracting. It constructs no terminality witness.
EncodingFixpoints.muAlgebra. For core theory , context , wild , and a term internally asserting half-adjoint equivalence of every canonical existential map , this constructs the ordinary algebra with carrier and structure . Here is transport along the reversed recursive universe path and the inverse is the one extracted from .
EncodingFixpoints.nuCoalgebra. For core theory , context , wild , and a term internally asserting half-adjoint equivalence of every canonical universal map , this constructs the ordinary coalgebra with carrier and structure , using forward recursive-path transport and the inverse selected by .
EncodingFixpoints.muAlgebra_carrier. For core theory , context , wild , and every contextual weak-existential-commutation witness , the carrier of the just-defined ordinary algebra is exactly the code selected by existential recursive encoding; the equality does not depend on any initiality claim.
EncodingFixpoints.nuCoalgebra_carrier. For core theory , context , wild , and every contextual weak-universal-commutation witness , the carrier of the defined ordinary coalgebra is exactly the code selected by universal recursive encoding.
Universe.sub_id. For universe , context , and code in , reindexing along returns exactly.
Universe.sub_generic_heq. For universe , contexts , and substitution , reindexing the generic universe code along is heterogeneously equal to reindexing the newest comprehension variable along .
Universe.hom_ext. For universe , contexts , and substitutions , equality of their projections into and equality of the generic universe codes pulled back by imply the external substitution equality .
Universe.extend_comp. For universe , contexts , , code in , and , composing the extended substitution with equals .
Universe.extend_generic. For universe and context , extending the projection by its own generic universe code gives the identity substitution on .
Universe.liftEl_comp_as. For universe , contexts , a code in , , and , the lift of under decoded , composed with the lift of under decoded using the equality , equals the lift of under decoded .
GenericArrow.specialize_comp. For , function interface , contexts , , codes in , internal arrow , and , as substitutions into the generic-arrow context over .
GenericArrow.specialize_generic. For , function interface , and context , specializing the generic-arrow context using its own projection, source, target, and arrow yields its identity substitution.
Polynomial.code. For , dependent products , sums , identities , small constructors , context , code in , code family over , and code in , this constructs the code using small sums and small nondependent arrow codes. There is no finiteness or nonemptiness restriction on either code.
Polynomial.obj. For , contexts , code in , code family , , and code in , this constructs , where is the lift under decoded .
Polynomial.obj_sub. For with small-constructor substitution stability, contexts , parameter codes , , code in , and , the polynomial code at reindexed by equals the polynomial code at .
Polynomial.action. For , function interface compatible with , context , codes in , code family , and internal arrow , this constructs the internal arrow by splitting a dependent pair and returning .
Polynomial.genericMap. For with function/product compatibility, context , parameter code and family , this constructs in the generic-arrow context the polynomial arrow , with reindexed along its projection.
Polynomial.genericMap_type_sub. For , function interface , small-constructor substitution stability, contexts , parameter code and family over , , codes in , and arrow , the type of the generic polynomial arrow reindexed along equals the arrow between the polynomial codes at and .
Polynomial.map. For , function/product compatibility and small-constructor substitution stability, contexts , parameters , , codes in , and arrow , this constructs the polynomial arrow by substituting into the single generic pair/postcomposition term and transporting its type. This definition uses that generic specialization rather than a fresh application of Polynomial.action at .
Polynomial.map_sub. For with function/product compatibility and small-constructor substitution stability, contexts , parameters , , codes and arrow in , and , reindexing the constructed polynomial map is heterogeneously equal to the constructed map at .
Polynomial.data. For , function/product compatibility, small-constructor substitution stability, context , code , and family , this constructs substitution-natural internal object/arrow data with object and the generic-specialization pair/postcomposition arrow operation. The resulting record contains object/map substitution proofs but no wild-functor identity or composition witnesses.
Polynomial.data_genericMap. For , compatibility, small-constructor substitution stability, context , and parameters , the generic morphism operation of the assembled polynomial data is heterogeneously equal to the literal generic arrow .
Sized.HasPath. For core theory , context , code families , and sized arrows , this proposition means that there exists a contextual term of the internal identity type in the decoded sized-arrow type. It provides neither an external equality of nor a chosen term merely by being defined.
Sized.PreservesIdComp. For core theory , fixed context , an external operation on contextual code families and an external arrow operation taking each sized to a sized , this proposition is the conjunction of: for every , nonemptiness of the contextual internal path type ; and, for every , sized , and sized , nonemptiness of . The quantifiers over the chosen operations, families, and arrows are external; this proposition itself imposes no substitution naturality or coherent choice of path terms.
Sized.DiamondFunctorLaws. For core theory and context , this defines the identity/composition-law proposition for and its arrow operation . It asks externally for nonempty internal identity witnesses for every sized identity and every pair of composable sized arrows; it proves none here.
Sized.BoxFunctorLaws. For core theory and context , this defines identity/composition preservation, through external nonemptiness of internal path types, for and arrow operation .
Sized.liftDiamondMap. For core theory , context , wild , code families , and sized arrow , this constructs the sized arrow from to by first applying the explicit bounded-existential arrow operation and then the pointwise arrow operation of .
Sized.liftBoxMap. For core theory , context , wild , families , and sized arrow , this constructs by the bounded-universal arrow operation followed by pointwise application of .
Sized.LiftDiamondFunctorLaws. For core theory , context , and wild , this is the proposition that the specified object/arrow operations and preserve every sized identity and composition up to nonempty contextual internal path types. It is not a theorem asserting those paths exist.
Sized.LiftBoxFunctorLaws. For core theory , context , and wild , this is the analogous proposition for the specified operations and , with external quantification over sized arrows and nonemptiness of internal identity witnesses.
CoreTheory.WeaklyCommutesExists. For core theory , context , and wild , this is the external type of one contextual term of , where sends to and . The internal equivalence structure includes the inverse, both homotopies, and half-adjoint coherence.
CoreTheory.WeaklyCommutesAll. For core theory , context , and wild , this is the external type of one contextual term of , where is and , including the full half-adjoint-equivalence data.
CoreTheory.InductiveEncoding. For core theory , context , wild , and a specified contextual weak-existential-commutation witness , this proposition is the conjunction of nonemptiness of the internal initiality-term type of the specific algebra and nonemptiness of the internal half-adjoint-equivalence-term type of that same structure arrow. Initiality internally quantifies over every code and structure and makes internally contractible, including its square witness. The declaration defines this conjunction without proving it; no assertion is made for a lacking such an .
CoreTheory.CoinductiveEncoding. For core theory , context , wild , and specified contextual weak-universal-commutation witness , this proposition conjoins nonemptiness of the internal terminality-term type of the specific coalgebra with nonemptiness of the internal half-adjoint-equivalence-term type of its structure arrow. Terminality internally quantifies over every and makes the complete incoming morphism type internally contractible. It is a proposition definition, with a required argument.
CoreTheory.PolynomialInductiveEncodings. For core theory , this proposition quantifies externally over every context , code , and code family over decoded . It requires existence of a wild endofunctor whose entire underlying substitution-natural data record is externally equal to the constructed polynomial data , and then existence of a contextual weak-existential-commutation term such that the specific recursive algebra is internally initial and its structure arrow has an internal half-adjoint-equivalence witness. The wild-functor law terms and are existential conclusions, not assumptions; the definition proves neither existence statement. No finite, inhabited, monotone, or bounded-branching restriction is imposed on .
CoreTheory.PolynomialCoinductiveEncodings. For core theory , this proposition quantifies externally over every , code , and family and requires a wild whose underlying data equal the constructed polynomial data, followed by a contextual weak-universal-commutation witness for which the specific recursive coalgebra is internally terminal and its structure arrow has an internal half-adjoint-equivalence witness. The record equality fixes the whole object/arrow data, while the functor-law and weak-commutation terms are existentially sought. Empty or arbitrarily branching code interpretations are not excluded, and no inhabitant of this proposition is supplied.
ArrowLifting.firstProjection. For core theory , context , type and dependent type over , this constructs the internal arrow by lambda abstraction of the first projection of a generic dependent pair.
ArrowLifting.liftType. For core theory , context , four arbitrary internal types , arrows and , and arrow , this forms . It is the type of an internal lift together with a pointwise internal agreement path, not an externally equal commuting square, and no lift term is constructed here.
ArrowLifting.identityType. For core theory , context , types , internal arrow , and selected contextual terms and , this returns the identity type . The terms called identities are arbitrary supplied terms in this general definition.
ArrowLifting.subBinary. For core theory , contexts , types in , a contextual curried arrow , and , this returns its reindexing transported to .
ArrowLifting.compositionType. For core theory , context , types , arrows , , , and supplied curried operations and , this forms the internal type . There are no laws assumed for the supplied and no term of this type is returned.
ArrowLifting.functionComposition. For core theory , context , and arbitrary internal types , this constructs the contextual curried function sending to by nested contextual abstraction.
ArrowLifting.sizedComposition. For core theory , context , and code families over the size context, this constructs the contextual curried function from and to , sending generic arguments to their internal pointwise composition, with reindexing under both binders.
QuantifierAdjunction.existsArrowAction. For core theory , context , and code families , this constructs one internal function by abstracting the generic sized arrow and using existential elimination/pairing with branch .
QuantifierAdjunction.allArrowAction. For core theory , context , and code families , this constructs one internal function , sending a generic sized arrow to the universal map .
QuantifierAdjunction.constantFamily_sub. For core theory , contexts , code in , and , the constant family obtained by weakening to and then reindexing along equals the family obtained by first forming and then weakening to .
QuantifierAdjunction.constantArrowAction. For core theory , context , and codes in , this constructs the internal function by sending the generic arrow to its weakening under a size and universal abstraction, .
QuantifierAdjunction.existsIdentityType. For core theory , context , and family , this forms the internal identity type , using the already constructed higher-order existential arrow action. This is a type, not a proof of the law.
QuantifierAdjunction.allIdentityType. For core theory , context , and family , this forms the internal identity type , without constructing a term.
QuantifierAdjunction.constantIdentityType. For core theory , context , and code , this forms the internal identity type between the image of under the constant-arrow action and the sized identity of the constant family .
QuantifierAdjunction.existsCompositionType. For core theory , context , and code families , this forms the internal product over sized and of the identity in the arrow type , using the constructed higher-order actions and the constructed sized and ordinary composition functions. It supplies no path term.
QuantifierAdjunction.allCompositionType. For core theory , context , and code families , this forms the internal product over sized and of , using the specified universal action and specified composition terms, without proving the law.
QuantifierAdjunction.constantCompositionType. For core theory , context , and codes , this forms , where is the constant-family arrow action and the target composition is the constructed sized composition. The declaration is type formation.
QuantifierAdjunction.existsMorphismLiftType. For core theory , wild over , context , , a contextual weak-existential-commutation witness for the reindexed data, and sized algebras over , this forms the type . Here is the internal dependent sum of a sized arrow and its algebra-square path, is the corresponding ordinary full morphism type between the specified quantified algebras and , and . This asks for a map on full morphisms whose underlying arrow agrees internally pointwise with the prescribed existential action; it does not provide such a map or prescribe the chosen output square proof.
QuantifierAdjunction.allMorphismLiftType. For core theory , wild over , , contextual weak-universal-commutation witness , and sized coalgebras over , this forms , where is the full sized coalgebra-morphism type and is the full ordinary coalgebra-morphism type between and . It is a type of lifts preserving the prescribed underlying universal arrow action up to internal pointwise identity, with the square witnesses retained but not otherwise identified.
QuantifierAdjunction.constantAlgebraMorphismLiftType. For core theory , wild over , , and ordinary algebras over , this forms , where consists of an ordinary algebra arrow and its square path, is the full sized-morphism type between the constant algebras with structures and , and . It does not construct a lift term.
QuantifierAdjunction.constantCoalgebraMorphismLiftType. For core theory , wild over , , and ordinary coalgebras over , this forms the internal type of a map from their full ordinary coalgebra-morphism type to the full sized-morphism type between the constant coalgebras with structures , together with . The domain and codomain include square paths, but only the underlying arrow is constrained by this pointwise identity.
CoreTheory.ConstantArrowLaws. For core theory , this proposition conjoins: for every context and code , nonemptiness of the contextual term type of ; and for every and codes , nonemptiness of the contextual term type . Here is the constant size family and . Outer quantifiers and nonemptiness are external; the composition-law arrow binders and identities are internal. This defines a proposition without proving it.
CoreTheory.ExistsArrowLaws. For core theory , this proposition conjoins external universal quantification over and family of nonempty contextual terms witnessing , and external universal quantification over and families of nonempty contextual terms of . The input arrows here are sized, the output arrows ordinary, and the action and compositions are the constructed terms.
CoreTheory.AllArrowLaws. For core theory , this proposition similarly requires, for every context and family, nonempty internal identity witnesses , and, for every context and three families, nonempty terms of the internally quantified composition identity . It asserts these requirements only as a defined predicate, with no proof term supplied by the declaration.
CoreTheory.InductiveInfrastructure. For core theory , this defines a conjunction of six requirements: (1) for every context , the explicit bounded-existential object/arrow operation preserves identities and compositions in the external-nonemptiness-of-internal-path sense; (2) for every and wild endofunctor there, the composite operation has those laws and the specified recursive sized algebra with carrier has a nonempty internal initiality-term type; (3) the defined constant-arrow identity/composition laws hold in every context; (4) for every pair of contexts , wild over , substitution , and ordinary algebras over , there is a contextual term giving a map on their full morphism types to those of the specified constant algebras, with pointwise internal agreement of underlying arrows with ; (5) the defined existential-arrow identity/composition laws hold; and (6) for every such , every contextual weak-existential-commutation term for , and every pair of sized algebras over , there is a contextual term lifting the prescribed existential underlying-arrow action to their full morphism types between the specified quantified algebras. Initiality uses internal contractibility of complete morphisms, including square proofs. The whole declaration is a proposition definition; the chosen lifts are not required here to preserve full-morphism identities/compositions, to be natural, or to furnish the previously defined hom-type equivalences. Requirement (6) imposes no obligation at a parameter choice with no .
CoreTheory.CoinductiveInfrastructure. For core theory , this defines the sixfold dual conjunction: (1) bounded-universal identity/composition laws in every context; (2) for every context and wild , laws for and nonemptiness of the internal terminality-term type of the specified sized coalgebra with carrier ; (3) all constant-arrow laws; (4) for all contexts , wild over , , and ordinary coalgebras over , nonemptiness of the type of maps on their full morphisms into those of the specified constant coalgebras agreeing pointwise internally with constant underlying-arrow formation; (5) all universal-arrow laws; and (6) for every such parameter choice, contextual weak-universal-commutation witness for , and sized coalgebras , nonemptiness of the type of maps on their full morphisms into the specified universally quantified coalgebras agreeing pointwise internally with the prescribed universal underlying-arrow action. Terminality includes internal contractibility of incoming arrows together with their square paths. This proposition does not require natural hom-equivalences or laws/coherence for the selected full-morphism lifts; its final universally quantified requirement is vacuous when no witness exists.
Edge and vacuity allowances visible in the literal declarations: no theorem here asserts that a core theory, wild functor, or weak-commutation term exists for a specified interpretation. The core-theory arguments do not assume consistency or the separate parametricity axioms. The size preorder may admit self-bounds or collapsed successors because only the listed positive rules are fields; must therefore retain its explicit meaning . Code carriers and arrow/identity-term types may have no contextual inhabitants, and internal products over empty types can impose no pointwise obligation in interpretations where those types are empty. Polynomial parameters have no cardinality or inhabitance restrictions. Existentially chosen laws or inverse data are not claimed unique. The predicates involving Nonempty require existence of terms but do not return chosen terms merely by definition. Fixed-point beta witnesses compare codes by internal identity, and their decoding uses identity elimination rather than equality reflection. The infrastructure contains full-morphism lifts and laws for their prescribed underlying actions, but does not include the hom-equivalence types, naturality, an adjunction structure, or coherence of the chosen square-proof components.
Literal defect report: I did not establish a literal type/formula defect from the permitted inputs. The distinctions and vacuity allowances above are statements of the definitions' scope, not judgments against an unseen intended statement. The inspected encoding text contains no explicit sorry, admit, or axiom declaration after comments are removed; that source scan is not a kernel axiom audit or a proof of the defined conclusion predicates.