Naive Set Theory: Definitions
Sets
The Mathematical World
In the previous section on logic, we made the distinction between the real world and the mathematical world. The central difference between the two is that absolute certainty is impossible to obtain in the real world, while it is the only thing we deal with in the mathematical world. But if the real world contains rocks and trees and people and such, what does the mathematical world contain? And how do we know what's in there, anyway?
The answer is that we claim that certain objects exists by definition, which is to say, we simply assume they exists. You can interpret this answer in two ways (at least). The first is to see the mathematical world as a pure creation of our minds, where we can define any such thing to exist that we want. A definitional claim of existence is sufficient for us, and we treat the existence of such objects in the mathematical world as seriously as we treat the existence of grains of sand on the beach. An alternate way to see this answer is for the sake of argument. Perhaps we cannot say whether any such object, in fact, exists, whatever the word exists means in a deeper philosophical sense, but we'll just assume it does and see what we can learn about it.
So, what objects exist in the mathematical world? The answer is simple objects called sets. Axiomatic set theory deals with the exact formulation of such claims, but we will settle for the following simplification: sets exist as we define them to exist, as do the sets that result from the operations we can do on the sets.
Sets
A set is a collection of things. The contents of a set are listed individually, separated by commas, and surrounded by curly braces. For example, the set of primary colors is $\{ \text{red}, \text{yellow}, \text{blue} \}$. We can denote sets with variable names for brevity. Denote the set of books making up the Pentateuch as $P =\{ \text{Genesis}, \text{Exodus}, \text{Leviticus}, \text{Numbers}, \text{Deuteronomy} \}$.
The objects belonging to sets are called elements, and the relationship of belonging is denoted by the $\in$ symbol. For example, $\text{Exodus} \in P$, which is read as "Exodus is in $P$" or "Exodus is a member of $P$" or "Exodus is an element in $P$." A slash through the $\in$ symbol indicates that the object is not an element of the set. For example, $green \notin P$, which is read as "green is not in $P$" or "green is not a member of $P$" or "green is not an element of $P$."
Note: The membership of an element in a set is a proposition. An element is either in a set or not in the set, i.e., it is either true or false that an element belongs to a set.
Uniqueness
An important property of sets is that each element in a set is unique - there are no repeated elements in a set. For example, the set $\{a, b, c, a\}$ is really just an incorrectly written version of the set $\{a, b, c\}$, since the element $a$ is only included once. Additionally, elements may belong to more than one set. The element $a$ belongs to both the set $\{a, b, c\}$ and the set $\{a, e, i, o, u\}$.
Sets containing multiple instances of the same element are called multisets and are studied as a later subject in set theory.
Expressing Sets
Sets need not have all of their elements explicitly listed. For example, the set of natural numbers $\mathbb{N}$ has an infinite number of elements and is written as $\mathbb{N}=\{0, 1, 2, 3, \ldots \}$. Some sets are constructed by elaborate procedures and are simply referred to by standard notations, such as the set of real numbers, $\mathbb{R}$, or the set of complex numbers, $\mathbb{C}$. The empty set has no elements at all, and is denoted by the symbols $\varnothing$. Any set is nonempty if it is not the empty set. Sets can also have other sets as elements. A set containing other sets is called a collection, in order to easily distinguish it from its members and also simply because a collection of sets sounds nicer than a set of sets.
Many sets are constructed with rules. These rules are expressed in a format called set-builder notation, which takes the form of $\{ x : P(x) \}$, where $P(x)$ is a predicate. Read aloud, this expression says "the set of all $x$ such that $P(x)$ is true". For example, $\left\{ x : x \in \mathbb{Z} \text{ and } \frac{x}{2} \in \mathbb{Z} \right\}$ is read literally as "the set of all $x$ such that $x$ is an integer and $x$ divided by two is an element of the integers." However, such rigid formalism is neither necessary nor valuable. It is sufficient to say "the set of even integers." We also expand our use of predicate notation; predicates were previously defined to take propositions as arguments, but here they take elements. However, what remains unchanged is that for any given element $x$, $P(x)$ is only ever true or false.
Set-builder notation is reasonably flexible. We can rewrite the set of even integers as $\left\{ x \in \mathbb{Z} : \frac{x}{2} \in \mathbb{Z} \right\}$ to more efficiently indicate that the elements are all integers. We can also specify more interesting objects to the left of the colon, such as points in 2-D Euclidean space. For example, the set of all points inside the unit circle is given by $\{ (x,y) \in \mathbb{R}^2 : x^2 + y^2 \leq 1 \}$.
What Exists?
The empty set exists. If other objects (sets, really) exist, then a set containing those objects exists. The process of using the known existence of some sets to demonstrate the existence of a new set is called construction. Subsequent sections on subsets, power sets, and set algebra will define the existence of more sets and their constructions. For now, we will not focus much on the question of existence, and will instead assume it as necessary in order to focus on all other questions related to sets. That is, we will take the second interpretation of definitional existence explained above for now. We will return to the question of existence, and the first interpretation from above, when we embark on the construction of the natural numbers.
We can assume the existence of the natural numbers, $\mathbb{N}$, the integers, $\mathbb{Z}$, the rational numbers, $\mathbb{Q}$, and the real numbers, $\mathbb{R}$, all of which are, of course, sets. We can also take their familiar properties for granted in order to illustrate concepts as necessary. We could alternately insist on not referencing any sets until we've first rigorously defined them and shown them to exist, but that would make talking about everything else along the way much harder. So we simply assume such things for now on good faith, knowing that we will pay back the debt later.
Problems
Write out the following in set notation:
- The continents of the world
- The last names of the members of the Beatles
- The last names of the first five presidents of the United States
- The states comprising New England
- $\{\text{Africa}, \text{Antarctica}, \text{Asia}, \text{Australia}, \text{Europe}, \text{North America}, \text{South America}\}$
- $\{\text{Harrison}, \text{Lennon}, \text{McCartney}, \text{Starr}\}$
- $\{\text{Washington}, \text{Adams}, \text{Jefferson}, \text{Madison}, \text{Monroe}\}$
- $\{\text{Connecticut}, \text{Maine}, \text{Massachusetts}, \text{New Hampshire}, \text{Rhode Island}, \text{Vermont}\}$
Some sets are so important that they have special characters designated for them. See if you can name the following ones:
- The natural numbers
- The integers
- The rational numbers
- The real numbers
- The complex numbers
- $\mathbb{N}$ is the set of natural numbers
- $\mathbb{Z}$ is the integers
- $\mathbb{Q}$ is the rational numbers
- $\mathbb{R}$ is the real numbers
- $\mathbb{C}$ is the complex numbers
Translate the following sets from set-builder notation to English:
- $\left\{ x \in \mathbb{Z} : x > 0 \land \frac{x}{7} \in \mathbb{Z} \right\}$
- $\{x \in \mathbb{R} : x \notin \mathbb{Q} \}$
- $\{ x : \sqrt{x} \in \mathbb{Z} \}$
- $\{ (x, y) \in \mathbb{R}^2 : y = 2x \}$
- The set of all positive integers evenly divisible by $7$
- The set of irrational numbers
- The set of all perfect squares
-
The set of all ordered pairs of real numbers such that the second is twice the first. Alternatively, the line $y=2x$.
Translate these sets from English into set-builder notation:
- The set of all integer multiples of $5$
- The set of all 3D points less than 1 unit from the origin
- The set of all perfect cubes
- The set of prime numbers
- $\{x \in \mathbb{Z} : \frac{x}{5} \in \mathbb{Z} \}$
- $\{ (x,y,z) \in \mathbb{R}^3 : x^2 + y^2 + z^2 < 1 \}$
- $\{ x \in \mathbb{Z} : \sqrt[3]{x} \in \mathbb{Z} \}$
-
$\{ x \in \mathbb{N} : \frac{x}{y} \in \mathbb{N} \implies (y = 1 \lor y = x) \}$ Note: The $\implies$ symbol is the logical implication symbol.