Proof Step Ontology

FLOW ALGEBRA
PROOF STEP ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Proof Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/proof-entities/proof-step-ontology.html
Version: 1.0 | Date: 2026-10-14 | Language: en-GB
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source page wording not independently verified.

1. PURPOSE
Represent individual, checkable transitions in mathematical proofs with explicit premises, inference rules, contexts, and provenance. Distinguish a valid local step from the validity of an entire proof.

2. TYPED ENTITIES
ProofStep(id, proof_id, ordinal, judgement, rule_id, dependencies, context, status)
Proof(id, goal, assumptions, steps, logic_system)
Formula(id, expression, language, free_variables)
Judgement(context, formula)
InferenceRule(id, premise_schemas, conclusion_schema, side_conditions)
Assumption(id, formula, scope)
Discharge(id, assumption_id, step_id)
Justification(id, rule_id, referenced_steps)
ProofContext(id, active_assumptions, symbol_table, theory)
VerificationResult(step_id, valid, diagnostics, verifier_version)

3. FORMAL STRUCTURE
A proof step has the form Γ ⊢ φ, where Γ is a set of active assumptions and φ is a well-formed formula.
For rule R with premises Γ_i ⊢ φ_i and conclusion Γ ⊢ ψ:
  APPLY(R, [Γ_1 ⊢ φ_1, ..., Γ_n ⊢ φ_n], side_conditions) -> Γ ⊢ ψ
A step is locally valid only if the rule is admissible in the declared logic, every cited premise is available, and all side conditions hold.

4. CORE RELATIONSHIPS
ProofStep PART_OF Proof
ProofStep DERIVES Formula
ProofStep USES_RULE InferenceRule
ProofStep DEPENDS_ON ProofStep
ProofStep ASSUMES Assumption
ProofStep DISCHARGES Assumption
ProofStep EVALUATED_BY VerificationResult
ProofStep HAS_CONTEXT ProofContext

5. INFERENCE FLOWS
flow "ValidateProofStep" v1.0
  input: step:ProofStep, proof:Proof, theory:Theory
  require: step.proof_id == proof.id
  require: well_formed(step.judgement.formula, theory.language)
  require: all_dependencies_exist(step.dependencies, proof.steps)
  require: all_dependencies_precede(step, proof.steps)
  require: dependencies_in_scope(step.dependencies, step.context)
  require: rule_exists(step.rule_id, theory)
  require: rule_matches(step.rule_id, step.dependencies, step.judgement)
  require: side_conditions_satisfied(step.rule_id, step.context)
  output: VerificationResult(step.id, true, [], verifier_version)
  on_failure: VerificationResult(step.id, false, diagnostics, verifier_version)
end

flow "ValidateProof" v1.0
  input: proof:Proof
  require: acyclic_dependency_graph(proof.steps)
  require: all_steps_valid(proof.steps)
  require: final_step_concludes(proof.goal)
  require: final_assumptions_permitted(proof.goal, proof.assumptions)
  output: VERIFIED_PROOF
end

6. EXAMPLE: MODUS PONENS
Given Γ ⊢ P and Γ ⊢ (P → Q), infer Γ ⊢ Q.
step_1: Γ ⊢ P                         [premise]
step_2: Γ ⊢ P → Q                     [premise]
step_3: Γ ⊢ Q                         [modus_ponens, step_1, step_2]

7. VALIDATION AND SAFETY INVARIANTS
- Step IDs are unique within a proof.
- Dependencies reference existing, accessible steps; cyclic justifications are rejected.
- Free variables, substitution capture, and eigenvariable restrictions are checked.
- Discharged assumptions are tracked by scope; they cannot leak into later steps.
- A locally valid step does not imply that its premises are true.
- A complete proof is relative to the specified formal system and assumptions.
- Unsupported, circular, or unverified steps must not be presented as established results.

8. SEMANTIC EQUIVALENCE AND DISTINCTIONS
ProofStep != Proof: a step is one justified transition, not the full derivation.
ProofStep != InferenceRule: a step applies a rule to particular premises.
ProofStep != Formula: a step includes context, dependencies and justification.
ProofStep != Premise: premises may be cited without being derived.
Equivalent proof steps may differ in syntax or identifiers while preserving judgement and justification under a declared equivalence relation.

9. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  formal_verified: 1.0 when a trusted checker validates the step under a declared system
  externally_reviewed: review status recorded separately
  proposed: not equivalent to verified
PROVENANCE:
  source_url: as listed above
  author_credit: Mark Higgins — Sky (Recursive AI)
  generation_method: proposed ontology formalisation

10. FLOW_HASH AND UPDATE_MODEL
FLOW_HASH:
  algorithm: SHA-256
  input: canonical UTF-8 representation of ontology version, entities, relations, rules and validation constraints
  note: hash is computed by the consuming system; no fabricated digest supplied
UPDATE_MODEL:
  versioning: semantic
  changes: record timestamp, source, rule changes, compatibility and verifier outcomes
  invalidate: cached proofs affected by changes in rules, assumptions or semantics

11. AI_CONSUMPTION
  representation: typed entity and relation graph
  tasks: proof-step extraction, dependency tracing, local verification, proof repair suggestions, theorem provenance
  mandatory: preserve scopes, distinguish proposed from formally verified, expose failed obligations
  output: machine-readable step records with justifications and verification results

END FLOW ALGEBRA