1.3 Set Operations and Cartesian Products

In Section 1.2, you learned how to describe one set and how to decide whether an object belongs to it. We will now combine two sets. This gives us two useful ways to build new objects:

• Set operations combine or compare membership rules.

• A Cartesian product combines one choice from a first set with one choice from a second set.

By the end of this section, you will be able to compute unions, intersections, differences, complements, and Cartesian products from scratch. You will also be able to explain what each result means instead of only manipulating symbols.

Fix the universe before operating on sets

A universal set, written $U$, is the collection of every object currently under discussion. It is not the set of everything that exists. Its meaning depends on the problem.

For example, if we study the integers from $1$ through $6$, we may choose

Every set in that problem is then treated as a subset of $U$. Let

We will use this same example throughout the first half of the section. Keeping one universe fixed prevents an important ambiguity: the phrase “not in $A$” only tells us which objects to keep after we know which objects are allowed in the first place.

Four set operations, one element at a time

Imagine choosing one element $x$ from $U$ and asking two yes-or-no questions:

1. Is $x$ in $A$?

2. Is $x$ in $B$?

There are exactly four possible membership regions:

Every operation below selects one or more of these regions.

Union: keep anything appearing in either set

The union of $A$ and $B$, written $A\cup B$, contains an element when it is in $A$, in $B$, or in both:

The vertical bar $\mid$ means “such that.” Read the formula as: “the set of elements $x$ in $U$ such that $x$ belongs to $A$ or $B$.” Mathematical “or” is inclusive here, so an element in both sets is kept.

For our example, start with the elements of $A$ and add the elements of $B$ that are not already listed:

Repeated elements are written only once because a set does not record duplicates.

Intersection: keep only shared elements

The intersection, written $A\cap B$, contains an element only when it belongs to both sets:

Checking the elements shows that only $2$ and $6$ pass both membership tests:

Difference: keep one side and remove the overlap

The difference $A\setminus B$ begins with $A$ and removes every element that also lies in $B$:

The symbol $\notin$ means “is not an element of.” In the example, remove $2$ and $6$ from $A$, leaving

Difference has a direction. If we reverse the sets, we begin with $B$ instead:

Therefore $A\setminus B$ and $B\setminus A$ are generally different.

Complement: keep everything outside one set

The complement of $A$, written $A^{\mathsf c}$, contains every element of the fixed universe that is not in $A$:

Starting with $U=\{1,2,3,4,5,6\}$ and removing $1,2,4,6$ gives

This is why the universe matters. If the universe changed, the complement could change even when $A$ stayed the same.

Check all four regions

For the same $U$, $A$, and $B$, the four disjoint regions are

“Disjoint” means that no element occurs in two of these regions. Together the regions contain every element of $U$. You can therefore use them as an error check: each element of $U$ must appear exactly once.

The lab turns the four membership regions into drop zones. Before dropping an object, say its two membership answers aloud—“in $A$, not in $B$,” for example—and then choose the matching region. This connects the picture to the membership rule.

Counting a union without counting twice

If we add $|A|$ and $|B|$, every element in $A\cap B$ is counted once as part of $A$ and a second time as part of $B$. Subtracting the size of the intersection removes that extra copy:

In our example,

which agrees with the five listed elements $\{1,2,3,4,6\}$. This reasoning is called inclusion–exclusion for two sets. Later chapters will extend the same counting idea.

Why complements reverse “or” and “and”

The following identities are called De Morgan’s laws:

The notation looks compact, but the idea can be read in ordinary language:

• An element is not in the union only if it is not in $A$ and not in $B$.

• An element is not in the intersection if it is not in $A$, or not in $B$, or in neither.

To check the first law, follow one arbitrary element $x$. If $x\notin A\cup B$, then $x$ was accepted by neither set. Thus $x\in A^{\mathsf c}$ and $x\in B^{\mathsf c}$, so $x\in A^{\mathsf c}\cap B^{\mathsf c}$. The reasoning also runs backward, so the two sets contain exactly the same elements.

The words “and,” “or,” and “not” will become formal logical operations in Chapter 2. Here you only need their ordinary membership meanings.

Ordered pairs remember two positions

Set operations combine membership rules. Our second construction combines choices. Suppose an app has two users,

and three actions,

To describe “Ada performs edit,” we need to store both a user and an action. An ordered pair does this:

The first position and second position have different roles. In general,

Two ordered pairs are equal only when their first coordinates match and their second coordinates match:

The words first coordinate and second coordinate simply name the two positions. No geometric knowledge is required.

Cartesian products generate every possible pair

The Cartesian product $A\times B$ contains every ordered pair whose first coordinate comes from $A$ and whose second coordinate comes from $B$:

Use a systematic procedure to list it:

1. Choose the first element of $A$.

2. Pair it with every element of $B$.

3. Move to the next element of $A$ and repeat.

For $A=\{1,2\}$ and $B=\{x,y,z\}$, this produces

We may display the same six pairs as a rectangular table:

The brackets only organize the pairs into rows and columns here. You do not need matrix algebra.

If $A$ has $2$ choices and $B$ has $3$ choices, each of the $2$ first-coordinate choices has $3$ possible partners. Therefore there are $2\cdot3=6$ pairs. For any finite sets,

In the pixel floor, every cell represents one ordered pair. Its row fixes one coordinate and its column fixes the other. Painting all cells constructs the full Cartesian product; painting only selected cells creates a set of selected pairs.

Such a selected set $R\subseteq A\times B$ is called a binary relation from $A$ to $B$. For now, “relation” means only “some selected ordered pairs.” Chapter 4 will build the full theory, so no other facts about relations are assumed here.

Chapter bridge

Across this chapter, you learned to recognize discrete states, describe collections as sets, operate on membership, and construct ordered pairs. Notice how often the words “and,” “or,” and “not” appeared in our definitions. Chapter 2 begins with those familiar words and turns them into precise logical statements, one step at a time.