[proofplan] We compare the elements counted by $S(A,P,z_1)$ with those counted by $S(A,P,z_2)$. The only elements lost when the cutoff is raised from $z_1$ to $z_2$ are those whose first prime divisor from $P$ in the relevant range lies in $[z_1,z_2)$. We partition this lost set according to that least prime divisor, identify each part with the set counted by $S(A_p,P,p)$, and then take cardinalities. [/proofplan] [step:Express the change in the sifted set as a lost subset] For each real number $z \geq 2$, define the sifted subset \begin{align*} A_z := \{a \in A : \text{no prime } q \in P \text{ with } q < z \text{ divides } a\}. \end{align*} By definition, \begin{align*} S(A,P,z)=\#A_z. \end{align*} Since every prime $q \in P$ with $q < z_1$ also satisfies $q < z_2$, we have $A_{z_2} \subseteq A_{z_1}$. Define the lost set \begin{align*} D := A_{z_1} \setminus A_{z_2}. \end{align*} Because $A$ is finite, all these sets are finite, and therefore \begin{align*} S(A,P,z_1)-S(A,P,z_2)=\#D. \end{align*} [guided] For each cutoff $z \geq 2$, the set $A_z$ consists of exactly those elements of $A$ that survive sieving by primes from $P$ below $z$. Thus $S(A,P,z)=\#A_z$ by the definition of $S$ in the theorem statement. Increasing the cutoff from $z_1$ to $z_2$ can only remove elements, because every prime $q \in P$ satisfying $q<z_1$ also satisfies $q<z_2$. Hence $A_{z_2}\subseteq A_{z_1}$. We define the removed part by \begin{align*} D:=A_{z_1}\setminus A_{z_2}. \end{align*} Since $A$ is finite, the sets $A_{z_1}$, $A_{z_2}$, and $D$ are finite. The inclusion $A_{z_2}\subseteq A_{z_1}$ gives the finite disjoint decomposition $A_{z_1}=A_{z_2}\cup D$, so subtracting cardinalities gives \begin{align*} S(A,P,z_1)-S(A,P,z_2)=\#A_{z_1}-\#A_{z_2}=\#D. \end{align*} [/guided] [/step] [step:Partition the lost set by the least new prime divisor] For each prime $p \in P$ with $z_1 \leq p < z_2$, define \begin{align*} D_p := \{a \in A : p \mid a \text{ and no prime } q \in P \text{ with } q < p \text{ divides } a\}. \end{align*} We claim that \begin{align*} D=\bigcup_{p\in P,\ z_1\le p<z_2} D_p \end{align*} and that this union is disjoint. First let $a \in D$. Then $a \in A_{z_1}$, so no prime $q \in P$ with $q < z_1$ divides $a$. Also $a \notin A_{z_2}$, so at least one prime $r \in P$ with $r < z_2$ divides $a$. Since no such divisor can satisfy $r < z_1$, consider the set \begin{align*} \{r \in P : z_1 \leq r < z_2 \text{ and } r \mid a\}. \end{align*} This set is nonempty by the preceding sentence, and it is finite because the interval $[z_1,z_2)$ contains only finitely many primes. Hence it has a least element; call it $p$. Then $z_1 \leq p < z_2$, $p \in P$, and no prime $q \in P$ with $q < p$ divides $a$: primes $q < z_1$ are excluded by $a \in A_{z_1}$, while primes $z_1 \leq q < p$ are excluded by the minimality of $p$. Hence $a \in D_p$. Conversely, if $a \in D_p$ for some $p \in P$ with $z_1 \leq p < z_2$, then no prime $q \in P$ with $q < z_1$ divides $a$, since every such $q$ satisfies $q < p$. Thus $a \in A_{z_1}$. But $p \mid a$ and $p < z_2$, so $a \notin A_{z_2}$. Hence $a \in D$. The union is disjoint because if $a \in D_p \cap D_r$ with $p<r$, then $p \mid a$ and $p \in P$ with $p<r$, contradicting the defining condition of $D_r$. [guided] The set $D$ records exactly what disappears when the cutoff changes from $z_1$ to $z_2$. Since $D=A_{z_1}\setminus A_{z_2}$, an element $a \in D$ has no prime divisor from $P$ below $z_1$, but it does have at least one prime divisor from $P$ below $z_2$. Therefore any newly detected prime divisor must lie in the interval $[z_1,z_2)$. For each prime $p \in P$ with $z_1 \leq p < z_2$, we define \begin{align*} D_p := \{a \in A : p \mid a \text{ and no prime } q \in P \text{ with } q < p \text{ divides } a\}. \end{align*} This definition says that $p$ is the least prime divisor of $a$ among primes belonging to $P$. Now fix $a \in D$. Since $a \notin A_{z_2}$, there exists at least one prime $r \in P$ with $r<z_2$ and $r \mid a$. Since $a \in A_{z_1}$, no prime $q \in P$ with $q<z_1$ divides $a$. Hence every such prime divisor $r$ must satisfy $z_1 \leq r < z_2$. The set \begin{align*} \{r \in P : z_1 \leq r < z_2 \text{ and } r \mid a\} \end{align*} is nonempty by existence of $r$, and it is finite because the bounded interval $[z_1,z_2)$ contains only finitely many primes. Let $p$ be its least element. Then $p \in P$, $z_1 \leq p < z_2$, and $p \mid a$. If a prime $q \in P$ with $q<p$ divided $a$, then either $q<z_1$, contradicting $a \in A_{z_1}$, or $z_1 \leq q<p$, contradicting the minimality of $p$. Thus $a \in D_p$. Conversely, suppose $a \in D_p$ for some $p \in P$ with $z_1 \leq p < z_2$. The condition defining $D_p$ excludes every prime $q \in P$ with $q<p$. In particular it excludes every prime $q \in P$ with $q<z_1$, because $z_1 \leq p$. Hence $a \in A_{z_1}$. At the same time, $p \mid a$ and $p<z_2$, so $a$ fails the defining condition for $A_{z_2}$. Hence $a \in A_{z_1} \setminus A_{z_2}=D$. Finally, two different primes cannot both be the least such prime divisor. More formally, if $a \in D_p \cap D_r$ and $p<r$, then $p \mid a$ with $p \in P$ and $p<r$, contradicting the condition in the definition of $D_r$ that no prime from $P$ below $r$ divides $a$. Therefore the union of the sets $D_p$ is disjoint. [/guided] [/step] [step:Identify each partition piece with the corresponding sifted set] Fix a prime $p \in P$ with $z_1 \leq p < z_2$. By definition, \begin{align*} S(A_p,P,p)=\#\{a \in A_p : \text{no prime } q \in P \text{ with } q < p \text{ divides } a\}. \end{align*} Since $A_p=\{a \in A : p \mid a\}$, the set on the right is exactly \begin{align*} D_p=\{a \in A : p \mid a \text{ and no prime } q \in P \text{ with } q < p \text{ divides } a\}. \end{align*} Thus \begin{align*} S(A_p,P,p)=\#D_p. \end{align*} [guided] Fix a prime $p \in P$ with $z_1\leq p<z_2$. By the definition of $A_p$, an element belongs to $A_p$ exactly when it is an element of $A$ divisible by $p$: \begin{align*} A_p=\{a\in A:p\mid a\}. \end{align*} By the definition of the sifted counting function $S$, the quantity $S(A_p,P,p)$ counts those elements of $A_p$ that have no prime divisor from $P$ below $p$: \begin{align*} S(A_p,P,p)=\#\{a\in A_p: \text{no prime } q\in P \text{ with } q<p \text{ divides } a\}. \end{align*} Substituting the defining description of $A_p$ into this set gives \begin{align*} \{a\in A_p: \text{no prime } q\in P \text{ with } q<p \text{ divides } a\}=\{a\in A:p\mid a \text{ and no prime } q\in P \text{ with } q<p \text{ divides } a\}=D_p. \end{align*} Therefore $S(A_p,P,p)=\#D_p$. [/guided] [/step] [step:Take cardinalities to obtain the decomposition] From the disjoint partition of $D$ and the identification of each part, \begin{align*} \#D=\sum_{p\in P,\ z_1\le p<z_2}\#D_p=\sum_{p\in P,\ z_1\le p<z_2}S(A_p,P,p). \end{align*} Combining this with \begin{align*} S(A,P,z_1)-S(A,P,z_2)=\#D \end{align*} gives \begin{align*} S(A,P,z_2)=S(A,P,z_1)-\sum_{p\in P,\ z_1\le p<z_2}S(A_p,P,p). \end{align*} This is the Buchstab decomposition. [guided] The previous steps give two facts. First, the lost set $D$ is the disjoint union of the sets $D_p$ over primes $p\in P$ with $z_1\leq p<z_2$. Since all sets involved are finite, cardinality is additive over this disjoint union: \begin{align*} \#D=\sum_{p\in P,\ z_1\le p<z_2}\#D_p. \end{align*} Second, for each such prime $p$, the identification step proved that $\#D_p=S(A_p,P,p)$. Substituting this into the preceding equality gives \begin{align*} \#D=\sum_{p\in P,\ z_1\le p<z_2}S(A_p,P,p). \end{align*} The first step also proved that $S(A,P,z_1)-S(A,P,z_2)=\#D$. Combining the two equalities yields \begin{align*} S(A,P,z_1)-S(A,P,z_2)=\sum_{p\in P,\ z_1\le p<z_2}S(A_p,P,p). \end{align*} Rearranging this finite equality gives \begin{align*} S(A,P,z_2)=S(A,P,z_1)-\sum_{p\in P,\ z_1\le p<z_2}S(A_p,P,p), \end{align*} which is the claimed Buchstab decomposition. [/guided] [/step]