TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck 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.

Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it

Statement

Let $X$ , $I$ , $(A_{i})_{i \in I}$ and the intersections $A_{J}$ be a sieve family (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$ ), let $U : = ⋃_{i \in I} A_{i}$ , put $N : = ∣ I ∣$ , and let $ι$ be the canonical natural (The canonical natural $ι (n) = n \cdot 1_{F}$ of a field). For $j \in N$ and $m \in N$ set

$S_{j} : = \sum_{J \in [I]^{j}} ι ∣ A_{J} ∣, T_{m} : = \sum_{i < m} (- 1)^{i} S_{i + 1},$

the first sum being over the finite set of $j$ -element subsets of $I$ and the second the real finite sum of Finite sums and finite products, by recursion. Thus $T_{0} = 0$ , $T_{1} = S_{1}$ and $T_{2} = S_{1} - S_{2}$ . Then, in $R$ :

Odd truncation over-estimates. $ι ∣ U ∣ \leq T_{2 r + 1}$ for every $r \in N$ .
Even truncation under-estimates. $ι ∣ U ∣ \geq T_{2 r}$ for every $r \in N$ .
Both are equalities once the truncation reaches $∣ I ∣$ . $T_{m} = ι ∣ U ∣$ for every $m \geq N$ .

Clause 1 at $r = 0$ is the union bound $ι ∣ U ∣ \leq S_{1}$ , and clause 2 at $r = 0$ is the trivial $ι ∣ U ∣ \geq T_{0} = 0$ ; the first substantial even case is $r = 1$ , where $T_{2} = S_{1} - S_{2}$ .

Facts & Assumptions

Given: A sieve family $X$ , $I$ , $(A_{i})_{i \in I}$ with intersections $A_{J}$ , union $U$ , traces $T (x)$ and $t (x) : = ∣ T (x) ∣$ (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$ ); $N : = ∣ I ∣$ ; the quantities $S_{j}$ and $T_{m}$ of the Statement; and, for $V \subseteq X$ , the indicator $1_{V} : X \to R$ with value $1$ on $V$ and $0$ off it.

[L1]

Indicator sums: $\sum_{p \in S} 1_{W} (p) = ι ∣ W ∣$ for a finite $S$ and $W \subseteq S$ . Split $S$ into the disjoint blocks $W$ and $S ∖ W$ (clause 3 of 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) and apply the constant clause (c) of The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form.

[L2]

Sieve facts (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$ ): $P (I)$ , $[I]^{j}$ , $A_{J}$ , $U$ and $T (x)$ are finite ( $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ , A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , The cardinality $∣ A ∣$ of a finite set); for nonempty $J$ , $x \in A_{J}$ if and only if $J \subseteq T (x)$ ; $x \in U$ if and only if $t (x) \geq 1$ ; $∣ [S]^{j} ∣ = (\binom{∣ S ∣}{j})$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ); and every $J \subseteq I$ satisfies $∣ J ∣ \leq N$ , by clause 2 of A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , so $[I]^{j} = \emptyset$ whenever $j > N$ .

[L3]

Splitting a sum along a partition of its index set (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 3); and, for sums over a finite index set, the bridge $\sum_{i \in n} u_{i} = \sum_{i < n} u_{i}$ , the empty index set and the constant summand (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, clauses (a) and (c)).

[L4]

Interchange of a double sum over two finite index sets ( $\sum_{i \in S} \sum_{j \in T} a_{i j} = \sum_{(i, j) \in S \times T} a_{i j} = \sum_{j \in T} \sum_{i \in S} a_{i j}$ for finite index sets $S$ and $T$ ).

[L5]

Real finite-sum laws, read over a finite index set through an enumeration (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form): additivity, scaling, splitting at an index and monotonicity (Laws of finite sums and finite products, clauses 1 to 4, Finite sums and finite products, by recursion).

[L6]

