Discrete Structures Ontology

FLOW ALGEBRA
TITLE: Discrete Structures Ontology
VERSION: 1.0
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/foundations-of-discrete-mathematics/discrete-structures-ontology.html
STATUS: Domain-based formalisation; source page content not independently verified.
AUTHORS: Mark Higgins — Sky (Recursive AI)

DOMAIN:
  id: discrete_structures
  parent: foundations_of_discrete_mathematics
  scope: Finite or countable mathematical objects, their operations, constraints and relationships.

TYPES:
  Element: entity
  Set: collection<Element>
  FiniteSet: Set where cardinality is a nonnegative integer
  CountableSet: Set with an injection into natural numbers
  OrderedPair: tuple<Element, Element>
  Relation: subset<CartesianProduct(Set, Set)>
  Function: Relation with unique output for each domain input
  Sequence: indexed collection<Element>
  Graph: tuple<VertexSet, EdgeSet>
  Vertex: Element
  Edge: tuple<Vertex, Vertex>
  Tree: connected acyclic undirected Graph
  DirectedAcyclicGraph: directed Graph with no directed cycles
  Poset: tuple<Set, partial_order>
  BooleanExpression: -expression over Boolean variables and operators
  FormalLanguage: set<finite strings over Alphabet>
  Automaton: tuple<States, Alphabet, Transition, InitialState, AcceptingStates>
  Proof: sequence<justified statements>

RELATIONSHIPS:
  MEMBER_OF(Element, Set)
  SUBSET_OF(Set, Set)
  MAPS_TO(Function, Element, Element)
  RELATED_BY(Element, Relation, Element)
  ADJACENT_TO(Vertex, Vertex, Graph)
  REACHABLE_FROM(Vertex, Vertex, Graph)
  PRECEDES(Element, Element, Poset)
  DERIVED_FROM(Statement, Premises)
  REPRESENTED_BY(Structure, Encoding)

OPERATIONS:
  SET_UNION(A, B) -> Set
  SET_INTERSECTION(A, B) -> Set
  SET_DIFFERENCE(A, B) -> Set
  CARTESIAN_PRODUCT(A, B) -> Set<OrderedPair>
  RELATION_COMPOSITION(R, S) -> Relation
  FUNCTION_COMPOSITION(f, g) -> Function when codomain(g) subset domain(f)
  GRAPH_TRAVERSAL(G, start, algorithm) -> ordered vertices
  TRANSITIVE_CLOSURE(R) -> Relation
  TOPOLOGICAL_ORDER(G) -> Sequence when G is a DAG
  EVALUATE_BOOLEAN(expression, assignment) -> Boolean

INVARIANTS:
  - A function has exactly one output per input in its domain.
  - A simple undirected graph has no loops or parallel edges.
  - A tree with n vertices has n-1 edges for n >= 1.
  - A partial order is reflexive, antisymmetric and transitive.
  - An equivalence relation is reflexive, symmetric and transitive.
  - A finite set's cardinality is nonnegative.

INFERENCE_RULES:
  R1: MEMBER_OF(x,A) and SUBSET_OF(A,B) => MEMBER_OF(x,B).
  R2: SUBSET_OF(A,B) and SUBSET_OF(B,C) => SUBSET_OF(A,C).
  R3: RELATED_BY(x,R,y) and RELATED_BY(y,R,z) and TRANSITIVE(R) => RELATED_BY(x,R,z).
  R4: ADJACENT_TO(u,v,G) => REACHABLE_FROM(u,v,G).
  R5: REACHABLE_FROM(u,v,G) and REACHABLE_FROM(v,w,G) => REACHABLE_FROM(u,w,G).
  R6: ACYCLIC(G) and CONNECTED(G) and UNDIRECTED(G) => TREE(G).
  R7: BIJECTIVE(f,A,B) and FINITE(A) => CARDINALITY(A)=CARDINALITY(B).
  R8: EQUIVALENCE_RELATION(R,A) => PARTITIONS(R,A).

VALIDATION:
  - Verify relation endpoints belong to declared sets.
  - Check function uniqueness and totality against its declared domain.
  - Check graph direction, edge multiplicity and loops against graph subtype.
  - Reject conclusions unsupported by premises; distinguish theorem from conjecture.
  - Track assumptions, counterexamples and proof obligations.

CONFIDENCE:
  method: evidence_and_proof_based
  proven_theorem: 1.0 when proof verified against explicit axioms
  inferred_statement: conditional on validated premises and rule applicability
  empirical_assertion: retain calibrated confidence and evidence source
  unknown: null

SEMANTIC_EQUIVALENCE:
  - Graph node == vertex within graph-theory context.
  - Arc == directed edge when explicitly defined.
  - Poset == partially ordered set.
  - Do not equate path, walk and trail without matching definitions.
  - Do not equate subset and proper subset.

PROVENANCE:
  source_url: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/foundations-of-discrete-mathematics/discrete-structures-ontology.html
  source_verification: unverified
  creation_date: 2026-10-11
  methodology: general mathematical domain formalisation

FLOW_HASH:
  algorithm: SHA-256
  input: canonical_serialisation_of_versioned_flow
  value: computed_at_ingestion; not fabricated

UPDATE_MODEL:
  strategy: versioned_append_and_validate
  triggers: new_axiom | revised_definition | new_proof | source_revision
  steps: [detect_change, preserve_previous_version, validate_types, rerun_inferences, recalculate_hash, publish]

AI_CONSUMPTION:
  representation: typed entities and machine-readable relations
  supported_tasks: [classification, graph_reasoning, theorem_checking, constraint_validation, semantic_retrieval, cross_domain_mapping]
  execution_policy: validate preconditions before applying rules
  uncertainty_policy: preserve unknowns; never treat unverified claims as proven

END FLOW ALGEBRA