TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)verified 2026-07-29 (claude-fable-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

If $∣ A ∣ > k ∣ B ∣$ then every $f : A \to B$ has a fibre with more than $k$ elements, and for nonempty $B$ some fibre has at least $⌈ ∣ A ∣ / ∣ B ∣ ⌉$ elements

Statement

Let $A$ and $B$ be finite sets, let $k \in N$ , let $f : A \to B$ , and for $b \in B$ write

$f^{- 1} [{b}] : = {a \in A : f (a) = b}$

for the fibre of $f$ over $b$ (Injection, surjection, bijection). Then:

The counting form. If $∣ A ∣ > k ∣ B ∣$ then there is $b \in B$ with $∣ f^{- 1} [{b}] ∣ > k$ .
The ceiling form. If $B \neq \emptyset$ then there is $b \in B$ with $∣ f^{- 1} [{b}] ∣ \geq ⌈ ∣ A ∣ / ∣ B ∣ ⌉$ ( $⌈ m / n ⌉$ for naturals $m$ and $n \geq 1$ : the least $q \in N$ with $m \leq n q$ , which is defined because $∣ B ∣ \geq 1$ ).

Every quantity here is a natural number and the comparisons are those of $N$ (Order on the natural numbers). Clause 1 at $k = 0$ says that a nonempty $A$ has a nonempty fibre. Clause 1 is vacuous when $B = \emptyset$ , since then $k ∣ B ∣ = 0$ , the hypothesis says $A \neq \emptyset$ , and there is no function from a nonempty set to $\emptyset$ for the conclusion to be about. Clause 2 at $A = \emptyset$ says only that some fibre has at least $0$ elements, since $⌈ 0 / ∣ B ∣ ⌉ = 0$ .

Facts & Assumptions

Given: Finite sets $A$ and $B$ , a natural number $k$ , a function $f : A \to B$ , and the fibres $f^{- 1} [{b}]$ for $b \in B$ .

[L1]

The fibres are pairwise disjoint subsets of $A$ whose union is $A$ : distinct values of $f$ give disjoint fibres, and every $a \in A$ lies in the fibre over $f (a)$ . Each fibre is finite (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , clause 1), so The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition clause 2 gives $∣ A ∣ = \sum_{b \in B} ∣ f^{- 1} [{b}] ∣$ in $N$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, The cardinality $∣ A ∣$ of a finite set).

[L2]

Monotonicity over a finite index set: if $c, d : S \to N$ satisfy $c_{i} \leq d_{i}$ for every $i \in S$ , then $\sum_{i \in S} c_{i} \leq \sum_{i \in S} d_{i}$ . Both sums are computed through one enumeration $ψ : ∣ S ∣ \to S$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form), and $c_{ψ (j)} \leq d_{ψ (j)}$ for every $j < ∣ S ∣$ , so clause 4 of Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ applies (Finite sums and finite products, by recursion).

[L3]

A constant natural summand: $\sum_{i \in S} k = ∣ S ∣ \cdot k$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, clause (c)).

[L4]

Order and arithmetic of $N$ : multiplication is commutative (Multiplication is commutative); exactly one of $p < q$ , $p = q$ , $q < p$ holds (Trichotomy of the order on $N$ ); $p < q$ if and only if $σ (p) \leq q$ (Discreteness: $σ (n)$ is the immediate successor); every nonzero natural is a successor (Every nonzero natural number is a successor); and $0 \leq p$ for every $p$ (Order on the natural numbers).

[L5]

The ceiling ( $⌈ m / n ⌉$ for naturals $m$ and $n \geq 1$ : the least $q \in N$ with $m \leq n q$ ): for $n \geq 1$ , $⌈ m / n ⌉$ is the least $q \in N$ with $m \leq n q$ , so any $q < ⌈ m / n ⌉$ satisfies $n q < m$ .

[L6]

$∣ B ∣ = 0$ if and only if $B = \emptyset$ (The cardinality $∣ A ∣$ of a finite set, clause (b)).

Proof

technique · contradiction

1.1

Suppose, for contradiction, that $∣ A ∣ > k ∣ B ∣$ and yet $∣ f^{- 1} [{b}] ∣ \leq k$ for every $b \in B$ .

assume-contra

1.2

By [L1], $∣ A ∣ = \sum_{b \in B} ∣ f^{- 1} [{b}] ∣$ .

1.3

For clause 2, assume $B \neq \emptyset$ ; then $∣ B ∣ \neq 0$ by [L6], so $∣ B ∣ \geq 1$ and $c : = ⌈ ∣ A ∣ / ∣ B ∣ ⌉$ is defined, and $B$ has at least one element.

L4L5L6

2.1

Clause 1. Under the assumption of step 1.1, monotonicity and the constant sum give $∣ A ∣ = \sum_{b \in B} ∣ f^{- 1} [{b}] ∣ \leq \sum_{b \in B} k = ∣ B ∣ \cdot k = k ∣ B ∣$ , which contradicts $∣ A ∣ > k ∣ B ∣$ by trichotomy. So the supposition of step 1.1 is untenable and clause 1 holds.

step 1.1step 1.2L2L3L4

2.2

Clause 2 when $c = 0$ . Choose any $b \in B$ , available by step 1.3; then $∣ f^{- 1} [{b}] ∣ \geq 0 = c$ by [L4].

step 1.3L4

3.1

Clause 2 when $c \neq 0$ . Write $c = σ (q)$ by [L4]. Then $q < c$ , so [L5] gives $∣ B ∣ q < ∣ A ∣$ , that is $∣ A ∣ > q ∣ B ∣$ by commutativity; clause 1, established in step 2.1, therefore produces $b \in B$ with $∣ f^{- 1} [{b}] ∣ > q$ , and $∣ f^{- 1} [{b}] ∣ \geq σ (q) = c$ by [L4].

step 1.3step 2.1L4L5

4.1

Clause 1 is step 2.1, and clause 2 is steps 2.2 and 3.1, whose two cases are exhaustive.

step 2.1step 2.2step 3.1discharge-contradiction∎

Remarks

Where the ceiling earns its keep. Clause 2 is not a separate argument: it is clause 1 applied at the single value $q$ with $σ (q) = c$ , and the only thing that has to be checked is that this $q$ satisfies $∣ A ∣ > q ∣ B ∣$ , which is exactly the minimality of $c$ . That is the whole reason the ceiling was defined by minimality rather than by a division.
The case $c = 0$ is not a degenerate nuisance. It occurs precisely when $A = \emptyset$ , where the conclusion is empty of content but still needs an element of $B$ to be stated about, and that is where $B \neq \emptyset$ is spent in clause 2.
Disjointness of the fibres is free, since a fibre is determined by the value it lies over. This is what lets the sum rule be applied with no hypothesis beyond finiteness, in contrast to a union of arbitrary sets.

Depends on

Used by

Dependency tree · two levels

46 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Pigeonhole principle (Wikipedia) (standard reference, not scraped)
Floor and ceiling functions (Wikipedia) (standard reference, not scraped)
Sylvestre, Pigeonhole Principle (LibreTexts) (standard reference, not scraped)

If ∣A∣>k∣B∣∣A∣>k∣B∣ then every f:A→Bf:A→B has a fibre with more than kk elements, and for nonempty BB some fibre has at least ⌈∣A∣/∣B∣⌉⌈∣A∣/∣B∣⌉ elements