The partial alternating row sum: $\sum_{j < M + 1} (- 1)^{j} ι (\binom{t}{j}) = (- 1)^{M} ι (\binom{t - 1}{M})$ for every $t \geq 1$ and every $M$ ( $\sum_{j < m + 1} (- 1)^{j} ι (\binom{t}{j}) = (- 1)^{m} ι (\binom{t - 1}{m})$ for every $t \geq 1$ and every $m$ ).

[L7]

Powers of $- 1$ : $(- 1)^{0} = 1$ and $(- 1)^{p + 1} = - (- 1)^{p}$ (Integer powers $a^{m}$ ); and $(- 1)^{2 r} = 1$ , $(- 1)^{2 r + 1} = - 1$ . For the last two, $(- 1)^{2 r} = ((- 1)^{2})^{r} = 1^{r}$ by clause 1 of Laws of integer exponents, and $1^{r} = ι (1)^{r} = ι (1^{r}) = ι (1) = 1$ by clauses (b) and (d) of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ with The canonical natural $ι (n) = n \cdot 1_{F}$ of a field; then $(- 1)^{2 r + 1} = (- 1)^{2 r} \cdot (- 1) = - 1$ .

[L8]

Inclusion and exclusion, clause 1 (Inclusion and exclusion: $ι ∣ ⋃_{i \in I} A_{i} ∣ = \sum_{\emptyset \neq J \subseteq I} (- 1)^{∣ J ∣ + 1} ι ∣ A_{J} ∣$ , together with the complementary form counting the elements in none of the $A_{i}$ ).

[L9]

Boundary values of a binomial coefficient: $(\binom{n}{0}) = 1$ for every $n$ , while $(\binom{n}{j}) = 0$ whenever $j > n$ , so in particular $(\binom{0}{j}) = 0$ for $j \geq 1$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ); $ι (0) = 0$ and $ι (p) \geq 0$ for every natural $p$ , $ι$ being strictly increasing with $ι (0) = 0$ (Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ , clause 7).

[L10]

$R$ is an ordered field (Ordered field, Field).

Proof

technique · direct

1.1

Each $S_{j}$ with $j \geq 1$ counted pointwise. By [L1], $ι ∣ A_{J} ∣ = \sum_{x \in X} 1_{A_{J}} (x)$ for every $J \subseteq I$ ; interchanging the resulting double sum by [L4] gives $S_{j} = \sum_{x \in X} (\sum_{J \in [I]^{j}} 1_{A_{J}} (x))$ . For $j \geq 1$ every $J \in [I]^{j}$ is nonempty, so by [L2] the inner sum is $ι$ of the number of $J \in [I]^{j}$ with $J \subseteq T (x)$ , that is $ι ∣ [T (x)]^{j} ∣ = ι (\binom{t (x)}{j})$ . Hence $S_{j} = \sum_{x \in X} ι (\binom{t (x)}{j})$ for every $j \geq 1$ .

L1L2L4

1.2

The pointwise truncation. For $x \in X$ and $m \in N$ put $c_{m} (x) : = \sum_{i < m} (- 1)^{i} ι (\binom{t (x)}{i + 1})$ .

construct

1.3

A closed form for $c_{m} (x)$ . Splitting $\sum_{j < m + 1} (- 1)^{j} ι (\binom{t (x)}{j})$ at the index $1$ by [L5] gives $(- 1)^{0} ι (\binom{t (x)}{0}) + \sum_{i < m} (- 1)^{1 + i} ι (\binom{t (x)}{1 + i})$ , which by [L7] and scaling is $1 - c_{m} (x)$ ; hence $c_{m} (x) = 1 - \sum_{j < m + 1} (- 1)^{j} ι (\binom{t (x)}{j})$ . So $c_{m} (x) = 1 - (- 1)^{m} ι (\binom{t (x) - 1}{m})$ when $t (x) \geq 1$ , by [L6]. When $t (x) = 0$ every term of $c_{m} (x)$ is $ι (\binom{0}{i + 1}) = 0$ by [L9], so $c_{m} (x) = 0$ .

L5L6L7L9

2.1

