Algebra 1

Elements and membership

When you gather things into one collection, what does it mean for a thing to belong to it, and when are two collections the same?

Unlocks

Subsets, proper subsets and equal setsDiscrete Mathematics and Proof Writing sets: roster, rule and the empty setAlgebra 1

Where you are 15 in Sets

Logic, proof and discrete math6

Sets15

Elements and membership

Subsets, proper subsets and equal sets Writing sets: roster, rule and the empty set Cardinality of a finite set Cartesian product ▾ Show all 15 (10 more)

Why this exists

Mathematics is full of collections: the whole numbers from 1 to 10, the solutions of an equation, the points on a line, the letters of a word. Before anyone can say something true about a collection, two plain questions need settled answers. Is this particular thing in it, or not? And when are two collections the same collection?

Without answers, arguments about collections fall apart. Is the collection of letters in “LOOT” the same as the collection of letters in “TOOL”? Is a collection that lists the number 7 twice different from one that lists it once? A collection of solutions found by factoring and a collection of solutions found by a graph: are they the same?

The idea of a set gives firm answers to both. A thing is either in a set or it is not, with nothing in between. And a set is decided entirely by what is in it: nothing else about how it was described or written down matters. Every later idea about sets, subsets, unions, counting and proof, rests on these two sentences.

Definition

A set is a collection of objects. The objects in it are called its elements, or its members. For this lesson, numbers and letters count as plain objects, not as collections.

The simplest way to name a set is to list its elements between braces and give the set a capital letter:

A = \{2, 4, 6, 8\}

This is read “A is the set whose elements are 2, 4, 6 and 8”.

To say that an object belongs to a set, write \in. To say that it does not, write \notin:

4 \in A \qquad\text{and}\qquad 5 \notin A

These read “4 is an element of A” and “5 is not an element of A”. Both statements are true. A statement like x \in A is either true or false, and never anything in between.

Figure 1The set A = \{2, 4, 6, 8\}. A dot inside the loop is an element; a dot outside is not.

Figure 1 shows the picture that goes with the notation: the set is a loop, and each element is a dot inside it. A dot outside the loop is an object that is not an element.

The second half of the definition says when two sets are the same.

Two sets are equal exactly when they have the same elements.

That is the whole rule. It is sometimes called extensionality, a long word for “a set is settled by what is in it, and by nothing more”. It says that the set is not its name, not the order you happened to list it in, and not the way you described it.

Intuition

Think of a guest list for one party. The party has a yes or no answer for every person: invited or not. That is membership.

Now suppose two people write out the guest list separately. One writes Ana, Ben, Cho. The other writes Cho, Ana, Ben, and writes Ben a second time by accident. The guests are the same: the same three people are invited, so the two lists describe the same party. The order was never part of it, and writing a name twice does not invite that person twice.

A set works the same way. What it holds is which objects are in it, never in what order they were written, and never how many times a name was repeated.

Results

Membership is a yes or no question. For any object x and any set A, exactly one of the two statements x \in A and x \notin A is true.

Equal sets. Two sets A and B are equal, written A = B, exactly when every element of A is an element of B and every element of B is an element of A.

Two facts about lists follow at once.

\{2, 5\} = \{5, 2\} \qquad\qquad \{7, 7\} = \{7\}

Order does not matter, and repeats collapse. The number of elements of a set is the number of different objects in it, so \{1, 2, 2, 3, 3, 3\} has three elements.

An element and a set are different things. A set can itself be an element of another set. The set T = \{1, \{2, 3\}\} has two elements: the number 1, and the set \{2, 3\}. So \{2, 3\} \in T, but 2 \notin T. Belonging counts one layer only: the number 2 is in the set \{2, 3\}, and that set is in T, but 2 itself is not directly in T.

The empty set. The set with no elements at all is written \{\ \} or \varnothing. It is a perfectly good set, and it is not the same as \{\varnothing\}, which has one element (that element is the empty set).

Why it is true

The two facts about lists come from what a listed set means. Writing \{a_1, a_2, \dots, a_n\} names the set whose elements are exactly the listed objects, so

x \in \{a_1, a_2, \dots, a_n\}

means that at least one of these is true:

x = a_1, \quad x = a_2, \quad \dots, \quad x = a_n

