Variable Binding Ontology

KIRETH RESEARCH — SEMANTIC LIBRARY
AI CORE → ONTOLOGIES → MATHEMATICAL ONTOLOGIES → MATHEMATICAL LOGIC ONTOLOGIES
PREDICATE LOGIC → VARIABLE BINDING ONTOLOGY

Canonical URL:
https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/predicate-logic/variable-binding-ontology.html

FLOW_ALGEBRA VariableBindingOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN VariableBindingOntology := {
    VariableBinding,
    PredicateLogic,
    Variable,
    BoundVariable,
    FreeVariable,
    VariableOccurrence,
    BoundOccurrence,
    FreeOccurrence,
    Quantifier,
    UniversalQuantifier,
    ExistentialQuantifier,
    Formula,
    OpenFormula,
    ClosedFormula,
    Scope,
    BindingScope,
    Binder,
    Term,
    Predicate,
    Substitution,
    Capture,
    VariableCapture,
    CaptureAvoidingSubstitution,
    AlphaConversion,
    AlphaEquivalence,
    Renaming,
    Assignment,
    DomainOfDiscourse,
    Interpretation,
    Model
}

DEFINE ENTITY_TYPES := {
    BINDING,
    VARIABLE,
    VARIABLE_OCCURRENCE,
    QUANTIFIER,
    BINDER,
    FORMULA,
    SCOPE,
    TERM,
    SUBSTITUTION,
    ASSIGNMENT,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    BINDS,
    HAS_BINDER,
    HAS_SCOPE,
    OCCURS_IN,
    IS_BOUND_IN,
    IS_FREE_IN,
    GOVERNS,
    RANGES_OVER,
    SUBSTITUTES_FOR,
    RENAMES,
    CAPTURES,
    AVOIDS_CAPTURE,
    ALPHA_EQUIVALENT_TO,
    DEPENDS_ON,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF
}

SET VariableBinding.type = BINDING
SET VariableBinding.context = PredicateLogic
SET VariableBinding.role =
    "associate a variable occurrence with the logical operator that governs its interpretation within a defined scope"

RULE universal_binding:
    Formula(∀x phi)
    -> BINDS(∀,x)
    ∧ HAS_SCOPE(∀,phi)

RULE existential_binding:
    Formula(∃x phi)
    -> BINDS(∃,x)
    ∧ HAS_SCOPE(∃,phi)

RULE bound_occurrence:
    VariableOccurrence(x_i)
    ∧ OCCURS_IN(x_i,phi)
    ∧ EXISTS binder b [
        BINDS(b,x)
        ∧ x_i within Scope(b)
        ∧ same_variable_symbol(x_i,x)
    ]
    -> BoundOccurrence(x_i)
    ∧ IS_BOUND_IN(x_i,phi)

RULE free_occurrence:
    VariableOccurrence(x_i)
    ∧ OCCURS_IN(x_i,phi)
    ∧ NOT EXISTS binder b [
        BINDS(b,x)
        ∧ x_i within Scope(b)
        ∧ same_variable_symbol(x_i,x)
    ]
    -> FreeOccurrence(x_i)
    ∧ IS_FREE_IN(x_i,phi)

RULE bound_variable:
    Variable(x)
    ∧ EXISTS occurrence x_i [
        BoundOccurrence(x_i)
        ∧ same_variable_symbol(x_i,x)
    ]
    -> BoundVariable(x)

RULE free_variable:
    Variable(x)
    ∧ EXISTS occurrence x_i [
        FreeOccurrence(x_i)
        ∧ same_variable_symbol(x_i,x)
    ]
    -> FreeVariable(x)

RULE closed_formula:
    Formula(phi)
    ∧ FreeVariables(phi) = ∅
    -> ClosedFormula(phi)

RULE open_formula:
    Formula(phi)
    ∧ FreeVariables(phi) != ∅
    -> OpenFormula(phi)

