We prove the asymmetric version of the lemma, from which the symmetric version can be derived. By using the principle of mathematical induction we prove that for all A{displaystyle A} in A{displaystyle {mathcal {A}}} and all subsets S{displaystyle S} of A{displaystyle {mathcal {A}}} that do not include A{displaystyle A}, Pr(A∣⋀B∈SB¯)≤x(A){displaystyle Pr left(Amid bigwedge _{Bin S}{overline {B}}right)leq x(A)}. The induction here is applied on the size (cardinality) of the set S{displaystyle S}. For base case S=∅{displaystyle S=emptyset } the statement obviously holds since Pr(Ai)≤x(Ai){displaystyle Pr(A_{i})leq xleft(A_{i}right)}. We need to show that the inequality holds for any subset of A{displaystyle {mathcal {A}}} of a certain cardinality given that it holds for all subsets of a lower cardinality.