What Does It Mean for Sets to Be Equal?
In Subset and Proper Subset, we compared two sets by checking whether every element of one also belongs to the other. Set equality uses that same element-by-element viewpoint, but asks for agreement in both directions. Two sets are equal when every element of the first is in the second and every element of the second is in the first.
This is the central idea behind equality of sets: a set is determined by its elements. The way a set is written is not part of the set itself. For example, \(\{1,4,9\}\) and \(\{9,1,4\}\) are equal because they contain precisely the same objects. Writing an element twice does not create an additional element, so \(\{1,4,4,9\}\) describes that same set as well.
Set equality is written \(A=B\). It is distinct from membership notation \(A\in B\): equality compares the elements of two sets, while membership asks whether one object is an element of a set. An object can itself be a set, so both kinds of statement can sometimes be meaningful, but they make different claims.
Equality and Inclusion in Both Directions
The formal criterion for equality can be written using the subset relation. Two sets have the same elements if and only if each is a subset of the other: $$ A=B \quad\Longleftrightarrow\quad \bigl(A\subseteq B\ \text{and}\ B\subseteq A\bigr). $$ The two inclusions are both necessary. The first rules out an element of \(A\) that is missing from \(B\), and the second rules out an element of \(B\) that is missing from \(A\).
Theorem (Equality by Double Inclusion). Let \(A\) and \(B\) be sets. Then \(A=B\) if and only if \(A\subseteq B\) and \(B\subseteq A\).
Proof. First suppose \(A=B\). Let \(x\) be any object. If \(x\in A\), then \(x\in B\), because \(A\) and \(B\) are the same set. Thus \(A\subseteq B\). The same reasoning in the reverse direction shows that \(B\subseteq A\).
Conversely, suppose \(A\subseteq B\) and \(B\subseteq A\). If \(x\in A\), then the first inclusion gives \(x\in B\). If \(x\in B\), then the second inclusion gives \(x\in A\). Therefore an object belongs to \(A\) exactly when it belongs to \(B\). The sets have the same elements, so \(A=B\). This proves both directions.
This theorem gives a practical proof method: treat equality as two subset claims. For the first, begin with an arbitrary element of \(A\) and show it lies in \(B\). For the second, begin with an arbitrary element of \(B\) and show it lies in \(A\). A proof in only one direction establishes an inclusion, but not necessarily equality.
Take an arbitrary \(x\in A\) and establish \(x\in B\).
Take an arbitrary \(x\in B\) and establish \(x\in A\). This is a separate direction and may require a different argument.
By the Equality by Double Inclusion theorem, the two inclusions imply \(A=B\).
Worked Example: Comparing Two Finite Rosters
Let \(A=\{3,6,10\}\) and \(B=\{10,3,6\}\). To verify \(A\subseteq B\), consider each element of \(A\). The element \(3\) belongs to \(B\), the element \(6\) belongs to \(B\), and the element \(10\) belongs to \(B\). Therefore \(A\subseteq B\).
For the reverse inclusion, the elements of \(B\) are \(10\), \(3\), and \(6\), and each belongs to \(A\). Hence \(B\subseteq A\). By the Equality by Double Inclusion theorem, \(A=B\). The different order of the entries has no effect on this conclusion.
Equality for Sets Defined by Conditions
Sets are not always given by finite rosters. Earlier in this course, a set defined on a domain \(D\) by a condition \(P\) was written in the form \(\{x\in D:P(x)\}\). For two such sets on the same domain, equality reduces to a question about their defining conditions: do the conditions accept exactly the same elements of \(D\)?
Theorem (Equality of Condition-Defined Sets). Let \(D\) be a domain, and let \(P(x)\) and \(Q(x)\) be conditions defined for every \(x\in D\). Define $$ A=\{x\in D:P(x)\}, \qquad B=\{x\in D:Q(x)\}. $$ Then $$ A=B \quad\Longleftrightarrow\quad \forall x\in D,\ \bigl(P(x)\Longleftrightarrow Q(x)\bigr). $$
Proof. Suppose first that \(A=B\). Let \(x\in D\). By the definition of these sets, \(P(x)\) holds exactly when \(x\in A\), and \(Q(x)\) holds exactly when \(x\in B\). Since \(A=B\), membership in \(A\) is equivalent to membership in \(B\). It follows that \(P(x)\) holds exactly when \(Q(x)\) holds. Because \(x\) was arbitrary in \(D\), the two conditions are equivalent for every \(x\in D\).
Conversely, suppose \(P(x)\Longleftrightarrow Q(x)\) for every \(x\in D\). Let \(y\) be any object. If \(y\in A\), then the definition of \(A\) gives \(y\in D\) and \(P(y)\). The assumed equivalence gives \(Q(y)\), so \(y\in B\). Thus \(A\subseteq B\). In the reverse direction, if \(y\in B\), then \(y\in D\) and \(Q(y)\). The same equivalence gives \(P(y)\), so \(y\in A\). Thus \(B\subseteq A\). The Equality by Double Inclusion theorem now gives \(A=B\).
The shared domain matters. The conditions are compared only for inputs in \(D\), because neither set includes objects outside \(D\). The result is useful when two different descriptions appear to define the same collection: compare their membership conditions for an arbitrary allowed input.
Worked Example: Two Descriptions of the Same Integers
Let $$ A=\{n\in\mathbb Z:n\text{ is divisible by }4\}, \qquad B=\{n\in\mathbb Z:\text{there is }k\in\mathbb Z\text{ such that }n=4k\}. $$ The first condition describes divisibility by \(4\); the second gives the corresponding integer-multiple condition. By the definition of divisibility, an integer is divisible by \(4\) exactly when it equals \(4k\) for some integer \(k\). Thus for every \(n\in\mathbb Z\), the defining condition for \(A\) holds if and only if the defining condition for \(B\) holds.
The Equality of Condition-Defined Sets theorem applies with domain \(\mathbb Z\). It follows that \(A=B\). For example, \(12\) belongs to both sets because \(12=4\cdot3\), while \(10\) belongs to neither because there is no integer \(k\) with \(10=4k\). The proof does not depend on checking only these examples; it uses the equivalence of the defining conditions for every integer.
How to Prove That Sets Are Unequal
To disprove equality, it is enough to find an object whose membership differs between the two sets. Such an object is often called a distinguishing element or a witness to inequality. If \(x\in A\) but \(x\notin B\), then \(A\) cannot equal \(B\). If instead \(x\in B\) but \(x\notin A\), the same conclusion follows.
This is the direct counterpart of proving equality. Equality requires both inclusions, so failure of either inclusion gives a witness that the sets are not equal. It is not necessary to find all the elements on which the sets differ; one valid witness is enough.
Worked Example: One Element Disproves Equality
Let \(C=\{2,5,8\}\) and \(D=\{2,5,9\}\). The object \(8\) belongs to \(C\), but \(8\notin D\), since the listed elements of \(D\) are \(2\), \(5\), and \(9\). Therefore \(C\not\subseteq D\), and in particular \(C\ne D\).
There is also a witness in the reverse direction: \(9\in D\) and \(9\notin C\). Either witness suffices to establish inequality. Notice that the shared elements \(2\) and \(5\) do not make the sets equal; equality requires agreement on every possible object's membership.
Proposition. If \(A\) and \(B\) are unequal sets, then there is an object \(x\) such that either \(x\in A\) and \(x\notin B\), or \(x\in B\) and \(x\notin A\).
Proof. Suppose \(A\ne B\). If there were no object belonging to one set but not the other, then every object in \(A\) would belong to \(B\), giving \(A\subseteq B\), and every object in \(B\) would belong to \(A\), giving \(B\subseteq A\). By the Equality by Double Inclusion theorem, these two inclusions would imply \(A=B\), contrary to the assumption. Therefore at least one of the two inclusions fails. By the definition of subset, failure of \(A\subseteq B\) means there is an object \(x\) with \(x\in A\) and \(x\notin B\); failure of \(B\subseteq A\) means there is an object \(x\) with \(x\in B\) and \(x\notin A\). In either case the required witness exists.
Common Misreadings
One common error is to show only that every element of \(A\) belongs to \(B\), and then conclude \(A=B\). That argument proves \(A\subseteq B\). The reverse direction is still needed: every element of \(B\) must also belong to \(A\). For example, \(\{1,4\}\subseteq\{1,4,7\}\), but the sets are not equal because \(7\) belongs to the second and not the first.
Another mistake is to count written entries rather than distinct elements. A set does not record how many times an element is listed. Thus \(\{a,b,a\}=\{a,b\}\). Likewise, changing the order of the entries does not change which objects belong to the set. These facts follow from the element-based meaning of set equality, not from a convention that rosters must be written in a particular order.
| Statement | Meaning |
|---|---|
| \(x\in A\) | The object \(x\) is an element of \(A\). |
| \(A\subseteq B\) | Every element of \(A\) is an element of \(B\). |
| \(A=B\) | Every object belongs to \(A\) exactly when it belongs to \(B\). |
| \(A\ne B\) | At least one object belongs to one of the sets and not the other. |
For each question, distinguish carefully between checking one inclusion and establishing equality.
Check Your Understanding
- Let \(A=\{4,7,11\}\) and \(B=\{11,4,7\}\). Show whether \(A=B\), using the two-inclusion criterion.
- Let \(C=\{1,3\}\) and \(D=\{1,3,6\}\). Is \(C\subseteq D\)? Are the sets equal? Identify a witness that resolves the equality question.
- Suppose \(P\subseteq Q\) and \(Q\subseteq P\). What conclusion follows about \(P\) and \(Q\), and which theorem justifies it?
- On domain \(\mathbb Z\), compare \(E=\{n\in\mathbb Z:n\text{ is even}\}\) with \(F=\{n\in\mathbb Z:\text{there is }k\in\mathbb Z\text{ such that }n=2k\}\). What must be shown to conclude \(E=F\)?
- If \(A\ne B\), what kind of object must exist? State the two possible membership patterns for such a witness.
- Explain why \(\{2,5,2\}=\{5,2\}\). Does this equality assert that the two written lists have the same number of entries?