Now take \{2, 5\} and \{5, 2\}. An object x is in the first set exactly when x = 2 or x = 5. It is in the second exactly when x = 5 or x = 2. “Or” does not care which statement comes first, so the two conditions are the same condition. Every object passes the test for one set exactly when it passes the test for the other, so the sets have the same elements and are equal.

Repeats work the same way. An object x is in \{7, 7\} exactly when x = 7 or x = 7, and saying the same thing twice is the same as saying it once: that is x = 7, which is exactly the test for \{7\}. So \{7, 7\} = \{7\}.

For the layering, take T = \{1, \{2, 3\}\}. Because numbers are plain objects here, the number 2 is not equal to 1, and it is not equal to the set \{2, 3\}. So the test “2 = 1 or 2 = \{2, 3\}” fails, and 2 \notin T. The set \{2, 3\} passes the test “\{2, 3\} = 1 or \{2, 3\} = \{2, 3\}”, so \{2, 3\} \in T.

Notice what all of this leans on: only that membership is tested element by element, and that a set is identified by the outcome of those tests. That is why no extra rule is needed for order or repeats. They are consequences of the definition, not additions to it.

Worked examples

Example 1

Reading membership

Let A = \{2, 4, 6, 8\}, as in Figure 1. Say whether each statement is true or false: 4 \in A, 5 \in A, 10 \notin A and 8 \notin A. Then say how many elements A has.

Solution

To test “4 \in A”, look for 4 in the list. It is there, so the statement is true.

To test “5 \in A”, look for 5. The list has 2, 4, 6 and 8, and none of them is 5, so the statement is false. (That is the same as saying 5 \notin A, which is true.)

“10 \notin A” says 10 is not in the list. It is not, so the statement is true.

“8 \notin A” says 8 is not in the list. But 8 is the last element, so the statement is false.

The list has four different objects, so A has 4 elements.

Example 2

Order and repeats

Are the sets P = \{3, 1, 2\}, Q = \{1, 2, 3, 2\} and R = \{1, 2, 3, 3, 1\} equal? How many elements does each have?

Solution

By the rule for equal sets, compare elements. List which different objects each set contains.

P contains 3, 1 and 2. Q contains 1, 2 and 3 (the second 2 adds nothing new). R contains 1, 2 and 3 (the second 3 and the second 1 add nothing new).

All three contain exactly the objects 1, 2 and 3, and nothing else. So all three are equal:

P = Q = R = \{1, 2, 3\}

Each has 3 elements, because the number of elements counts different objects, and there are three different objects.

Example 3

A set inside a set

Figure 2 shows S = \{5, \{5\}, \{6, 7\}, \varnothing\}. List the elements of S. Then say whether each statement is true: 5 \in S, 6 \in S, \{6, 7\} \in S, \{5, 6, 7\} \in S and \varnothing \in S.

Figure 2A set can have sets as elements. Only what sits directly inside the big loop is an element of S.

Solution

Read the elements off as the things written directly between the outer braces, separated by commas. There are four of them: the number 5, the set \{5\}, the set \{6, 7\}, and the empty set \varnothing. So S has 4 elements. (The number 5 and the set \{5\} are different objects, so both count.)

Now test each statement against that list of four:

5 \in S is true, because 5 is on the list.
6 \in S is false. The number 6 is inside the set \{6, 7\}, but that is one layer down. It is not one of the four elements of S.
\{6, 7\} \in S is true, because this set is on the list.
\{5, 6, 7\} \in S is false. That set is not on the list; it is a different set from \{6, 7\} and from \{5\}.
\varnothing \in S is true, because the empty set is one of the four elements.

Example 4

Describing a set by a rule

Let T be the set of whole numbers that leave remainder 2 when divided by 5. Which of 12, 17, 22, 50 and 102 are elements of T? List the elements of T that are less than 30.

Solution

For this set there is no list to look at. Instead there is a test: divide by 5 and look at the remainder. That is enough to make it a set, because for any whole number the test gives a clear yes or no.

\begin{aligned} 12 &= 2 \cdot 5 + 2 \\ 17 &= 3 \cdot 5 + 2 \\ 22 &= 4 \cdot 5 + 2 \\ 50 &= 10 \cdot 5 + 0 \\ 102 &= 20 \cdot 5 + 2 \end{aligned}

