Proof Ontology

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

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

FLOW_ALGEBRA ProofOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN ProofOntology := {
    Proof,
    FormalProof,
    ProofTheory,
    Derivation,
    ProofStep,
    ProofTree,
    ProofSequence,
    FormalSystem,
    FormalLanguage,
    Formula,
    WellFormedFormula,
    Axiom,
    AxiomSchema,
    Premise,
    Assumption,
    Hypothesis,
    Conclusion,
    Theorem,
    Lemma,
    Corollary,
    Inference,
    InferenceRule,
    RuleApplication,
    Justification,
    Dependency,
    AssumptionScope,
    Discharge,
    Provability,
    Derivability,
    NaturalDeduction,
    SequentCalculus,
    HilbertSystem,
    Resolution,
    Tableau,
    ProofVerification,
    ProofSearch,
    ProofTransformation,
    Normalisation,
    CutElimination,
    ValidProof,
    InvalidProof,
    IncompleteProof
}

DEFINE ENTITY_TYPES := {
    PROOF,
    PROOF_STEP,
    FORMULA,
    FORMAL_SYSTEM,
    AXIOM,
    PREMISE,
    ASSUMPTION,
    CONCLUSION,
    THEOREM,
    INFERENCE_RULE,
    RULE_APPLICATION,
    JUSTIFICATION,
    DEPENDENCY,
    SCOPE,
    PROOF_SYSTEM,
    TRANSFORMATION,
    VERIFICATION_RESULT,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    CONTAINS,
    HAS_STEP,
    HAS_PREMISE,
    HAS_ASSUMPTION,
    HAS_CONCLUSION,
    USES_RULE,
    JUSTIFIED_BY,
    DEPENDS_ON,
    DERIVES,
    PROVES,
    INFERRED_FROM,
    PRECEDES,
    DISCHARGES,
    IS_PROVABLE_IN,
    IS_DERIVABLE_IN,
    TRANSFORMS_TO,
    PRESERVES,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF
}

SET Proof.type = PROOF
SET Proof.context = ProofTheory
SET Proof.role =
    "represent a finite or otherwise formally admissible rule-governed derivation establishing a conclusion from axioms, premises and scoped assumptions"

RULE proof_initial_axiom:
    Formula(phi)
    ∧ IS_AXIOM_OF(phi,S)
    -> PermittedInitialStep(phi)

RULE proof_initial_premise:
    Formula(phi)
    ∧ phi ∈ PremiseSet(Gamma)
    -> PermittedInitialStep(phi)

RULE proof_initial_assumption:
    Formula(phi)
    ∧ AssumptionAllowed(phi,scope)
    -> PermittedScopedStep(phi,scope)

RULE derived_step:
    ProofStep(s)
    ∧ InferenceRule(R)
    ∧ RequiredPremises(R)={p1,...,pn}
    ∧ FOR_ALL i [
        AvailableEarlierStep(pi)
    ]
    ∧ SideConditionsSatisfied(R)
    ∧ Formula(s)=Apply(R,p1,...,pn)
    -> ValidDerivedStep(s)

RULE proof_step_order:
    ProofStep(si)
    ∧ DEPENDS_ON(si,sj)
    -> PRECEDES(sj,si)

RULE proof_validity:
    Proof(pi)
    ∧ FOR_ALL step s IN pi [
        PermittedInitialStep(s)
        OR PermittedScopedStep(s)
        OR ValidDerivedStep(s)
    ]
    ∧ AssumptionScopesValid(pi)
    ∧ FinalStep(pi)=Conclusion(pi)
    -> ValidProof(pi)

RULE invalid_proof:
    Proof(pi)
    ∧ EXISTS step s IN pi [
        NOT ValidStep(s)
    ]
    -> InvalidProof(pi)

RULE incomplete_proof:
    ProofArtifact(pi)
    ∧ steps_valid_so_far(pi)
    ∧ target_conclusion_not_yet_derived(pi)
    -> IncompleteProof(pi)

RULE proof_conclusion:
    ValidProof(pi)
    ∧ FinalFormula(pi)=phi
    -> HAS_CONCLUSION(pi,phi)
    ∧ PROVES(pi,phi)

RULE derivability:
    ValidProof(pi)
    ∧ HAS_PREMISE(pi,Gamma)
    ∧ HAS_CONCLUSION(pi,phi)
    -> Gamma ⊢ phi

RULE theoremhood:
    ValidProof(pi)
    ∧ HAS_PREMISE(pi,∅)
    ∧ HAS_CONCLUSION(pi,phi)
    ∧ proof_system(pi)=S
    -> Theorem(phi)
    ∧ IS_PROVABLE_IN(phi,S)

RULE assumption_discharge:
    Proof(pi)
    ∧ Assumption(phi,scope)
    ∧ DischargeRule(R)
    ∧ R discharges phi
    -> DISCHARGES(R,phi)
    ∧ close(scope)

RULE dependency_integrity:
    ProofStep(s)
    ∧ DEPENDS_ON(s,d)
    -> d exists_in_same_proof
    ∧ d precedes s
    ∧ d available_in_scope_of s

