Class notes
Mam1000w - Sets and functions lecture Notes
- Course
- MAM1000W
- Institution
- University Of Cape Town (UCT)
This is a comprehensive and detailed note on sets and functions. Quality stuff!! U'll need it!!
[Show more]
Content preview
Chapter 1Sets and Functions
We understand a “set” to be any collection M of certain distinct objects
of our thought or intuition (called the “elements” of M ) into a whole.
(Georg Cantor, 1895)
In mathematics you don’t understand things. You just get used to them.
(Attributed to John von Neumann)
In this chapter, we define sets, functions, and relations and discuss some of
their general properties. This material can be referred back to as needed in the
subsequent chapters.
1.1. Sets
. The
objects could be anything (planets, squirrels, characters in Shakespeare’s plays, or
other sets) but for us they will be mathematical objects such as numbers, or sets
of numbers. We write x ∈ X if x is an element of the set X and x ∈ / X if x is not
an element of X .
If the definition of a “set” as a “collection” seems circular, that’s because it
is. Conceiving of many objects as a single whole is a basic intuition that cannot
be analyzed further, and the the notions of “set” and “membership” are primitive
ones. These notions can be made mathematically precise by introducing a system
of axioms for sets and membership that agrees with our intuition and proving other
set-theoretic properties from the axioms.
The most commonly used axioms for sets are the ZFC axioms, named somewhat
inconsistently after two of their founders (Zermelo and Fraenkel) and one of their
axioms (the Axiom of Choice). We won’t state these axioms here; instead, we use
“naive” set theory, based on the intuitive properties of sets. Nevertheless, all the
set-theory arguments we use can be rigorously formalized within the ZFC system.
1
,2 1. Sets and Functions
Sets are determined entirely by their elements. Thus, the sets X, Y are equal,
written X = Y , if
x∈X if and only if x ∈ Y.
It is convenient to define the empty set, denoted by ∅, as the set with no elements.
(Since sets are determined by their elements, there is only one set with no elements!)
If X 6= ∅, meaning that X has at least one element, then we say that X is non-
empty.
We can define a finite set by listing its elements (between curly brackets). For
example,
X = {2, 3, 5, 7, 11}
is a set with five elements. The order in which the elements are listed or repetitions
of the same element are irrelevant. Alternatively, we can define X as the set whose
elements are the first five prime numbers. It doesn’t matter how we specify the
elements of X, only that they are the same.
Infinite sets can’t be defined by explicitly listing all of their elements. Never-
theless, we will adopt a realist (or “platonist”) approach towards arbitrary infinite
sets and regard them as well-defined totalities. In constructive mathematics and
computer science, one may be interested only in sets that can be defined by a rule or
algorithm — for example, the set of all prime numbers — rather than by infinitely
many arbitrary specifications, and there are some mathematicians who consider
infinite sets to be meaningless without some way of constructing them. Similar
issues arise with the notion of arbitrary subsets, functions, and relations.
1.1.1. Numbers. The infinite sets we use are derived from the natural and real
numbers, about which we have a direct intuitive understanding.
Our understanding of the natural numbers 1, 2, 3, . . . derives from counting.
We denote the set of natural numbers by
N = {1, 2, 3, . . . } .
We define N so that it starts at 1. In set theory and logic, the natural numbers
are defined to start at zero, but we denote this set by N0 = {0, 1, 2, . . . }. Histori-
cally, the number 0 was later addition to the number system, primarily by Indian
mathematicians in the 5th century AD. The ancient Greek mathematicians, such
as Euclid, defined a number as a multiplicity and didn’t consider 1 to be a number
either.
Our understanding of the real numbers derives from durations of time and
lengths in space. We think of the real line, or continuum, as being composed of an
(uncountably) infinite number of points, each of which corresponds to a real number,
and denote the set of real numbers by R. There are philosophical questions, going
back at least to Zeno’s paradoxes, about whether the continuum can be represented
as a set of points, and a number of mathematicians have disputed this assumption
or introduced alternative models of the continuum. There are, however, no known
inconsistencies in treating R as a set of points, and since Cantor’s work it has been
the dominant point of view in mathematics because of its precision, power, and
simplicity.
, 1.1. Sets 3
We denote the set of (positive, negative and zero) integers by
Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . . },
and the set of rational numbers (ratios of integers) by
Q = {p/q : p, q ∈ Z and q 6= 0}.
The letter “Z” comes from “zahl” (German for “number”) and “Q” comes from
“quotient.” These number systems are discussed further in Chapter 2.
Although we will not develop any complex analysis here, we occasionally make
use of complex numbers. We denote the set of complex numbers by
C = {x + iy : x, y ∈ R} ,
where we add and multiply complex numbers in the natural way, with the additional
identity that i2 = −1, meaning that i is a square root of −1. If z = x + iy ∈ C, we
call x = ℜz the real part of z and y = ℑz the imaginary part of z, and we call
p
|z| = x2 + y 2
the absolute value, or modulus, of z. Two complex numbers z = x + iy, w = u + iv
are equal if and only if x = u and y = v .
1.1.2. Subsets. A set A is a subset of a set X, written A ⊂ X or X ⊃ A, if
every element of A belongs to X; that is, if
x ∈ A implies that x ∈ X.
We also say that A is included in X.1 For example, if P is the set of prime numbers,
then P ⊂ N, and N ⊂ R. The empty set ∅ and the whole set X are subsets of any
set X. Note that X = Y if and only if X ⊂ Y and Y ⊂ X; we often prove the
equality of two sets by showing that each one includes the other.
In our notation, A ⊂ X does not imply that A is a proper subset of X (that
is, a subset of X not equal to X itself ), and we may have A = X. This notation
for non-strict inclusion is not universal; some authors use A ⊂ X to denote strict
inclusion, in which A 6= X, and A ⊆ X to denote non-strict inclusion, in which
A = X is allowed.
Definition 1.1. The power set P(X) of a set X is the set of all subsets of X .
Example 1.2. If X = {1, 2, 3}, then
P(X) = {∅, {1}, {2}, {3}, {2, 3}, {1, 3}, {1, 2}, {1, 2, 3}} .
The power set of a finite set with n elements has 2n elements because, in
defining a subset, we have two independent choices for each element (does it belong
to the subset or not?). In Example 1.2, X has 3 elements and P(X) has 23 = 8
elements.
The power set of an infinite set, such as N, consists of all finite and infinite
subsets and is infinite. We can define finite subsets of N, or subsets with finite
1By contrast, we say that an element x ∈ X is contained in X, in which cases the singleton set
{x} is included in X. This terminological distinction is not universal, but it is almost always clear from
the context whether one is referring to an element of a set or a subset of a set. In fact, before the
development of the contemporary notation for set theory, Dedekind [3] used the same symbol (⊆) to
denote both membership of elements and inclusion of subsets.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller anyiamgeorge19. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R177,16. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
72042 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 14 years now