Multisets
Multiset is an unordered collection of elements where an element can occur as a member more than once. Hence, multiset is a set in which elements are not necessarily distinct. The multiplicity of an element is the number of times the element repeated in the multiset.
Example: If F is the set of some of my friends:
F = {Deepak, Himanshu, Deepak, Avishkar, Himanshi, Anuj, Deepak, Kamal, Umesh, Deepanshu}
Operations on Multisets
Union of Multisets
The union of two multisets A and B is a multiset such that the multiplicity of an element is equal to the maximum multiplicity of an element in A and B. It is denoted by A ∪ B.
Example: Let A = {1, 2, 1, 2, 3, 1} and B = {1, 2, 3, 2, 2, 4, 1}
then A ∪ B = {1, 1, 1, 2, 2, 2, 3}
Intersection of Multisets
The intersection of two multisets A and B is a multiset such that the multiplicity of an element is equal to the minimum of the multiplicity of an element in A and B. It is denoted by A ∩ B.
Example: Let A = {1, 2, 1, 2, 3, 1} and B = {1, 2, 3, 2, 2, 4, 1}
then A ∩ B = {1, 1, 2, 2, 3}
Difference of Multisets
The difference of two multisets A and B is a multiset such that the multiplicity of an element is equal to the multiplicity of the element in A minus the multiplicity of the element in B if the difference is positive, and is equal to zero(0) if the difference is zero or negative.
Example: Let A = {1, 2, 1, 2, 3, 1} and B = {1, 2, 3, 2, 2, 4, 1}
then A - B = {1} and B - A = {2, 4}
Sum of Multisets
The sum of two multisets A and B is a multiset such that the multiplicity of an element is equal to the sum of the multiplicity of an element in A and B.
Example: Let A = {1, 2, 1, 2, 3, 1} and B = {1, 2, 3, 2, 2, 4, 1}
then A + B = {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4}
Cardinality of Multisets
The cardinality of a multiset is the number of distinct elements in a multiset without considering the multiplicity of an element.
Example: Let A = {1, 2, 1, 2, 3, 1} and B = {1, 2, 3, 2, 2, 4, 1}
then cardinality of A is 3 and cardinality of B is 4.
Ordered Pairs
An ordered pair consists of two elements such that one of them is designated as the first member and the other as the second member.
(a, b) and (b, a) are two different ordered pair. An ordered triple can also be written regarding an ordered pair as {(a, b), c}. An ordered quadrable is an ordered pair {(((a, b), c), d)} with the first element as ordered triple.
An ordered n-tuple is an ordered pair where the first component is an ordered (n-1) tuples and nth element is the second component i.e. {(n-1), n}.
Mathematical Induction
The process to establish the validity of an ordinary result involving natural numbers is the principle of mathematical induction.
Working Rule
Let n0(generally 1) be a fixed integer. Suppose P(n) is a statement involving the natural number n and we wish to prove that P(n) is true for all n0 ≤ n such that
- Basic of Induction: P(n0) is true i.e. P(n) is true for n = n0(1).
- Induction Step: Assume that the P(k) is true for n = k.
Then P(k+1) must also be true.
Then P(n) is true for all n0 ≤ n.
Comments
Post a Comment