Proof Theory

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

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

FLOW_ALGEBRA ProofTheory_v1.0

BEGIN_FLOW

DEFINE DOMAIN ProofTheory := {
    ProofTheory,
    FormalProof,
    Proof,
    Derivation,
    FormalSystem,
    FormalLanguage,
    Syntax,
    Formula,
    WellFormedFormula,
    Sentence,
    Proposition,
    Axiom,
    AxiomSchema,
    Premise,
    Assumption,
    Hypothesis,
    Conclusion,
    Theorem,
    Lemma,
    Corollary,
    Inference,
    InferenceRule,
    Deduction,
    ProofStep,
    ProofTree,
    DerivationSequence,
    NaturalDeduction,
    SequentCalculus,
    HilbertSystem,
    Resolution,
    Tableau,
    Sequent,
    Antecedent,
    Succedent,
    StructuralRule,
    LogicalRule,
    CutRule,
    CutElimination,
    Normalisation,
    NormalForm,
    Consistency,
    Completeness,
    Soundness,
    Decidability,
    Provability,
    Derivability,
    Metatheorem,
    ProofSystem,
    ProofCalculus,
    ProofSearch,
    AutomatedTheoremProving,
    ConstructiveProof,
    ClassicalProof,
    IntuitionisticProof,
    Induction,
    Contradiction,
    ReductioAdAbsurdum
}

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

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

SET ProofTheory.type = FORMAL_SYSTEM
SET ProofTheory.domain = MathematicalLogic
SET ProofTheory.role =
    "study formal proofs as mathematical objects, their rules, transformations, structural properties and relationships to formal systems"

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

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

RULE rule_application:
    InferenceRule(R)
    ∧ Premises(phi1,...,phin)
    ∧ Conclusion(psi)
    ∧ R(phi1,...,phin => psi)
    ∧ FOR_ALL i [DERIVES(Gamma,phii)]
    -> DERIVES(Gamma,psi)

RULE proof_definition:
    FiniteSequence(phi1,...,phin)
    ∧ FOR_ALL i [
        phii is axiom
        OR phii is premise
        OR phii follows_from_previous_steps_by_valid_rule
    ]
    -> FormalProof(phi1,...,phin)

RULE theorem:
    FormalSystem(S)
    ∧ DERIVES(S,phi)
    ∧ no_undischarged_assumptions(phi)
    -> Theorem(phi,S)

RULE derivability:
    PremiseSet(Gamma)
    ∧ Formula(phi)
    ∧ EXISTS formal_derivation d [
        d derives phi from Gamma
    ]
    -> Gamma ⊢ phi

RULE provability:
    FormalSystem(S)
    ∧ ∅ ⊢_S phi
    -> Provable_S(phi)

RULE modus_ponens:
    DERIVES(Gamma,phi)
    ∧ DERIVES(Gamma,phi -> psi)
    -> DERIVES(Gamma,psi)

RULE conjunction_introduction:
    DERIVES(Gamma,phi)
    ∧ DERIVES(Gamma,psi)
    -> DERIVES(Gamma,phi ∧ psi)

RULE conjunction_elimination_left:
    DERIVES(Gamma,phi ∧ psi)
    -> DERIVES(Gamma,phi)

RULE conjunction_elimination_right:
    DERIVES(Gamma,phi ∧ psi)
    -> DERIVES(Gamma,psi)

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

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

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

RULE proof_by_contradiction_classical:
    ClassicalSystem(S)
    ∧ DERIVES(Gamma ∪ {¬phi}, contradiction)
    -> DERIVES(Gamma,phi)

RULE induction_schema:
    DERIVES(Gamma,P(0))
    ∧ DERIVES(Gamma,∀n(P(n)->P(n+1)))
    -> DERIVES(Gamma,∀n P(n))
       WHEN arithmetic_induction_available=TRUE

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 syntactic_consistency:
    ProofSystem(S)
    ∧ NOT Provable_S(Contradiction)
    -> Consistent(S)

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

