Operations on Finite Sets

Building New Sets: Union, Intersection, and Difference

At their core, the three most basic set operations are direct analogues of the logical connectives "OR", "AND", and "AND NOT" that we've already discussed.

• Union ($\cup$): The union of two sets A and B contains every element that is in A or in B (or in both).
• Intersection ($\cap$): The intersection of A and B contains only those elements that are in A and in B.
• Difference ($-$ or $\setminus$): The difference of A and B contains the elements that are in A and not in B.

The following video provides an excellent visual and spoken-word introduction to these three concepts, using Venn diagrams to help build your intuition.

Now that you have a strong visual and intuitive grasp, let's look at the formal definitions. These definitions are what we use in mathematical proofs and are crucial for precise communication.

From Sets to Ordered Pairs: The Cartesian Product

Union, intersection, and difference all produce a new set containing elements of the same "type" as the original sets. The Cartesian product is different: it takes two sets and creates a new set of ordered pairs.

An ordered pair (a, b) is not the same as the set {a, b}. In the set, order doesn't matter, so {a, b} is identical to {b, a}. In the ordered pair, order is critical, so (a, b) is different from (b, a) unless a = b. You've encountered ordered pairs constantly in algebra when plotting points (x, y) on a graph.

The Cartesian product $A\times B$ (read "A cross B") is the set of all possible ordered pairs (a, b) where a is an element of A and b is an element of B.

This concept is fundamental for understanding relations and functions, which we'll see soon. It's also critical in computer science for things like generating all possible test cases (e.g., set of browsers $\times$ set of operating systems) or in database theory when joining tables.

The following video from TrevTutor provides a very clear explanation of ordered pairs and how to construct Cartesian products.

Set Operations in Python

Given your background in Python, it's useful to see how directly these mathematical concepts map to code. Python's set data type is a direct implementation of the mathematical idea of a finite set.

Let's define two sets:

# A is the set of vowels
A = {'a', 'e', 'i', 'o', 'u'}
# B is the set of letters in 'cybersecurity'
B = set('cybersecurity')
# Python automatically handles duplicates, so B is {'c', 'y', 'b', 'e', 'r', 's', 'u', 'i', 't'}

Now we can perform the operations:

• Union: A | B or A.union(B)

  >>> A | B
  {'o', 'c', 't', 'b', 'y', 'i', 's', 'r', 'a', 'e', 'u'}
  

• Intersection: A & B or A.intersection(B)

  >>> A & B
  {'e', 'i', 'u'} # The vowels present in 'cybersecurity'
  

• Difference: A - B or A.difference(B)

  >>> A - B
  {'a', 'o'} # Vowels that are NOT in 'cybersecurity'
  

For the Cartesian product, there's no simple operator, but the itertools module in the standard library provides the product function for exactly this purpose.

import itertools

A = {1, 2}
B = {'x', 'y'}

# itertools.product returns an iterator, so we convert it to a list to see the elements
cartesian_product = list(itertools.product(A, B))

print(cartesian_product)
# Output: [(1, 'x'), (1, 'y'), (2, 'x'), (2, 'y')]

This is a great example of how mathematical foundations are built directly into the programming languages you use.

Practice and Consolidation

To solidify your understanding, please return to the "Set Theory" reading and complete the following exercises. These will test your ability to apply all four operations to finite sets of integers.

Conclusion

In this lesson, we have defined and practiced the four fundamental operations for building new sets from existing ones. These tools are essential for working with collections of objects in a structured way.

Key Takeaways:

• Union ($\cup$) combines elements using a logical OR.
• Intersection ($\cap$) selects common elements using a logical AND.
• Difference ($-$) removes elements from one set that are present in another.
• Cartesian Product ($\times$) creates a new set of all possible ordered pairs from two sets.
• These abstract mathematical operations have direct, high-performance implementations in programming languages like Python.

In our next lesson, we will continue our study of sets by formalizing concepts we've already touched upon: membership ($\in$), subsets ($\subseteq$), and cardinality ($|A|$). This will give us the vocabulary to make precise statements about the relationships between sets and their elements.