Naive Set Theory: Definitions
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$."
An important property of sets is that each element is unique - there are no repeated elements in a set (though two different sets may contain the same element). 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. Sets containing multiple instances of the same element are called multisets and are studied as a later subject in set theory.
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) \}$. Read aloud, this expression says "the set of all $x$ such that $P(x)$ is true". $P(x)$ is formally known as a predicate, which is some condition or rule defining the elements in the set. 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."
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 \}$.
First order logic gives us two symbols to more efficiently represent the concepts of "and" and "or": $\land$ stands for and, and $\lor$ stands for or. For example, the set of integers divisible by either 2 or 3 can be written as $\{ x \in \mathbb{Z} : \frac{x}{2} \in \mathbb{Z} \lor \frac{x}{3} \in \mathbb{Z} \}$. However, writing out the words "and" and "or" often makes things easier to read. Additionally, the concept of logical implication is very useful as well. If a statement $A$ implies the truth of a statement $B$, we write this as $A \implies B$. If $A$ implies $B$, then $B$ is necessarily true if $A$ is true, although $B$ can be either true or false if $A$ is false.
The familiar sets of numbers, such as $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and so on, are themselves sets, and can in fact be formally constructed out of sets. However, it is useful to assume the familiar properties of these sets in order to better illustrate many properties of sets themselves. We could insist on not referencing these sets until we've first built them up and rigorously defined all their properties, but this makes illustrating everything about sets along the way there much harder. Instead, it's easier to assume their existence and familiar properties in the interim.
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.