This chapter introduces the basic notions of set theory.
A set 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 and are equal (denoted by ) if and only if they have the same elements.
If a set has a finite number of elements, then we call it a finite set and denote this number by . Otherwise, we call it an infinite set and write . The number (possibly infinite) is called the size of .
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 of object).
The first and second case are examples of finite sets, with at most
and
elements, respectively. The three dots
indicate that we continue in a like manner or with the same pattern.
Examples
The set of all vowels in the English alphabet is determined by .
The elements of are , , , and . A more complicated description of the same set is .
Thus, .
The size of is .
The size of is infinite.
The set has size .
The sets and coincide.
The set of even integers is
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 .
Although the elements between the curly brackets seem to be ordered, the ordering is not relevant for the set, so .
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 .
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 for some choice of elements with 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 and are equal if and only if
- every element of is an element of and, conversely,
- every element of is an element of .
We write this as .
For example, if and , then .
Equality is (as it always should be) an equivalence relation. This means that it satisfies the following three properties for all sets , , and .
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:
where
is an arbitrary object for each natural number
serving as an index, and
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
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:
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.
In the mathematical literature, the symbol is sometimes also used to denote the set . In this course, we will not refer to as a natural number.
Above we mentioned that the set of real numbers cannot be enumerated. In contrast, the set is enumerable and so can described by use of dots. Here is an example of how this can be done.
Separating positive and negative numbers, we find another way, in which two series of dots
occur:
From
onwards, the expansion to the right will be
The equality
shows that the element
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 is an element of . Later, we will be expressing this in terms of containment of sets.
The set has no elements at all. This is the unique set of size .
We also have a special symbol for expressing membership of a set.
The set membership symbol is used to say that an object is an element of a set. We use the symbol to indicate that the object is not an element of a set.
Let be a set and an object.
- We write if is an element of .
- We write if is not an element of .
Example
Consider the set .
The statement that is an element of can be expressed as .
The statement that is not an element of can be expressed as .
There are more ways of expressing that is an element of the set . We also say
- belongs to , or
- is a member of , or
- is in , or
- lies in .
In the same vein, we can express that
does not belong to
by saying
- does not belong to , or
- lies outside , or
- is not in , or
- does not lie in .
Some more examples on the use of
and
.
Let
be a
set.
Rewrite the definition of the set
in such a way that the elements are ordered from lowest to highest and each element occurs only once.
The numbers , , and occur twice, so we can remove one copy of each. Only four elements remain; ordering these from lowest to highest, we find .