RULE rule_integrity:
    ProofStep(s)
    ∧ USES_RULE(s,R)
    -> R belongs_to proof_system(s)
    ∧ RuleSideConditionsSatisfied(R,s)

RULE proof_equivalence_endpoint:
    ValidProof(pi1)
    ∧ ValidProof(pi2)
    ∧ same_premises(pi1,pi2)
    ∧ same_conclusion(pi1,pi2)
    -> EndpointEquivalent(pi1,pi2)

RULE normalisation:
    Proof(pi)
    ∧ NormalisationApplicable(pi)
    -> TRANSFORMS_TO(pi,NormalForm(pi))
    ∧ PRESERVES(Normalisation,Conclusion(pi))

RULE cut_elimination:
    SequentProof(pi)
    ∧ contains_cut(pi)
    ∧ CutEliminationApplicable(pi)
    -> TRANSFORMS_TO(pi,CutFreeProof(pi))
    ∧ PRESERVES(CutElimination,EndSequent(pi))

DEFINE PROOF_SCHEMA := {
    proof_id: unique_identifier,
    proof_system: ProofSystem,
    formal_language: FormalLanguage,
    axioms_used: SetOfFormula,
    premises: SetOfFormula,
    assumptions: ScopedAssumptionSet,
    steps: OrderedProofStepSequence,
    conclusion: Formula,
    verification_status: {
        valid,
        invalid,
        incomplete
    }
}

DEFINE PROOF_STEP_SCHEMA := {
    step_id: unique_identifier,
    position: integer_or_structural_position,
    formula: Formula,
    justification_type: {
        axiom,
        premise,
        assumption,
        inference
    },
    inference_rule: optional_InferenceRule,
    dependencies: SetOfStepIDs,
    side_conditions: SetOfConditions,
    scope: AssumptionScope
}

DEFINE JUSTIFICATION_MODEL := {
    axiom:
        "formula admitted directly by the formal system",
    premise:
        "formula supplied as an initial premise",
    assumption:
        "formula temporarily admitted within a controlled scope",
    inference:
        "formula obtained by applying a permitted rule to available dependencies"
}

DEFINE PROOF_VALIDITY_MODEL := {
    local_validity:
        "every step is correctly justified",
    dependency_validity:
        "every cited dependency exists, precedes the dependent step and is in scope",
    scope_validity:
        "assumptions and discharges obey the proof system",
    global_validity:
        "the final target formula is reached through a sequence/tree of locally valid steps"
}

DEFINE PROOF_REPRESENTATIONS := {
    LinearProof: {
        structure: OrderedSequence
    },
    ProofTree: {
        structure: DirectedAcyclicTree
    },
    ProofDAG: {
        structure: DirectedAcyclicGraph,
        advantage:
            "shared subderivations may be represented once"
    },
    SequentProof: {
        structure:
            "tree of sequents linked by sequent-calculus rules"
    }
}

DEFINE EXAMPLE_1 := {
    proof_system: "Natural Deduction",
    premises: {
        "P",
        "P → Q"
    },
    steps: {
        "1. P       Premise",
        "2. P → Q   Premise",
        "3. Q       Modus Ponens 1,2"
    },
    conclusion: "Q",
    status: ValidProof
}

DEFINE EXAMPLE_2 := {
    assumption: "P",
    derivation: "Q",
    discharge_rule: ImplicationIntroduction,
    conclusion: "P → Q"
}

DEFINE EXAMPLE_3 := {
    candidate_steps: {
        "1. P",
        "2. Q"
    },
    claimed_rule_for_step_2: ModusPonens,
    missing_dependency: "P → Q",
    status: InvalidProof
}

DEFINE PROOF_PARSE_PIPELINE :=
    ProofArtifact
    -> IdentifyProofSystem
    -> IdentifyFormalLanguage
    -> ParseAxiomsPremisesAssumptions
    -> ParseSteps
    -> ParseJustifications
    -> ParseDependencies
    -> ParseScopes
    -> ParseConclusion
    -> ConstructTypedProofObject

DEFINE PROOF_VERIFICATION_PIPELINE :=
    TypedProofObject
    -> ValidateProofSystemMembership
    -> ValidateInitialSteps
    -> ValidateStepOrdering
    -> ForEachDerivedStep
       -> ResolveInferenceRule
       -> ResolveDependencies
       -> ValidateDependenciesAvailable
       -> ValidateRuleApplication
       -> ValidateSideConditions
    -> TrackAssumptionScopes
    -> ValidateDischarges
    -> VerifyFinalConclusion
    -> ClassifyProofStatus

DEFINE PROOF_GRAPH_PIPELINE :=
    Proof
    -> CreateFormulaNodes
    -> CreateRuleApplicationNodes
    -> AddDependencyEdges
    -> AddRuleEdges
    -> AddScopeEdges
    -> IdentifyRootPremises
    -> IdentifyConclusionNode
    -> ValidateAcyclicDependencyStructure
    -> ReturnProofGraph