RULE cut_elimination:
    Proof(pi)
    ∧ contains_cut(pi)
    ∧ cut_elimination_applicable(pi)
    -> Transform(pi,pi_prime)
    ∧ cut_free(pi_prime)
    ∧ same_end_sequent(pi,pi_prime)

RULE normalisation:
    NaturalDeductionProof(pi)
    ∧ contains_reducible_detours(pi)
    -> NORMALISES_TO(pi,normal_form(pi))

DEFINE PROOF_OBJECT_MODEL := {
    proof: {
        input: {
            axioms,
            premises,
            assumptions,
            inference_rules
        },
        structure:
            "finite rule-governed derivation",
        output:
            Conclusion
    },
    validity_condition:
        "every non-initial proof step must follow from earlier available formulas by an admitted inference rule"
}

DEFINE DERIVABILITY_MODEL := {
    notation: "Γ ⊢ φ",
    meaning:
        "φ is syntactically derivable from premise set Γ in the specified proof system",
    system_sensitive: TRUE
}

DEFINE SEMANTIC_CONTRAST := {
    syntactic_consequence: "Γ ⊢ φ",
    semantic_consequence: "Γ ⊨ φ",
    soundness:
        "syntactic consequence implies semantic consequence",
    completeness:
        "semantic consequence implies syntactic consequence",
    critical_distinction:
        "proof theory primarily studies the syntactic derivation relation, although metatheory connects it to semantics"
}

DEFINE PROOF_SYSTEMS := {
    HilbertSystem: {
        structure:
            "axiom schemas plus a small collection of inference rules"
    },
    NaturalDeduction: {
        structure:
            "introduction and elimination rules corresponding to logical connectives and quantifiers"
    },
    SequentCalculus: {
        structure:
            "rules operating on sequents, typically separating structural and logical rules"
    },
    Resolution: {
        structure:
            "clause-based inference suited to refutation and automated theorem proving"
    },
    Tableau: {
        structure:
            "tree-based decomposition of formulas to test satisfiability or derive contradiction"
    }
}

DEFINE SEQUENT_MODEL := {
    notation: "Γ ⊢ Δ",
    antecedent: Gamma,
    succedent: Delta,
    interpretation:
        "formal judgement used as the basic proof object in sequent calculi"
}

DEFINE STRUCTURAL_RULES := {
    Weakening,
    Contraction,
    Exchange,
    Cut
}

DEFINE PROOF_TRANSFORMATIONS := {
    CutElimination,
    Normalisation,
    Reduction,
    PermutationOfRules,
    Substitution
}

DEFINE META_PROPERTIES := {
    Soundness,
    Completeness,
    Consistency,
    Decidability,
    Normalisation,
    CutElimination,
    Conservativity
}

DEFINE EXAMPLE_1 := {
    premises: {
        "P",
        "P → Q"
    },
    rule: ModusPonens,
    conclusion: "Q",
    derivability: "{P, P→Q} ⊢ Q"
}

DEFINE EXAMPLE_2 := {
    assumption: "P",
    derived: "Q",
    discharged_result: "P → Q",
    rule: ImplicationIntroduction
}

DEFINE EXAMPLE_3 := {
    premise: "∀x(Human(x) → Mortal(x))",
    premise_2: "Human(Socrates)",
    derived_1: "Human(Socrates) → Mortal(Socrates)",
    conclusion: "Mortal(Socrates)"
}

DEFINE EXAMPLE_4 := {
    proof_system: SequentCalculus,
    transformation: CutElimination,
    invariant:
        "the end sequent remains derivable after elimination of cuts"
}

DEFINE SYNTAX_PIPELINE :=
    FormalLanguage
    -> WellFormedFormulas
    -> AxiomsAndPremises
    -> InferenceRules
    -> ProofSteps
    -> Derivation
    -> Conclusion
    -> Theorem

DEFINE PROOF_VERIFICATION_PIPELINE :=
    CandidateProof
    -> ParseProofStructure
    -> IdentifyInitialAxiomsPremisesAssumptions
    -> ForEachProofStep
       -> IdentifyAppliedRule
       -> VerifyRulePremisesAvailable
       -> VerifyRuleSideConditions
       -> VerifyConclusionMatchesRule
    -> TrackAssumptionDischarge
    -> VerifyFinalConclusion
    -> Return ValidProof OR InvalidProof