$T_{m}$ counted pointwise. Scaling step 1.1 by $(- 1)^{i}$ gives $(- 1)^{i} S_{i + 1} = \sum_{x \in X} (- 1)^{i} ι (\binom{t (x)}{i + 1})$ for every $i$ ; summing over $i \in m$ , using $\sum_{i \in m} = \sum_{i < m}$ from [L3] and interchanging by [L4], gives $T_{m} = \sum_{x \in X} c_{m} (x)$ for every $m \in N$ .

step 1.1step 1.2L3L4L5

2.2

The pointwise comparison. Let $x \in X$ and $r \in N$ . If $x \notin U$ then $t (x) = 0$ by [L2], so $c_{2 r} (x) = c_{2 r + 1} (x) = 0 = 1_{U} (x)$ by step 1.3. If $x \in U$ then $t (x) \geq 1$ , and step 1.3 with [L7] gives $c_{2 r + 1} (x) = 1 + ι (\binom{t (x) - 1}{2 r + 1}) \geq 1 = 1_{U} (x)$ and $c_{2 r} (x) = 1 - ι (\binom{t (x) - 1}{2 r}) \leq 1 = 1_{U} (x)$ , since $ι$ of a natural number is at least $0$ by [L9]. So $c_{2 r + 1} (x) \geq 1_{U} (x) \geq c_{2 r} (x)$ for every $x \in X$ .

step 1.3L2L7L9L10

3.1

Clauses 1 and 2. Monotonicity of a finite sum over the index set $X$ , applied to step 2.2, gives $\sum_{x \in X} c_{2 r} (x) \leq \sum_{x \in X} 1_{U} (x) \leq \sum_{x \in X} c_{2 r + 1} (x)$ ; the middle term is $ι ∣ U ∣$ by [L1] and the outer two are $T_{2 r}$ and $T_{2 r + 1}$ by step 2.1.

step 2.1step 2.2L1L5

4.1

Clause 3. The sets $[I]^{i + 1}$ for $i \in N$ are pairwise disjoint with union $P (I) ∖ {\emptyset}$ , since a nonempty $J \subseteq I$ has exactly one cardinality and it satisfies $1 \leq ∣ J ∣ \leq N$ by [L2]; splitting the sieve sum along this partition, and using $(- 1)^{∣ J ∣ + 1} = (- 1)^{i + 2} = (- 1)^{i}$ for $J \in [I]^{i + 1}$ from [L7], gives $\sum_{J \in P (I) ∖ {\emptyset}} (- 1)^{∣ J ∣ + 1} ι ∣ A_{J} ∣ = \sum_{i < N} (- 1)^{i} S_{i + 1} = T_{N}$ , which equals $ι ∣ U ∣$ by [L8]. For $m \geq N$ , splitting $T_{m}$ at the index $N$ by [L5] and noting that $i \geq N$ forces $i + 1 > N$ , hence $[I]^{i + 1} = \emptyset$ and $S_{i + 1} = 0$ by [L2], [L3] and [L9], gives $T_{m} = T_{N} = ι ∣ U ∣$ ; with step 3.1 this completes all three clauses.

step 3.1L2L3L5L7L8L9∎

Remarks

Why the parity is written as $2 r$ and $2 r + 1$ . Nothing among this page's declared prerequisites defines the words even and odd, and the statement needs only the two families of truncation depths, which the two displayed forms name directly. The sign facts $(- 1)^{2 r} = 1$ and $(- 1)^{2 r + 1} = - 1$ are then the whole use of parity in the proof.
Where the error term comes from. Step 1.3 says that a truncation at depth $m$ misses the indicator of $U$ at a point of trace size $t \geq 1$ by exactly $(- 1)^{m} ι (\binom{t - 1}{m})$ , a single binomial coefficient. The sign of that term is what makes the inequality go one way for one parity and the other way for the other, and its nonnegativity is what makes the inequality hold at all.
A point outside the union contributes nothing at any depth, which is why no hypothesis relating $X$ to $U$ appears. The ambient set may be much larger than the union without affecting either side.

Depends on

Used by

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

Dependency tree · two levels

65 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)
R. Stanley, Enumerative Combinatorics, Vol. 1, Ch. 2 (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)