Set Operations in Discrete Mathematics

---

---

In Discrete Mathematics, to represent discrete elements as collections, we can use sets. Sets are very useful in organizing and structuring the data. When working on sets, we must understand how to perform set operations.

In this chapter, we will have a look at some of the main set operations such as union, intersection, complement, difference, and Cartesian product.

Union of Sets

The most basic operation on sets is union. The union of two sets combines all elements from both sets into one. We can say this mathematically as the union of sets A and B is written as (A ∪ B). This operation includes all elements that are in A, in B, or in both. It is important to note that duplicate elements are not counted twice.

Definition − The union of sets A and B is the set containing all elements that are either in A, in B, or in both.

Symbol − (A ∪ B)

Example − If A = {1, 2, 3} and B = {2, 3, 4}, then A ∪ B = {1, 2, 3, 4}

Intersection of Sets

The next widely used operation is the intersection of two sets. Intersection finds the common elements shared by both sets. It is denoted by (A ∩ B) and contains only the elements that exist in both A and B.

Definition − The intersection of sets A and B is the set containing all elements that are present in both A and B.

Symbol − (A ∩ B)

Example − If A = {1, 2, 3} and B = {2, 3, 4}, then A ∩ B = {2, 3}

Set Difference

The next operation is the difference of two sets. This is denoted as (A – B). Set difference gives the elements that are in A but not in B. It is also called the relative complement of B in A.

Definition − The difference of sets A and B is the set of all elements that belong to A but not to B.

Symbol − (A – B)

Example − If A = {1, 2, 3} and B = {2, 3, 4}, then A – B = {1}.

Complement of a Set

After union and intersection, another fundamental operation is complement. Remember the difference is a combination of these fundamental operations. The complement of a set A, denoted as A^C or A′.

Complement contains all the elements not in A, assuming there is a universal set U that includes all possible elements under consideration.

Definition − The complement of set A consists of all elements in the universal set U that are not in A.

Symbol − A^C or A′

Example − If the universal set U = {1, 2, 3, 4, 5} and A = {1, 2, 3} then A^C = {4, 5}

Advanced Operations

Let us now see some of the advanced set operations. These operations are special due to their use cases. Some of them are known to us, but some of them are quite unfamiliar.

Symmetric Difference

The symmetric difference between two sets A and B, which is denoted by (A B), is the set of elements that are in either of the sets but not in their intersection.

Definition − The symmetric difference is the set of elements that are in one of the sets but not in both.

Symbol − (A B)

Example − If A = {1, 2, 3} and B = {2, 3, 4} then A B = {1, 4}.

Cartesian Product

The Cartesian product of two sets A and B, denoted as (A × B). It is the set of all ordered pairs where the first element is from A and the second is from B.

Definition − The Cartesian product of sets A and B is the set of all ordered pairs (a, b) where a ∈ A and b ∈

Symbol − (A × B)

Example − If A = {1, 2} and B = {3, 4}, then A × B = {(1, 3), (1, 4), (2, 3), (2, 4)}

Examples of Set Operations

We have here a couple of examples to illustrate set operations in greater detail.

Example 1 − Let A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 6}, C = {1, 2, 3}, and D = {7, 8, 9}

• A ∪ B = {1, 2, 3, 4, 5, 6} (since everything in B is already in A).
• A ∩ B = {2, 4, 6} (elements common to both sets).
• B ∩ C = {2} (the only element common to both B and C).
• A ∩ D = ∅ (no common elements between A and D).
• B ∪ C = {1, 2, 3, 4, 6} (union of B and C).
• A – B = {1, 3, 5} (elements in A but not in B).

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

• A × B = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}
• A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}

Using Venn Diagrams

Sometimes we need to represent sets through diagrams. These are known as Venn diagrams. These diagrams are a visual tool for representing set operations.

In Venn diagrams, sets are represented by overlapping circles. The intersection, union, and other operations can be shown by shading the appropriate regions of the circles.

• Union − The union of two sets is shown by shading the entire area covered by both circles.
• Intersection − The intersection is represented by shading only the region where the circles overlap.
• Difference − The difference A – B is represented by shading the part of A that does not overlap with B.

Venn diagrams help visualize the relationships between sets and can simplify the process of understanding more complex operations.

We will see all of these operations and other complex sets in the next chapter.

Important Properties of Set Operations

Let us see some of the key properties of set operations −

Commutativity −

• A ∪ B = B ∪ A
• A ∩ B = B ∩ A

Associativity −

• A ∪ (B ∪ C) = (A ∪ B) ∪ C
• A ∩ (B ∩ C) = (A ∩ B) ∩ C

Distributivity −

• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

De Morgan’s Laws −

• (A ∪ B)^C = A^C ∩ B^C
• (A ∩ B)^C = A^C ∪ B^C

These properties provide a framework for simplifying and understanding set expressions.

Conclusion

In this chapter, we explained the basic set operations like union, intersection, difference, and complement, as well as more advanced operations such as Cartesian products, etc.

Through examples and explanations, we understood how these operations work. Additionally, we learned about key properties of set operations, including commutativity, associativity, and De Morgans Laws.