Multisets and Ordered Sets in Discrete Mathematics: Definitions and Operations

Learn about multisets (bags) and ordered sets in discrete mathematics. This guide explains the differences between these structures and regular sets, defines common multiset operations (union, intersection, etc.), and provides examples.

Understanding Multisets and Ordered Sets

What is a Multiset?

A multiset is like a regular set, but it allows elements to appear more than once. The number of times an element appears is called its multiplicity. Think of it as a collection where duplicates are allowed and counted.

Examples of Multisets

A = {l, l, m, m, n, n, n, n} (l appears twice, m twice, n four times)

B = {a, a, a, a, a, c} (a appears five times, c appears once)

Operations on Multisets

Here are some common operations you can perform on multisets:

  • Union (A ∪ B): The multiplicity of each element is the larger of its multiplicities in A and B.
  • Intersection (A ∩ B): The multiplicity of each element is the smaller of its multiplicities in A and B.
  • Difference (A - B): The multiplicity of each element is its multiplicity in A minus its multiplicity in B (if positive; otherwise 0).
  • Sum (A + B): The multiplicity of each element is the sum of its multiplicities in A and B.
  • Cardinality: The number of distinct elements in the multiset (ignoring multiplicities).

Examples of Multiset Operations

Let A = {1, 1, 2, 3, 3, 3} and B = {1, 2, 2, 3, 4}

  • A ∪ B = {1, 1, 2, 2, 3, 3, 3, 4}
  • A ∩ B = {1, 2, 3}
  • A - B = {1, 3, 3}
  • A + B = {1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4}
  • Cardinality of A = 3

Ordered Sets

An ordered set is a collection of distinct elements where the order matters. Unlike multisets, duplicates aren't allowed.

Examples of Ordered Sets

Roll numbers: {3, 6, 7, 8, 9} (order matters)

Days of the week: {Monday, Tuesday, Wednesday, ...}

Ordered Pairs, Triples, and n-tuples

An ordered pair is a set with two elements where the order is important: (a, b) is different from (b, a). Ordered triples, quadruples, and n-tuples extend this concept to three, four, or n elements respectively. The order always matters.

Conclusion

Multisets and ordered sets are important concepts in mathematics and computer science. They offer ways to represent collections of items where either the order or the multiplicity of elements, or both, are significant.