Sets and Set Operations

In this post, we’ll build the basic vocabulary the rest of this course uses: sets. We’ll start with the number line and the plane, then define sets and distinguish between countable and uncountable sets. Next, we’ll work through the main set operations (union, intersection, complement, and difference), prove De Morgan’s laws with a technique we’ll use again and again, and finish with the Cartesian product, the operation that builds a plane out of two number lines.

Sets and Set Operations

Why Start With Sets?

Automata theory is about machines and the problems they can solve, so why begin with sets? Because every idea in this course is described using them:

• A machine’s states form a set, usually called Q.
• The symbols a machine can read form a set called the alphabet, written Σ.
• A language, which is how we describe a problem, is a set of strings.
• Showing that two machines solve the same problem comes down to showing that two sets are equal.

A solid grip on sets now makes everything later much easier.

The Real Line

The real line is the number line you have used since school. Zero sits in the middle, positive numbers go off to the right toward +∞, and negative numbers go off to the left toward −∞.

Several kinds of numbers live on this line:

• Positive integers: 1, 2, 3, …
• Negative integers: −1, −2, −3, …
• Whole numbers: 0 together with the positive integers: 0, 1, 2, 3, …
• Rational numbers: numbers that can be written as a fraction p/q with q ≠ 0, such as 1/2 = 0.5. Repeating decimals are rational too: 0.555… = 5/9.
• Irrational numbers: numbers that can’t be written as a fraction, such as √2 ≈ 1.41421… and π ≈ 3.14159…. Their decimals go on forever without repeating.

All of these are real numbers, and together they fill the line with no gaps.

The real line has one very useful property. For any two real numbers x and y, exactly one of these is true:

x < y      x > y      x = y

The real line. Integers (blue), rational numbers such as −3/2 and 1/2 (green), and irrational numbers such as √2 and π (orange) all sit on the same line. The whole numbers start at 0 and go right, the negative integers go left, and together all real numbers fill the line with no gaps.

The Plane

Put two real lines at right angles, and you get the plane, also called the Cartesian plane or the xy-plane. Every point on it is described by a pair (x, y).

On the plane, we can still say when two points are equal:

(x, y) = (u, v)   if and only if   x = u and y = v

But there’s no natural way to say one point is “less than” another. Is (1, 5) smaller than (3, 2)? There’s no obvious answer. So the plane keeps equality but loses the ordering that the real line had.

The two axes don’t have to be ordinary number lines. In the complex plane, the horizontal axis holds real numbers (counting in steps of 1), and the vertical axis holds imaginary numbers (counting in steps of i, where i = √−1). In signal processing, these are the familiar I and Q axes. It looks like a plane, but it’s built from two different kinds of lines.

That raises a question: is there one general way to describe how two lines “combine” into a plane? There is, and it’s built from sets. We’ll get there at the end of this post.

What Is a Set?

A set is a collection of distinct elements. We write a set with curly braces and separate the elements with commas:

Fruits = {apple, orange, banana}
ℕ      = {1, 2, 3, 4, ...}

ℕ is the set of natural numbers.

Two rules to remember:

• No duplicates: each element counts once. {1, 1, 2} is the same set as {1, 2}.
• Order doesn’t matter: {1, 2, 3} and {3, 1, 2} are the same set.

The elements don’t need to share any property; any collection of distinct things is a set.

Some notation we’ll use constantly:

• x ∈ A means x is an element of A.
• x ∉ A means x is not an element of A.
• ∅ (or {}) is the empty set, the set with no elements at all.
• {x | condition} is set-builder notation, read as “the set of all x such that the condition holds.” For example, {x | x ∈ ℕ and x < 4} = {1, 2, 3}.

Finite, Infinite, Countable, Uncountable

Finite vs. infinite. A set is finite if it has a limited number of elements; Fruits has 3. A set like ℕ, which never runs out of elements, is infinite.

Countable. Intuitively, a set is countable if you can line up its elements and give each one a position: first, second, third, and so on, so that every element eventually gets a spot.

• Every finite set is countable: just count the elements.
• ℕ is infinite, but still countable: 1 is first, 2 is second, 3 is third, and so on. You’ll never finish counting, but every number gets a position. This makes ℕ the most basic example of a countably infinite set.

ℕ is also discrete. There are no natural numbers between 1 and 2, so given any element, you know exactly which one comes next. If you drew ℕ, you’d draw separate dots.

Uncountable. The set of all real numbers, ℝ, is also infinite, but it is uncountable: no list, not even an infinitely long one, contains every real number.