The remainders are 2, 2, 2, 0, 2. So 12, 17, 22 and 102 are elements, and 50 is not.

For the elements below 30, start at the first number with remainder 2, which is 2 itself (2 = 0 \cdot 5 + 2), and add 5 each time, because adding 5 keeps the remainder the same:

2,\ 7,\ 12,\ 17,\ 22,\ 27

The next one, 32, is too large. So the elements of T below 30 are 2, 7, 12, 17, 22 and 27.

Example 5

The same set, described differently

Let A be the set of solutions of x^2 - 5x + 6 = 0, let B = \{2, 3\}, let C = \{3, 2, 3\}, and let D be the set of prime numbers less than 4. Are these four sets equal?

Solution

Work out the elements of each, since the elements are all that matter.

A: factor the equation as (x - 2)(x - 3) = 0. A product is zero only when one of its factors is zero, so x = 2 or x = 3. Hence A = \{2, 3\}.

B = \{2, 3\} as given.

C = \{3, 2, 3\} has the different objects 3 and 2 (the repeat adds nothing), so C = \{2, 3\}.

D: the whole numbers less than 4 that are prime are 2 and 3. The number 1 is not prime, and 4 is not less than 4. So D = \{2, 3\}.

All four have exactly the elements 2 and 3, so all four are the same set. Four different descriptions, one set: the rule for equality looks only at the elements.

Example 6

Sets of letters

The word MISSISSIPPI has 11 letters. Write the set of letters it uses and count its elements. Then decide which of the words TOOL, LOOT and TOLL use the same set of letters.

Solution

The set of letters keeps each different letter once. Reading through MISSISSIPPI, the different letters are M, I, S and P, so the set is \{M, I, S, P\} and it has 4 elements, even though the word has 11 letters. (Counting letters in a word counts positions. Counting elements of a set counts different objects.)

For the three words:

\begin{aligned} \text{TOOL} &\to \{T, O, L\} \\ \text{LOOT} &\to \{L, O, T\} \\ \text{TOLL} &\to \{T, O, L\} \end{aligned}

Each set has the letters T, O and L and nothing else, and order does not matter, so all three words use the same set of letters.

That does not mean they use the same letters the same number of times. TOOL and LOOT each have one T, two O’s and one L. TOLL has one T, one O and two L’s. A set cannot see that difference, since it forgets repeats. When the repeats matter, a set is the wrong object.

Example 7

Finding an unknown from a set equation

Find every value of x for which \{x, 5\} = \{5, 2x - 3\}.

Solution

If the two sets are equal, every element of each is an element of the other. Look at the element x of the left set. It must be an element of the right set, so either x = 5 or x = 2x - 3. Check each case.

Case x = 5. The left set is \{5, 5\} = \{5\}. The right set is \{5, 2(5) - 3\} = \{5, 7\}. The number 7 is in the right set and not in the left, so the sets are not equal. This case fails.

Case x = 2x - 3. Subtracting x from both sides gives x = 3. The left set is \{3, 5\}. The right set is \{5, 2(3) - 3\} = \{5, 3\}. These have the same elements, so they are equal.

So the only value is x = 3.

Boundaries

A set needs a definite yes or no. “The tall students in this class” does not describe a set, because for a student of medium height there is no answer to “is this student tall?”. Give a cutoff, such as “students taller than 160 cm”, and every student gets a clear yes or no, so a set exists.

Equal sets may be described in very different ways, but they are equal only when the elements match. The set of solutions of x^2 - 5x + 6 = 0 and the set of primes less than 4 look nothing alike, and they are the same set. On the other hand, \{1, 2\} and \{1, 2, 3\} look almost alike and are different sets, since 3 is in one and not the other.

Order and repeats are forgotten on purpose. When they matter, a different object is needed. A collection that keeps repeats but ignores order is called a multiset: the multiset holding 1, 2, 2 differs from the one holding 1, 2. A collection where order counts is a sequence, and a sequence of length two is an ordered pair, written with parentheses: (1, 2) differs from (2, 1). Unless a text says otherwise, braces mean a set, and a set keeps neither order nor repeats.

