CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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 \ne \varnothing$ , 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 $\lvert X\rvert \ne 0$ , the real number

$\mu \;:=\; \frac{\iota(\lvert R\rvert)}{\iota(\lvert X\rvert)}$

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

$\iota(\lvert R_{x_{+}}\rvert) \ \ge\ \mu \qquad\text{and}\qquad \iota(\lvert R_{x_{-}}\rvert) \ \le\ \mu .$

The two elements need not be distinct, and neither inequality need be an equality: $\mu$ 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 \ne \varnothing$ and $Y$ , a relation $R \subseteq X \times Y$ with row fibres $R_x$ , and a fixed enumeration $\varphi : \lvert X\rvert \to X$ of $X$ , which exists because $X$ is finite (The cardinality $\lvert A\rvert$ of a finite set).

[L1]

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

[L2]

The bridge over a finite index set: for a finite $S$ and $c : S \to \mathbb{N}$ , $\iota\big(\sum_{i \in S} c_i\big) = \sum_{i \in S}\iota(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 $\psi : \lvert S\rvert \to S$ , and $\iota\big(\sum_{k<n} c_{\psi(k)}\big) = \sum_{k<n}\iota(c_{\psi(k)})$ is clause 6 of Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ .

[L3]

A constant real summand: $\sum_{i \in S}\lambda = \iota(\lvert S\rvert)\,\lambda$ for $\lambda \in \mathbb{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 \mathbb{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 \ge 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_{\psi(k)}$ through an enumeration $\psi$ 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, $\psi$ is onto $S$ , so every value of $u$ is some $u_{\psi(k)}$ .

[L5]

$\iota$ is strictly increasing with $\iota(0) = 0$ , so $n \ge 1$ gives $\iota(n) > 0$ (Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ , clause 7, The canonical natural $\iota(n) = n \cdot 1_F$ of a field).

[L6]

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

[L7]

$\mathbb{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 \ne \varnothing$ , [L6] gives $\lvert X\rvert \ne 0$ , hence $\lvert X\rvert \ge 1$ and $\iota(\lvert X\rvert) > 0$ by [L5]; in particular $\iota(\lvert X\rvert) \ne 0$ , so $\mu = \iota(\lvert R\rvert)/\iota(\lvert X\rvert)$ names a single real number and $\iota(\lvert X\rvert)\,\mu = \iota(\lvert R\rvert)$ .

givenL5L6L7

1.2

Applying [L2] to the list $x \mapsto \lvert R_x\rvert$ and then [L1] gives $\sum_{x \in X}\iota(\lvert R_x\rvert) = \iota\big(\sum_{x \in X}\lvert R_x\rvert\big) = \iota(\lvert R\rvert)$ .

L1L2

1.3

A positive list over a nonempty finite index set has nonzero sum: if $w : X \to \mathbb{R}$ has $w_x > 0$ for every $x \in X$ and $\sum_{x \in X}w_x = 0$ , then $w_x \ge 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 $\mu$ , $\sum_{x \in X}\mu = \iota(\lvert X\rvert)\,\mu = \iota(\lvert R\rvert)$ , the second equality by step 1.1.

step 1.1L3

3.1

Suppose there were no $x_{+}$ with $\iota(\lvert R_{x_{+}}\rvert) \ge \mu$ . Since the order of $\mathbb{R}$ is total, $\iota(\lvert R_x\rvert) < \mu$ for every $x \in X$ , so $w_x := \mu - \iota(\lvert R_x\rvert)$ 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}\iota(\lvert R_x\rvert) = \sum_{x \in X}\mu$ , that is $\sum_{x \in X}w_x = \iota(\lvert R\rvert) - \iota(\lvert R\rvert) = 0$ , contradicting step 1.3. So some $x_{+} \in X$ has $\iota(\lvert R_{x_{+}}\rvert) \ge \mu$ .

step 1.2step 1.3step 2.1L4L7

3.2

Suppose there were no $x_{-}$ with $\iota(\lvert R_{x_{-}}\rvert) \le \mu$ . Then $\iota(\lvert R_x\rvert) > \mu$ for every $x \in X$ , so $w_x := \iota(\lvert R_x\rvert) - \mu$ is positive for every $x$ ; the same computation gives $\sum_{x \in X}w_x = \iota(\lvert R\rvert) - \iota(\lvert R\rvert) = 0$ , again contradicting step 1.3. So some $x_{-} \in X$ has $\iota(\lvert R_{x_{-}}\rvert) \le \mu$ .

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 \ne \varnothing$ is a hypothesis and not decoration. It is used twice: to make $\iota(\lvert X\rvert)$ invertible, so that $\mu$ exists at all, and to produce the element at which the vanishing test is contradicted. With $X = \varnothing$ there is no fibre to exhibit and no quotient to compare it to.
The average lives in $\mathbb{R}$ and the fibre sizes live in $\mathbb{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 $\mathbb{R}$ by $\iota$ . This is the reason the statement is written with $\iota$ throughout rather than as $\lvert R_x\rvert \ge \lvert R\rvert/\lvert X\rvert$ , 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 $\mu$ exists, and it is exhibited on the companion page.

Depends on

Used by

A relation whose row fibres all differ from the average size, so the averaging principle gives a bound that no fibre meets exactly Counterexample

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 67 results over 21 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click 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 XXX is nonempty, some row fibre is at least the average size and some row fibre is at most the average size