Proofs Involving Sets

Translate Set Claims into Membership

In the previous tutorial, the definitions of injectivity and surjectivity determined which elements to choose and what each proof had to establish. Set proofs follow a similar discipline: begin with an element and translate the set statement into a claim about membership. This approach is often called an element argument. It is useful because inclusion and equality are claims about which elements belong to which sets.

For example, to prove that $A$ is contained in $B$, it is not enough to compare how the sets are described informally. The definition requires showing that every element of $A$ is also an element of $B$. To prove equality, one must account for elements in both directions: nothing in $A$ lies outside $B$, and nothing in $B$ lies outside $A$.

Definition. For sets $A$ and $B$, $A\subseteq B$ means that every element of $A$ is an element of $B$: for every $x$, if $x\in A$, then $x\in B$. The sets $A$ and $B$ are equal, written $A=B$, if they have exactly the same elements: for every $x$, $x\in A$ if and only if $x\in B$.

These definitions give direct proof plans. For an inclusion, take an arbitrary $x\in A$ and prove $x\in B$. For equality, take an arbitrary $x$ and prove the equivalence $x\in A\Longleftrightarrow x\in B$. Equivalently, prove $A\subseteq B$ and $B\subseteq A$. In either direction, the element is arbitrary; a calculation for only one selected element does not establish a claim about the whole set.

Theorem (Set Equality by Double Inclusion). For any sets $A$ and $B$, $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.

Proof. Suppose $A=B$. Every element of $A$ is then an element of $B$, so $A\subseteq B$. Every element of $B$ is also an element of $A$, so $B\subseteq A$.

Conversely, suppose $A\subseteq B$ and $B\subseteq A$. Let $x$ be arbitrary. If $x\in A$, the first inclusion gives $x\in B$. If $x\in B$, the second inclusion gives $x\in A$. Thus $x\in A$ if and only if $x\in B$. Since this holds for every $x$, the sets have exactly the same elements, and $A=B$. $\square$

Worked Example: Inclusion Between Sets of Multiples

Let $A=\{6k:k\in\mathbb{Z}\}$ and $B=\{3m:m\in\mathbb{Z}\}$. We prove $A\subseteq B$. Take an arbitrary $n\in A$. By the definition of $A$, there is an integer $k$ such that $n=6k$. Since $2k\in\mathbb{Z}$, we can write

$$ n=6k=3(2k). $$

This expresses $n$ as three times an integer, so $n\in B$. Because the choice of $n\in A$ was arbitrary, $A\subseteq B$. Notice that the proof explicitly checks the condition on the witness: $2k$ is an integer, as required in the definition of $B$.

Membership in Unions, Intersections, and Complements

The element method becomes especially effective when a set is built from other sets. Membership in a union means membership in at least one of the sets; membership in an intersection means membership in every one of them. Complements require a specified universe $U$: the complement of $A\subseteq U$, written $A^c$, consists of the elements of $U$ that are not in $A$. Set difference also records nonmembership: $A\setminus B$ consists of elements in $A$ but not in $B$.

Definition. For sets $A,B\subseteq U$, $$ A\cup B=\{x:x\in A\text{ or }x\in B\},\qquad A\cap B=\{x:x\in A\text{ and }x\in B\}, $$ $$ A^c=\{x\in U:x\notin A\},\qquad A\setminus B=\{x:x\in A\text{ and }x\notin B\}. $$ Here “or” is inclusive: an element may belong to both sets.

To use these definitions in a proof, write out what it means for the arbitrary element to belong to the set under consideration. For instance, $x\in A\cap(B\cup C)$ means both $x\in A$ and at least one of $x\in B$ or $x\in C$. Keeping that logical structure visible helps avoid changing an “and” into an “or,” or losing a required condition.

Worked Example: Equality by Reindexing

Let $A=\{2k+2:k\in\mathbb{Z}\}$ and $B=\{2m:m\in\mathbb{Z}\}$. We prove $A=B$ by double inclusion. If $x\in A$, then $x=2k+2=2(k+1)$ for some $k\in\mathbb{Z}$. Since $k+1\in\mathbb{Z}$, this shows $x\in B$, so $A\subseteq B$.

For the reverse inclusion, if $x\in B$, then $x=2m$ for some $m\in\mathbb{Z}$. Since $m-1\in\mathbb{Z}$,

$$ x=2m=2(m-1)+2. $$

Thus $x\in A$, and $B\subseteq A$. The Set Equality by Double Inclusion theorem now gives $A=B$. The key is that shifting the integer parameter by $1$ or $-1$ still gives an integer; without that check, the proposed representations would not yet verify membership.

Prove Identities by Following an Arbitrary Element

