Cartesian Product Ontology

FLOW ALGEBRA
CARTESIAN PRODUCT ONTOLOGY
Kireth Semantic Library | Entity Graph | Mathematical Entities | Set Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/set-entities/cartesian-product-ontology-3.html
Authors: Mark Higgins — Sky (Recursive AI)
Version: 1.0 | Date: 2026-10-13 | Language: en-GB
Source status: Formal mathematical specification; source page text not independently verified.

01. PURPOSE
flow "CartesianProductOntology" v1.0
  domain: set_theory
  concept: CartesianProduct
  notation: A × B
  output: typed ordered tuples and their product set

02. TYPES
  Set[T] = collection of elements of type T
  OrderedPair[A,B] = (first:A, second:B)
  Tuple[T1,...,Tn] = positionally ordered n-tuple
  Product[A,B] = Set[OrderedPair[A,B]]
  Predicate[T] = T -> Boolean
  Cardinal = finite or infinite cardinal number

03. DEFINITION
  CartesianProduct(A:Set[X], B:Set[Y]) := {(a,b) | a in A and b in B}
  membership: (a,b) in A×B iff a in A AND b in B
  ordered_pair_equality: (a,b)=(c,d) iff a=c AND b=d
  note: ordered pairs are not unordered two-element sets

04. ENTITY SCHEMA
  CartesianProductEntity:
    id: URI
    left_factor: Set[X]
    right_factor: Set[Y]
    elements: Set[OrderedPair[X,Y]]
    arity: 2
    ordering: positional
    source_uri: URI
    provenance: record

05. CONSTRUCTION
  product(A,B):
    require is_set(A) and is_set(B)
    return {(a,b) for a in A for b in B}
  finite_example:
    A={1,2}; B={x,y}
    A×B={(1,x),(1,y),(2,x),(2,y)}

06. EMPTY FACTOR RULE
  A×empty = empty
  empty×B = empty
  if A×B is nonempty then A and B are both nonempty
  caution: A×B=empty does not imply both factors are empty

07. ORDER AND COMMUTATIVITY
  generally A×B != B×A as sets of ordered pairs
  swap: A×B -> B×A; (a,b) |-> (b,a)
  swap is a bijection
  do_not_rewrite: A×B = B×A without additional justification

08. ASSOCIATIVITY
  (A×B)×C and A×(B×C) have different nested tuple shapes
  canonical_associator: ((a,b),c) |-> (a,(b,c))
  canonical_associator_is_bijection: true
  do_not_assert_literal_set_equality_without_tuple_convention

09. N-ARY PRODUCTS
  Product(A1,...,An) := {(a1,...,an) | each ai in Ai}
  n=0: empty_product is a singleton containing the empty tuple
  n=1: singleton-length tuples correspond canonically to A1
  n>1: positional component domains are preserved

10. CARDINALITY
  |A×B| = |A| * |B| (cardinal multiplication)
  finite: if |A|=m and |B|=n then |A×B|=m*n
  finite_n_ary: |Product(A1,...,An)| = product_i |Ai|
  infinite_cardinality: use cardinal arithmetic, not ordinary real multiplication

11. SUBSET MONOTONICITY
  if A subset C and B subset D then A×B subset C×D
  if A subset C then A×B subset C×B
  converse_inference_requires_nonempty_other_factor

12. DISTRIBUTIVITY
  A×(B union C) = (A×B) union (A×C)
  (A union B)×C = (A×C) union (B×C)
  A×(B intersect C) = (A×B) intersect (A×C)
  (A intersect B)×C = (A×C) intersect (B×C)
  A×(B difference C) = (A×B) difference (A×C)
  (A difference B)×C = (A×C) difference (B×C)

13. RELATIONS
  BinaryRelation(A,B) = subset_of(A×B)
  RelationOn(A) = subset_of(A×A)
  domain(R) = {a | exists b: (a,b) in R}
  range(R) = {b | exists a: (a,b) in R}
  require R subset A×B for relation_from_A_to_B

