Antisymmetric Relation Ontology

FLOW ALGEBRA
TITLE: Antisymmetric Relation Ontology
DOMAIN: Discrete Mathematics / Relations / Relation Properties
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations/antisymmetric-relation-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Formal mathematical reference; live source text not independently verified.

1. PURPOSE
Model antisymmetry as a formally testable property of binary relations, distinguishing it from asymmetry and symmetry and enabling consistent inference across discrete mathematics and knowledge representation.

2. TYPED ENTITIES
Set[A] := collection of elements of type A
Element[A] := member of Set[A]
OrderedPair[A] := (a:A,b:A)
BinaryRelation[A] := subset of A × A
IdentityRelation[A] := {(a,a) | a in A}
ConverseRelation[A] := R^-1 = {(b,a) | (a,b) in R}
RelationIntersection[A] := R ∩ S
RelationDifference[A] := R \ S
PropertyTest := Boolean with proof or counterexample
Counterexample[A] := (a,b) where a != b and (a,b) in R and (b,a) in R

3. CORE DEFINITION
ANTISYMMETRIC(R,A) := forall a,b in A: ((a,b) in R AND (b,a) in R) => a=b
EQUIVALENT_TEST := R ∩ R^-1 ⊆ IdentityRelation(A)
COUNTEREXAMPLE_EXISTS := exists a,b in A: a != b AND aRb AND bRa
ANTISYMMETRIC(R,A) iff NOT COUNTEREXAMPLE_EXISTS

4. OPERATIONS
CHECK_ANTISYMMETRY(R,A) -> Boolean
  require R ⊆ A × A
  return forall (a,b) in R: (a=b OR (b,a) not in R)

FIND_COUNTEREXAMPLE(R,A) -> Optional[OrderedPair[A]]
  return any (a,b) in R such that a!=b and (b,a) in R

ANTISYMMETRIC_REPAIR(R,A,choose_direction) -> BinaryRelation[A]
  for each distinct a,b with aRb and bRa:
    remove at least one of (a,b),(b,a) according to declared policy
  preserve diagonal pairs unless another constraint requires removal
  postcondition: ANTISYMMETRIC(result,A)
  note: repair is not unique and may change semantics

5. ALGEBRAIC LAWS
ANTISYMMETRIC(IdentityRelation(A),A) = true
ANTISYMMETRIC(EmptyRelation(A),A) = true
ANTISYMMETRIC(R,A) => ANTISYMMETRIC(S,A) for every S ⊆ R
ANTISYMMETRIC(R,A) iff ANTISYMMETRIC(R^-1,A)
ANTISYMMETRIC(R,A) iff (R ∩ R^-1) ⊆ IdentityRelation(A)
ANTISYMMETRIC(R,A) AND SYMMETRIC(R,A) iff R ⊆ IdentityRelation(A)
NOT UNIVERSALLY VALID: antisymmetry of R and S implies antisymmetry of R ∪ S
NOT UNIVERSALLY VALID: antisymmetry of R implies antisymmetry of transitive closure R+

6. RELATED RELATION PROPERTIES
ASYMMETRIC(R,A) := forall a,b in A: aRb => NOT bRa
ASYMMETRIC(R,A) => ANTISYMMETRIC(R,A)
ASYMMETRIC(R,A) => IRREFLEXIVE(R,A)
ANTISYMMETRIC(R,A) does NOT imply ASYMMETRIC(R,A)
PARTIAL_ORDER(R,A) := REFLEXIVE(R,A) AND ANTISYMMETRIC(R,A) AND TRANSITIVE(R,A)
TOTAL_ORDER(R,A) := PARTIAL_ORDER(R,A) AND forall a,b in A: aRb OR bRa
STRICT_PARTIAL_ORDER(R,A) := IRREFLEXIVE(R,A) AND TRANSITIVE(R,A)

7. EXAMPLES
EXAMPLE 1: A={1,2,3}; R={(1,1),(1,2),(2,2),(2,3)} => antisymmetric
EXAMPLE 2: A={1,2}; R={(1,2),(2,1)} => not antisymmetric; witness=(1,2)
EXAMPLE 3: subset-or-equal relation on P(A) => antisymmetric
EXAMPLE 4: less-than-or-equal on integers => antisymmetric
EXAMPLE 5: equality on any set => antisymmetric and symmetric
EXAMPLE 6: divisibility on positive integers => antisymmetric; on nonzero integers it is not antisymmetric because 2 divides -2 and -2 divides 2

8. INFERENCE RULES
[R ⊆ A×A, forall a,b: aRb and bRa => a=b] |- ANTISYMMETRIC(R,A)
[aRb, bRa, ANTISYMMETRIC(R,A)] |- a=b
[aRb, bRa, a!=b] |- NOT ANTISYMMETRIC(R,A)
[REFLEXIVE(R,A), ANTISYMMETRIC(R,A), TRANSITIVE(R,A)] |- PARTIAL_ORDER(R,A)
[ASYMMETRIC(R,A)] |- ANTISYMMETRIC(R,A)

9. SEMANTIC RELATIONSHIPS
AntisymmetricRelation --is_a--> BinaryRelationWithProperty
AntisymmetricRelation --constrains--> ReciprocalPairs
AntisymmetricRelation --permits--> ReflexivePairs
AntisymmetricRelation --component_of--> PartialOrder
AsymmetricRelation --subclass_property_of--> AntisymmetricRelation
Counterexample --refutes--> AntisymmetryClaim

10. SEMANTIC_EQUIVALENCE
ANTISYMMETRIC(R,A) <=> forall a!=b: NOT(aRb AND bRa)
ANTISYMMETRIC(R,A) <=> R ∩ R^-1 ⊆ Δ_A
Δ_A := {(a,a) | a in A}
WARNING: antisymmetric != not symmetric; a relation can satisfy both.

11. VALIDATION
V1: verify carrier set A and typing R ⊆ A×A
V2: verify all reciprocal pairs of distinct elements are absent
V3: report a concrete witness on failure
V4: distinguish missing pairs from asserted negative facts in open-world datasets
V5: for finite R use exact enumeration; for infinite R require proof or sound symbolic decision procedure
V6: avoid claiming global antisymmetry from incomplete samples
V7: maintain provenance for every observed or inferred edge

12. CONFIDENCE
Mathematically proved result: 1.00 conditional on valid premises and proof checker
Finite exhaustive test: 1.00 conditional on complete and correct input
Sampled observation: empirical only; not a proof of universal antisymmetry
Unverified or open-world relation: unknown until evidence establishes property
Never substitute confidence scores for a logical proof.

13. FLOW_HASH
FLOW_HASH := SHA-256(canonical_utf8(flow_content_without_FLOW_HASH_value))
CANONICALISATION := UTF-8; LF line endings; stable section order; normalised whitespace
NOTE: compute actual digest when published; no fabricated hash is supplied.

14. UPDATE_MODEL
On relation insertion (a,b):
  if a!=b and (b,a) already in R: invalidate antisymmetry assertion and emit witness
On relation deletion: revalidate previously failed claims as appropriate
On carrier set change: recheck domain/range constraints and property
Record version, timestamp, provenance, reason and validation result.

15. AI_CONSUMPTION
INPUT: carrier_set, relation_edges, completeness_mode, provenance
PROCESS: type_check -> check_reciprocal_distinct_pairs -> infer_properties -> validate -> explain
OUTPUT: antisymmetric_status [true|false|unknown], witnesses, proofs, dependencies, confidence, provenance
SAFETY: preserve distinction between formal logical entailment and heuristic semantic similarity

END FLOW ALGEBRA