Base Case Ontology

FLOW ALGEBRA
TITLE: Base Case Ontology
VERSION: 1.0
DATE: 2026-10-14
DOMAIN: Mathematical Entities / Recursive Mathematical Entities
SOURCE: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/recursive-mathematical-entities/base-case-ontology.html
SOURCE_ALIGNMENT: Pending direct verification of webpage content
AUTHORS: Mark Higgins — Sky (Recursive AI)

1. PURPOSE
Define a typed, testable semantic representation of base cases in recursive functions, relations, sequences, proofs and data structures. A base case is a directly specified or independently decidable condition that supplies a result without invoking the same recursive dependency.

2. TYPED ENTITIES
entity BaseCase {
  id: URI
  belongs_to: RecursiveDefinition
  predicate: Predicate<Input>
  result: Value | Proposition | Structure
  priority: Integer? 
  evidence: Provenance?
}
entity RecursiveDefinition {
  id: URI
  input_domain: Set
  output_codomain: Set
  base_cases: Set<B-aseCase>
  recursive_rules: Set<RecursiveRule>
  evaluation_semantics: Semantics
}
entity RecursiveRule {
  applicability: Predicate<Input>
  dependencies: List<Input>
  combination: Operator
  measure: WellFoundedMeasure?
}
entity WellFoundedMeasure {
  rank: Input -> OrderedSet
  order: WellFoundedRelation
}
entity EvaluationTrace {
  input: Input
  selected_rule: BaseCase | RecursiveRule
  dependencies: List<EvaluationTrace>
  result: Value
}

3. RELATIONSHIPS
BaseCase --belongs_to--> RecursiveDefinition
BaseCase --matches--> Input
BaseCase --returns--> Value
RecursiveRule --reduces_to--> Input
RecursiveDefinition --evaluates_via--> EvaluationTrace
WellFoundedMeasure --certifies_decrease_of--> RecursiveRule

4. FORMAL SEMANTICS
For recursive F:D -> C with base predicate B and base expression b:
  F(x) = b(x)                         if B(x)
  F(x) = R(x,F(g1(x)),...,F(gk(x)))  otherwise
Base branch evaluation must not recursively invoke F. A complete, deterministic definition requires consistent handling of overlapping base predicates and an applicable rule for every intended input. Base-case presence alone does NOT prove termination: every reachable recursive path must eventually reach a base case, commonly established by a strictly decreasing well-founded measure.

5. INFERENCE RULES
RULE BASE_EVALUATE:
  IF B(x) = true AND b(x) is defined
  THEN F(x) := b(x), with no recursive expansion.
RULE RECURSIVE_EVALUATE:
  IF no base predicate matches x AND recursive rule applies
  THEN evaluate dependencies and combine results, subject to semantics.
RULE TERMINATION_CERTIFICATE:
  IF each recursive dependency y has rank(y) < rank(x) in a well-founded order AND base cases cover minimal reachable inputs
  THEN evaluation terminates for inputs in the certified domain (assuming finite branching and terminating local computations).
RULE INDUCTION_ANCHOR:
  IF property P holds for base constructors AND inductive step preserves P
  THEN P holds for all finitely generated objects in the inductive domain.

6. VALIDATION CONSTRAINTS
V01: Every base case has a typed input predicate and a result in the declared codomain.
V02: Base-case evaluation has no same-definition recursive call.
V03: Overlapping base cases must agree or have explicitly defined priority.
V04: Recursive branches must be defined for all intended non-base inputs.
V05: A termination claim requires a proof or certificate; do not infer it solely from base-case existence.
V06: Distinguish base cases for structural induction from initial conditions for recurrences when their roles differ.
V07: Reject cyclic evaluation traces lacking an explicitly defined fixed-point or coinductive semantics.

7. WORKED EXAMPLES
EXAMPLE A: Factorial on natural numbers
  F(0)=1; F(n)=n*F(n-1) for n>0.
  BaseCase: predicate n=0; result 1.
  Measure: n in natural numbers; decreases by one.
  Trace: F(3)=3*F(2)=3*2*F(1)=3*2*1*F(0)=6.
EXAMPLE B: Fibonacci
  Fib(0)=0; Fib(1)=1; Fib(n)=Fib(n-1)+Fib(n-2) for n>=2.
  Two base cases, both needed for this recurrence.
EXAMPLE C: Recursive list length
  len([])=0; len(head::tail)=1+len(tail).
  Structural base case: empty list; structural measure: list length.
EXAMPLE D: Nonterminating counterexample
  G(0)=0; G(n)=G(n+1) for n>0.
  A base case exists but positive inputs never reach it.

8. SEMANTIC_EQUIVALENCE
base_case ~ recursion_anchor (context: inductive recursive evaluation)
base_case != termination_proof
base_case != recursive_step
base_case != initial_condition (not universally interchangeable)

9. CONFIDENCE
formal_definitions: HIGH
worked_examples: HIGH
source_page_alignment: UNVERIFIED
Avoid treating confidence as a statistical probability without a calibrated evidence model.

10. FLOW_HASH
canonicalisation: UTF-8; LF line endings; stable key ordering; normalised identifiers
algorithm: SHA-256
value: COMPUTE_ON_INGEST (no fabricated digest)

11. UPDATE_MODEL
version_policy: semantic versioning
change_triggers: formal correction; new examples; source-page alignment; ontology cross-links
provenance_required: true

12. AI_CONSUMPTION
inputs: recursive definition, domain, base predicates, recursive rules, optional ranking function
outputs: typed graph, base-case match, evaluation trace, coverage diagnostics, termination status
safety: distinguish PROVED, REFUTED and UNKNOWN termination states
reasoning: prioritise type checks, branch consistency, reachable-case analysis and proof obligations
cross_links: Recursive Definition; Recursive Function; Recursive Relation; Recursive Sequence Entity; Recursive Structure; Fixed Point; Recursive Model

END FLOW ALGEBRA