Binary Relation Ontology

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

1. ONTOLOGY DECLARATION
ontology BinaryRelationOntology {
  entity Set;
  entity Element;
  entity OrderedPair;
  entity BinaryRelation;
  entity Domain;
  entity Codomain;
  entity Image;
  entity InverseRelation;
  entity RelationComposition;
  entity RelationProperty;
}

2. TYPED SIGNATURE
  A, B, C : Set
  a, a1, a2 : Element(A)
  b : Element(B)
  c : Element(C)
  R : BinaryRelation(A,B) = subset(A × B)
  S : BinaryRelation(B,C) = subset(B × C)
  pair : A × B -> OrderedPair
  relates : BinaryRelation(A,B) × A × B -> Boolean
  inverse : BinaryRelation(A,B) -> BinaryRelation(B,A)
  compose : BinaryRelation(B,C) × BinaryRelation(A,B) -> BinaryRelation(A,C)

3. CORE SEMANTICS
  relates(R,a,b) iff (a,b) in R
  dom(R) = {a in A | exists b in B: (a,b) in R}
  ran(R) = {b in B | exists a in A: (a,b) in R}
  image(R,X) = {b in B | exists a in X: (a,b) in R}, X subseteq A
  inverse(R) = {(b,a) | (a,b) in R}
  compose(S,R) = {(a,c) | exists b in B: (a,b) in R and (b,c) in S}
  empty_relation(A,B) = empty_set
  universal_relation(A,B) = A × B
  identity_relation(A) = {(a,a) | a in A}

4. RELATION PROPERTIES (HOMOGENEOUS R subseteq A × A)
  reflexive(R) iff forall a in A: (a,a) in R
  irreflexive(R) iff forall a in A: (a,a) notin R
  symmetric(R) iff forall a,b in A: (a,b) in R => (b,a) in R
  antisymmetric(R) iff forall a,b in A: ((a,b) in R and (b,a) in R) => a=b
  asymmetric(R) iff forall a,b in A: (a,b) in R => (b,a) notin R
  transitive(R) iff forall a,b,c in A: ((a,b) in R and (b,c) in R) => (a,c) in R
  equivalence_relation(R) iff reflexive(R) and symmetric(R) and transitive(R)
  partial_order(R) iff reflexive(R) and antisymmetric(R) and transitive(R)
  strict_partial_order(R) iff irreflexive(R) and transitive(R)
  total_order(R) iff partial_order(R) and forall a,b in A: (a,b) in R or (b,a) in R

5. ALGEBRAIC LAWS
  inverse(inverse(R)) = R
  inverse(R union T) = inverse(R) union inverse(T)
  inverse(R intersection T) = inverse(R) intersection inverse(T)
  inverse(compose(S,R)) = compose(inverse(R),inverse(S))
  compose(T,compose(S,R)) = compose(compose(T,S),R)
  compose(R,identity_relation(A)) = R
  compose(identity_relation(B),R) = R
  compose(S,R union T) = compose(S,R) union compose(S,T)
  compose(S union T,R) = compose(S,R) union compose(T,R)
  R subseteq T => inverse(R) subseteq inverse(T)
  R subseteq T => compose(S,R) subseteq compose(S,T)

6. CLOSURES (R subseteq A × A)
  reflexive_closure(R) = R union identity_relation(A)
  symmetric_closure(R) = R union inverse(R)
  transitive_closure(R) = union_{n>=1} R^n
  reflexive_transitive_closure(R) = identity_relation(A) union transitive_closure(R)
  where R^1=R and R^(n+1)=compose(R,R^n)

7. SEMANTIC RELATIONSHIPS
  BinaryRelation IS_A SetOfOrderedPairs
  BinaryRelation SUBSET_OF CartesianProduct
  OrderedPair HAS_FIRST_COMPONENT Element
  OrderedPair HAS_SECOND_COMPONENT Element
  BinaryRelation HAS_DOMAIN Set
  BinaryRelation HAS_CODOMAIN Set
  BinaryRelation HAS_INVERSE InverseRelation
  BinaryRelation PARTICIPATES_IN RelationComposition
  EquivalenceRelation IS_A BinaryRelation
  PartialOrder IS_A BinaryRelation
  TotalOrder IS_A PartialOrder
  BinaryRelation REPRESENTS ConnectionsBetweenElements

8. INFERENCE RULES
  [MEMBERSHIP] (a,b) in R => relates(R,a,b)
  [INVERSE] (a,b) in R => (b,a) in inverse(R)
  [COMPOSITION] (a,b) in R and (b,c) in S => (a,c) in compose(S,R)
  [TRANSITIVE] transitive(R) and (a,b) in R and (b,c) in R => (a,c) in R
  [SYMMETRIC] symmetric(R) and (a,b) in R => (b,a) in R
  [REFLEXIVE] reflexive(R) and a in A => (a,a) in R
  [EQUIVALENCE] reflexive(R) and symmetric(R) and transitive(R) => equivalence_relation(R)
  [ORDER] reflexive(R) and antisymmetric(R) and transitive(R) => partial_order(R)

9. SEMANTIC_EQUIVALENCE
  'binary relation from A to B' <=> 'subset of A × B'
  'a R b' <=> '(a,b) belongs to R'
  'converse relation' <=> 'inverse relation'
  'relational composition S after R' <=> 'compose(S,R)'
  CAUTION: domain(R) may be a proper subset of declared source set A.
  CAUTION: codomain B is not necessarily the range of R.
  CAUTION: antisymmetric does not mean asymmetric.

10. VALIDATION
  REQUIRE R subseteq A × B
  REQUIRE every (a,b) in R satisfies a in A and b in B
  REQUIRE composition operands have compatible intermediate set B
  REQUIRE homogeneous relations for reflexivity, symmetry and transitivity tests
  TEST inverse(inverse(R)) = R
  TEST identity composition = R
  TEST transitive_closure(R) is transitive and contains R
  TEST equivalence and ordering predicates only under their stated axioms

11. EXAMPLE
  A = {1,2,3}
  R = {(1,2),(2,3)} subseteq A × A
  inverse(R) = {(2,1),(3,2)}
  compose(R,R) = {(1,3)}
  transitive_closure(R) = {(1,2),(2,3),(1,3)}
  dom(R) = {1,2}
  ran(R) = {2,3}

12. CONFIDENCE
  formal_definitions: 1.00
  standard_algebraic_laws: 1.00
  source_page_alignment: unverified
  interpretation: mathematical reference ontology; not a claim of live page extraction

13. FLOW_HASH
  strategy: SHA-256
  canonical_input: UTF-8 canonicalised ontology content excluding FLOW_HASH output
  computed_digest: not_computed
  note: Generate digest during publication; never treat a placeholder as a hash.

14. UPDATE_MODEL
  update_policy: versioned
  triggers: definition_change | property_change | relationship_change | validation_change
  checks: type_consistency | mathematical_soundness | backwards_compatibility
  provenance: retain source URL, version, author and revision date

15. AI_CONSUMPTION
  machine_readable: true
  reasoning_modes: deductive | symbolic | graph | relational
  retrieval_keys: binary relation | ordered pair | relation inverse | composition | closure
  recommended_uses: ontology alignment | knowledge graphs | graph queries | discrete mathematics tutoring
  guardrails: preserve operand types; distinguish range from codomain; avoid unstated relation properties

END FLOW ALGEBRA