DEFINE PROOF_SEARCH_PIPELINE :=
    GoalFormula
    -> SelectProofSystem
    -> IdentifyApplicableRules
    -> GenerateSubgoals
    -> ExploreDerivationSpace
    -> PruneInvalidBranches
    -> DetectAxiomPremiseOrClosure
    -> ConstructProofObject
    -> VerifyProof
    -> ReturnDerivation

DEFINE META_REASONING_PIPELINE :=
    ProofSystem
    -> FormaliseSyntaxAndRules
    -> DefineDerivability
    -> AnalyseStructuralProperties
    -> ProveSoundnessOrIdentifyFailure
    -> ProveCompletenessOrIdentifyLimits
    -> AnalyseConsistency
    -> AnalyseNormalisationAndCutElimination
    -> DetermineComputationalConsequences

DEFINE ONTOLOGY_RELATIONS := {
    ProofTheory IS_SUBTYPE_OF MathematicalLogic,
    FormalProof CONTAINS ProofStep,
    ProofStep USES_RULE InferenceRule,
    Proof HAS_CONCLUSION Formula,
    Derivation DEPENDS_ON Axiom,
    Derivation DEPENDS_ON Premise,
    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,
    CutElimination TRANSFORMS Proof,
    Normalisation TRANSFORMS Proof,
    Soundness RELATES Derivability TO SemanticConsequence,
    Completeness RELATES SemanticConsequence TO Derivability
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "proof theory" <=> ProofTheory,
    "formal proof" <=> FormalProof,
    "derivation" <=> Derivation,
    "provable" <=> Provability,
    "derivable" <=> Derivability,
    "turnstile" <=> "⊢" WHEN proof_theory_context=TRUE,
    "natural deduction" <=> NaturalDeduction,
    "sequent calculus" <=> SequentCalculus,
    "cut elimination" <=> CutElimination,
    "proof normalisation" <=> Normalisation
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation of formal proofs, derivations, inference systems and proof transformations",
    preserve_formula_identity: TRUE,
    preserve_proof_step_order: TRUE,
    preserve_rule_identity: TRUE,
    preserve_premise_dependencies: TRUE,
    preserve_assumption_scope: TRUE,
    track_assumption_discharge: TRUE,
    verify_rule_side_conditions: TRUE,
    distinguish_derivability_from_semantic_entailment: TRUE,
    support_proof_tree_representation: TRUE,
    support_proof_search: TRUE,
    support_cut_elimination_analysis: TRUE,
    support_normalisation_analysis: TRUE,
    reasoning_mode: "symbolic + syntactic + structural + meta-logical"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    formal_proof_structure: 0.99,
    rule_application_verification: rule_system_dependent,
    derivability_mapping: 0.99,
    natural_deduction_mapping: 0.99,
    sequent_calculus_mapping: 0.99,
    soundness_completeness_mapping: 0.99,
    automated_proof_search: search_space_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        formal_derivation,
        inference_rule_application,
        derivability_relation,
        proof_step_dependency,
        assumption_scope,
        syntactic_semantic_distinction
    },
    extensible_layers: {
        Hilbert_calculi,
        natural_deduction,
        sequent_calculi,
        resolution_calculi,
        tableaux,
        linear_logic_proof_theory,
        type_theoretic_proofs,
        ordinal_analysis,
        proof_complexity,
        automated_theorem_proving,
        proof_assistant_formalisations
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + PROOF_OBJECT_MODEL
    + DERIVABILITY_MODEL
    + SEMANTIC_CONTRAST
    + PROOF_SYSTEMS
    + SEQUENT_MODEL
    + STRUCTURAL_RULES
    + PROOF_TRANSFORMATIONS
    + META_PROPERTIES
    + SYNTAX_PIPELINE
    + PROOF_VERIFICATION_PIPELINE
    + PROOF_SEARCH_PIPELINE
    + META_REASONING_PIPELINE
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

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

END_FLOW