Not every description makes a set. Suppose there were a set R of all sets that are not elements of themselves. Ask whether R \in R. If it is, then R fails its own rule, so R \notin R. If it is not, then R meets its own rule, so R \in R. Either answer contradicts itself. This is called Russell’s paradox, and it is why the theory of sets places limits on which collections are allowed to be sets.

Where this goes next

Membership is the single building block. A subset is defined through it: A is a subset of B when every element of A is an element of B. The empty set is the set that nothing belongs to. Listing elements is roster notation, and describing them by a test, as in the remainder example, is describing a set by a rule.

The equality rule becomes a method of proof in when two sets are equal: to show two sets are equal, show each is inside the other. Counting how many different elements a set has is cardinality, and combining sets is union and intersection, which Venn diagrams picture. All of these are part of set notation.

Exercises

Reading membership

Let A = \{1, 3, 5, 7, 9\}. Say whether each statement is true or false: (a) 5 \in A, (b) 6 \in A, (c) 9 \notin A, (d) 0 \notin A.
Let V = \{a, e, i, o, u\}. List the different letters of the word “mathematics” that are elements of V.
Let C be the set of whole numbers (0, 1, 2, 3, \dots) that are less than 6. Which of -1, 0, 5, 6 and 6.5 are elements of C?

Counting and equal sets

How many elements does each set have? (a) \{4, 4, 4\}, (b) \{1, 2, 2, 3, 3, 3\}, (c) \{a, b, \{a, b\}\}, (d) \{\varnothing\}, (e) \{\ \}.
Which of these sets are equal to \{2, 5, 9\}? (a) \{9, 5, 2\}, (b) \{2, 5, 9, 5\}, (c) \{2, 5\}, (d) \{2, 5, 9, 0\}, (e) \{5, 2, 9, 2, 9\}.
Write the set of letters used in the word BANANA and the set of letters used in the word LETTER, and give the number of elements of each.

Sets inside sets

Let S = \{1, \{1\}, \{1, 2\}, 2\}. How many elements does S have? True or false: (a) 1 \in S, (b) \{1\} \in S, (c) \{2\} \in S, (d) \{1, 2\} \in S, (e) \varnothing \in S.
Let T = \{\{1, 2\}, \{3\}\}. How many elements does T have? True or false: (a) 1 \in T, (b) 3 \in T, (c) \{3\} \in T, (d) \{1, 2\} \in T.
How many elements does \varnothing have, and how many does \{\varnothing\} have? True or false: (a) \varnothing \in \{\varnothing\}, (b) \varnothing \in \varnothing.
Write a set with exactly three elements, exactly one of which is itself a set with two elements.

Rules and unknowns

Let R be the set of whole numbers that leave remainder 1 when divided by 4. Which of 1, 5, 14, 21, 100 and 101 are elements of R? List the elements of R that are less than 30.
Let P be the set of prime numbers less than 20. List its elements, say how many there are, and say whether 1 \in P.
Find every value of x for which \{2, x\} = \{x + 1, 5\}.
Two numbers m and n satisfy \{m, n\} = \{3, 10\}. Find m + n and mn, and explain why m and n cannot be equal.
Write the set of solutions of x^2 - 7x + 12 = 0 and compare it with \{3, 4\}. Then write the set of solutions of x^2 - 6x + 9 = 0 and say how many elements it has.

Reasoning

Using only the statement “two sets are equal exactly when they have the same elements”, explain why \{1, 2, 3\} and \{3, 2, 1\} are the same set.
Explain why 2 \in \{1, 2, 3\} is true but 2 \in \{\{1, 2\}, 3\} is false.
“The tall students in this class” does not yet describe a set. Say why, and give a change that does describe one.
Give two different-looking descriptions of the set \{2, 4, 6\}, neither of them a listing in a different order.
Explain why \{1, 2\} and \{\{1\}, \{2\}\} are not equal, even though both are built from 1 and 2.
The points (1, 2) and (2, 1) are in different places on a grid, but \{1, 2\} = \{2, 1\}. Explain why braces are the wrong tool for naming a point.

Answers

