N-ary Relation Ontology

FLOW ALGEBRA
TITLE: N-ary Relation Ontology
DOMAIN: Discrete Mathematics / Relations
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations/n-ary-relation-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org

1. PURPOSE
Formalise n-ary relations as typed subsets of Cartesian products, supporting mathematical reasoning, semantic modelling, databases, and knowledge representation.

2. TYPED ENTITIES
  Set[T]                  : collection of elements of type T
  Arity                   : integer n >= 1
  Domain_i                : Set[T_i] for i in {1,...,n}
  Tuple_n                 : T_1 × ... × T_n
  Relation_n              : Set[Tuple_n]
  TupleMembership         : Predicate[Tuple_n, Relation_n]
  Projection              : Relation_n -> Relation_k, 1 <= k <= n
  Selection               : Relation_n × Predicate[Tuple_n] -> Relation_n
  Join                    : compatible relations -> relation
  Permutation             : bijection on argument positions
  Constraint              : Predicate[Tuple_n]
  Provenance              : source and derivation metadata

3. DEFINITIONS
  Given n >= 1 and sets D_1,...,D_n:
    Product(D_1,...,D_n) = D_1 × ... × D_n
    R ⊆ Product(D_1,...,D_n)
    R(x_1,...,x_n) iff (x_1,...,x_n) ∈ R
  Unary relations are subsets of one domain; binary relations have arity two.
  Argument order and types are significant.

4. CORE OPERATIONS
  contains(R,t)          := t ∈ R
  insert(R,t)            := R ∪ {t}, provided t has valid types
  remove(R,t)            := R \ {t}
  union(R,S)             := R ∪ S, when signatures match
  intersection(R,S)      := R ∩ S, when signatures match
  difference(R,S)        := R \ S, when signatures match
  complement(R)          := Product(D_1,...,D_n) \ R
  select(R,p)            := {t ∈ R | p(t)}
  project_I(R)           := { (t_i)_(i∈I) | t ∈ R }, with ordered index list I
  permute_pi(R)          := { (t_pi(1),...,t_pi(n)) | t ∈ R }
  join_theta(R,S)        := { concatenate(r,s) | r∈R, s∈S, theta(r,s) }
  natural_join(R,S)      := merge compatible tuples agreeing on shared named attributes

5. ALGEBRAIC LAWS
  R ∪ S = S ∪ R
  R ∩ S = S ∩ R
  (R ∪ S) ∪ T = R ∪ (S ∪ T)
  (R ∩ S) ∩ T = R ∩ (S ∩ T)
  R ∩ (S ∪ T) = (R ∩ S) ∪ (R ∩ T)
  R ∪ (S ∩ T) = (R ∪ S) ∩ (R ∪ T)
  R \ S = R ∩ complement(S)
  project_I(R ∪ S) = project_I(R) ∪ project_I(S)
  select_p(R ∪ S) = select_p(R) ∪ select_p(S)
  project_I(R ∩ S) ⊆ project_I(R) ∩ project_I(S)
  NOTE: Projection does not generally distribute over intersection or difference as equality.

6. RELATIONSHIPS
  N_ARY_RELATION --IS_A--> RELATION
  N_ARY_RELATION --SUBSET_OF--> CARTESIAN_PRODUCT
  N_ARY_RELATION --HAS_ARITY--> ARITY
  N_ARY_RELATION --HAS_ARGUMENT_DOMAIN--> DOMAIN_i
  N_ARY_RELATION --CONTAINS--> TUPLE_n
  N_ARY_RELATION --SUPPORTS--> PROJECTION
  N_ARY_RELATION --SUPPORTS--> SELECTION
  N_ARY_RELATION --SUPPORTS--> JOIN
  N_ARY_RELATION --MODELS--> MULTI_ENTITY_FACT
  N_ARY_RELATION --MAPS_TO--> RELATIONAL_DATABASE_TABLE

7. INFERENCE RULES
  [MEMBERSHIP] t ∈ R => R(t)
  [SUBRELATION] R ⊆ S and t ∈ R => t ∈ S
  [SELECTION] t ∈ select(R,p) => t ∈ R and p(t)
  [PROJECTION] t ∈ R => project_I(t) ∈ project_I(R)
  [JOIN] r ∈ R and s ∈ S and theta(r,s) => concatenate(r,s) ∈ join_theta(R,S)
  [TYPING] t ∈ R => t_i ∈ D_i for every i=1,...,n

8. EXAMPLE
  Person = {Ada, Ben}
  Course = {Logic, Algebra}
  Term = {Autumn, Spring}
  Enrolment ⊆ Person × Course × Term
  Enrolment = {(Ada, Logic, Autumn), (Ben, Algebra, Spring)}
  arity(Enrolment) = 3
  project_[1,2](Enrolment) = {(Ada, Logic), (Ben, Algebra)}
  select_term=Autumn(Enrolment) = {(Ada, Logic, Autumn)}

9. VALIDATION
  V1: arity >= 1
  V2: every tuple has exactly n coordinates
  V3: every coordinate belongs to its declared domain
  V4: set operations require compatible signatures
  V5: projection indices must be valid and explicitly ordered
  V6: permutation must be a bijection on {1,...,n}
  V7: joins must specify attribute correspondence and collision handling
  V8: constraints must be satisfied before a tuple is admitted
  V9: empty relations are valid for any well-formed signature

10. SEMANTIC_EQUIVALENCE
  Canonical concept: N-ARY_RELATION
  Equivalent descriptions: n-place relation; relation of arity n
  Context-sensitive near terms: relational table; predicate of arity n; hyperedge
  Caution: Tables may use bag semantics and nulls; mathematical relations use sets of typed tuples.
  Caution: Reification into binary links requires additional structure to preserve tuple identity and argument roles.

11. CONFIDENCE
  Mathematical definitions and standard set laws: HIGH
  Modelling correspondences (database, knowledge graph): CONTEXT_DEPENDENT
  Source-page fidelity: UNVERIFIED (live page not inspected)
  Confidence must not be interpreted as a numerical probability without calibration.

12. FLOW_HASH
  Method: SHA-256 over canonical UTF-8 serialisation of the flow content excluding the FLOW_HASH value.
  Canonicalisation: normalise line endings to LF, retain field order and Unicode NFC.
  Status: NOT_COMPUTED

13. UPDATE_MODEL
  Change triggers: formal definition revision, signature changes, new relation operators, new constraints.
  Update procedure: revise version; validate mathematical claims; recalculate hash; preserve provenance and change log.
  Compatibility: changes to argument order, arity or domains are breaking changes.

14. AI_CONSUMPTION
  Read relation signature before processing facts.
  Distinguish ordered tuples from unordered collections.
  Verify typing, arity and constraints before inference.
  Apply algebraic rewrites only when their preconditions hold.
  Preserve provenance and uncertainty for extracted claims.
  Never infer missing tuple members from projection alone.

END FLOW ALGEBRA