Foundation Primitive Recognition Calculus Formal System Formal System Embedding

The embedding target

A formal system is a set of rules for writing and manipulating symbols. In mathematics, a formal system has tokens, which are the basic symbols, and expressions, which are finite strings built from those tokens. The Recognition Science framework's library, a machine-checked collection of formal theorems, defines a minimal interface for such a system: it must be able to distinguish two specific tokens, and it must have a way to record that one expression extends another.

The theorem FormalSystemEmbeddingTarget_proved establishes a conditional guarantee. It states that if any formal system can distinguish the two endpoints of the primitive distinction, which are the two basic alternatives in the framework's account of recognition, then that system can host an embedding of the primitive recognition calculus. The embedding preserves the distinction between the two endpoints and the relation of one finite trace extending another. This is a structural result: it shows that the core recognition structure is portable, not tied to one particular notation.

The proof is constructive. Given any expressive formal system, the theorem builds the embedding by using the system's own token and expression carriers. It does not require the system to have any additional features beyond the minimal interface. The framework's own formal system, where tokens are endpoints and expressions are finite traces, is shown to be expressive because the two endpoints are provably distinct. This closes the formal-system surface for the framework's internal development.

In Recognition Science, this theorem is a step in a larger inevitability argument. The broader claim, that every external foundation satisfies this interface, is the next layer of the argument and is not hidden in this theorem. The theorem itself is a precise, conditional statement about what follows from the minimal interface, not a claim about the actual structure of any particular external formal system.

theorem FormalSystemEmbeddingTarget_proved :
    FormalSystemEmbeddingTarget := by
  intro F hF
  exact ⟨PRCEmbeddingInto.ofExpressive F hF⟩

/-- A PRC embedding into a formal system preserves the primitive endpoint
distinction and finite trace extension. -/
structure PRCEmbeddingInto (F : FormalSystem) where
  endpointMap : Endpoint → F.Token
  traceMap : Trace → F.Expr
  preserves_distinction :
    F.distinguishes (endpointMap Endpoint.left) (endpointMap Endpoint.right)
  preserves_trace_extension :
    ∀ {T U : Trace}, Trace.Extends T U → F.exprExtends (traceMap T) (traceMap U)

theorem PRCFormalSystem_expressive :
    PRCFormalSystem.Expressive := by
  exact Endpoint.left_ne_right

What this page does not claim

The theorem does not prove that every external formal system satisfies the interface. The theorem does not claim that any particular real-world formal system is expressive. The theorem does not establish the physical recognition-to-linking bridge.

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/FormalSystem.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: