Cardinality of a Set
Cardinality of a set (n) is defined as the number of elements in a set. Suppose A={2,4,6,7,8}, then n=5.
If A1,A2,A3,A4,.......,Am are the sets with cardinality ni where i=1,2,3,.......m respectively, then
n(A1∪A2) = n1 (A1) + n2 (A2) - n(A1∩A2) ......... no. of entries 3
n(A1∪A2∪A3) = n1 (A1) + n2 (A2) + n3 (A3) - n(A1∩A2)- n(A2∩A3)- n(A1∩A3) + n(A1∩A2∩A3) ......... no. of entries 7
n(A1∪A2∪A3∪A4) = n1 (A1) + n2 (A2) + n3 (A3) + n3 (A4) - n(A1∩A2)- n(A2∩A3)- n(A1∩A3) - n(A3∩A4)- n(A2∩A4)- n(A1∩A4)+ n(A1∩A2∩A3) + n(A2∩A3∩A4)+ n(A1∩A3∩A4)
+ n(A1∩A2∩A4) + n(A1∩A2∩A3∩A4) ......... no. of entries 15
n(UAi) = Σ n(Ai) - Σ n(Ai ∩Aj) + Σ n(Ai ∩Aj ∩Ak) - Σ n(Ai ∩Aj ∩Ak ∩Al)+ ............ +(-1)m-1 n( Ai ∩Aj ∩Ak ∩Al.........∩Am)
i= 1 to m i= 1 to m i,j= 1 to m, i<j i,j,k= 1 to m, i<j <k i,j,k,l= 1 to m, i<j <k<l
Observation :
(1) When 2 sets are there, no. of entries 3, when 3 sets,no. of entries 7, when 4 sets, no.of entries , So when m sets, Total no. of entries=2m -1. If one includes the set itself, it becomes 2m
(2) If one studies the distributions, one finds
(a) first is the sum of cardinalities of individual sets, Which is mC1.
(b) second is sum of cardinalities of various dual combinations of sets, Which is mC2 with -Ve sign
(c) third is sum of cardinalities of various triple combinations of sets, Which is mC3With +Ve sign
(d) so on with alternate changes of sign
(e) Last is the single combination of all sets Which is mCm
Therefore the total no. of entries is mC1+ mC2 + mC3 + ...... + mCm = Σ mCi (where i= 1 to m.) = 2m -1
1 means one set, 2 means dual combination of sets , 3 means triple combination of sets and so on so forth.
Table