Partial Order Ontology

FLOW ALGEBRA
TITLE: Partial Order Ontology
DOMAIN: Discrete Mathematics / Relations / Order Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/relations/partial-order-ontology.html
VERSION: 1.0
AUTHORS: Mark Higgins — Sky (Recursive AI)
STATUS: Formal mathematical model; source webpage not independently verified.

1. PURPOSE
Represent partially ordered sets, their axioms, structural features, inference rules, and computational checks in a typed, machine-consumable flow.

2. TYPED ENTITIES
entity Set S
entity Element x : S
entity Element y : S
entity Element z : S
entity BinaryRelation R : subset(S × S)
entity Poset P : tuple(S,R)
entity Chain C : subset(S)
entity Antichain A : subset(S)
entity UpperBound u : S
entity LowerBound l : S
entity LeastUpperBound sup : S optional
entity GreatestLowerBound inf : S optional
entity HasseDiagram H : directed_acyclic_graph

3. CORE DEFINITION
PARTIAL_ORDER(S,R) :=
  REFLEXIVE(S,R) AND ANTISYMMETRIC(S,R) AND TRANSITIVE(S,R)
REFLEXIVE(S,R) := forall x in S: R(x,x)
ANTISYMMETRIC(S,R) := forall x,y in S: (R(x,y) AND R(y,x)) => x=y
TRANSITIVE(S,R) := forall x,y,z in S: (R(x,y) AND R(y,z)) => R(x,z)
POSET(S,R) := PARTIAL_ORDER(S,R)
COMPARABLE(x,y) := R(x,y) OR R(y,x)
INCOMPARABLE(x,y) := NOT R(x,y) AND NOT R(y,x)
STRICT_ORDER(x,y) := R(x,y) AND x != y
TOTAL_ORDER(S,R) := PARTIAL_ORDER(S,R) AND forall x,y in S: COMPARABLE(x,y)

4. STRUCTURAL RELATIONSHIPS
CHAIN(C) := C subset S AND forall x,y in C: COMPARABLE(x,y)
ANTICHAIN(A) := A subset S AND forall distinct x,y in A: INCOMPARABLE(x,y)
MINIMAL(m) := m in S AND NOT exists x in S: STRICT_ORDER(x,m)
MAXIMAL(m) := m in S AND NOT exists x in S: STRICT_ORDER(m,x)
LEAST(l) := l in S AND forall x in S: R(l,x)
GREATEST(g) := g in S AND forall x in S: R(x,g)
UPPER_BOUND(u,T) := u in S AND forall t in T: R(t,u)
LOWER_BOUND(l,T) := l in S AND forall t in T: R(l,t)
SUPREMUM(u,T) := UPPER_BOUND(u,T) AND forall v in S: UPPER_BOUND(v,T) => R(u,v)
INFIMUM(l,T) := LOWER_BOUND(l,T) AND forall v in S: LOWER_BOUND(v,T) => R(v,l)
COVER(x,y) := STRICT_ORDER(x,y) AND NOT exists z in S: STRICT_ORDER(x,z) AND STRICT_ORDER(z,y)

5. ALGEBRAIC AND LOGICAL LAWS
LAW Reflexivity: x <= x
LAW Antisymmetry: (x <= y AND y <= x) => x=y
LAW Transitivity: (x <= y AND y <= z) => x <= z
LAW UniqueLeast: LEAST(a) AND LEAST(b) => a=b
LAW UniqueGreatest: GREATEST(a) AND GREATEST(b) => a=b
LAW LeastImpliesMinimal: LEAST(a) => MINIMAL(a)
LAW GreatestImpliesMaximal: GREATEST(a) => MAXIMAL(a)
LAW Duality: reversing R exchanges least/greatest, minimal/maximal, upper/lower, sup/inf
NOTE: A minimal element need not be least; a maximal element need not be greatest.
NOTE: An arbitrary poset need not contain bounds, a supremum, or an infimum.

6. EXAMPLES
EXAMPLE SubsetOrder: (PowerSet(U), subseteq)
EXAMPLE Divisibility: (PositiveIntegers, divides)
EXAMPLE NaturalOrder: (Integers, <=) is a total order and therefore a partial order
EXAMPLE Incomparability: {a} and {b} are incomparable under subseteq when a != b

7. INFERENCE RULES
RULE R1: R(x,y), R(y,z) -> R(x,z)
RULE R2: R(x,y), R(y,x) -> EQUAL(x,y)
RULE R3: LEAST(x) -> MINIMAL(x)
RULE R4: GREATEST(x) -> MAXIMAL(x)
RULE R5: TOTAL_ORDER(S,R) -> PARTIAL_ORDER(S,R)
RULE R6: PARTIAL_ORDER(S,R) -> PARTIAL_ORDER(S,INVERSE(R))
RULE R7: SUPREMUM(u,T), SUPREMUM(v,T) -> EQUAL(u,v)

8. VALIDATION
CHECK relation_pairs_are_members_of_S_cross_S
CHECK reflexivity_for_all_elements
CHECK antisymmetry_for_all_pairs
CHECK transitivity_for_all_triples
CHECK strict_relation_is_irreflexive_and_transitive
CHECK HasseDiagram_edges_match_cover_relation_for_finite_posets
CHECK acyclic_HasseDiagram_for_finite_posets
CHECK claimed_bounds_against_all_members_of_T
CHECK claimed_supremum_or_infimum_is_unique
FAIL if any required partial-order axiom is violated

9. SEMANTIC RELATIONSHIPS
PARTIAL_ORDER IS_A BinaryRelation
PARTIAL_ORDER HAS_PROPERTY Reflexive
PARTIAL_ORDER HAS_PROPERTY Antisymmetric
PARTIAL_ORDER HAS_PROPERTY Transitive
TOTAL_ORDER IS_A PartialOrder
POSET COMPOSED_OF Set AND PartialOrder
HASSE_DIAGRAM REPRESENTS FinitePoset
PARTIAL_ORDER RELATED_TO LatticeTheory
PARTIAL_ORDER RELATED_TO DependencyOrdering
PARTIAL_ORDER RELATED_TO KnowledgeRepresentation

10. SEMANTIC_EQUIVALENCE
"partial order" <=> "reflexive antisymmetric transitive binary relation"
"partially ordered set" <=> "poset"
"least upper bound" <=> "supremum"
"greatest lower bound" <=> "infimum"
CAUTION: "minimal" != "least" in general
CAUTION: "maximal" != "greatest" in general
CAUTION: "partial order" != "total order" in general

11. CONFIDENCE
mathematical_axioms: 1.00
standard_definitions: 1.00
source_page_alignment: unverified
assertion_policy: do_not_infer_totality_or_bounds_without_proof

12. FLOW_HASH
algorithm: SHA-256
input: canonical_utf8(normalised_flow_without_FLOW_HASH_value)
value: COMPUTE_ON_PUBLISH

13. UPDATE_MODEL
version: 1.0
change_policy: preserve_axioms_and_mathematical_invariants
on_update: revalidate_types_axioms_rules_examples_and_hash
provenance: maintain_source_url_and_revision_history

14. AI_CONSUMPTION
format: plain_text_flow_algebra
parse: entities -> predicates -> laws -> rules -> validation -> metadata
reasoning_mode: typed_symbolic_deduction
inference_constraints: preserve_domain_and_quantifier_scope
uncertainty_policy: distinguish_verified_theorems_from_unverified_page_content
output: validated_partial_order_knowledge_graph

END FLOW ALGEBRA