Set equality

We will often need to test or prove that two given collections of items are equal. In some cases the sets are expressed differently, and in other instances the equality of the sets will “seem” obvious. In either case, an argument must be made that demonstrates that the two sets are equal.

Before delving into the definition for set equality and the essentials of showing two sets are equal, consider a closely related concept in mathematics. The following is a statement that two objects are equal. These objects are expressions in the current case, and the objects are different in their appearance but we are given that they are equal. If we assume this to be true, the usual next step is to write a new statement about the value(s) of \(x\) that must then be true. Specifically, what are the values of \(x\)?

The next true statement could be found by multiplying through by the least common denominator of all the terms.

Again, the two expressions look different but are considered equivalent. The truth of this statement implies the truth of the statement:

\(10x = -2\) and also the truth of: \(x = \frac {-1}{5}\)

The progression of statements that must be true if equality holds for the initial statement is a basic “proof.” Now to define what it means for objects to be equal when the objects are sets.

For sets, the definition of equality is written with two similar statements. Sets \(A\) and \(B\) are equivalent if both the statements are true: \(\text{If the element } x \text{ is in the set } A, \text{ then the element } x \text{ is in the set } B.\) \(\text{If the element } x \text{ is in the set } B, \text{ then the element } x \text{ is in the set } A.\)

Both statements relay information about the containment of one set in the other, and we can alternatively say that the sets \(A\) and \(B\) are equal if both the following statements are true: \(\text{The set } B \text{ is contained in the set } A\) \(\text{The set } A \text{ is contained in the set } B\)

Using the notation \(B \subseteq A\) to mean that the set \(B\) is contained in the set \(A,\) we can further reduce the entire definition of set equality to:

Example 1: For set \(A = \{1, 2, 3, 4\}\) and set \(\emptyset = \{ \},\) the two sets are defined by enumerating their elements, and visual inspection shows that these two sets are not equal. Afterall, the definiton of equality requires that \(\emptyset\) be contained in \(A.\) This is true. So if we suspect that the two sets are not equal, you need to show the other statement, \(A \subseteq \emptyset\) is false. Since the element 1 is in \(A\) and 1 is not in \(\emptyset,\) the set \(A\) is not contained in \(\emptyset.\) The definition is not a true statement, so the sets are not equal.

Here is another example where both of the sets are finite and defined by listing out their respective elements.

Example 2: Let \(A = \{0, 1\}\) and \(B = \{0, 2\}.\) Note that the intersection of the sets, \(A \cap B,\) is nonempty since the element \(0\) is in both \(A\) and \(B.\) However, there is an element in \(A,\) the element \(1,\) that is not in the set \(B.\) Thus \(A\) is not contained in \(B.\) We already have a false statement in the definition of equal sets, so we have proven that \(A\) is not equal to \(B.\)

In the previous examples, it was proven that the given sets are not equal by showing that one of the statements in the definition is a false statement. The next example will show how to prove that two sets are equal using the defintion.

Example 3: Let \(Z_2\) be the collection of all remainders when an integer is divided by 2. For example, the remainder when \(7\) is divided by \(2\) is 1 since \(5 = 2*3 + 1.\) For reference later, the number \(3\) is refered to as the quotient. Since \(1\) satisfies the defintion of the set for \(Z_2,\) \(1\) is in the set. Let \(R = \{0,1\}\). Prove that \(Z_2\) and \(R\) are equivalent sets.

Proof: (statement \(Z_2\) is contained in \(R\)) If \(x\) is in the set \(Z_2,\) then there is an integer, say \(z \in Z\) so that \(x\) is the remainder when \(z\) is divided by \(2.\) Because it is true that \(x\) is a remainder when \(z\) is divided by \(2\) means that it is true that there is an integer \(q \in Z,\) that acts as the quotient in the expression: \(z = 2*q + x\).

The previous statement’s truth implies that \(x <= 2.\) If this were not the case, then we could half a number with more than one outcome, which is not true in our usual perspective of the world. It also follows from \(x\) being a remainder, that \(0 <= x.\) So now we know that \(x \in {0,1} = R.\)

(statement \(R\) is contained in \(Z_2\)) If \(x\) is in the set \(R,\) then \(x = 0\) or \(x = 1.\) In the case that \(x = 0,\) since \(2 = 2 * 1 + 0,\) \(0\) is the remainder when \(2\) is divided by \(2.\) So, \(0\) is in \(Z_2\) by the definition of \(Z_2.\) In the same way, \(3 = 2*1 + 1\) so that \(1\) is the unique remainder when \(3\) is divided by \(2.\) Since it is true that every element of \(R\) is in \(Z_2\) the truth of the statement that \(R\) is contained in \(Z_2\) is implied.

It has been shown that all statements in the definiton of equality are true for sets \(Z_2\) and \(R.\) The definition of equivalent sets, \(Z_2 = R,\) is thus a true statement.

A very common mistake is for students to assume that if two sets have the same number of elements, same cardinality, then the sets are equal. There are many counter-examples that disprove that statement. That is, examples that show the statement “If A and B are sets with the size of \(A\) equal to the size of \(B,\) then the sets \(A\) and \(B\) are equal. One such example is Example 2, where \(\vert A \vert = 2 = \vert B \vert\) but \(A \neq B\).

We can say that:

If two sets are equal, then the sets must be the same size.

We can reword this true statement with the use of negations to an equivalent statement:

If two sets do not have the same size, then the sets are not equal.

Example 4: The set of all id numbers collected for students has size \(1,324.\) The set of all student records is \(1,320.\)

Here we are less concerned with the sets being the same, especially since the elements are not the same types of objects. But, one would hope that there is a third collection of actual students. Only one of these sets can be “essentially equivalent” to the set of students. If there is a mapping from each student to one and only student record, then the two sets are essentially equal. So, the size of these two sets is the same meaning that the number of students is \(1,320.\) However, it is also hoped that each student has one and only one student id number. This cannot be the case since there are \(1,324\) elements in the set of id numbers which is greater than the number of students.

Back to course home