ℝ is also continuous: you can draw it without lifting your pencil. Between any two different real numbers there is always another one (their average, for example). So there is no “next” real number after 0. Is it 0.0001? Or 0.000…01 with ten thousand zeros? Whatever you pick, there’s a smaller positive number.

A careful note: “there’s no next number” is good intuition, but it is not the reason ℝ is uncountable. The rational numbers also have no “next” element (between any two fractions there is always another fraction), yet the rationals are countable. The real proof that ℝ is uncountable is Cantor’s diagonal argument, which we’ll meet later in the course.

So ℝ is the basic example of an uncountably infinite set. In a later post, we’ll make “countable” precise: a set is countable when its elements can be paired up one-to-one with the natural numbers.

Discrete vs. continuous. The natural numbers ℕ are separate dots: every element has a clear next one, so we can count them as first, second, third, and so on. The real numbers ℝ form a solid line: zoom in as far as you like and there are still no gaps and no “next” number. ℕ is countably infinite, while ℝ is uncountably infinite.

Subsets and Set Equality

A is a subset of B if every element of A is also an element of B.

S = {5, 7, 9, 12, 15}
A = {7, 9, 12}

A ⊆ S

There are two symbols for this, and the difference matters:

• A ⊆ B: A is a subset of B, and A might even be equal to B. Think of it like ≤.
• A ⊂ B: A is a proper subset of B. Every element of A is in B, but B has at least one element that A doesn’t. Think of it like <. Some books write ⊊ to make this extra clear.

A few facts that follow directly from the definition:

• Every set is a subset of itself: S ⊆ S. But S is never a proper subset of itself.
• The empty set is a subset of every set, since it has no elements that could break the rule.
• If A ⊆ B, we also say that B is a superset of A.

Set equality. Two sets are equal when they contain exactly the same elements. Here’s a precise way to say it that we’ll lean on heavily:

A = B   if and only if   A ⊆ B and B ⊆ A

A subset. Every element of A = {7, 9, 12} is also in S = {5, 7, 9, 12, 15}, so A ⊆ S. Since S also has elements that A doesn’t (5 and 15), A is a proper subset too: A ⊂ S. Equivalently, S is a superset of A.

Intervals

An interval is a continuous piece of the real line.

• Closed interval [1, 2]: every real number from 1 to 2, including the endpoints 1 and 2.
• Open interval (1, 2): every real number strictly between 1 and 2, excluding the endpoints.

[1, 2] = {x ∈ ℝ | 1 ≤ x ≤ 2}
(1, 2) = {x ∈ ℝ | 1 < x < 2}

The whole real line is the interval (−∞, ∞). Its ends are always open because ∞ is not a real number, so it can’t be included.

Closed vs. open intervals. A filled dot means the endpoint is included, and a hollow dot means it is left out. The closed interval [1, 2] contains 1 and 2, while the open interval (1, 2) contains every number between them but not the endpoints themselves.

A Surprising Fact: The Part Can Be as Big as the Whole

Clearly, (1, 2) ⊆ ℝ. But ℝ is not a subset of (1, 2), since a number like 5 is in ℝ but not in (1, 2). So, as sets, they are not equal.

Now ask a different question: do they have the same number of elements? Surprisingly, yes. We can pair up every number in (1, 2) with exactly one real number, and every real number with exactly one number in (1, 2), with nothing left over on either side. Here is one such pairing:

f(x) = tan(π(x − 3/2))

As x moves from 1 to 2, the expression π(x − 3/2) moves from −π/2 to π/2, and the tangent function stretches that short stretch across the entire real line, from −∞ to +∞. The midpoint x = 1.5 lands on 0.

So a tiny piece of the line holds just as many points as the whole line. (The same is true for the closed interval [1, 2]; the pairing is just messier to write down.)

This idea of comparing infinite sets by pairing elements instead of counting them comes from Georg Cantor. It’s so elegant that the mathematician Paul Erdős, who liked to say that God keeps a book of the most beautiful proof of every theorem, would have counted it among them. A real book inspired by that idea, Proofs from THE BOOK by Martin Aigner and Günter Ziegler, includes Cantor’s ideas about infinite sets.

We’ll use exactly this kind of pairing argument near the end of the course to show that some problems can’t be solved by any computer.

The part is as big as the whole. The function f(x) = tan(π(x − 3/2)) takes the short open interval (1, 2) on the horizontal axis and stretches it over the entire real line on the vertical axis: 1.25 pairs with −1, 1.5 pairs with 0, and 1.75 pairs with 1. Near 1 the curve plunges toward −∞, and near 2 it climbs toward +∞. Every number in (1, 2) pairs with exactly one real number and every real number is used exactly once, so the two sets have the same size.

Set Operations

For the first two operations, let’s use these sets:

