Relation Composition Ontology

FLOW ALGEBRA
RELATION COMPOSITION ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Relation Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/relation-entities/relation-composition-ontology-2.html
Authors: Mark Higgins — Sky (Recursive AI)
Version: 1.0 | 2026-10-13
Status: Formal mathematical synthesis; source webpage not independently verified.

01. PURPOSE
flow "RelationCompositionOntology" v1.0
  domain: mathematics.set_theory.relations
  intent: represent, compose, reason about, and validate binary relations
  semantics: classical two-valued set theory
  notation_policy: explicitly define composition orientation

02. ENTITY TYPES
  Set := collection of elements
  Element := member of a Set
  OrderedPair[A,B] := (a:A,b:B)
  BinaryRelation[A,B] := subset(A × B)
  CompositeRelation[A,C] := subset(A × C)
  Witness[B] := intermediate element proving composition membership
  IdentityRelation[A] := {(a,a) | a in A}
  InverseRelation[B,A] := {(b,a) | (a,b) in R}
  RelationChain := ordered list of composable relations
  RelationGraph := directed graph interpretation
  RelationMatrix := Boolean adjacency matrix interpretation

03. TYPED INPUTS
  input A:Set
  input B:Set
  input C:Set
  input R:BinaryRelation[A,B]
  input S:BinaryRelation[B,C]
  require all relation endpoints respect declared sets
  output T:BinaryRelation[A,C]

04. DEFINING OPERATION
  convention: S ∘ R means apply R first, then S
  T = S ∘ R
  (a,c) in T iff exists b in B: (a,b) in R AND (b,c) in S
  T = {(a,c) in A × C | exists b in B, aRb and bSc}
  warning: some sources use R;S for the same left-to-right operation
  preserve operator convention in serialized data

05. MEMBERSHIP INFERENCE
  rule COMPOSE_INTRO:
    premises: R(a,b), S(b,c)
    conclude: (S ∘ R)(a,c)
  rule COMPOSE_ELIM:
    premise: (S ∘ R)(a,c)
    conclude: exists b in B with R(a,b) and S(b,c)
  witness is existential and need not be unique
  absence of an observed witness is not evidence of nonmembership under incomplete data

06. DOMAIN AND RANGE
  dom(R) = {a in A | exists b in B: R(a,b)}
  ran(R) = {b in B | exists a in A: R(a,b)}
  dom(S ∘ R) subseteq dom(R)
  ran(S ∘ R) subseteq ran(S)
  actual endpoints depend on compatible intermediate witnesses

07. TYPE COMPOSITION
  R:A ->rel B
  S:B ->rel C
  compose(S,R):A ->rel C
  incompatible intermediate types: TYPE_ERROR
  empty intermediate set: composition is empty
  relation membership must not be confused with functional application

08. ASSOCIATIVITY
  given R subseteq A×B, S subseteq B×C, T subseteq C×D:
    T ∘ (S ∘ R) = (T ∘ S) ∘ R
  proof condition: existential witnesses can be regrouped
  no commutativity assumed
  generally S ∘ R != R ∘ S (latter may be ill-typed)

09. IDENTITY LAWS
  I_A = {(a,a) | a in A}
  R ∘ I_A = R for R subseteq A×B
  I_B ∘ R = R for R subseteq A×B
  composition plus identities forms a category of sets and relations (Rel)

10. EMPTY AND UNIVERSAL RELATIONS
  empty_BC ∘ R = empty_AC
  S ∘ empty_AB = empty_AC
  U_AB = A×B
  U_BC ∘ U_AB = A×C if B nonempty; otherwise empty
  universal composition is not universally universal without witness existence

11. UNION DISTRIBUTIVITY
  S ∘ (R1 union R2) = (S ∘ R1) union (S ∘ R2)
  (S1 union S2) ∘ R = (S1 ∘ R) union (S2 ∘ R)
  composition is monotone in both arguments
  R1 subseteq R2 implies S ∘ R1 subseteq S ∘ R2
  S1 subseteq S2 implies S1 ∘ R subseteq S2 ∘ R

12. INTERSECTION LIMITATION
  S ∘ (R1 intersection R2) subseteq (S ∘ R1) intersection (S ∘ R2)
  equality not guaranteed because separate witnesses may differ
  (S1 intersection S2) ∘ R subseteq (S1 ∘ R) intersection (S2 ∘ R)
  do not infer equality without additional assumptions

13. INVERSE OF COMPOSITION
  (S ∘ R)^(-1) = R^(-1) ∘ S^(-1)
  reversal of order is mandatory
  inverse of identity equals identity
  inverse of a relation need not be a function

14. RELATION POWERS
  for R subseteq A×A:
    R^0 = I_A
    R^(n+1) = R ∘ R^n for n >= 0
    R^2 records two-step reachability
    R^n records n-step reachability
  do not define R^n for non-endorelations without typed chain context

15. CLOSURES
  R^+ = union over n>=1 of R^n (transitive closure)
  R^* = union over n>=0 of R^n (reflexive-transitive closure)
  R^* = I_A union R^+
  R transitive iff R ∘ R subseteq R
  R reflexive and transitive iff R^* = R
  finite graphs permit fixed-point computation of reachability

16. FUNCTIONAL SPECIAL CASE
  graph(f) = {(a,f(a)) | a in A} for f:A->B
  graph(g) ∘ graph(f) = graph(g ∘ f) for g:B->C
  relation composition generalises function composition
  a relation may have zero, one, or many outputs per input

