Editing Sieve theory (section)

=== The inclusion–exclusion principle ===
For <math>\mathcal{P}</math> define
:<math>A_{\operatorname{sift}}:=\{a\in A|(a,p_1\cdots p_k)=1\}, \quad p_1,\dots,p_k\in\mathcal{P}</math>
and for each prime <math>p\in \mathcal{P}</math> denote the subset <math>E_p\subseteq A</math> of multiples <math>E_p:=\{pn:n\in\mathbb{N}\}</math> and let <math>|E_p|</math> be the cardinality.

We now introduce a way to calculate the cardinality of <math>A_{\operatorname{sift}}</math>. For this the sifting range <math>\mathcal{P}</math> will be a concrete example of primes of the form <math>\mathcal{P}:=\{2,3,5,7,11,13\dots\}</math>.

If one wants to calculate the cardinality of <math>A_{\operatorname{sift}}</math>, one can apply the [[inclusion–exclusion principle]]. This algorithm works like this: first one removes from the cardinality of <math>|A|</math> the cardinality <math>|E_2|</math> and <math>|E_3|</math>. Now since one has removed the numbers that are divisible by <math>2</math> and <math>3</math> twice, one has to add the cardinality <math>|E_6|</math>. In the next step one removes <math>|E_5|</math> and adds <math>|E_{10}|</math> and <math>|E_{15}|</math> again. Additionally one has now to remove <math>|E_{30}|</math>, i.e. the cardinality of all numbers divisible by <math>2,3</math> and <math>5</math>. This leads to the inclusion–exclusion principle
:<math>|A_{\operatorname{sift}}|=|A|-|E_2|-|E_3|+|E_6|-|E_5|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots</math>

Notice that one can write this as
:<math>|A_{\operatorname{sift}}|=\sum\limits_{d|P} \mu(d)| E_d|</math>
where <math>\mu</math> is the [[Möbius function]] and <math>P:=\prod\limits_{p\in\mathcal{P}} p</math> the product of all primes in <math>\mathcal{P}</math> and <math>E_1:=A</math>.