Properties of Set Operations

Set operations follow some fundamental properties.

Some of these properties resemble those found in arithmetic, such as the commutative, associative, and distributive properties of union and intersection.

Others, however, are unique to set theory. These include the idempotent property, the absorption laws, and De Morgan’s laws.

Table of Properties

The table below outlines the key properties of set operations.

Property	Expression
Idempotent Property	\( A \cap A = A \) \( A \cup A = A \)
Commutative Property of Intersection	\( A \cap B = B \cap A \)
Commutative Property of Union	\( A \cup B = B \cup A \)
Associative Property of Intersection	\( A \cap (B \cap C) = (A \cap B) \cap C \)
Associative Property of Union	\( A \cup (B \cup C) = (A \cup B) \cup C \)
Absorption Laws	\( A \cap (A \cup B) = A \) \( A \cup (A \cap B) = A \)
Distributive Property of Intersection over Union	\( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)
Distributive Property of Union over Intersection	\( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \)
De Morgan’s Laws	\( \overline{A \cap B} = \overline{A} \cup \overline{B} \) \( \overline{A \cup B} = \overline{A} \cap \overline{B} \)

These properties are essential because they form the foundation for problem-solving in set algebra.

For instance, they play a crucial role in programming languages, combinatorial analysis, and probability theory. Another key application lies in formal language theory and automata, where operations like union and intersection are fundamental in defining and manipulating regular languages and more complex grammatical structures.

Idempotent Property

The idempotent property states that if you take a set \( A \) and apply union to itself (\( A \cup A \)), you still get \( A \):

$$ A \cup A = A $$

Similarly, if you intersect \( A \) with itself (\( A \cap A \)), the result is still \( A \):

$$ A \cap A = A $$

In other words, these operations leave the set unchanged because you're simply repeating the same elements.

At first glance, this might seem trivial—of course, merging a set with itself won’t change anything. And that’s exactly the point! Nothing happens.

The same holds true for intersection:

$$ A \cap A = A $$

While this property may seem obvious, overlooking it can lead to basic mistakes.

Note: The idempotent property is particularly useful in Boolean algebra when simplifying set expressions. Recognizing this property prevents redundant calculations and unnecessary work, making expressions more efficient to handle.

Example

Suppose we have a list of students enrolled in a university course:

\[ A = \{ \text{Alice, Bob, Charlie} \} \]

Now, for some reason, we attempt to unite the set with itself:

\[ A \cup A = \{ \text{Alice, Bob, Charlie} \} \cup \{ \text{Alice, Bob, Charlie} \} \]

The result? The exact same set. Adding the same students twice doesn’t change anything—the course still consists of the same three people.

\[ A \cup A = \{ \text{Alice, Bob, Charlie} \} \]

The same logic applies to intersection:

\[ A \cap A = \{ \text{Alice, Bob, Charlie} \} \cap \{ \text{Alice, Bob, Charlie} \} \]

Of course, the result is still \( A \), since we’re identifying elements that are common to two identical sets.

In simple terms, uniting or intersecting a set with itself is like trying to increase your wardrobe by listing the same clothes twice—it doesn’t change what’s in your closet.

Absorption Laws

The absorption law states that intersecting a set with a larger expression that already contains it yields the set itself: \[ A \cap (A \cup B) = A \] Likewise, taking the union of a set with a subset of itself also leaves the set unchanged: \[ A \cup (A \cap B) = A \]

In simple terms, adding elements that are already included or removing elements that make no difference doesn’t change the outcome—the set remains the same.

These are called "absorption laws" because, in both cases, set \( A \) absorbs the effect of the union or intersection with \( B \), rendering \( B \) irrelevant in the final result.

For example, consider the intersection: \[ A \cap (A \cup B) = A \] Here, \( A \) "absorbs" \( B \) because intersecting with \( A \cup B \) doesn’t introduce anything new—everything in the result was already in \( A \). Similarly, in the union: \[ A \cup (A \cap B) = A \] Set \( A \) "absorbs" \( A \cap B \) since adding a portion of \( A \) back into itself is redundant.

Example

Suppose set \( A \) represents students who passed an exam, while set \( B \) includes all students who took the exam, regardless of whether they passed or failed.

1] First Absorption Law

The first absorption law states: \[ A \cap (A \cup B) = A \]

Here, \( A \cup B \) represents all students who attempted the exam, including both those who passed and those who failed.

When we take the intersection \( A \cap (A \cup B) \), we’re selecting only the students who belong to both sets.

But since every student in \( A \) is already in \( A \cup B \), the result is simply \( A \). The presence of \( B \) is irrelevant.

2] Second Absorption Law

The second absorption law states: \[ A \cup (A \cap B) = A \]

Here, \( A \cap B \) consists of students who both passed the exam (\( A \)) and, by definition, took the exam (\( B \)).

Since \( A \cap B \) is already a subset of \( A \), taking the union with \( A \) changes nothing.

$$ (A \cap B) \subseteq A $$

And if we take the union with \( A \), we still get \( A \). Nothing new is added:

$$ A \cup (A \cap B) = A \cup A = A $$

The absorption laws are a handy tool for simplifying redundant expressions and avoiding unnecessary complexity in calculations.

Distributive Property of Intersection Over Union

The distributive property of intersection over union states that taking the intersection of a set with the union of two sets is equivalent to taking the union of the intersections of that set with each of the two sets separately. Mathematically, this can be expressed as:   \[
A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \]

