DHARMDISCRETE THEORY, RELATIONS AND FUNCTIONS 7(S2) Rule of Sums
Let Xk {for k = 1 to n}, is a finite family of finite pair wise disjoint sets, then∪=
kn=to k kn=to k
XX
1 1
Σ | |1.3.4 Multisets.................................................................................................................
Since, we know that the elements of the sets are all distinct, but often we see that the elements
are not necessarily distinct, we may say that there are repeated occurrence of some elements
in the set. Such sets may be pronounced as redundant representation of set called multiset.
For example, {a, b, b, c, b}, {a, a, a, a}, { a, b, c}, { } etc. are all multisets.
A multiset on X is a set X together with a function f : X → N, where N = {0, 1, 2, .....}
giving the multiplicity of the elements of X. Multiplicity of the elements is given by the number
of times the element appears in the multiset. Multiset is a set where multiplicity of its ele-
ments are all 1 and it is a null set where element multiplicity is 0.
We can denote the multiset M on X is M = {ama : a ∈ X} with ma = f(a), a ∈ X. The usual
operations for sets can be carried over to multisets. For instance, if M = {ama : a ∈ X} and N =
{ana : a ∈ X} then
l M ⊆ N = ma ≤ na for all a ∈ X,
l M ∪ N = {:aamax (mnaa, ) ∈X], and
l M ∩ N = {:aamin (mnaa, ) ∈X] ;
l M – N = {a()mnaa− : (ma – na) ≥ 1 and a ∈ X};
[It also seen that multisets on a set X forms a lattice under inclusion (⊆)] for lattice see
more in chapter 2.
1.3.5 Ordered Sets...........................................................................................................
In the sets the order of the elements are discretionary. So a set may be further defined as an
unordered aggregation of objects or elements. In this section we will concentrate on the ordered
set of objects. A couple (duo) of objects is said to be ordered if it is arranged distinctly. We can
denote the ordered couple by (x, y) where component x and y referring the first and second
objects of the ordered couple. Ordered couple is different from the set in the sense that ordering
of the objects is important simultaneously objects need not to be distinct in the ordered pair.
Because of distinct ordering of the objects (x, y) ≠ (y, x) while sets {x, y} = {y, x}.
Resemblance, to that idea of ordered couple can be extended to ordered triple, ordered
quadruple, ...., and ordered n - tuples. Alternatively, an ordered triple e.g. (x, y, z) is an ordered
couple ((x, y), z) where first component is itself is an ordered couple. Likeness to that, an
ordered quadruple (w, x, y, z) has first component is an ordered triple e.g. ((w, x, y), z) and so
(((w, x), y), z). Therefore, an ordered n-tuples (x 1 , x 2 .......xn) has first component is an ordered
(n – 1) tuples e.g. ((x 1 , x 2 .......xn–1), xn).
1.3.6 Cartesian Products.................................................................................................
Given two sets X and Y, then Cartesian product of sets X and Y denoted by X × Y, is the set of
all ordered couples (x, y) such that x ∈ X and y ∈ Y.
i.e. X × Y = {(x, y)/x ∈ X and y ∈ Y}