Foundation Primitive Recognition Calculus Completion Conservativity Product Cons

Certifying combined displays

In formal verification, a completion is a bridge from raw data to a display form, together with certificates that vouch for display properties. Think of a certificate as a receipt: if a display datum satisfies a predicate, a certificate records why. A completion is conservative for a predicate when every display satisfying that predicate carries such a certificate. The framework's machine-checked library of formal theorems proves a basic closure fact: if two completions are each conservative for their own predicates, then the product completion, which displays pairs by displaying each component, is conservative for the paired predicate. The theorem product_conservative states this precisely: given certificates for the first component and the second component, it constructs a paired certificate for the pair.

The proof is a direct composition. Suppose a pair (d₁, d₂) satisfies the product predicate, meaning d₁ satisfies P₁ and d₂ satisfies P₂. Conservativity of the first completion yields a certificate c₁ for d₁; conservativity of the second yields c₂ for d₂. The pair (c₁, c₂) then certifies the display pair, because the product completion's certification relation checks each component separately. This is the base case for certificate-preserving completions, and it composes: the identity completion, which displays data as itself and certifies each datum by itself, is conservative for every predicate. The headline theorem packages both facts: a completion is conservative exactly when it has no uncertified display artifacts, and the identity completion is always conservative.

The practical content is that multi-field display objects can be certified componentwise. If a form has several fields, and each field's display is backed by a certificate, the whole form inherits a certificate without inventing a new kind of evidence. The same closure extends to finite vectors and finite fields: the function-space completion, which completes each coordinate through the same interface, is conservative for pointwise predicates. This is what lets a framework built on discrete recognition events scale from single values to structured records without losing the guarantee that every displayed claim has native backing.

What the theorem does not claim is just as important. It does not assert that any particular completion exists for a given data type, nor that certificates are unique, nor that the predicates involved are decidable. It is a conditional statement: if the components are conservative, then the product is. It also does not say that every predicate on a product is certificate-covered, only those built from component predicates in the pointwise way. The theorem is a structural closure property, not a claim about which predicates hold in the world.

/-- Conservative completions compose across products: if each component display
predicate descends to a certificate, the product predicate descends to paired
certificates. -/
theorem product_conservative
    {N₁ D₁ Cert₁ N₂ D₂ Cert₂ : Type*}
    (C₁ : Completion N₁ D₁ Cert₁) (C₂ : Completion N₂ D₂ Cert₂)
    (P₁ : D₁ → Prop) (P₂ : D₂ → Prop)
    (h₁ : ConservativeFor C₁ P₁) (h₂ : ConservativeFor C₂ P₂) :
    ConservativeFor (productCompletion C₁ C₂) (ProductPredicate P₁ P₂) := by
  intro d hd
  rcases hd with ⟨hP₁, hP₂⟩
  rcases h₁ d.1 hP₁ with ⟨c₁, hc₁⟩
  rcases h₂ d.2 hP₂ with ⟨c₂, hc₂⟩
  exact ⟨(c₁, c₂), ⟨hc₁, hc₂⟩⟩

theorem identity_conservative (N : Type*) (P : N → Prop) :
    ConservativeFor (identityCompletion N) P := by
  intro d _
  exact ⟨d, rfl⟩

theorem conservative_iff_no_artifact {N D Cert : Type*} (C : Completion N D Cert) (P : D → Prop) :
    ConservativeFor C P ↔ ¬ ArtifactFor C P := by
  unfold ConservativeFor CertificateCovered ArtifactFor
  constructor
  · intro h hc
    rcases hc with ⟨d, hP, hno⟩
    exact hno (h d hP)
  · intro h d hP
    by_contra hno
    exact h ⟨d, hP, hno⟩

/-- Conservativity lifts pointwise to finite function displays: if each coordinate
predicate has a certificate, the whole function has a coordinatewise certificate. -/
theorem function_conservative
    {I N D Cert : Type*} (C : Completion N D Cert) (P : D → Prop)
    (hC : ConservativeFor C P) :
    ConservativeFor (functionCompletion I N D Cert C) (AllPredicate P) := by
  intro d hd
  choose c hc using fun i : I => hC (d i) (hd i)
  exact ⟨c, hc⟩

What this page does not claim

The theorem does not assert that any particular completion exists for a given data type. It does not claim certificates are unique or that predicates are decidable. It does not say every predicate on a product is certificate-covered, only pointwise product predicates.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/PrimitiveRecognitionCalculus/CompletionConservativity.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: