Pigeonhole Principle Ontology

FLOW ALGEBRA
TITLE: Pigeonhole Principle Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/pigeonhole-principle-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
PROJECT: Kireth Semantic Library
SOURCE_STATUS: Mathematical synthesis; live source page not independently verified.

1. PURPOSE
Represent the pigeonhole principle as a typed, checkable counting and inference framework for finite allocations, occupancy bounds, collisions and combinatorial proofs.

2. TYPED ENTITIES
ENTITY Object : element of finite set O
ENTITY Container : element of finite set B
ENTITY Allocation : total function f : O -> B
ENTITY Occupancy : function occ_f : B -> NaturalNumber
ENTITY ObjectCount : n = |O|
ENTITY ContainerCount : m = |B|
ENTITY CapacityBound : nonnegative integer k
ENTITY Collision : distinct x,y in O with f(x)=f(y)
ENTITY WitnessContainer : b in B satisfying an occupancy condition
ENTITY ProofCertificate : premises, conclusion and verifiable witness
CONSTRAINT: O and B are finite; m >= 1 for division-based bounds.

3. CORE DEFINITIONS
DEFINE occ_f(b) := |{x in O : f(x)=b}|
INVARIANT sum_{b in B} occ_f(b) = n
DEFINE maximum_occupancy(f) := max_{b in B} occ_f(b)
DEFINE minimum_occupancy(f) := min_{b in B} occ_f(b)

4. FUNDAMENTAL PIGEONHOLE PRINCIPLE
RULE PHP_BASIC:
  GIVEN n > m >= 1 AND total f : O -> B
  INFER EXISTS distinct x,y in O : f(x)=f(y)
  EQUIVALENT: f is not injective.
PROOF: An injective function between finite sets requires |O| <= |B|.

5. GENERALISED PIGEONHOLE PRINCIPLE
RULE PHP_GENERAL:
  GIVEN n >= 1 AND m >= 1 AND total f : O -> B
  INFER EXISTS b in B : occ_f(b) >= ceil(n/m)
RULE PHP_CAPACITY:
  GIVEN k >= 0 AND n > k*m
  INFER EXISTS b in B : occ_f(b) >= k+1
RULE PHP_LOWER:
  GIVEN m >= 1
  INFER EXISTS b in B : occ_f(b) <= floor(n/m)
RULE PHP_BALANCED:
  GIVEN n,m >= 1
  THERE EXISTS an allocation where every occupancy belongs to
    {floor(n/m), ceil(n/m)}.
NOTE: PHP_BALANCED is an existence statement, not a property of every allocation.

6. RELATIONSHIPS
RELATION allocated_to(Object, Container)
RELATION shares_container(Object, Object)
RELATION has_occupancy(Container, NaturalNumber)
RELATION proves_lower_bound(ProofCertificate, CapacityBound)
RELATION witnesses_collision(Object, Object, Container)
SEMANTIC_EQUIVALENCE:
  "pigeonhole principle" <=> "drawer principle" (terminological synonym)
  "n > m forces collision" <=> "no injection from an n-element set into an m-element set when n > m"
  "at least one box has >= ceil(n/m) objects" <=> generalised occupancy bound
CAUTION: The finite assumptions are essential to these counting formulations.

7. INFERENCE FLOWS
FLOW CollisionDetection:
  INPUT finite O, finite B, total f
  CHECK |O| > |B| >= 1
  DERIVE noninjective(f)
  OUTPUT collision_exists=true
FLOW MinimumMaximumLoad:
  INPUT n,m where n >= 1 and m >= 1
  COMPUTE q=ceil(n/m)
  DERIVE exists_container_with_occupancy_at_least(q)
  OUTPUT lower_bound=q
FLOW CapacityContradiction:
  INPUT n,m,k
  ASSUME for_all b in B: occ_f(b) <= k
  DERIVE n=sum occ_f(b) <= k*m
  IF n > k*m THEN contradiction
  OUTPUT some_container_has_at_least(k+1)

8. ALGEBRAIC LAWS AND BOUNDS
LAW SUM_OCCUPANCIES: sum_b occ_f(b)=n
LAW MAX_BOUND: max_b occ_f(b) >= ceil(n/m) for m>=1
LAW MIN_BOUND: min_b occ_f(b) <= floor(n/m) for m>=1
LAW INJECTION_BOUND: injective(f) => n<=m
LAW SURJECTION_BOUND: surjective(f) => n>=m
LAW EXACT_BALANCE: n=m*q+r, 0<=r<m;
  balanced allocations can have r containers of size q+1 and m-r of size q.

9. EXAMPLES
EXAMPLE A: 13 objects, 12 containers => at least one container holds 2 or more.
EXAMPLE B: 22 objects, 5 containers => at least one container holds 5 or more.
EXAMPLE C: 10 objects, 3 containers => at least one container holds 4 or more.
COUNTEREXAMPLE: 3 objects, 5 containers do not force a collision.

10. VALIDATION
VALIDATE finite(O) AND finite(B)
VALIDATE allocation f is total on O and maps into B
VALIDATE m>0 before calculating ceil(n/m)
VALIDATE n=sum_b occ_f(b)
VALIDATE witness b is in B and occ_f(b)>=claimed_bound
VALIDATE collision witnesses x!=y and f(x)=f(y)
REJECT claims of forced collision when n<=m without further premises.
REJECT interpreting the guaranteed maximum occupancy as an exact value.

11. CONFIDENCE
CONFIDENCE:
  mathematical_theorems: 1.0 (under stated finite assumptions)
  example_calculations: 1.0 (if inputs validated)
  external_empirical_allocations: requires evidence and provenance
  semantic_aliases: contextual; review terminology in application

12. FLOW_HASH
FLOW_HASH:
  method: SHA-256
  canonicalisation: UTF-8, LF line endings, stable key ordering
  scope: canonical flow content excluding the FLOW_HASH digest field
  digest: COMPUTE_ON_INGEST

13. UPDATE_MODEL
UPDATE_MODEL:
  change_detection: source URL, definitions, inference rules, examples
  semantic_versioning: major for theorem/typing changes; minor for additions
  revalidation: rerun finite-set, arithmetic and witness checks
  provenance: retain prior versions and source verification status

14. AI_CONSUMPTION
AI_CONSUMPTION:
  input_schema: {objects: finite_set, containers: finite_set, allocation?: total_mapping}
  operations: [detect_forced_collision, bound_maximum_occupancy, verify_witness]
  outputs: [theorem_applied, premises, bound, proof_trace, witness_if_available]
  safeguards: [check_finiteness, avoid_division_by_zero, distinguish_existence_from_witness]
  interoperability: [set_theory, function_ontology, combinatorics, counting_principles]

END FLOW ALGEBRA