A = {1, 2, 3}
B = {3, 4, 5}

Union

The union A ∪ B contains everything that is in A, in B, or in both. Elements in both sets still appear only once.

A ∪ B = {1, 2, 3, 4, 5}

A ∪ B = {x | x ∈ A or x ∈ B}

In math, “or” always means “one, the other, or both.” That’s why we don’t need to write “or both” separately. The logic symbol for “or” is ∨, so you’ll also see this written as {x | x ∈ A ∨ x ∈ B}.

Intersection

The intersection A ∩ B contains only the elements that are in both sets.

A ∩ B = {3}

A ∩ B = {x | x ∈ A and x ∈ B}

The logic symbol for “and” is ∧.

Complement

The complement needs a universal set S (also called the support set): the set of everything we’re currently talking about. The complement of A is everything in S that is not in A.

S  = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A  = {2, 3, 4}
Aᶜ = {1, 5, 6, 7, 8, 9, 10}

Aᶜ = {x | x ∈ S and x ∉ A}

Other books write the complement as A′ or Ā. Any of these is fine, but pick one and stay consistent.

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Without a universal set, a complement means nothing. “Everything that isn’t in {2, 3, 4}” raises the question: everything out of what? In practice, the universal set is usually clear from context (ℕ or ℝ, for example), so we often don’t write it.

Two facts always hold:

• A ∪ Aᶜ = S (together, A and its complement make up everything)
• A ∩ Aᶜ = ∅ (nothing is in both A and its complement)

Difference

The difference B − A (also written B \ A) contains the elements that are in B but not in A.

B = {2, 3, 4, 5, 6}
A = {2, 3, 4}

B − A = {5, 6}
B − A = {x | x ∈ B and x ∉ A}

A does not have to be a subset of B. If A = {1, 7, 8}, then none of A’s elements are in B, so there’s nothing to remove, and B − A = B.

The complement is really just a special case of the difference: Aᶜ = S − A.

The four basic set operations, with the result shaded. The rectangle is the universal set S. Union keeps everything in A or B, intersection keeps only the overlap, the complement of A keeps everything in S outside A, and the difference B − A keeps the part of B that is not in A.

Proving Two Sets Are Equal

A Venn diagram can make a fact look obvious, but a picture isn’t a proof. The standard way to prove that two sets are equal is called double containment. To show S₁ = S₂:

1. Show S₁ ⊆ S₂: take an arbitrary element x ∈ S₁ and show that x ∈ S₂.
2. Show S₂ ⊆ S₁: take an arbitrary element y ∈ S₂ and show that y ∈ S₁.

Together, these two steps prove S₁ = S₂.

The word “arbitrary” matters. We don’t pick a specific element; the argument has to work for any element, because we often don’t even know what the sets contain.

You’ll see this technique all over automata theory. For example, to show that a machine accepts exactly the strings of some language, you show that every string the machine accepts is in the language, and every string in the language is accepted by the machine.

Warm-up: A ∪ Aᶜ = S

This one looks obvious, and that’s exactly why it’s good practice. The more obvious a fact seems, the harder it can feel to prove, so the trick is to unpack the definitions one step at a time.

Step 1: A ∪ Aᶜ ⊆ S

• Let x ∈ A ∪ Aᶜ.
• By the definition of union, x ∈ A or x ∈ Aᶜ.
• Both A and Aᶜ are subsets of S, so either way, x ∈ S.

Step 2: S ⊆ A ∪ Aᶜ

• Let y ∈ S.
• Either y ∈ A, or y ∉ A. If y ∉ A, then y ∈ Aᶜ by the definition of complement.
• Either way, y ∈ A ∪ Aᶜ.

Both containments hold, so A ∪ Aᶜ = S.

De Morgan’s Laws

De Morgan’s laws tell us how to take the complement of a union or an intersection:

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

In plain words:

• “Not in (A or B)” is the same as “not in A and not in B.”
• “Not in (A and B)” is the same as “not in A or not in B.”

Notice the pattern: taking the complement flips ∪ into ∩, and ∩ into ∪.

