Free Variable Ontology

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

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

FLOW_ALGEBRA FreeVariableOntology_v1.0

BEGIN_FLOW

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

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

DEFINE RELATION_TYPES := {
    OCCURS_IN,
    IS_FREE_IN,
    IS_BOUND_IN,
    BINDS,
    HAS_SCOPE,
    RANGES_OVER,
    ASSIGNED_BY,
    SUBSTITUTES_FOR,
    CAPTURED_BY,
    DEPENDS_ON,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF,
    TRANSFORMS
}

SET FreeVariable.type = FREE_VARIABLE
SET FreeVariable.parent = Variable
SET FreeVariable.context = PredicateLogic
SET FreeVariable.role =
    "represent a variable occurrence that is not governed by an applicable quantifier or other binder within the formula in which it occurs"

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_occurrence_exclusion:
    VariableOccurrence(x_i)
    ∧ IS_BOUND_IN(x_i,phi)
    -> NOT IS_FREE_IN(x_i,phi)

RULE free_variable_set:
    Formula(phi)
    -> FV(phi) = {
        x | EXISTS occurrence x_i [
            IS_FREE_IN(x_i,phi)
            ∧ same_variable_symbol(x_i,x)
        ]
    }

RULE variable_term:
    Variable(x)
    -> FV(x) = {x}

RULE constant_term:
    Constant(c)
    -> FV(c) = {}

RULE function_term:
    Term(f(t1,...,tn))
    -> FV(f(t1,...,tn))
       = UNION(FV(t1),...,FV(tn))

RULE atomic_formula:
    Formula(P(t1,...,tn))
    -> FV(P(t1,...,tn))
       = UNION(FV(t1),...,FV(tn))

RULE negation:
    Formula(phi)
    -> FV(¬phi) = FV(phi)

RULE binary_connective:
    Formula(phi)
    ∧ Formula(psi)
    ∧ connective op IN {∧,∨,→,↔}
    -> FV(phi op psi)
       = FV(phi) UNION FV(psi)

RULE universal_quantification:
    Formula(phi)
    ∧ Variable(x)
    -> FV(∀x phi)
       = FV(phi) \ {x}

RULE existential_quantification:
    Formula(phi)
    ∧ Variable(x)
    -> FV(∃x phi)
       = FV(phi) \ {x}

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

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

RULE sentence:
    Formula(phi)
    ∧ FV(phi) = ∅
    -> Sentence(phi)

RULE assignment_dependence:
    Formula(phi)
    ∧ x ∈ FV(phi)
    -> Evaluation(phi)
       MAY_DEPEND_ON
       Assignment(x)

RULE substitution_target:
    Formula(phi)
    ∧ x ∈ FV(phi)
    ∧ Term(t)
    -> SUBSTITUTE_FREE_OCCURRENCES(phi,x,t)

RULE capture_risk:
    Formula(phi)
    ∧ x ∈ FV(phi)
    ∧ Term(t)
    ∧ EXISTS y [
        y ∈ FV(t)
        ∧ substitution_places_y_inside_scope_of_binder_for_y
    ]
    -> VariableCaptureRisk(y)

RULE capture_avoiding_substitution:
    VariableCaptureRisk(y)
    -> AlphaRenameConflictingBinder(y)
    -> SUBSTITUTE_WITHOUT_CAPTURE(phi,x,t)

DEFINE FREE_VARIABLE_RECURSION := {
    "FV(x)" : "{x} when x is a variable",
    "FV(c)" : "∅ when c is a constant",
    "FV(P(t1,...,tn))" : "FV(t1) ∪ ... ∪ FV(tn)",
    "FV(¬φ)" : "FV(φ)",
    "FV(φ ∧ ψ)" : "FV(φ) ∪ FV(ψ)",
    "FV(φ ∨ ψ)" : "FV(φ) ∪ FV(ψ)",
    "FV(φ → ψ)" : "FV(φ) ∪ FV(ψ)",
    "FV(φ ↔ ψ)" : "FV(φ) ∪ FV(ψ)",
    "FV(∀x φ)" : "FV(φ) \ {x}",
    "FV(∃x φ)" : "FV(φ) \ {x}"
}

DEFINE OCCURRENCE_DISTINCTION := {
    variable_symbol:
        "the syntactic variable name such as x",
    variable_occurrence:
        "a particular occurrence of that symbol in an expression",
    free_occurrence:
        "an occurrence outside the scope of a binder for that variable",
    bound_occurrence:
        "an occurrence inside the applicable scope of a binder for that variable"
}