17. BOOLEAN MATRIX SEMANTICS
  for finite A,B,C, let M_R indexed A×B and M_S indexed B×C
  M_(S∘R)[a,c] = OR_{b in B}(M_R[a,b] AND M_S[b,c])
  Boolean matrix multiplication uses OR and AND, not ordinary arithmetic
  matrix dimensions must match at B

18. GRAPH SEMANTICS
  R edges connect A to B
  S edges connect B to C
  composite edge a->c exists iff a->b->c path exists
  preserve edge direction and intermediate node identity
  graph traversal must respect types and graph scope

19. KNOWLEDGE GRAPH SCHEMA
  nodes: Relation, Set, Element, Composition, Witness, Proof, Context
  predicates:
    hasDomain(Relation,Set)
    hasCodomain(Relation,Set)
    hasOrderedPair(Relation,OrderedPair)
    leftOperand(Composition,Relation)
    rightOperand(Composition,Relation)
    yieldsRelation(Composition,Relation)
    hasWitness(Composition,Witness)
    usesConvention(Composition,Convention)
    justifiedBy(Assertion,Proof)
  composition edge order: leftOperand=S, rightOperand=R for S∘R

20. SEMANTIC EQUIVALENCE
  equivalent(R,S) iff same typed pair membership for all admissible pairs
  extensionallyEqual(R,S) requires matching domain/codomain context
  syntactic difference does not imply relational difference
  normalize composition trees by associativity, preserving operand order
  never normalize by swapping operands

21. INFERENCE ENGINE
  rule R1: if R(a,b) and S(b,c), infer compose(S,R)(a,c)
  rule R2: if R subseteq R2, infer S∘R subseteq S∘R2
  rule R3: if S subseteq S2, infer S∘R subseteq S2∘R
  rule R4: infer inverse(compose(S,R)) = compose(inverse(R),inverse(S))
  rule R5: if R is transitive, infer R∘R subseteq R
  rule R6: infer compose(I_B,R)=R and compose(R,I_A)=R
  soundness: all rules follow standard relation semantics
  completeness: no claim of general first-order completeness for this rule subset

22. VALIDATION
  check declared relation types
  check all ordered pairs have valid endpoints
  check intermediate type alignment
  check operator orientation metadata
  check inferred pairs possess witness or valid symbolic proof
  check equality assertions by extensional comparison where decidable
  distinguish empty relation from unknown relation data
  reject unsupported inverse-function assumptions

23. ERROR AND UNCERTAINTY MODEL
  TYPE_ERROR: incompatible intermediate domains
  SCOPE_ERROR: different universes or graph contexts
  CONVENTION_AMBIGUITY: order of composition unspecified
  INCOMPLETE_DATA: absence of stored edge cannot prove falsehood
  INVALID_WITNESS: intermediate entity violates membership/type
  UNKNOWN: proof or evidence insufficient
  mathematical certainty applies to valid deductions, not unverified inputs

24. CONFIDENCE
  confidence.schema = 1.0 for explicitly defined mathematical axioms
  confidence.deduction = 1.0 for sound rules with verified premises
  confidence.observation = evidence-dependent
  confidence.source_alignment = unverified until source text checked
  never convert confidence scores into proof of theorem validity

25. FLOW_HASH AND PROVENANCE
  FLOW_HASH := SHA-256(canonical UTF-8 representation of flow specification)
  hash excludes mutable external timestamps unless explicitly versioned
  hash must be computed by implementation, not invented in text
  provenance.source_url = source listed in header
  provenance.authorship = Mark Higgins — Sky (Recursive AI)
  provenance.ontology_version = 1.0
  provenance.source_verified = false

26. UPDATE_MODEL
  update triggers: corrected definitions, ontology changes, proof corrections
  maintain immutable version identifiers and changelog
  recompute FLOW_HASH after canonical-content changes
  invalidate dependent inferences if an underlying relation changes
  revalidate relation types and witness chains on updates

27. AI_CONSUMPTION
  ingest: parse typed relation declarations and composition nodes
  reason: execute sound composition and closure inference
  retrieve: index relation type, direction, domains, witness paths
  explain: provide witness chain for each materialised composite pair
  export: preserve convention, provenance, confidence and version
  prohibit: interpreting relation composition as commutative
  prohibit: treating incomplete graphs as closed-world without policy

28. WORKED EXAMPLE
  A={a1,a2}; B={b1,b2}; C={c1,c2}
  R={(a1,b1),(a1,b2),(a2,b2)}
  S={(b1,c1),(b2,c2)}
  S∘R={(a1,c1),(a1,c2),(a2,c2)}
  witness(a1,c1)=b1
  witness(a1,c2)=b2
  witness(a2,c2)=b2
  validate: no pair (a2,c1) because no matching intermediate witness

29. PROPERTY TESTS
  test associativity for all well-typed finite relation triples
  test left and right identity for arbitrary finite relations
  test inverse-composition law
  test distributivity over union
  test monotonicity under subset extension
  test transitive closure fixed point on finite endorelations
  test empty-intermediate-domain edge case
  test intersection non-distributivity counterexample
  test witness provenance and orientation consistency

30. TERMINATION
  return CompositeRelation with typed endpoints, supporting witnesses,
         proof metadata, validation status, confidence, provenance and version
end flow