De Morgan’s first law, (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ. Top row: shade A ∪ B, then take its complement, which leaves only the region outside both circles. Bottom row: Aᶜ is everything outside A, Bᶜ is everything outside B, and the region in both of them is again the area outside both circles. Both sides give exactly the same region.

Proof of the First Law: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

Everything here lives inside a universal set S, so for any element of S, “x ∉ A” means the same thing as “x ∈ Aᶜ.”

Step 1: (A ∪ B)ᶜ ⊆ Aᶜ ∩ Bᶜ

• Let x ∈ (A ∪ B)ᶜ.
• Then x ∉ A ∪ B.
• A ∪ B contains everything that is in A or in B. Since x isn’t in it, x is in neither: x ∉ A and x ∉ B.
• So x ∈ Aᶜ and x ∈ Bᶜ.
• Therefore, x ∈ Aᶜ ∩ Bᶜ.

Step 2: Aᶜ ∩ Bᶜ ⊆ (A ∪ B)ᶜ

• Let y ∈ Aᶜ ∩ Bᶜ.
• Then y ∈ Aᶜ and y ∈ Bᶜ, which means y ∉ A and y ∉ B.
• Since y is in neither A nor B, it can’t be in A ∪ B.
• Therefore, y ∈ (A ∪ B)ᶜ.

Both containments hold, so (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.

Proof of the Second Law: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Try this one yourself first; it follows the same pattern.

Step 1: (A ∩ B)ᶜ ⊆ Aᶜ ∪ Bᶜ

• Let x ∈ (A ∩ B)ᶜ, so x ∉ A ∩ B.
• That means x is not in both sets, so x ∉ A or x ∉ B.
• So x ∈ Aᶜ or x ∈ Bᶜ, which means x ∈ Aᶜ ∪ Bᶜ.

Step 2: Aᶜ ∪ Bᶜ ⊆ (A ∩ B)ᶜ

• Let y ∈ Aᶜ ∪ Bᶜ, so y ∉ A or y ∉ B.
• Either way, y can’t be in both A and B, so y ∉ A ∩ B.
• Therefore, y ∈ (A ∩ B)ᶜ.

Both containments hold, so (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

The Cartesian Product

The Cartesian product is named after René Descartes, the French mathematician and philosopher credited with joining algebra and geometry. He described points using coordinates, which made it possible to write shapes as equations: the line y = 2x + 1, or the circle x² + y² = 1. Before that, algebra and geometry were treated as largely separate subjects.

The Cartesian product A × B is the set of all ordered pairs (a, b), where the first element comes from A and the second comes from B.

A = {1, 2, 3}
B = {3, 4}

A × B = {(1,3), (1,4), (2,3), (2,4), (3,3), (3,4)}
A × B = {(x, y) | x ∈ A and y ∈ B}

To build it, take each element of A and pair it with every element of B.

A few things to notice:

• Size: if |A| means the number of elements in A, then |A × B| = |A| · |B|. Here, 3 × 2 = 6 pairs.
• Order inside a pair matters: (1, 3) and (3, 1) are different pairs. So in general, A × B ≠ B × A. For example, (4, 1) is in B × A but not in A × B.
• The elements are pairs: the members of A × B are pairs like (2, 4), not single numbers.

The Plane, Revisited

Now we can answer the question from the start of this post. The plane is simply the Cartesian product of the real line with itself:

ℝ² = ℝ × ℝ = {(x, y) | x ∈ ℝ and y ∈ ℝ}

Every point (x, y) on the plane is one ordered pair from ℝ × ℝ. That’s the general way two lines “combine” into a plane.

The idea extends to more sets. A × B × C is the set of all triples (x, y, z) with x ∈ A, y ∈ B, and z ∈ C, so three-dimensional space is ℝ³ = ℝ × ℝ × ℝ, and higher dimensions follow the same pattern.

The Cartesian product shows up again almost immediately. In the next post, a relation is defined as a subset of a Cartesian product, and later, a machine’s transition function takes its input from Q × Σ: a (state, symbol) pair.

Left: the Cartesian product A × B for A = {1, 2, 3} and B = {3, 4}. Each dot is one ordered pair, with the first element from A and the second from B, for 3 × 2 = 6 pairs in total. Right: the plane is the same idea applied to two copies of the real line, so every point, such as (2, 1.5), is one ordered pair in ℝ × ℝ.

Quick Reference

x ∈ A      x is an element of A
x ∉ A      x is not an element of A
∅          the empty set
A ⊆ B      A is a subset of B (may be equal)
A ⊂ B      A is a proper subset of B
A = B      A ⊆ B and B ⊆ A
A ∪ B      {x | x ∈ A or x ∈ B}
A ∩ B      {x | x ∈ A and x ∈ B}
Aᶜ         {x | x ∈ S and x ∉ A}
B − A      {x | x ∈ B and x ∉ A}
A × B      {(x, y) | x ∈ A and y ∈ B}
[a, b]     {x ∈ ℝ | a ≤ x ≤ b}   closed interval
(a, b)     {x ∈ ℝ | a < x < b}   open interval

🔙 Back to all notes
𝕏 Let’s Connect

Backlinks:
Formal Languages and Automata Theory: What Computers Can and Cannot Do