14. FUNCTIONS
  Function(A,B) = relation f subset A×B with
    for_all a in A: exists_unique b in B such_that (a,b) in f
  function_graph(f) subset A×B
  note: not every subset of A×B is a function

15. COORDINATE AND PRODUCT SPACES
  R×R conventionally written R^2
  R×R×R conventionally written R^3 using flat tuples
  coordinates: ordered components, not unordered members
  product_topology: requires topological structures on factors
  vector_space_product: requires compatible vector space structures

16. PROJECTIONS
  pi1: A×B -> A; pi1(a,b)=a
  pi2: A×B -> B; pi2(a,b)=b
  pi1 and pi2 are total functions
  surjective_if: opposite factor is nonempty (for nonempty codomain)
  pairing: given f:X->A and g:X->B, <f,g>:X->A×B
  pairing(x)=(f(x),g(x))

17. SEMANTIC RELATIONSHIPS
  CartesianProduct --is_a--> SetConstruction
  CartesianProduct --has_left_factor--> Set
  CartesianProduct --has_right_factor--> Set
  CartesianProduct --contains--> OrderedPair
  OrderedPair --has_first_component--> Element
  OrderedPair --has_second_component--> Element
  BinaryRelation --is_subset_of--> CartesianProduct
  FunctionGraph --is_subset_of--> CartesianProduct
  Projection --maps_from--> CartesianProduct

18. SEMANTIC EQUIVALENCE
  A×B equivalent_to {(a,b) | a in A and b in B}
  tuple_reordering: isomorphic_under_swap, not generally identical
  tuple_reassociation: canonically_bijective, not literally identical
  canonicalisation: preserve factor order and tuple nesting

19. INFERENCE RULES
  R1: a in A AND b in B => (a,b) in A×B
  R2: (a,b) in A×B => a in A AND b in B
  R3: A=empty OR B=empty => A×B=empty
  R4: finite(A) AND finite(B) => |A×B|=|A|*|B|
  R5: R subset A×B => R is a binary relation from A to B
  R6: A subset C AND B subset D => A×B subset C×D
  R7: (a,b)=(c,d) => a=c AND b=d

20. VALIDATION
  validate_factors: both operands must denote sets
  validate_pairs: each member must be ordered and length two
  validate_membership: first in A; second in B
  validate_types: preserve factor-specific types
  validate_empty: empty factor yields empty product
  validate_equality: compare ordered components
  validate_cardinality: finite enumeration agrees with m*n
  reject: automatic commutativity or literal associativity

21. CONFIDENCE
  formal_axioms: 1.0 within stated set-theoretic conventions
  derived_claims: proof_or_rule_reference_required
  empirical_claims: not_applicable
  source_alignment: unverified_page_content
  confidence_does_not_replace_proof: true

22. FLOW_HASH
  canonical_fields: [concept, factors, ordered_pair_semantics, rules, version]
  canonical_encoding: UTF-8; normalise line endings; stable field order
  algorithm: SHA-256
  hash_value: computed_on_ingestion_not_fabricated

23. UPDATE_MODEL
  on_source_revision: compare ontology concepts and relationships
  on_axiom_revision: revalidate dependent inference rules
  on_schema_revision: increment version and preserve migration map
  on_semantic_change: regenerate canonical hash
  provenance: retain previous version and source timestamp

24. AI_CONSUMPTION
  ingest: parse typed entities, relations, rules and constraints
  retrieve: by URI, concept, notation or relation type
  reason: apply only sound rules with satisfied preconditions
  generate: produce ordered tuples with explicit factor domains
  explain: report construction, membership and cardinality proof
  distinguish: equality versus bijection/isomorphism
  output: machine-readable assertions with provenance

25. EXAMPLES AND TESTS
  test_1: {1,2}×{a} = {(1,a),(2,a)}
  test_2: {1}×empty = empty
  test_3: ({1}×{2}) != ({2}×{1})
  test_4: |{1,2}×{a,b,c}| = 6
  test_5: pi1((1,a))=1; pi2((1,a))=a
  test_6: {(1,a)} subset {1,2}×{a,b}
  test_7: swap((1,a))=(a,1)

END FLOW ALGEBRA