TWO SETS.
Consider a finite set S
and two subsets
S_{1},S_{2}
of S
. These two
sets partition S
into four atoms, some of which
may be empty. Let N_{ii}
,
N_{io}
, N_{oi}
,
N_{oo}
denote the sizes of these atoms: let us
write
N_{ii}
for the number of elements in both
S_{1}
and S_{2}
,
N_{io}
for the number of elements in
S_{1}
and outside S_{2}
,
N_{oi}
for the number of elements outside
S_{1}
and in S_{2}
,
N_{oo}
for the number of elements outside both
S_{1}
and S_{2}
.
i
is mnemonic for "in" and o
is
mnemonic for "out".) Furthermore, let us write
N_{id}
for the number of elements in
S_{1}
,
N_{di}
for the number of elements in
S_{2}
,
N_{dd}
for the total number of elements in
S
.
d
is mnemonic for "don't care".) By definition, we have
N_{id} = N_{ii} + N_{io} N_{di} = N_{ii} + N_{oi} N_{dd} = N_{ii} + N_{io} + N_{oi} + N_{oo};it follows that
N_{oo} = N_{dd} - (N_{ii} + N_{io} + N_{oi}) = N_{dd} - (N_{id} + N_{di}) + N_{ii}.Identity
N_{oo} = N_{dd} - (N_{id} + N_{di}) + N_{ii}is a special case of the inclusion-exclusion principle; inequalities
N_{oo} <= N_{dd} N_{oo} >= N_{dd} - (N_{id} + N_{di})a special case of the Boole-Bonferroni inequalities.
THREE SETS.
Consider a finite set S
and three subsets
S_{1},S_{2},S_{3}
of
S
. These three sets partition S
into eight
atoms (some of which may be empty). Let
N_{iii}
, N_{iio}
,
N_{ioi}
, N_{ioo}
,
N_{oii}
, N_{oio}
,
N_{ooi}
, N_{ooo}
denote the sizes of these atoms: let us write
N_{iii}
for the number of elements
in S_{1}
, in S_{2}
, and in
S_{3}
,
N_{iio}
for the number of elements
in S_{1}
, in S_{2}
, and outside
S_{3}
,
N_{ioi}
for the number of elements
in S_{1}
, outside S_{2}
, and in
S_{3}
,
N_{ioo}
for the number of elements
in S_{1}
, outside S_{2}
, and outside
S_{3}
,
N_{oii}
for the number of elements
outside S_{1}
, in S_{2}
, and in
S_{3}
,
N_{oio}
for the number of elements
outside S_{1}
, in S_{2}
, and outside
S_{3}
,
N_{ooi}
for the number of elements
outside S_{1}
, outside S_{2}
, and in
S_{3}
,
N_{ooo}
for the number of elements
outside S_{1}
, outside S_{2}
, and
outside S_{3}
.
N_{iid}
for the number of elements
in S_{1}
and in S_{2}
,
N_{idi}
for the number of elements
in S_{1}
and in S_{3}
,
N_{dii}
for the number of elements
in S_{2}
and in S_{3}
,
N_{idd}
for the number of elements
in S_{1}
,
N_{did}
for the number of elements
in S_{2}
,
N_{ddi}
for the number of elements
in S_{3}
,
N_{ddd}
for the total number of elements
in S
.
N_{iid} = N_{iii} + N_{iio}, N_{idi} = N_{iii} + N_{ioi}, N_{idd} = N_{iii} + N_{iio} + N_{ioi} + N_{ioo}, N_{dii} = N_{iii} + N_{oii}, N_{did} = N_{iii} + N_{iio} + N_{oii} + N_{oio}, N_{ddi} = N_{iii} + N_{ioi} + N_{oii} + N_{ooi}, N_{ddd} = N_{iii} + N_{iio} + N_{ioi} + N_{oii} + N_{ioo} + N_{oio} + N_{ooi} + N_{ooo};it follows that
N_{ooo} = N_{ddd} - (N_{iii} + N_{iio} + N_{ioi} + N_{oii} + N_{ioo} + N_{oio} + N_{ooi}) = N_{ddd} - (N_{idd} + N_{did} + N_{ddi}) + (2N_{iii} + N_{iio} + N_{ioi} + N_{oii}) = N_{ddd} - (N_{idd} + N_{did} + N_{ddi}) + (N_{iid} + N_{idi} + N_{dii}) - N_{iii}.Identity
N_{ooo} = N_{ddd} - (N_{idd} + N_{did} + N_{ddi}) + (N_{iid} + N_{idi} + N_{dii}) - N_{iii}is a special case of the inclusion-exclusion principle; inequalities
N_{ooo} <= N_{ddd} N_{ooo} >= N_{ddd} - (N_{idd} + N_{did} + N_{ddi}) N_{ooo} <= N_{ddd} - (N_{idd} + N_{did} + N_{ddi}) + (N_{iid} + N_{idi} + N_{dii})are a special case of the Boole-Bonferroni inequalities.
FOUR SETS.
Consider a finite set S
and four subsets
S_{1},S_{2},S_{3},S_{4}
of S
. In the notation suggested by the preceding two
examples, we have
N_{oooo} = N_{dddd} - (N_{iiii} + N_{iiio} + N_{iioi} + N_{ioii} + N_{oiii} + N_{iioo} + N_{ioio} + N_{iooi} + N_{oiio} + N_{oioi} + N_{ooii} + N_{iooo} + N_{oioo} + N_{ooio} + N_{oooi}) = N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (3N_{iiii} + 2N_{iiio} + 2N_{iioi} + 2N_{ioii} + 2N_{oiii} + N_{iioo} + N_{ioio} + N_{iooi} + N_{oiio} + N_{oioi} + N_{ooii}) = N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (N_{iidd} + N_{idid} + N_{iddi} + N_{diid} + N_{didi} + N_{ddii}) - (3N_{iiii} + N_{iiio} + N_{iioi} + N_{ioii} + N_{oiii}) = N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (N_{iidd} + N_{idid} + N_{iddi} + N_{diid} + N_{didi} + N_{ddii}) - (N_{iiio} + N_{iioi} + N_{ioii} + N_{oiii}) + N_{iiii}.Identity
N_{oooo} = N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (N_{iidd} + N_{idid} + N_{iddi} + N_{diid} + N_{didi} + N_{ddii}) - (N_{iiio} + N_{iioi} + N_{ioii} + N_{oiii}) + N_{iiii}is a special case of the inclusion-exclusion principle; inequalities
N_{oooo} <= N_{dddd} N_{oooo} >= N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) N_{oooo} <= N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (N_{iidd} + N_{idid} + N_{iddi} + N_{diid} + N_{didi} + N_{ddii}) N_{oooo} >= N_{dddd} - (N_{iddd} + N_{didd} + N_{ddid} + N_{dddi}) + (N_{iidd} + N_{idid} + N_{iddi} + N_{diid} + N_{didi} + N_{ddii}) - (N_{iiio} + N_{iioi} + N_{ioii} + N_{oiii})are a special case of the Boole-Bonferroni inequalities.
MANY SETS.
Consider a finite set S
and k
subsets
S_{1},S_{2},...,S_{k}
of S
. With the notation suggested by the preceding
examples, let T_{j}
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
N_{oo...o} = T_{0} - T_{1} + T_{2} - T_{3} + ... + (-1)^{k}T_{k};the Boole-Bonferroni inequalities assert that prefix-sums of the right-hand side alternate between upper and lower bounds on
N_{oo...o}
:
N_{oo...o} <= T_{0} N_{oo...o} >= T_{0} - T_{1} N_{oo...o} <= T_{0} - T_{1} + T_{2} N_{oo...o} >= T_{0} - T_{1} + T_{2} - T_{3}and so on.