ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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.

Distributing a finite set over a finite set of boxes, with the ceiling bound computed and attained

Example

Take $A : = 17$ and $B : = 5$ , so $∣ A ∣ = 17$ and $∣ B ∣ = 5$ .

The ceiling. $⌈ 17 / 5 ⌉ = 4$ : the least $q$ with $17 \leq 5 q$ is $4$ , since $5 \cdot 3 = 15 < 17$ while $5 \cdot 4 = 20 \geq 17$ ( $⌈ m / n ⌉$ for naturals $m$ and $n \geq 1$ : the least $q \in N$ with $m \leq n q$ ). So 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 says that every $f : A \to B$ has a fibre with at least $4$ elements.

The bound is attained. Partition $A$ into the blocks

$P_{0} : = {0, 1, 2, 3}, P_{1} : = {4, 5, 6, 7}, P_{2} : = {8, 9, 10}, P_{3} : = {11, 12, 13}, P_{4} : = {14, 15, 16},$

and let $f : A \to B$ send each $i$ to the unique $b$ with $i \in P_{b}$ . The fibre sizes are $4, 4, 3, 3, 3$ , summing to $17$ , and the largest of them is $4$ . So no $f : A \to B$ has all its fibres smaller than $4$ , and some $f$ has none larger than $4$ : the ceiling bound is exactly right for this pair of sizes and cannot be raised to $5$ .

The counting form behind it. $17 > 3 \cdot 5 = 15$ , so clause 1 of 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 already gives a fibre with more than $3$ elements, that is with at least $4$ ; and $17 > 4 \cdot 5 = 20$ is false, so clause 1 gives nothing at $k = 4$ , which matches the witness above.

Facts & Assumptions

Given: $A = 17$ , $B = 5$ , the blocks $P_{0}, \dots, P_{4}$ above, and the function $f : A \to B$ they define.

[L1]

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

[L2]

If $f : A \to B$ maps finite sets and $k \in N$ , then (i) $∣ A ∣ > k ∣ B ∣$ implies some fibre has more than $k$ elements, and (ii), when $B \neq \emptyset$ , some fibre has at least $⌈ ∣ A ∣ / ∣ B ∣ ⌉$ elements (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, Injection, surjection, bijection).

[L3]

A listed set with distinct entries has as many elements as entries (The cardinality $∣ A ∣$ of a finite set, clauses (a) and (c), Injection, surjection, bijection); and $∣ 17 ∣ = 17$ , $∣ 5 ∣ = 5$ .

[L4]

The sum rule for a finite partition and the fibres of a function: $∣ A ∣ = \sum_{b \in B} ∣ f^{- 1} [{b}] ∣$ (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, The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L5]

Arithmetic and order of $N$ : $5 \cdot 3 = 15$ , $5 \cdot 4 = 20$ , $15 < 17 \leq 20$ , and exactly one of $p < q$ , $p = q$ , $q < p$ holds (Multiplication of natural numbers, Order on the natural numbers, Trichotomy of the order on $N$ ).

Verification

technique · direct

1.1

The blocks are pairwise disjoint with union $A$ , each entry of $A = 17$ appearing in exactly one of them, and their cardinalities are $4$ , $4$ , $3$ , $3$ , $3$ by [L3]. So $f$ is a well-defined function $A \to B$ and its fibres are exactly the blocks: $f^{- 1} [{b}] = P_{b}$ .

givenL3construct

1.2

The ceiling is $4$ . By [L5], $5 \cdot 3 = 15 < 17$ , and likewise $5 \cdot 0 = 0$ , $5 \cdot 1 = 5$ and $5 \cdot 2 = 10$ , all of them less than $17$ , so no $q < 4$ satisfies $17 \leq 5 q$ ; and $5 \cdot 4 = 20 \geq 17$ , so $4$ does. Hence $⌈ 17 / 5 ⌉ = 4$ by [L1].

L1L5

2.1

Every $f : A \to B$ has a fibre with at least $4$ elements, by clause 2 of [L2] with $B \neq \emptyset$ and the value computed in step 1.2; equivalently, by clause 1 of [L2] with $k = 3$ , since $17 > 3 \cdot 5 = 15$ .

step 1.2L2L5

2.2

The witness of step 1.1 has no fibre with more than $4$ elements, its fibre sizes being $4, 4, 3, 3, 3$ ; and these sum to $17 = ∣ A ∣$ , in agreement with [L4].

step 1.1L3L4

3.1

So the ceiling bound of step 1.2 is attained and cannot be improved for this pair of sizes: every function has a fibre of size at least $4$ , and some function has every fibre of size at most $4$ .

step 2.1step 2.2∎

Remarks

Why the counting form stops at $k = 3$ . Clause 1 needs $∣ A ∣ > k ∣ B ∣$ , and $17 > 20$ is false, so it says nothing at $k = 4$ . That is exactly right: a fibre with more than $4$ elements is not forced, as the witness shows. The ceiling form is the counting form used at the largest $k$ for which the hypothesis still holds.
The unequal block sizes are unavoidable. A function with all fibres of size $3$ would give $∣ A ∣ = 15$ , and one with all fibres of size $4$ would give $20$ ; since $17$ lies strictly between, the fibre sizes of any $f$ cannot all be equal.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

42 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)