(a) true, (b) false, (c) false, (d) true. The list A contains 5 and 9, and it does not contain 6 or 0.
a, e and i. The letters of “mathematics” are m, a, t, h, e, m, a, t, i, c, s. Of these only a, e and i are vowels, and a is listed once even though it appears twice.
0 and 5. The number -1 is not a whole number, 6 is not less than 6, and 6.5 is neither a whole number nor less than 6.
(a) 1, (b) 3, (c) 3, (d) 1, (e) 0. In (a) the repeats collapse to one element, 4. In (b) the different objects are 1, 2 and 3. In (c) the elements are a, b and the set \{a, b\}. In (d) the only element is the empty set. In (e) nothing is listed.
(a), (b) and (e). Each of these has exactly the elements 2, 5 and 9. The set in (c) is missing 9, and the set in (d) has an extra element, 0.
BANANA uses \{B, A, N\}, which has 3 elements. LETTER uses \{L, E, T, R\}, which has 4 elements. The repeated letters (the A and N in BANANA, and the T and E in LETTER) are counted once.
S has 4 elements. (a) true, (b) true, (c) false, (d) true, (e) false. The four elements are 1, \{1\}, \{1, 2\} and 2. The set \{2\} is not on that list, and neither is \varnothing.
T has 2 elements. (a) false, (b) false, (c) true, (d) true. The elements are \{1, 2\} and \{3\}. The numbers 1 and 3 are inside those sets, not directly in T.
\varnothing has 0 elements and \{\varnothing\} has 1. (a) true, (b) false. The one element of \{\varnothing\} is \varnothing, so \varnothing \in \{\varnothing\}. Nothing is an element of \varnothing, so \varnothing \in \varnothing is false.
One answer is \{1, 2, \{3, 4\}\}. Its three elements are 1, 2 and the set \{3, 4\}, and only \{3, 4\} is a set with two elements. Any set of this shape works.
1, 5, 21 and 101 are elements. 14 leaves remainder 2 and 100 leaves remainder 0. The elements below 30 are 1, 5, 9, 13, 17, 21, 25, 29.
P = \{2, 3, 5, 7, 11, 13, 17, 19\}, which has 8 elements. 1 \notin P because 1 is not a prime (one is neither prime nor composite).
There is no such x. The element 2 of the left set must be in the right set, so x + 1 = 2 or 5 = 2. The second is false, so x = 1. But then the left set is \{2, 1\} and the right set is \{2, 5\}, and 1 is not in the right set. So no value works.
m + n = 13 and mn = 30. If m = n then \{m, n\} has one element, but \{3, 10\} has two. So m and n are 3 and 10 in some order, and a sum and a product do not depend on order.
x^2 - 7x + 12 = (x - 3)(x - 4) = 0 gives \{3, 4\}, the same set. And x^2 - 6x + 9 = (x - 3)^2 = 0 gives only x = 3, so the set is \{3\}, which has 1 element.
The set \{1, 2, 3\} has the elements 1, 2 and 3. The set \{3, 2, 1\} has the elements 3, 2 and 1. These are the same three objects, so the two sets have the same elements. By the statement, they are equal. The order of writing is not an element of either set.
The elements of \{1, 2, 3\} are 1, 2 and 3, so 2 is one of them. The elements of \{\{1, 2\}, 3\} are the set \{1, 2\} and the number 3. The number 2 is inside the set \{1, 2\}, but it is not directly one of the two elements, and it is not equal to either of them.
A set needs a clear yes or no for every object, and “tall” does not give one: a student of medium height is neither clearly tall nor clearly not. A cutoff fixes it, for example “students taller than 160 cm”. Then each student is either in the set or not.
Sample answer: “the even whole numbers between 1 and 7”, and “the solutions of x^3 - 12x^2 + 44x - 48 = 0”. Both have exactly the elements 2, 4 and 6. Many other answers work; all that is needed is that the elements match.
The set \{1, 2\} has two elements, the numbers 1 and 2. The set \{\{1\}, \{2\}\} has two elements too, but they are the sets \{1\} and \{2\}. The number 1 is an element of \{1, 2\}, but it is neither of the two elements of \{\{1\}, \{2\}\}: a number is a plain object, not a set, so 1 is not the set \{1\} and not the set \{2\}. The two sets do not have the same elements, so they are not equal.
Braces forget order, and the two points differ only in order. Since \{1, 2\} and \{2, 1\} are equal, braces cannot tell the point (1, 2) from the point (2, 1). A notation that keeps order is needed, and that is what an ordered pair is.