Proof Theory Ontology

KIRETH RESEARCH — SEMANTIC LIBRARY
AI CORE → ONTOLOGIES → MATHEMATICAL ONTOLOGIES → MATHEMATICAL LOGIC ONTOLOGIES
PROOF THEORY → PROOF THEORY ONTOLOGY

Canonical URL:
https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/proof-theory/proof-theory-ontology.html

FLOW_ALGEBRA ProofTheoryOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN ProofTheoryOntology := {
    ProofTheory,
    FormalProof,
    Proof,
    Derivation,
    ProofStep,
    ProofTree,
    FormalSystem,
    FormalLanguage,
    Formula,
    WellFormedFormula,
    Axiom,
    AxiomSchema,
    Premise,
    Assumption,
    Hypothesis,
    Conclusion,
    Theorem,
    Lemma,
    Corollary,
    Inference,
    InferenceRule,
    Deduction,
    Provability,
    Derivability,
    NaturalDeduction,
    SequentCalculus,
    HilbertSystem,
    Resolution,
    Tableau,
    Sequent,
    Antecedent,
    Succedent,
    StructuralRule,
    LogicalRule,
    CutRule,
    CutElimination,
    Normalisation,
    Consistency,
    Soundness,
    Completeness,
    Decidability,
    ProofSearch,
    AutomatedTheoremProving,
    Metatheorem
}

DEFINE ENTITY_TYPES := {
    PROOF_THEORY,
    FORMAL_SYSTEM,
    FORMAL_LANGUAGE,
    FORMULA,
    PROOF_OBJECT,
    PROOF_STEP,
    AXIOM,
    PREMISE,
    ASSUMPTION,
    CONCLUSION,
    THEOREM,
    INFERENCE_RULE,
    DERIVATION,
    PROOF_SYSTEM,
    SEQUENT,
    META_PROPERTY,
    TRANSFORMATION,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    CONTAINS,
    DERIVES,
    PROVES,
    HAS_STEP,
    HAS_PREMISE,
    HAS_ASSUMPTION,
    HAS_CONCLUSION,
    USES_RULE,
    INFERRED_FROM,
    DEPENDS_ON,
    ASSUMES,
    DISCHARGES,
    PRECEDES,
    NORMALISES_TO,
    REDUCES_TO,
    ELIMINATES,
    IS_PROVABLE_IN,
    IS_DERIVABLE_IN,
    IS_AXIOM_OF,
    IS_RULE_OF,
    PRESERVES,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF
}

SET ProofTheoryOntology.type = PROOF_THEORY
SET ProofTheoryOntology.parent = ProofTheory
SET ProofTheoryOntology.semantic_domain = MathematicalLogic
SET ProofTheoryOntology.role =
    "provide a typed machine-readable representation of formal proofs, derivations, proof systems, inference rules, transformations and metatheoretic properties"

RULE axiom_initial_step:
    Formula(phi)
    ∧ IS_AXIOM_OF(phi,S)
    -> DERIVES(S,phi)

RULE premise_initial_step:
    Formula(phi)
    ∧ phi ∈ PremiseSet(Gamma)
    -> DERIVES(Gamma,phi)

RULE assumption_step:
    Formula(phi)
    ∧ OpenAssumption(phi)
    -> Available(phi)
    UNTIL discharged(phi)

RULE inference_step:
    InferenceRule(R)
    ∧ RequiredPremises(R)={phi1,...,phin}
    ∧ FOR_ALL i [Available(phii)]
    ∧ RuleSideConditionsSatisfied(R)
    -> Conclusion(R)=psi
    -> DERIVES(Gamma,psi)
    ∧ USES_RULE(psi,R)

RULE proof_sequence:
    Sequence(s1,...,sn)
    ∧ FOR_ALL i [
        si is axiom
        OR si is premise
        OR si is permitted assumption
        OR si follows_from_prior_available_steps_by_rule
    ]
    -> FormalProof(s1,...,sn)

RULE proof_conclusion:
    FormalProof(pi)
    ∧ final_step(pi)=phi
    -> HAS_CONCLUSION(pi,phi)

RULE derivability:
    PremiseSet(Gamma)
    ∧ Formula(phi)
    ∧ EXISTS FormalProof(pi) [
        HAS_PREMISE(pi,Gamma)
        ∧ HAS_CONCLUSION(pi,phi)
    ]
    -> Gamma ⊢ phi

