False statementConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck 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.

FALSE: truncating the sieve at a fixed depth of at least two gives the exact size of the union

Statement

FALSE. The statement

for every sieve family $X$ , $I$ , $(A_i)_{i \in I}$ and every $m \ge 2$ , $\iota\Big\lvert\bigcup_{i \in I}A_i\Big\rvert = T_m,$

with $S_j$ and $T_m$ as in Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it.

The claim reads the Bonferroni inequalities as if a truncation at any depth beyond the first were already exact. What is true is that the truncation is an over-estimate at an odd depth and an under-estimate at an even depth, and that it is guaranteed to become exact once the depth reaches $\lvert I\rvert$ , though special families may become exact earlier; the hypothesis $m \ge 2$ does nothing to close that gap when $\lvert I\rvert$ exceeds $m$ .

Facts & Assumptions

Given: The ambient set $X := \{0\}$ , the index set $I := 3 = \{0,1,2\}$ , the family $A_0 := A_1 := A_2 := \{0\}$ , and the truncation depth $m := 2$ .

[L1]

$\lvert\{0\}\rvert = 1$ , $\iota(1) = 1$ and $\iota(3) = 3$ (The cardinality $\lvert A\rvert$ of a finite set, The canonical natural $\iota(n) = n \cdot 1_F$ of a field).

[L2]

$\lvert [I]^{j}\rvert = \binom{3}{j}$ , and $\binom{3}{1} = \binom{3}{2} = 3$ , $\binom{3}{3} = 1$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , A finite family $(A_i)_{i \in I}$ of subsets of a finite set $X$ , the intersections $A_J$ for $J \subseteq I$ , and the convention $A_\varnothing = X$ ).

[L3]

$S_j = \sum_{J \in [I]^{j}}\iota\lvert A_J\rvert$ and $T_m = \sum_{i<m}(-1)^{i}S_{i+1}$ ; a constant real summand gives $\sum_{p \in S}\lambda = \iota(\lvert S\rvert)\lambda$ (Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it, The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form, clause (c), Finite sums and finite products, by recursion, Laws of finite sums and finite products).

[L4]

$(-1)^{0} = 1$ and $(-1)^{1} = -1$ (Integer powers $a^m$ ); $\mathbb{R}$ is an ordered field, so $1 \ne 0$ (Ordered field, Field).

[L5]

Clause 3 of Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it, which says $T_m = \iota\lvert\bigcup_{i \in I}A_i\rvert$ once $m \ge \lvert I\rvert$ .

Refutation

technique · constructive

1.1

The witness. With $X = \{0\}$ and $A_0 = A_1 = A_2 = \{0\}$ , every $A_J$ with $J \subseteq I$ is $\{0\}$ , and the union is $\{0\}$ , so $\iota\lvert\bigcup_{i \in I}A_i\rvert = 1$ by [L1].

givenconstruct

2.1

The first two truncation levels. Each summand $\iota\lvert A_J\rvert$ is $1$ by step 1.1, so $S_1 = \iota\lvert [I]^{1}\rvert\cdot 1 = 3$ and $S_2 = \iota\lvert [I]^{2}\rvert\cdot 1 = 3$ by [L2] and the constant clause of [L3]; likewise $S_3 = 1$ .

L1L2L3

3.1

Therefore $T_2 = (-1)^{0}S_1 + (-1)^{1}S_2 = 3 - 3 = 0$ , while $\iota\lvert\bigcup_{i \in I}A_i\rvert = 1$ . Since $1 \ne 0$ by [L4], the displayed claim fails at this family and at $m = 2$ , which satisfies its hypothesis $m \ge 2$ .

step 1.1step 2.1L3L4

4.1

What is true here instead. Clause 2 of Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it gives $\iota\lvert\bigcup_i A_i\rvert \ge T_2$ , and indeed $1 \ge 0$ ; and $T_3 = 3 - 3 + 1 = 1$ , which is the exact value, in agreement with clause 3 of that theorem at $m = 3 = \lvert I\rvert$ . So the truncation becomes exact one level later than the claim asserts, and the gap at depth $2$ is the whole content of the failure.

step 2.1step 3.1L3L4L5discharge-construct∎

Remarks

The claim is not repaired by raising the fixed depth. For any fixed $m$ the same all-equal family with $I$ taken to have more than $m$ elements refutes it again; clause 3 guarantees exactness once the depth reaches $\lvert I\rvert$ , while other families may already be exact sooner. That is why the true uniform guarantee fixes the depth relative to $\lvert I\rvert$ rather than absolutely.
The direction of the error is not accidental. Depth $2$ is an even truncation, and an even truncation under-estimates, so the truncated value is below the truth rather than above it. A witness at depth $3$ would over-shoot instead.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 86 results over 28 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

Inclusion-exclusion principle (Wikipedia) (standard reference, not scraped)
Boole's inequality (Wikipedia) (standard reference, not scraped)
Indicator Functions and Inclusion-Exclusion (University of South Carolina notes) (standard reference, not scraped)
Principle of Inclusion and Exclusion and Bonferroni Inequalities (Concordia notes) (standard reference, not scraped)