This might look a bit abstract at first, but all it really says is that intersection distributes over union—just like multiplication distributes over addition in arithmetic.

In simpler terms, instead of first computing the union and then intersecting it with \( A \), we can first find the intersection of \( A \) with \( B \) and the intersection of \( A \) with \( C \), and then take the union of those two results.

Example

Let’s consider three sets: \( A \), \( B \), and \( C \).

• \( A \) represents the set of students who scored at least 18 on their linear algebra exam.
• \( B \) is the set of students enrolled in the department of mathematics.
• \( C \) is the set of students enrolled in the department of computer science.

Now, we want to determine the set of students who passed the linear algebra exam and are enrolled in either mathematics or computer science.

We’ll evaluate both sides of the equation to verify that they yield the same result.

1] Evaluating the left-hand side: \( A \cap (B \cup C) \)

First, we compute the union \( B \cup C \), which consists of all students enrolled in either mathematics or computer science.

Next, we intersect this set with \( A \), which contains students who scored at least 18 on the exam.

The result is the set of students who both passed the exam and are enrolled in at least one of the two programs.

2] Evaluating the right-hand side: \( (A \cap B) \cup (A \cap C) \)

First, we compute \( A \cap B \), which consists of students who passed the exam and are enrolled in mathematics.

Next, we compute \( A \cap C \), which consists of students who passed the exam and are enrolled in computer science.

Finally, we take the union of these two sets. The result is the set of students who passed the exam and are enrolled in at least one of the two programs.

Since both sides yield the same set, the property holds.

Distributive Property of Union Over Intersection

The distributive property of union over intersection states that the union of a set with the intersection of two sets is equivalent to the intersection of the unions of that set with each of the two sets separately: \[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]

In other words, taking the union first and then the intersection yields the same result as taking the intersection first and then the union.

Practically speaking, instead of uniting \( A \) with \( B \cap C \) in one step, we can distribute the union across both terms of \( B \cap C \), perform each operation separately, and then take their intersection.

Example

Let's consider three sets:

• \( A \) represents students who have a scholarship.
• \( B \) represents students enrolled in the mathematics program.
• \( C \) represents students enrolled in the computer science program.

We want to determine the set of students who either have a scholarship or are enrolled in both programs (mathematics and computer science).

To do this, we evaluate both sides of the equation:

1] Evaluating the left-hand side: \( A \cup (B \cap C) \)

First, we compute the intersection \( B \cap C \), which gives us the students who are enrolled in both programs.

Next, we take the union with \( A \), meaning we include all students who either have a scholarship or are enrolled in both programs.

The result is the set of students who meet at least one of these criteria.

2] Evaluating the right-hand side: \( (A \cup B) \cap (A \cup C) \)

We start by computing \( A \cup B \), which includes students who either have a scholarship or are enrolled in the mathematics program.

Similarly, \( A \cup C \) consists of students who either have a scholarship or are enrolled in the computer science program.

Finally, we take the intersection of these two sets, which gives us students who appear in both—meaning they either have a scholarship or are enrolled in both programs.

Since both approaches yield the same result, this confirms the validity of the distributive property.

De Morgan's Laws

De Morgan's Laws describe how the negation of a logical operation can be rewritten using the negations of its individual components with an opposite operation. The formulas are: \[ \overline{A \cap B} = \overline{A} \cup \overline{B} \] \[ \overline{A \cup B} = \overline{A} \cap \overline{B} \]

But what do these laws actually mean in practice? They’re among the less intuitive properties of set operations.

Put simply, De Morgan’s Laws state that negating an intersection is equivalent to taking the union of the negations, while negating a union is equivalent to taking the intersection of the negations.

Think of it this way: saying you don’t love both coffee and tea means you dislike at least one of them. On the other hand, saying you don’t love coffee or tea means you dislike both.

Let’s clarify this with a concrete example.

Practical Example

Suppose a restaurant serves only two main dishes:

- \( A \): Pizza
- \( B \): Pasta

Now, let’s describe the group of people who don’t want either pizza or pasta in two different ways.

According to De Morgan’s first law, we have the following formula:

$$ \overline{A \cap B} = \overline{A} \cup \overline{B} $$

The left-hand side of the equation, \( \overline{A \cap B} \), represents "everyone who doesn’t want both pizza and pasta at the same time."

Note: The intersection \( A \cap B \) includes all the people who enjoy both pizza and pasta. Therefore, its negation, \( \overline{A \cap B} \), represents those who do not enjoy both together—meaning it’s enough to dislike at least one of the two to be included in this set.

The set of people who either don’t want pizza (\( \overline{A} \)) or don’t want pasta (\( \overline{B} \)) can also be written as:

\[ \overline{A} \cup \overline{B} \]

Both expressions describe the same set.

Now, according to De Morgan’s second law, we have the following formula:

$$ \overline{A \cup B} = \overline{A} \cap \overline{B} $$

Here, the left-hand side, \( \overline{A \cup B} \), represents "everyone who doesn’t want either pizza or pasta."

Since these are exactly the people who reject both pizza and pasta simultaneously, we can rewrite this group as:

$$ \overline{A} \cap \overline{B} $$

Here, \( \overline{A} \) represents "people who don’t want pizza," while \( \overline{B} \) represents "people who don’t want pasta."

The intersection \( \overline{A} \cap \overline{B} \) gives us the elements common to both sets—namely, the people who refuse both pizza and pasta.

And so on.