Ivan Shishkin, Rye (1878)

Discussions

Démonstration de la formule du crible à l’aide des fonctions indicatrices

0 messages

Back to problem

Solution

Solution by darktoaster · FR

Question 1 : Quelques propriétés de l’indicatrice

\newline

Propriété i)

\newline
Soit i∈[ ⁣[1,n] ⁣]i \in [\![1,n]\!], montrons que 1Ai=1−1Ai‾\mathbb{1}_{A_{i}} = 1 - \mathbb{1}_{\overline{ A_{i}}}
Soit x∈Ex \in E, montrons 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x)

Si x∈Aix \in A_{i}, alors 1Ai(x)=1\mathbb{1}_{A_{i}} (x) = 1, de plus x∉Ai‾x \not\in \overline{A_{i}}, ainsi 1Ai‾(x)=0\mathbb{1}_{\overline{A_{i}}}(x) = 0
nous avons bien 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x) , en effet 1=1−01 = 1 - 0

Si x∈Aix \in A_{i}, alors 1Ai(x)=0\mathbb{1}_{A_{i}} (x) = 0, de plus x∈Ai‾x \in \overline{A_{i}}, ainsi 1Ai‾(x)=1\mathbb{1}_{\overline{A_{i}}}(x) = 1
nous avons également 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x) , en effet 0=1−10 = 1 - 1
\newline

Propriété ii)

\newline
Soient i,j∈[ ⁣[1,n] ⁣]i,j \in [\![1,n]\!], montrons que 1Ai∩Aj=1Ai⋅1Aj\mathbb{1}_{A_{i} \cap A_{j}} = \mathbb{1}_{ A_{i}} \cdot \mathbb{1}_{A_{j}}
Soit x∈Ex \in E, montrons 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x)

Si x∈Ai∩Ajx \in A_{i}\cap A_{j}, alors 1Ai∩Aj(x)=1\mathbb{1}_{A_{i}\cap A_{j}} (x) = 1, de plus x∈Aix \in A_{i} et x∈Ajx \in A_{j}, ainsi 1Ai(x)=1\mathbb{1}_{A_{i}}(x) = 1 et 1Aj(x)=1\mathbb{1}_{A_{j}}(x) = 1
nous avons bien 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x) , en effet 1=1⋅11 = 1 \cdot 1

Si x∉Ai∩Ajx \not\in A_{i}\cap A_{j}, alors 1Ai∩Aj(x)=0\mathbb{1}_{A_{i}\cap A_{j}} (x) = 0, de plus x∉Aix \not\in A_{i} ou x∉Ajx \not\in A_{j} , ainsi 1Ai(x)=0\mathbb{1}_{A_{i}}(x) = 0 ou 1Aj(x)=0\mathbb{1}_{A_{j}}(x) = 0
nous avons également 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x) via la règle du produit nul

\newline

Propriété iii)

\newline
On généralise la propriété ii) par récurrence et on utilise la propriété i)
\newline

Propriété iv)

\newline
∀i∈[ ⁣[1,n] ⁣],∑x∈E1Ai(x)=∑x∈Ai1=card(Ai)\forall i \in [\![1,n]\!], \sum\limits_{x \in E} \mathbb{1}_{A_{i}}(x) = \sum\limits_{x \in A_{i}} 1 = \mathrm{card}(A_{i})
On enlève les éléments de EE n’étant pas dans AiA_{i} puis on compte 11 par 11 les éléments de AiA_{i}
\newline

Question 2 : Démonstration de la formule du crible

On commence par utiliser les différentes propriétés de l’indicatrice démontrées précédemment et les lois de de Morgan pour récrire notre cardinal :
\newline
∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right| =∑x∈E1⋃i=1nAi(x)= \sum\limits_{x\in E} \mathbb{1}_{\bigcup\limits_{i = 1}^{n} A_{i}}(x) =∑x∈E1−1⋃i=1nAi‾(x)= \sum\limits_{x\in E} 1 - \mathbb{1}_{\overline{\bigcup\limits_{i = 1}^{n} A_{i}}}(x) =∑x∈E1−1⋂i=1nAi‾(x)= \sum\limits_{x\in E} 1 - \mathbb{1}_{\bigcap\limits_{i = 1}^{n} \overline{A_{i}}}(x) =∑x∈E1−∏i=1n1Ai‾(x)= \sum\limits_{x\in E} 1 - \prod\limits_{i = 1}^{n}\mathbb{1}_{ \overline{A_{i}}}(x) =∑x∈E1−∏i=1n(1−1Ai(x))= \sum\limits_{x\in E} 1 - \prod\limits_{i = 1}^{n} ( 1 - \mathbb{1}_{ A_{i}}(x))
\newline
Ensuite, passage délicat, on va développer le produit :
∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|=∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k∏i∈I(−1Ai(x))= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \prod\limits_{i \in I} (-\mathbb{1}_{A_{i}}(x))

  • Lorsque l’on développe, soit on prend 00 indicatrice, soit 11, ..., soit nn, d’où la somme ∑k=0n\sum\limits_{k = 0}^{n}
  • Ensuite, en fixant le nombre d’indicatrices sélectionnées, par exemple k=1k=1, les termes sont −1A1-\mathbb{1}_{A_{1}}, ..., −1An-\mathbb{1}_{A_{n}} . Pour k=2k=2 : (−1A1)⋅(−1A2)(-\mathbb{1}_{A_{1}} ) \cdot (-\mathbb{1}_{A_{2}}) , ..., (−1A1)⋅(−1An)(-\mathbb{1}_{A_{1}} ) \cdot (-\mathbb{1}_{A_{n}}) ,..., d’où ∑I⊂[[1,n]]∣I∣=k∏i∈I\sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \prod\limits_{i \in I}
    \newline
    On peut réaranger l’expression
    ∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|
    =∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k(−1)k∏i∈I1Ai(x)= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } (-1)^{k}\prod\limits_{i \in I} \mathbb{1}_{A_{i}}(x)
    =∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k(−1)k1⋂i∈IAi(x)= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } (-1)^{k} \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    =∑x∈E1+∑k=0n(−1)k+1∑I⊂[[1,n]]∣I∣=k1⋂i∈IAi(x)= \sum\limits_{x \in E} 1 + \sum\limits_{k=0}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    =∑x∈E∑k=1n(−1)k+1∑I⊂[[1,n]]∣I∣=k1⋂i∈IAi(x)= \sum\limits_{x \in E} \sum\limits_{k=1}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    \newline
    On conclut :
    ∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|=∑k=1n(−1)k+1∑I⊂[[1,n]]∣I∣=k∣⋂i∈IAi∣= \sum\limits_{k=1}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \left| \bigcap\limits_{i \in I} A_{i}\right|

No messages yet.