Real examples of proofs involving sets: step‑by‑step guide

When students ask for the best examples of proofs involving sets, I usually start with problems that force you to use the definitions directly. That’s how you build real proof muscle: by unpacking what each symbol actually means in plain language.

Below, you’ll see several real examples of proofs involving sets that highlight different strategies:

• direct proof using element-chasing ("pick an arbitrary element and follow it"),
• proof of set equality via double inclusion,
• proof by counterexample,
• and a taste of induction with sets.

Each example of a set proof is written in a style that would look natural on a homework solution or exam.

Example of proving a subset relation using definitions

Claim: For any sets \(A, B, C\), if \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\).

This is one of the simplest but best examples of how to organize a direct proof.

Proof:
Take an arbitrary element \(x\) in \(A\). Because \(A \subseteq B\), every element of \(A\) is in \(B\), so \(x \in B\). Because \(B \subseteq C\), every element of \(B\) is in \(C\), so \(x \in C\).

So we started with an arbitrary element of \(A\) and showed it must lie in \(C\). Therefore, every element of \(A\) is in \(C\), which is exactly the definition of \(A \subseteq C\). ◻

This is a clean, real example of a direct proof: no tricks, just definitions.

Classic examples of proofs involving sets: union and intersection

Example 1: Distributive law for sets

Claim: For any sets \(A, B, C\),
[
A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
]

This is one of the best examples of examples of proofs involving sets that show how to prove a set equality: you prove two subset relations.

Step 1: Show \(A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)\)

Take an arbitrary element \(x\) in \(A \cap (B \cup C)\). By definition of intersection, \(x \in A\) and \(x \in B \cup C\). The second part means: \(x \in B\) or \(x \in C\).

• If \(x \in B\), then \(x \in A\) and \(x \in B\), so \(x \in A \cap B\).
• If \(x \in C\), then \(x \in A\) and \(x \in C\), so \(x \in A \cap C\).

In either case, \(x\) belongs to \((A \cap B) \cup (A \cap C)\). That proves the first inclusion.

Step 2: Show \((A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)\)

Now take \(x\) in \((A \cap B) \cup (A \cap C)\). So \(x\) is in at least one of those intersections.

• If \(x \in A \cap B\), then \(x \in A\) and \(x \in B\).
• If \(x \in A \cap C\), then \(x \in A\) and \(x \in C\).

In both cases, \(x \in A\). And in both cases, \(x\) is in either \(B\) or \(C\), so \(x \in B \cup C\).

Thus \(x \in A\) and \(x \in B \cup C\), so \(x \in A \cap (B \cup C)\).

We’ve proved both inclusions, so the sets are equal. This is a textbook example of how to prove a set identity.

Example 2: De Morgan’s law for complements

Another favorite among real examples of proofs involving sets is De Morgan’s law.

Claim: For a universal set \(U\) and subsets \(A, B \subseteq U\),
[
(A \cup B)^c = A^c \cap B^c.
]

Again, we use double inclusion.

First inclusion: \((A \cup B)^c \subseteq A^c \cap B^c\)

Let \(x \in (A \cup B)^c\). By definition of complement, \(x \notin A \cup B\). That means \(x \notin A\) and \(x \notin B\). So \(x \in A^c\) and \(x \in B^c\), hence \(x \in A^c \cap B^c\).

Second inclusion: \(A^c \cap B^c \subseteq (A \cup B)^c\)

Let \(x \in A^c \cap B^c\). Then \(x \in A^c\) and \(x \in B^c\), so \(x \notin A\) and \(x \notin B\). Therefore, \(x \notin A \cup B\), which means \(x \in (A \cup B)^c\).

This example of a proof shows how simple logical negations translate directly to set complements. If you’re also studying logic, check out how De Morgan’s laws are presented for propositions in discrete math texts, for instance in the open materials linked from many U.S. universities such as MIT OpenCourseWare.

