Relations

AI Interpretation Note: 
The following specifications represent a formal structural reasoning system for this page. 
Execute as formal rules, not pseudocode. 

FLOW ALGEBRA
RELATIONS — DISCRETE MATHEMATICS ONTOLOGIES
Kireth Semantic Library
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations.html
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Authorship: Mark Higgins — Sky (Recursive AI)
Research: https://kirethresearch.org

SCOPE
Formal semantic model for mathematical relations, their representations, properties, compositions, closures and applications. This is a foundational parent-page flow. Live webpage content was not available for verification; the definitions below follow standard discrete mathematics.

TYPES
  Set<T>                   := collection of distinct elements of type T
  Element<T>               := member of Set<T>
  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 -> Bool
  DirectedGraph<A>         := (vertices:A, edges:Endorelation<A>)
  EquivalenceClass<A>      := subset of A under an equivalence relation
  Partition<A>             := set of nonempty disjoint subsets covering A
  Confidence               := real number in [0,1]

ENTITIES
  RELATION; DOMAIN; CODOMAIN; IMAGE; PREIMAGE; ORDERED_PAIR
  REFLEXIVE; IRREFLEXIVE; SYMMETRIC; ANTISYMMETRIC; ASYMMETRIC
  TRANSITIVE; EQUIVALENCE_RELATION; EQUIVALENCE_CLASS
  PARTIAL_ORDER; STRICT_ORDER; TOTAL_ORDER
  INVERSE_RELATION; COMPOSITION; IDENTITY_RELATION
  REFLEXIVE_CLOSURE; SYMMETRIC_CLOSURE; TRANSITIVE_CLOSURE
  ADJACENCY_MATRIX; DIRECTED_GRAPH; RELATIONAL_DATABASE

DEFINITIONS
  relation(R,A,B)             := R ⊆ A × B
  holds(R,a,b)                := (a,b) ∈ R
  domain(R)                   := {a ∈ A | ∃b ∈ B: (a,b) ∈ R}
  range(R)                    := {b ∈ B | ∃a ∈ A: (a,b) ∈ R}
  inverse(R)                  := {(b,a) | (a,b) ∈ R}
  identity(A)                 := {(a,a) | a ∈ A}
  compose(S,R)                := {(a,c) | ∃b: (a,b) ∈ R ∧ (b,c) ∈ S}
  reflexive(R,A)              := ∀a ∈ A: (a,a) ∈ R
  irreflexive(R,A)            := ∀a ∈ A: (a,a) ∉ R
  symmetric(R)                := ∀a,b: (a,b) ∈ R ⇒ (b,a) ∈ R
  antisymmetric(R)            := ∀a,b: ((a,b) ∈ R ∧ (b,a) ∈ R) ⇒ a=b
  asymmetric(R)               := ∀a,b: (a,b) ∈ R ⇒ (b,a) ∉ R
  transitive(R)               := ∀a,b,c: ((a,b) ∈ R ∧ (b,c) ∈ R) ⇒ (a,c) ∈ R
  equivalence(R,A)           := reflexive(R,A) ∧ symmetric(R) ∧ transitive(R)
  partial_order(R,A)         := reflexive(R,A) ∧ antisymmetric(R) ∧ transitive(R)
  total_order(R,A)           := partial_order(R,A) ∧ ∀a,b ∈ A: (a,b) ∈ R ∨ (b,a) ∈ R
  strict_partial_order(R,A)  := irreflexive(R,A) ∧ transitive(R)
  class_of(R,a,A)            := {b ∈ A | (a,b) ∈ R}, where equivalence(R,A)

OPERATIONS
  R ∪ S                      := union of relations of the same type
  R ∩ S                      := intersection of relations of the same type
  R \ S                      := relative difference of relations of the same type
  complement(R,A,B)         := (A × B) \ R
  reflexive_closure(R,A)     := R ∪ identity(A)
  symmetric_closure(R)       := R ∪ inverse(R)
  transitive_closure(R)      := R⁺, the least transitive relation containing R
  reflexive_transitive(R,A)  := R*, the least reflexive/transitive relation containing R
  equivalence_closure(R,A)   := (R ∪ inverse(R) ∪ identity(A))*

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(identity(B),R) = R = compose(R,identity(A))  for R ⊆ A × B
  R ⊆ reflexive_closure(R,A)
  R ⊆ symmetric_closure(R)
  R ⊆ transitive_closure(R)
  R ⊆ reflexive_transitive(R,A)
  |A × B| = |A| · |B|  for finite sets
  number_of_binary_relations(A,B) = 2^(|A|·|B|) for finite sets

