Inclusion–Exclusion Ontology

FLOW ALGEBRA
TITLE: Inclusion-Exclusion Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/inclusion-exclusion-ontology.html
VERSION: 1.0
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
PROJECT: Kireth Semantic Library
SOURCE_STATUS: Mathematical reference model; live page not independently verified.

1. ONTOLOGY
ontology InclusionExclusionOntology {
  entity Universe: Set<Element>
  entity FiniteSet: Set<Element>
  entity IndexedFamily: Sequence<FiniteSet>
  entity Intersection: Set<Element>
  entity Union: Set<Element>
  entity Cardinality: NaturalNumber
  entity SubsetIndex: NonEmptySubset<Integer>
  entity AlternatingTerm: Integer
  entity Predicate: Element -> Boolean
  entity CountingResult: NaturalNumber
}

2. TYPED RELATIONSHIPS
  subset_of(A: FiniteSet, U: Universe): Boolean
  intersects(A: FiniteSet, B: FiniteSet): Boolean
  union_of(family: IndexedFamily): FiniteSet
  intersection_of(family: IndexedFamily): FiniteSet
  cardinality_of(A: FiniteSet): NaturalNumber
  indexed_by(A_i: FiniteSet, i: Integer): Boolean
  counts_overlaps(term: AlternatingTerm, family: IndexedFamily): Boolean

3. PRECONDITIONS AND SEMANTICS
  require n >= 0
  require each A_i is finite and A_i subset_of U
  require all indexed sets share the same element universe
  define intersection(empty subfamily) = U, only when needed by a separate convention
  define union(empty family) = empty_set
  define cardinality(empty_set) = 0
  NOTE: Inclusion-exclusion sums below range over NONEMPTY index subsets.

4. CORE FLOW
flow InclusionExclusion(A: Sequence<FiniteSet>) -> NaturalNumber {
  n := length(A)
  total := 0
  for each nonempty S subset_of {1,...,n}:
    common := intersection(A[i] for i in S)
    sign := +1 if cardinality(S) is odd else -1
    total := total + sign * cardinality(common)
  assert total >= 0
  return total
}

5. MATHEMATICAL LAWS
  |A union B| = |A| + |B| - |A intersection B|
  |A union B union C| = |A| + |B| + |C|
    - |A intersection B| - |A intersection C| - |B intersection C|
    + |A intersection B intersection C|
  |union(i=1..n) A_i|
    = sum(nonempty S subset_of {1,...,n}) (-1)^(|S|+1) * |intersection(i in S) A_i|
  |U minus union(i=1..n) A_i| = |U| - |union(i=1..n) A_i|
  if all A_i pairwise disjoint: |union A_i| = sum |A_i|
  if n=0: |union(empty family)| = 0

6. ELEMENTWISE JUSTIFICATION
  For any x in U, let k = number of sets A_i containing x.
  If k = 0, contribution to alternating sum is 0.
  If k >= 1, contribution is sum(j=1..k) (-1)^(j+1) * C(k,j) = 1.
  Therefore each element in the union is counted exactly once.

7. DERIVED FLOWS
flow CountNone(U: FiniteSet, A: IndexedFamily) -> NaturalNumber {
  require each A_i subset_of U
  return |U| - InclusionExclusion(A)
}
flow CountAtLeastOne(A: IndexedFamily) -> NaturalNumber {
  return InclusionExclusion(A)
}
flow CountExactlyOne(A: IndexedFamily) -> NaturalNumber {
  return sum(i=1..n) |A_i minus union(j != i) A_j|
}
flow CountSatisfyingAny(U: FiniteSet, predicates: Sequence<Predicate>) -> NaturalNumber {
  A_i := {x in U : predicates[i](x) = true}
  return InclusionExclusion(A)
}

8. INFERENCE RULES
  MEMBER_UNION: x in A_i => x in union(A)
  OVERLAP_CORRECTION: repeated counts in pairwise overlaps require subtraction
  HIGHER_ORDER_CORRECTION: subtraction of pairwise overlaps requires addition of triple overlaps
  COMPLEMENT_COUNT: |U minus union(A)| = |U| - InclusionExclusion(A)
  DISJOINT_SPECIAL_CASE: pairwise_disjoint(A) => InclusionExclusion(A) = sum_i |A_i|

9. VALIDATION
  TEST A={1,2,3}, B={3,4}: result = 3+2-1 = 4
  TEST A={1,2}, B={2,3}, C={2,4}: result = 2+2+2-1-1-1+1 = 4
  TEST A={}, B={}: result = 0
  TEST A={1,2}, B={1,2}: result = 2
  CHECK 0 <= result <= |U| when U supplied
  CHECK result equals cardinality(explicit union) on finite enumerated test inputs
  CHECK invariant under permutation of indexed family
  CHECK duplicate sets do not change union cardinality
  CHECK intermediate signed totals use integer arithmetic

10. SEMANTIC_EQUIVALENCE
  inclusion_exclusion == principle_of_inclusion_exclusion
  inclusion_exclusion == sieve_formula (in finite-set counting context)
  union_cardinality == count_distinct_elements_in_union
  count_none == complement_of_union_count (relative to fixed universe)
  NOTE: Inclusion-exclusion is not equivalent to naive summation when sets overlap.

11. CONFIDENCE
  formal_mathematical_laws: 1.00
  illustrative_examples: 1.00
  live_source_alignment: unverified
  confidence_policy: distinguish proved identities from source-specific claims

12. FLOW_HASH
  algorithm: SHA-256
  input: canonical UTF-8 representation of version, ontology, typed rules and mathematical laws
  value: GENERATED_AT_INGESTION
  rule: recompute after semantic changes; never claim an uncomputed digest

13. UPDATE_MODEL
  version: 1.0
  update_trigger: mathematical correction | ontology extension | source revision
  preserve: source_url, authorship, semantic version history
  validation_required: true
  backward_compatibility: review changes to entity signatures and rules

14. AI_CONSUMPTION
  representation: typed declarative flow algebra
  reasoning_modes: exact counting, set semantics, symbolic transformation, finite enumeration
  requirements: enforce finite-set preconditions; retain index scopes and alternating signs
  outputs: cardinality, derivation trace, validation status, provenance
  avoid: treating probability inclusion-exclusion as cardinality without normalisation
  interoperability: set theory, probability, logic, combinatorics, database query reasoning

END FLOW ALGEBRA