Relation Ontology

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

1. PURPOSE
Represent mathematical relations as typed sets of tuples, with explicitly scoped domains, codomains, properties, transformations, and machine-checkable inference rules.

2. TYPED ENTITIES
Set[A]                 := collection of elements of type A
Element[A]             := member of Set[A]
OrderedPair[A,B]       := (a:A, b:B)
BinaryRelation[A,B]    := subset of A × B
Endorelation[A]        := BinaryRelation[A,A]
NaryRelation[T1..Tn]   := subset of T1 × ... × Tn
Predicate[A,B]         := A × B -> Boolean
RelationProperty       := {reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total}
EquivalenceClass[A]    := subset of A
Partition[A]           := set of pairwise disjoint nonempty subsets covering A
PartialOrder[A]        := Endorelation[A] satisfying reflexivity, antisymmetry, transitivity

3. DEFINITIONS AND OPERATORS
relation(A:Set[A], B:Set[B], pairs:Set[OrderedPair[A,B]]) -> BinaryRelation[A,B]
member((a,b), R)       := (a,b) ∈ R
relates(R,a,b)        := (a,b) ∈ R
inverse(R)            := {(b,a) | (a,b) ∈ R}
domain(R)             := {a ∈ A | ∃b∈B: (a,b)∈R}
range(R)              := {b ∈ B | ∃a∈A: (a,b)∈R}
complement(R,A,B)      := (A × B) \ R
union(R,S)            := R ∪ S, where R,S ⊆ A × B
intersection(R,S)     := R ∩ S, where R,S ⊆ A × B
difference(R,S)       := R \ S, where R,S ⊆ A × B
compose(S,R)          := {(a,c) | ∃b: (a,b)∈R ∧ (b,c)∈S}
identity(A)           := {(a,a) | a∈A}
image(R,X)            := {b∈B | ∃a∈X: (a,b)∈R}
preimage(R,Y)         := {a∈A | ∃b∈Y: (a,b)∈R}

4. RELATION PROPERTY PREDICATES (R ⊆ A × A)
reflexive(R,A)         iff ∀a∈A: (a,a)∈R
irreflexive(R,A)       iff ∀a∈A: (a,a)∉R
symmetric(R)           iff ∀a,b∈A: aRb => bRa
antisymmetric(R)       iff ∀a,b∈A: (aRb ∧ bRa) => a=b
asymmetric(R)          iff ∀a,b∈A: aRb => ¬bRa
transitive(R)          iff ∀a,b,c∈A: (aRb ∧ bRc) => aRc
total(R,A)             iff ∀a,b∈A: aRb ∨ bRa
equivalence(R,A)       iff reflexive(R,A) ∧ symmetric(R) ∧ transitive(R)
partial_order(R,A)     iff reflexive(R,A) ∧ antisymmetric(R) ∧ transitive(R)
strict_partial_order(R,A) iff irreflexive(R,A) ∧ transitive(R)
linear_order(R,A)      iff partial_order(R,A) ∧ total(R,A)

5. ALGEBRAIC LAWS
inverse(inverse(R)) = R
inverse(R ∪ S) = inverse(R) ∪ inverse(S)
inverse(compose(S,R)) = compose(inverse(R),inverse(S))
compose(T,compose(S,R)) = compose(compose(T,S),R)
compose(R,identity(A)) = R, for R ⊆ A × B
compose(identity(B),R) = R, for R ⊆ A × B
R ⊆ S => inverse(R) ⊆ inverse(S)
R ⊆ S => compose(T,R) ⊆ compose(T,S), for compatible types
R is transitive iff compose(R,R) ⊆ R
R is symmetric iff inverse(R) = R
R is reflexive on A iff identity(A) ⊆ R

6. CLOSURES
reflexive_closure(R,A) := R ∪ identity(A)
symmetric_closure(R) := R ∪ inverse(R)
transitive_closure(R) := least transitive relation containing R
reflexive_transitive_closure(R,A) := identity(A) ∪ transitive_closure(R)
For finite A, transitive_closure(R) = union of R^k for k=1..|A| (empty when A is empty).

7. SEMANTIC RELATIONSHIPS
Relation --is_a--> SetOfTuples
BinaryRelation --is_a--> Relation
Endorelation --is_a--> BinaryRelation
EquivalenceRelation --defined_by--> Reflexivity, Symmetry, Transitivity
PartialOrder --defined_by--> Reflexivity, Antisymmetry, Transitivity
LinearOrder --specialises--> PartialOrder
RelationComposition --uses--> SharedIntermediateType
InverseRelation --reverses--> TupleOrientation
EquivalenceRelation --induces--> Partition
Partition --induces--> EquivalenceRelation

8. INFERENCE RULES
IF equivalence(R,A) AND aRb AND bRc THEN aRc.
IF equivalence(R,A) AND aRb THEN equivalence_class(R,a) = equivalence_class(R,b).
IF partial_order(R,A) AND aRb AND bRa THEN a=b.
IF asymmetric(R) THEN irreflexive(R,A) AND antisymmetric(R).
IF transitive(R) AND aRb AND bRc THEN aRc.
IF (a,b)∈R THEN (b,a)∈inverse(R).
Do not infer symmetry, transitivity, or equivalence without validating their defining conditions.

9. EXAMPLES
A={1,2,3}; R={(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)}.
R is reflexive, antisymmetric, transitive, and total on A: a linear order.
B={x,y}; S={(1,x),(2,y)} ⊆ A×B; inverse(S)={(x,1),(y,2)}.

10. VALIDATION
V01: All relation tuples conform to declared operand types.
V02: Each relation pair belongs to its declared A × B.
V03: Property tests use the complete declared carrier set A, not merely domain(R).
V04: Composition requires matching intermediate types.
V05: Complement is evaluated relative to explicit A × B.
V06: Equality and set membership must use consistent semantics.
V07: Equivalence-class claims require equivalence(R,A).
V08: For infinite sets, algorithmic property tests may be undecidable without symbolic assumptions or proofs.

11. SEMANTIC_EQUIVALENCE
(a,b) ∈ R <=> R(a,b) <=> aRb
inverse(R) <=> converse(R)
reflexive_transitive_closure(R,A) <=> R* (with carrier A explicit)
transitive_closure(R) <=> R+ (conventional notation)
Do not conflate equivalence relation with logical equivalence of propositions.

12. CONFIDENCE
Mathematical definitions and identities: 1.00 (subject to explicit type assumptions).
Derived property classifications: 1.00 only when verified by proof or exhaustive finite-set check.
Empirical or extracted relation facts: assign source-specific confidence; never assume 1.00.

13. FLOW_HASH
canonicalise: UTF-8; normalise line endings to LF; preserve mathematical symbols; sort unordered relation tuples where semantically appropriate.
hash_algorithm: SHA-256
hash_input: canonical representation excluding the FLOW_HASH value itself.
flow_hash_value: COMPUTE_ON_PUBLICATION (not precomputed)

14. UPDATE_MODEL
trigger: mathematical correction | schema revision | source-page revision | new formal proof
versioning: increment version; retain provenance and prior versions
invalidation: recompute affected properties, closures, derived relations and FLOW_HASH

15. AI_CONSUMPTION
mode: typed semantic retrieval + symbolic reasoning
inputs: carrier sets, relation tuples or predicates, declared properties, evidence
outputs: validated properties, inverse, composition, closures, equivalence classes, order structures
constraints: preserve type boundaries; report missing assumptions; distinguish proven from inferred and unknown
provenance: source URL + version + author credits + validation status

END FLOW ALGEBRA