Examples include counterexamples: when a statement about sets is false

Not every statement about sets is true, and some of the best examples of learning proofs involving sets come from disproving a claim.

Example 3: Counterexample with union and intersection

Consider the statement:
[
A \cap (B \cup C) = (A \cap B) \cup C.
]

Is this always true? No. We can show it’s false by giving a counterexample.

Take

• \(A = {1}\),
• \(B = {1}\),
• \(C = {2}\).

Compute each side:

Left side:

• \(B \cup C = {1, 2}\),
• \(A \cap (B \cup C) = {1} \cap {1, 2} = {1}.\)

Right side:

• \(A \cap B = {1} \cap {1} = {1}\),
• \((A \cap B) \cup C = {1} \cup {2} = {1, 2}.\)

So the left side is \({1}\) and the right side is \({1, 2}\). They are not equal, so the statement is false.

This is a clear example of how examples include counterexamples: a single specific construction can kill a supposed identity.

Real examples of proofs involving sets in functions and images

Set proofs show up constantly in modern math and computer science, especially in reasoning about functions, databases, and algorithms.

Example 4: Image of a union under a function

Let \(f : X \to Y\) be a function and \(A, B \subseteq X\). Define the image
[
f(A) = {f(x) : x \in A}.
]

Claim: \(f(A \cup B) = f(A) \cup f(B)\).

This is one of the best examples of proofs involving sets that connects directly to programming and data.

Proof:

Take \(y \in f(A \cup B)\). Then there exists \(x \in A \cup B\) with \(f(x) = y\). So \(x \in A\) or \(x \in B\).

• If \(x \in A\), then \(y = f(x) \in f(A)\).
• If \(x \in B\), then \(y = f(x) \in f(B)\).

So \(y \in f(A) \cup f(B)\). This shows \(f(A \cup B) \subseteq f(A) \cup f(B)\).

For the other inclusion, take \(y \in f(A) \cup f(B)\). Then either \(y \in f(A)\) or \(y \in f(B)\).

• If \(y \in f(A)\), then there exists \(x \in A\) with \(f(x) = y\). Since \(A \subseteq A \cup B\), we get \(x \in A \cup B\), so \(y \in f(A \cup B)\).
• The case \(y \in f(B)\) is similar.

Thus \(f(A) \cup f(B) \subseteq f(A \cup B)\), giving equality.

In computer science terms, this is saying: if you apply a function to the union of two datasets, you get the union of the outputs you would get by applying the function to each dataset separately.

Examples of proofs involving sets and probability

Modern data science, statistics, and epidemiology all rely on set reasoning. Probability theory literally starts by defining events as subsets of a sample space. If you browse introductory probability notes from universities like Harvard or UCLA, you’ll see the same identities we’re proving here.

Example 5: Inclusion–exclusion for two sets

Let \(A\) and \(B\) be subsets of a finite sample space with a probability measure \(P\).

Claim:
[
P(A \cup B) = P(A) + P(B) - P(A \cap B).
]

A clean way to motivate this formula is with a set-based argument.

Proof idea using sets:

The elements of \(A \cup B\) can be split into two disjoint groups:

• elements in \(A\) but not in \(B\), and
• elements in \(B\) (including those also in \(A\)).

If we simply added \(P(A) + P(B)\), we would count the overlap \(A \cap B\) twice. So we subtract \(P(A \cap B)\) once to fix that double-counting.

Formally, we can use the disjoint union representation:
[
A \cup B = (A \setminus B) \cup B,
]
where \((A \setminus B)\) and \(B\) are disjoint. Then
[
P(A \cup B) = P(A \setminus B) + P(B).
]
But \(A = (A \setminus B) \cup (A \cap B)\) with disjoint union, so
[
P(A) = P(A \setminus B) + P(A \cap B),
]
which rearranges to
[
P(A \setminus B) = P(A) - P(A \cap B).
]
Substitute this back into the first equation to get the inclusion–exclusion formula.

