Transitive Relation Ontology

FLOW ALGEBRA
TITLE: Transitive Relation Ontology
DOMAIN: Discrete Mathematics / Relations
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations/transitive-relation-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org

1. PURPOSE
Represent transitive binary relations, their mathematical properties, closures, inference mechanisms and machine-readable semantic connections.

2. TYPED ENTITIES
Set[A]: collection of elements of type A
Element[A]: member of Set[A]
BinaryRelation[A]: subset of A × A
OrderedPair[A]: (a,b) with a,b in A
TransitiveRelation[A] <: BinaryRelation[A]
RelationComposition[A]: binary operation on BinaryRelation[A]
TransitiveClosure[A]: least transitive relation containing a given relation
Path[A]: finite sequence of related elements
DirectedGraph[A]: vertices A and edges from a relation

3. FORMAL DEFINITION
For R ⊆ A × A:
TRANSITIVE(R) := ∀a,b,c ∈ A, ((a,b) ∈ R ∧ (b,c) ∈ R) ⇒ (a,c) ∈ R.
Equivalent composition criterion: R ∘ R ⊆ R, where
R ∘ S := {(a,c) | ∃b ∈ A: (a,b) ∈ S ∧ (b,c) ∈ R}.
The empty relation is transitive (vacuously).

4. OPERATIONS
COMPOSE(R,S): relation composition as defined above.
POWER(R,1) := R; POWER(R,n+1) := R ∘ POWER(R,n).
TRANSITIVE_CLOSURE(R) := R+ := ⋃_{n≥1} POWER(R,n).
REFLEXIVE_TRANSITIVE_CLOSURE(R) := R* := I_A ∪ R+.
I_A := {(a,a) | a ∈ A}.
IS_TRANSITIVE(R): returns true iff R ∘ R ⊆ R.

5. ALGEBRAIC LAWS
TRANSITIVE(R) ⇔ R² ⊆ R.
TRANSITIVE(R) ⇒ ∀n≥1, R^n ⊆ R.
R ⊆ R+.
TRANSITIVE(R+).
For any transitive T, R ⊆ T ⇒ R+ ⊆ T.
(R+)+ = R+.
(R*)* = R*.
(R+)⁻¹ = (R⁻¹)+.
Intersection of any family of transitive relations on A is transitive.
Union of transitive relations need not be transitive.
Composition of two transitive relations need not be transitive.
Transitivity alone does not imply reflexivity, symmetry or antisymmetry.

6. RELATIONSHIPS
TransitiveRelation IS_A BinaryRelation.
TransitiveRelation HAS_PROPERTY Transitivity.
TransitiveClosure DERIVED_FROM BinaryRelation.
TransitiveClosure REPRESENTS ReachabilityByPositiveLengthPath.
ReflexiveTransitiveClosure REPRESENTS ReachabilityByZeroOrMoreSteps.
PartialOrder REQUIRES Reflexivity AND Antisymmetry AND Transitivity.
EquivalenceRelation REQUIRES Reflexivity AND Symmetry AND Transitivity.
StrictPartialOrder REQUIRES Irreflexivity AND Transitivity.

7. INFERENCE RULES
TRANSITIVE_CHAIN:
  premises: R(a,b), R(b,c), TRANSITIVE(R)
  conclusion: R(a,c)
PATH_INFERENCE:
  premises: R(a0,a1), ..., R(a[n-1],an), n≥1
  conclusion: R+(a0,an)
CLOSURE_MINIMALITY:
  premises: TRANSITIVE(T), R ⊆ T
  conclusion: R+ ⊆ T
No inference of R(a,a) is permitted from transitivity alone.

8. VALIDATION
Input: a well-typed set A and relation R ⊆ A × A.
For finite A, inspect each (a,b),(b,c) ∈ R and verify (a,c) ∈ R.
Counterexample: R={(1,2),(2,3)} on A={1,2,3} is not transitive, because (1,3) is missing.
Positive example: R={(1,2),(2,3),(1,3)} is transitive.
For infinite A, validation may require symbolic proof or domain-specific decision procedures.
Distinguish R+ (paths of positive length) from R* (paths of zero or more edges).

9. COMPUTATIONAL MODEL
For finite directed graphs, transitive closure can be computed by Warshall's algorithm or graph traversal from each vertex.
Warshall recurrence: reach[i,j] := reach[i,j] OR (reach[i,k] AND reach[k,j]).
A directed cycle may introduce (a,a) into R+ even when R itself is irreflexive.
Use typed vertices and deterministic ordering when serialising finite relation instances.

10. SEMANTIC_EQUIVALENCE
TRANSITIVE(R) ≡ (R ∘ R ⊆ R).
TRANSITIVE_CLOSURE(R) ≡ LEAST_TRANSITIVE_SUPERRELATION(R).
R+(a,b) ≡ EXISTS_NONEMPTY_R_PATH(a,b).
R*(a,b) ≡ (a=b OR EXISTS_NONEMPTY_R_PATH(a,b)).
These equivalences are mathematical definitions, not claims that every semantic relation is transitive.

11. CONFIDENCE
Formal definitions and theorems: 1.00 within standard classical set theory.
Observed or inferred real-world edges: confidence must be supplied from provenance; do not automatically propagate numeric confidence through transitivity.
Keep logical entailment separate from empirical confidence.

12. FLOW_HASH
Canonicalise: version, entity types, definitions, axioms, operations, rules and source URL.
FLOW_HASH := SHA-256(UTF-8(canonical_representation)).
Compute hash only after canonicalisation; no precomputed hash is asserted here.

13. UPDATE_MODEL
On changes to the relation's edge set, recompute or incrementally maintain closure.
On addition of (a,b), assess newly reachable pairs via predecessors of a and successors of b.
On deletion, do not merely remove one closure pair: alternative paths may preserve reachability.
Record revision, timestamp, provenance and verification status.

14. AI_CONSUMPTION
Expose entity types, predicates, inference rules, closure distinctions and validation constraints to symbolic reasoners and knowledge graphs.
Apply transitive reasoning only to predicates explicitly declared transitive.
Avoid treating approximate similarity, association or causal claims as transitive without justified axioms.
Provide traceable proof paths for inferred edges and distinguish asserted from derived facts.

END FLOW ALGEBRA