Set
For the computer science term, see Sets (ADT).
A set is an unordered group of items (called elements). For example, \(\{\text{cat}, \text{dog}, \text{fish}, \text{bird}\}\) is a set of animals, \(\{2,4,6,8,10\}\) is a set of even numbers, and \(\{a, b, c, d\}\) is a set of letters. Though sets are pretty simple data structures, they are important for understanding concepts in combinatorics, probability, and number theory.
Definition of a Set
A set is an unordered group of elements denoted by a sequence of items (separated by commas) between curly braces "\(\{\)" and "\(\}\)".
What does it mean to be unordered?
Sets are not organized in any particular way. For example, the set \(A = \{1,2,3,4,5\}\) appears to be the set of ordered numbers between 1 and 5, but this set is actually equivalent to \(B = \{2,3,1,5,4\}\). The order of elements in a set does not matter. Two sets are equal if they contain all of the same elements.
Repeated elements make no difference in a set. \(A = \{1,1,1,1\}\) is equal to \(B = \{1\}\). In fact, sets are generally not written to include repeated elements.
Operations with Sets
There are several useful operations one can use to combine, compare, and analyze sets.
Union: The union of two sets, denoted \( \cup\) (which is called a cup), refers to the set of all the elements that are in at least one of the two sets. For example, \( \{1,2,3\} \cup \{3,4,5\} = \{1,2,3,4,5\}.\) In Boolean logic, union is expressed as a logical OR.
Intersection: The intersection of two sets, denoted \( \cap\) (which is called a cap), refers to the set of the elements that are in both sets. For example, \( \{1,2,3\} \cap \{3,4,5\} = \{3\}.\) In Boolean logic, intersection is expressed as a logical AND.
Complement (Absolute): Denoted \( ^c\), the absolute complement refers to the set of all the elements that are not in a set. If we consider the universal set, \(U\), as the set of all integers, \( \{ 1, 2, 3 \}^c \) would represent all integers except for 1, 2, and 3. In Boolean logic, complement is expressed as a logical NOT.
Complement (Relative): Relative complement, denoted \( \backslash \), refers to the set of elements that are in the first set but not in the second. For example, \( \{1,2,3\} \backslash \{3,4,5\} = \{1,2\}.\) Relative complement can also be expressed by the minus sign, and thus \(\{1,2,3\}-\{3,4,5\}=\{1,2\}.\)
Symmetric Difference: Symmetric difference, denoted \( \triangle \), refers to the set of elements which are in one of the two sets but not both. For example, \( \{1,2,3\} \triangle \{3,4,5\} = \{1,2,4,5\}.\) In Boolean logic, symmetric difference is expressed as a logical XOR.
What is \( \{2,4,6\} \cup \{3,5,7\} ?\)
The symbol \(\cup\) refers to the union of the two sets.
Thus, \( \{2,4,6\} \cup \{3,5,7\} \) is \( \{2,3,4,5,6,7\}.\ _ \square \)
Given the following two sets
\[ \begin{align} A &= \{ 2, a^2-4a+7 \} \\ B &= \{ a+1, a^2+1, a^2-1 \}, \end{align} \]
if \( A \cap B = \{4\} ,\) what is \(a?\)
From \( A \cap B = \{4\}, \) we know that both sets \(A\) and \(B\) must have \(4\) as an element. Therefore, for set \(A\) we have
\[ \begin{align} a^2-4a+7&=4 \\ (a-1)(a-3)&=0 \\ \Rightarrow a&= 1\text{ or }3. \end{align} \]
If the value of \(a\) is 1, set \(B\) is
\[ \begin{align} B &= \{a+1, a^2+1, a^2-1\} \\ &= \{1+1, 1^2+1, 1^2-1\} \\ &=\{ 2,2,0\} . \end{align} \]
Then \( A \cap B = \{2\} \neq \{4\}. \)
If the value of \(a\) is 3, set \(B\) is
\[ \begin{align} B &= \{a+1, a^2+1, a^2-1\} \\ &= \{2+1, 2^2+1, 2^2-1\} \\ &=\{ 4,10,8\} . \end{align} \]
Then \( A \cap B = \{4\}. \)
Thus, the value of \(a\) that satisfies \( A \cap B = \{4\}\) is \(a=3.\ _ \square \)
What is \( \{2,4,6,8,10,12\} \triangle \{3,6,9,12,15\} ?\)
The symbol \(\triangle\) denotes symmetric difference, which means the set of elements which are in one of the two sets but not both.
Thus, \( \{2,4,6,8,10,12\} \triangle \{3,6,9,12,15\} \) is \( \{ 2,3,4,8,9,10,15 \} .\ _ \square \)
Set Laws
De Morgan's laws are useful for showing equivalencies, transforming, and simplifying logical expressions.
- De Morgan's First Law:
It states that the complement of the union of two sets is the intersection of their complements. For two sets \(A\) and \(B,\) \((A \cup B)^c=(A)^c\cap (B)^c.\)
In Boolean logic, De Morgan's first law is expressed as \(\overline{A + B} = \overline{A} * \overline{B}.\) - De Morgan's Second Law:
It states that the complement of the intersection of two sets is the union of the complements. Specifically, \( (A \cap B)^c = A^c\cup B^c. \)
In Boolean logic, De Morgan's second law is expressed as: \(\overline{A * B} = \overline{A} + \overline{B}\).
Given the following, use De Morgan's second law to determine \(A^c\cup B^c:\)
- \(U = \{1,2,3,4,5,6,7,8,9\},\) where \(U\) is the set of all possible values for this problem
- \(A=\{2,5,7,3,1\}\)
- \(B=\{9,8,7,5,2\}\).
De Morgan's second law is \( (A \cap B)^c = A^c\cup B^c. \) Since we are looking for \(A^c\cup B^c \), we will first determine the left side of the equation, \( (A \cap B)^c\).
To find \( (A \cap B)^c\), determine \( (A \cap B):\) \( (A \cap B)\) is the set of elements that are in both \(A\) and \(B,\) so \( (A \cap B) = \{2,5,7\}.\)
To find \( (A \cap B)^c\), compare the elements in \( (A \cap B)\) with the elements in \(U\), and the elements in \( (A \cap B)^c\) will be the elements that are in \(U\) but not in \( (A \cap B)\). So, \( (A \cap B)^c = \{1,3,4,6,8,9\}\).
We know from De Morgan's second law that \(A^c\cup B^c \) = \( (A \cap B)^c\). In other words, elements that are not in both \(A\) and \(B\) must either be missing from \(A\) or \(B\) (or both).
Examine \( (A \cap B)^c = \{1,3,4,6,8,9\}\) for yourself to verify that elements in \( (A \cap B)^c\) are missing from either \(A\) or \(B\) or both. \(_\square\)
Terminology
Here are some important concepts and terms about sets:
Universal Set: Denoted \(U,\) a universal set is the set of all possible elements for a particular problem. For example, if a problem deals only with positive, nonzero integers, \(U = \{1,2,3,4, \dots\}\).
Empty/Null Set: Denoted by \(\{\}\) or \(\phi\), a set is said to be null or empty if it does not contain any elements. For example, if \(A\) is the set of all integers \(x\) that satisfy \(x^2=7,\) then the set \(A\) has no elements, and thus \(A=\phi.\)
Subsets: If every element of a set \(A\) is also a member of the set \(B,\) then we say that \(A\) is a subset of \(B.\) For example if \(A=\{1,2,3\}\) and \(B=\{5,4,3,2,1\},\) then \(A\) is a subset of \(B,\) or \(A \subset B.\) When two sets are equal, they are subsets of each other.
Cardinality: The cardinality of a set \(S,\) written as \(\lvert S\rvert,\) is the number of distinct elements in \(S.\) For example, if \(A\) is the set of all the letters in "Mississippi", then \(A=\{m,i,p,s\},\) and hence \(\lvert A\rvert=4.\)
Inclusion-Exclusion Principle: The inclusion-exclusion principle states that any two sets \(A\) and \(B\) satisfy \(\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert- \lvert A \cap B\rvert .\) In other words, to get the size of the union of sets \(A\) and \(B\), we first add (include) all the elements of \(A\), then we add (include) all the elements of \(B\), and then we remove (exclude) the elements in their intersection \(A \cap B\), since those elements were counted twice \((\)i.e. once for \(A\) and once for \(B).\) For a concrete example, let \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7,8\}\), which gives \(A \cap B=\{4,5\}\). Then \(\lvert A \rvert=5\), \(\lvert B \rvert=5\), and \(\lvert A \cap B \rvert=2\). By the inclusion-exclusion principle, \(\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert- \lvert A \cap B\rvert = 5 + 5 - 2 = 8 ,\) which we can verify directly by counting the elements of \(\lvert A \cup B\rvert =\{1,2,3,4,5,6,7,8\}.\) Note that the elements in the intersection (4 and 5) were counted once in \(A\) and once in \(B\), necessitating their exclusion.
For this problem, the universal set \(U\) is
\[ U = \{ 1,2,3,4,5,6,7,8,9,10 \} ,\]
and its three subsets \( A, B \) and \(C\) are as follows:
\[ \begin{align} A &= \{ 1,2,3,4,5,6,7 \} \\ B &= \{ 2,6,8,9 \} \\ C &= \{ 9, 10 \}. \end{align} \]
Then what is \( (A^{c} \cup B) \backslash C ?\)
The symbol \(A^{c} \) means the set of all elements that are not in \(A.\) Since \( A = \{ 1,2,3,4,5,6,7 \}, \) the set \( A^{c} \) is
\[ A^{c} = \{ 8,9,10\} .\]
Then, \( A^{c} \cup B \) is
\[ A^{c} \cup B = \{8,9,10\} \cup \{ 2,6,8,9 \} = \{ 2,6,8,9,10 \}. \]
Therefore, \( (A^{c} \cup B) \backslash C \) is
\[ (A^{c} \cup B) \backslash C = \{ 2,6,8,9,10 \} \backslash \{ 9, 10 \} = \{ 2,6,8 \}.\ _\square\]