Bound Variable Ontology

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

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

FLOW_ALGEBRA BoundVariableOntology_v1.0

BEGIN_FLOW

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

DEFINE ENTITY_TYPES := {
    BOUND_VARIABLE,
    VARIABLE,
    VARIABLE_OCCURRENCE,
    FORMULA,
    TERM,
    PREDICATE,
    QUANTIFIER,
    BINDER,
    SCOPE,
    DOMAIN,
    ASSIGNMENT,
    INTERPRETATION,
    SUBSTITUTION,
    SEMANTIC_OBJECT
}

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

SET BoundVariable.type = BOUND_VARIABLE
SET BoundVariable.parent = Variable
SET BoundVariable.context = PredicateLogic
SET BoundVariable.role =
    "represent a variable occurrence governed by an applicable quantifier or other binder within a defined syntactic scope"

RULE universal_bound_occurrence:
    Formula(∀x phi)
    ∧ VariableOccurrence(x_i)
    ∧ OCCURS_IN(x_i,phi)
    ∧ x_i within Scope(∀x)
    -> BoundOccurrence(x_i)
    ∧ IS_BOUND_IN(x_i,phi)
    ∧ GOVERNED_BY(x_i,∀x)

RULE existential_bound_occurrence:
    Formula(∃x phi)
    ∧ VariableOccurrence(x_i)
    ∧ OCCURS_IN(x_i,phi)
    ∧ x_i within Scope(∃x)
    -> BoundOccurrence(x_i)
    ∧ IS_BOUND_IN(x_i,phi)
    ∧ GOVERNED_BY(x_i,∃x)

RULE nearest_binder:
    VariableOccurrence(x_i)
    ∧ candidate_binders = {
        b | BINDS(b,x)
        ∧ x_i within Scope(b)
    }
    -> GOVERNED_BY(x_i, nearest(candidate_binders))

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

RULE free_exclusion:
    VariableOccurrence(x_i)
    ∧ IS_BOUND_IN(x_i,phi)
    -> NOT IS_FREE_IN(x_i,phi)

RULE quantifier_binding:
    Quantifier(q)
    ∧ Variable(x)
    ∧ Formula(phi)
    -> Formula(q x phi)
    ∧ BINDS(q,x)
    ∧ HAS_SCOPE(q,phi)

RULE universal_range:
    Formula(∀x phi)
    ∧ DomainOfDiscourse(D)
    -> RANGES_OVER(x,D)

RULE existential_range:
    Formula(∃x phi)
    ∧ DomainOfDiscourse(D)
    -> RANGES_OVER(x,D)

RULE bound_assignment_variation:
    Model(M)
    ∧ Assignment(g)
    ∧ Formula(∀x phi)
    -> evaluate phi under assignments g[x:=d]
       FOR_ALL d IN Domain(M)

RULE existential_bound_assignment:
    Model(M)
    ∧ Assignment(g)
    ∧ Formula(∃x phi)
    -> evaluate phi under assignments g[x:=d]
       UNTIL satisfying d exists
       OR domain exhausted

RULE shadowing:
    Binder(b1,x)
    ∧ Binder(b2,x)
    ∧ Scope(b2) subset_of Scope(b1)
    -> b2 SHADOWS b1 within Scope(b2)

RULE bound_variable_renaming:
    Formula(q x phi)
    ∧ Variable(y)
    ∧ y fresh_for(phi)
    -> AlphaConvert(q x phi,x,y)
    -> Formula(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)

RULE substitution_protection:
    Formula(phi)
    ∧ BoundOccurrence(x_i)
    -> ordinary_free_substitution DOES_NOT_REPLACE x_i

RULE capture_detection:
    Formula(phi)
    ∧ Term(t)
    ∧ Variable(y)
    ∧ y free_in(t)
    ∧ substitution_moves_y_under_binder_for_y
    -> VariableCapture(y)

RULE capture_avoidance:
    VariableCapturePossible(y)
    -> AlphaRenameConflictingBinder(y)
    -> PerformSubstitution
    -> AVOIDS_CAPTURE(Substitution,y)

DEFINE BOUND_VARIABLE_STRUCTURE := {
    binder: Quantifier,
    bound_symbol: Variable,
    governed_occurrences: BoundOccurrence,
    scope: Formula,
    domain: DomainOfDiscourse,
    governing_rule:
        "each occurrence is bound by the nearest applicable binder for the same variable symbol"
}

DEFINE BOUND_FREE_DISTINCTION := {
    BoundOccurrence:
        "an occurrence within the scope of an applicable binder",
    FreeOccurrence:
        "an occurrence not within the scope of an applicable binder",
    note:
        "the same variable symbol may have both bound and free occurrences in a larger formula"
}

DEFINE EXAMPLE_1 := {
    formula: "∀x Human(x)",
    binder: "∀x",
    bound_variable: x,
    bound_occurrence: "x in Human(x)"
}

DEFINE EXAMPLE_2 := {
    formula: "∃x Prime(x)",
    binder: "∃x",
    bound_variable: x,
    bound_occurrence: "x in Prime(x)"
}