DEFINE EXAMPLE_1 := {
    formula: "Human(x) → Mortal(x)",
    free_variables: {x},
    formula_type: OpenFormula
}

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

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

DEFINE EXAMPLE_4 := {
    formula: "P(x) ∧ ∃x Q(x)",
    first_x: FreeOccurrence,
    second_x: BoundOccurrence,
    free_variables: {x},
    observation:
        "the same variable symbol can have free and bound occurrences in one formula"
}

DEFINE EXAMPLE_5 := {
    formula: "∀x(P(x,y) → ∃z R(y,z))",
    free_variables: {y},
    bound_variables: {x,z}
}

DEFINE SEMANTIC_PIPELINE :=
    Formula
    -> ParseSyntaxTree
    -> IdentifyVariableOccurrences
    -> IdentifyQuantifierBinders
    -> DetermineBinderScopes
    -> MatchOccurrencesToApplicableBinders
    -> MarkBoundOccurrences
    -> MarkRemainingOccurrencesAsFree
    -> ComputeFreeVariableSet
    -> DetermineOpenOrClosedStatus
    -> PreserveFreeVariablesForAssignmentBasedEvaluation

DEFINE SUBSTITUTION_PIPELINE :=
    Formula
    -> ComputeFreeVariableSet
    -> IdentifyTargetFreeVariable
    -> LocateFreeOccurrencesOnly
    -> InspectReplacementTerm
    -> DetectCaptureRisk
    -> AlphaRenameIfNecessary
    -> SubstituteFreeOccurrences
    -> RecomputeFreeVariableSet
    -> ValidateBindingIntegrity

DEFINE REASONING_PIPELINE :=
    InputExpression
    -> ParseFormula
    -> ResolveVariableBinding
    -> ComputeFreeVariables
    -> DetermineAssignmentDependencies
    -> DetermineFormulaClosure
    -> ValidateSubstitution
    -> PreserveScopeAndBinding
    -> EvaluateOrTransform

DEFINE ONTOLOGY_RELATIONS := {
    FreeVariable IS_SUBTYPE_OF Variable,
    FreeVariable IS_COMPONENT_OF PredicateLogicSyntax,
    FreeOccurrence OCCURS_IN Formula,
    FreeOccurrence IS_FREE_IN Formula,
    BoundOccurrence IS_BOUND_IN Formula,
    Quantifier BINDS Variable,
    Quantifier HAS_SCOPE Formula,
    OpenFormula DEPENDS_ON FreeVariable,
    FormulaEvaluation DEPENDS_ON Assignment WHEN free_variables_exist=TRUE,
    Substitution TARGETS FreeOccurrence,
    CaptureAvoidingSubstitution DEPENDS_ON FreeVariableAnalysis
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "free variable" <=> FreeVariable,
    "free occurrence" <=> FreeOccurrence,
    "unbound variable" <=> FreeVariable WHEN formal_logic_context=TRUE,
    "FV" <=> FreeVariableSet WHEN formula_analysis_context=TRUE,
    "free variables of φ" <=> FV(phi)
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation and detection of free variables in predicate logic",
    preserve_variable_symbol: TRUE,
    preserve_occurrence_identity: TRUE,
    preserve_scope: TRUE,
    distinguish_free_bound_occurrences: TRUE,
    compute_free_variable_sets_recursively: TRUE,
    detect_open_formulas: TRUE,
    track_assignment_dependencies: TRUE,
    restrict_substitution_to_free_occurrences: TRUE,
    detect_variable_capture_risk: TRUE,
    support_capture_avoiding_substitution: TRUE,
    reasoning_mode: "symbolic + recursive + scope-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    formal_free_variable_detection: 0.99,
    recursive_FV_computation: 0.99,
    open_closed_formula_classification: 0.99,
    substitution_target_detection: 0.99,
    capture_risk_detection: 0.99,
    natural_language_variable_mapping: context_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        free_occurrence_definition,
        free_variable_set_recursion,
        bound_free_distinction,
        open_formula_relation,
        assignment_dependence,
        substitution_free_occurrence_constraint
    },
    extensible_layers: {
        lambda_calculus_free_variables,
        typed_logic_free_variables,
        many_sorted_free_variables,
        higher_order_free_variables,
        modal_formula_free_variables,
        computational_static_analysis
    }
}

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

FLOW_HASH := HASH(FLOW_HASH_INPUT)

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

END_FLOW