RULE nested_binding:
    Formula(q1 x (... q2 x psi ...))
    ∧ Scope(q2) subset_of Scope(q1)
    -> occurrences_of(x) within Scope(q2)
       governed_by nearest_applicable_binder(q2)

RULE shadowing:
    Binder(q1,x)
    ∧ Binder(q2,x)
    ∧ q2 nested_within q1
    -> q2 SHADOWS q1
       within Scope(q2)

RULE substitution:
    Formula(phi)
    ∧ Variable(x)
    ∧ Term(t)
    -> SUBSTITUTE(phi,x,t) = phi[x:=t]

RULE free_for_substitution:
    Term(t)
    ∧ Variable(x)
    ∧ Formula(phi)
    ∧ no_free_variable_of(t)_becomes_bound_in(phi[x:=t])
    -> FreeFor(t,x,phi)

RULE variable_capture:
    Formula(phi)
    ∧ SUBSTITUTE(phi,x,t)
    ∧ EXISTS variable y [
        y free_in(t)
        ∧ y becomes_bound_after_substitution
    ]
    -> VariableCapture(y)

RULE capture_avoiding_substitution:
    VariableCapturePossible(phi,x,t)
    -> AlphaRenameConflictingBinders(phi)
    -> SUBSTITUTE_WITHOUT_CAPTURE(phi,x,t)

RULE alpha_conversion:
    Formula(q x phi)
    ∧ Variable(y)
    ∧ y fresh_for(phi)
    -> AlphaRename(q x phi, x, y)
    -> q y phi[x:=y]

RULE alpha_equivalence:
    Formula(phi)
    ∧ Formula(psi)
    ∧ differ_only_by_consistent_renaming_of_bound_variables(phi,psi)
    -> ALPHA_EQUIVALENT_TO(phi,psi)

DEFINE BINDING_STRUCTURE := {
    binder: Quantifier,
    variable: Variable,
    scope: Formula,
    relation: BINDS,
    constraint:
        "a binder governs matching variable occurrences only inside its scope unless shadowed by a nearer binder"
}

DEFINE VARIABLE_STATE_MODEL := {
    BoundOccurrence:
        "an occurrence governed by an applicable binder",
    FreeOccurrence:
        "an occurrence not governed by an applicable binder",
    BoundVariable:
        "a variable having at least one bound occurrence in the relevant expression",
    FreeVariable:
        "a variable having at least one free occurrence in the relevant expression"
}

DEFINE EXAMPLE_1 := {
    formula: "∀x Human(x)",
    binder: "∀x",
    occurrence: "x in Human(x)",
    state: BoundOccurrence
}

DEFINE EXAMPLE_2 := {
    formula: "Human(x) → Mortal(x)",
    occurrences: {"x","x"},
    state: FreeOccurrence,
    formula_type: OpenFormula
}

DEFINE EXAMPLE_3 := {
    formula: "∀x(Human(x) → Mortal(x))",
    free_variables: {},
    formula_type: ClosedFormula
}

DEFINE EXAMPLE_4 := {
    formula: "∀x(P(x) ∧ ∃x Q(x))",
    outer_binding: "∀x governs x in P(x)",
    inner_binding: "∃x governs x in Q(x)",
    property: "inner binder shadows outer binder within its scope"
}

DEFINE EXAMPLE_CAPTURE := {
    original_formula: "∀y R(x,y)",
    substitution: "x := y",
    unsafe_result: "∀y R(y,y)",
    issue: VariableCapture,
    required_operation: CaptureAvoidingSubstitution
}

DEFINE EXAMPLE_ALPHA_CONVERSION := {
    original: "∀x P(x)",
    renamed: "∀z P(z)",
    relation: AlphaEquivalence
}

DEFINE SEMANTIC_PIPELINE :=
    Formula
    -> ParseSyntaxTree
    -> IdentifyVariableOccurrences
    -> IdentifyBinders
    -> DetermineBinderScopes
    -> MatchOccurrencesToNearestApplicableBinder
    -> ClassifyBoundOccurrences
    -> ClassifyFreeOccurrences
    -> ComputeFreeVariableSet
    -> DetermineOpenOrClosedFormula
    -> PreserveBindingStructureForEvaluation

