Contextual type theory with large sizes and parametricity
DefinitionLaarakkerOttenVanDenBerg2026_TheoryRevision2The contextual rules of the paper's type theory: dependent products and sums, internal identity and J, function extensionality, a Tarski universe with small constructors and base types, the large size preorder, primitive size recursion with propositional unfolding, small existential and universal size quantifiers, and their substitution coherence. All four parametricity axioms refer to explicitly constructed canonical maps and internal half-adjoint equivalence types. Neither realizability data nor tracker restrictions are assumptions of the abstract theory. Contractibility, quantifier consequences, and the type of fixed-point solutions are defined without assuming their theorem witnesses.
import Mathlib.Logic.Basic
/-! Generated from reviewed V2 modules by bundle_v2.py.
See the accompanying manifest for exact input hashes and source order. -/
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TypeTheoryV2 -/
/-!
# Contextual interfaces for the type theory of large sizes
These interfaces present the structural and type-forming rules of Section 2 and
Appendix A of Laarakker–Otten–van den Berg (2026). `Tm Γ A` is an abstract set of
terms in a context; it is never identified with all metatheoretic functions.
In particular, abstraction accepts a term in an extended context. Realizability
and computability are properties of an interpretation, not additional premises
of these syntactic rules.
The external equalities below describe definitional equality and substitution
coherence. The separate `IdentityTypes.id` represents propositional identity;
no equality reflection or uniqueness of identity proofs is assumed.
This file gives interfaces for individual groups of rules, not a claim that the
full theory has been interpreted. Function extensionality and the four
parametricity equivalence axioms are not yet part of these interfaces.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
set_option linter.checkUnivs false in
/-- A category with families, with transport-explicit substitution equations. -/
structure CwF where
Ctx : Type u
Sub : Ctx → Ctx → Type v
id : {Γ : Ctx} → Sub Γ Γ
comp : {Γ Δ Θ : Ctx} → Sub Δ Γ → Sub Θ Δ → Sub Θ Γ
id_comp : ∀ {Γ Δ} (σ : Sub Δ Γ), comp id σ = σ
comp_id : ∀ {Γ Δ} (σ : Sub Δ Γ), comp σ id = σ
assoc : ∀ {Γ Δ Θ Ξ} (σ : Sub Δ Γ) (τ : Sub Θ Δ) (υ : Sub Ξ Θ),
comp (comp σ τ) υ = comp σ (comp τ υ)
Ty : Ctx → Type w
Tm : (Γ : Ctx) → Ty Γ → Type t
tySub : {Γ Δ : Ctx} → Ty Γ → Sub Δ Γ → Ty Δ
tmSub : {Γ Δ : Ctx} → {A : Ty Γ} → Tm Γ A → (σ : Sub Δ Γ) → Tm Δ (tySub A σ)
tySub_id : ∀ {Γ} (A : Ty Γ), tySub A id = A
tySub_comp : ∀ {Γ Δ Θ} (A : Ty Γ) (σ : Sub Δ Γ) (τ : Sub Θ Δ),
tySub (tySub A σ) τ = tySub A (comp σ τ)
tmSub_id : ∀ {Γ} {A : Ty Γ} (a : Tm Γ A), HEq (tmSub a id) a
tmSub_comp : ∀ {Γ Δ Θ} {A : Ty Γ} (a : Tm Γ A)
(σ : Sub Δ Γ) (τ : Sub Θ Δ), HEq (tmSub (tmSub a σ) τ) (tmSub a (comp σ τ))
empty : Ctx
emptySub : {Γ : Ctx} → Sub Γ empty
empty_unique : ∀ {Γ} (σ : Sub Γ empty), σ = emptySub
ext : (Γ : Ctx) → Ty Γ → Ctx
fst : {Γ : Ctx} → {A : Ty Γ} → Sub (ext Γ A) Γ
snd : {Γ : Ctx} → {A : Ty Γ} → Tm (ext Γ A) (tySub A fst)
pair : {Γ Δ : Ctx} → {A : Ty Γ} →
(σ : Sub Δ Γ) → Tm Δ (tySub A σ) → Sub Δ (ext Γ A)
pair_fst : ∀ {Γ Δ} {A : Ty Γ} (σ : Sub Δ Γ) (a : Tm Δ (tySub A σ)),
comp fst (pair σ a) = σ
pair_snd : ∀ {Γ Δ} {A : Ty Γ} (σ : Sub Δ Γ) (a : Tm Δ (tySub A σ)),
HEq (tmSub snd (pair σ a)) a
pair_unique : ∀ {Γ Δ} {A : Ty Γ} (σ : Sub Δ Γ) (a : Tm Δ (tySub A σ))
(τ : Sub Δ (ext Γ A)), comp fst τ = σ → HEq (tmSub snd τ) a → τ = pair σ a
namespace CwF
variable (C : CwF.{u, v, w, t})
/-- Transport a term along an external (definitional) type equality. -/
def castTm {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B) (a : C.Tm Γ A) : C.Tm Γ B :=
h ▸ a
/-- The substitution extending the identity by a term. -/
def termSub {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) : C.Sub Γ (C.ext Γ A) :=
C.pair C.id (C.castTm (C.tySub_id A).symm a)
/-- Lift a substitution under one binder. -/
def lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) :
C.Sub (C.ext Δ (C.tySub A σ)) (C.ext Γ A) :=
C.pair (C.comp σ C.fst) (C.castTm (C.tySub_comp A σ C.fst) C.snd)
/-- The defining equation for the first projection of a term section. -/
theorem termSub_fst {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) :
C.comp C.fst (C.termSub a) = C.id :=
C.pair_fst _ _
/-- External transport does not change the represented term. -/
theorem castTm_heq {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B) (a : C.Tm Γ A) :
HEq (C.castTm h a) a := by
cases h
rfl
/-- Substitution respects transport of a term's type. -/
theorem tmSub_heq {Γ Δ : C.Ctx} {A B : C.Ty Γ} {a : C.Tm Γ A} {b : C.Tm Γ B}
(hAB : A = B) (h : HEq a b) (σ : C.Sub Δ Γ) : HEq (C.tmSub a σ) (C.tmSub b σ) := by
cases hAB
cases h
rfl
/-- Substituting a term for the newest variable recovers that term. -/
theorem termSub_snd {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) :
HEq (C.tmSub C.snd (C.termSub a)) a :=
(C.pair_snd _ _).trans (C.castTm_heq _ _)
/-- Weakening a type and then substituting for the fresh variable recovers it. -/
theorem tySub_fst_termSub {Γ : C.Ctx} {A : C.Ty Γ} (B : C.Ty Γ) (a : C.Tm Γ A) :
C.tySub (C.tySub B C.fst) (C.termSub a) = B := by
rw [C.tySub_comp, C.termSub_fst, C.tySub_id]
/-- The corresponding equation for a weakened term. -/
theorem tmSub_fst_termSub {Γ : C.Ctx} {A B : C.Ty Γ} (b : C.Tm Γ B) (a : C.Tm Γ A) :
HEq (C.tmSub (C.tmSub b C.fst) (C.termSub a)) b := by
have h := C.tmSub_comp b C.fst (C.termSub a)
rw [C.termSub_fst] at h
exact h.trans (C.tmSub_id b)
end CwF
/-- Nondependent function types, with contextual abstraction and application.
These are a separately exposed fragment of the source's dependent products. -/
structure FunctionTypes (C : CwF.{u, v, w, t}) where
arr : {Γ : C.Ctx} → C.Ty Γ → C.Ty Γ → C.Ty Γ
arr_sub : ∀ {Γ Δ} (A B : C.Ty Γ) (σ : C.Sub Δ Γ),
C.tySub (arr A B) σ = arr (C.tySub A σ) (C.tySub B σ)
lam : {Γ : C.Ctx} → {A B : C.Ty Γ} →
C.Tm (C.ext Γ A) (C.tySub B C.fst) → C.Tm Γ (arr A B)
app : {Γ : C.Ctx} → {A B : C.Ty Γ} → C.Tm Γ (arr A B) → C.Tm Γ A → C.Tm Γ B
beta : ∀ {Γ} {A B : C.Ty Γ} (b : C.Tm (C.ext Γ A) (C.tySub B C.fst))
(a : C.Tm Γ A), HEq (app (lam b) a) (C.tmSub b (C.termSub a))
eta : ∀ {Γ} {A B : C.Ty Γ} (f : C.Tm Γ (arr A B)),
lam (app (C.castTm (arr_sub A B C.fst) (C.tmSub f C.fst)) C.snd) = f
app_sub : ∀ {Γ Δ} {A B : C.Ty Γ} (f : C.Tm Γ (arr A B)) (a : C.Tm Γ A)
(σ : C.Sub Δ Γ), C.tmSub (app f a) σ =
app (C.castTm (arr_sub A B σ) (C.tmSub f σ)) (C.tmSub a σ)
lam_sub : ∀ {Γ Δ} {A B : C.Ty Γ}
(b : C.Tm (C.ext Γ A) (C.tySub B C.fst)) (σ : C.Sub Δ Γ)
(b' : C.Tm (C.ext Δ (C.tySub A σ)) (C.tySub (C.tySub B σ) C.fst)),
HEq (C.tmSub b (C.lift σ A)) b' →
C.castTm (arr_sub A B σ) (C.tmSub (lam b) σ) = lam b'
namespace FunctionTypes
variable {C : CwF.{u, v, w, t}} (P : FunctionTypes C)
/-- Substitution on an arrow term, transporting its function type. -/
def sub {Γ Δ : C.Ctx} {A B : C.Ty Γ} (f : C.Tm Γ (P.arr A B)) (σ : C.Sub Δ Γ) :
C.Tm Δ (P.arr (C.tySub A σ) (C.tySub B σ)) :=
C.castTm (P.arr_sub A B σ) (C.tmSub f σ)
/-- The internal identity function, obtained by contextual abstraction. -/
def identity {Γ : C.Ctx} (A : C.Ty Γ) : C.Tm Γ (P.arr A A) :=
P.lam C.snd
/-- Internal function composition. -/
def compose {Γ : C.Ctx} {A B D : C.Ty Γ}
(g : C.Tm Γ (P.arr B D)) (f : C.Tm Γ (P.arr A B)) : C.Tm Γ (P.arr A D) :=
P.lam (P.app (P.sub g C.fst) (P.app (P.sub f C.fst) C.snd))
end FunctionTypes
/-- Dependent products with contextual abstraction, its inverse, and substitution. -/
structure DependentProducts (C : CwF.{u, v, w, t}) where
pi : {Γ : C.Ctx} → (A : C.Ty Γ) → C.Ty (C.ext Γ A) → C.Ty Γ
pi_sub : ∀ {Γ Δ} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) (σ : C.Sub Δ Γ),
C.tySub (pi A B) σ = pi (C.tySub A σ) (C.tySub B (C.lift σ A))
lam : {Γ : C.Ctx} → {A : C.Ty Γ} → {B : C.Ty (C.ext Γ A)} →
C.Tm (C.ext Γ A) B → C.Tm Γ (pi A B)
unlam : {Γ : C.Ctx} → {A : C.Ty Γ} → {B : C.Ty (C.ext Γ A)} →
C.Tm Γ (pi A B) → C.Tm (C.ext Γ A) B
beta : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)} (b : C.Tm (C.ext Γ A) B),
unlam (lam b) = b
eta : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)} (f : C.Tm Γ (pi A B)),
lam (unlam f) = f
lam_sub : ∀ {Γ Δ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(b : C.Tm (C.ext Γ A) B) (σ : C.Sub Δ Γ),
C.castTm (pi_sub A B σ) (C.tmSub (lam b) σ) = lam (C.tmSub b (C.lift σ A))
/-- Dependent sums; the projection types retain the dependency on the first component. -/
structure DependentSums (C : CwF.{u, v, w, t}) where
sigma : {Γ : C.Ctx} → (A : C.Ty Γ) → C.Ty (C.ext Γ A) → C.Ty Γ
sigma_sub : ∀ {Γ Δ} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) (σ : C.Sub Δ Γ),
C.tySub (sigma A B) σ = sigma (C.tySub A σ) (C.tySub B (C.lift σ A))
pair : {Γ : C.Ctx} → {A : C.Ty Γ} → {B : C.Ty (C.ext Γ A)} →
(a : C.Tm Γ A) → C.Tm Γ (C.tySub B (C.termSub a)) → C.Tm Γ (sigma A B)
fst : {Γ : C.Ctx} → {A : C.Ty Γ} → {B : C.Ty (C.ext Γ A)} →
C.Tm Γ (sigma A B) → C.Tm Γ A
snd : {Γ : C.Ctx} → {A : C.Ty Γ} → {B : C.Ty (C.ext Γ A)} →
(p : C.Tm Γ (sigma A B)) → C.Tm Γ (C.tySub B (C.termSub (fst p)))
fst_pair : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(a : C.Tm Γ A) (b : C.Tm Γ (C.tySub B (C.termSub a))), fst (pair a b) = a
snd_pair : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(a : C.Tm Γ A) (b : C.Tm Γ (C.tySub B (C.termSub a))), HEq (snd (pair a b)) b
eta : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)} (p : C.Tm Γ (sigma A B)),
pair (fst p) (snd p) = p
/-- Formation, reflexivity, and substitution for internal propositional identity.
There is deliberately no map from an identity term to external Lean equality. -/
structure IdentityTypes (C : CwF.{u, v, w, t}) where
id : {Γ : C.Ctx} → (A : C.Ty Γ) → C.Tm Γ A → C.Tm Γ A → C.Ty Γ
refl : {Γ : C.Ctx} → {A : C.Ty Γ} → (a : C.Tm Γ A) → C.Tm Γ (id A a a)
id_sub : ∀ {Γ Δ} {A : C.Ty Γ} (a b : C.Tm Γ A) (σ : C.Sub Δ Γ),
C.tySub (id A a b) σ = id (C.tySub A σ) (C.tmSub a σ) (C.tmSub b σ)
refl_sub : ∀ {Γ Δ} {A : C.Ty Γ} (a : C.Tm Γ A) (σ : C.Sub Δ Γ),
HEq (C.tmSub (refl a) σ) (refl (C.tmSub a σ))
namespace IdentityTypes
variable {C : CwF.{u, v, w, t}} (I : IdentityTypes C)
/-- Formation respects external transport; this is not equality reflection. -/
theorem id_congr {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B)
{a a' : C.Tm Γ A} {b b' : C.Tm Γ B} (ha : HEq a b) (hb : HEq a' b') :
I.id A a a' = I.id B b b' := by
cases h
cases ha
cases hb
rfl
/-- In `Γ, y : A`, the type `a = y` with `a` weakened from `Γ`. -/
def basedPath {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) : C.Ty (C.ext Γ A) :=
I.id (C.tySub A C.fst) (C.tmSub a C.fst) C.snd
/-- The identity context `Γ, y : A, p : a = y`. -/
def pathContext {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) : C.Ctx :=
C.ext (C.ext Γ A) (I.basedPath a)
/-- The identity type in the based path context specializes to `a = b`. -/
theorem basedPath_sub {Γ : C.Ctx} {A : C.Ty Γ} (a b : C.Tm Γ A) :
C.tySub (I.basedPath a) (C.termSub b) = I.id A a b := by
rw [basedPath, I.id_sub]
exact I.id_congr (C.tySub_fst_termSub A b)
(C.tmSub_fst_termSub a b) (C.termSub_snd b)
/-- Substitute an endpoint and a path into the based identity context. -/
def pathSub {Γ : C.Ctx} {A : C.Ty Γ} (a b : C.Tm Γ A)
(p : C.Tm Γ (I.id A a b)) : C.Sub Γ (I.pathContext a) :=
C.pair (C.termSub b) (C.castTm (I.basedPath_sub a b).symm p)
end IdentityTypes
/-- Based identity elimination, equivalent to the source's two-endpoint `J`
after weakening the first endpoint into the context. The motive is an actual
contextual type over endpoints and paths, not an arbitrary Lean function. -/
structure IdentityElimination (C : CwF.{u, v, w, t}) (I : IdentityTypes C) where
elim : ∀ {Γ} {A : C.Ty Γ} (a : C.Tm Γ A) (M : C.Ty (I.pathContext a)),
C.Tm Γ (C.tySub M (I.pathSub a a (I.refl a))) →
(b : C.Tm Γ A) → (p : C.Tm Γ (I.id A a b)) →
C.Tm Γ (C.tySub M (I.pathSub a b p))
beta : ∀ {Γ} {A : C.Ty Γ} (a : C.Tm Γ A) (M : C.Ty (I.pathContext a))
(d : C.Tm Γ (C.tySub M (I.pathSub a a (I.refl a)))),
elim a M d a (I.refl a) = d
/-- A Tarski universe and its decoding operation, stable under substitution. -/
structure Universe (C : CwF.{u, v, w, t}) where
type : (Γ : C.Ctx) → C.Ty Γ
type_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), C.tySub (type Γ) σ = type Δ
el : {Γ : C.Ctx} → C.Tm Γ (type Γ) → C.Ty Γ
el_sub : ∀ {Γ Δ} (A : C.Tm Γ (type Γ)) (σ : C.Sub Δ Γ),
C.tySub (el A) σ = el (C.castTm (type_sub σ) (C.tmSub A σ))
namespace Universe
variable {C : CwF.{u, v, w, t}} (U : Universe C)
/-- A small-type code in a context. -/
abbrev Code (Γ : C.Ctx) := C.Tm Γ (U.type Γ)
/-- Substitution on universe codes. -/
def sub {Γ Δ : C.Ctx} (A : U.Code Γ) (σ : C.Sub Δ Γ) : U.Code Δ :=
C.castTm (U.type_sub σ) (C.tmSub A σ)
/-- The generic universe code in a context extended by `U`. -/
def generic (Γ : C.Ctx) : U.Code (C.ext Γ (U.type Γ)) :=
C.castTm (U.type_sub C.fst) C.snd
/-- Extend a substitution by a universe code. -/
def extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Δ) :
C.Sub Δ (C.ext Γ (U.type Γ)) :=
C.pair σ (C.castTm (U.type_sub σ).symm A)
/-- Universe-code substitution respects composition. -/
theorem sub_comp {Γ Δ Θ : C.Ctx} (A : U.Code Γ) (σ : C.Sub Δ Γ) (τ : C.Sub Θ Δ) :
U.sub (U.sub A σ) τ = U.sub A (C.comp σ τ) := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (U.type_sub σ).symm (C.castTm_heq _ _) τ).trans
((C.tmSub_comp A σ τ).trans (C.castTm_heq _ _).symm))
/-- The generic universe code specializes to the code extending a substitution. -/
theorem generic_sub_extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Δ) :
U.sub (U.generic Γ) (U.extend σ A) = A := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (U.type_sub C.fst).symm (C.castTm_heq _ _) (U.extend σ A)).trans
((C.pair_snd _ _).trans (C.castTm_heq _ _)))
/-- Forgetting the last universe code recovers the original substitution. -/
theorem extend_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Δ) :
C.comp C.fst (U.extend σ A) = σ :=
C.pair_fst _ _
end Universe
/-- Closure of the Tarski universe under the source's small type constructors. -/
structure SmallTypeConstructors (C : CwF.{u, v, w, t})
(U : Universe C) (P : DependentProducts C) (S : DependentSums C)
(I : IdentityTypes C) where
pi : {Γ : C.Ctx} → (A : U.Code Γ) → U.Code (C.ext Γ (U.el A)) → U.Code Γ
sigma : {Γ : C.Ctx} → (A : U.Code Γ) → U.Code (C.ext Γ (U.el A)) → U.Code Γ
id : {Γ : C.Ctx} → (A : U.Code Γ) → C.Tm Γ (U.el A) → C.Tm Γ (U.el A) → U.Code Γ
el_pi : ∀ {Γ} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))),
U.el (pi A B) = P.pi (U.el A) (U.el B)
el_sigma : ∀ {Γ} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))),
U.el (sigma A B) = S.sigma (U.el A) (U.el B)
el_id : ∀ {Γ} (A : U.Code Γ) (a b : C.Tm Γ (U.el A)),
U.el (id A a b) = I.id (U.el A) a b
/-- The large size type, its preorder, and the source's proof-irrelevance rule
for that preorder. Proof irrelevance here is an internal term, not Lean equality. -/
structure SizeRules (C : CwF.{u, v, w, t}) (U : Universe C) (I : IdentityTypes C) where
type : (Γ : C.Ctx) → C.Ty Γ
type_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), C.tySub (type Γ) σ = type Δ
zero : {Γ : C.Ctx} → C.Tm Γ (type Γ)
succ : {Γ : C.Ctx} → C.Tm Γ (type Γ) → C.Tm Γ (type Γ)
le : {Γ : C.Ctx} → C.Tm Γ (type Γ) → C.Tm Γ (type Γ) → U.Code Γ
le_zero : ∀ {Γ} (i : C.Tm Γ (type Γ)), C.Tm Γ (U.el (le zero i))
le_succ : ∀ {Γ} (i : C.Tm Γ (type Γ)), C.Tm Γ (U.el (le i (succ i)))
le_refl : ∀ {Γ} (i : C.Tm Γ (type Γ)), C.Tm Γ (U.el (le i i))
le_trans : ∀ {Γ} {i j k : C.Tm Γ (type Γ)},
C.Tm Γ (U.el (le i j)) → C.Tm Γ (U.el (le j k)) → C.Tm Γ (U.el (le i k))
le_prop : ∀ {Γ} {i j : C.Tm Γ (type Γ)} (p q : C.Tm Γ (U.el (le i j))),
C.Tm Γ (I.id (U.el (le i j)) p q)
namespace SizeRules
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
/-- Reindex a term of the large size type. -/
def sub {Γ Δ : C.Ctx} (i : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ) :
C.Tm Δ (Z.type Δ) :=
C.castTm (Z.type_sub σ) (C.tmSub i σ)
/-- The generic size in `Γ, i : Size`. -/
def generic (Γ : C.Ctx) : C.Tm (C.ext Γ (Z.type Γ)) (Z.type (C.ext Γ (Z.type Γ))) :=
C.castTm (Z.type_sub C.fst) C.snd
/-- Extend a substitution by a size term. -/
def extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (i : C.Tm Δ (Z.type Δ)) :
C.Sub Δ (C.ext Γ (Z.type Γ)) :=
C.pair σ (C.castTm (Z.type_sub σ).symm i)
/-- In `Γ, i : Size, j : Size`, the small type `j < i`. -/
def bound {Γ : C.Ctx} :
C.Ty (C.ext (C.ext Γ (Z.type Γ)) (Z.type (C.ext Γ (Z.type Γ)))) :=
U.el (Z.le (Z.succ (Z.generic (C.ext Γ (Z.type Γ))))
(Z.sub (Z.generic Γ) C.fst))
/-- Select the inner size `j` from `Γ, i : Size, j : Size`. -/
def inner {Γ : C.Ctx} :
C.Sub (C.ext (C.ext Γ (Z.type Γ)) (Z.type (C.ext Γ (Z.type Γ))))
(C.ext Γ (Z.type Γ)) :=
Z.extend (C.comp C.fst C.fst) (Z.generic (C.ext Γ (Z.type Γ)))
/-- The source abbreviation `Π j : Size, j < i → A(j)` in context `Γ, i : Size`.
For a large family the products are large dependent products. -/
def bounded (P : DependentProducts C) (F : FunctionTypes C)
{Γ : C.Ctx} (A : C.Ty (C.ext Γ (Z.type Γ))) : C.Ty (C.ext Γ (Z.type Γ)) :=
P.pi (Z.type (C.ext Γ (Z.type Γ))) (F.arr Z.bound (C.tySub A Z.inner))
/-- Restrict an internal dependent function to sizes below the generic size.
This is the source term `λ j < i, h j`, formed solely by contextual abstraction. -/
def restrict (P : DependentProducts C) (F : FunctionTypes C)
{Γ : C.Ctx} {A : C.Ty (C.ext Γ (Z.type Γ))}
(h : C.Tm Γ (P.pi (Z.type Γ) A)) :
C.Tm (C.ext Γ (Z.type Γ)) (Z.bounded P F A) :=
P.lam (F.lam (C.tmSub (C.tmSub (P.unlam h) Z.inner) C.fst))
end SizeRules
/-- The source's primitive size elimination rule and its propositional β-rule.
Neither uniqueness nor an algebraic fixed-point theorem is a field. -/
structure SizeRecursion (C : CwF.{u, v, w, t}) (U : Universe C)
(I : IdentityTypes C) (Z : SizeRules C U I)
(P : DependentProducts C) (F : FunctionTypes C) where
fix : ∀ {Γ} (A : C.Ty (C.ext Γ (Z.type Γ))),
C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A)) →
C.Tm Γ (P.pi (Z.type Γ) A)
beta : ∀ {Γ} (A : C.Ty (C.ext Γ (Z.type Γ)))
(f : C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A))),
C.Tm Γ (P.pi (Z.type Γ)
(I.id A (P.unlam (fix A f))
(F.app (P.unlam f) (Z.restrict P F (fix A f)))))
/-- Small universal quantification over the large size type. Both introduction
and generic application act on contextual terms, with the source's β/η equations. -/
structure UniversalSizeQuantifier (C : CwF.{u, v, w, t})
(U : Universe C) (I : IdentityTypes C) (Z : SizeRules C U I) where
code : {Γ : C.Ctx} → U.Code (C.ext Γ (Z.type Γ)) → U.Code Γ
lam : {Γ : C.Ctx} → {A : U.Code (C.ext Γ (Z.type Γ))} →
C.Tm (C.ext Γ (Z.type Γ)) (U.el A) → C.Tm Γ (U.el (code A))
unlam : {Γ : C.Ctx} → {A : U.Code (C.ext Γ (Z.type Γ))} →
C.Tm Γ (U.el (code A)) → C.Tm (C.ext Γ (Z.type Γ)) (U.el A)
beta : ∀ {Γ} {A : U.Code (C.ext Γ (Z.type Γ))}
(a : C.Tm (C.ext Γ (Z.type Γ)) (U.el A)), unlam (lam a) = a
eta : ∀ {Γ} {A : U.Code (C.ext Γ (Z.type Γ))}
(f : C.Tm Γ (U.el (code A))), lam (unlam f) = f
/-- Small existential quantification, including dependent elimination only to
a small motive. The generic pair lives in `Γ, i : Size, x : A(i)`; the eliminator
takes a contextual branch over precisely that context. -/
structure ExistentialSizeQuantifier (C : CwF.{u, v, w, t})
(U : Universe C) (I : IdentityTypes C) (Z : SizeRules C U I) where
code : {Γ : C.Ctx} → U.Code (C.ext Γ (Z.type Γ)) → U.Code Γ
pair : ∀ {Γ} (A : U.Code (C.ext Γ (Z.type Γ))),
C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el A))
(C.tySub (U.el (code A)) (C.comp C.fst C.fst))
elim : ∀ {Γ} (A : U.Code (C.ext Γ (Z.type Γ)))
(M : U.Code (C.ext Γ (U.el (code A)))),
C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el A))
(C.tySub (U.el M) (C.pair (C.comp C.fst C.fst) (pair A))) →
C.Tm (C.ext Γ (U.el (code A))) (U.el M)
beta : ∀ {Γ} (A : U.Code (C.ext Γ (Z.type Γ)))
(M : U.Code (C.ext Γ (U.el (code A))))
(p : C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el A))
(C.tySub (U.el M) (C.pair (C.comp C.fst C.fst) (pair A)))),
C.tmSub (elim A M p) (C.pair (C.comp C.fst C.fst) (pair A)) = p
/-- The internal contractibility type `Σ x : A, Π y : A, x = y`.
Its identity witnesses remain internal terms. -/
def contractible {C : CwF.{u, v, w, t}} (P : DependentProducts C)
(S : DependentSums C) (I : IdentityTypes C) {Γ : C.Ctx} (A : C.Ty Γ) : C.Ty Γ :=
S.sigma A (P.pi (C.tySub A C.fst)
(I.id (C.tySub (C.tySub A C.fst) C.fst) (C.tmSub C.snd C.fst) C.snd))
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TypeTheoryRulesV2 -/
/-!
# Further contextual rules and substitution stability
This module supplies the source's base-type rules and the substitution stability
of its size operations and quantifiers. It remains separate from the underlying
CwF interface so that interpretations can be constructed in stages.
No realizability assumptions, external function introduction rules, or
fixed-point uniqueness principles occur here.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
/-- The nondependent function interface is the corresponding special case of
dependent products, as required by the source notation `A → B`. -/
structure FunctionProductCompatibility (F : FunctionTypes C) (P : DependentProducts C) where
arr_eq : ∀ {Γ} (A B : C.Ty Γ), F.arr A B = P.pi A (C.tySub B C.fst)
lam_eq : ∀ {Γ} {A B : C.Ty Γ} (b : C.Tm (C.ext Γ A) (C.tySub B C.fst)),
HEq (F.lam b) (P.lam b)
/-- Substitution coherence for dependent sum introduction and projections. -/
structure DependentSumSubstitution (S : DependentSums C) where
pair_sub : ∀ {Γ Δ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(a : C.Tm Γ A) (b : C.Tm Γ (C.tySub B (C.termSub a))) (σ : C.Sub Δ Γ)
(b' : C.Tm Δ (C.tySub (C.tySub B (C.lift σ A)) (C.termSub (C.tmSub a σ)))),
HEq (C.tmSub b σ) b' → HEq (C.tmSub (S.pair a b) σ) (S.pair (C.tmSub a σ) b')
fst_sub : ∀ {Γ Δ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(p : C.Tm Γ (S.sigma A B)) (σ : C.Sub Δ Γ),
C.tmSub (S.fst p) σ = S.fst (C.castTm (S.sigma_sub A B σ) (C.tmSub p σ))
snd_sub : ∀ {Γ Δ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(p : C.Tm Γ (S.sigma A B)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (S.snd p) σ) (S.snd (C.castTm (S.sigma_sub A B σ) (C.tmSub p σ)))
/-- Empty, unit, and boolean types as codes in the source's Tarski universe,
including their dependent elimination and computation rules. -/
structure BaseTypes (U : Universe C) where
empty : {Γ : C.Ctx} → U.Code Γ
unit : {Γ : C.Ctx} → U.Code Γ
bool : {Γ : C.Ctx} → U.Code Γ
star : {Γ : C.Ctx} → C.Tm Γ (U.el unit)
false : {Γ : C.Ctx} → C.Tm Γ (U.el bool)
true : {Γ : C.Ctx} → C.Tm Γ (U.el bool)
empty_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), U.sub empty σ = empty
unit_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), U.sub unit σ = unit
bool_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), U.sub bool σ = bool
star_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), HEq (C.tmSub star σ) (@star Δ)
false_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), HEq (C.tmSub false σ) (@false Δ)
true_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), HEq (C.tmSub true σ) (@true Δ)
emptyElim : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el empty))),
C.Tm (C.ext Γ (U.el empty)) M
unitElim : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el unit))),
C.Tm Γ (C.tySub M (C.termSub star)) → C.Tm (C.ext Γ (U.el unit)) M
unit_beta : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el unit)))
(d : C.Tm Γ (C.tySub M (C.termSub star))),
C.tmSub (unitElim M d) (C.termSub star) = d
boolElim : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el bool))),
C.Tm Γ (C.tySub M (C.termSub false)) →
C.Tm Γ (C.tySub M (C.termSub true)) → C.Tm (C.ext Γ (U.el bool)) M
bool_beta_false : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el bool)))
(f : C.Tm Γ (C.tySub M (C.termSub false)))
(t : C.Tm Γ (C.tySub M (C.termSub true))),
C.tmSub (boolElim M f t) (C.termSub false) = f
bool_beta_true : ∀ {Γ} (M : C.Ty (C.ext Γ (U.el bool)))
(f : C.Tm Γ (C.tySub M (C.termSub false)))
(t : C.Tm Γ (C.tySub M (C.termSub true))),
C.tmSub (boolElim M f t) (C.termSub true) = t
namespace SizeRules
variable {U : Universe C} {I : IdentityTypes C} (Z : SizeRules C U I)
/-- Lift a substitution under a size binder, accounting for stability of Size. -/
def lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
C.Sub (C.ext Δ (Z.type Δ)) (C.ext Γ (Z.type Γ)) :=
Z.extend (C.comp σ C.fst) (Z.generic Δ)
end SizeRules
/-- Substitution coherence of the source's size constructors and preorder terms. -/
structure SizeSubstitution (U : Universe C) (I : IdentityTypes C) (Z : SizeRules C U I) where
zero_sub : ∀ {Γ Δ} (σ : C.Sub Δ Γ), Z.sub Z.zero σ = Z.zero
succ_sub : ∀ {Γ Δ} (i : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ),
Z.sub (Z.succ i) σ = Z.succ (Z.sub i σ)
le_sub : ∀ {Γ Δ} (i j : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ),
U.sub (Z.le i j) σ = Z.le (Z.sub i σ) (Z.sub j σ)
le_zero_sub : ∀ {Γ Δ} (i : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Z.le_zero i) σ) (Z.le_zero (Z.sub i σ))
le_succ_sub : ∀ {Γ Δ} (i : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Z.le_succ i) σ) (Z.le_succ (Z.sub i σ))
le_refl_sub : ∀ {Γ Δ} (i : C.Tm Γ (Z.type Γ)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Z.le_refl i) σ) (Z.le_refl (Z.sub i σ))
le_trans_sub : ∀ {Γ Δ} {i j k : C.Tm Γ (Z.type Γ)}
(p : C.Tm Γ (U.el (Z.le i j))) (q : C.Tm Γ (U.el (Z.le j k))) (σ : C.Sub Δ Γ)
(p' : C.Tm Δ (U.el (Z.le (Z.sub i σ) (Z.sub j σ))))
(q' : C.Tm Δ (U.el (Z.le (Z.sub j σ) (Z.sub k σ)))),
HEq (C.tmSub p σ) p' → HEq (C.tmSub q σ) q' →
HEq (C.tmSub (Z.le_trans p q) σ) (Z.le_trans p' q')
le_prop_sub : ∀ {Γ Δ} {i j : C.Tm Γ (Z.type Γ)}
(p q : C.Tm Γ (U.el (Z.le i j))) (σ : C.Sub Δ Γ)
(p' q' : C.Tm Δ (U.el (Z.le (Z.sub i σ) (Z.sub j σ)))),
HEq (C.tmSub p σ) p' → HEq (C.tmSub q σ) q' →
HEq (C.tmSub (Z.le_prop p q) σ) (Z.le_prop p' q')
/-- Substitution coherence of the primitive size fixpoint and its propositional
unfolding proof. Transported recursive-step terms are stated explicitly. -/
structure SizeRecursionSubstitution (U : Universe C) (I : IdentityTypes C)
(Z : SizeRules C U I) (P : DependentProducts C) (F : FunctionTypes C)
(R : SizeRecursion C U I Z P F) where
fix_sub : ∀ {Γ Δ} (A : C.Ty (C.ext Γ (Z.type Γ)))
(f : C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A))) (σ : C.Sub Δ Γ)
(f' : C.Tm Δ (P.pi (Z.type Δ)
(F.arr (Z.bounded P F (C.tySub A (Z.lift σ))) (C.tySub A (Z.lift σ))))),
HEq (C.tmSub f σ) f' → HEq (C.tmSub (R.fix A f) σ) (R.fix (C.tySub A (Z.lift σ)) f')
beta_sub : ∀ {Γ Δ} (A : C.Ty (C.ext Γ (Z.type Γ)))
(f : C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A))) (σ : C.Sub Δ Γ)
(f' : C.Tm Δ (P.pi (Z.type Δ)
(F.arr (Z.bounded P F (C.tySub A (Z.lift σ))) (C.tySub A (Z.lift σ))))),
HEq (C.tmSub f σ) f' → HEq (C.tmSub (R.beta A f) σ) (R.beta (C.tySub A (Z.lift σ)) f')
/-- Substitution coherence of the small universal size quantifier. -/
structure UniversalSizeSubstitution (U : Universe C) (I : IdentityTypes C)
(Z : SizeRules C U I) (Q : UniversalSizeQuantifier C U I Z) where
code_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ),
U.sub (Q.code A) σ = Q.code (U.sub A (Z.lift σ))
lam_sub : ∀ {Γ Δ} {A : U.Code (C.ext Γ (Z.type Γ))}
(a : C.Tm (C.ext Γ (Z.type Γ)) (U.el A)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Q.lam a) σ)
(Q.lam (C.castTm (U.el_sub A (Z.lift σ)) (C.tmSub a (Z.lift σ))))
unlam_sub : ∀ {Γ Δ} {A : U.Code (C.ext Γ (Z.type Γ))}
(f : C.Tm Γ (U.el (Q.code A))) (σ : C.Sub Δ Γ)
(f' : C.Tm Δ (U.el (Q.code (U.sub A (Z.lift σ))))),
HEq (C.tmSub f σ) f' → HEq (C.tmSub (Q.unlam f) (Z.lift σ)) (Q.unlam f')
/-- Substitution coherence for existential type formation. Its elimination
rule is already contextual in `ExistentialSizeQuantifier`. -/
structure ExistentialSizeSubstitution (U : Universe C) (I : IdentityTypes C)
(Z : SizeRules C U I) (Q : ExistentialSizeQuantifier C U I Z) where
code_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ),
U.sub (Q.code A) σ = Q.code (U.sub A (Z.lift σ))
namespace Universe
variable (U : Universe C)
/-- Lift a substitution under a variable of a decoded small type. -/
def liftEl {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) :
C.Sub (C.ext Δ (U.el (U.sub A σ))) (C.ext Γ (U.el A)) :=
C.pair (C.comp σ C.fst)
(C.castTm ((congrArg (fun B => C.tySub B C.fst) (U.el_sub A σ).symm).trans
(C.tySub_comp (U.el A) σ C.fst)) C.snd)
/-- The same context lift with a definitionally equal target code. -/
def liftElAs {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) (B : U.Code Δ)
(h : U.sub A σ = B) : C.Sub (C.ext Δ (U.el B)) (C.ext Γ (U.el A)) :=
h ▸ U.liftEl σ A
end Universe
/-- Substitution coherence of the base-type eliminators. The code equalities
select the exact lifted context; branch terms are transported explicitly. -/
structure BaseTypeSubstitution (U : Universe C) (B : BaseTypes U) where
emptyElim_sub : ∀ {Γ Δ} (M : C.Ty (C.ext Γ (U.el B.empty))) (σ : C.Sub Δ Γ),
C.tmSub (B.emptyElim M) (U.liftElAs σ B.empty B.empty (B.empty_sub σ)) =
B.emptyElim (C.tySub M (U.liftElAs σ B.empty B.empty (B.empty_sub σ)))
unitElim_sub : ∀ {Γ Δ} (M : C.Ty (C.ext Γ (U.el B.unit)))
(d : C.Tm Γ (C.tySub M (C.termSub B.star))) (σ : C.Sub Δ Γ)
(d' : C.Tm Δ (C.tySub
(C.tySub M (U.liftElAs σ B.unit B.unit (B.unit_sub σ))) (C.termSub B.star))),
HEq (C.tmSub d σ) d' →
C.tmSub (B.unitElim M d) (U.liftElAs σ B.unit B.unit (B.unit_sub σ)) =
B.unitElim (C.tySub M (U.liftElAs σ B.unit B.unit (B.unit_sub σ))) d'
boolElim_sub : ∀ {Γ Δ} (M : C.Ty (C.ext Γ (U.el B.bool)))
(f : C.Tm Γ (C.tySub M (C.termSub B.false)))
(t : C.Tm Γ (C.tySub M (C.termSub B.true))) (σ : C.Sub Δ Γ)
(f' : C.Tm Δ (C.tySub
(C.tySub M (U.liftElAs σ B.bool B.bool (B.bool_sub σ))) (C.termSub B.false)))
(t' : C.Tm Δ (C.tySub
(C.tySub M (U.liftElAs σ B.bool B.bool (B.bool_sub σ))) (C.termSub B.true))),
HEq (C.tmSub f σ) f' → HEq (C.tmSub t σ) t' →
C.tmSub (B.boolElim M f t) (U.liftElAs σ B.bool B.bool (B.bool_sub σ)) =
B.boolElim (C.tySub M (U.liftElAs σ B.bool B.bool (B.bool_sub σ))) f' t'
/-- Substitution coherence for existential pairing and dependent elimination. -/
structure ExistentialTermSubstitution (U : Universe C) (I : IdentityTypes C)
(Z : SizeRules C U I) (E : ExistentialSizeQuantifier C U I Z)
(ES : ExistentialSizeSubstitution U I Z E) where
pair_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ),
HEq (C.tmSub (E.pair A) (U.liftEl (Z.lift σ) A)) (E.pair (U.sub A (Z.lift σ)))
elim_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ)))
(M : U.Code (C.ext Γ (U.el (E.code A))))
(b : C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el A))
(C.tySub (U.el M) (C.pair (C.comp C.fst C.fst) (E.pair A))))
(σ : C.Sub Δ Γ)
(b' : C.Tm (C.ext (C.ext Δ (Z.type Δ)) (U.el (U.sub A (Z.lift σ))))
(C.tySub
(U.el (U.sub M
(U.liftElAs σ (E.code A) (E.code (U.sub A (Z.lift σ))) (ES.code_sub A σ))))
(C.pair (C.comp C.fst C.fst) (E.pair (U.sub A (Z.lift σ)))))),
HEq (C.tmSub b (U.liftEl (Z.lift σ) A)) b' →
HEq (C.tmSub (E.elim A M b)
(U.liftElAs σ (E.code A) (E.code (U.sub A (Z.lift σ))) (ES.code_sub A σ)))
(E.elim (U.sub A (Z.lift σ))
(U.sub M (U.liftElAs σ (E.code A) (E.code (U.sub A (Z.lift σ))) (ES.code_sub A σ))) b')
/-- Substitution coherence of the universe's dependent product, dependent sum,
and identity codes. -/
structure SmallTypeSubstitution (U : Universe C) (P : DependentProducts C)
(S : DependentSums C) (I : IdentityTypes C) (K : SmallTypeConstructors C U P S I) where
pi_sub : ∀ {Γ Δ} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) (σ : C.Sub Δ Γ),
U.sub (K.pi A B) σ = K.pi (U.sub A σ) (U.sub B (U.liftEl σ A))
sigma_sub : ∀ {Γ Δ} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) (σ : C.Sub Δ Γ),
U.sub (K.sigma A B) σ = K.sigma (U.sub A σ) (U.sub B (U.liftEl σ A))
id_sub : ∀ {Γ Δ} (A : U.Code Γ) (a b : C.Tm Γ (U.el A)) (σ : C.Sub Δ Γ),
U.sub (K.id A a b) σ = K.id (U.sub A σ)
(C.castTm (U.el_sub A σ) (C.tmSub a σ))
(C.castTm (U.el_sub A σ) (C.tmSub b σ))
namespace SizeRules
variable {U : Universe C} {I : IdentityTypes C} (Z : SizeRules C U I)
/-- The universe code for the source abbreviation `j < i`. -/
def boundCode {Γ : C.Ctx} :
U.Code (C.ext (C.ext Γ (Z.type Γ)) (Z.type (C.ext Γ (Z.type Γ)))) :=
Z.le (Z.succ (Z.generic (C.ext Γ (Z.type Γ)))) (Z.sub (Z.generic Γ) C.fst)
/-- The code of the bounded existential `∃ j < i, A(j)`. -/
def diamond {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (E : ExistentialSizeQuantifier C U I Z)
{Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code (C.ext Γ (Z.type Γ)) :=
E.code (K.sigma Z.boundCode (U.sub (U.sub A Z.inner) C.fst))
/-- The code of the bounded universal `∀ j < i, A(j)`. -/
def box {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (Q : UniversalSizeQuantifier C U I Z)
{Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code (C.ext Γ (Z.type Γ)) :=
Q.code (K.pi Z.boundCode (U.sub (U.sub A Z.inner) C.fst))
/-- The canonical forward operation for universal quantification over `<`:
`f ↦ λ i, λ j < i, f j`. Its body uses only the source introduction rules. -/
def forallBound {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (Q : UniversalSizeQuantifier C U I Z)
{Γ : C.Ctx} {A : U.Code (C.ext Γ (Z.type Γ))}
(f : C.Tm Γ (U.el (Q.code A))) : C.Tm Γ (U.el (Q.code (Z.box K Q A))) :=
Q.lam (Q.lam (C.castTm (K.el_pi Z.boundCode (U.sub (U.sub A Z.inner) C.fst)).symm
(P.lam (C.castTm (U.el_sub (U.sub A Z.inner) C.fst)
(C.tmSub (C.castTm (U.el_sub A Z.inner) (C.tmSub (Q.unlam f) Z.inner)) C.fst)))))
end SizeRules
namespace ExistentialSizeQuantifier
variable {U : Universe C} {I : IdentityTypes C} {Z : SizeRules C U I}
(E : ExistentialSizeQuantifier C U I Z)
/-- The context map presenting the generic existential pair. -/
def pairSub {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) :
C.Sub (C.ext (C.ext Γ (Z.type Γ)) (U.el A)) (C.ext Γ (U.el (E.code A))) :=
C.pair (C.comp C.fst C.fst) (E.pair A)
/-- Nondependent elimination to a small code, derived from the source's
dependent elimination rule. The branch is still an internal contextual term. -/
def recursor (F : FunctionTypes C) {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ)))
(B : U.Code Γ)
(b : C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el A))
(C.tySub (U.el B) (C.comp C.fst C.fst))) :
C.Tm Γ (F.arr (U.el (E.code A)) (U.el B)) := by
have h : C.tySub (U.el (U.sub B C.fst)) (E.pairSub A) =
C.tySub (U.el B) (C.comp C.fst C.fst) := by
calc
_ = C.tySub (C.tySub (U.el B) C.fst) (E.pairSub A) :=
congrArg (fun X => C.tySub X (E.pairSub A)) (U.el_sub B C.fst).symm
_ = _ := by rw [C.tySub_comp, pairSub, C.pair_fst]
exact F.lam (C.castTm (U.el_sub B C.fst).symm
(E.elim A (U.sub B C.fst) (C.castTm h.symm b)))
end ExistentialSizeQuantifier
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TheoryEquivalenceV2 -/
/-!
# Internal paths and half-adjoint equivalences
These are contextual constructions in the theory of Section 2, not Lean equality
or metatheoretic equivalences. Function action on paths is derived from the source's
identity eliminator. No identity reflection or uniqueness of identity proofs is used.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace FunctionTypes
variable {C : CwF.{u, v, w, t}} (F : FunctionTypes C)
/-- Function substitution represents ordinary term substitution with its type transported. -/
theorem sub_heq {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (σ : C.Sub Δ Γ) :
HEq (F.sub f σ) (C.tmSub f σ) := C.castTm_heq _ _
/-- Function substitution composes, with the explicit type transports retained. -/
theorem sub_comp_heq {Γ Δ Θ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (σ : C.Sub Δ Γ) (τ : C.Sub Θ Δ) :
HEq (F.sub (F.sub f σ) τ) (F.sub f (C.comp σ τ)) :=
(F.sub_heq _ _).trans
((C.tmSub_heq (F.arr_sub A B σ).symm (F.sub_heq f σ) τ).trans
((C.tmSub_comp f σ τ).trans (F.sub_heq _ _).symm))
/-- Application respects external type transport. This says nothing about internal paths. -/
theorem app_congr {Γ : C.Ctx} {A A' B B' : C.Ty Γ}
(hA : A = A') (hB : B = B')
{f : C.Tm Γ (F.arr A B)} {f' : C.Tm Γ (F.arr A' B')}
{a : C.Tm Γ A} {a' : C.Tm Γ A'} (hf : HEq f f') (ha : HEq a a') :
HEq (F.app f a) (F.app f' a') := by
cases hA
cases hB
cases hf
cases ha
rfl
end FunctionTypes
namespace IdentityTypes
variable {C : CwF.{u, v, w, t}} (I : IdentityTypes C)
/-- Forgetting a path argument recovers its endpoint substitution. -/
theorem pathSub_fst {Γ : C.Ctx} {A : C.Ty Γ} (a b : C.Tm Γ A)
(p : C.Tm Γ (I.id A a b)) : C.comp C.fst (I.pathSub a b p) = C.termSub b :=
C.pair_fst _ _
end IdentityTypes
namespace InternalPath
variable {C : CwF.{u, v, w, t}}
(F : FunctionTypes C) (I : IdentityTypes C) (J : IdentityElimination C I)
/-- The endpoint-indexed family `f(a) = f(y)` before adjoining the source path. -/
def apEndpoint {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (a : C.Tm Γ A) : C.Ty (C.ext Γ A) :=
I.id (C.tySub B C.fst) (C.tmSub (F.app f a) C.fst)
(F.app (F.sub f C.fst) C.snd)
theorem apEndpoint_sub {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (a b : C.Tm Γ A) :
C.tySub (apEndpoint F I f a) (C.termSub b) = I.id B (F.app f a) (F.app f b) := by
rw [apEndpoint, I.id_sub]
apply I.id_congr (C.tySub_fst_termSub B b) (C.tmSub_fst_termSub (F.app f a) b)
rw [F.app_sub]
apply F.app_congr (C.tySub_fst_termSub A b) (C.tySub_fst_termSub B b)
· have h := F.sub_comp_heq f C.fst (C.termSub b)
rw [C.termSub_fst] at h
exact h.trans ((F.sub_heq f C.id).trans (C.tmSub_id f))
· exact C.termSub_snd b
/-- The motive for identity elimination defining action on paths. -/
def apMotive {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (a : C.Tm Γ A) : C.Ty (I.pathContext a) :=
C.tySub (apEndpoint F I f a) C.fst
theorem apMotive_sub {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (a b : C.Tm Γ A) (p : C.Tm Γ (I.id A a b)) :
C.tySub (apMotive F I f a) (I.pathSub a b p) = I.id B (F.app f a) (F.app f b) := by
calc
_ = C.tySub (apEndpoint F I f a) (C.comp C.fst (I.pathSub a b p)) :=
C.tySub_comp _ _ _
_ = _ := by rw [I.pathSub_fst, apEndpoint_sub]
/-- Function action on identity terms, obtained by the actual `J` rule. -/
def ap {Γ : C.Ctx} {A B : C.Ty Γ} (f : C.Tm Γ (F.arr A B))
{a b : C.Tm Γ A} (p : C.Tm Γ (I.id A a b)) :
C.Tm Γ (I.id B (F.app f a) (F.app f b)) :=
C.castTm (apMotive_sub F I f a b p)
(J.elim a (apMotive F I f a)
(C.castTm (apMotive_sub F I f a a (I.refl a)).symm (I.refl (F.app f a))) b p)
/-- The action of a function on reflexivity is reflexivity, by the beta rule for `J`. -/
theorem ap_refl {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (a : C.Tm Γ A) :
ap F I J f (I.refl a) = I.refl (F.app f a) := by
unfold ap
rw [J.beta]
apply eq_of_heq
exact (C.castTm_heq _ _).trans (C.castTm_heq _ _)
end InternalPath
namespace InternalEquivalence
variable {C : CwF.{u, v, w, t}}
(F : FunctionTypes C) (P : DependentProducts C) (I : IdentityTypes C)
/-- The family `g (f x) = x` over the generic source element. -/
def homotopyBody {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A)) : C.Ty (C.ext Γ A) :=
I.id (C.tySub A C.fst) (F.app (F.sub g C.fst) (F.app (F.sub f C.fst) C.snd)) C.snd
/-- A homotopy from `g ∘ f` to the identity, expressed as an internal dependent product. -/
def homotopyType {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A)) : C.Ty Γ :=
P.pi A (homotopyBody F I f g)
theorem homotopyBody_sub {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A))
(σ : C.Sub Δ Γ) (a : C.Tm Δ (C.tySub A σ)) :
C.tySub (homotopyBody F I f g) (C.pair σ a) =
I.id (C.tySub A σ) (F.app (F.sub g σ) (F.app (F.sub f σ) a)) a := by
have hTy (T : C.Ty Γ) : C.tySub (C.tySub T C.fst) (C.pair σ a) = C.tySub T σ := by
rw [C.tySub_comp, C.pair_fst]
have hf : HEq (F.sub (F.sub f C.fst) (C.pair σ a)) (F.sub f σ) := by
have h := F.sub_comp_heq f C.fst (C.pair σ a)
rwa [C.pair_fst] at h
have hg : HEq (F.sub (F.sub g C.fst) (C.pair σ a)) (F.sub g σ) := by
have h := F.sub_comp_heq g C.fst (C.pair σ a)
rwa [C.pair_fst] at h
rw [homotopyBody, I.id_sub]
apply I.id_congr (hTy A) ?_ (C.pair_snd σ a)
rw [F.app_sub, F.app_sub]
exact F.app_congr (hTy B) (hTy A) hg
(F.app_congr (hTy A) (hTy B) hf (C.pair_snd σ a))
/-- Evaluate an internal homotopy after any substitution and at any source term. -/
def homotopyAt {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A))
(η : C.Tm Γ (homotopyType F P I f g))
(σ : C.Sub Δ Γ) (a : C.Tm Δ (C.tySub A σ)) :
C.Tm Δ (I.id (C.tySub A σ) (F.app (F.sub g σ) (F.app (F.sub f σ) a)) a) :=
C.castTm (homotopyBody_sub F I f g σ a) (C.tmSub (P.unlam η) (C.pair σ a))
/-- Homotopy formation is stable under contextual substitution. -/
theorem homotopyType_sub {Γ Δ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A)) (σ : C.Sub Δ Γ) :
C.tySub (homotopyType F P I f g) σ =
homotopyType F P I (F.sub f σ) (F.sub g σ) := by
rw [homotopyType, P.pi_sub]
congr 1
change C.tySub (homotopyBody F I f g)
(C.pair (C.comp σ C.fst) (C.castTm (C.tySub_comp A σ C.fst) C.snd)) = _
rw [homotopyBody_sub]
apply I.id_congr (C.tySub_comp A σ C.fst).symm ?_ (C.castTm_heq _ _)
exact F.app_congr (C.tySub_comp B σ C.fst).symm (C.tySub_comp A σ C.fst).symm
(F.sub_comp_heq g σ C.fst).symm
(F.app_congr (C.tySub_comp A σ C.fst).symm (C.tySub_comp B σ C.fst).symm
(F.sub_comp_heq f σ C.fst).symm (C.castTm_heq _ _))
/-- Substitute a homotopy, transporting its explicitly formed dependent product. -/
def homotopySub {Γ Δ : C.Ctx} {A B : C.Ty Γ}
{f : C.Tm Γ (F.arr A B)} {g : C.Tm Γ (F.arr B A)}
(η : C.Tm Γ (homotopyType F P I f g)) (σ : C.Sub Δ Γ) :
C.Tm Δ (homotopyType F P I (F.sub f σ) (F.sub g σ)) :=
C.castTm (homotopyType_sub F P I f g σ) (C.tmSub η σ)
/-- Half-adjoint coherence: `ap f (η x) = ε (f x)` for each source element. -/
def coherenceType (J : IdentityElimination C I) {Γ : C.Ctx} {A B : C.Ty Γ}
(f : C.Tm Γ (F.arr A B)) (g : C.Tm Γ (F.arr B A))
(η : C.Tm Γ (homotopyType F P I f g))
(ε : C.Tm Γ (homotopyType F P I g f)) : C.Ty Γ :=
P.pi A (I.id
(I.id (C.tySub B C.fst)
(F.app (F.sub f C.fst) (F.app (F.sub g C.fst) (F.app (F.sub f C.fst) C.snd)))
(F.app (F.sub f C.fst) C.snd))
(InternalPath.ap F I J (F.sub f C.fst) (P.unlam η))
(homotopyAt F P I g f ε C.fst (F.app (F.sub f C.fst) C.snd)))
/-- The source's `isEquiv f`, literally a dependent sum of an inverse, the two
homotopies, and the half-adjoint coherence, with `ap` derived from identity elimination. -/
def isEquiv (S : DependentSums C) (J : IdentityElimination C I)
{Γ : C.Ctx} {A B : C.Ty Γ} (f : C.Tm Γ (F.arr A B)) : C.Ty Γ :=
let G := F.arr B A
let f₁ := F.sub f C.fst (A := A) (B := B)
let g₁ : C.Tm (C.ext Γ G) (F.arr (C.tySub B C.fst) (C.tySub A C.fst)) :=
C.castTm (F.arr_sub B A C.fst) C.snd
let H := homotopyType F P I f₁ g₁
let f₂ := F.sub f₁ (C.fst (A := H))
let g₂ := F.sub g₁ (C.fst (A := H))
let η₂ := C.castTm (homotopyType_sub F P I f₁ g₁ C.fst) C.snd
let E := homotopyType F P I g₂ f₂
let f₃ := F.sub f₂ (C.fst (A := E))
let g₃ := F.sub g₂ (C.fst (A := E))
let η₃ := homotopySub F P I η₂ (C.fst (A := E))
let ε₃ := C.castTm (homotopyType_sub F P I g₂ f₂ C.fst) C.snd
S.sigma G (S.sigma H (S.sigma E (coherenceType F P I J f₃ g₃ η₃ ε₃)))
/-- The internal type of half-adjoint equivalences, including the forward function. -/
def equivalence (S : DependentSums C) (J : IdentityElimination C I)
{Γ : C.Ctx} (A B : C.Ty Γ) : C.Ty Γ :=
S.sigma (F.arr A B)
(isEquiv F P I S J (C.castTm (F.arr_sub A B C.fst) C.snd))
end InternalEquivalence
namespace CwF
variable (C : CwF.{u, v, w, t})
theorem tySub_fst_pair {Γ Δ : C.Ctx} (A B : C.Ty Γ)
(σ : C.Sub Δ Γ) (a : C.Tm Δ (C.tySub A σ)) :
C.tySub (C.tySub B C.fst) (C.pair σ a) = C.tySub B σ := by
rw [C.tySub_comp, C.pair_fst]
theorem pair_fst_snd {Γ : C.Ctx} (A : C.Ty Γ) :
C.pair (C.fst (A := A)) C.snd = C.id :=
(C.pair_unique _ _ _ (C.comp_id _) (C.tmSub_id _)).symm
theorem pair_comp {Γ Δ Θ : C.Ctx} {A : C.Ty Γ}
(σ : C.Sub Δ Γ) (a : C.Tm Δ (C.tySub A σ)) (τ : C.Sub Θ Δ) :
C.comp (C.pair σ a) τ =
C.pair (C.comp σ τ) (C.castTm (C.tySub_comp A σ τ) (C.tmSub a τ)) := by
apply C.pair_unique
· rw [← C.assoc, C.pair_fst]
· exact (C.tmSub_comp C.snd (C.pair σ a) τ).symm.trans
((C.tmSub_heq (C.tySub_fst_pair A A σ a) (C.pair_snd σ a) τ).trans
(C.castTm_heq _ _).symm)
theorem lift_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) :
C.comp C.fst (C.lift σ A) = C.comp σ C.fst := C.pair_fst _ _
theorem lift_snd {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) :
HEq (C.tmSub C.snd (C.lift σ A)) (C.snd (A := C.tySub A σ)) :=
(C.pair_snd _ _).trans (C.castTm_heq _ _)
/-- Context transport along an external equality of types. -/
def castExt {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B) : C.Sub (C.ext Γ A) (C.ext Γ B) :=
h ▸ C.id
theorem castExt_fst {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B) :
C.comp C.fst (C.castExt h) = C.fst := by
cases h
exact C.comp_id _
theorem castExt_snd {Γ : C.Ctx} {A B : C.Ty Γ} (h : A = B) :
HEq (C.tmSub C.snd (C.castExt h)) (C.snd (A := A)) := by
cases h
exact C.tmSub_id _
/-- A lift composed with a section is the corresponding extended substitution. -/
theorem lift_termSub {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ)
(a : C.Tm Δ (C.tySub A σ)) :
C.comp (C.lift σ A) (C.termSub a) = C.pair σ a := by
apply C.pair_unique
· rw [← C.assoc, C.lift_fst, C.assoc, C.termSub_fst, C.comp_id]
· have hTy : C.tySub (C.tySub A C.fst) (C.lift σ A) =
C.tySub (C.tySub A σ) C.fst := by
rw [C.tySub_comp, C.lift_fst, C.tySub_comp]
exact (C.tmSub_comp C.snd (C.lift σ A) (C.termSub a)).symm.trans
((C.tmSub_heq hTy (C.lift_snd σ A) (C.termSub a)).trans (C.termSub_snd a))
end CwF
namespace DependentProducts
variable {C : CwF.{u, v, w, t}} (P : DependentProducts C)
def sub {Γ Δ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ) :
C.Tm Δ (P.pi (C.tySub A σ) (C.tySub B (C.lift σ A))) :=
C.castTm (P.pi_sub A B σ) (C.tmSub f σ)
theorem sub_heq {Γ Δ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ) :
HEq (P.sub f σ) (C.tmSub f σ) := C.castTm_heq _ _
theorem unlam_sub {Γ Δ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ) :
P.unlam (P.sub f σ) = C.tmSub (P.unlam f) (C.lift σ A) := by
have h := congrArg P.unlam (P.lam_sub (P.unlam f) σ)
rw [P.eta, P.beta] at h
exact h
end DependentProducts
namespace CwF
variable (C : CwF.{u, v, w, t})
theorem tySub_lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) :
C.tySub (C.tySub A C.fst) (C.lift σ A) = C.tySub (C.tySub A σ) C.fst := by
rw [C.tySub_comp, C.lift_fst, C.tySub_comp]
/-- Lifting a retraction of contexts and transporting its domain yields the identity. -/
theorem lift_section {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (τ : C.Sub Γ Δ)
(hστ : C.comp σ τ = C.id) (A : C.Ty Γ)
(hA : C.tySub (C.tySub A σ) τ = A) :
C.comp (C.comp (C.lift σ A) (C.lift τ (C.tySub A σ))) (C.castExt hA.symm) = C.id := by
apply Eq.trans (C.pair_unique C.fst C.snd _ ?_ ?_) (C.pair_fst_snd A)
· calc
_ = C.comp (C.comp (C.comp C.fst (C.lift σ A)) (C.lift τ (C.tySub A σ)))
(C.castExt hA.symm) := by simp only [C.assoc]
_ = C.comp (C.comp (C.comp σ C.fst) (C.lift τ (C.tySub A σ)))
(C.castExt hA.symm) := by rw [C.lift_fst]
_ = C.comp (C.comp σ (C.comp τ C.fst)) (C.castExt hA.symm) := by
rw [C.assoc σ C.fst, C.lift_fst]
_ = C.comp (C.comp (C.comp σ τ) C.fst) (C.castExt hA.symm) := by
rw [C.assoc σ τ]
_ = C.fst := by rw [hστ, C.id_comp, C.castExt_fst]
· have hTy : C.tySub (C.tySub A C.fst)
(C.comp (C.lift σ A) (C.lift τ (C.tySub A σ))) =
C.tySub (C.tySub (C.tySub A σ) τ) C.fst := by
rw [← C.tySub_comp, C.tySub_lift, C.tySub_lift]
have hs : HEq (C.tmSub C.snd (C.comp (C.lift σ A) (C.lift τ (C.tySub A σ))))
(C.snd (A := C.tySub (C.tySub A σ) τ)) :=
(C.tmSub_comp C.snd (C.lift σ A) (C.lift τ (C.tySub A σ))).symm.trans
((C.tmSub_heq (C.tySub_lift σ A) (C.lift_snd σ A)
(C.lift τ (C.tySub A σ))).trans (C.lift_snd τ (C.tySub A σ)))
exact (C.tmSub_comp C.snd
(C.comp (C.lift σ A) (C.lift τ (C.tySub A σ))) (C.castExt hA.symm)).symm.trans
((C.tmSub_heq hTy hs (C.castExt hA.symm)).trans (C.castExt_snd hA.symm))
end CwF
namespace DependentProducts
variable {C : CwF.{u, v, w, t}} (P : DependentProducts C) (I : IdentityTypes C)
/-- Pointwise paths between dependent functions, as an internal dependent product. -/
def homotopyType {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) : C.Ty Γ :=
P.pi A (I.id B (P.unlam f) (P.unlam g))
theorem homotopyType_sub {Γ Δ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ) :
C.tySub (P.homotopyType I f g) σ = P.homotopyType I (P.sub f σ) (P.sub g σ) := by
simp only [homotopyType, P.pi_sub, I.id_sub, P.unlam_sub]
/-- Pointwise-path formation respects transport of a dependent function's domain and family. -/
theorem homotopyType_congr {Γ : C.Ctx} {A A' : C.Ty Γ}
{B : C.Ty (C.ext Γ A)} {B' : C.Ty (C.ext Γ A')}
(hA : A = A') (hB : C.tySub B (C.castExt hA.symm) = B')
{f g : C.Tm Γ (P.pi A B)} {f' g' : C.Tm Γ (P.pi A' B')}
(hf : HEq f f') (hg : HEq g g') : P.homotopyType I f g = P.homotopyType I f' g' := by
cases hA
simp only [CwF.castExt, C.tySub_id] at hB
cases hB
cases hf
cases hg
rfl
end DependentProducts
namespace InternalPath
variable {C : CwF.{u, v, w, t}}
(P : DependentProducts C) (I : IdentityTypes C) (J : IdentityElimination C I)
/-- The pointwise-path motive over a variable function endpoint. -/
def happlyEndpoint {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) : C.Ty (C.ext Γ (P.pi A B)) :=
P.homotopyType I (P.sub f C.fst) (C.castTm (P.pi_sub A B C.fst) C.snd)
theorem happlyEndpoint_sub {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) :
C.tySub (happlyEndpoint P I f) (C.termSub g) = P.homotopyType I f g := by
rw [happlyEndpoint, P.homotopyType_sub]
apply P.homotopyType_congr I (C.tySub_fst_termSub A g)
· rw [C.tySub_comp, C.tySub_comp, ← C.assoc,
C.lift_section C.fst (C.termSub g) (C.termSub_fst g) A
(C.tySub_fst_termSub A g), C.tySub_id]
· exact (P.sub_heq _ _).trans
((C.tmSub_heq (P.pi_sub A B C.fst).symm (P.sub_heq f C.fst) (C.termSub g)).trans
(C.tmSub_fst_termSub f g))
· exact (P.sub_heq _ _).trans
((C.tmSub_heq (P.pi_sub A B C.fst).symm (C.castTm_heq _ _) (C.termSub g)).trans
(C.termSub_snd g))
/-- The based identity-elimination motive defining canonical dependent happly. -/
def happlyMotive {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) : C.Ty (I.pathContext f) :=
C.tySub (happlyEndpoint P I f) C.fst
theorem happlyMotive_sub {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) (p : C.Tm Γ (I.id (P.pi A B) f g)) :
C.tySub (happlyMotive P I f) (I.pathSub f g p) = P.homotopyType I f g := by
calc
_ = C.tySub (happlyEndpoint P I f) (C.comp C.fst (I.pathSub f g p)) :=
C.tySub_comp _ _ _
_ = _ := by rw [I.pathSub_fst, happlyEndpoint_sub]
/-- Canonical dependent happly, derived by path induction into pointwise identity types. -/
def happlyTerm {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
{f g : C.Tm Γ (P.pi A B)} (p : C.Tm Γ (I.id (P.pi A B) f g)) :
C.Tm Γ (P.homotopyType I f g) :=
C.castTm (happlyMotive_sub P I f g p)
(J.elim f (happlyMotive P I f)
(C.castTm (happlyMotive_sub P I f f (I.refl f)).symm
(P.lam (I.refl (P.unlam f)))) g p)
theorem happlyTerm_refl {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f : C.Tm Γ (P.pi A B)) :
happlyTerm P I J (I.refl f) = P.lam (I.refl (P.unlam f)) := by
unfold happlyTerm
rw [J.beta]
apply eq_of_heq
exact (C.castTm_heq _ _).trans (C.castTm_heq _ _)
/-- The canonical happly as an internal function, obtained by contextual abstraction. -/
def happly (F : FunctionTypes C) {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) :
C.Tm Γ (F.arr (I.id (P.pi A B) f g) (P.homotopyType I f g)) :=
let pathSub : C.tySub (I.id (P.pi A B) f g) C.fst =
I.id (P.pi (C.tySub A C.fst) (C.tySub B (C.lift C.fst A)))
(P.sub f C.fst) (P.sub g C.fst) :=
(I.id_sub f g C.fst).trans
(I.id_congr (P.pi_sub A B C.fst) (P.sub_heq f C.fst).symm
(P.sub_heq g C.fst).symm)
F.lam (C.castTm (P.homotopyType_sub I f g C.fst).symm
(happlyTerm P I J (C.castTm pathSub C.snd)))
end InternalPath
/-- Function extensionality as stated in Section 2: the J-defined canonical
happly map is internally a half-adjoint equivalence. -/
structure FunctionExtensionality (C : CwF.{u, v, w, t}) (F : FunctionTypes C)
(P : DependentProducts C) (S : DependentSums C) (I : IdentityTypes C)
(J : IdentityElimination C I) where
isEquiv_happly : ∀ {Γ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)),
C.Tm Γ (InternalEquivalence.isEquiv F P I S J (InternalPath.happly P I J F f g))
namespace FunctionExtensionality
variable {C : CwF.{u, v, w, t}} {F : FunctionTypes C} {P : DependentProducts C}
{S : DependentSums C} {I : IdentityTypes C} {J : IdentityElimination C I}
(E : FunctionExtensionality C F P S I J)
/-- The inverse to canonical happly selected by the internal equivalence witness. -/
def funext {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) :
C.Tm Γ (F.arr (P.homotopyType I f g) (I.id (P.pi A B) f g)) :=
S.fst (E.isEquiv_happly f g)
/-- Function extensionality applied to an internal pointwise homotopy. -/
def funextApply {Γ : C.Ctx} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
{f g : C.Tm Γ (P.pi A B)} (h : C.Tm Γ (P.homotopyType I f g)) :
C.Tm Γ (I.id (P.pi A B) f g) := F.app (E.funext f g) h
end FunctionExtensionality
namespace IdentityTypes
variable {C : CwF.{u, v, w, t}} (I : IdentityTypes C)
/-- Based path families are stable under the lift of a context substitution. -/
theorem basedPath_lift {Γ Δ : C.Ctx} {A : C.Ty Γ}
(a : C.Tm Γ A) (σ : C.Sub Δ Γ) :
C.tySub (I.basedPath a) (C.lift σ A) = I.basedPath (C.tmSub a σ) := by
rw [basedPath, I.id_sub]
apply I.id_congr (C.tySub_lift σ A) ?_ (C.lift_snd σ A)
have h := C.tmSub_comp a C.fst (C.lift σ A)
rw [C.lift_fst] at h
exact h.trans (C.tmSub_comp a σ C.fst).symm
/-- Lift a context substitution through both an endpoint and its based path. -/
def pathLift {Γ Δ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) (σ : C.Sub Δ Γ) :
C.Sub (I.pathContext (C.tmSub a σ)) (I.pathContext a) :=
C.pair (C.comp (C.lift σ A) C.fst)
(C.castTm ((congrArg (fun T ↦ C.tySub T C.fst) (I.basedPath_lift a σ)).symm.trans
(C.tySub_comp (I.basedPath a) (C.lift σ A) C.fst)) C.snd)
theorem pathLift_fst {Γ Δ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) (σ : C.Sub Δ Γ) :
C.comp C.fst (I.pathLift a σ) = C.comp (C.lift σ A) C.fst := C.pair_fst _ _
end IdentityTypes
namespace InternalPath
variable {C : CwF.{u, v, w, t}} (I : IdentityTypes C) (J : IdentityElimination C I)
/-- The transport motive pulls a contextual family back along the endpoint projection. -/
def transportMotive {Γ : C.Ctx} {A : C.Ty Γ} (B : C.Ty (C.ext Γ A))
(a : C.Tm Γ A) : C.Ty (I.pathContext a) := C.tySub B C.fst
theorem transportMotive_sub {Γ : C.Ctx} {A : C.Ty Γ} (B : C.Ty (C.ext Γ A))
(a b : C.Tm Γ A) (p : C.Tm Γ (I.id A a b)) :
C.tySub (transportMotive I B a) (I.pathSub a b p) = C.tySub B (C.termSub b) := by
calc
_ = C.tySub B (C.comp C.fst (I.pathSub a b p)) := C.tySub_comp _ _ _
_ = _ := by rw [I.pathSub_fst]
/-- Internal dependent transport, constructed by the based identity eliminator. -/
def transport {Γ : C.Ctx} {A : C.Ty Γ} (B : C.Ty (C.ext Γ A))
{a b : C.Tm Γ A} (p : C.Tm Γ (I.id A a b))
(x : C.Tm Γ (C.tySub B (C.termSub a))) : C.Tm Γ (C.tySub B (C.termSub b)) :=
C.castTm (transportMotive_sub I B a b p)
(J.elim a (transportMotive I B a)
(C.castTm (transportMotive_sub I B a a (I.refl a)).symm x) b p)
theorem transport_refl {Γ : C.Ctx} {A : C.Ty Γ} (B : C.Ty (C.ext Γ A))
(a : C.Tm Γ A) (x : C.Tm Γ (C.tySub B (C.termSub a))) :
transport I J B (I.refl a) x = x := by
unfold transport
rw [J.beta]
apply eq_of_heq
exact (C.castTm_heq _ _).trans (C.castTm_heq _ _)
end InternalPath
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ParametricityV2 -/
/-!
# The source type expressions for the four parametricity axioms
All domains and codomains are literal contextual translations of Section 2.2.
The small family `B` is a term in `Γ, x : A, i : Size`; the interchange map below
puts it in `Γ, i : Size, x : A`. No arbitrary Lean family over decoded sizes or
elements is introduced.
This module forms the exact type expressions. The canonical arrows are defined
in the `Canonical*V2` modules and their half-adjoint equivalence axioms in
`ParametricityAxiomsV2`.
-/
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 Parametricity
variable {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S I)
(Q : UniversalSizeQuantifier C U I Z) (E : ExistentialSizeQuantifier C U I Z)
/-- Interchange an independent small variable and a size variable. -/
def interchange {Γ : C.Ctx} (A : U.Code Γ) :
C.Sub (C.ext (C.ext Γ (Z.type Γ)) (U.el (U.sub A C.fst)))
(C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A)))) :=
Z.extend (U.liftEl C.fst A) (Z.sub (Z.generic Γ) C.fst)
/-- Existential quantification bounded by an arbitrary contextual size term. -/
def boundedExAt {Γ : C.Ctx} (i : C.Tm Γ (Z.type Γ))
(B : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
E.code (K.sigma (Z.le (Z.succ (Z.generic Γ)) (Z.sub i C.fst)) (U.sub B C.fst))
/-- Left-hand side of `∃` parametric over `Π`. -/
def existsPiSource {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) : U.Code Γ :=
K.pi A (E.code B)
/-- Right-hand side of `∃` parametric over `Π`, with the source's essential
inner bounded existential. No monotonicity hypothesis is added. -/
def existsPiTarget {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) : U.Code Γ :=
E.code (K.pi (U.sub A C.fst)
(boundedExAt Z K E (Z.sub (Z.generic Γ) C.fst) (U.sub B (Z.lift (U.liftEl C.fst A)))))
/-- Left-hand side of `∀` parametric over `Σ`. -/
def allSigmaSource {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) : U.Code Γ :=
K.sigma A (Q.code B)
/-- Right-hand side of `∀` parametric over `Σ`. -/
def allSigmaTarget {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) : U.Code Γ :=
Q.code (K.sigma (U.sub A C.fst) (U.sub B (interchange Z A)))
/-- Domain of the right-to-left canonical map for `∃` parametric over `<`. -/
def existsLtSource {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
E.code (Z.diamond K E A)
/-- Codomain of that canonical map. -/
def existsLtTarget {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
E.code A
/-- Domain of the left-to-right canonical map for `∀` parametric over `<`. -/
def allLtSource {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
Q.code A
/-- Codomain of that canonical map. -/
def allLtTarget {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) : U.Code Γ :=
Q.code (Z.box K Q A)
end Parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_QuantifierNaturalityV2 -/
/-!
# Substitution of bounded size quantifiers
The source abbreviations `∀ j < i, A(j)` and `∃ j < i, A(j)` are stable under
substitution. Their stability is derived from the primitive constructor rules;
it is not an additional field imposed on the interpretation.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace SizeRules
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
theorem sub_comp {Γ Δ Θ : C.Ctx} (i : C.Tm Γ (Z.type Γ))
(σ : C.Sub Δ Γ) (τ : C.Sub Θ Δ) :
Z.sub (Z.sub i σ) τ = Z.sub i (C.comp σ τ) := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (Z.type_sub σ).symm (C.castTm_heq _ _) τ).trans
((C.tmSub_comp i σ τ).trans (C.castTm_heq _ _).symm))
theorem generic_sub_extend {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ)
(i : C.Tm Δ (Z.type Δ)) : Z.sub (Z.generic Γ) (Z.extend σ i) = i := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans
((C.tmSub_heq (Z.type_sub C.fst).symm (C.castTm_heq _ _) (Z.extend σ i)).trans
((C.pair_snd _ _).trans (C.castTm_heq _ _)))
theorem extend_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (i : C.Tm Δ (Z.type Δ)) :
C.comp C.fst (Z.extend σ i) = σ := C.pair_fst _ _
theorem sub_generic_heq {Γ Δ : C.Ctx} (σ : C.Sub Δ (C.ext Γ (Z.type Γ))) :
HEq (Z.sub (Z.generic Γ) σ) (C.tmSub C.snd σ) :=
(C.castTm_heq _ _).trans
(C.tmSub_heq (Z.type_sub C.fst).symm (C.castTm_heq _ _) σ)
/-- A substitution into a size extension is determined by its base and size component. -/
theorem hom_ext {Γ Δ : C.Ctx} {f g : C.Sub Δ (C.ext Γ (Z.type Γ))}
(hfst : C.comp C.fst f = C.comp C.fst g)
(hsnd : Z.sub (Z.generic Γ) f = Z.sub (Z.generic Γ) g) : f = g := by
let a := C.castTm (C.tySub_comp (Z.type Γ) C.fst g) (C.tmSub C.snd g)
have hf : f = C.pair (C.comp C.fst g) a :=
C.pair_unique _ _ _ hfst
((Z.sub_generic_heq f).symm.trans ((heq_of_eq hsnd).trans
((Z.sub_generic_heq g).trans (C.castTm_heq _ _).symm)))
have hg : g = C.pair (C.comp C.fst g) a :=
C.pair_unique _ _ _ rfl (C.castTm_heq _ _).symm
exact hf.trans hg.symm
theorem lift_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
C.comp C.fst (Z.lift σ) = C.comp σ C.fst := C.pair_fst _ _
theorem generic_sub_lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
Z.sub (Z.generic Γ) (Z.lift σ) = Z.generic Δ := Z.generic_sub_extend _ _
theorem inner_fst {Γ : C.Ctx} : C.comp C.fst (Z.inner (Γ := Γ)) = C.comp C.fst C.fst :=
C.pair_fst _ _
theorem generic_sub_inner {Γ : C.Ctx} :
Z.sub (Z.generic Γ) Z.inner = Z.generic (C.ext Γ (Z.type Γ)) :=
Z.generic_sub_extend _ _
/-- Selecting the inner size commutes with lifting a substitution through both size binders. -/
theorem inner_lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
C.comp (Z.inner (Γ := Γ)) (Z.lift (Z.lift σ)) =
C.comp (Z.lift σ) (Z.inner (Γ := Δ)) := by
apply Z.hom_ext
· calc
C.comp C.fst (C.comp Z.inner (Z.lift (Z.lift σ))) =
C.comp (C.comp C.fst C.fst) (Z.lift (Z.lift σ)) := by
rw [← C.assoc, Z.inner_fst]
_ = C.comp C.fst (C.comp (Z.lift σ) C.fst) := by
rw [C.assoc, Z.lift_fst]
_ = C.comp (C.comp σ C.fst) C.fst := by rw [← C.assoc, Z.lift_fst]
_ = C.comp (C.comp C.fst (Z.lift σ)) Z.inner := by
simp only [Z.lift_fst, C.assoc, Z.inner_fst]
_ = C.comp C.fst (C.comp (Z.lift σ) Z.inner) := C.assoc _ _ _
· rw [← Z.sub_comp, Z.generic_sub_inner, Z.generic_sub_lift,
← Z.sub_comp, Z.generic_sub_lift, Z.generic_sub_inner]
theorem outer_sub_lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
Z.sub (Z.sub (Z.generic Γ) C.fst) (Z.lift (Z.lift σ)) =
Z.sub (Z.generic Δ) C.fst := by
rw [Z.sub_comp, Z.lift_fst, ← Z.sub_comp, Z.generic_sub_lift]
/-- The source predicate `j < i` commutes with substitution under both size binders. -/
theorem boundCode_sub (ZS : SizeSubstitution U I Z) {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
U.sub (Z.boundCode (Γ := Γ)) (Z.lift (Z.lift σ)) = Z.boundCode (Γ := Δ) := by
simp only [boundCode, ZS.le_sub, ZS.succ_sub, Z.generic_sub_lift, Z.outer_sub_lift]
end SizeRules
namespace Universe
variable {C : CwF.{u, v, w, t}} (U : Universe C)
theorem liftElAs_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) (B : U.Code Δ)
(h : U.sub A σ = B) :
C.comp C.fst (U.liftElAs σ A B h) = C.comp σ C.fst := by
subst B
exact C.pair_fst _ _
end Universe
namespace SmallTypeConstructors
variable {C : CwF.{u, v, w, t}} {U : Universe C} {P : DependentProducts C}
{S : DependentSums C} {I : IdentityTypes C} (K : SmallTypeConstructors C U P S I)
theorem pi_sub_as (KS : SmallTypeSubstitution U P S I K) {Γ Δ : C.Ctx}
(A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) (σ : C.Sub Δ Γ)
(A' : U.Code Δ) (h : U.sub A σ = A') :
U.sub (K.pi A B) σ = K.pi A' (U.sub B (U.liftElAs σ A A' h)) := by
subst A'
exact KS.pi_sub A B σ
theorem sigma_sub_as (KS : SmallTypeSubstitution U P S I K) {Γ Δ : C.Ctx}
(A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) (σ : C.Sub Δ Γ)
(A' : U.Code Δ) (h : U.sub A σ = A') :
U.sub (K.sigma A B) σ = K.sigma A' (U.sub B (U.liftElAs σ A A' h)) := by
subst A'
exact KS.sigma_sub A B σ
end SmallTypeConstructors
namespace SizeRules
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
/-- The family under the bound-proof binder has the expected substitution. -/
theorem boundedFamily_sub (ZS : SizeSubstitution U I Z) {Γ Δ : C.Ctx}
(A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
U.sub (U.sub (U.sub A Z.inner) C.fst)
(U.liftElAs (Z.lift (Z.lift σ)) Z.boundCode Z.boundCode (Z.boundCode_sub ZS σ)) =
U.sub (U.sub (U.sub A (Z.lift σ)) Z.inner) C.fst := by
rw [U.sub_comp, U.liftElAs_fst]
rw [← U.sub_comp]
rw [U.sub_comp A, Z.inner_lift, ← U.sub_comp]
/-- Bounded universal quantification commutes with substitution of its free context. -/
theorem box_sub {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S 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}
(A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
U.sub (Z.box K Q A) (Z.lift σ) = Z.box K Q (U.sub A (Z.lift σ)) := by
unfold box
rw [QS.code_sub]
rw [K.pi_sub_as KS _ _ _ _ (Z.boundCode_sub ZS σ), Z.boundedFamily_sub ZS]
/-- Bounded existential quantification commutes with substitution of its free context. -/
theorem diamond_sub {P : DependentProducts C} {S : DependentSums C}
(K : SmallTypeConstructors C U P S I) (E : ExistentialSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(ES : ExistentialSizeSubstitution U I Z E) {Γ Δ : C.Ctx}
(A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
U.sub (Z.diamond K E A) (Z.lift σ) = Z.diamond K E (U.sub A (Z.lift σ)) := by
unfold diamond
rw [ES.code_sub]
rw [K.sigma_sub_as KS _ _ _ _ (Z.boundCode_sub ZS σ), Z.boundedFamily_sub ZS]
end SizeRules
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ContextInterchangeV2 -/
/-! Interchange of an independent small variable and a size variable. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace CwF
variable (C : CwF.{u, v, w, t})
/-- A map into a context extension is determined by its two components. -/
theorem sub_ext {Γ Δ : C.Ctx} {A : C.Ty Γ} {f g : C.Sub Δ (C.ext Γ A)}
(hfst : C.comp C.fst f = C.comp C.fst g)
(hsnd : HEq (C.tmSub C.snd f) (C.tmSub C.snd g)) : f = g := by
let a := C.castTm (C.tySub_comp A C.fst g) (C.tmSub C.snd g)
have hf : f = C.pair (C.comp C.fst g) a :=
C.pair_unique _ _ _ hfst (hsnd.trans (C.castTm_heq _ _).symm)
have hg : g = C.pair (C.comp C.fst g) a :=
C.pair_unique _ _ _ rfl (C.castTm_heq _ _).symm
exact hf.trans hg.symm
end CwF
namespace Universe
variable {C : CwF.{u, v, w, t}} (U : Universe C)
theorem liftEl_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) :
C.comp C.fst (U.liftEl σ A) = C.comp σ C.fst := C.pair_fst _ _
theorem liftEl_snd {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) :
HEq (C.tmSub C.snd (U.liftEl σ A)) (C.snd (Γ := Δ) (A := U.el (U.sub A σ))) :=
(C.pair_snd _ _).trans (C.castTm_heq _ _)
/-- Lifting through an equal presentation of a decoded code preserves the variable. -/
theorem liftElAs_snd {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ)
(B : U.Code Δ) (h : U.sub A σ = B) :
HEq (C.tmSub C.snd (U.liftElAs σ A B h)) (C.snd (Γ := Δ) (A := U.el B)) := by
subst B
exact U.liftEl_snd σ A
theorem liftEl_snd_type {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : U.Code Γ) :
C.tySub (C.tySub (U.el A) C.fst) (U.liftEl σ A) =
C.tySub (U.el (U.sub A σ)) C.fst := by
rw [C.tySub_comp, U.liftEl_fst, ← C.tySub_comp, U.el_sub]
rfl
end Universe
namespace SizeRules
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
theorem sub_id {Γ : C.Ctx} (i : C.Tm Γ (Z.type Γ)) : Z.sub i C.id = i := by
apply eq_of_heq
exact (C.castTm_heq _ _).trans (C.tmSub_id i)
end SizeRules
namespace Parametricity
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
/-- Forget the small variable while retaining the last size. -/
def interchangeSizeMap {Γ : C.Ctx} (A : U.Code Γ) :
C.Sub (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))
(C.ext Γ (Z.type Γ)) :=
Z.extend (C.comp C.fst C.fst) (Z.generic (C.ext Γ (U.el A)))
theorem interchangeInverseType {Γ : C.Ctx} (A : U.Code Γ) :
C.tySub (U.el (U.sub A C.fst)) (interchangeSizeMap Z A) =
C.tySub (C.tySub (U.el A) C.fst) C.fst := by
calc
_ = C.tySub (C.tySub (U.el A) C.fst) (interchangeSizeMap Z A) :=
congrArg (fun T => C.tySub T (interchangeSizeMap Z A)) (U.el_sub A C.fst).symm
_ = C.tySub (U.el A) (C.comp C.fst (interchangeSizeMap Z A)) := C.tySub_comp _ _ _
_ = C.tySub (U.el A) (C.comp C.fst C.fst) := by rw [interchangeSizeMap, Z.extend_fst]
_ = _ := (C.tySub_comp _ _ _).symm
/-- The inverse swap from `Γ, x : A, i : Size` to `Γ, i : Size, x : A`. -/
def interchangeInverse {Γ : C.Ctx} (A : U.Code Γ) :
C.Sub (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))
(C.ext (C.ext Γ (Z.type Γ)) (U.el (U.sub A C.fst))) :=
C.pair (interchangeSizeMap Z A)
(C.castTm (interchangeInverseType Z A).symm (C.tmSub C.snd C.fst))
theorem interchangeInverse_fst {Γ : C.Ctx} (A : U.Code Γ) :
C.comp C.fst (interchangeInverse Z A) = interchangeSizeMap Z A := C.pair_fst _ _
theorem interchangeInverse_snd {Γ : C.Ctx} (A : U.Code Γ) :
HEq (C.tmSub C.snd (interchangeInverse Z A))
(C.tmSub (C.snd (A := U.el A)) (C.fst (A := Z.type (C.ext Γ (U.el A))))) :=
(C.pair_snd _ _).trans (C.castTm_heq _ _)
theorem interchangeInverse_snd_type {Γ : C.Ctx} (A : U.Code Γ) :
C.tySub (C.tySub (U.el (U.sub A C.fst)) C.fst) (interchangeInverse Z A) =
C.tySub (C.tySub (U.el A) C.fst) C.fst := by
rw [C.tySub_comp, interchangeInverse_fst]
exact interchangeInverseType Z A
theorem interchange_fst {Γ : C.Ctx} (A : U.Code Γ) :
C.comp C.fst (interchange Z A) = U.liftEl C.fst A := Z.extend_fst _ _
theorem generic_sub_interchange {Γ : C.Ctx} (A : U.Code Γ) :
Z.sub (Z.generic (C.ext Γ (U.el A))) (interchange Z A) =
Z.sub (Z.generic Γ) C.fst := Z.generic_sub_extend _ _
/-- Recover the original small variable after swapping it past the size. -/
theorem interchange_liftEl_inverse {Γ : C.Ctx} (A : U.Code Γ) :
C.comp (U.liftEl C.fst A) (interchangeInverse Z A) = C.fst := by
apply C.sub_ext
· rw [← C.assoc, U.liftEl_fst, C.assoc, interchangeInverse_fst,
interchangeSizeMap, Z.extend_fst]
· exact (C.tmSub_comp C.snd (U.liftEl C.fst A) (interchangeInverse Z A)).symm.trans
((C.tmSub_heq (U.liftEl_snd_type C.fst A) (U.liftEl_snd C.fst A)
(interchangeInverse Z A)).trans (interchangeInverse_snd Z A))
/-- Recover the original size after swapping it past the small variable. -/
theorem interchangeSizeMap_interchange {Γ : C.Ctx} (A : U.Code Γ) :
C.comp (interchangeSizeMap Z A) (interchange Z A) = C.fst := by
apply Z.hom_ext
· rw [← C.assoc, interchangeSizeMap, Z.extend_fst, C.assoc,
interchange_fst, U.liftEl_fst]
· rw [← Z.sub_comp, interchangeSizeMap, Z.generic_sub_extend, generic_sub_interchange]
/-- Swapping to size-first order and back is the identity substitution. -/
theorem interchange_inverse {Γ : C.Ctx} (A : U.Code Γ) :
C.comp (interchange Z A) (interchangeInverse Z A) = C.id := by
apply Z.hom_ext
· rw [← C.assoc, interchange_fst, interchange_liftEl_inverse, C.comp_id]
· rw [← Z.sub_comp, generic_sub_interchange, Z.sub_comp, interchangeInverse_fst,
interchangeSizeMap, Z.generic_sub_extend, Z.sub_id]
/-- Swapping to small-variable-first order and back is the identity substitution. -/
theorem inverse_interchange {Γ : C.Ctx} (A : U.Code Γ) :
C.comp (interchangeInverse Z A) (interchange Z A) = C.id := by
apply C.sub_ext
· rw [← C.assoc, interchangeInverse_fst, interchangeSizeMap_interchange, C.comp_id]
· have hmid := C.tmSub_comp (C.snd (A := U.el A)) C.fst (interchange Z A)
rw [interchange_fst] at hmid
exact (C.tmSub_comp C.snd (interchangeInverse Z A) (interchange Z A)).symm.trans
((C.tmSub_heq (interchangeInverse_snd_type Z A) (interchangeInverse_snd Z A)
(interchange Z A)).trans
(hmid.trans ((U.liftEl_snd C.fst A).trans (C.tmSub_id C.snd).symm)))
end Parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ContextualSumsV2 -/
/-!
# Context substitutions extracting dependent pairs
These substitutions are derived from the source's dependent-sum projections.
They expose the two components in a context and preserve the original context.
They are useful when constructing the canonical parametricity maps.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace DependentSums
variable {C : CwF.{u, v, w, t}} (S : DependentSums C)
/-- The generic dependent pair, transported through sigma-type substitution. -/
def generic {Γ : C.Ctx} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) :
C.Tm (C.ext Γ (S.sigma A B))
(S.sigma (C.tySub A C.fst) (C.tySub B (C.lift C.fst A))) :=
C.castTm (S.sigma_sub A B C.fst) C.snd
/-- Replace one dependent-pair variable by its first and second projections. -/
def split {Γ : C.Ctx} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) :
C.Sub (C.ext Γ (S.sigma A B)) (C.ext (C.ext Γ A) B) :=
C.pair (C.pair C.fst (S.fst (S.generic A B)))
(C.castTm ((C.tySub_comp B (C.lift C.fst A) (C.termSub (S.fst (S.generic A B)))).trans
(congrArg (C.tySub B) (C.lift_termSub C.fst A (S.fst (S.generic A B)))))
(S.snd (S.generic A B)))
/-- Extracting the components of a pair preserves the preceding context. -/
theorem split_base {Γ : C.Ctx} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A)) :
C.comp (C.comp C.fst C.fst) (S.split A B) = C.fst := by
rw [C.assoc, split, C.pair_fst, C.pair_fst]
end DependentSums
namespace SmallTypeConstructors
variable {C : CwF.{u, v, w, t}} {U : Universe C} {P : DependentProducts C}
{S : DependentSums C} {I : IdentityTypes C} (K : SmallTypeConstructors C U P S I)
/-- Extract the components of a decoded small dependent pair. -/
def sigmaSplit {Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) :
C.Sub (C.ext Γ (U.el (K.sigma A B))) (C.ext (C.ext Γ (U.el A)) (U.el B)) :=
C.comp (S.split (U.el A) (U.el B)) (C.castExt (K.el_sigma A B))
/-- Extracting a small dependent pair preserves the original context. -/
theorem sigmaSplit_base {Γ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A))) :
C.comp (C.comp C.fst C.fst) (K.sigmaSplit A B) = C.fst := by
rw [sigmaSplit, ← C.assoc, S.split_base, C.castExt_fst]
/-- Discard the first component of a small nondependent pair. This is a
contextual term derived from the small sigma decoding and projections. -/
def forgetFirst (F : FunctionTypes C) {Γ : C.Ctx} (A B : U.Code Γ) :
C.Tm Γ (F.arr (U.el (K.sigma A (U.sub B C.fst))) (U.el B)) := by
let σ := K.sigmaSplit A (U.sub B C.fst)
have h : C.tySub (C.tySub (U.el (U.sub B C.fst)) C.fst) σ =
C.tySub (U.el B) C.fst := by
calc
_ = C.tySub (C.tySub (C.tySub (U.el B) C.fst) C.fst) σ :=
congrArg (fun X => C.tySub (C.tySub X C.fst) σ) (U.el_sub B C.fst).symm
_ = C.tySub (U.el B) (C.comp (C.comp C.fst C.fst) σ) := by
rw [C.tySub_comp, C.tySub_comp, C.assoc]
_ = _ := congrArg (C.tySub (U.el B)) (K.sigmaSplit_base A (U.sub B C.fst))
exact F.lam (C.castTm h (C.tmSub C.snd σ))
/-- Introduce a small dependent pair after any substitution of its parameter
context. This is the ordinary sigma constructor with explicit type transports. -/
def sigmaPairAt {Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (a : C.Tm Δ (C.tySub (U.el A) σ))
(b : C.Tm Δ (C.tySub (U.el B) (C.pair σ a))) :
C.Tm Δ (C.tySub (U.el (K.sigma A B)) σ) :=
C.castTm (congrArg (fun X => C.tySub X σ) (K.el_sigma A B).symm)
(C.castTm (S.sigma_sub (U.el A) (U.el B) σ).symm
(S.pair a (C.castTm
((C.tySub_comp (U.el B) (C.lift σ (U.el A)) (C.termSub a)).trans
(congrArg (C.tySub (U.el B)) (C.lift_termSub σ (U.el A) a))).symm b)))
/-- Apply an internal arrow to the second component of a small product. -/
def productMap (F : FunctionTypes C) {Γ : C.Ctx} (R A B : U.Code Γ)
(f : C.Tm Γ (F.arr (U.el A) (U.el B))) :
C.Tm Γ (F.arr (U.el (K.sigma R (U.sub A C.fst)))
(U.el (K.sigma R (U.sub B C.fst)))) := by
let p₀ := @C.fst Γ (U.el R)
let p₁ := @C.fst (C.ext Γ (U.el R)) (U.el (U.sub A p₀))
let τ := C.comp p₀ p₁
let r := C.castTm (C.tySub_comp (U.el R) p₀ p₁) (C.tmSub C.snd p₁)
have pair_eq : C.pair τ r = p₁ :=
(C.pair_unique τ r p₁ rfl (C.castTm_heq _ _).symm).symm
have hA : C.tySub (U.el (U.sub A p₀)) p₁ = C.tySub (U.el A) τ :=
(congrArg (fun X => C.tySub X p₁) (U.el_sub A p₀).symm).trans (C.tySub_comp _ _ _)
let a := C.castTm hA C.snd
let b := F.app (F.sub f τ) a
have hB : C.tySub (U.el (U.sub B p₀)) (C.pair τ r) = C.tySub (U.el B) τ :=
(congrArg (C.tySub (U.el (U.sub B p₀))) pair_eq).trans
((congrArg (fun X => C.tySub X p₁) (U.el_sub B p₀).symm).trans (C.tySub_comp _ _ _))
let output := K.sigmaPairAt R (U.sub B p₀) τ r (C.castTm hB.symm b)
let ρ := K.sigmaSplit R (U.sub A p₀)
have hout : C.tySub (C.tySub (U.el (K.sigma R (U.sub B p₀))) τ) ρ =
C.tySub (U.el (K.sigma R (U.sub B p₀))) C.fst :=
(C.tySub_comp _ τ ρ).trans
(congrArg (C.tySub (U.el (K.sigma R (U.sub B p₀)))) (K.sigmaSplit_base R (U.sub A p₀)))
exact F.lam (C.castTm hout (C.tmSub output ρ))
end SmallTypeConstructors
namespace ExistentialSizeQuantifier
variable {C : CwF.{u, v, w, t}} {U : Universe C} {I : IdentityTypes C}
{Z : SizeRules C U I} (E : ExistentialSizeQuantifier C U I Z)
/-- Introduce an existential after a contextual substitution supplying its size.
The second component is a contextual term, with no added tracking premise. -/
def pairAt {Γ Δ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ)))
(σ : C.Sub Δ (C.ext Γ (Z.type Γ))) (a : C.Tm Δ (C.tySub (U.el A) σ)) :
C.Tm Δ (C.tySub (U.el (E.code A)) (C.comp C.fst σ)) :=
C.castTm ((C.tySub_comp (U.el (E.code A)) (C.comp C.fst C.fst) (C.pair σ a)).trans
(congrArg (C.tySub (U.el (E.code A))) (by rw [C.assoc, C.pair_fst])))
(C.tmSub (E.pair A) (C.pair σ a))
end ExistentialSizeQuantifier
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_CanonicalAllSigmaV2 -/
/-!
# The canonical map for universal size quantification over dependent sums
The source map sends `(a, f)` to `λ i, (a, f i)`. It is constructed from
dependent-sum projections and universal introduction; invertibility is a
separate parametricity principle.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace Parametricity
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)
(QS : UniversalSizeSubstitution U I Z Q)
/-- The exact canonical left-to-right map in `∀` parametric over `Σ`:
`(a, f) ↦ λ i, (a, f i)`. -/
def allSigmaMap {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) :
C.Tm Γ (F.arr (U.el (allSigmaSource Z K Q A B))
(U.el (allSigmaTarget Z K Q A B))) := by
let pA := @C.fst Γ (U.el A)
let ph := @C.fst (C.ext Γ (U.el A)) (U.el (Q.code B))
let σ := C.comp pA ph
let σsize := Z.lift σ
let ρ := C.comp (interchangeInverse Z A) (Z.lift ph)
have hρ : C.comp C.fst ρ = σsize := by
dsimp [ρ, σsize]
rw [← C.assoc, interchangeInverse_fst]
apply Z.hom_ext
· rw [← C.assoc, interchangeSizeMap, Z.extend_fst, C.assoc,
Z.lift_fst, Z.lift_fst, ← C.assoc]
· rw [← Z.sub_comp, interchangeSizeMap, Z.generic_sub_extend,
Z.generic_sub_lift, Z.generic_sub_lift]
let a := C.castTm ((C.tySub_comp (U.el (U.sub A C.fst)) C.fst ρ).trans
(congrArg (C.tySub (U.el (U.sub A C.fst))) hρ)) (C.tmSub C.snd ρ)
have hpair : C.pair σsize a = ρ :=
(C.pair_unique σsize a ρ hρ (C.castTm_heq _ _).symm).symm
have hswap : C.comp (interchange Z A) (C.pair σsize a) = Z.lift ph := by
rw [hpair]
dsimp [ρ]
rw [← C.assoc, interchange_inverse, C.id_comp]
have hin : C.tySub (U.el (Q.code B)) ph = U.el (Q.code (U.sub B (Z.lift ph))) :=
(U.el_sub (Q.code B) ph).trans (congrArg U.el (QS.code_sub B ph))
let value := Q.unlam (C.castTm hin C.snd)
have hvalue : U.el (U.sub B (Z.lift ph)) =
C.tySub (U.el (U.sub B (interchange Z A))) (C.pair σsize a) := by
exact (U.el_sub B (Z.lift ph)).symm.trans
((congrArg (C.tySub (U.el B)) hswap.symm).trans
((C.tySub_comp (U.el B) (interchange Z A) (C.pair σsize a)).symm.trans
(congrArg (fun X => C.tySub X (C.pair σsize a))
(U.el_sub B (interchange Z A)))))
let D := K.sigma (U.sub A C.fst) (U.sub B (interchange Z A))
let body := K.sigmaPairAt (U.sub A C.fst) (U.sub B (interchange Z A))
σsize a (C.castTm hvalue value)
let quantified := Q.lam (C.castTm (U.el_sub D σsize) body)
have hout : C.tySub (U.el (Q.code D)) σ = U.el (Q.code (U.sub D σsize)) :=
(U.el_sub (Q.code D) σ).trans (congrArg U.el (QS.code_sub D σ))
let branch := C.castTm hout.symm quantified
let split := K.sigmaSplit A (Q.code B)
have hbase : C.tySub (C.tySub (U.el (Q.code D)) σ) split =
C.tySub (U.el (Q.code D)) C.fst := by
rw [C.tySub_comp]
exact congrArg (C.tySub (U.el (Q.code D))) (K.sigmaSplit_base A (Q.code B))
exact F.lam (C.castTm hbase (C.tmSub branch split))
end Parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_CanonicalParametricityV2 -/
/-!
# Canonical maps appearing in the parametricity axioms
The arrows in this file are constructed from the source type formers. They are
not supplied as extra hypotheses and their invertibility is not assumed here.
-/
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 Parametricity
variable (Z : SizeRules C U I) (F : FunctionTypes C)
(K : SmallTypeConstructors C U P S I) (E : ExistentialSizeQuantifier C U I Z)
/-- The source map `∃ j < i, A(j) → ∃ j, A(j)`, in the context of a size `i`.
It eliminates the existential and forgets the order-proof component of its pair. -/
def boundedToExists {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) :
C.Tm (C.ext Γ (Z.type Γ))
(F.arr (U.el (Z.diamond K E A)) (U.el (U.sub (E.code A) C.fst))) := by
let D := K.sigma Z.boundCode (U.sub (U.sub A Z.inner) C.fst)
let p₀ := @C.fst Γ (Z.type Γ)
let p₁ := @C.fst (C.ext Γ (Z.type Γ)) (Z.type (C.ext Γ (Z.type Γ)))
let p₂ := @C.fst _ (U.el D)
let payload := F.app (F.sub (K.forgetFirst F Z.boundCode (U.sub A Z.inner)) p₂) C.snd
have hp : C.tySub (U.el (U.sub A Z.inner)) p₂ =
C.tySub (U.el A) (C.comp Z.inner p₂) :=
(congrArg (fun X => C.tySub X p₂) (U.el_sub A Z.inner).symm).trans
(C.tySub_comp (U.el A) Z.inner p₂)
let output := E.pairAt A (C.comp Z.inner p₂) (C.castTm hp payload)
have hbase : C.comp p₀ (C.comp Z.inner p₂) = C.comp p₀ (C.comp p₁ p₂) := by
dsimp [p₀, p₁]
rw [← C.assoc, SizeRules.inner, SizeRules.extend, C.pair_fst, C.assoc]
have hout : C.tySub (U.el (E.code A)) (C.comp p₀ (C.comp Z.inner p₂)) =
C.tySub (U.el (U.sub (E.code A) p₀)) (C.comp p₁ p₂) := by
calc
_ = C.tySub (U.el (E.code A)) (C.comp p₀ (C.comp p₁ p₂)) :=
congrArg (C.tySub (U.el (E.code A))) hbase
_ = C.tySub (C.tySub (U.el (E.code A)) p₀) (C.comp p₁ p₂) :=
(C.tySub_comp _ _ _).symm
_ = _ := congrArg (fun X => C.tySub X (C.comp p₁ p₂)) (U.el_sub (E.code A) p₀)
exact E.recursor F D (U.sub (E.code A) p₀) (C.castTm hout output)
/-- The same bounded-existential elimination with an arbitrary contextual bound. -/
def boundedAtToExists {Γ : C.Ctx} (i : C.Tm Γ (Z.type Γ))
(A : U.Code (C.ext Γ (Z.type Γ))) :
C.Tm Γ (F.arr (U.el (boundedExAt Z K E i A)) (U.el (E.code A))) := by
let R := Z.le (Z.succ (Z.generic Γ)) (Z.sub i C.fst)
let D := K.sigma R (U.sub A C.fst)
let π := @C.fst (C.ext Γ (Z.type Γ)) (U.el D)
let payload := F.app (F.sub (K.forgetFirst F R A) π) C.snd
exact E.recursor F D (E.code A) (E.pairAt A π payload)
/-- The exact canonical right-to-left map in `∃` parametric over `<`:
`⟨i, ⟨j, p, a⟩⟩ ↦ ⟨j, a⟩`. -/
def existsLtMap {Γ : C.Ctx} (A : U.Code (C.ext Γ (Z.type Γ))) :
C.Tm Γ (F.arr (U.el (existsLtSource Z K E A)) (U.el (existsLtTarget Z E A))) := by
let p₀ := @C.fst Γ (Z.type Γ)
let p₁ := @C.fst (C.ext Γ (Z.type Γ)) (U.el (Z.diamond K E A))
let branch := F.app (F.sub (boundedToExists Z F K E A) p₁) C.snd
have h : C.tySub (U.el (U.sub (E.code A) p₀)) p₁ =
C.tySub (U.el (E.code A)) (C.comp p₀ p₁) :=
(congrArg (fun X => C.tySub X p₁) (U.el_sub (E.code A) p₀).symm).trans
(C.tySub_comp _ p₀ p₁)
exact E.recursor F (Z.diamond K E A) (E.code A) (C.castTm h branch)
/-- The exact canonical left-to-right map in `∀` parametric over `<`:
`f ↦ λ i, λ j < i, f j`. Substitution stability used to abstract its argument
is proved from the source's primitive substitution rules. -/
def allLtMap (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 Γ))) :
C.Tm Γ (F.arr (U.el (allLtSource Z Q A)) (U.el (allLtTarget Z K Q A))) := 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 (Z.box K Q A))) σ =
U.el (Q.code (Z.box K Q (U.sub A (Z.lift σ)))) :=
(U.el_sub (Q.code (Z.box K Q A)) σ).trans
((congrArg U.el (QS.code_sub (Z.box K Q A) σ)).trans
(congrArg (fun B => U.el (Q.code B)) (Z.box_sub K Q ZS KS QS A σ)))
exact F.lam (C.castTm hout.symm (Z.forallBound K Q (C.castTm hin C.snd)))
end Parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ContextualProductsV2 -/
/-!
# Small dependent-function rules after contextual substitution
The two operations here are source lambda abstraction and application, with the
universe decoding and context-lifting transports written explicitly.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace SmallTypeConstructors
variable {C : CwF.{u, v, w, t}} {U : Universe C} {P : DependentProducts C}
{S : DependentSums C} {I : IdentityTypes C} (K : SmallTypeConstructors C U P S I)
/-- The small code for a nondependent function type. -/
def arrow {Γ : C.Ctx} (A B : U.Code Γ) : U.Code Γ :=
K.pi A (U.sub B C.fst)
/-- Decoding the small arrow gives the source's nondependent function type. -/
theorem el_arrow {F : FunctionTypes C} (FP : FunctionProductCompatibility F P)
{Γ : C.Ctx} (A B : U.Code Γ) : U.el (K.arrow A B) = F.arr (U.el A) (U.el B) :=
(K.el_pi A (U.sub B C.fst)).trans
((congrArg (P.pi (U.el A)) (U.el_sub B C.fst).symm).trans (FP.arr_eq _ _).symm)
/-- Small arrow codes commute with contextual substitution. -/
theorem arrow_sub (KS : SmallTypeSubstitution U P S I K)
{Γ Δ : C.Ctx} (A B : U.Code Γ) (σ : C.Sub Δ Γ) :
U.sub (K.arrow A B) σ = K.arrow (U.sub A σ) (U.sub B σ) := by
have h : U.sub (U.sub B C.fst) (U.liftEl σ A) = U.sub (U.sub B σ) C.fst := by
rw [U.sub_comp, U.sub_comp]
exact congrArg (U.sub B) (C.pair_fst _ _)
exact (KS.pi_sub A (U.sub B C.fst) σ).trans (congrArg (K.pi (U.sub A σ)) h)
/-- The ordinary postcomposition operation on decoded small arrows. -/
def postcompose (F : FunctionTypes C) (FP : FunctionProductCompatibility F P)
{Γ : C.Ctx} (R A B : U.Code Γ) (f : C.Tm Γ (F.arr (U.el A) (U.el B))) :
C.Tm Γ (F.arr (U.el (K.arrow R A)) (U.el (K.arrow R B))) := by
let σ := @C.fst Γ (U.el (K.arrow R A))
let h := C.castTm ((congrArg (fun X => C.tySub X σ) (K.el_arrow FP R A)).trans
(F.arr_sub (U.el R) (U.el A) σ)) C.snd
let output := F.compose (F.sub f σ) h
exact F.lam (C.castTm
((congrArg (fun X => C.tySub X σ) (K.el_arrow FP R B)).trans
(F.arr_sub (U.el R) (U.el B) σ)).symm output)
/-- Introduce a decoded small dependent function after a substitution. -/
def piAbsAt {Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ)
(b : C.Tm (C.ext Δ (C.tySub (U.el A) σ)) (C.tySub (U.el B) (C.lift σ (U.el A)))) :
C.Tm Δ (C.tySub (U.el (K.pi A B)) σ) :=
C.castTm (congrArg (fun X => C.tySub X σ) (K.el_pi A B).symm)
(C.castTm (P.pi_sub (U.el A) (U.el B) σ).symm (P.lam b))
/-- Apply a decoded small dependent function after a substitution. -/
def piAppAt {Γ Δ : C.Ctx} (A : U.Code Γ) (B : U.Code (C.ext Γ (U.el A)))
(σ : C.Sub Δ Γ) (f : C.Tm Δ (C.tySub (U.el (K.pi A B)) σ))
(a : C.Tm Δ (C.tySub (U.el A) σ)) :
C.Tm Δ (C.tySub (U.el B) (C.pair σ a)) :=
C.castTm ((C.tySub_comp (U.el B) (C.lift σ (U.el A)) (C.termSub a)).trans
(congrArg (C.tySub (U.el B)) (C.lift_termSub σ (U.el A) a)))
(C.tmSub (P.unlam (C.castTm (P.pi_sub (U.el A) (U.el B) σ)
(C.castTm (congrArg (fun X => C.tySub X σ) (K.el_pi A B)) f))) (C.termSub a))
end SmallTypeConstructors
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_CanonicalExistsPiV2 -/
/-!
# The canonical map for existential quantification and dependent products
The map sends `⟨i, f⟩` to `λ x, let ⟨j, p, b⟩ := f x; ⟨j, b⟩`.
Its construction uses the small existential eliminator and the ordinary small
dependent-function rules. Its invertibility remains a source axiom, not a fact
assumed in this definition.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace Parametricity
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) (E : ExistentialSizeQuantifier C U I Z)
(ES : ExistentialSizeSubstitution U I Z E)
/-- The size-indexed family under the outer existential in the source's
`∃`-over-`Π` axiom. -/
def existsPiFiber {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) :
U.Code (C.ext Γ (Z.type Γ)) :=
K.pi (U.sub A C.fst)
(boundedExAt Z K E (Z.sub (Z.generic Γ) C.fst) (U.sub B (Z.lift (U.liftEl C.fst A))))
/-- The branch of the outer existential eliminator in the canonical map. -/
def existsPiBranch {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) :
C.Tm (C.ext (C.ext Γ (Z.type Γ)) (U.el (existsPiFiber Z K E A B)))
(C.tySub (U.el (existsPiSource Z K E A B)) (C.comp C.fst C.fst)) := by
let p₀ := @C.fst Γ (Z.type Γ)
let Ai := U.sub A p₀
let xMap := U.liftEl p₀ A
let B' := U.sub B (Z.lift xMap)
let i := Z.sub (Z.generic Γ) (@C.fst (C.ext Γ (Z.type Γ)) (U.el Ai))
let Bi := boundedExAt Z K E i B'
let T := K.pi Ai Bi
let pf := @C.fst (C.ext Γ (Z.type Γ)) (U.el T)
let σ := C.comp p₀ pf
let px := @C.fst (C.ext (C.ext Γ (Z.type Γ)) (U.el T)) (C.tySub (U.el A) σ)
let inputSub := C.comp pf px
have hx : C.tySub (U.el Ai) inputSub = C.tySub (C.tySub (U.el A) σ) px := by
calc
_ = C.tySub (C.tySub (U.el A) p₀) inputSub :=
congrArg (fun X => C.tySub X inputSub) (U.el_sub A p₀).symm
_ = C.tySub (U.el A) (C.comp p₀ inputSub) := C.tySub_comp _ _ _
_ = C.tySub (U.el A) (C.comp σ px) := congrArg (C.tySub (U.el A)) (C.assoc p₀ pf px).symm
_ = _ := (C.tySub_comp _ _ _).symm
let x := C.castTm hx.symm C.snd
let f := C.castTm (C.tySub_comp (U.el T) pf px) (C.tmSub C.snd px)
let b := K.piAppAt Ai Bi inputSub f x
let ρ := C.pair inputSub x
let output := F.app (F.sub (boundedAtToExists Z F K E i B') ρ) b
have hρ : C.comp xMap ρ = C.lift σ (U.el A) := by
apply C.sub_ext
· change C.comp C.fst (C.comp (U.liftEl p₀ A) (C.pair inputSub x)) =
C.comp C.fst (C.lift σ (U.el A))
rw [← C.assoc, U.liftEl_fst, C.assoc, C.pair_fst, C.lift_fst]
exact (C.assoc p₀ pf px).symm
· exact (C.tmSub_comp C.snd xMap ρ).symm.trans
((C.tmSub_heq (U.liftEl_snd_type p₀ A) (U.liftEl_snd p₀ A) ρ).trans
((C.pair_snd inputSub x).trans
((C.castTm_heq hx.symm C.snd).trans (C.lift_snd σ (U.el A)).symm)))
have he : C.tySub (U.el (E.code B)) xMap = U.el (E.code B') :=
(U.el_sub (E.code B) xMap).trans (congrArg U.el (ES.code_sub B xMap))
have hout : C.tySub (U.el (E.code B')) ρ = C.tySub (U.el (E.code B)) (C.lift σ (U.el A)) :=
(congrArg (fun X => C.tySub X ρ) he.symm).trans
((C.tySub_comp (U.el (E.code B)) xMap ρ).trans
(congrArg (C.tySub (U.el (E.code B))) hρ))
exact K.piAbsAt A (E.code B) σ (C.castTm hout output)
/-- The exact canonical right-to-left arrow in `∃` parametric over `Π`. -/
def existsPiMap {Γ : C.Ctx} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) :
C.Tm Γ (F.arr (U.el (existsPiTarget Z K E A B)) (U.el (existsPiSource Z K E A B))) :=
E.recursor F (existsPiFiber Z K E A B) (existsPiSource Z K E A B)
(existsPiBranch Z F K E ES A B)
end Parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TheorySubstitutionV2 -/
/-!
# Substitution of identity elimination
The source explicitly assumes substitution admissible for every judgment.
This interface states its instance for `J`, using the actual based path-context
lift constructed from the CwF rules. The motive is reindexed along that lift;
there is no independent semantic operation hidden in this condition.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
/-- Identity elimination commutes with contextual substitution. The transported
reflexivity branch is explicit so that no equality of internal paths is imposed. -/
structure IdentityEliminationSubstitution (I : IdentityTypes C) (J : IdentityElimination C I) where
elim_sub : ∀ {Γ Δ} {A : C.Ty Γ} (a : C.Tm Γ A) (M : C.Ty (I.pathContext a))
(d : C.Tm Γ (C.tySub M (I.pathSub a a (I.refl a))))
(b : C.Tm Γ A) (p : C.Tm Γ (I.id A a b)) (σ : C.Sub Δ Γ)
(d' : C.Tm Δ (C.tySub (C.tySub M (I.pathLift a σ))
(I.pathSub (C.tmSub a σ) (C.tmSub a σ) (I.refl (C.tmSub a σ))))),
HEq (C.tmSub d σ) d' →
HEq (C.tmSub (J.elim a M d b p) σ)
(J.elim (C.tmSub a σ) (C.tySub M (I.pathLift a σ)) d' (C.tmSub b σ)
(C.castTm (I.id_sub a b σ) (C.tmSub p σ)))
/-- The function-extensionality axiom schema is stable under substitution.
The canonical map remains the one constructed by identity elimination. -/
structure FunctionExtensionalitySubstitution (F : FunctionTypes C)
(P : DependentProducts C) (S : DependentSums C) (I : IdentityTypes C)
(J : IdentityElimination C I) (E : FunctionExtensionality C F P S I J) where
isEquiv_sub : ∀ {Γ Δ} {A : C.Ty Γ} {B : C.Ty (C.ext Γ A)}
(f g : C.Tm Γ (P.pi A B)) (σ : C.Sub Δ Γ),
HEq (C.tmSub (E.isEquiv_happly f g) σ)
(E.isEquiv_happly (P.sub f σ) (P.sub g σ))
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_RecursionNaturalityV2 -/
/-! Substitution of the large size-recursion types and its internal solution type. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace CwF
variable (C : CwF.{u,v,w,t})
/-- Lift under a type binder, using an explicitly equal presentation of its substitution. -/
def liftAs {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) (A' : C.Ty Δ)
(h : C.tySub A σ = A') : C.Sub (C.ext Δ A') (C.ext Γ A) :=
h ▸ C.lift σ A
theorem liftAs_fst {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) (A' : C.Ty Δ)
(h : C.tySub A σ = A') : C.comp C.fst (C.liftAs σ A A' h) = C.comp σ C.fst := by
subst A'
exact C.pair_fst _ _
theorem liftAs_snd {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) (A : C.Ty Γ) (A' : C.Ty Δ)
(h : C.tySub A σ = A') : HEq (C.tmSub C.snd (C.liftAs σ A A' h))
(@C.snd Δ A') := by
subst A'
exact (C.pair_snd _ _).trans (C.castTm_heq _ _)
end CwF
namespace DependentProducts
variable {C : CwF.{u,v,w,t}} (P : DependentProducts C)
theorem pi_sub_as {Γ Δ : C.Ctx} (A : C.Ty Γ) (B : C.Ty (C.ext Γ A))
(σ : C.Sub Δ Γ) (A' : C.Ty Δ) (h : C.tySub A σ = A') :
C.tySub (P.pi A B) σ = P.pi A' (C.tySub B (C.liftAs σ A A' h)) := by
subst A'
exact P.pi_sub A B σ
end DependentProducts
namespace SizeRules
variable {C : CwF.{u,v,w,t}} {U : Universe C} {I : IdentityTypes C}
(Z : SizeRules C U I)
theorem liftAs_eq_lift {Γ Δ : C.Ctx} (σ : C.Sub Δ Γ) :
C.liftAs σ (Z.type Γ) (Z.type Δ) (Z.type_sub σ) = Z.lift σ := by
apply Z.hom_ext
· exact (C.liftAs_fst _ _ _ _).trans (Z.lift_fst σ).symm
· rw [Z.generic_sub_lift]
apply eq_of_heq
exact (Z.sub_generic_heq _).trans ((C.liftAs_snd _ _ _ _).trans (C.castTm_heq _ _).symm)
theorem pi_sub (P : DependentProducts C) {Γ Δ : C.Ctx}
(A : C.Ty (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
C.tySub (P.pi (Z.type Γ) A) σ = P.pi (Z.type Δ) (C.tySub A (Z.lift σ)) := by
rw [P.pi_sub_as _ _ _ _ (Z.type_sub σ), Z.liftAs_eq_lift]
theorem bounded_sub (P : DependentProducts C) (F : FunctionTypes C)
(ZS : SizeSubstitution U I Z) {Γ Δ : C.Ctx}
(A : C.Ty (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
C.tySub (Z.bounded P F A) (Z.lift σ) = Z.bounded P F (C.tySub A (Z.lift σ)) := by
unfold bounded
rw [Z.pi_sub, F.arr_sub]
apply congrArg (P.pi _)
apply congrArg₂ F.arr
· change C.tySub (U.el Z.boundCode) (Z.lift (Z.lift σ)) = U.el Z.boundCode
exact (U.el_sub _ _).trans (congrArg U.el (Z.boundCode_sub ZS σ))
· rw [C.tySub_comp, Z.inner_lift, ← C.tySub_comp]
theorem step_sub (P : DependentProducts C) (F : FunctionTypes C)
(ZS : SizeSubstitution U I Z) {Γ Δ : C.Ctx}
(A : C.Ty (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ) :
C.tySub (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A)) σ =
P.pi (Z.type Δ) (F.arr (Z.bounded P F (C.tySub A (Z.lift σ)))
(C.tySub A (Z.lift σ))) := by
rw [Z.pi_sub, F.arr_sub, Z.bounded_sub P F ZS]
/-- The internal pointwise unfolding equation for a candidate size-recursive function. -/
def fixedPointEquation (P : DependentProducts C) (F : FunctionTypes C)
{Γ : C.Ctx} (A : C.Ty (C.ext Γ (Z.type Γ)))
(f : C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A)))
(h : C.Tm Γ (P.pi (Z.type Γ) A)) : C.Ty Γ :=
P.pi (Z.type Γ) (I.id A (P.unlam h) (F.app (P.unlam f) (Z.restrict P F h)))
/-- The precise internal solution type of Lemma 1, including its equality witness.
Contractibility of this type is a theorem, not an assumption of size recursion. -/
def fixedPointSolutions (P : DependentProducts C) (F : FunctionTypes C)
(S : DependentSums C) (ZS : SizeSubstitution U I Z)
{Γ : C.Ctx} (A : C.Ty (C.ext Γ (Z.type Γ)))
(f : C.Tm Γ (P.pi (Z.type Γ) (F.arr (Z.bounded P F A) A))) : C.Ty Γ :=
let σ := @C.fst Γ (P.pi (Z.type Γ) A)
S.sigma (P.pi (Z.type Γ) A)
(Z.fixedPointEquation P F (C.tySub A (Z.lift σ))
(C.castTm (Z.step_sub P F ZS A σ) (C.tmSub f σ))
(C.castTm (Z.pi_sub P A σ) C.snd))
end SizeRules
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TheoryPackageV2 -/
/-! The complete source rule package, before adding the four parametricity axioms. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
/-- A contextual interpretation of Section 2 before the parametricity axioms.
Every field is a primitive source rule or its substitution stability. In
particular, neither uniqueness of fixpoints nor algebra initiality is assumed. -/
structure CoreTheory (C : CwF.{u,v,w,t}) where
functions : FunctionTypes C
products : DependentProducts C
functionProducts : FunctionProductCompatibility functions products
sums : DependentSums C
sumSubstitution : DependentSumSubstitution sums
identities : IdentityTypes C
identityElimination : IdentityElimination C identities
identitySubstitution : IdentityEliminationSubstitution identities identityElimination
univ : Universe C
small : SmallTypeConstructors C univ products sums identities
smallSubstitution : SmallTypeSubstitution univ products sums identities small
base : BaseTypes univ
baseSubstitution : BaseTypeSubstitution univ base
size : SizeRules C univ identities
sizeSubstitution : SizeSubstitution univ identities size
recursion : SizeRecursion C univ identities size products functions
recursionSubstitution : SizeRecursionSubstitution univ identities size products functions recursion
all : UniversalSizeQuantifier C univ identities size
allSubstitution : UniversalSizeSubstitution univ identities size all
ex : ExistentialSizeQuantifier C univ identities size
exSubstitution : ExistentialSizeSubstitution univ identities size ex
exTermSubstitution : ExistentialTermSubstitution univ identities size ex exSubstitution
funext : FunctionExtensionality C functions products sums identities identityElimination
funextSubstitution : FunctionExtensionalitySubstitution functions products sums identities
identityElimination funext
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TheoryPathOperationsV2 -/
/-! Internal path operations derived from the identity eliminator. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory.InternalPath
universe u v w t
variable {C : CwF.{u, v, w, t}} (I : IdentityTypes C) (J : IdentityElimination C I)
def reverseFamily {Γ : C.Ctx} {A : C.Ty Γ} (a : C.Tm Γ A) : C.Ty (C.ext Γ A) :=
I.id (C.tySub A C.fst) C.snd (C.tmSub a C.fst)
theorem reverseFamily_sub {Γ : C.Ctx} {A : C.Ty Γ} (a b : C.Tm Γ A) :
C.tySub (reverseFamily I a) (C.termSub b) = I.id A b a := by
rw [reverseFamily, I.id_sub]
exact I.id_congr (C.tySub_fst_termSub A b)
(C.termSub_snd b) (C.tmSub_fst_termSub a b)
/-- Reverse an internal path using dependent transport, hence the source J rule. -/
def symm {Γ : C.Ctx} {A : C.Ty Γ} {a b : C.Tm Γ A}
(p : C.Tm Γ (I.id A a b)) : C.Tm Γ (I.id A b a) :=
C.castTm (reverseFamily_sub I a b)
(transport I J (reverseFamily I a) p
(C.castTm (reverseFamily_sub I a a).symm (I.refl a)))
end LaarakkerOttenVanDenBerg2026.V2.Theory.InternalPath
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ParametricityAxiomsV2 -/
/-!
# The four source parametricity axioms
Each axiom asserts that the source's exact canonical map is a half-adjoint
equivalence. All four maps are constructed in preceding modules. Their inverses,
homotopies, and coherence are encoded internally by `isEquiv`; no metatheoretic
equivalence or merely existential map is substituted for the source statement.
-/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
variable {C : CwF.{u, v, w, t}}
/-- The four equivalence axioms of Section 2.2, on their canonical arrows. -/
structure ParametricityAxioms (F : FunctionTypes C) (P : DependentProducts C)
(S : DependentSums C) (I : IdentityTypes C) (J : IdentityElimination C I)
(U : Universe C) (K : SmallTypeConstructors C U P S I) (Z : SizeRules C U I)
(E : ExistentialSizeQuantifier C U I Z) (Q : UniversalSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q) (ES : ExistentialSizeSubstitution U I Z E) where
existsPi : ∀ {Γ} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))),
C.Tm Γ (InternalEquivalence.isEquiv F P I S J (Parametricity.existsPiMap Z F K E ES A B))
allSigma : ∀ {Γ} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))),
C.Tm Γ (InternalEquivalence.isEquiv F P I S J (Parametricity.allSigmaMap Z F K Q QS A B))
existsLt : ∀ {Γ} (A : U.Code (C.ext Γ (Z.type Γ))),
C.Tm Γ (InternalEquivalence.isEquiv F P I S J (Parametricity.existsLtMap Z F K E A))
allLt : ∀ {Γ} (A : U.Code (C.ext Γ (Z.type Γ))),
C.Tm Γ (InternalEquivalence.isEquiv F P I S J (Parametricity.allLtMap Z F K Q ZS KS QS A))
/-- Structural substitution for the four source axiom schemas. These equations
only express substitution of their proof terms; they do not add any equivalence
or encoding conclusion beyond the source's four axioms. -/
structure ParametricitySubstitution (F : FunctionTypes C) (P : DependentProducts C)
(S : DependentSums C) (I : IdentityTypes C) (J : IdentityElimination C I)
(U : Universe C) (K : SmallTypeConstructors C U P S I) (Z : SizeRules C U I)
(E : ExistentialSizeQuantifier C U I Z) (Q : UniversalSizeQuantifier C U I Z)
(ZS : SizeSubstitution U I Z) (KS : SmallTypeSubstitution U P S I K)
(QS : UniversalSizeSubstitution U I Z Q) (ES : ExistentialSizeSubstitution U I Z E)
(Axioms : ParametricityAxioms F P S I J U K Z E Q ZS KS QS ES) where
existsPi_sub : ∀ {Γ Δ} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Axioms.existsPi A B) σ)
(Axioms.existsPi (U.sub A σ) (U.sub B (Z.lift (U.liftEl σ A))))
allSigma_sub : ∀ {Γ Δ} (A : U.Code Γ)
(B : U.Code (C.ext (C.ext Γ (U.el A)) (Z.type (C.ext Γ (U.el A))))) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Axioms.allSigma A B) σ)
(Axioms.allSigma (U.sub A σ) (U.sub B (Z.lift (U.liftEl σ A))))
existsLt_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Axioms.existsLt A) σ) (Axioms.existsLt (U.sub A (Z.lift σ)))
allLt_sub : ∀ {Γ Δ} (A : U.Code (C.ext Γ (Z.type Γ))) (σ : C.Sub Δ Γ),
HEq (C.tmSub (Axioms.allLt A) σ) (Axioms.allLt (U.sub A (Z.lift σ)))
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_ParametricTheoryV2 -/
/-! The full source theory: the contextual core plus exactly four parametricity axioms. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
/-- Section 2 and Appendix A, with all operations acting on contextual terms.
Realizers, trackers, external function introduction, identity reflection, and
uniqueness of fixpoints are not fields of this theory. -/
structure ParametricTheory (C : CwF.{u,v,w,t}) extends CoreTheory C where
parametricity : ParametricityAxioms functions products sums identities identityElimination
univ small size ex all sizeSubstitution smallSubstitution allSubstitution exSubstitution
parametricitySubstitution : ParametricitySubstitution functions products sums identities
identityElimination univ small size ex all sizeSubstitution smallSubstitution
allSubstitution exSubstitution parametricity
end LaarakkerOttenVanDenBerg2026.V2.Theory
/- Module: Definitions.Def_LaarakkerOttenVanDenBerg2026_TheoryConsequencesV2 -/
/-! Source conclusions used as open mission targets. These are predicates,
not fields of the primitive type theory and not assumed proof results. -/
namespace LaarakkerOttenVanDenBerg2026.V2.Theory
universe u v w t
namespace CoreTheory
variable {C : CwF.{u,v,w,t}} (T : CoreTheory C)
/-- An internal half-adjoint equivalence between two contextual types. -/
abbrev HasTypeEquivalence {Γ : C.Ctx} (A B : C.Ty Γ) : Prop :=
Nonempty (C.Tm Γ (InternalEquivalence.equivalence T.functions T.products
T.identities T.sums T.identityElimination A B))
/-- Proposition 2: dependent products commute with universal size quantification,
and dependent sums commute with existential size quantification. -/
def DefinableQuantifierEquivalences : Prop :=
∀ (Γ : C.Ctx) (A : T.univ.Code Γ)
(B : T.univ.Code (C.ext (C.ext Γ (T.univ.el A))
(T.size.type (C.ext Γ (T.univ.el A))))),
T.HasTypeEquivalence
(T.univ.el (T.small.pi A (T.all.code B)))
(T.univ.el (T.all.code
(T.small.pi (T.univ.sub A C.fst)
(T.univ.sub B (Parametricity.interchange T.size A))))) ∧
T.HasTypeEquivalence
(T.univ.el (T.small.sigma A (T.ex.code B)))
(T.univ.el (T.ex.code
(T.small.sigma (T.univ.sub A C.fst)
(T.univ.sub B (Parametricity.interchange T.size A)))))
/-- Proposition 3: quantifying a size-independent small type returns an
internally equivalent type. Dependence on the ambient context remains allowed. -/
def ConstantQuantifierEquivalences : Prop :=
∀ (Γ : C.Ctx) (A : T.univ.Code Γ),
T.HasTypeEquivalence (T.univ.el (T.ex.code (T.univ.sub A
(@C.fst Γ (T.size.type Γ))))) (T.univ.el A) ∧
T.HasTypeEquivalence (T.univ.el (T.all.code (T.univ.sub A
(@C.fst Γ (T.size.type Γ))))) (T.univ.el A)
/-- Semantic consistency means there is no closed term of the chosen empty type. -/
def IsConsistent : Prop :=
¬ Nonempty (C.Tm C.empty (T.univ.el T.base.empty))
end CoreTheory
end LaarakkerOttenVanDenBerg2026.V2.Theory
Read-back
What the Lean code literally says, in plain math · Codex / GPT-6 (independent fresh-context read-back)
Independent literal read-back
Input: Definitions/Def_LaarakkerOttenVanDenBerg2026_TheoryRevision2.lean (2,454 lines).
SHA256: d3fa3c4567a0c8574ca523a6420469ba5d6ff7d5cbcffb943b6735d5a5013ce1.
Method: static reading of this Lean file using mission_auditor.md. No informal mathematical source, previous read-back, review report, or implementation-agent guidance was consulted. The workspace contributor manual was also read as required by the user; it supplied no mathematical interpretation. Comments claiming a relationship to an informal source are not premises of this read-back. No compilation or source comparison is claimed.
All declaration names below are relative to LaarakkerOttenVanDenBerg2026.V2.Theory. Universes are arbitrary. Common notation is fixed as follows: is the specified category-with-families structure; is context extension, its first projection and its last variable; and denote type and term substitution; is context pairing; includes the required external type transport; and is the lift under . The symbols denote, respectively, the supplied function, dependent-product, dependent-sum, identity, identity-elimination, universe, small-constructor, size, universal-size, and existential-size structures. Each occurrence presupposes exactly such a supplied structure on the same , with the dependencies specified in its paragraph. Write for decoding a universe code, for 's type, and . Thus “” below abbreviates the internal type , not a metatheoretic strict-order proposition. and denote the decoded small quantifier codes of and . Internal use (and their small codes use ); uses . These symbols are not identifications with all external functions, sets, or propositions. An unqualified equality is external Lean equality; denotes external heterogeneous equality, including across different term carriers. Neither is an internal identity witness. Every reindexing displayed below includes the type transports written in the code.
CwF. This structure supplies a type of contexts in universe , a type of substitutions in universe for every pair of contexts, identities and composition with left/right identity and associativity equalities; a type of types over every context in universe , and a type of terms for each such type in universe ; type and term substitution along every substitution; external identity/composition equalities for type substitution and heterogeneous identity/composition equalities for term substitution; a context , a substitution from every context to it, and equality of every substitution into it with this chosen one; context extension , projection , and generic term ; and pairing for every and . Pairing satisfies and , and every map into with these two components equals that pairing. No external nonemptiness of arbitrary type or term carriers, distinctness of contexts/types, or interpretation of terms as functions is required.
CwF.castTm. For any , context , types over it, external equality , and term , this transports along to a term of .
CwF.termSub. For any , context , type , and term , this is the substitution pairing the identity with transported to using the inverse type-substitution identity equality.
CwF.lift. For any , contexts , substitution , and type over , this gives by pairing with the generic variable transported from to .
CwF.termSub_fst. For any and term , the section satisfies .
CwF.castTm_heq. For any , types , equality , and term , transport of along is heterogeneously equal to .
CwF.tmSub_heq. For any , contexts , types over , terms , external equality , heterogeneous equality , and substitution , the substituted terms satisfy .
CwF.termSub_snd. For any and , substituting into the generic variable gives .
CwF.tySub_fst_termSub. For any , types over and , weakening through and then substituting gives the external equality .
CwF.tmSub_fst_termSub. For any , types , terms , weakening through and then substituting gives .
FunctionTypes. Given , this supplies for every context and pair of types, stable under every substitution; abstraction of a contextual term in ; application for and ; the heterogeneous computation equality ; the external equality , using the weakened and transported ; equality of substituted application with application of the substituted arguments; and abstraction stability: for every and contextual term of the substituted weakened codomain, if , then the transported substitution of equals . Abstraction accepts contextual terms, not arbitrary external functions.
FunctionTypes.sub. For any , contexts , types over , arrow term , and , this is transported to using function-type substitution.
FunctionTypes.identity. For any and type , this defines the term by abstraction of the generic variable of .
FunctionTypes.compose. For any , types , terms and , this defines a term by contextual abstraction of , with both functions weakened to .
DependentProducts. Given , this supplies a type for every context, type , and contextual type over ; its substitution equality ; mutually inverse abstraction and generic evaluation between terms of in and terms of in , with both inverse laws external equalities; and equality of transported substituted abstraction with abstraction of the body substituted along . The inverse generic evaluation is a contextual operation, not a primitive external function evaluator.
DependentSums. Given , this supplies for every contextual type and family over , with the analogous substitution equality under lifted substitutions; pairing of and ; first projection in and second projection in ; external first-projection computation, heterogeneous second-projection computation, and external equality of a pair reconstructed from both projections with the original pair. Substitution laws for these term operations are not fields of this structure.
IdentityTypes. Given , this supplies a contextual type for every and two terms , a term in , an external equality identifying substituted identity types with identity types of substituted endpoints, and heterogeneous equality identifying substituted reflexivity with reflexivity of the substituted endpoint. It supplies neither identity elimination nor a conversion from internal identity terms to external endpoint equality.
IdentityTypes.id_congr. For any , types , equality , pairs and , and heterogeneous equalities , , the identity types and are externally equal.
IdentityTypes.basedPath. For any and , this is the type over , expressing an internal path from the weakened fixed endpoint to the variable endpoint.
IdentityTypes.pathContext. For any and , this is the double extension , with weakening of and understood.
IdentityTypes.basedPath_sub. For any and , substituting into the based-path family for yields the external type equality .
IdentityTypes.pathSub. For any , terms , and internal identity term , this gives by pairing with transported using the based-path substitution equality.
IdentityElimination. Given , this supplies the following operation for every context, , fixed term , and contextual motive over the endpoint-and-path context of : a term of at gives, for every and , a term of at . At its result equals externally. The motive is a contextual type. Substitution stability is not a field here.
Universe. Given , this supplies a type in every context, an external equality for every , and decoding of every term into a type over ; decoding commutes by external equality with substitution of the code, transported to . No injectivity, surjectivity, hierarchy, or strict size comparison is required.
Universe.Code. For any and context , a code is exactly a term of in .
Universe.sub. For any , code in and , code substitution is ordinary term substitution transported along .
Universe.generic. For any , this is the generic variable of , transported to a code in that extended context using stability of the universe type.
Universe.extend. For any , and code in , this is a map pairing with transported to .
Universe.sub_comp. For any , code in , substitutions and , successive code substitution equals substitution along externally.
Universe.generic_sub_extend. For any , and code in , substituting the extension by into the generic universe code of gives exactly .
Universe.extend_fst. For any , and code in , projecting the universe extension of by recovers .
SmallTypeConstructors. Given , this supplies, in every context, a product code and sum code from a code and a code family over , and an identity code from and terms . Their decodings equal, respectively, , , and externally. There are no substitution equations for these code constructors in this structure.
SizeRules. Given , this supplies a substitution-stable contextual type , a term in every context, an operation on its terms, and a universe code for every pair of size terms. It supplies terms of , , and for every ; an operation composing any terms of and into one of ; and an internal identity term between any two terms of any . No antisymmetry, strictness of successor, absence of cycles, well-foundedness, or external proof irrelevance is specified by these fields.
SizeRules.sub. For any , size term in and substitution , this is transported along the external stability equality for the size type.
SizeRules.generic. For any , this is the generic variable of transported to the size type of that extended context.
SizeRules.extend. For any , substitution and size term in , this gives by pairing with after the inverse size-type stability transport.
SizeRules.bound. For any , this is the decoded type in the context , using the newest size for and the weakened earlier size for .
SizeRules.inner. For any , this is the substitution retaining the base context and the newest size, built by size extension over the double projection.
SizeRules.bounded. For any , context and arbitrary type family over , this is the type over , using the inner-size substitution to pull back . The family need not be universe-coded.
SizeRules.restrict. For any , contextual type family and term in , this constructs a term of in by two contextual abstractions, with body independent of the bound-proof variable.
SizeRecursion. Given , this supplies, for every context, arbitrary type family , and term , a chosen term . It also supplies a term of . This is an internal pointwise unfolding witness, not an external equality of terms, and no uniqueness of or of the witness is included.
UniversalSizeQuantifier. Given , this supplies a code in each context for every code family over its size extension. It supplies abstraction from contextual terms of over that extension and a generic evaluation in the opposite direction, with both composites equal to the identity externally. The resulting quantified type is a decoded universe code even though the indexing size type is only a contextual type. No substitution fields occur here.
ExistentialSizeQuantifier. Given , this supplies an existential code for each code family; a generic pair term in of the existential type pulled back from ; and dependent elimination into any code over . A branch over of the motive pulled back along the generic-pair substitution yields a contextual term of over , whose substitution along the generic pair equals the branch externally. No existential eta law, large-motive elimination, or term substitution stability is included here.
contractible. For any , context and type , this defines the contextual type , with all occurrences of and weakened to their required contexts. It does not assert that this type has a term.
FunctionProductCompatibility. Given , this supplies, for every context and types , external equality , and, for every contextual body , heterogeneous equality between its -abstraction and -abstraction.
DependentSumSubstitution. Given , this requires for every , , and family over : substituted pairing is heterogeneously equal to pairing with any term of the appropriately substituted fiber for which ; first projection of a substituted and transported sum term equals the substituted first projection externally; and second projection of that term is heterogeneously equal to the substituted second projection. The pairing clause quantifies over , , and every such and is conditional on the displayed heterogeneous equality.
BaseTypes. Given , this supplies codes named empty, unit, and bool in every context, plus a term star of decoded unit and terms false and true of decoded bool. All three codes are externally stable under code substitution, and all three terms are heterogeneously stable under term substitution. For every contextual type motive over the decoded empty type it supplies a contextual term of that motive; for every motive over unit and term at star it supplies a contextual term of the motive whose specialization at star equals the supplied term; for every motive over bool and branches at false and true it supplies a contextual term computing externally to the corresponding branch at each constructor. The motives may be arbitrary contextual types. The fields do not assert that decoded empty has no closed terms, that false and true differ, or that the three codes are distinct.
SizeRules.lift. For any and , this is the map obtained by extending by the generic size of ; write it .
SizeSubstitution. Given , this requires, for every context substitution, external preservation of zero, successor, and the comparison code; heterogeneous preservation of the supplied zero-bound, successor-bound, and reflexivity terms; heterogeneous preservation of transitivity applied to and , conditional on chosen reindexed being heterogeneously equal to ; and heterogeneous preservation of the internal proof-irrelevance witness for , conditional on the same property for chosen . All source size terms and all target witnesses of the stated reindexed types are universally quantified.
SizeRecursionSubstitution. Given and recursion operations , this has two fields, for every contextual family , recursive-step term , substitution , and target recursive-step term for : if , then the substituted chosen fixed point is heterogeneously equal to , and the substituted chosen pointwise unfolding witness is heterogeneously equal to . These are conditional term-coherence requirements, not additional fixed-point uniqueness.
UniversalSizeSubstitution. Given , this requires external equality for every code family and substitution; heterogeneous equality between substituted universal abstraction and abstraction of the body reindexed along and decoding-transported; and, for every quantified term and target term with , heterogeneous equality between generic evaluation of reindexed along and generic evaluation of .
ExistentialSizeSubstitution. Given , this requires, for every code family over and , the external code equality .
Universe.liftEl. For any , code in and , this constructs by pairing with the generic term transported using decoding stability and type-substitution composition. Write this lift .
Universe.liftElAs. For any , , source code , target code , and external equality , this transports to a map with domain exactly .
BaseTypeSubstitution. Given and base-type operations , this requires naturality of each eliminator under every , using the decoded-code lifts with targets identified by the respective code-stability equalities. The empty eliminator after substitution equals the eliminator of the substituted arbitrary motive. For every unit motive and branch , and every appropriately typed target branch with , the substituted unit eliminator equals the target eliminator with . The boolean clause likewise quantifies over a motive, both source branches , both target branches , and heterogeneous equality of each substituted branch, and concludes external equality of the two eliminator terms.
ExistentialTermSubstitution. Given and existential code-substitution law , this requires heterogeneous equality of the generic pair after lifting any through the size binder and decoded family with the generic pair for . For every code motive over the original existential, branch , substitution , and branch of the reindexed motive over the new pair context, it also requires: if reindexed along that size-and-family lift is heterogeneously equal to , then the original eliminator reindexed along the existential-code lift is heterogeneously equal to elimination for , the reindexed motive, and . The existential-code lift uses to identify its target code.
SmallTypeSubstitution. Given , this supplies external substitution equalities for the small product and sum codes, reindexing the domain code along and the family along , for every code , family , and substitution. It also supplies external stability of the small identity code for every , using reindexed endpoints transported along decoding stability.
SizeRules.boundCode. For any , this is the universe code over the two-size context, whose decoding is .
SizeRules.diamond. Given and any code family over , this is the code over for , where the family is pulled back by the inner-size map and then weakened through the bound-proof binder.
SizeRules.box. Given and any code family , this is the code over for , with the same inner-size and proof-binder pullbacks.
SizeRules.forallBound. Given , a code family and a term in , this constructs a term of by two universal abstractions and a small dependent-product abstraction, with body obtained by generic evaluation of at , independent of and .
ExistentialSizeQuantifier.pairSub. Given and code family , this maps to by pairing the double projection with the generic existential-pair term.
ExistentialSizeQuantifier.recursor. Given , code family , code in , and contextual branch of the pullback of to , this constructs an arrow term . It uses the existential dependent eliminator with the weakened code as motive and then arrow abstraction, transporting the branch and result along the displayed external equalities. There is no analogous construction here for an arbitrary uncoded target type.
FunctionTypes.sub_heq. For any , contextual types , arrow term , and substitution , the transported arrow substitution is heterogeneously equal to ordinary term substitution .
FunctionTypes.sub_comp_heq. For any , types over , , and composable , , successive transported arrow substitutions are heterogeneously equal to transported substitution along .
FunctionTypes.app_congr. For any , types , external equalities and , terms , , , , and heterogeneous equalities , , their applications satisfy .
IdentityTypes.pathSub_fst. For any , endpoints , and , projecting the path-context substitution at recovers .
InternalPath.apEndpoint. Given , types over , and , this is the contextual type over .
InternalPath.apEndpoint_sub. For any , and , specializing the preceding endpoint family at yields the external type equality .
InternalPath.apMotive. For any , and , this pulls the endpoint family back to the based path context of along its projection, so its motive ignores the path variable.
InternalPath.apMotive_sub. For any , , , and , the preceding motive specialized along the path substitution equals externally.
InternalPath.ap. Given , contextual types , , endpoints , and internal path , this constructs by with motive and reflexivity branch at , with external transports to the displayed type.
InternalPath.ap_refl. For any , and , the constructed action on reflexivity satisfies the external term equality .
InternalEquivalence.homotopyBody. Given , contextual types , and , this is the type over .
InternalEquivalence.homotopyType. Given , contextual types , and , this defines as an internal dependent product, not an external assertion for all elements of a metatheoretic set.
InternalEquivalence.homotopyBody_sub. Given , types over , , , any and in , substitution of into the homotopy body equals externally, using transported function substitutions.
InternalEquivalence.homotopyAt. Given , over , a term , any , and , this constructs a term of by substituting into generic evaluation of and transporting its type.
InternalEquivalence.homotopyType_sub. For any , contextual , and , externally, where function substitutions include their type transports.
InternalEquivalence.homotopySub. Given , contextual , a term and substitution , this transports to a term of using the preceding type equality.
InternalEquivalence.coherenceType. Given , contextual types , terms , , and , this is . The two compared objects are internal paths, their equality is another internal identity type, and the action on paths is the operation derived from the supplied .
InternalEquivalence.isEquiv. Given , contextual types and an arrow term , this defines the nested internal sum of an inverse , a homotopy , a homotopy , and a coherence term . Each later summand is formed in the context extended by the earlier chosen data, using the explicit homotopy and function substitution transports. This is a contextual type; it neither asserts inhabitance nor discards the coherence term.
InternalEquivalence.equivalence. Given , context and types , this defines the internal type , where the second component consists of an inverse, both inverse homotopies, and the internal path coherence just described. The generic forward map is transported through arrow-type substitution before forming that component.
CwF.tySub_fst_pair. For any , types over , substitution and term , weakening through then substituting gives externally.
CwF.pair_fst_snd. For any and type , pairing the projection and generic variable of is the identity substitution on .
CwF.pair_comp. For any , type over , , , and , the composite equals , with the latter term transported from to .
CwF.lift_fst. For any , and type over , .
CwF.lift_snd. For any , and type , the original generic variable substituted along is heterogeneously equal to the generic variable of .
CwF.castExt. For any , types and external equality , this transports an identity substitution to a substitution .
CwF.castExt_fst. For any and equality , projecting after that context transport equals projection from .
CwF.castExt_snd. For any and equality , the generic variable of reindexed along context transport is heterogeneously equal to the generic variable of .
CwF.lift_termSub. For any , , type over and , .
DependentProducts.sub. Given , type over , family over , and , this transports ordinary to a term of .
DependentProducts.sub_heq. For any of the preceding kinds, the transported dependent-product substitution is heterogeneously equal to ordinary term substitution .
DependentProducts.unlam_sub. For any , family over , dependent-function term , and , generic evaluation of the transported substituted equals generic evaluation of reindexed along externally.
CwF.tySub_lift. For any , and type over , externally.
CwF.lift_section. For any , , , equality , type over , and supplied equality , the composite after precomposition with context transport from to along is the identity on . Both displayed equalities are explicit hypotheses.
DependentProducts.homotopyType. Given , type over , family over , and , this defines using generic evaluation of both functions.
DependentProducts.homotopyType_sub. For any , such and , substituting the pointwise-identity type equals the pointwise-identity type of the transported substituted dependent functions externally.
DependentProducts.homotopyType_congr. For any , types , families over and over , equality , equality of transported along the reverse context transport with , functions , , and heterogeneous equalities , , the corresponding pointwise-identity types are externally equal.
InternalPath.happlyEndpoint. Given , a family over and , this is the type over expressing , after reindexing and transporting the generic function through product-type substitution.
InternalPath.happlyEndpoint_sub. For any , such and functions , specializing the preceding endpoint family at equals externally.
InternalPath.happlyMotive. Given , family over and , this pulls the endpoint family of pointwise paths back to the based identity context of ; its value at is the pointwise-identity type, independent of .
InternalPath.happlyMotive_sub. For any , such , functions , and , specializing that motive at equals the pointwise-identity type between and externally.
InternalPath.happlyTerm. Given , family over , functions and , this constructs a term by , using at reflexivity the dependent abstraction of reflexivity of the generic evaluation of , and transporting the motive specialization.
InternalPath.happlyTerm_refl. For any , family over and , applying the preceding construction to equals externally.
InternalPath.happly. Given , family over and , this constructs the internal arrow by arrow abstraction of happlyTerm applied to the generic path in the path-variable extension, with product, identity and pointwise-type transports.
FunctionExtensionality. Given , this supplies in every context and for every type , contextual family , and , a term of for the specific arrow constructed by above. Thus the supplied witness includes an internal inverse, both inverse homotopies, and the half-adjoint coherence path. It is a field supplying data, not a theorem derived here from the other structures.
FunctionExtensionality.funext. Given and a function-extensionality structure, family over and , this selects the first dependent-sum component of the given equivalence witness, yielding an arrow from pointwise internal identities to .
FunctionExtensionality.funextApply. Under the same structural assumptions, for any and term , this applies that selected inverse arrow to , yielding an internal identity between and .
IdentityTypes.basedPath_lift. For any , type over , and , reindexing the based-path family of along equals the based-path family of externally.
IdentityTypes.pathLift. Given , type over , and , this constructs a substitution from the based path context of to that of , preserving the endpoint and path variables via two lifts and the based-path stability equality.
IdentityTypes.pathLift_fst. For any as above, projecting the path lift equals followed by projection of the path variable.
InternalPath.transportMotive. Given , family over and , this is the pullback of along the endpoint projection from the based path context of , with no dependency on its path variable.
InternalPath.transportMotive_sub. For any , such , and , specializing the transport motive at equals externally.
InternalPath.transport. Given , family over , endpoints , path and term , this produces a term of by with the endpoint-dependent motive and initial branch , using external transports at both specializations.
InternalPath.transport_refl. For any , family over , and , transport along equals externally.
Parametricity.interchange. Given and any code over , this constructs the substitution from to retaining both variables, where is independent of the size variable. It uses the decoded-code lift of the size projection and extends it by the weakened generic size.
Parametricity.boundedExAt. Given , a size term over and code family over , this defines the code , with weakened through and weakened through .
Parametricity.existsPiSource. Given , code over and code family over , this is the code .
Parametricity.existsPiTarget. Under the same assumptions and for the same arbitrary , this is the code . The outer is shared across the dependent product; the inner existential size and its bound witness are inside that product. Context lifts preserve the base and while adding the independent bound . No monotonicity hypothesis on appears.
Parametricity.allSigmaSource. Given , code over and code family over , this is the code .
Parametricity.allSigmaTarget. Under the same assumptions and for the same , this is the code , obtained by weakening under the size binder and reindexing along the variable-interchange substitution.
Parametricity.existsLtSource. Given and code family over , this is the code .
Parametricity.existsLtTarget. Given and code family over , this is simply the code .
Parametricity.allLtSource. Given and code family over , this is simply the code .
Parametricity.allLtTarget. Given and code family over , this is the code .
SizeRules.sub_comp. For any , size term in and substitutions , , successive transported size substitutions equal substitution along externally.
SizeRules.generic_sub_extend. For any , and size term in , substituting the size extension of into the generic size of yields exactly .
SizeRules.extend_fst. For any , and size term in , projecting the size extension of recovers .
SizeRules.sub_generic_heq. For any , contexts and substitution , transported substitution of the generic size is heterogeneously equal to ordinary substitution of the last context variable along .
SizeRules.hom_ext. For any , contexts and maps , if and substituted generic sizes are externally equal, then externally.
SizeRules.lift_fst. For any and , projection after its size lift satisfies .
SizeRules.generic_sub_lift. For any and , the generic size of substituted along equals the generic size of externally.
SizeRules.inner_fst. For any , projecting the inner-size selection map equals the double projection .
SizeRules.generic_sub_inner. For any , substituting the inner-size selection into the generic size over gives the newest generic size over externally.
SizeRules.inner_lift. For any and , inner-size selection after lifting through two size binders equals the size lift of after inner-size selection over .
SizeRules.outer_sub_lift. For any and , the weakened outer generic size over , reindexed along the double size lift of , equals the weakened outer generic size over .
SizeRules.boundCode_sub. Given and the full size-substitution structure , for every , the code reindexed along the double size lift equals the corresponding bound code over .
Universe.liftElAs_fst. For any , , source code , target code and equality , projection after the decoded-code lift with domain equals .
SmallTypeConstructors.pi_sub_as. Given and small-constructor substitution laws , source code , family over , , target code and equality , the substituted small product code equals the product of with reindexed along the decoded-code lift whose domain is identified as .
SmallTypeConstructors.sigma_sub_as. Under the same structural assumptions, for every and equality , the analogous external equality holds for the small sum code, with its family reindexed along that same explicitly identified decoded-code lift.
SizeRules.boundedFamily_sub. Given , a code family over and , first selecting the inner size and weakening through the bound-proof binder, then reindexing through the decoded bound-code lift of the double size lift of , equals first reindexing along , then selecting the inner size and weakening through the new bound-proof binder. The lift uses the bound-code stability equality supplied by .
SizeRules.box_sub. Given , size, small-constructor and universal-quantifier substitution structures , any code family and , reindexing the code along equals forming that code from externally.
SizeRules.diamond_sub. Given , size, small-constructor and existential-code substitution structures , any code family and , reindexing along equals forming it from externally.
CwF.sub_ext. For any , type over and maps , equality and heterogeneous equality imply externally.
Universe.liftEl_fst. For any , source code and , projecting its decoded-code lift yields .
Universe.liftEl_snd. For any as above, the original generic decoded term reindexed along is heterogeneously equal to the generic variable of .
Universe.liftElAs_snd. For any , code over , code over , and equality , the original generic decoded term reindexed along the identified lift is heterogeneously equal to the generic variable of .
Universe.liftEl_snd_type. For any , code over and , the weakened type reindexed along equals externally.
SizeRules.sub_id. For any and size term , transported size substitution along the identity equals externally.
Parametricity.interchangeSizeMap. Given and code over , this is the map that forgets and retains the generic size, constructed by size extension over the double projection.
Parametricity.interchangeInverseType. For any , the decoding of weakened into and then pulled back along the map forgetting from equals weakened successively through and externally.
Parametricity.interchangeInverse. Given and code over , this constructs the reverse swap by pairing the size-retaining map with the weakened generic , transported by the preceding type equality.
Parametricity.interchangeInverse_fst. For any , projecting the last variable after the reverse swap yields the map that forgets while retaining .
Parametricity.interchangeInverse_snd. For any , the generic small variable in size-first order pulled back along the reverse swap is heterogeneously equal to the original small variable weakened through the final size binder.
Parametricity.interchangeInverse_snd_type. For any , the type of the small generic variable in size-first order pulled back along the reverse swap equals weakened through the original small-variable and size binders externally.
Parametricity.interchange_fst. For any , projection after the forward swap equals the decoded-code lift of the size projection, a map .
Parametricity.generic_sub_interchange. For any , the last generic size in pulled back by the forward swap equals the generic size in weakened through externally.
Parametricity.interchange_liftEl_inverse. For any , composing the reverse swap with the map supplied by the decoded-code lift of the size projection recovers projection .
Parametricity.interchangeSizeMap_interchange. For any , the forward swap followed by the map forgetting and retaining the final size recovers projection .
Parametricity.interchange_inverse. For any , the reverse swap followed by the forward swap is the identity substitution on .
Parametricity.inverse_interchange. For any , the forward swap followed by the reverse swap is the identity substitution on .
DependentSums.generic. Given , type over and family over , this is the generic variable of transported through sum-type substitution to a term of in that context.
DependentSums.split. Given , contextual and family , this is the substitution whose components are the first and second projections of the transported generic pair; the second component is transported to the fiber over the paired first component.
DependentSums.split_base. For any , composing this pair-splitting substitution with the double projection to gives the original single projection from .
SmallTypeConstructors.sigmaSplit. Given , a code and code family over , this maps to by transporting its input context using the sum decoding equality and applying dependent-sum splitting.
SmallTypeConstructors.sigmaSplit_base. For any of these kinds, projecting both decoded components after small-sum splitting equals the projection from the original decoded-sum extension to .
SmallTypeConstructors.forgetFirst. Given and two codes over , this constructs an arrow for the sum whose second code is the weakening of . It abstracts the second generic component obtained by small-sum splitting, transporting its type back to the weakened target. No inhabitant of either factor is supplied or required.
SmallTypeConstructors.sigmaPairAt. Given , code over , code family over , substitution , term and term , this constructs a term of by dependent pairing and the decoding and sum-substitution transports.
SmallTypeConstructors.productMap. Given , codes over and arrow , this constructs an arrow sending a decoded nondependent pair to . Its definition splits the generic input, applies weakened to its second component, pairs the unchanged first component with the result, and abstracts.
ExistentialSizeQuantifier.pairAt. Given , code family over , any and term , this substitutes into the generic existential pair and transports to a term of in . The size is the component of ; no external witness-selection operation is used.
Parametricity.allSigmaMap. Given and universal substitution structure , a code over and code family over , this constructs the arrow . The body splits the generic input into and , evaluates at the generic size, pairs this value with the same , and universally abstracts that size before arrow abstraction. The definition uses the inverse context swap and to transport the quantified terms. It supplies this particular forward map, with no inverse or equivalence witness in this declaration.
Parametricity.boundedToExists. Given and code family , this constructs over an arrow from to the weakening of . Its existential-elimination branch discards the pair's bound witness and forms the existential pair with the same and payload, and its target is a small code.
Parametricity.boundedAtToExists. Under the same structural assumptions, for any size term in and code family , this constructs an arrow in , using small existential elimination and the second projection to discard the bound witness.
Parametricity.existsLtMap. Given and any code family , this constructs the arrow . It eliminates the outer existential using boundedToExists as its branch, thereby sending to and discarding both the outer bound and its witness. Its source and target are the declarations named existsLtSource and existsLtTarget in that order.
Parametricity.allLtMap. Given and substitution structures , any code family yields the arrow . This abstracts the generic input and applies the previously constructed restriction , transporting the types using universal and bounded-family substitution. No monotonicity assumption occurs.
SmallTypeConstructors.arrow. Given and codes over , this is the small product code , with codomain code weakened through its domain binder.
SmallTypeConstructors.el_arrow. Given , function structure , compatibility structure between and , and codes over , decoding the preceding small arrow code equals externally.
SmallTypeConstructors.arrow_sub. Given and small substitution structure , codes over and , substituting their small arrow code equals the small arrow code on externally.
SmallTypeConstructors.postcompose. Given , function/product compatibility , codes over and , this constructs an arrow on decoded small-arrow codes by contextual abstraction of , transporting between decoded small arrows and -arrows using .
SmallTypeConstructors.piAbsAt. Given , code over , code family over , substitution , and body over , this uses dependent abstraction and decoding/substitution transports to produce a term of in .
SmallTypeConstructors.piAppAt. Under the same structural assumptions, for any , term and argument , this transports to a dependent-function term, generically evaluates it, substitutes , and transports the result to .
Parametricity.existsPiFiber. Given , code over and code family over , this is the code over for , with weakened under and reindexed to the required order of independent binders.
Parametricity.existsPiBranch. Given and existential code-substitution structure , code over and family , this constructs in the context of a size and a term a term of pulled back from . The body applies the generic to the generic , eliminates the bounded existential by dropping , and abstracts , with supplying the existential code transports.
Parametricity.existsPiMap. Under the preceding structural assumptions, for any , this constructs the arrow by small existential recursion with existsPiBranch. It sends to the function sending to obtained from . This arrow goes from existsPiTarget to existsPiSource, despite those declaration names, and does not itself assert invertibility.
IdentityEliminationSubstitution. Given , this requires for every , contextual type , endpoint , motive over the based path context of , reflexivity branch , endpoint , path , and target reflexivity branch : if , then the substituted result is heterogeneously equal to , with transported through identity-type substitution. Here must have the specialized type of that reindexed motive at the reflexivity path of . The law quantifies over such target branches and is conditional on their heterogeneous agreement.
FunctionExtensionalitySubstitution. Given and a supplied function-extensionality structure , this requires for every family over , functions , and , heterogeneous equality between the substituted full witness and the chosen full witness for the transported substituted dependent functions. The compared witness terms include inverse, both homotopies, and their coherence, rather than just the derived inverse arrow.
CwF.liftAs. Given , , type over , type over , and external equality , this transports to a substitution with domain exactly and codomain .
CwF.liftAs_fst. For any as above, projection after that identified lift equals .
CwF.liftAs_snd. For any as above, the generic variable of reindexed along that identified lift is heterogeneously equal to the generic variable of .
DependentProducts.pi_sub_as. Given , type over , family over , , type over and equality , the product type substituted along equals externally.
SizeRules.liftAs_eq_lift. For any and , the general contextual lift under the size type, with domain identified using size-type stability, equals the specially defined size lift externally.
SizeRules.pi_sub. Given , arbitrary family over and , the type equals externally.
SizeRules.bounded_sub. Given and size-substitution structure , arbitrary family over and , reindexing the large bounded product along equals forming that product from externally.
SizeRules.step_sub. Under the same assumptions and for every such , substituting the recursive-step type along equals the corresponding recursive-step type for over externally.
SizeRules.fixedPointEquation. Given , context , arbitrary family , a term and candidate , this defines the type . It is an internal product of identity types; the declaration supplies no term of it for an arbitrary candidate .
SizeRules.fixedPointSolutions. Given and size-substitution structure , context , arbitrary family and recursive-step term as above, this defines the internal sum . In the context extended by , the family is reindexed along the size lift of the new projection, is reindexed and transported via step_sub, and the generic candidate is transported via pi_sub. Solutions retain their unfolding witness as a component. No contractibility or uniqueness theorem is asserted in this definition.
CoreTheory. For a supplied , this structure packages chosen function operations , dependent products , and their type/abstraction compatibility; dependent sums and substitution for their pair/projections; identity types , identity elimination , and substitution for ; a universe , small product/sum/identity constructors , and their substitution; base empty/unit/bool codes, constructors, eliminators and computations, and substitution for those eliminators; size operations with their preorder and internal proof-irrelevance witnesses and all their substitution laws; a size recursion operation and its internal pointwise unfolding witness, together with substitution for both; small universal quantification and its code/term substitution; small existential quantification, its code substitution and pair/eliminator substitution; and full equivalence witnesses for the -constructed dependent-function happly arrows, together with substitution of those witnesses. These are the fields functions, products, functionProducts, sums, sumSubstitution, identities, identityElimination, identitySubstitution, univ, small, smallSubstitution, base, baseSubstitution, size, sizeSubstitution, recursion, recursionSubstitution, all, allSubstitution, ex, exSubstitution, exTermSubstitution, funext, and funextSubstitution, with each later field using the already chosen operations. There is no field of consistency, fixed-point uniqueness, or quantifier equivalence beyond function extensionality.
InternalPath.reverseFamily. Given , context , type and , this is the family over , with and weakened.
InternalPath.reverseFamily_sub. For any and , substituting into that reverse family yields externally.
InternalPath.symm. Given , contextual type , endpoints and , this constructs a term of by transporting along in the family , with the two specialization transports. Thus path reversal here is derived through the supplied .
ParametricityAxioms. Given and substitution structures for size operations, for small constructors, for universal codes and terms, and for existential codes, this supplies four families of terms. For every context, code , and code family over , existsPi is a term witnessing that the specific map constructed by nested existential elimination and product abstraction is an internal equivalence; allSigma witnesses that the specific map from to is an internal equivalence. For every context and code family , existsLt witnesses that from to is an internal equivalence; allLt witnesses that from to is an internal equivalence. Every witness is a term of the actual nested sum defining isEquiv: it includes an inverse , inverse homotopies , and in the appropriate path type. These are supplied fields for the four already defined maps, with no family monotonicity or external function-realization assumption.
ParametricitySubstitution. Given all the structures and four chosen witnesses of ParametricityAxioms, this supplies four naturality fields, each quantified over every . For existsPi_sub and allSigma_sub, any code in and code family are reindexed to and pulled back along the size lift of the decoded-code lift ; the full original equivalence witness after term substitution must be heterogeneously equal to the chosen witness for these new parameters. For existsLt_sub and allLt_sub, any code family is reindexed along , and the substituted full witness must be heterogeneously equal to the chosen witness for that family. These four fields concern the supplied inverse, homotopy, and coherence data collectively; they are additional equalities between proof terms, not merely assertions that some equivalence remains inhabited.
ParametricTheory. For a supplied , this extends a chosen CoreTheory C by a parametricity field containing the four equivalence-witness schemas for its exact already constructed canonical maps, and a parametricitySubstitution field asserting the four heterogeneous substitution equalities for those same chosen witnesses. All structures used by these fields are the inherited core structures. There is no consistency field and no separate existence assertion for an instance of this package.
CoreTheory.HasTypeEquivalence. Given , a chosen core theory , context and arbitrary contextual types , this external proposition says that the term carrier of the internal type is nonempty. Unfolded, there exists an internal term containing a forward arrow, inverse arrow, both inverse homotopies, and the half-adjoint coherence built using 's identity elimination. It neither identifies the types externally nor fixes a particular forward map in advance.
CoreTheory.DefinableQuantifierEquivalences. Given and a core theory , this defines an external proposition quantified over every context , every code there, and every code family over . It requires both nonemptiness of the internal equivalence type from to , and nonemptiness of the internal equivalence type from to . Each internal equivalence comprises a forward map, inverse, two homotopies and half-adjoint coherence. The right-hand code families are reindexed using the actual context-interchange map. This is a conjunction for every family, not a supplied proof or a requirement that chosen maps or witnesses vary naturally with the parameters.
CoreTheory.ConstantQuantifierEquivalences. Given and a core theory , this defines the external proposition that for every context and code in it, both the internal equivalence type from to and the internal equivalence type from to have a term. In both quantifiers is weakened along , so it is independent of the newly introduced size but may depend on all parameters of . The equivalence data include inverse, homotopies and coherence; no particular forward arrow, chosen natural family, or proof of this proposition is supplied here.
CoreTheory.IsConsistent. Given and a core theory , this is the external proposition that the carrier of terms of the decoded chosen empty code in the chosen terminal context is not nonempty. Equivalently, there is no such closed term. It does not quantify over arbitrary theories, assert that an instance exists, or prove this property of .
Literal defects
No definite literal defect was established by this static read-back. This statement is not an elaboration result, a consistency proof, or a comparison with any informal source. The following points record the literal strength and allowed degeneracies separately from the declaration paragraphs.
Degeneracies and boundaries of the assertions
The supplied carriers are abstract. Contexts are inhabited because a terminal context is supplied, but a bare CwF need not supply arbitrary types or terms. Once a core theory is supplied, base codes and the size zero term exist in every context. No declaration requires two different contexts, two different codes, two different size terms, two different boolean terms, or any injectivity of decoding. In particular, the displayed algebraic fields do not exclude a completely collapsed interpretation in which the context, substitution, type and term carriers each have one element, every operation is the unique available operation, and all equations hold. In that interpretation the chosen empty type has a closed term, so IsConsistent fails; consistency is an additional proposition rather than an automatic field of either theory package.
Neither the word “empty” nor the name of the boolean constructors imposes external emptiness or distinctness. Empty elimination supplies contextual terms over the empty-type extension; it is not itself a hypothesis that the empty-type term carrier is empty. The zero size ensures a size term in every context, but successor may coincide externally with its input, and the comparison code need not denote an external preorder relation. Its proof-irrelevance field compares comparison witnesses by internal identity. The abbreviation is exactly the internal type and includes the case whenever that type has terms; no irreflexivity or exclusion of self-bounds is stated. Nothing in the universe structure requires that the size type lack a universe code.
The type-former and identity structures alone admit empty term carriers wherever their supplied operations do not force inhabitants. Statements universally quantified over terms or code families have no instances when their parameter carrier is empty. Each conditional substitution field applies only after the explicitly quantified target term and heterogeneous agreement have been provided; its conclusion must not be read as independently constructing that target term. The standalone declarations include all contexts and all allowable families, without a nonempty-domain, monotonicity, computability, or tracking premise. The full packages may impose further consequences through their combined operations, but no separate exclusions of these parameter cases are present in their signatures.
External equality fields are ordinary Lean equalities of the supplied data, not automatically judgmental reduction rules. Heterogeneous equality is likewise external and must not be replaced by an internal path. Conversely, internal paths, homotopies, comparison proof-irrelevance witnesses, unfolding witnesses, and equivalence witnesses are terms of the supplied contextual types. No conversion of an arbitrary such path into external endpoint equality, and no general uniqueness of internal identity proofs, is supplied. The half-adjoint coherence in isEquiv compares the -derived action on one homotopy with evaluation of the other homotopy at the forward image; it is not omitted or replaced by an external equality.
Existential size elimination is restricted to decoded code motives, whereas ordinary base-type elimination and based identity elimination take arbitrary contextual motives. Universal size quantification has inverse contextual abstraction/evaluation with external beta and eta equalities; existential size quantification has its displayed elimination beta equality but no primitive eta field. The recursive operator supplies one candidate and its internal pointwise unfolding witness. The solution sum retains that witness, and neither its contractibility nor uniqueness of fixed points is proved in this file. The three final consequence definitions are propositions only. The file supplies no inhabitant of CoreTheory or ParametricTheory, no proof of their consistency, and no proof of either final quantifier-equivalence predicate.
The four parametricity fields assert equivalence of specific constructed arrows. By contrast, HasTypeEquivalence and the final quantifier-equivalence predicates only assert nonemptiness of an internal type that also chooses a forward arrow. Their logical content does not prescribe the canonical maps of the earlier definitions or add substitution coherence for the selected witnesses.
Coverage check: all 208 explicitly written public structure, definition, abbreviation, and theorem declarations have one paragraph each, in source order; primitive structure fields are covered within their structure paragraph. The input SHA256 was rechecked after writing and still matched the value above.