How to prove Boole's Inequality by mathematical induction?P[Asub1 U Asub2 U ... U Asubn] is less than or equal to P[Asub1] + P[Asub2] + ... + P[Asubn]

1 Answer | Add Yours

sciencesolve's profile pic

sciencesolve | Teacher | (Level 3) Educator Emeritus

Posted on

Boole's inequality is known as Bonferroni inequality or inclusion-exclusion principle.

Let's take two subsets `A_1`  and `A_2` .

`|A_1UA_2| = |A_1| + |A_2| - |A_1nn A_2|`

`` `|A_1UA_2| ` denotes the cardinal of reunion of subsets `A_1`  and `A_2` .

|A_1`` A_2| denotes the cardinal of intersection of subsets `A_1`  and `A_2` .

`|A_1|`  denotes the cardinal of subset `A_1`

`` `|A_2| ` denotes the cardinal of subset `A_2`

The generalization of  Boole's inequality for n subsets:

 

Check this inequality for 3 subsets: `A_1={1,3,4}, A_2 = {3,4,6,7,8}; A_3 = {3;7;8}.`

`A_1UA_2UA_3 = {1,3,4,6,7,8} =gt |A_1UA_2UA_3| = 6`

`|A_1| = 3`

`` `|A_2| = 5`

`` `A_1 nn A_2 = {3,4} =gt |A_1 nn A_2| = 2`

`A_1 nn A_3 = {3} =gt |A_1 nn A_3| = 1`

`A_2 nn A_3 = {3,7,8} =gt |A_2 nn A_3| = 3`

`A_1 nn A_2 nn A_3 = {3} =gt |A_1 nn A_2 nn A_3| = 1`

`` Apply Boole's inequality for n = 3:

6 = (3+5+3) - (2+1+3) + 1

6 = 11 - 6+1

6 = 6

Boole's inequality is verified for 3 subsets, therefore, it can be generalized for n subsets.

We’ve answered 318,914 questions. We can answer yours, too.

Ask a question