DEFINE SUBSTITUTION_PIPELINE :=
    Formula
    -> IdentifyTargetFreeOccurrences
    -> InspectReplacementTermFreeVariables
    -> DetectConflictingBinders
    -> IF conflict
       THEN AlphaRenameConflictingBinders
    -> ReplaceTargetOccurrences
    -> VerifyNoVariableCapture
    -> ReturnCaptureSafeFormula

DEFINE REASONING_PIPELINE :=
    InputLogicalExpression
    -> ParseQuantifierStructure
    -> ResolveScopes
    -> TrackVariableIdentity
    -> ResolveShadowing
    -> ClassifyOccurrences
    -> ValidateSubstitutionSafety
    -> PreserveBindingDuringTransformation
    -> EvaluateOrInfer

DEFINE ONTOLOGY_RELATIONS := {
    VariableBinding IS_COMPONENT_OF PredicateLogic,
    Quantifier IS_SUBTYPE_OF Binder,
    UniversalQuantifier BINDS Variable,
    ExistentialQuantifier BINDS Variable,
    Binder HAS_SCOPE Formula,
    VariableOccurrence OCCURS_IN Formula,
    BoundOccurrence IS_BOUND_IN Formula,
    FreeOccurrence IS_FREE_IN Formula,
    Substitution DEPENDS_ON VariableBinding,
    CaptureAvoidingSubstitution AVOIDS_CAPTURE Variable,
    AlphaConversion RENAMES BoundVariable,
    AlphaEquivalentFormula ALPHA_EQUIVALENT_TO AlphaEquivalentFormula
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "variable binding" <=> VariableBinding,
    "bound occurrence" <=> BoundOccurrence,
    "free occurrence" <=> FreeOccurrence,
    "bound variable" <=> BoundVariable,
    "free variable" <=> FreeVariable,
    "capture-free substitution" <=> CaptureAvoidingSubstitution,
    "alpha conversion" <=> AlphaConversion,
    "alpha renaming" <=> AlphaConversion
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation of variable binding and scope in predicate logic",
    preserve_variable_identity: TRUE,
    preserve_occurrence_identity: TRUE,
    preserve_binder_identity: TRUE,
    preserve_scope: TRUE,
    resolve_nearest_binder: TRUE,
    detect_shadowing: TRUE,
    distinguish_free_bound_occurrences: TRUE,
    detect_variable_capture: TRUE,
    require_capture_avoiding_substitution: TRUE,
    recognise_alpha_equivalence: TRUE,
    reasoning_mode: "symbolic + scope-aware + substitution-safe"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    formal_binding_resolution: 0.99,
    bound_free_classification: 0.99,
    scope_resolution_formal_language: 0.99,
    capture_detection: 0.99,
    alpha_equivalence_detection: 0.99,
    natural_language_binding_mapping: context_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        binder_variable_relation,
        lexical_scope,
        bound_free_distinction,
        nearest_binder_resolution,
        capture_avoidance,
        alpha_equivalence
    },
    extensible_layers: {
        lambda_calculus_binding,
        typed_variable_binding,
        many_sorted_binding,
        higher_order_binding,
        modal_binding,
        computational_scope_analysis,
        proof_assistant_binding_models
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + BINDING_STRUCTURE
    + VARIABLE_STATE_MODEL
    + SEMANTIC_PIPELINE
    + SUBSTITUTION_PIPELINE
    + REASONING_PIPELINE
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: VariableBindingOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/predicate-logic/variable-binding-ontology.html",
    parent_domain: PredicateLogic,
    semantic_domain: MathematicalLogic,
    primary_entity: VariableBinding,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    scope_sensitive: TRUE,
    substitution_safe: TRUE,
    flow_complete: TRUE
}

END_FLOW