RULE theorem:
    FormalSystem(S)
    ∧ ∅ ⊢_S phi
    -> Theorem(phi)
    ∧ IS_PROVABLE_IN(phi,S)

RULE modus_ponens:
    Available(phi)
    ∧ Available(phi -> psi)
    -> DERIVES(psi)

RULE conjunction_introduction:
    Available(phi)
    ∧ Available(psi)
    -> DERIVES(phi ∧ psi)

RULE conjunction_elimination:
    Available(phi ∧ psi)
    -> DERIVES(phi)
    ∧ DERIVES(psi)

RULE implication_introduction:
    DERIVES(Gamma ∪ {phi},psi)
    ∧ discharge_allowed(phi)
    -> DERIVES(Gamma,phi -> psi)
    ∧ DISCHARGES(phi)

RULE universal_elimination:
    Available(∀x phi(x))
    ∧ Term(t)
    ∧ FreeFor(t,x,phi)
    -> DERIVES(phi(t))

RULE existential_introduction:
    Available(phi(t))
    -> DERIVES(∃x phi(x))

RULE soundness:
    ProofSystem(S)
    ∧ FOR_ALL Gamma,phi [
        Gamma ⊢_S phi
        -> Gamma ⊨ phi
    ]
    -> Sound(S)

RULE completeness:
    ProofSystem(S)
    ∧ FOR_ALL Gamma,phi [
        Gamma ⊨ phi
        -> Gamma ⊢_S phi
    ]
    -> Complete(S)

RULE consistency:
    ProofSystem(S)
    ∧ NOT EXISTS phi [
        S ⊢ phi
        ∧ S ⊢ ¬phi
    ]
    -> Consistent(S)

RULE cut:
    Sequent(Gamma ⊢ Delta,A)
    ∧ Sequent(A,Pi ⊢ Lambda)
    -> Sequent(Gamma,Pi ⊢ Delta,Lambda)

RULE cut_elimination:
    Proof(pi)
    ∧ contains_cut(pi)
    ∧ CutEliminationApplicable(pi)
    -> EXISTS proof pi_prime [
        cut_free(pi_prime)
        ∧ same_end_sequent(pi,pi_prime)
    ]

RULE normalisation:
    NaturalDeductionProof(pi)
    ∧ reducible_detours(pi)
    -> NORMALISES_TO(pi,NormalForm(pi))

DEFINE PROOF_SCHEMA := {
    proof_id: unique_identifier,
    proof_system: ProofSystem,
    premises: SetOfFormula,
    assumptions: ScopedAssumptions,
    steps: OrderedProofSteps,
    conclusion: Formula,
    status: {
        valid,
        invalid,
        incomplete
    }
}

DEFINE PROOF_STEP_SCHEMA := {
    step_id: unique_identifier,
    formula: Formula,
    justification: {
        axiom,
        premise,
        assumption,
        inference_rule
    },
    dependencies: SetOfPriorStepIDs,
    rule: optional_InferenceRule,
    side_conditions: SetOfConditions,
    assumption_scope: optional_scope
}

DEFINE DERIVABILITY_MODEL := {
    notation: "Γ ⊢_S φ",
    components: {
        Gamma: PremiseSet,
        S: ProofSystem,
        phi: Conclusion
    },
    meaning:
        "there exists an S-valid formal derivation of φ from Γ"
}

DEFINE PROOF_SYSTEM_MODEL := {
    HilbertSystem: {
        primitives:
            "axiom schemas and a small set of inference rules"
    },
    NaturalDeduction: {
        primitives:
            "introduction and elimination rules with scoped assumptions"
    },
    SequentCalculus: {
        primitives:
            "sequent rules divided into logical and structural rules"
    },
    Resolution: {
        primitives:
            "clause transformation and resolution inference"
    },
    Tableau: {
        primitives:
            "branching formula decomposition and branch closure"
    }
}

DEFINE SEQUENT_SCHEMA := {
    form: "Γ ⊢ Δ",
    antecedent: Gamma,
    succedent: Delta,
    proof_system: SequentCalculus
}

