Sets Collect Objects
In Proof Structure and Organization, we focused on how to state assumptions, introduce objects, and make a conclusion follow. Sets give us a language for describing collections of objects precisely. They will provide a setting for many definitions and arguments in this module, including functions, whose inputs and outputs are described using sets.
A set is a collection of distinct mathematical objects. The objects in a set are called its elements, or its members. A set can contain numbers, points, functions, other sets, or objects of different kinds. The elements need not have any particular order, and listing the same element more than once does not create additional elements.
For example, the notation \(\{4,7,9\}\) describes the set whose elements are \(4\), \(7\), and \(9\). The braces \(\{\ \}\) mark the collection, and commas separate the listed elements. This notation is called roster notation. When the elements are real numbers, the order in which we write them on the page does not change the set they describe.
Basic Notation and Conventions
We use capital letters such as \(A\), \(B\), and \(S\) to name sets, and lower-case letters such as \(x\), \(y\), and \(a\) to name objects. This is a convention rather than a requirement, but it helps a reader see which role a symbol is playing. The phrase “\(x\) is an element of \(A\)” is commonly written \(x\in A\). The symbol \(\notin\) means “is not an element of.”
Membership notation records a relationship between an object and a set. For instance, if \(A=\{4,7,9\}\), then \(7\in A\) and \(5\notin A\). The number \(7\) is an element; \(A\) is the set. It is important not to confuse a set with the objects listed inside its braces.
A set with no elements is called the empty set, written \(\varnothing\) or \(\{\}\). These two notations name the same set. The empty set is not the same thing as a set whose element is the empty set: \(\varnothing\) has no elements, while \(\{\varnothing\}\) has one element, namely \(\varnothing\).
| Notation | What it describes | Number of elements |
|---|---|---|
| \(6\) | The number \(6\), by itself | Not a set |
| \(\{6\}\) | The set whose only element is \(6\) | One |
| \(\{\{6\}\}\) | The set whose only element is the set \(\{6\}\) | One |
| \(\varnothing\) | The set with no elements | Zero |
The braces show which collection is being formed. In \(\{6\}\), the element is the number \(6\). In \(\{\{6\}\}\), the element is the set \(\{6\}\); the number \(6\) is an element of that inner set, not directly an element of the outer one. Careful attention to the braces prevents a common ambiguity.
Worked Example: Reading a Set with Nested Braces
Let \(B=\{2,\{2\}\}\). The two elements of \(B\) are \(2\) and the set \(\{2\}\). They are different objects: one is a number, and the other is a set.
Consequently, \(2\in B\) and \(\{2\}\in B\). The number \(2\) is also an element of the inner set, so \(2\in\{2\}\). But \(\{\{2\}\}\notin B\), because neither of the two elements listed in \(B\) is the set \(\{\{2\}\}\). Reading from the outermost braces inward makes each membership claim clear.
How to Read and Build Finite Sets
A finite set can be written by listing each of its elements between braces. For example, \(\{a,b,c\}\) has precisely the elements \(a\), \(b\), and \(c\). If the elements are numbers or other objects with a familiar pattern, a description may be more useful than a long roster. Set-builder notation, introduced earlier in Writing Definitions Precisely, describes a set by specifying a domain and a condition on its elements.
For example, \(\{n\in\mathbb Z:n^2=16\}\) means the set of integers \(n\) for which \(n^2=16\). The condition has two integer solutions, \(n=4\) and \(n=-4\), so this set is \(\{-4,4\}\). The domain restriction \(n\in\mathbb Z\) is part of the description: the set consists only of objects in the stated domain that satisfy the condition.
When checking a set description, separate its ingredients. Identify the domain from which possible elements are drawn, identify the property those elements must satisfy, and then determine which objects meet that property. This is the same precision needed when reading a theorem: the allowed objects and the condition on them must both be understood.
Read the objects after “such that” as restricted by the stated domain, such as \(n\in\mathbb Z\).
Determine the property an object must satisfy to be included in the set.
Check that every listed object is in the domain and satisfies the condition.
The roster must contain all objects in the domain that satisfy the condition, not just some examples.
Worked Example: Turning a Condition into a Roster
Consider the set $$ C=\{m\in\mathbb Z: 1\leq m\leq 5\text{ and }m\text{ is even}\}. $$ The domain is the integers, and the condition requires an integer from \(1\) through \(5\) that is even. The integers in that range are \(1,2,3,4,5\). Among them, exactly \(2\) and \(4\) are even. Therefore $$ C=\{2,4\}. $$
The endpoints are included because the inequalities are \(\leq\), but neither endpoint is even. The roster contains every integer in the given range that meets the condition, and no integer that fails it.
When Are Two Sets Equal?
Two sets are equal exactly when they have the same elements. In symbols, \(A=B\) means that every element of \(A\) is an element of \(B\), and every element of \(B\) is an element of \(A\). This is the extensionality principle for sets: the identity of a set is fixed by its elements, not by how its elements are listed or described.
To prove two sets equal, it is therefore enough to show that they contain precisely the same objects. Sometimes this can be checked by comparing two finite rosters. For sets described by conditions, the same goal is often expressed by taking an arbitrary object and showing that it satisfies the first description exactly when it satisfies the second. The detailed notation for membership will be developed in the next tutorial; the underlying idea is already useful here.
Worked Example: Comparing Two Descriptions
Let \(D=\{x\in\mathbb R:x=3\text{ or }x=-1\}\) and \(E=\{-1,3\}\). The condition defining \(D\) permits exactly the real numbers \(-1\) and \(3\). Thus the elements of \(D\) are precisely the elements listed in \(E\), and the extensionality principle gives \(D=E\).
The order of the two entries in the roster for \(E\) is immaterial. The conclusion does not depend on which description is shorter; it follows because both descriptions specify the same elements.
Two Consequences for Roster Notation
The definition of set equality immediately explains why changing the order of a roster does not change its set. It also explains why repeating an entry has no effect. These are not special rules about numbers; they hold for elements of any kind, since the definition depends only on which objects are present.
Theorem. Let \(a\) and \(b\) be objects. Then $$ \{a,b\}=\{b,a\} \qquad\text{and}\qquad \{a,a\}=\{a\}. $$
Proof. The set \(\{a,b\}\) contains exactly the objects \(a\) and \(b\). The set \(\{b,a\}\) contains exactly those same objects, so the extensionality principle gives \(\{a,b\}=\{b,a\}\). This reasoning still applies when \(a=b\): in that case both sets have just the single element \(a\).
The set \(\{a,a\}\) also contains just the object \(a\), because listing \(a\) a second time does not add a new object. The set \(\{a\}\) contains exactly that same object. By extensionality, \(\{a,a\}=\{a\}\). This proves both claims.
The next result gives a useful test for when two one-element sets are equal. Such a set is called a singleton.
Proposition. For any objects \(a\) and \(b\), $$ \{a\}=\{b\}\quad\Longleftrightarrow\quad a=b. $$
Proof. First suppose \(\{a\}=\{b\}\). Since \(a\) is the element of \(\{a\}\), equality of the sets means that \(a\) is also an element of \(\{b\}\). The only element of \(\{b\}\) is \(b\), so \(a=b\).
Conversely, suppose \(a=b\). The singleton \(\{a\}\) and the singleton \(\{b\}\) then each have the same one element, because their listed objects are equal. By extensionality, \(\{a\}=\{b\}\). Both directions have been proved, so the equivalence follows.
Common Misreadings to Avoid
A roster is not an ordered list in the usual sense. Writing \(\{1,4,8\}\) rather than \(\{8,1,4\}\) changes the presentation but not the set. Similarly, \(\{1,4,4,8\}\) and \(\{1,4,8\}\) describe the same set because the repeated \(4\) does not create another element. The set notation records distinct objects, not a sequence of entries with positions.
Do not assume that the elements of every set are numbers. A set can contain a point, a function, another set, or a mixture of objects. Nor should braces be treated as decoration: changing where braces begin and end can change the object being described. For example, \(\{3\}\) and \(\{\{3\}\}\) each have one element, but those elements differ. One contains the number \(3\); the other contains the singleton whose element is \(3\).
Finally, set equality concerns all elements, not merely a few examples. If two sets each contain \(2\) and \(5\), that fact alone does not establish that they are equal; one set might also contain another object. A complete comparison accounts for every element on both sides. This is why equality of sets is described using “exactly the same elements.”
Worked Example: Detecting a Missing Element
Let \(F=\{0,3,6\}\) and \(G=\{0,3,6,9\}\). The first three objects occur in both sets, but \(9\in G\) and \(9\notin F\). Therefore the sets do not have exactly the same elements, so \(F\ne G\).
This comparison illustrates why checking only shared elements is insufficient. To establish equality, one must also check that no element occurs in one set but not the other.
Check Your Understanding
For each question, use the distinction between an object, a set, and the elements of a set.
- If \(A=\{1,5,8\}\), name all the elements of \(A\). Is \(5\in A\), and is \(6\in A\)?
- Explain why \(\{2,7\}=\{7,2\}\), and state whether \(\{2,2,7\}=\{2,7\}\).
- How many elements does \(\varnothing\) have? How many elements does \(\{\varnothing\}\) have?
- Describe the elements of \(H=\{n\in\mathbb Z:n^2=25\}\), then write \(H\) in roster notation.
- What is the difference between the element of \(\{4\}\) and the element of \(\{\{4\}\}\)?
- According to the extensionality principle, what must be checked to conclude that two sets are equal?