This chapter introduces the basic notions of set theory.
A set #\blue A# is a collection of distinct objects, considered as an object in its own right. An object can be anything from a number and a letter to a combination of these (or even a set). The distinct objects in a set are called the elements of that set.
Two sets #\blue A# and #\green B# are equal (denoted by #\blue A=\green B#) if and only if they have the same elements.
If a set #\blue A# has a finite number of elements, then we call it a finite set and denote this number by #|\blue{A}|#. Otherwise, we call it an infinite set and write #|\blue{A}| = \infty#. The number #|\blue{A}|# (possibly infinite) is called the size of #\blue{A}#.
We use curly brackets to describe sets by means of their elements. Here are four ways to describe a set with a moderate number of elements (referred to the abbreviation #\text{obj}# of object). \[\begin{array}{rcl}\text{set}&=&\{\text{obj}_1, \text{obj}_2,\text{obj}_3\}\\
\text{set}&=&\{\text{obj}_1, \text{obj}_2, \ldots,\text{obj}_n\}\\
\text{set}&=&\{\text{obj}_1, \text{obj}_2, \ldots\}\\
\text{set}&=&\{\ldots,\text{obj}_{-2}, \text{obj}_{-1},\text{obj}_0,\text{obj}_1, \text{obj}_2, \ldots\}\end{array}\]
The first and second case are examples of finite sets, with at most #3# and #n# elements, respectively. The three dots #{\ldots}# indicate that we continue in a like manner or with the same pattern.
Examples
The set #\blue A# of all vowels in the English alphabet is determined by #\blue A =\{\text{a}, \text{e}, \text{i}, \text{o}, \text{u}\}#.
The elements of # \{1, 2, 3, 4\}# are #1#, #2#, #3#, and #4#. A more complicated description of the same set is # \{1, 2, 2, 3, 4, 1\}#.
Thus, # \{1, 2, 3, 4\}= \{1, 2, 2, 3, 4, 1\}#.
The size of #\blue {B} = \{ \text{apple}, \pi, 4, 7.5, \text{q}
\} # is #|\blue{B}|=5#.
The size of # \{2,4,6,8,\ldots\}# is infinite.
The set #\{3,9,27,81,\ldots,729\}# has size #6#.
The sets #\{4, 3, 2\}# and #\{2, 4, 3\}# coincide.
The set of even integers is # \{\ldots,-4,-2,0,2,4,\ldots\}#
The same object cannot be included in the set more than once, so every element in a set is unique. This means that duplicate elements count as one. So #\{3,3,3\} = \{3\}#.
Although the elements between the curly brackets seem to be ordered, the ordering is not relevant for the set, so #\{1,2\} = \{2,1\}#.
It may help to visualize a set by using a Venn diagram. This consists of an oval representing the set, whose elements are represented by dots described in the oval.
If the set is finite, this provides a very accurate description of the set.
The Venn diagram below corresponds to the set #\blue A = \{1, 2, 3, 4, 5, 6\}#.
As we will see later, there are more ways to define sets; often they make use of curly brackets "#\{#" and "#\}#". This is needed because the current notation with brackets can only describe sets of moderate size, that is, sets whose elements are enumerable. The real numbers are a set that cannot be enumerated; we cannot list them as #a_1,a_2,a_3,\ldots# for some choice of elements #a_i# with #i# running over the natural numbers, because there are too many.
To distinguish the current set description from others, we will say that the way sets are described here by enumeration.
Sets are commonly denoted by a capital letter. Often, an element of the set is represented by a lowercase letter.
Two sets #\blue A# and #\green B# are equal if and only if
- every element of #\blue A# is an element of #\green B# and, conversely,
- every element of #\green B# is an element of #\blue A#.
We write this as #\blue A = \green B#.
For example, if #\blue A =\left\{\frac{1}{2}, 2, 3\right\}# and #\green B=\left\{2,3, 2, \frac{2}{4}\right\}#, then #\blue A= \green B#.
Equality is (as it always should be) an equivalence relation. This means that it satisfies the following three properties for all sets #\blue A#, #\green B#, and #\orange C#.
- #\blue A = \blue A#
- #\blue A = \green B# #\Rightarrow# #\green B = \blue A#
- #(\blue A = \green B# and #\green B = \orange C)# #\Rightarrow# #\blue A = \orange C#
A set given by enumeration is not to be confused with a list. A list is a sequence of objects, usually put between square brackets:
\[ \rv{a_1, a_2,\ldots }\quad \text{ or } \quad\rv{a_1,a_2,\ldots,a_n}
\]
where #a_i# is an arbitrary object for each natural number #i# serving as an index, and #n# is the length of the list (at least, in the latter case; in the former case we say that the list has inifinite length). Here, the elements #a_i# of the list are ordered and multiplicities may occur. If the curly brackets for a set given were to be replaced by square brackets, then we would be dealing with lists:
\[ \{1,2\}=\{2,1\}\quad \text{ and } \quad\{3,3,3\}= \{3\}\\ \text{ but } \\
\rv{1,2}\ne\rv{2,1}\quad \text{ and } \quad\rv{3,3,3}\ne \rv{3}\]
Later, we will deal with sets whose elements are lists of a given length.
We will be working a lot with the following sets, which are so special that they are denoted by widely accepted symbols.
\[\begin{array}{rcl} \mathbb{N} &=& \text{the set of all natural numbers} = \{1, 2, 3, 4, \ldots\}\\ \mathbb{Z} & = & \text{the set of all integers} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}\\ \mathbb{Q} &=& \text{the set of all rational numbers} = \text{the set of all elements of the form }\frac{a}{b}\text{ for integers } a,b \text { with } b\gt 0\\ \mathbb{R} & = & \text{the set of all real numbers} = \text{all numbers on the axis of numbers } (\text{neither } \infty \text{ nor } -\infty) \\ \emptyset &=&\text{the empty set} = \{\}\end{array}\]
In the mathematical literature, the symbol #\mathbb{N}# is sometimes also used to denote the set #\{0,1,2,\ldots\}#. In this course, we will not refer to #0# as a natural number.
Above we mentioned that the set of real numbers cannot be enumerated. In contrast, the set #{\mathbb Q}# is enumerable and so can described by use of dots. Here is an example of how this can be done. \[\mathbb{Q} = \left\{0,1,-1,2,-2,\frac{1}{2},-\frac{1}{2},3,-3,\frac{1}{3},-\frac{1}{3},\frac{2}{3},-\frac{2}{3},4,-4\ldots \right\} \]Separating positive and negative numbers, we find another way, in which two series of dots #(\ldots)# occur:
\[\mathbb{Q} = \left\{\ldots, -4,-\frac{2}{3},-\frac{1}{3},-3,-\frac{1}{2},-2,-1,0,1,2,\frac{1}{2},3,\frac{1}{3},\frac{2}{3},4,\ldots \right\} \]
From #4# onwards, the expansion to the right will be
\[4,\frac{1}{4},\frac{2}{4},\frac{3}{4},5,\ldots\] The equality #\frac{2}{4}= \frac{1}{2}# shows that the element #\frac{2}{4}# in the enumeration is redundant, but in view of the agreement that each element is counted only once, we do not care about that.
Each natural number is also an integer. In terms of sets, this means that every element of #{\mathbb N}# is an element of # {\mathbb Z}#. Later, we will be expressing this in terms of containment of sets.
The set #\emptyset# has no elements at all. This is the unique set of size #0#.
We also have a special symbol for expressing membership of a set.
The set membership symbol #\in# is used to say that an object is an element of a set. We use the symbol #\notin# to indicate that the object is not an element of a set.
Let #\blue A# be a set and #a# an object.
- We write #a \in \blue A# if #a# is an element of #\blue A#.
- We write #a \notin \blue A# if #a# is not an element of #\blue A#.
Example
Consider the set #\blue A = \{2, 3, 4\}#.
The statement that #3# is an element of #\blue A# can be expressed as #3\in\blue A#.
The statement that #5# is not an element of #\blue A# can be expressed as #5\not\in\blue A#.
There are more ways of expressing that #a# is an element of the set #A#. We also say
- #a# belongs to #A#, or
- #a# is a member of #A#, or
- #a# is in #A#, or
- #a# lies in #A#.
In the same vein, we can express that #b# does not belong to #A# by saying
- #b# does not belong to #A#, or
- #b# lies outside #A#, or
- #b# is not in #A#, or
- #b# does not lie in #A#.
Some more examples on the use of #\in# and #\notin#.
\[\begin{array}{clclclc} 3\in \mathbb{N}&& -3\in \mathbb{Z}&& \frac{1}{2}\in \mathbb{Q}&& \pi\in \mathbb{R}\\ 3\notin \emptyset&&-3\notin \mathbb{N}&&\frac{1}{2}\notin \mathbb{Z}& &\pi\notin \mathbb{Q}\end{array}\]
Let #A =## \{0,19,4,19,7,7,4\}# be a
set.
Rewrite the definition of the set #A# in such a way that the elements are ordered from lowest to highest and each element occurs only once.
#A =# # \left\{0,4,7,19\right\}#
The numbers #4#, #7#, and #19# occur twice, so we can remove one copy of each. Only four elements remain; ordering these from lowest to highest, we find #\left\{0, 4, 7, 19\right\}#.
The notion of set