This is a powerful real example of how set identities guide quantitative reasoning.

Example of proof by induction with sets

Induction isn’t just for integers. Some of the best examples of examples of proofs involving sets use induction on the size of a finite set.

Example 6: Size of a power set

For a finite set \(A\), its power set \(\mathcal{P}(A)\) is the set of all subsets of \(A\).

Claim: If \(|A| = n\), then \(|\mathcal{P}(A)| = 2^n\).

Proof by induction on \(n\):

Base case: If \(n = 0\), then \(A = \emptyset\). The only subset of the empty set is \(\emptyset\) itself, so \(|\mathcal{P}(A)| = 1 = 2^0\). Base case holds.

Inductive step: Assume that every set with \(n\) elements has a power set of size \(2^n\). Let \(A\) be a set with \(n+1\) elements. Pick one element and call it \(a\). Let \(B = A \setminus {a}\), so \(|B| = n\).

Every subset of \(A\) either contains \(a\) or does not contain \(a\):

• Subsets of \(A\) that do not contain \(a\) are exactly the subsets of \(B\). There are \(2^n\) of these by the inductive hypothesis.
• Subsets of \(A\) that do contain \(a\) are obtained by taking a subset of \(B\) and then adding \(a\). There are also \(2^n\) of these.

So in total, \(|\mathcal{P}(A)| = 2^n + 2^n = 2^{n+1}\). That completes the induction.

This is a classic example of a proof involving sets that also trains your proof-by-induction skills.

Modern applications: where these examples show up in 2024–2025

If you look at current syllabi for discrete mathematics, data structures, or introductory statistics in 2024–2025, you’ll see that these examples of proofs involving sets are not just theoretical exercises. They sit at the core of:

• Database query languages (like SQL), where AND, OR, and NOT correspond to intersection, union, and complement.
• Information retrieval and search: combining search filters is literally combining sets of documents.
• Epidemiology and public health: events like “tested positive” or “has symptom X” are modeled as sets; organizations like the CDC routinely explain risk in terms of overlapping groups.
• Machine learning: training, validation, and test sets are disjoint subsets of a larger dataset; reasoning about leakage or overlap uses the same set identities.

In other words, the real examples of proofs involving sets you practice now are the same logic people use professionally in 2024 and 2025 when they argue about data, risk, and algorithms.

FAQ: short examples of common questions about set proofs

Q1. Can you give a quick example of proving two sets are equal?
Yes. One of the best examples is the distributive law:
[
A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
]
You prove it by showing each side is a subset of the other, using element-chasing. This pattern—prove both inclusions—is the standard method for any equality of sets.

Q2. What are typical examples of statements about sets that are false?
Statements like \(A \cap (B \cup C) = (A \cap B) \cup C\) or \(f(A \cap B) = f(A) \cap f(B)\) (for arbitrary \(f\)) are not always true. You disprove them using a counterexample: pick specific sets where the left and right sides differ.

Q3. How do real examples of proofs involving sets help with logic?
Every time you unpack a definition like \(x \in A \cup B\) into “\(x \in A\) or \(x \in B\),” you’re practicing propositional logic. De Morgan’s laws for sets match De Morgan’s laws for logical statements exactly, so examples of set proofs double as logic practice.

Q4. Are these examples of proofs involving sets relevant outside pure math?
Definitely. Probability, statistics, and computer science all use the same identities. For instance, the inclusion–exclusion principle in probability is just a weighted version of a union identity for sets, and it appears in many introductory probability courses hosted by major universities.

Q5. Where can I find more worked examples of set proofs?
Look at open course notes from U.S. and international universities. For instance, many discrete math and probability courses on MIT OpenCourseWare, Harvard’s statistics resources, and similar .edu sites provide problem sets with fully worked solutions that include dozens of examples of proofs involving sets.