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

Total no. of sets Total no. of entries Formula No. of Entries value
m -  2m -1
Single combination mC1
Double combination mC2
Triple combination mC3
4 combinations mC4
5 combinations mC5
6 combinations mC6
7 combinations mC7
8 combinations mC8
9 combinations mC9
10 combinations mC10
Total Σ mCi