Logic and Set Theory
2.2 Describing Sets
What Is a Set?
Mathematics is largely about studying collections of things and the relationships between them. The most fundamental such collection is a set.
Definition: Set and Element
A set is a collection of objects. The objects in a set are called elements.
Sets are written using curly brackets. For example, $S =\{a, b, c, d\}$ is a set containing the letters $a$, $b$, $c$, and $d$. We write $a \in S$ to say that $a$ is an element of $S$, and $e \notin S$ to say $e$ is not in $S$.
A (very) Brief History of Numbers
Long before algebra existed, people needed numbers. At first, people just needed to count, then to measure, then to describe debts and portions of whole things. Each new type of real-world problem demanded a new type of number. There are several number sets that have standardized symbols used throughout mathematics.
| Name | Examples | Type of Problem | Symbol |
|---|---|---|---|
| Natural Numbers | $$1, 2, 3, 4, \ldots$$ | $$2 + x = 4$$ | $\mathbb{N}$ |
| Whole Numbers | $$0, 1, 2, 3, 4, \ldots$$ | $$5 + x = 5$$ | $\mathbb{W}$ |
| Integers | $$\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$$ | $$40 + x = 15$$ | $\mathbb{Z}$ |
| Rational Numbers | $$\frac{1}{2},\ \frac{1}{3},\ \frac{5}{7}$$ | $$4x = 19$$ | $\mathbb{Q}$ |
| Irrational Numbers | $$\pi,\ e,\ \sqrt{2}$$ | $$x^2 = 2$$ | $$\mathbb{R} \setminus \mathbb{Q}$$ |
| Real Numbers | All of the above | All of the above | $\mathbb{R}$ |
These number systems nest inside one another: $\mathbb{N} \subset \mathbb{W} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$. The $\subset$ symbol just means that the first set is contained within the second. Each set was invented to solve a problem the previous one couldn't handle.
Example: Finding which number set applies
Try to solve each of these problems and decide which number set above the solution belongs to.
- Alice bought 10 items off of Amazon, but only 8 were delivered. How many are missing?
- $7 + x = 2$
- What is the length of the side of a square whose area is 4?
- What is the length of the side of a square whose area is 5?
- Steve ate 3 of the 8 slices of a pizza. How much of the pizza is left?
Show Solution
- $10 - 8 = 2$ items are missing. $2 \in \mathbb{N}$.
- $x = -5$. Negative numbers aren't in $\mathbb{N}$ or $\mathbb{W}$, so $x \in \mathbb{Z}$.
- Side $= \sqrt{4} = 2$. $2 \in \mathbb{N}$.
- Side $= \sqrt{5}$. Since 5 is not a perfect square, $\sqrt{5}$ cannot be written as a fraction. It's irrational. $\sqrt{5} \in \mathbb{R}$.
- $\frac{5}{8}$ of the pizza remains. $\frac{5}{8} \in \mathbb{Q}$.
MyOpenMath: Number Sets
Set-Builder Notation
There are two common ways to describe a set. The roster method (or listing) simply lists the elements. Set-builder notation describes the rule an element must satisfy to belong to the set.
Both methods can describe the same set:
| Method | Example |
|---|---|
| Roster | $$S =\{1, 2, 3, 4\}$$ |
| Set-builder | $$S =\{x \mid (x \in \mathbb{N}) \land (x < 5)\}$$ |
Set-builder notation is read as: "$S$ is the set of all elements $x$ such that $x$ is a natural number and $x$ is less than 5." The vertical bar $\mid$ means "such that." The requirements on the right must completely and exactly describe the elements of the set.
Example: Writing sets in set-builder notation
Use set-builder notation to write the following sets.
- $\{2, 4, 6, 8, 10, \ldots\}$
- $\{1, 3, 5, 7, 9, \ldots\}$
- $\{1, 4, 7, 10, \ldots\}$
Show Solution
- $\{x \mid x = 2n,\ n \in \mathbb{N}\}$, the even natural numbers.
- $\{x \mid x = 2n - 1,\ n \in \mathbb{N}\}$, the odd natural numbers.
- $\{x \mid x = 3n - 2,\ n \in \mathbb{N}\}$, starts at 1 and increases by 3 each step.
MyOpenMath: Set-Builder Notation
Example: Listing elements from set-builder notation
Write each of these sets by listing their elements.
- Set $$C = \{x = 2k + 1 \mid k = 3, 4, 5\}$$
- Set $$D = \{x \mid x \text{ is an even natural number less than 8}\}$$
- Set $$T = \left\{x = \dfrac{n(n+1)}{2}\ \middle|\ n \in \mathbb{N}\right\}$$
Show Solution
- Plug in $k = 3, 4, 5$: $2(3)+1 = 7$, $2(4)+1 = 9$, $2(5)+1 = 11$. So $C =\{7, 9, 11\}$.
- $D =\{2, 4, 6\}$.
- These are the triangular numbers from the previous chapter: $T =\{1, 3, 6, 10, 15, \ldots\}$ (substitute $n = 1, 2, 3, \ldots$).
MyOpenMath: Set-Builder Notation
Equality and Equivalence
Equal Sets
Definition: Equal Sets
Two sets are equal if they contain exactly the same elements. Formally, $A = B$ if and only if every element of $A$ is in $B$ and every element of $B$ is in $A$:
$$A = B \iff (\forall x \in A,\ x \in B)\ \land\ (\forall x \in B,\ x \in A)$$
Fact: Order and repetition don't matter in sets
In a set, order is irrelevant and repetition doesn't count. If $A =\{1, 1, 2, 3\}$, it is best written $A =\{1, 2, 3\}$. And if $B =\{3, 1, 2\}$, then $A = B$.
One-to-One Correspondence
Equal sets have the same elements. But sometimes we just care whether two sets have the same size. That's where one-to-one correspondence comes in.
Definition: One-to-One Correspondence
There is a one-to-one correspondence between two sets if each element of one set can be paired with exactly one element of the other, with nothing left out or doubled up.
As an example, consider $$S =\{1, 2, 3, 4, 5\}$$ and $$R =\{\text{Adam, Cathy, Mandy, Reggie, Daniel}\}$$
| $S$ | $R$ | Pair |
|---|---|---|
| 1 | Adam | (1, Adam) |
| 2 | Cathy | (2, Cathy) |
| 3 | Mandy | (3, Mandy) |
| 4 | Reggie | (4, Reggie) |
| 5 | Daniel | (5, Daniel) |
Every element on each side is matched exactly once, this is a one-to-one correspondence.
Example: Counting one-to-one correspondences
Consider the set of 3 people $\{A, B, C\}$ and the set of swimming lanes $\{1, 2, 3\}$.
- Find all of the one-to-one correspondences between the two sets.
- How many correspondences are there?
- Find the number of one-to-one correspondences between two sets with 4 elements each.
Show Solution
- There are $3! = 6$ ways to assign lanes to people: $(A1, B2, C3)$, $(A1, B3, C2)$, $(A2, B1, C3)$, $(A2, B3, C1)$, $(A3, B1, C2)$, $(A3, B2, C1)$.
- There are 6 correspondences.
- For 4 elements: $4! = 24$.
Fact: Fundamental Principle of Counting
In the above example, we used something called the fundamental principle of counting. We will use it frequently and it merits a formal statment here:
If an event $M$ can happen $m$ ways and event $N$ can happen $n$ ways, then both happening in sequence can occur $m \cdot n$ ways.
Example: Outfit combinations
If you have 4 shirts, 3 pairs of pants, 5 hats, and 2 pairs of shoes, how many distinct outfits could you make?
Show Solution
$4 \times 3 \times 5 \times 2 = \mathbf{120}$ outfits.
Equivalent Sets
Definition: Equivalent Sets
Two sets $A$ and $B$ are equivalent, written $A \sim B$, if and only if there exists a one-to-one correspondence between them.
Equal sets are always equivalent, but equivalent sets are not necessarily equal.
Example: Equal vs. equivalent
Compare each of these sets using the terms equal and equivalent:
- $A =\{p, q, r, s\}$
- $B =\{a, b, c\}$
- $C =\{x, y, z\}$
- $D =\{b, a, c\}$
Show Solution
- $B = D$: same elements, just listed in different order. They are equal (and therefore also equivalent).
- $B \sim C$: both have 3 elements, but the elements differ. They are equivalent but not equal.
- $A$ has 4 elements while $B$, $C$, and $D$ each have 3. $A$ is neither equal nor equivalent to any of the others.
MyOpenMath: Equal, Equivalent, or Neither
Cardinal Numbers
Definition: Cardinal Number
The cardinal number of a set is the number of elements in the set, denoted $n(S)$ for a set $S$.
Example: Finding cardinal numbers
Find the cardinal number of each set.
- Set $$A =\{p, q, r, s\}$$
- Set $$B =\{19, 20, 21, \ldots, 99\}$$
- Set $$C =\{x \mid x \text{ is a letter of the English alphabet}\}$$
- Set $$D =\{x \mid x = x + 1 \land x \in \mathbb{N}\}$$
Show Solution
- Counting the elements, $$n(A) = 4$$
- From 19 to 99 inclusive: $$99 - 19 + 1 = \mathbf{81}$$
- There are 26 letters in the English alphabet: $$n(C) = 26$$
- The equation $$x = x + 1$$ has no solution. That means no natural number satisfies it. So $$D = \emptyset$$ and $$n(D) = 0$$
MyOpenMath: Equality, Equivalence, and Cardinal Numbers
Universal and Empty Sets, and Complements
Definition: Empty and Universal Sets
The empty set is the set with no elements, denoted $\emptyset$ or $\{\}$.
The universal set $U$ is the set that contains everything under consideration in a given context.
Definition: Complement
The complement of a set $A$, written $\bar{A}$ (also written $A'$ or $A^c$), is the set of all elements in the universal set $U$ that are not in $A$:
$$\bar{A} =\{x \mid x \in U \land x \notin A\}$$
Note that $\bar{U} = \emptyset$ and $\bar{\emptyset} = U$, the complement of everything is nothing, and the complement of nothing is everything. The complement is our set equivalent version of the not operation in logic.
Example: Finding complements
- If $$U =\{1, 2, 3, \ldots, 10\}$$ find $\bar{A}$ where $$A =\{1, 5, 7, 10\}$$
- If $$U =\{a, b, c, d\}$$ and $$B =\{c, d\}$$ find $\bar{B}$, $\bar{U}$, and $\bar{\emptyset}$.
- If $$U =\{x \mid x \text{ is an animal in the zoo}\}$$ and $$S =\{x \mid x \text{ is a snake in the zoo}\}$$ describe $\bar{S}$ in words.
- If $U = \mathbb{N}$ $$E =\{2, 4, 6, 8, \ldots\}$$ and $$O =\{1, 3, 5, 7, \ldots\}$$ find $\bar{E}$ and $\bar{O}$.
Show Solution
- Everything in $U$ that is not in $$A=\bar{A} =\{2, 3, 4, 6, 8, 9\}$$
- $$\bar{B} =\{a, b\}$$ $$\bar{U} = \emptyset$$ $$\bar{\emptyset} = U =\{a, b, c, d\}$$
- $$\bar{S} =\{x \mid x \text{ is an animal in the zoo that is not a snake}\}$$
- $\bar{E} = O$ (the odd natural numbers) and $\bar{O} = E$ (the even natural numbers). Together the odds and evens partition $\mathbb{N}$ perfectly.
MyOpenMath: Complements and the Universal Set
Subsets and Proper Subsets
Subsets
Definition: Subset
$B$ is a subset of $A$, written $B \subseteq A$, if and only if every element of $B$ is also an element of $A$. Formally:
$$B \subseteq A \leftrightarrow ((x \in B) \rightarrow (x \in A))$$
Note that $\emptyset \subseteq A$ for any set $A$, the empty set is a subset of every set. And every set is a subset of itself: $A \subseteq A$.
Example: Listing all subsets
List all of the subsets of $S =\{a, b, c\}$.
Show Solution
A set with 3 elements has $2^3 = 8$ subsets:
$$\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$$
MyOpenMath: Picking Subsets
Proper Subsets
Definition: Proper Subset
$B$ is a proper subset of $A$, written $B \subset A$, if every element of $B$ is in $A$ and $B \neq A$. In other words, $B$ is a subset that is strictly smaller, it's missing at least one element of $A$.
The Power Set
Theorem: Power Set
Given a set $A$, the power set of $A$, written $2^A$, is the set of all subsets of $A$. Its cardinal number is:
$$n(2^A) = 2^{n(A)}$$
This is a direct result of out counting principle mentioned earlier. If you have a set with 3 elements, say $n(A) = 3$, then when picking subsets you have to make several decisions. First, do you include the first element or not? Then the next element, and so on. That means you have 2 options to pick from and you're making that decison 3 times. There are $$2\cdot 2 \cdot 2 = 2^3 = 8$$ total subsets and $2^3 - 1 = 7$ proper subsets (all subsets except $A$ itself).
Example: Counting subsets
How many subsets does $$A =\{x \mid x = 2n+1,\ n \in\{1, 2, 3, 4, 5, 6, 7\}\}$$ have? How many proper subsets?
Show Solution
First find what $A$ actually is: plugging in $n = 1$ through $7$ gives $$A =\{3, 5, 7, 9, 11, 13, 15\}$$ so $n(A) = 7$.
- Total subsets: $$2^7 = \mathbf{128}$$
- Proper subsets: $$2^7 - 1 = \mathbf{127}$$
Example: Subset relationships
Let $$A =\{1, 2, 3, 7, 15\}$$ $$B =\{1, 3\}$$ and $$P =\{x \mid x = 2^n - 1,\ n \in \mathbb{N}\}$$
- Identify all subset relationships among these sets.
- Identify all proper subset relationships.
- If $$C =\{x \mid x = 2n,\ n \in \mathbb{N}\}$$ and $$D =\{x \mid x = 4n,\ n \in \mathbb{N}\}$$ show that one is a subset of the other.
Show Solution
- (numbers of the form $2^n - 1$) $$P =\{1, 3, 7, 15, 31, \ldots\}$$ Both 1 and 3 are in $A$, so $B \subseteq A$. Both 1 ($= 2^1 - 1$) and 3 ($= 2^2 - 1$) are in $P$, so $B \subseteq P$.
- Since $B \neq A$ and $B \neq P$, both are proper subsets: $B \subset A$ and $B \subset P$.
- Every element of $D$ has the form $4n = 2(2n)$, which is also of the form $2k$ with $k = 2n$. So every element of $D$ is in $C$, meaning $D \subseteq C$. But $C$ contains elements like $2$ (with $n = 1$) that are not multiples of 4, so $D \neq C$. Therefore $D \subset C$ (a proper subset).