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.

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.

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{aligned} A &= \{ 2, a^2-4a+7 \} \\ B &= \{ a+1, a^2+1, a^2-1 \}, \end{aligned}$

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{aligned} a^2-4a+7&=4 \\ (a-1)(a-3)&=0 \\ \Rightarrow a&= 1\text{ or }3. \end{aligned}$

If the value of $a$ is 1, set $B$ is

$\begin{aligned} B &= \{a+1, a^2+1, a^2-1\} \\ &= \{1+1, 1^2+1, 1^2-1\} \\ &=\{ 2,2,0\} . \end{aligned}$

Then $A \cap B = \{2\} \neq \{4\}.$

If the value of $a$ is 3, set $B$ is

$\begin{aligned} B &= \{a+1, a^2+1, a^2-1\} \\ &= \{3+1, 3^2+1, 3^2-1\} \\ &=\{ 4,10,8\} . \end{aligned}$

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$

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$

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{aligned} A &= \{ 1,2,3,4,5,6,7 \} \\ B &= \{ 2,6,8,9 \} \\ C &= \{ 9, 10 \}. \end{aligned}$

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$