Counting Principle Ontology

FLOW ALGEBRA
TITLE: Counting Principle Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/counting-principle-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Formal mathematical synthesis; live page not independently verified.

1. ONTOLOGY
ontology CountingPrincipleOntology {
  entity FiniteSet : Set<Element>
  entity DisjointFamily : Sequence<FiniteSet>
  entity ChoiceStage : FiniteSet
  entity Outcome : Tuple<Element>
  entity Constraint : Predicate<Outcome>
  entity CountingResult : NaturalNumber
  relation disjoint(A:FiniteSet,B:FiniteSet) : Boolean
  relation independent_choices(stages:Sequence<ChoiceStage>) : Boolean
  relation admissible(outcome:Outcome, constraint:Constraint) : Boolean
  operation cardinality(A:FiniteSet) -> NaturalNumber
  operation disjoint_union(sets:DisjointFamily) -> FiniteSet
  operation cartesian_product(stages:Sequence<ChoiceStage>) -> FiniteSet
  operation count_valid(stages, constraint) -> NaturalNumber
}

2. FORMAL SEMANTICS
- Cardinality |A| counts distinct elements of finite set A.
- Addition principle: for pairwise disjoint finite A_1,...,A_k,
  |A_1 union ... union A_k| = sum(i=1..k) |A_i|.
- General union for two finite sets:
  |A union B| = |A| + |B| - |A intersection B|.
- Multiplication principle: for finite choice sets A_1,...,A_k,
  |A_1 x ... x A_k| = product(i=1..k) |A_i|.
- Dependent stages: if each valid partial outcome at stage i has exactly n_i
  extensions, the total is product(i=1..k) n_i. Fixed extension counts
  are required; mere existence of successive stages is insufficient.
- Complement principle: |A \ B| = |A| - |B| when B subseteq A.
- Division principle: if a finite set of labelled representations
  partitions into equivalence classes each of exactly m elements,
  number of distinct classes = |A| / m (m > 0).
- Bijection principle: if f:A -> B is bijective, then |A| = |B|.
- Pigeonhole principle: distributing n+1 objects among n boxes (n>0)
  forces at least one box to contain two or more objects.

3. DERIVED IDENTITIES
- Ordered selections without replacement: P(n,r) = n!/(n-r)!
  for 0 <= r <= n.
- Unordered selections without replacement: C(n,r) = n!/[r!(n-r)!].
- Binary subset choices: |P(A)| = 2^|A| for finite A.
- Inclusion-exclusion for finite A_1,...,A_k:
  |union A_i| = sum(nonempty S subseteq {1,...,k})
                (-1)^(|S|+1) |intersection(i in S) A_i|.
- Sum rule applies directly to disjoint alternatives; otherwise
  overlap correction is necessary.

4. TYPED FLOW OPERATIONS
flow CountAlternatives(family:DisjointFamily) -> CountingResult:
  require pairwise_disjoint(family)
  return sum(cardinality(A) for A in family)

flow CountSequentialChoices(stages:Sequence<ChoiceStage>) -> CountingResult:
  require all_finite(stages)
  return product(cardinality(A) for A in stages)

flow CountConstrainedChoices(stages, predicate:Constraint) -> CountingResult:
  candidates := cartesian_product(stages)
  return cardinality({x in candidates | predicate(x)})

flow CountByBijection(A:FiniteSet, B:FiniteSet, f) -> CountingResult:
  require bijection(f,A,B)
  return cardinality(B)

5. SEMANTIC RELATIONSHIPS
CountingPrinciple --isPartOf--> Combinatorics
AdditionPrinciple --requires--> DisjointAlternatives
MultiplicationPrinciple --counts--> CartesianProduct
InclusionExclusion --corrects--> OverlappingAlternatives
BijectionPrinciple --preserves--> Cardinality
PigeonholePrinciple --constrains--> Occupancy
Permutation --counts--> OrderedSelection
Combination --counts--> UnorderedSelection

6. INFERENCE RULES
R1: pairwise_disjoint(A_i) => |union A_i| = sum |A_i|.
R2: finite(A_i) => |product A_i| = product |A_i|.
R3: bijection(A,B) => |A| = |B|.
R4: B subseteq A => |A\B| = |A| - |B|.
R5: n_objects > n_boxes and n_boxes > 0 => some box has >= 2 objects.
R6: finite(A,B) => |A union B| = |A|+|B|-|A intersection B|.

7. VALIDATION
V1: All counted sets are finite unless an infinite-cardinality extension is declared.
V2: Cardinalities and counting results are non-negative integers.
V3: Addition rule checks pairwise disjointness.
V4: Product rule verifies choice spaces and stage dependence assumptions.
V5: Division rule verifies uniform class size and nonzero divisor.
V6: Permutation/combination arguments satisfy 0 <= r <= n.
V7: Test empty set: |empty|=0; empty Cartesian product of zero factors
    contains one empty tuple by convention.
V8: Counterexample: A={1,2}, B={2,3}; |A union B|=3, not 4.

8. SEMANTIC_EQUIVALENCE
- Sum Rule <=> Addition Principle (under disjoint alternatives).
- Product Rule <=> Multiplication Principle (for finite Cartesian products).
- One-to-One Correspondence <=> Bijection (for specified sets).
- Counting by Complement <=> Total minus Excluded (when subset conditions hold).
Equivalence is scoped to the stated mathematical assumptions.

9. CONFIDENCE
- Formal definitions and classical identities: 1.00 (mathematical, conditional on assumptions).
- Application-specific classification: requires evidence and validation.
- Confidence is not a substitute for a proof or data provenance.

10. FLOW_HASH
algorithm: SHA-256
canonicalisation: UTF-8; LF newlines; exclude FLOW_HASH computed value
value: COMPUTE_ON_PUBLICATION

11. UPDATE_MODEL
trigger: definition_change | theorem_correction | ontology_alignment | source_revision
steps: validate_types -> verify_assumptions -> run_examples -> compare_version
       -> compute_flow_hash -> publish_version
preserve: provenance, revision_history, mathematical_counterexamples

12. AI_CONSUMPTION
mode: typed_semantic_reasoning
inputs: finite sets, selection stages, constraints, known bijections
outputs: counts, assumptions, derivations, validation status
requirements:
  - Distinguish ordered from unordered choices.
  - Distinguish replacement from non-replacement.
  - Check overlap before applying the sum rule.
  - Report assumptions and exact arithmetic.
  - Do not infer independence without evidence.
  - Reject invalid premises rather than fabricating a count.

END FLOW ALGEBRA