False statementConstruction: AI-adaptedVerification: 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.

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 \geq 2$ , $ι ∣ ⋃_{i \in I} A_{i} ∣ = 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 $∣ I ∣$ , though special families may become exact earlier; the hypothesis $m \geq 2$ does nothing to close that gap when $∣ I ∣$ 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]

$∣ {0} ∣ = 1$ , $ι (1) = 1$ and $ι (3) = 3$ (The cardinality $∣ A ∣$ of a finite set, The canonical natural $ι (n) = n \cdot 1_{F}$ of a field).

[L2]

$∣ [I]^{j} ∣ = (\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}) : = ∣ [n]^{k} ∣$ , 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_{\emptyset} = X$ ).

[L3]

$S_{j} = \sum_{J \in [I]^{j}} ι ∣ A_{J} ∣$ and $T_{m} = \sum_{i < m} (- 1)^{i} S_{i + 1}$ ; a constant real summand gives $\sum_{p \in S} λ = ι (∣ S ∣) λ$ (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}$ ); $R$ is an ordered field, so $1 \neq 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} = ι ∣ ⋃_{i \in I} A_{i} ∣$ once $m \geq ∣ I ∣$ .

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 $ι ∣ ⋃_{i \in I} A_{i} ∣ = 1$ by [L1].

givenconstruct

2.1

The first two truncation levels. Each summand $ι ∣ A_{J} ∣$ is $1$ by step 1.1, so $S_{1} = ι ∣ [I]^{1} ∣ \cdot 1 = 3$ and $S_{2} = ι ∣ [I]^{2} ∣ \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 $ι ∣ ⋃_{i \in I} A_{i} ∣ = 1$ . Since $1 \neq 0$ by [L4], the displayed claim fails at this family and at $m = 2$ , which satisfies its hypothesis $m \geq 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 $ι ∣ ⋃_{i} A_{i} ∣ \geq T_{2}$ , and indeed $1 \geq 0$ ; and $T_{3} = 3 - 3 + 1 = 1$ , which is the exact value, in agreement with clause 3 of that theorem at $m = 3 = ∣ I ∣$ . 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 $∣ I ∣$ , while other families may already be exact sooner. That is why the true uniform guarantee fixes the depth relative to $∣ I ∣$ 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 · 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

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)