DEFINE EXAMPLE_3 := {
    formula: "∀x R(x,y)",
    bound_variables: {x},
    free_variables: {y}
}

DEFINE EXAMPLE_4 := {
    formula: "P(x) ∧ ∃x Q(x)",
    occurrence_1: {
        expression: "x in P(x)",
        state: FreeOccurrence
    },
    occurrence_2: {
        expression: "x in Q(x)",
        state: BoundOccurrence,
        binder: "∃x"
    }
}

DEFINE EXAMPLE_5 := {
    formula: "∀x(P(x) ∧ ∃x Q(x))",
    outer_binder: "∀x",
    inner_binder: "∃x",
    outer_scope_occurrence: "x in P(x)",
    inner_scope_occurrence: "x in Q(x)",
    property: Shadowing
}

DEFINE EXAMPLE_ALPHA := {
    formula_A: "∀x P(x)",
    formula_B: "∀z P(z)",
    relation: AlphaEquivalence,
    semantic_difference_due_to_bound_name: NONE
}

DEFINE SEMANTIC_PIPELINE :=
    Formula
    -> ParseSyntaxTree
    -> IdentifyQuantifiersAndBinders
    -> IdentifyVariableOccurrences
    -> ComputeBinderScopes
    -> MatchEachOccurrenceToNearestApplicableBinder
    -> MarkBoundOccurrences
    -> ResolveShadowing
    -> AssociateBoundVariablesWithDomain
    -> PreserveBindingDuringEvaluation

DEFINE RENAMING_PIPELINE :=
    BoundFormula
    -> SelectBoundVariable
    -> GenerateFreshVariable
    -> RenameBinder
    -> RenameExactlyGovernedOccurrences
    -> PreserveFreeOccurrences
    -> VerifyNoCapture
    -> EstablishAlphaEquivalence

DEFINE REASONING_PIPELINE :=
    InputLogicalExpression
    -> ParseFormulaStructure
    -> DetectBinders
    -> ResolveScopes
    -> ResolveBoundOccurrences
    -> ResolveShadowing
    -> DistinguishBoundFromFreeVariables
    -> PreserveBindingsDuringSubstitution
    -> EvaluateQuantifiedFormula
    -> ReturnBindingAwareRepresentation

DEFINE ONTOLOGY_RELATIONS := {
    BoundVariable IS_SUBTYPE_OF Variable,
    BoundVariable IS_COMPONENT_OF PredicateLogicSyntax,
    UniversalQuantifier BINDS Variable,
    ExistentialQuantifier BINDS Variable,
    Quantifier HAS_SCOPE Formula,
    BoundOccurrence IS_BOUND_IN Formula,
    BoundOccurrence GOVERNED_BY Binder,
    BoundVariable RANGES_OVER DomainOfDiscourse,
    InnerBinder SHADOWS OuterBinder WHEN same_variable_symbol=TRUE,
    AlphaConversion RENAMES BoundVariable,
    CaptureAvoidingSubstitution AVOIDS_CAPTURE BoundVariable,
    FormulaEvaluation DEPENDS_ON VariableBinding
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "bound variable" <=> BoundVariable,
    "bound occurrence" <=> BoundOccurrence,
    "quantified variable" <=> BoundVariable WHEN quantifier_context=TRUE,
    "dummy variable" <=> BoundVariable WHEN renaming_context=TRUE,
    "bound name" <=> BoundVariable WHEN alpha_equivalence_context=TRUE
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation and resolution of bound variables in predicate logic",
    preserve_variable_symbol: TRUE,
    preserve_occurrence_identity: TRUE,
    preserve_binder_identity: TRUE,
    preserve_scope: TRUE,
    resolve_nearest_applicable_binder: TRUE,
    detect_shadowing: TRUE,
    distinguish_bound_free_occurrences: TRUE,
    preserve_domain_ranging: TRUE,
    protect_bound_occurrences_from_free_substitution: TRUE,
    detect_variable_capture: TRUE,
    support_alpha_conversion: TRUE,
    recognise_alpha_equivalence: TRUE,
    reasoning_mode: "symbolic + scope-aware + binding-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    formal_bound_variable_detection: 0.99,
    binder_resolution: 0.99,
    scope_resolution: 0.99,
    shadowing_detection: 0.99,
    alpha_equivalence_detection: 0.99,
    capture_detection: 0.99,
    natural_language_binding_mapping: context_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        bound_occurrence_definition,
        binder_scope_relation,
        nearest_binder_resolution,
        bound_free_distinction,
        shadowing,
        alpha_renaming,
        capture_avoidance
    },
    extensible_layers: {
        lambda_calculus_bound_variables,
        typed_logic_binding,
        many_sorted_binding,
        higher_order_binding,
        modal_binding,
        temporal_binding,
        proof_assistant_variable_models
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + BOUND_VARIABLE_STRUCTURE
    + BOUND_FREE_DISTINCTION
    + SEMANTIC_PIPELINE
    + RENAMING_PIPELINE
    + REASONING_PIPELINE
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

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

END_FLOW