4.1 Set operations

Set operations give you a systematic way to combine, compare, and manipulate collections of objects. They're the core toolkit for working with sets, and you'll see them constantly in logic, probability, and computer science. This guide covers the operations themselves, their properties, and how to use them.

Fundamentals of sets

Before diving into operations, you need a solid grasp of what sets are and how we talk about them.

Definition of a set

A set is a collection of distinct objects called elements (or members). You can define a set by listing its elements or by describing a property they share. Sets are written with curly braces: $\{1, 2, 3\}$.

Two things to remember:

• Order doesn't matter: $\{1, 2, 3\}$ and $\{3, 1, 2\}$ are the same set
• No duplicates: each element appears exactly once

Elements can be numbers, symbols, or really any mathematical objects.

Set notation

• Elements are listed within curly braces, separated by commas: $\{a, b, c\}$
• Set-builder notation defines a set by a property: $\{x \mid x > 5\}$ means "the set of all $x$ such that $x$ is greater than 5." The vertical bar $\mid$ (or colon) is read as "such that."
• $\in$ means "is an element of." So $3 \in \{1, 2, 3\}$ is true.
• $\notin$ means "is not an element of."
• $\emptyset$ or $\{\}$ is the empty set, which contains no elements.
• $U$ is the universal set, the set of all elements under consideration in a given problem.

Types of sets

• Finite sets have a countable number of elements: $\{2, 4, 6\}$
• Infinite sets have unlimited elements, like the natural numbers $\{1, 2, 3, \ldots\}$
• Empty set ($\emptyset$) contains nothing at all
• Singleton set has exactly one element: $\{7\}$
• Subset: $A \subseteq B$ means every element of $A$ is also in $B$
• Proper subset: $A \subset B$ means $A \subseteq B$ but $A \neq B$
• Equal sets contain exactly the same elements: $A = B$

Basic set operations

These four operations are the building blocks. Once you understand them, everything else in this guide builds on top.

Union of sets

The union of two sets combines all elements from both into one set, with no duplicates.

$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$

For example, if $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$, then $A \cup B = \{1, 2, 3, 4, 5\}$. The 3 appears in both, but it's listed only once in the result.

Think of union as "everything from either set."

Intersection of sets

The intersection keeps only the elements that appear in both sets.

$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$

Using the same sets: $A \cap B = \{3\}$, since 3 is the only shared element. If two sets share no elements, their intersection is $\emptyset$, and they're called disjoint.

Think of intersection as "only what they have in common."

Set difference

The difference $A \setminus B$ gives you everything in $A$ that's not in $B$.

$A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}$

With $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$: $A \setminus B = \{1, 2\}$, while $B \setminus A = \{4, 5\}$. Notice these aren't equal. Set difference is not commutative.

Complement of a set

The complement of $A$ is everything in the universal set that's not in $A$.

$A^c = \{x \mid x \in U \text{ and } x \notin A\}$

If $U = \{1, 2, 3, 4, 5\}$ and $A = \{1, 2\}$, then $A^c = \{3, 4, 5\}$. The complement always depends on what $U$ is, so make sure you know the universal set before computing it.

You'll also see the complement written as $A'$ or $\overline{A}$.

Advanced set operations

These build on the basics and show up in more complex problems.

Symmetric difference

The symmetric difference contains elements that are in one set or the other, but not both. It's the union minus the intersection.

$A \triangle B = (A \setminus B) \cup (B \setminus A)$

Equivalently: $A \triangle B = (A \cup B) \setminus (A \cap B)$

With $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$: $A \triangle B = \{1, 2, 4, 5\}$. The shared element 3 gets excluded. Unlike set difference, symmetric difference is commutative: $A \triangle B = B \triangle A$.

Cartesian product

The Cartesian product generates all possible ordered pairs from two sets.

$A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$

If $A = \{1, 2\}$ and $B = \{x, y\}$, then $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$. The result has $|A| \times |B|$ elements (here, $2 \times 2 = 4$).

This is not commutative: $(1, x) \neq (x, 1)$, so $A \times B \neq B \times A$ in general. Cartesian products are the foundation for defining relations and functions between sets.

Power set

The power set of $A$ is the set of all subsets of $A$, including $\emptyset$ and $A$ itself.

$\mathcal{P}(A) \text{ or } 2^A$

If $A = \{1, 2\}$, then $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$. That's 4 subsets.

The number of elements in a power set is always $2^n$, where $n = |A|$. So a set with 3 elements has $2^3 = 8$ subsets. This grows fast.

Properties of set operations

These properties let you rearrange and simplify set expressions, much like algebraic rules let you simplify equations.

Commutative property

You can swap the order of the sets in union and intersection:

• $A \cup B = B \cup A$
• $A \cap B = B \cap A$

This does not hold for set difference or Cartesian product.

Associative property

You can regroup sets in union and intersection without changing the result:

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

This means when you're taking the union (or intersection) of three or more sets, you don't need to worry about parentheses.

Distributive property

Union and intersection distribute over each other, similar to how multiplication distributes over addition in algebra:

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

These are extremely useful for expanding or factoring set expressions.

De Morgan's laws

De Morgan's laws tell you how complements interact with union and intersection:

• $(A \cup B)^c = A^c \cap B^c$
• $(A \cap B)^c = A^c \cup B^c$

In words: the complement of a union is the intersection of the complements, and vice versa. These come up constantly in proofs and in logic (where AND, OR, and NOT follow the same pattern).

Set identities

These identities are specific equations that always hold true. They're your go-to tools for simplifying expressions.

Identity laws

The empty set and universal set act like 0 and 1 in arithmetic:

