Target Audience: Anyone moving from proving statements to proving things about structures.
Prerequisites: Logic and Quantifiers and Proof Techniques. Every proof here is one of those methods applied to sets.
Almost every object in mathematics is a set, a relation, or a function — and the last two are themselves sets. This page defines all three and then does the one thing the previous pages could not: applies the proof techniques to real structures.
Sections 1–5 are sets; 6–7 relations; 8–10 functions. The two that repay the most attention are Section 4, where the double-inclusion method turns every set identity into a routine proof, and Section 7, where the relation explorer lets you build a relation by clicking and watch its properties — and its partition — appear.
Counting infinite sets is deliberately left out; that is the subject of the next page.
A set is an unordered collection of distinct objects, called its elements. We write \(x \in A\) for "\(x\) is an element of \(A\)" and \(x \notin A\) for its negation.
Two words carry all the weight. Unordered: \(\{1,2,3\}\) and \(\{3,1,2\}\) are the same set. Distinct: \(\{1,1,2\}\) is just \(\{1,2\}\) — an element is either in or out, never in twice.
By roster, listing the elements: \(A = \{2, 3, 5, 7\}\).
By set-builder notation, giving a rule:
Read the colon as "such that" (a vertical bar is also used). The part before it says what kind of object and where it comes from; the part after is an open sentence that decides membership.
\(A = B\) means they have exactly the same elements:
A set is determined by what is in it and nothing else — not by how it was described. \(\{x \in \mathbb{Z} : x^2 = 1\}\) and \(\{-1, 1\}\) are the same set.
\(x\) and \(\{x\}\) are different objects: \(\{x\}\) is a box containing \(x\). So \(1 \in \{1\}\) is true but \(1 = \{1\}\) is not, and \(\{1\} \in \{\{1\}, 2\}\) while \(1 \notin \{\{1\}, 2\}\). Sets can contain sets, and keeping the layers straight is the whole skill.
\(A\) is a proper subset, \(A \subsetneq B\), when additionally \(A \neq B\).
Note the shape: the definition is a universally quantified conditional, which is exactly why proving \(A \subseteq B\) always starts "let \(x \in A\)".
The condition is \(\forall x,\; (x \in \varnothing \Rightarrow x \in A)\). The hypothesis \(x \in \varnothing\) is never true, so the conditional is vacuously true for every \(x\). The empty set is a subset of everything, including itself — and this is not a special rule, just the definition applied honestly.
The power set \(\mathcal{P}(A)\) is the set of all subsets of \(A\):
\(\mathcal{P}(\{1,2\}) = \big\{\varnothing, \{1\}, \{2\}, \{1,2\}\big\}\) — four elements, each of them a set.
If \(|A| = n\) then \(|\mathcal{P}(A)| = 2^n\): each element is independently in or out of a subset, so there are \(2\) choices \(n\) times. That counting argument is proved on the site's Power Set Cardinality page.
For \(A = \{1, 2\}\): \(1 \in A\) is true, \(1 \subseteq A\) is nonsense (\(1\) is not a set), \(\{1\} \subseteq A\) is true, and \(\{1\} \in A\) is false — \(A\) contains the numbers, not the boxes. Reading a claim wrongly at this level makes every later step unfixable.
Each operation is defined by the logical connective that decides membership:
Read the middle column: union is "or", intersection is "and", complement is "not". Every law in Section 4 is a law of logic wearing set notation.
\(A \times B\) is the set of ordered pairs:
Ordered, so \((1,2) \neq (2,1)\) even though \(\{1,2\} = \{2,1\}\). If \(|A| = m\) and \(|B| = n\) then \(|A \times B| = mn\).
This is the operation that makes Section 6 possible: a relation is a subset of a Cartesian product, and so is a function.
\(A\) and \(B\) are disjoint when \(A \cap B = \varnothing\). A family of sets is pairwise disjoint when every two distinct members are disjoint — the condition that makes a partition work.
| Law | Statement |
|---|---|
| Commutative | \(A \cup B = B \cup A\), \(A \cap B = B \cap A\) |
| Associative | \((A \cup B) \cup C = A \cup (B \cup C)\), likewise for \(\cap\) |
| Distributive | \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) and dually |
| De Morgan | \((A \cup B)^{c} = A^{c} \cap B^{c}\), \((A \cap B)^{c} = A^{c} \cup B^{c}\) |
| Identity | \(A \cup \varnothing = A\), \(A \cap U = A\) |
| Domination | \(A \cup U = U\), \(A \cap \varnothing = \varnothing\) |
| Idempotent | \(A \cup A = A\), \(A \cap A = A\) |
| Absorption | \(A \cup (A \cap B) = A\), \(A \cap (A \cup B) = A\) |
| Double complement | \((A^{c})^{c} = A\) |
Compare this table with the logical equivalences of Unit 1, line for line. They are the same laws: \(\cup\) for \(\lor\), \(\cap\) for \(\land\), \(^{c}\) for \(\lnot\). Learning one table is learning both.
To prove \(A = B\), prove \(A \subseteq B\) and \(B \subseteq A\).
(\(\subseteq\)) Let \(x \in A\). […] Therefore \(x \in B\).
(\(\supseteq\)) Let \(x \in B\). […] Therefore \(x \in A\). Hence \(A = B\). \(\blacksquare\)
This is proving a biconditional in disguise — set equality is the biconditional \(x \in A \Leftrightarrow x \in B\), so it needs two directions. The method of chasing a single element through the definitions is called an element chase.
Claim. \((A \cup B)^{c} = A^{c} \cap B^{c}\).
(\(\subseteq\)) Let \(x \in (A \cup B)^{c}\). Then \(x \notin A \cup B\), so it is not the case that \(x \in A\) or \(x \in B\). By De Morgan for logic, \(x \notin A\) and \(x \notin B\). Hence \(x \in A^{c}\) and \(x \in B^{c}\), so \(x \in A^{c} \cap B^{c}\).
(\(\supseteq\)) Every step above is reversible — each was a definition or the logical law — so the same chain read backwards gives the other inclusion. \(\blacksquare\)
The full argument, with both directions written out separately rather than appealing to reversibility, is on De Morgan's Laws for Sets. Its "A picture is not a proof" remark is worth reading alongside this.
A Venn diagram is an excellent way to find an identity and a poor way to prove one: it shows a single generic arrangement, and cannot represent the case where a region is empty or the sets are nested. Use it to guess; use an element chase to prove.
Given a set \(A_i\) for each \(i\) in an index set \(I\):
Again the connectives decide: union is \(\exists\), intersection is \(\forall\). The index set may be infinite, which is what makes these worth having.
With \(A_n = [0, 1/n]\) for \(n \in \mathbb{N}\): \(\bigcup_n A_n = [0,1]\), and \(\bigcap_n A_n = \{0\}\) — every \(A_n\) contains \(0\), and any \(x \gt 0\) fails to be in \(A_n\) once \(1/n \lt x\).
Set-builder notation invites a tempting rule: any property whatsoever carves out a set. It does not. Consider the collection of all sets that are not elements of themselves,
and ask whether \(R \in R\). If \(R \in R\), then \(R\) satisfies the defining property, so \(R \notin R\). If \(R \notin R\), then it satisfies the property, so \(R \in R\). Both branches are contradictory: \(R \in R \Leftrightarrow R \notin R\), a statement equivalent to its own negation, which is a contradiction in the strict sense. So no such \(R\) exists.
Modern set theory restricts comprehension: you may not form \(\{x : P(x)\}\) out of nothing, only \(\{x \in A : P(x)\}\) — carving a subset out of a set you already have. That is why every set-builder expression on this page names a source set before the colon.
The full argument and its consequences are on Russell's Paradox.
A relation from \(A\) to \(B\) is a subset \(R \subseteq A \times B\). A relation on \(A\) is a subset of \(A \times A\). We write \(a \mathbin{R} b\) for \((a,b) \in R\).
That is the whole definition — a relation is not a rule or a test, it is simply the set of pairs that stand in it. "\(\leq\) on \(\{1,2\}\)" is the set \(\{(1,1),(1,2),(2,2)\}\).
Let \(R\) be a relation on \(A\).
Each is a universally quantified conditional, so each is disproved by a single counterexample — one pair, or one triple. That is exactly what the explorer below reports when a property fails.
They are independent. Equality is both symmetric and antisymmetric; "differ by 1" is symmetric and not antisymmetric; strict \(\lt\) is antisymmetric and not symmetric; and a relation can be neither. Antisymmetry only forbids \(a \mathbin{R} b\) and \(b \mathbin{R} a\) together for distinct \(a, b\) — pairs \((a,a)\) are irrelevant to it.
An equivalence relation is reflexive, symmetric and transitive. A partial order is reflexive, antisymmetric and transitive.
For an equivalence relation \(\sim\) on \(A\), the equivalence class of \(a\) is
A partition of \(A\) is a family of non-empty, pairwise disjoint subsets whose union is \(A\).
The equivalence classes of an equivalence relation on \(A\) form a partition of \(A\); and conversely every partition arises from exactly one equivalence relation.
The three properties do exactly three jobs: reflexivity puts every element into a class (so the classes cover \(A\)), symmetry and transitivity together force two classes that meet to coincide (so they are disjoint), and non-emptiness is reflexivity again. Proved in full on Equivalence Relations Partition a Set.
A relation on \(\{1,2,3,4\}\) is just a set of pairs, so it can be drawn as a grid. Choose a preset, or click any cell to add or remove a pair. The four properties are re-checked on every edit, with a counterexample shown whenever one fails — and when the relation is an equivalence relation, its partition appears.
Try removing a single pair from "same parity" and watch which property breaks first — and how the partition vanishes with it.
Define \(a \sim b\) when \(n \mid (a - b)\). Reflexive: \(n \mid 0\). Symmetric: if \(a - b = nk\) then \(b - a = n(-k)\). Transitive: if \(a - b = nk\) and \(b - c = nm\) then \(a - c = n(k+m)\). So \(\sim\) is an equivalence relation, and its classes are the \(n\) residue classes — the partition of \(\mathbb{Z}\) that all of modular arithmetic is built on.
A function \(f : A \to B\) is a relation \(f \subseteq A \times B\) such that for every \(a \in A\) there is exactly one \(b \in B\) with \((a,b) \in f\). We write \(f(a) = b\).
So a function is a special kind of relation, and the \(\exists!\) of Unit 1 is doing the work: at least one \(b\) makes \(f\) total, at most one makes it well-defined.
\(A\) is the domain, \(B\) the codomain, and the range (or image) is what is actually hit:
The codomain is chosen; the range is determined. \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\) has codomain \(\mathbb{R}\) and range \([0,\infty)\) — and changing the codomain to \([0,\infty)\) changes whether \(f\) is surjective without changing a single value.
When a function is defined on equivalence classes — "let \(f([a]) = \ldots\)" — the recipe uses a representative, and different representatives must give the same answer. Checking that is what "well-defined" means, and skipping the check is a standard way to prove something false.
Injective means no two inputs collide (one-to-one); surjective means the range is all of the codomain (onto).
Injective. Assume \(f(a_1) = f(a_2)\). [Algebra.] Therefore \(a_1 = a_2\).
Surjective. Let \(b \in B\). [Construct \(a\) from \(b\).] Then \(f(a) = b\).
\(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = 3x + 7\).
Injective. Suppose \(3a_1 + 7 = 3a_2 + 7\). Subtract \(7\), divide by \(3\): \(a_1 = a_2\).
Surjective. Let \(b \in \mathbb{R}\) and set \(a = (b-7)/3\), which is real. Then \(f(a) = 3\left(\frac{b-7}{3}\right) + 7 = b\). So \(f\) is bijective.
Note the surjectivity proof is constructive — it builds the witness, which is exactly what existence proofs ask for.
\(f(x) = x^2\) is not surjective as a map \(\mathbb{R} \to \mathbb{R}\), but is as a map \(\mathbb{R} \to [0,\infty)\). Neither is it injective on \(\mathbb{R}\) (\(f(-2) = f(2)\)) though it is on \([0,\infty)\). Always state the domain and codomain before claiming either property.
For \(f : A \to B\) and \(g : B \to C\), the composition \(g \circ f : A \to C\) is \((g \circ f)(a) = g(f(a))\).
Composition is associative but not commutative — \(g \circ f\) and \(f \circ g\) need not even both be defined. Read \(g \circ f\) right to left: \(f\) acts first.
\(f : A \to B\) is invertible when there is \(g : B \to A\) with \(g \circ f = \mathrm{id}_A\) and \(f \circ g = \mathrm{id}_B\). Then \(g\) is unique and written \(f^{-1}\).
A function is invertible if and only if it is bijective. Injectivity is what lets \(f^{-1}\) be single-valued; surjectivity is what lets it be defined on all of \(B\).
\(f^{-1}(y)\) for an inverse function requires \(f\) to be bijective. But \(f^{-1}(S) = \{a \in A : f(a) \in S\}\), the preimage of a set, is defined for every function — no bijectivity needed. The notation is identical; only the argument (an element or a set) distinguishes them.
| Idea | The one thing to remember |
|---|---|
| Set | Unordered, no repeats; determined by its elements alone. |
| \(\subseteq\) | A quantified conditional — so proofs start "let \(x \in A\)". \(\varnothing \subseteq A\) vacuously. |
| Operations | Union is "or", intersection is "and", complement is "not". |
| Set identities | Double inclusion plus an element chase. Venn diagrams suggest, they do not prove. |
| Russell | Not every description names a set; carve subsets out of sets you already have. |
| Relation | A set of ordered pairs. Four properties, each disproved by one counterexample. |
| Equivalence relation | Reflexive, symmetric, transitive — and exactly the same thing as a partition. |
| Function | A relation with exactly one output per input. Codomain is chosen; range is determined. |
| Bijective | Injective plus surjective — and precisely the condition for an inverse to exist. |
Text used for this page: Hammack, Book of Proof, Chapters 1, 8, 11 and 12 (free online). Next in this series: Cardinality and the Infinite — what it means for two sets to be the same size when neither is finite.
An addendum: the notation of this page in one place. The logic symbols it builds on are in the Unit 1 symbol reference.
| Notation | Read as | Means |
|---|---|---|
| \(x \in A\) | x is an element of A | Membership. Its negation is \(x \notin A\). |
| \(A \subseteq B\) | A is a subset of B | \(\forall x,\; (x \in A \Rightarrow x \in B)\) |
| \(A \subsetneq B\) | A is a proper subset of B | \(A \subseteq B\) and \(A \neq B\) |
| \(\varnothing\) | the empty set | No elements; a subset of every set. |
| \(\mathcal{P}(A)\) | the power set of A | All subsets of \(A\); \(2^{n}\) of them when \(|A| = n\). |
| \(A \cup B\) | A union B | In \(A\) or in \(B\) (inclusive). |
| \(A \cap B\) | A intersect B | In \(A\) and in \(B\). |
| \(A \setminus B\) | A minus B | In \(A\) but not in \(B\). |
| \(A^{c}\) | the complement of A | In the universe \(U\) but not in \(A\). |
| \(A \times B\) | A cross B | Ordered pairs \((a,b)\); \((1,2) \neq (2,1)\). |
| \(\bigcup_{i \in I} A_i\) | the union over the family | In \(A_i\) for some \(i\). |
| \(\bigcap_{i \in I} A_i\) | the intersection over the family | In \(A_i\) for every \(i\). |
| \(a \mathbin{R} b\) | a is related to b | \((a,b) \in R\), where \(R \subseteq A \times A\). |
| \([a]\) | the class of a | \(\{x : x \sim a\}\), for an equivalence relation \(\sim\). |
| \(f : A \to B\) | f maps A to B | Exactly one output in \(B\) for each input in \(A\). |
| \(g \circ f\) | g composed with f | \(a \mapsto g(f(a))\); \(f\) acts first. |
| \(f^{-1}\) | the inverse, or the preimage | Inverse function (needs bijectivity), or \(f^{-1}(S) = \{a : f(a) \in S\}\) (always defined). |
| \(\mathrm{id}_A\) | the identity on A | \(a \mapsto a\) for every \(a \in A\). |