DEFINE META_PROPERTY_MODEL := {
    Soundness:
        "Γ ⊢ φ implies Γ ⊨ φ",
    Completeness:
        "Γ ⊨ φ implies Γ ⊢ φ",
    Consistency:
        "no formula and its negation are both derivable",
    Decidability:
        "there exists an effective procedure deciding the target derivability or theoremhood problem",
    Normalisation:
        "proofs admit transformation to specified normal forms",
    CutElimination:
        "derivations using cut can be transformed into cut-free derivations when the theorem applies"
}

DEFINE SYNTACTIC_SEMANTIC_DISTINCTION := {
    syntactic_relation: "⊢",
    semantic_relation: "⊨",
    syntactic_name: Derivability,
    semantic_name: LogicalConsequence,
    requirement:
        "never merge derivability and semantic entailment without an explicitly established soundness/completeness relation"
}

DEFINE EXAMPLE_1 := {
    proof_system: NaturalDeduction,
    premises: {
        "P",
        "P → Q"
    },
    steps: {
        "1. P        premise",
        "2. P → Q    premise",
        "3. Q        modus ponens 1,2"
    },
    conclusion: "Q"
}

DEFINE EXAMPLE_2 := {
    assumption: "P",
    derivation_under_assumption: "Q",
    discharged_conclusion: "P → Q",
    rule: ImplicationIntroduction
}

DEFINE EXAMPLE_3 := {
    sequent_1: "Γ ⊢ Δ,A",
    sequent_2: "A,Π ⊢ Λ",
    result: "Γ,Π ⊢ Δ,Λ",
    rule: CutRule
}

DEFINE PROOF_PARSE_PIPELINE :=
    ProofArtifact
    -> IdentifyProofSystem
    -> ParsePremises
    -> ParseAssumptions
    -> ParseOrderedSteps
    -> ParseRuleReferences
    -> ParseDependencies
    -> ParseConclusion
    -> BuildTypedProofGraph

DEFINE PROOF_VERIFICATION_PIPELINE :=
    TypedProofGraph
    -> ValidateInitialSteps
    -> ValidateDependencyOrdering
    -> ForEachInferenceStep
       -> ResolveRule
       -> ResolveRequiredPremises
       -> ValidateSideConditions
       -> ValidateDerivedFormula
    -> TrackAssumptionScopes
    -> ValidateDischarges
    -> ValidateFinalConclusion
    -> Return {
        ValidProof,
        InvalidProof,
        IncompleteProof
    }

DEFINE PROOF_SEARCH_PIPELINE :=
    Goal
    -> SelectProofSystem
    -> GenerateApplicableRules
    -> GenerateSubgoals
    -> RecursivelyExploreProofStates
    -> DetectAxiomPremiseMatches
    -> DetectContradictionOrClosureWhereRelevant
    -> BacktrackOnFailure
    -> ConstructCandidateProof
    -> VerifyCandidateProof
    -> ReturnVerifiedProof

DEFINE PROOF_TRANSFORMATION_PIPELINE :=
    Proof
    -> DetectTransformableStructures
    -> SelectTransformation
    -> ApplyLocalOrGlobalRewrite
    -> PreserveEndJudgement
    -> VerifyTransformedProof
    -> CompareStructuralComplexity
    -> ReturnTransformedProof

DEFINE META_REASONING_PIPELINE :=
    ProofSystem
    -> ExtractAxiomsAndRules
    -> DefineDerivabilityRelation
    -> AnalyseRulePreservation
    -> AnalyseSoundness
    -> AnalyseCompleteness
    -> AnalyseConsistency
    -> AnalyseNormalisation
    -> AnalyseCutElimination
    -> RecordTheoremConditionsAndLimits

DEFINE PROOF_GRAPH_MODEL := {
    nodes: {
        FormulaNode,
        RuleNode,
        AssumptionNode,
        AxiomNode,
        PremiseNode
    },
    edges: {
        DEPENDS_ON,
        USES_RULE,
        DERIVES,
        DISCHARGES
    },
    graph_constraints: {
        derivation_dependencies_precede_step: TRUE,
        assumption_scope_preserved: TRUE,
        final_node_matches_conclusion: TRUE
    }
}