A set identity is an equality that holds for every choice of the sets involved. The most dependable way to prove one is to take an arbitrary element and show that its membership in the left-hand side is equivalent to its membership in the right-hand side. The logical equivalences do the work: each step should follow from a definition or a valid rule of logic.

Theorem (De Morgan’s Laws for Sets). Let $A,B\subseteq U$. Then $$ (A\cup B)^c=A^c\cap B^c \qquad\text{and}\qquad (A\cap B)^c=A^c\cup B^c. $$

Proof. First take an arbitrary $x\in U$. By the definitions of complement and union,

x\in(A\cup B)^c \Longleftrightarrow x\notin A\cup B \Longleftrightarrow (x\notin A\text{ and }x\notin B) \Longleftrightarrow x\in A^c\cap B^c.

Thus every element of $U$ belongs to the first set exactly when it belongs to the second, proving $(A\cup B)^c=A^c\cap B^c$.

For the other identity, again take an arbitrary $x\in U$. Then

x\in(A\cap B)^c \Longleftrightarrow x\notin A\cap B \Longleftrightarrow (x\notin A\text{ or }x\notin B) \Longleftrightarrow x\in A^c\cup B^c.

The middle equivalence uses the logical fact that it is not true that both conditions hold exactly when at least one of them fails. Therefore the second identity holds as well. $\square$

Worked Example: Checking De Morgan’s Law in a Finite Universe

Let $U=\{1,2,3,4,5,6,7,8\}$, $A=\{2,4,6,8\}$, and $B=\{1,2,3,4\}$. The elements of $U$ in neither $A$ nor $B$ are $5$ and $7$, so

(A\cup B)^c=\{5,7\}.

Also, $A^c=\{1,3,5,7\}$ and $B^c=\{5,6,7,8\}$. Their intersection is $\{5,7\}$, so $A^c\cap B^c=\{5,7\}=(A\cup B)^c$. The calculation illustrates the first De Morgan law: being outside the union means being outside both sets. This finite check illustrates the theorem but does not replace its proof for arbitrary sets.

Theorem (Distributive Law for Sets). For any sets $A,B,C$, $$ A\cap(B\cup C)=(A\cap B)\cup(A\cap C). $$

Proof. Let $x$ be arbitrary. Expanding membership in the left-hand side gives

x\in A\cap(B\cup C) \Longleftrightarrow \bigl(x\in A\text{ and }(x\in B\text{ or }x\in C)\bigr).

The distributive law of logic says that this condition is equivalent to $(x\in A\text{ and }x\in B)$ or $(x\in A\text{ and }x\in C)$. By the definitions of intersection and union, that is equivalent to

x\in(A\cap B)\cup(A\cap C).

We have proved that an arbitrary $x$ belongs to one side exactly when it belongs to the other. Hence the two sets are equal. $\square$

Keep the Universe and Both Directions in View

A complement is always relative to its universe. If $A\subseteq U$, then $A^c$ contains elements of $U$, not every object that might exist outside the stated universe. Changing $U$ can change $A^c$, even when $A$ itself is unchanged. In the De Morgan proof, the assumption $x\in U$ matters: it ensures that the membership statements for complements are being considered in their specified universe.

Another common error is to prove only one inclusion and announce equality. Showing $A\subseteq B$ establishes that $A$ has no elements outside $B$, but it does not rule out additional elements of $B$. For example, $\{1\}\subseteq\{1,2\}$, but these sets are not equal because $2$ belongs only to the second set. For equality, either prove both inclusions or establish the membership equivalence for an arbitrary element.

For an inclusion.
Take an arbitrary element of the proposed smaller set. Unpack its membership definition and prove that it belongs to the other set.

For equality.
Prove inclusion in both directions, or show that an arbitrary element belongs to the first set if and only if it belongs to the second.

For an identity involving set operations.
Translate membership into “and,” “or,” and “not.” Justify each change by the definitions and a valid logical equivalence.

For complements.
State the universe and keep each element under consideration inside that universe.

Key takeaway. Set proofs work by tracking arbitrary elements. Inclusion asks whether every element of one set belongs to another; equality requires agreement in both directions. Union, intersection, and complement turn set membership into logical operations, allowing identities such as De Morgan’s laws to be proved directly.

Check Your Understanding

Use the definitions and proof strategies in this tutorial to answer the following questions.

What must you assume and conclude when proving $A\subseteq B$ directly?
Why does proving $A\subseteq B$ alone not establish $A=B$?
In the proof of $(A\cup B)^c=A^c\cap B^c$, which logical condition corresponds to being outside both $A$ and $B$?
Why must the universe be specified when defining a complement?
How can you prove a set identity without proving two inclusions as separate arguments?

What You'll Learn