CorollaryStatement: AI-adaptedProof: AI-generatedprecheck 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 $X$ is nonempty, some row fibre is at least the average size and some row fibre is at most the average size

Statement

Let $X$ and $Y$ be finite sets with $X \neq \emptyset$ , let $R \subseteq X \times Y$ , and let $R_{x}$ be its row fibres (A relation $R \subseteq X \times Y$ between finite sets, its row fibres $R_{x}$ and its column fibres $R^{y}$ ). Since $∣ X ∣ \neq 0$ , the real number

$μ : = \frac{ι (∣ R ∣)}{ι (∣ X ∣)}$

is defined, where $ι : N \to R$ is the canonical natural (The canonical natural $ι (n) = n \cdot 1_{F}$ of a field). Then there are $x_{+}, x_{-} \in X$ with

$ι (∣ R_{x_{+}} ∣) \geq μ and ι (∣ R_{x_{-}} ∣) \leq μ .$

The two elements need not be distinct, and neither inequality need be an equality: $μ$ is a real number and a fibre size is a natural number, so no fibre need meet the average exactly.

Facts & Assumptions

Given: Finite sets $X \neq \emptyset$ and $Y$ , a relation $R \subseteq X \times Y$ with row fibres $R_{x}$ , and a fixed enumeration $φ : ∣ X ∣ \to X$ of $X$ , which exists because $X$ is finite (The cardinality $∣ A ∣$ of a finite set).

[L1]

Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣$ in $N$ (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

[L2]

The bridge over a finite index set: for a finite $S$ and $c : S \to N$ , $ι (\sum_{i \in S} c_{i}) = \sum_{i \in S} ι (c_{i})$ . This is not a clause of The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form and is derived here: both sides are computed through one and the same enumeration $ψ : ∣ S ∣ \to S$ , and $ι (\sum_{k < n} c_{ψ (k)}) = \sum_{k < n} ι (c_{ψ (k)})$ is clause 6 of Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ .

[L3]

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

[L4]

Additivity and the vanishing test over a finite index set: for $u, v : S \to R$ one has $\sum_{i \in S} (u_{i} + v_{i}) = \sum_{i \in S} u_{i} + \sum_{i \in S} v_{i}$ ; and if $u_{i} \geq 0$ for every $i \in S$ and $\sum_{i \in S} u_{i} = 0$ , then $u_{i} = 0$ for every $i \in S$ . Both are clauses 1 and 4 of Laws of finite sums and finite products applied to the list $k \mapsto u_{ψ (k)}$ through an enumeration $ψ$ of $S$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, Finite sums and finite products, by recursion); for the second, $ψ$ is onto $S$ , so every value of $u$ is some $u_{ψ (k)}$ .

[L5]

$ι$ is strictly increasing with $ι (0) = 0$ , so $n \geq 1$ gives $ι (n) > 0$ (Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ , clause 7, The canonical natural $ι (n) = n \cdot 1_{F}$ of a field).

[L6]

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

[L7]

$R$ is an ordered field: its order is total, a nonzero element has a multiplicative inverse, and $a < b$ is equivalent to $b - a > 0$ (Ordered field, Field).

Proof

technique · contradiction

1.1

Since $X \neq \emptyset$ , [L6] gives $∣ X ∣ \neq 0$ , hence $∣ X ∣ \geq 1$ and $ι (∣ X ∣) > 0$ by [L5]; in particular $ι (∣ X ∣) \neq 0$ , so $μ = ι (∣ R ∣) / ι (∣ X ∣)$ names a single real number and $ι (∣ X ∣) μ = ι (∣ R ∣)$ .

givenL5L6L7

1.2

Applying [L2] to the list $x \mapsto ∣ R_{x} ∣$ and then [L1] gives $\sum_{x \in X} ι (∣ R_{x} ∣) = ι (\sum_{x \in X} ∣ R_{x} ∣) = ι (∣ R ∣)$ .

L1L2

1.3

A positive list over a nonempty finite index set has nonzero sum: if $w : X \to R$ has $w_{x} > 0$ for every $x \in X$ and $\sum_{x \in X} w_{x} = 0$ , then $w_{x} \geq 0$ for every $x$ , so [L4] forces $w_{x} = 0$ for every $x \in X$ ; as $X$ has an element, its value is then both $0$ and positive, which is impossible.

assume-contraL4L7

2.1

By [L3] with the constant $μ$ , $\sum_{x \in X} μ = ι (∣ X ∣) μ = ι (∣ R ∣)$ , the second equality by step 1.1.

step 1.1L3

3.1

Suppose there were no $x_{+}$ with $ι (∣ R_{x_{+}} ∣) \geq μ$ . Since the order of $R$ is total, $ι (∣ R_{x} ∣) < μ$ for every $x \in X$ , so $w_{x} : = μ - ι (∣ R_{x} ∣)$ is positive for every $x$ ; and by additivity, step 1.2 and step 2.1, $\sum_{x \in X} w_{x} + \sum_{x \in X} ι (∣ R_{x} ∣) = \sum_{x \in X} μ$ , that is $\sum_{x \in X} w_{x} = ι (∣ R ∣) - ι (∣ R ∣) = 0$ , contradicting step 1.3. So some $x_{+} \in X$ has $ι (∣ R_{x_{+}} ∣) \geq μ$ .

step 1.2step 1.3step 2.1L4L7

3.2

Suppose there were no $x_{-}$ with $ι (∣ R_{x_{-}} ∣) \leq μ$ . Then $ι (∣ R_{x} ∣) > μ$ for every $x \in X$ , so $w_{x} : = ι (∣ R_{x} ∣) - μ$ is positive for every $x$ ; the same computation gives $\sum_{x \in X} w_{x} = ι (∣ R ∣) - ι (∣ R ∣) = 0$ , again contradicting step 1.3. So some $x_{-} \in X$ has $ι (∣ R_{x_{-}} ∣) \leq μ$ .

step 1.2step 1.3step 2.1L4L7

4.1

Steps 3.1 and 3.2 are the two assertions of the statement.

step 3.1step 3.2discharge-contradiction∎

Remarks

Why $X \neq \emptyset$ is a hypothesis and not decoration. It is used twice: to make $ι (∣ X ∣)$ invertible, so that $μ$ exists at all, and to produce the element at which the vanishing test is contradicted. With $X = \emptyset$ there is no fibre to exhibit and no quotient to compare it to.
The average lives in $R$ and the fibre sizes live in $N$ . A quotient of two natural numbers is not in general a natural number, so the comparison has to be made after both sides are carried into $R$ by $ι$ . This is the reason the statement is written with $ι$ throughout rather than as $∣ R_{x} ∣ \geq ∣ R ∣ / ∣ X ∣$ , which is not an inequality between elements of one ordered set.
Nothing is claimed about attainment. The proof produces an $x_{+}$ and an $x_{-}$ and no more; a relation whose fibre sizes all differ from $μ$ exists, and it is exhibited on the companion page.

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

Double counting (proof technique) (Wikipedia) (standard reference, not scraped)
Pigeonhole principle (Wikipedia) (standard reference, not scraped)
Mathematics for Computer Science (MIT OpenCourseWare) (standard reference, not scraped)

If XX is nonempty, some row fibre is at least the average size and some row fibre is at most the average size