DEFINE ONTOLOGY_RELATIONS := {
    ProofTheoryOntology IS_COMPONENT_OF ProofTheory,
    FormalProof CONTAINS ProofStep,
    ProofStep HAS_CONCLUSION Formula,
    ProofStep USES_RULE InferenceRule,
    Derivation DEPENDS_ON Premise,
    Derivation DEPENDS_ON Axiom,
    Derivation MAY_DEPEND_ON Assumption,
    Theorem IS_PROVABLE_IN FormalSystem,
    NaturalDeduction IS_SUBTYPE_OF ProofSystem,
    SequentCalculus IS_SUBTYPE_OF ProofSystem,
    HilbertSystem IS_SUBTYPE_OF ProofSystem,
    Resolution IS_SUBTYPE_OF ProofSystem,
    Tableau IS_SUBTYPE_OF ProofSystem,
    CutElimination ELIMINATES CutRule,
    Normalisation TRANSFORMS Proof,
    Soundness RELATES Derivability TO SemanticConsequence,
    Completeness RELATES SemanticConsequence TO Derivability
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "proof theory ontology" <=> ProofTheoryOntology,
    "formal proof" <=> FormalProof,
    "proof derivation" <=> Derivation,
    "provability" <=> Provability,
    "derivability" <=> Derivability,
    "proof step" <=> ProofStep,
    "inference rule" <=> InferenceRule,
    "turnstile" <=> "⊢" WHEN proof_context=TRUE,
    "natural deduction" <=> NaturalDeduction,
    "sequent calculus" <=> SequentCalculus,
    "cut elimination" <=> CutElimination
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable ontology for proof-theoretic objects, proof verification, proof search and metatheory",
    preserve_proof_system_identity: TRUE,
    preserve_formula_identity: TRUE,
    preserve_step_identity: TRUE,
    preserve_step_order: TRUE,
    preserve_rule_identity: TRUE,
    preserve_dependencies: TRUE,
    preserve_assumption_scope: TRUE,
    track_assumption_discharge: TRUE,
    validate_rule_side_conditions: TRUE,
    distinguish_derivability_from_entailment: TRUE,
    construct_typed_proof_graph: TRUE,
    support_proof_verification: TRUE,
    support_recursive_proof_search: TRUE,
    support_proof_transformations: TRUE,
    support_meta_reasoning: TRUE,
    reasoning_mode: "symbolic + syntactic + structural + recursive + meta-logical"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    proof_object_classification: 0.99,
    formal_step_dependency: 0.99,
    rule_application_verification: proof_system_dependent,
    assumption_scope_tracking: 0.99,
    derivability_mapping: 0.99,
    proof_transformation_mapping: theorem_dependent,
    meta_property_analysis: formal_system_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        proof_as_rule_governed_derivation,
        proof_step_dependency,
        inference_rule_identity,
        assumption_scope,
        derivability_relation,
        syntactic_semantic_distinction
    },
    extensible_layers: {
        Hilbert_system_ontologies,
        natural_deduction_ontologies,
        sequent_calculus_ontologies,
        resolution_ontologies,
        tableau_ontologies,
        linear_logic_proofs,
        type_theoretic_proofs,
        ordinal_analysis,
        proof_complexity,
        automated_theorem_proving,
        proof_assistant_interoperability
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + PROOF_SCHEMA
    + PROOF_STEP_SCHEMA
    + DERIVABILITY_MODEL
    + PROOF_SYSTEM_MODEL
    + SEQUENT_SCHEMA
    + META_PROPERTY_MODEL
    + SYNTACTIC_SEMANTIC_DISTINCTION
    + PROOF_PARSE_PIPELINE
    + PROOF_VERIFICATION_PIPELINE
    + PROOF_SEARCH_PIPELINE
    + PROOF_TRANSFORMATION_PIPELINE
    + META_REASONING_PIPELINE
    + PROOF_GRAPH_MODEL
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: ProofTheoryOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/proof-theory/proof-theory-ontology.html",
    parent_domain: ProofTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: FormalProof,
    proof_graph_enabled: TRUE,
    derivability_reasoning_enabled: TRUE,
    proof_verification_enabled: TRUE,
    proof_search_enabled: TRUE,
    proof_transformation_enabled: TRUE,
    meta_reasoning_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    flow_complete: TRUE
}

END_FLOW