SEMANTIC RELATIONSHIPS
  BinaryRelation --IS_SUBSET_OF--> CartesianProduct
  BinaryRelation --HAS_DOMAIN--> Set
  BinaryRelation --HAS_CODOMAIN--> Set
  OrderedPair --MEMBER_OF--> BinaryRelation
  Endorelation --SPECIALISES--> BinaryRelation
  EquivalenceRelation --SPECIALISES--> Endorelation
  PartialOrder --SPECIALISES--> Endorelation
  EquivalenceRelation --INDUCES--> Partition
  PartialOrder --REPRESENTED_BY--> DirectedGraph
  BinaryRelation --REPRESENTED_BY--> BooleanMatrix
  InverseRelation --DERIVED_FROM--> BinaryRelation
  RelationComposition --COMBINES--> BinaryRelation
  TransitiveClosure --DERIVED_FROM--> Endorelation

INFERENCE RULES
  IF (a,b) ∈ R AND symmetric(R) THEN (b,a) ∈ R
  IF (a,b) ∈ R AND (b,c) ∈ R AND transitive(R) THEN (a,c) ∈ R
  IF (a,b) ∈ R AND (b,a) ∈ R AND antisymmetric(R) THEN a=b
  IF equivalence(R,A) THEN {[a]R | a ∈ A} partitions A
  IF partial_order(R,A) AND all pairs comparable THEN total_order(R,A)
  IF (a,b) ∈ R AND (b,c) ∈ S THEN (a,c) ∈ compose(S,R)
  IF (a,b) ∈ R THEN (b,a) ∈ inverse(R)

VALIDATION
  CHECK operands have compatible domain/codomain types before union or composition
  CHECK quantifiers for endorelation properties range over the declared base set
  CHECK antisymmetric is not confused with asymmetric
  CHECK symmetric is not confused with reflexive
  CHECK transitive closure need not be reflexive
  CHECK empty and singleton base-set edge cases
  CHECK equivalence classes only asserted after equivalence proof
  CHECK a relation's codomain is not automatically equal to its range
  CHECK finite cardinality formulas are not applied indiscriminately to infinite sets

EXAMPLES
  A={1,2,3}; R={(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)}
  reflexive(R,A)=true; antisymmetric(R)=true; transitive(R)=true
  partial_order(R,A)=true; total_order(R,A)=true
  B={a,b}; S={(1,a),(2,b)} ⊆ A × B
  inverse(S)={(a,1),(b,2)}

SEMANTIC_EQUIVALENCE
  "binary relation" ≡ "subset of a Cartesian product of two sets"
  "equivalence relation" ≡ "reflexive, symmetric and transitive endorelation"
  "partial order" ≡ "reflexive, antisymmetric and transitive endorelation"
  "relation converse" ≡ "inverse relation"
  NOTE: Natural-language aliases are contextual; do not treat approximate similarity as logical equivalence.

CONFIDENCE
  mathematical_definitions: 1.00 (within classical set theory)
  source_page_alignment: unverified
  generated_examples: 1.00 (checked by stated definitions)
  provenance: standard discrete mathematics; original ontology synthesis

FLOW_HASH
  scheme: SHA-256 over canonical UTF-8 flow content, computed on ingestion
  value: COMPUTE_ON_INGEST (not fabricated)

UPDATE_MODEL
  revision: 1.0
  update_trigger: mathematical correction | ontology hierarchy change | verified source-page revision
  compatibility: preserve typed relations and operation direction
  change_policy: record source, timestamp, version and semantic differences

AI_CONSUMPTION
  parse_mode: typed semantic flow
  reasoning_mode: symbolic, constraint-checked, provenance-aware
  safe_use: validate base sets, relation signatures and property proofs
  downstream: knowledge graphs, discrete mathematics, database relations, graph theory, formal reasoning
  output_requirement: distinguish proved properties from inferred or unverified claims

END FLOW ALGEBRA