• $A \cup \emptyset = A$ (union with nothing gives you $A$)
• $A \cap U = A$ (intersection with everything gives you $A$)

Domination laws

• $A \cup U = U$ (union with everything gives you everything)
• $A \cap \emptyset = \emptyset$ (intersection with nothing gives you nothing)

Idempotent laws

Combining a set with itself changes nothing:

• $A \cup A = A$
• $A \cap A = A$

Complement laws

• $A \cup A^c = U$ (a set and its complement together cover the whole universal set)
• $A \cap A^c = \emptyset$ (a set and its complement share no elements)
• $(A^c)^c = A$ (complementing twice gets you back to the original)

Venn diagrams

Venn diagrams are visual representations of sets using overlapping circles inside a rectangle (the universal set). They're one of the best ways to build intuition for how set operations work.

Two-set Venn diagrams

Two overlapping circles create four distinct regions:

• Only in $A$ (left part, no overlap)
• Only in $B$ (right part, no overlap)
• In both $A$ and $B$ (the overlap, representing $A \cap B$)
• In neither (the area outside both circles, representing $(A \cup B)^c$)

These are great for visualizing union, intersection, difference, and complement with two sets.

Three-set Venn diagrams

Three overlapping circles create eight distinct regions (seven inside the circles, plus the region outside all three). The central region where all three overlap represents $A \cap B \cap C$.

These get more complex but are very helpful for problems involving three sets, like inclusion-exclusion counting problems.

Interpreting Venn diagrams

• Shading indicates which region represents the result of an operation
• Numbers placed in regions represent the count of elements (cardinality) in that region
• To find the result of an operation, identify which regions should be included and combine them

When solving problems, label each region carefully before filling in values. Working from the innermost overlap outward is usually the easiest approach.

Set theory applications

Logic and set theory

Set operations map directly onto logical connectives:

• Union ($\cup$) corresponds to OR
• Intersection ($\cap$) corresponds to AND
• Complement ($^c$) corresponds to NOT

This connection means De Morgan's laws work identically in both set theory and logic. Boolean algebra, which underlies digital circuit design and programming, is built on these same operations.

Probability and set theory

In probability, events are modeled as sets and the sample space is the universal set. Set operations translate directly:

• $P(A \cup B)$ is the probability of $A$ or $B$ occurring
• $P(A \cap B)$ is the probability of both occurring
• $P(A^c) = 1 - P(A)$ uses the complement to find the probability of an event not occurring

Computer science and set theory

Database operations like JOIN and UNION are direct applications of set operations. Programming languages often have built-in set data structures that support union, intersection, and difference. Formal language theory and automata theory also rely heavily on set-theoretic foundations.

Set algebra

Algebraic manipulation of sets

You can manipulate set expressions the same way you'd simplify algebraic expressions:

1. Apply distributive laws to expand or factor
2. Use De Morgan's laws to move complements inside or outside
3. Simplify using identity, domination, and idempotent laws
4. Cancel using complement laws ($A \cap A^c = \emptyset$, etc.)

The goal is usually to reduce a complex expression to something simpler or to show that two expressions are equal.

Proving set equalities

The standard approach to proving $A = B$ is to show mutual subset inclusion:

1. Show $A \subseteq B$: pick an arbitrary element $x \in A$ and show $x \in B$
2. Show $B \subseteq A$: pick an arbitrary element $x \in B$ and show $x \in A$

If both directions hold, then $A = B$. You can also prove equalities by transforming one side into the other using known set identities, or by verifying with a Venn diagram (though diagrams alone aren't formal proofs).

Cardinality of sets

Cardinality measures the size of a set, written $|A|$. For finite sets, it's simply the number of elements. For infinite sets, things get more interesting.

Finite vs infinite sets

A finite set has a specific number of elements: $|\{a, b, c\}| = 3$. An infinite set has no bound on its size. The natural numbers $\{1, 2, 3, \ldots\}$ are the classic example of an infinite set.

Countable vs uncountable sets

• A set is countably infinite if you can list its elements in a sequence (put them in one-to-one correspondence with the natural numbers). The integers and rational numbers are both countably infinite.
• A set is uncountable if no such listing is possible. The real numbers are uncountable, which Cantor proved using his famous diagonal argument: any attempted list of real numbers will always miss at least one.

This distinction matters because it shows that not all infinities are the same size.

Comparing set sizes

Two sets have the same cardinality if there exists a bijection (a one-to-one and onto function) between them. The Cantor-Bernstein-Schroeder theorem states that if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

Cantor also showed that for any set $A$, the power set $\mathcal{P}(A)$ is strictly larger than $A$. This means there's no largest infinity. Different sizes of infinity are labeled with aleph numbers ($\aleph_0, \aleph_1, \ldots$), where $\aleph_0$ is the cardinality of the natural numbers.

Set theory paradoxes

These paradoxes exposed problems with "naive" set theory (where you can form any set you want) and led to the development of more rigorous axiomatic systems.

Russell's paradox

Consider the set $R = \{x \mid x \notin x\}$, the set of all sets that don't contain themselves. Is $R \in R$? If yes, then by definition $R \notin R$. If no, then $R$ satisfies the condition and $R \in R$. Either way, you get a contradiction.

This paradox showed that unrestricted set formation leads to inconsistency. It motivated the development of axiomatic set theory (like ZFC), which places careful restrictions on how sets can be constructed.

Cantor's paradox

If you try to form the "set of all sets," call it $S$, then Cantor's theorem says $\mathcal{P}(S)$ must be strictly larger than $S$. But $S$ is supposed to contain everything, so nothing can be larger. Contradiction.

This shows there's no universal "set of all sets." In modern set theory, such collections are called proper classes rather than sets, which avoids the paradox.