TWO SETS.
Consider a finite set S and two subsets
S1,S2 of S. These two
sets partition S into four atoms, some of which
may be empty. Let Nii,
Nio, Noi,
Noo denote the sizes of these atoms: let us
write
Nii for the number of elements in both
S1 and S2,
Nio for the number of elements in
S1 and outside S2,
Noi for the number of elements outside
S1 and in S2,
Noo for the number of elements outside both
S1 and S2.
i is mnemonic for "in" and o is
mnemonic for "out".) Furthermore, let us write
Nid for the number of elements in
S1,
Ndi for the number of elements in
S2,
Ndd for the total number of elements in
S.
d is mnemonic for "don't care".) By definition, we have
Nid = Nii + Nio Ndi = Nii + Noi Ndd = Nii + Nio + Noi + Noo;it follows that
Noo = Ndd - (Nii + Nio + Noi)
= Ndd - (Nid + Ndi) + Nii.
Identity
Noo = Ndd - (Nid + Ndi) + Niiis a special case of the inclusion-exclusion principle; inequalities
Noo <= Ndd Noo >= Ndd - (Nid + Ndi)a special case of the Boole-Bonferroni inequalities.
THREE SETS.
Consider a finite set S and three subsets
S1,S2,S3 of
S. These three sets partition S into eight
atoms (some of which may be empty). Let
Niii, Niio,
Nioi, Nioo,
Noii, Noio,
Nooi, Nooo
denote the sizes of these atoms: let us write
Niii for the number of elements
in S1, in S2, and in
S3,
Niio for the number of elements
in S1, in S2, and outside
S3,
Nioi for the number of elements
in S1, outside S2, and in
S3,
Nioo for the number of elements
in S1, outside S2, and outside
S3,
Noii for the number of elements
outside S1, in S2, and in
S3,
Noio for the number of elements
outside S1, in S2, and outside
S3,
Nooi for the number of elements
outside S1, outside S2, and in
S3,
Nooo for the number of elements
outside S1, outside S2, and
outside S3.
Niid for the number of elements
in S1 and in S2,
Nidi for the number of elements
in S1 and in S3,
Ndii for the number of elements
in S2 and in S3,
Nidd for the number of elements
in S1,
Ndid for the number of elements
in S2,
Nddi for the number of elements
in S3,
Nddd for the total number of elements
in S.
Niid = Niii + Niio, Nidi = Niii + Nioi, Nidd = Niii + Niio + Nioi + Nioo, Ndii = Niii + Noii, Ndid = Niii + Niio + Noii + Noio, Nddi = Niii + Nioi + Noii + Nooi, Nddd = Niii + Niio + Nioi + Noii + Nioo + Noio + Nooi + Nooo;it follows that
Nooo = Nddd - (Niii + Niio + Nioi + Noii + Nioo + Noio + Nooi)
= Nddd - (Nidd + Ndid + Nddi) + (2Niii + Niio + Nioi + Noii)
= Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii) - Niii.
Identity
Nooo = Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii) - Niiiis a special case of the inclusion-exclusion principle; inequalities
Nooo <= Nddd Nooo >= Nddd - (Nidd + Ndid + Nddi) Nooo <= Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii)are a special case of the Boole-Bonferroni inequalities.
FOUR SETS.
Consider a finite set S and four subsets
S1,S2,S3,S4
of S. In the notation suggested by the preceding two
examples, we have
Noooo = Ndddd
- (Niiii + Niiio + Niioi + Nioii + Noiii +
Niioo + Nioio + Niooi + Noiio + Noioi + Nooii +
Niooo + Noioo + Nooio + Noooi)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (3Niiii + 2Niiio + 2Niioi + 2Nioii + 2Noiii +
Niioo + Nioio + Niooi + Noiio + Noioi + Nooii)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (3Niiii + Niiio + Niioi + Nioii + Noiii)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii) + Niiii.
Identity
Noooo = Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii) + Niiii
is a special case of the inclusion-exclusion principle; inequalities
Noooo <= Ndddd
Noooo >= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
Noooo <= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
Noooo >= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii)
are a special case of the Boole-Bonferroni inequalities.
MANY SETS.
Consider a finite set S and k subsets
S1,S2,...,Sk
of S. With the notation suggested by the preceding
examples, let Tj stand for the sum of
all the terms N**...* whose subscript
**...* consists of j symbols i and
k-j symbols d. The inclusion-exclusion principle
states that
Noo...o = T0 - T1 + T2 - T3 + ... + (-1)kTk;the Boole-Bonferroni inequalities assert that prefix-sums of the right-hand side alternate between upper and lower bounds on
Noo...o:
Noo...o <= T0 Noo...o >= T0 - T1 Noo...o <= T0 - T1 + T2 Noo...o >= T0 - T1 + T2 - T3and so on.