DEFINE PROOF_SEARCH_PIPELINE :=
    GoalFormula
    -> SelectProofSystem
    -> SearchApplicableInferenceRules
    -> GenerateRequiredPremisesOrSubgoals
    -> RecursivelyExpandProofState
    -> MatchAxiomsPremisesAssumptions
    -> BacktrackInvalidBranches
    -> ConstructCandidateProof
    -> VerifyCandidateProof
    -> ReturnValidProof

DEFINE PROOF_TRANSFORMATION_PIPELINE :=
    ValidProof
    -> IdentifyTransformationTarget
    -> ApplyPermittedProofRewrite
    -> PreservePremisesOrAllowedContext
    -> PreserveConclusion
    -> ReverifyTransformedProof
    -> ReturnEquivalentOrNormalisedProof

DEFINE PROOF_GRAPH_MODEL := {
    node_types: {
        FormulaNode,
        RuleApplicationNode,
        AssumptionNode,
        PremiseNode,
        AxiomNode
    },
    edge_types: {
        DEPENDS_ON,
        USES_RULE,
        DERIVES,
        DISCHARGES,
        PRECEDES
    },
    invariants: {
        dependencies_resolved: TRUE,
        scope_respected: TRUE,
        rule_applications_valid: TRUE,
        conclusion_reachable: TRUE
    }
}

DEFINE ONTOLOGY_RELATIONS := {
    Proof IS_COMPONENT_OF ProofTheory,
    FormalProof IS_SUBTYPE_OF Proof,
    Proof CONTAINS ProofStep,
    Proof HAS_PREMISE Premise,
    Proof MAY_HAVE Assumption,
    Proof HAS_CONCLUSION Conclusion,
    ProofStep USES_RULE InferenceRule,
    ProofStep DEPENDS_ON EarlierProofStep,
    Derivation IS_REPRESENTED_BY Proof,
    Theorem IS_ESTABLISHED_BY ValidProof,
    Normalisation TRANSFORMS Proof,
    CutElimination TRANSFORMS SequentProof,
    ProofVerification DEPENDS_ON ProofSystem,
    ProofSearch PRODUCES CandidateProof
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "proof" <=> Proof WHEN formal_logic_context=TRUE,
    "formal proof" <=> FormalProof,
    "derivation" <=> Derivation WHEN proof_context=TRUE,
    "proof step" <=> ProofStep,
    "justification" <=> Justification,
    "proof tree" <=> ProofTree,
    "proof verification" <=> ProofVerification,
    "proof checking" <=> ProofVerification,
    "proof search" <=> ProofSearch
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation, verification, search and transformation of formal proofs",
    preserve_proof_identity: TRUE,
    preserve_proof_system_identity: TRUE,
    preserve_step_identity: TRUE,
    preserve_formula_identity: TRUE,
    preserve_step_order: TRUE,
    preserve_dependencies: TRUE,
    preserve_rule_identity: TRUE,
    preserve_assumption_scope: TRUE,
    track_discharges: TRUE,
    validate_rule_side_conditions: TRUE,
    construct_proof_graph: TRUE,
    classify_valid_invalid_incomplete: TRUE,
    support_recursive_proof_search: TRUE,
    support_proof_transformation: TRUE,
    reasoning_mode: "symbolic + structural + dependency-aware + scope-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    proof_structure_mapping: 0.99,
    proof_step_classification: 0.99,
    dependency_resolution: 0.99,
    assumption_scope_tracking: 0.99,
    rule_verification: proof_system_dependent,
    proof_status_classification: 0.99,
    proof_search_success: search_space_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        proof_as_derivation,
        ordered_or_structured_steps,
        step_justification,
        dependency_integrity,
        rule_system_membership,
        assumption_scope,
        conclusion_reachability
    },
    extensible_layers: {
        natural_deduction_proofs,
        sequent_proofs,
        Hilbert_proofs,
        resolution_proofs,
        tableau_proofs,
        type_theoretic_proofs,
        proof_certificates,
        proof_assistant_formats,
        compressed_proofs,
        automated_proof_search
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + PROOF_SCHEMA
    + PROOF_STEP_SCHEMA
    + JUSTIFICATION_MODEL
    + PROOF_VALIDITY_MODEL
    + PROOF_REPRESENTATIONS
    + PROOF_PARSE_PIPELINE
    + PROOF_VERIFICATION_PIPELINE
    + PROOF_GRAPH_PIPELINE
    + PROOF_SEARCH_PIPELINE
    + PROOF_TRANSFORMATION_PIPELINE
    + PROOF_GRAPH_MODEL
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: ProofOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/proof-theory/proof-ontology.html",
    parent_domain: ProofTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: Proof,
    proof_verification_enabled: TRUE,
    dependency_reasoning_enabled: TRUE,
    scope_reasoning_enabled: TRUE,
    proof_graph_enabled: TRUE,
    proof_search_enabled: TRUE,
    transformation_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    flow_complete: TRUE
}

END_FLOW