Proving Properties of Sets
Three different ways to prove a statement about sets, when to reach for each, and the set identities the third one runs on. See sets-and-set-notation for the definitions being manipulated and proof-techniques for the general proof shapes underneath.
Three methods
| Method | Useful for | How it works |
|---|---|---|
| Element method | a variety of results about sets | argue about an arbitrary element |
| Laws of logical equivalence | proving two sets are equal | rewrite membership as a logical statement and transform it |
| Set identities | proving two sets are equal | rewrite the set expression itself, citing named identities |
The element method is the general-purpose one — it is the only one of the three whose stated forms reach a containment (\(\subseteq\), \(\subset\)) rather than an equality; the other two are given only for proving that two sets are equal. Those other two are quicker, and the choice between them is yours.
Figure 1: Which method can reach which goal. A containment has only one route open to it; an equality has three, and the two braced as quicker do it in a single chain rather than two separate containment proofs.
The element method
To prove \(S \subseteq T\), consider an arbitrary element \(x \in S\) and show that \(x \in T\).
To prove \(S \subset T\), prove \(S \subseteq T\) and then prove \(\exists\, t \in T\) such that \(t \notin S\).
To prove \(S = T\), prove \(S \subseteq T\) and also prove \(T \subseteq S\).
There is a fourth shape worth naming separately, since it is the one that does not mention two sets at all:
To prove that all elements of a set \(S\) have property \(P\), suppose \(x \in S\) and then prove that \(x\) has property \(P\).
Worked: a containment that is proper
Let \(S = \{x \in \mathbb{Z} \mid x \equiv 2 \;(\mathrm{mod}\; 3)\}\) and \(T = \{x \in \mathbb{Z} \mid x \equiv 5 \;(\mathrm{mod}\; 6)\}\). Prove \(T \subset S\).
Listing a few elements first is a good habit — it tells you which way the containment can possibly go:
\[S = \{\dots, -7, -4, -1, 2, 5, 8, 11, \dots\} \qquad T = \{\dots, -7, -1, 5, 11, \dots\}\]
\(T\) is visibly the sparser set, so \(T \subset S\) is the direction to attempt. The proof has the two parts the definition of \(\subset\) demands:
Proof.
(i) \(T \subseteq S\). Suppose \(t \in T\). Then \(t = 6k + 5\) for some integer \(k\). Thus \[t = 6k + 5 = 3(2k + 1) + 2\] and since \(2k + 1 \in \mathbb{Z}\), we have \(t \equiv 2 \;(\mathrm{mod}\; 3)\), so \(t \in S\). Therefore \(T \subseteq S\).
(ii) The containment is proper. \(2 \in S\) but \(2 \notin T\). Therefore \(T \subset S\). \(\blacksquare\)
Part (i) is a general argument about an arbitrary \(t\); part (ii) is a single exhibited witness. Getting those two registers the right way round is most of the skill — a general claim needs a general argument, a “there exists” needs one example.
Worked: complementation reverses containment
Prove that for all sets \(A\) and \(B\) in some universe \(U\), if \(A \subseteq B\) then \(B^{c} \subseteq A^{c}\).
Proof. Let \(x \in B^{c}\). Then \(x \in U - B\) by definition of complement, and thus \(x \in U\) and \(x \notin B\) by definition of set difference.
Since \(A \subseteq B\) we have: every element in \(A\) is also an element of \(B\). Taking the contrapositive, \[x \notin B \;\Longrightarrow\; x \notin A\] Since \(x \in U\) and \(x \notin A\), by definition of complement \(x \in A^{c}\). Therefore \(B^{c} \subseteq A^{c}\). \(\blacksquare\)
Figure 2: Complementation reverses containment. The smaller set has the larger complement — everything outside B is also outside A, because A was inside B to begin with. The shaded region on the right contains the shaded region on the left.
A picture is not a proof
For all sets \(A\), \(B\), \(C\): \(\;(A - B) \cap (B - A) = \emptyset\). True.
Figure 3: The sets A and B, then A − B shaded, then B − A shaded. The two shaded regions are visibly disjoint, which makes the result believable and is exactly what a proof may not rest on.
The diagrams make the claim obvious, and they are still not a proof. That is a point worth dwelling on, because Venn diagrams are so persuasive:
- A diagram shows one configuration of the sets. The claim is about all sets \(A\), \(B\), \(C\) — including cases the picture does not draw, such as \(A = B\), or either set empty, or one contained in the other.
- The regions in a Venn diagram are drawn as non-empty; the statement has to hold when they are not.
The proof is short and needs no picture: suppose \(x \in (A-B) \cap (B-A)\). Then \(x \in A - B\), so \(x \in A\) and \(x \notin B\); and \(x \in B - A\), so \(x \in B\) and \(x \notin A\). Then \(x \in B\) and \(x \notin B\), a contradiction. So no such \(x\) exists and the intersection is empty. \(\blacksquare\)
Use diagrams to find the answer and to check your intuition. Write the element argument to justify it.
The laws of logical equivalence method
The idea: “\(x \in S\)” is a logical statement, so the laws of logical-equivalence-laws apply to it directly. Write out what membership of \(S\) means, transform it, and read off membership of \(T\) at the end.
Example. Prove that for all sets \(A\) and \(B\), \(\;A - (A - B) = A \cap B\).
\[\begin{aligned} x \in A - (A - B) &\equiv (x \in A) \land \big(x \notin (A-B)\big) && \text{by definition of set difference} \\ &\equiv (x \in A) \land \sim\!\big(x \in (A-B)\big) && \text{by definition of } \notin \\ &\equiv (x \in A) \land \sim\!\big((x \in A) \land (x \notin B)\big) && \text{by definition of set difference} \\ &\equiv (x \in A) \land \big(\sim\!(x \in A) \lor \sim\!(x \notin B)\big) && \text{by De Morgan's law} \\ &\equiv (x \in A) \land \big((x \notin A) \lor (x \in B)\big) && \text{by definition of } \in \text{ and } \notin \\ &\equiv \big((x \in A) \land (x \notin A)\big) \lor \big((x \in A) \land (x \in B)\big) && \text{by the distributive law} \\ &\equiv \mathbf{c} \lor \big((x \in A) \land (x \in B)\big) && \text{by the negation law} \\ &\equiv (x \in A) \land (x \in B) && \text{by the identity law} \\ &\equiv x \in A \cap B && \text{by the definition of } \cap \end{aligned}\]
Two things to copy from the layout. Every line is justified by name — the marks are in the justification column as much as the algebra. And only four of the nine steps are logical manipulation at all: De Morgan, distributive, negation and identity. The other five are definitions translating set language into logic and back — the three at the top, the last one, and the “\(\in\) and \(\notin\)” line, which sits in the middle of the chain rather than at either end.
Note this method proves the equality in one pass, not two. The chain is a string of \(\equiv\), so it reads correctly in both directions — which is what saves you the second containment proof the element method would demand.
Set identities
For all sets \(A\), \(B\) and \(C\) that are subsets of a universal set \(U\):
| Law | (a) | (b) | |
|---|---|---|---|
| 1 | Commutative | \(A \cup B = B \cup A\) | \(A \cap B = B \cap A\) |
| 2 | Associative | \((A \cup B) \cup C = A \cup (B \cup C)\) | \((A \cap B) \cap C = A \cap (B \cap C)\) |
| 3 | Distributive | \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) | \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) |
| 4 | Identity | \(A \cup \emptyset = A\) | \(A \cap U = A\) |
| 5 | Complement | \(A \cup A^{c} = U\) | \(A \cap A^{c} = \emptyset\) |
| 6 | Double Complement | \((A^{c})^{c} = A\) | |
| 7 | Idempotent | \(A \cup A = A\) | \(A \cap A = A\) |
| 8 | Universal Bound | \(A \cup U = U\) | \(A \cap \emptyset = \emptyset\) |
| 9 | De Morgan’s | \((A \cup B)^{c} = A^{c} \cap B^{c}\) | \((A \cap B)^{c} = A^{c} \cup B^{c}\) |
| 10 | Absorption | \(A \cup (A \cap B) = A\) | \(A \cap (A \cup B) = A\) |
| 11 | Complement of \(U\) and \(\emptyset\) | \(U^{c} = \emptyset\) | \(\emptyset^{c} = U\) |
| 12 | Set Difference | \(A - B = A \cap B^{c}\) |
Provided in the exam. These are printed on the MATH1061/MATH7861 Examination Formula Page alongside the laws of logical equivalence — see formula-sheet. They do not need memorising; the marks are in picking the right one and naming it.
The correspondence with logical-equivalence-laws is not a coincidence: \(\cup\) behaves like \(\lor\), \(\cap\) like \(\land\), \({}^{c}\) like \(\sim\), \(U\) like \(\mathbf{t}\) and \(\emptyset\) like \(\mathbf{c}\). Laws 1–11 are the eleven logical equivalences with the symbols swapped, in the same order and under the same names bar the rename of negation to complement — which is precisely why the previous method works. Law 12 is the exception: the formula page’s logical equivalences have no entry corresponding to set difference, which is why it has to be cleared out of the way first.
Law 12 is the one to reach for first in almost any problem containing a minus sign: it converts set difference — which none of the other eleven laws mention — into intersection and complement, which all of them do.
The set identities method
Same result again, this time by transforming the set expression rather than a membership statement.
Prove that for all sets \(A\) and \(B\), \(\;A - (A - B) = A \cap B\).
\[\begin{aligned} A - (A - B) &= A - (A \cap B^{c}) && \text{by the set difference law (12)} \\ &= A \cap (A \cap B^{c})^{c} && \text{by the set difference law (12)} \\ &= A \cap \big(A^{c} \cup (B^{c})^{c}\big) && \text{by De Morgan's law (9b)} \\ &= A \cap (A^{c} \cup B) && \text{by the double complement law (6)} \\ &= (A \cap A^{c}) \cup (A \cap B) && \text{by the distributive law (3b)} \\ &= \emptyset \cup (A \cap B) && \text{by the complement law (5b)} \\ &= A \cap B && \text{by the identity law (4a)} \end{aligned}\]
Seven lines against the previous method’s nine, and no logic notation at all. Two details worth noting:
- Law 12 is applied twice, to the inner difference and then the outer one. Clearing both minus signs before doing anything else is the move that makes the rest routine.
- The last step cites identity law (4a), \(A \cup \emptyset = A\), applied to \(\emptyset \cup (A \cap B)\) — the operands are the other way round, so commutativity (1a) is being used silently. That is normal practice, but it is worth seeing that the step is really two.
Russell’s paradox
When mathematicians wanted to show that all of mathematics could be built on set theory, Bertrand Russell discovered a problem.
Let \(S\) be the set of all sets that are not elements of themselves: \[S = \{A \mid A \text{ is a set and } A \notin A\}\] Is \(S\) an element of itself?
If \(S \in S\), then \(S \notin S\). If \(S \notin S\), then \(S \in S\). So both \(S \in S\) and \(S \notin S\), which is impossible.
The natural objection — surely a set is never an element of itself? — is the right instinct but is not available as an answer, because it is exactly the thing the naive theory fails to guarantee. Nothing in “a set is any collection of objects” forbids self-membership, and \(S\) is built by a rule that looks as legitimate as any other. The contradiction is not in \(S\) being strange; it is in the assumption that every describable collection is a set.
Several ways to define the basic concepts of set theory were found so that Russell’s paradox does not arise — modern axiom systems restrict which collections count as sets. For more detail, read pages 419–421 (5th edition) or 378–380 (4th edition) of the textbook. For more set theory generally, the course to take is MATH3306 Set Theory and Logic.
See also
- sets-and-set-notation — the definitions and operations being proved about
- logical-equivalence-laws — the laws the second method uses, and the source of the set identities
- proof-techniques — contradiction, contraposition and the general proof shapes
- formula-sheet — what is provided in the exam
- inclusion-exclusion — the identities cited by number to prove the three-set counting rule
- functions-on-general-sets — the next thing built on these definitions
- 2026-09-03-set-properties-and-functions — Lecture 18
- practice-problems — §23 Properties of Sets, with full worked solutions