Theorem 11: Canonical inductive encodings and polynomial W-types
OpenLaarakkerOttenVanDenBerg2026.V2.theorem_11_inductive_typesFor every contextual wild functor with the internally quantified existential weak-commutation witness, the prescribed algebra on is internally initial and its prescribed structure map is an internal half-adjoint equivalence. Every small polynomial signature supplies functor-law witnesses for the literal polynomial object and morphism data, the required weak-commutation witness, and this canonical initial algebra. No finiteness or inhabitedness restriction is imposed on the branching types.
import Definitions.Def_LaarakkerOttenVanDenBerg2026_EncodingRevision2
namespace LaarakkerOttenVanDenBerg2026.V2
universe u v w t
open Theory
/-- The prescribed existential encoding is an initial algebra for every
weakly commuting wild functor, and every polynomial signature supplies the
needed functor and weak-commutation witnesses. -/
theorem theorem_11_inductive_types {C : CwF.{u,v,w,t}} (T : ParametricTheory C) :
(∀ (Γ : C.Ctx) (D : WildEndofunctor T.univ T.functions T.identities Γ)
(h : T.toCoreTheory.WeaklyCommutesExists D),
T.toCoreTheory.InductiveEncoding D h) ∧
T.toCoreTheory.PolynomialInductiveEncodings := by
sorry
end LaarakkerOttenVanDenBerg2026.V2Read-back
What the Lean code literally says, in plain math · Codex / GPT-6 (independent fresh-context read-back)
At arbitrary universe levels , let be a category with families whose contexts, substitutions, contextual types, and contextual terms lie respectively in those universes, with a terminal empty context, context extension, and the stated identity, composition, substitution, and comprehension equations. A core package on supplies contextual dependent products and sums with their introduction, elimination/projection, and computation rules; nondependent arrows compatible with the corresponding dependent products; internal identity types with reflexivity and based identity elimination and its computation rule; a Tarski universe with decoding, closed under small dependent products, sums, and identities; small empty, unit, and Boolean types with their constructors and dependent eliminators; and the indicated substitution equations for all these operations and witnesses. It also supplies a large type of sizes with zero, successor, a small relation , witnesses of , , reflexivity and transitivity, and internal equality of any two witnesses of the same comparison. Write for the decoded type , without assuming any additional external order properties. The core includes a contextual size recursor for every possibly large family and step , with an internal pointwise unfolding witness and substitution laws for the recursor and that witness. It includes primitive small size quantifiers and : has contextual abstraction/application and both computation equations, while has pairing and dependent elimination into small motives with its computation equation, together with their stated substitution laws. Finally the identity-elimination-defined map from equality of dependent functions to pointwise equality has a substitution-stable internal half-adjoint-equivalence witness. All products, sums, arrows, and identities in what follows are these internal types; small types are decoded contextual universe codes, not arbitrary metatheoretic sets, and contextual terms are not identified with all external functions. For an internal arrow , a half-adjoint-equivalence witness consists internally of , , , and , with derived by identity elimination. An equivalence between two types additionally includes its forward arrow. Write ; this contracts the whole type , including any witness components. Existence of a contextual term of one of these types is an external nonemptiness assertion, not an identification of internal identities with external equality. A parametric package means such a core package together with substitution-stable internal half-adjoint-equivalence witnesses for four prescribed maps, at every context and every indicated small family: , sending a common bound and bounded witnesses to their unbounded witnesses; , sending to the family ; , forgetting the outer size and comparison witness; and , restricting a family. Here in the first two schemas may depend on the ambient context but not on the newly introduced size, and may depend on both and that size. A wild endofunctor at a context means an operation on small codes and internal arrows in every context over by a substitution , commuting with further substitution, together with internal identities and in their generic code/arrow contexts; no higher coherence is a field. For a small size family , put and . A sized arrow is a contextual term of , with pointwise identity and composition; the modal arrow actions preserve the size and comparison witness and apply the given arrow to the -component, or postcompose the bounded function, respectively. An existential weak-commutation witness is one contextual term of the internal product over of the half-adjoint-equivalence type of the prescribed map . Its existential branch sends to , where forgets the bound and its witness. Thus the family quantification and all inverses, homotopies, and coherence of this hypothesis are internal, rather than an external assertion separately selecting an equivalence for each family. The prescribed family is the output of the chosen primitive size recursor on universe codes with step , where the recursive input is and may depend on the comparison witness. After restricting the resulting family, its actual recursor unfolding witness gives an internal universe path . Its prescribed sized structure is transport along the reverse of that path, formed by identity elimination. For every supplied parametric package , the header asserts two conclusions: first, for every context , every wild endofunctor there, and every existential weak-commutation term , the following prescribed inductive conclusion; and second, the polynomial clause below. For the specified , set and , using exactly the inverse extracted from . The asserted inductive conclusion is the conjunction of existence of a term of and existence of an internal half-adjoint-equivalence witness for this particular . Carrier and structure-map quantification in initiality is internal, and the contractible morphism type includes the commuting-square path, not just the underlying function. The polynomial clause quantifies externally over every context , every small code in , and every small code in . It asserts existence of a wild endofunctor whose entire object/morphism data is externally equal to the prescribed polynomial data , with arrow action and its specified substitution operations, and existence of an existential weak-commutation term for that functor for which the preceding prescribed inductive conclusion holds. Functor-law witnesses and are existential outputs, not additional hypotheses on the signature. There is no extra finiteness, nonemptiness, monotonicity, decidability, external well-foundedness, or consistency hypothesis on the abstract model or small families; empty signatures and empty or infinite small branching types are included whenever represented by its universe. Assertions quantified over a supplied package are conditional on such a package, and implications quantified over a weak-commutation term impose no conclusion for a functor with no such term. Internal quantifiers range over all internal values, including values available only in extended contexts. This is a readback of the asserted header; its proof body is a placeholder, so no proof is certified here.