Relation Composition Ontology

FLOW ALGEBRA
TITLE: Relation Composition Ontology
DOMAIN: Discrete Mathematics / Relations
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations/relation-composition-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Formal mathematical synthesis; source page content not independently verified.

1. PURPOSE
Represent the composition of typed binary relations, its existential semantics, algebraic laws, validation constraints and machine-readable reasoning pathways.

2. TYPED ENTITIES
Set[A], Set[B], Set[C] : sets of typed elements
Relation[A,B] : subset of A × B
Relation[B,C] : subset of B × C
Pair[A,B] : ordered pair
Identity[A] : {(a,a) | a in A}
EmptyRelation[A,B] : empty subset of A × B
Composite[A,C] : relation obtained by composition
Witness[B] : intermediate element establishing composition

3. CORE DEFINITIONS
R : Relation[A,B]
S : Relation[B,C]
S ∘ R : Relation[A,C]
(a,c) in (S ∘ R) iff exists b in B: (a,b) in R and (b,c) in S.
ORDER_CONVENTION: S ∘ R means apply R first, then S.
TYPE_RULE: compose(S: Relation[B,C], R: Relation[A,B]) -> Relation[A,C].

4. FLOW OPERATIONS
flow COMPOSE(R: Relation[A,B], S: Relation[B,C]) -> Relation[A,C]:
  return {(a,c) | a in A, c in C, exists b in B: R(a,b) and S(b,c)}

flow COMPOSITION_WITNESS(R,S,a,c) -> Set[B]:
  return {b in B | R(a,b) and S(b,c)}

flow INVERSE(R: Relation[A,B]) -> Relation[B,A]:
  return {(b,a) | (a,b) in R}

flow POWER(R: Relation[A,A], n: Natural) -> Relation[A,A]:
  require n >= 0
  if n == 0: return Identity[A]
  return COMPOSE(POWER(R,n-1),R)

flow TRANSITIVE_CLOSURE(R: Relation[A,A]) -> Relation[A,A]:
  return union over n >= 1 of POWER(R,n)

flow REFLEXIVE_TRANSITIVE_CLOSURE(R: Relation[A,A]) -> Relation[A,A]:
  return union over n >= 0 of POWER(R,n)

5. ALGEBRAIC LAWS
ASSOCIATIVITY: T ∘ (S ∘ R) = (T ∘ S) ∘ R for conformable types.
LEFT_IDENTITY: Identity[B] ∘ R = R.
RIGHT_IDENTITY: R ∘ Identity[A] = R.
EMPTY_LEFT: EmptyRelation[B,C] ∘ R = EmptyRelation[A,C].
EMPTY_RIGHT: S ∘ EmptyRelation[A,B] = EmptyRelation[A,C].
DISTRIBUTION_LEFT: T ∘ (R union S) = (T ∘ R) union (T ∘ S), where typed.
DISTRIBUTION_RIGHT: (S union T) ∘ R = (S ∘ R) union (T ∘ R), where typed.
INVERSE_COMPOSITION: (S ∘ R)^(-1) = R^(-1) ∘ S^(-1).
MONOTONICITY: R1 subseteq R2 implies S ∘ R1 subseteq S ∘ R2.
NONCOMMUTATIVITY: In general S ∘ R != R ∘ S; the latter may be ill-typed.
INTERSECTION_WARNING: Composition does not generally distribute over intersection; only inclusion holds for the analogous expressions.

6. SEMANTIC RELATIONSHIPS
RelationComposition --operates_on--> BinaryRelation
RelationComposition --requires--> CompatibleIntermediateDomain
RelationComposition --produces--> CompositeRelation
CompositeRelation --contains--> OrderedPair
OrderedPair --may_be_justified_by--> IntermediateWitness
RelationComposition --generalises--> FunctionComposition
RelationComposition --supports--> PathReachability
RelationPower --supports--> TransitiveClosure
RelationComposition --obeys--> Associativity

7. INFERENCE RULES
COMPOSE_INTRO:
  R(a,b) and S(b,c) => (S ∘ R)(a,c).
COMPOSE_ELIM:
  (S ∘ R)(a,c) => exists b: R(a,b) and S(b,c).
COMPOSE_MONOTONE:
  R1 subseteq R2 => S ∘ R1 subseteq S ∘ R2.
TRANSITIVITY_TEST:
  R is transitive iff R ∘ R subseteq R, for R subseteq A × A.
PATH_LENGTH_TWO:
  (a,c) in R^2 iff there exists b with R(a,b) and R(b,c).

8. VALIDATION
CHECK_TYPED: codomain(R) and domain(S) must use compatible element types; declared sets B must agree.
CHECK_PAIRS: every pair in R and S belongs to its declared Cartesian product.
CHECK_WITNESS: every composite pair has an intermediate witness.
CHECK_COMPLETENESS: every qualifying witness produces its composite pair.
CHECK_ASSOCIATIVITY: compare both parenthesisations for conformable sample relations.
CHECK_IDENTITY: verify both typed identity laws.
CHECK_EMPTY: composition with a typed empty relation returns empty.
CHECK_INVERSE: verify inverse reverses composition order.
CHECK_TERMINATION: finite closure algorithms terminate after fixed-point convergence; infinite sets require symbolic reasoning or additional assumptions.

9. EXAMPLE
A={1,2}; B={x,y}; C={p,q}
R={(1,x),(2,y)} subseteq A×B
S={(x,p),(y,p),(y,q)} subseteq B×C
S ∘ R={(1,p),(2,p),(2,q)}
WITNESS(2,q)={y}

10. SEMANTIC_EQUIVALENCE
'S after R' == 'S composed with R' == 'S ∘ R' under the stated convention.
'Existential join over B' == 'Relational composition' for compatible binary relations with projection onto (A,C).
CAUTION: Some texts use the opposite symbol-order convention; the convention must be explicit.

11. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard definitions under declared convention)
DERIVED_RELATION_MEMBERSHIP: 1.00 when computed exactly from validated finite inputs
SOURCE_PAGE_ALIGNMENT: unverified
PROVENANCE: Standard relation algebra and mathematical synthesis.

12. FLOW_HASH
ALGORITHM: SHA-256
CANONICALISATION: UTF-8; LF newlines; deterministic field order; exclude FLOW_HASH value from hash input.
VALUE: COMPUTE_ON_EXPORT

13. UPDATE_MODEL
TRIGGER: Definition changes, convention changes, type schema revisions, corrected laws, new examples or source-page updates.
ACTION: Revalidate types and proofs; increment version; recompute FLOW_HASH; retain provenance and change log.

14. AI_CONSUMPTION
INPUT: Typed sets, relations, query pairs and optional composition depth.
PROCESS: Type-check -> join on intermediate variable -> project endpoints -> deduplicate -> validate witnesses -> infer closure if requested.
OUTPUT: Composite relation, supporting witnesses, applicable laws, confidence and provenance.
SAFETY: Do not infer transitivity of an arbitrary relation without proof; do not swap composition order; distinguish symbolic infinite-set statements from enumerated finite results.

END FLOW ALGEBRA