Math 13 — An Introduction to Abstract Mathematics
Neil Donaldson & Alessandra Pantano
May 30, 2016
Contents
1 Introduction 3
2 Logic and the Language of Proofs 9
2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Methods of Proof............................................................................................................................. 21
2.3 Quantifiers ........................................................................................................................................ 36
3 Divisibility and the Euclidean Algorithm 45
3.1 Remainders and Congruence ......................................................................................................... 45
3.2 Greatest Common Divisors and the Euclidean Algorithm ......................................................... 52
4 Sets and Functions 58
4.1 Set Notation and Describing a Set ................................................................................................ 58
4.2 Subsets .............................................................................................................................................. 65
4.3 Unions, Intersections, and Complements ..................................................................................... 68
4.4 Introduction to Functions ............................................................................................................... 74
5 Mathematical Induction and Well-ordering 85
5.1 Investigating Recursive Processes ................................................................................................ 85
5.2 Proof by Induction........................................................................................................................... 89
5.3 Well-ordering and the Principle of Mathematical Induction ..................................................... 95
5.4 Strong Induction ............................................................................................................................ 104
6 Set Theory, Part II 109
6.1 Cartesian Products ........................................................................................................................ 109
6.2 Power Sets...................................................................................................................................... 113
6.3 Indexed Collections of Sets .......................................................................................................... 118
7 Relations and Partitions 130
7.1 Relations ......................................................................................................................................... 130
7.2 Functions revisited ........................................................................................................................ 135
7.3 Equivalence Relations................................................................................................................... 141
7.4 Partitions ........................................................................................................................................ 147
7.5 Well-definition, Rings and Congruence ...................................................................................... 155
7.6 Functions and Partitions .............................................................................................................. 159
1
,8 Cardinalities of Infinite Sets 164
8.1 Cantor’s Notion of Cardinality .................................................................................................... 164
8.2 Uncountable Sets........................................................................................................................... 172
Useful Texts
• Book of Proof, Richard Hammack, 2nd ed 2013. Available free online! Very good on the basics: if
you’re having trouble with reading set notation or how to construct a proof, this book’s for you!
These notes are deliberately pitched at a high level relative to this textbook to provide contrast.
• Mathematical Reasoning, Ted Sundstrom, 2nd ed 2014. Available free online! Excellent resource.
If you would like to buy the actual book, you can purchase it on Amazon at a really cheap price.
• Mathematical Proofs: A Transition to Advanced Mathematics, Chartrand/Polimeni/Zhang, 3rd Ed
2013, Pearson. The most recent course text. Has many, many exercises; the first half is fairly
straightforward while the second half is much more complex and dauntingly detailed.
• The Elements of Advanced Mathematics, Steven G. Krantz, 2nd ed 2002, Chapman & Hall and
Foundations of Higher Mathematics, Peter Fletcher and C. Wayne Patty, 3th ed 2000, Brooks–Cole
are old course textbooks for Math 13. Both are readable and concise with good exercises.
Learning Outcomes
1. Developing the skills necessary to read and practice abstract mathematics.
2. Understanding the concept of proof, and becoming acquainted with several proof techniques.
3. Learning what sort of questions mathematicians ask, what excites them, and what they are
looking for.
4. Introducing upper-division mathematics by giving a taste of what is covered in several areas of
the subject.
Along the way you will learn new techniques and concepts. For example:
Number Theory Five people each take the same number of candies from a jar. Then a group of
seven does the same. The, now empty, jar originally contained 239 candies. Can you decide
how much candy each person took?
Geometry and Topology How can we visualize and compute with objects like the Mobius strip?
Fractals How to use sequences of sets to produce objects that appear the same at all scales.
To Infinity and Beyond! Why are some infinities greater than others?
,1 Introduction
What is Mathematics?
For many students this course is a game-changer. A crucial part of the course is the acceptance that
upper-division mathematics is very different from what is presented at grade-school and in the cal-
culus sequence. Some students will resist this fact and spend much of the term progressing through
the various stages of grief (denial, anger, bargaining, depression, acceptance) as they discover that
what they thought they excelled at isn’t really what the subject is about. Thus we should start at the
beginning, with an attempt to place the mathematics you’ve learned within the greater context of the
subject.
The original Greek meaning of the word mathemata is the supremely unhelpful, “That which is to
be known/learned.” There is no perfect answer to our question, but a simplistic starting point might
be to think of your mathematics education as a progression.
Arithmetic College Calculus Abstract Mathematics
In elementary school you largely learn arithmetic and the basic notions of shape. This is the mathe-
matics all of us need in order to function in the real world. If you don’t know the difference between
15,000 and 150,000, you probably shouldn’t try to buy a new car! For the vast majority of people,
arithmetic is the only mathematics they’ll ever need. Learn to count, add, and work with percent-
ages and you are thoroughly equipped for most things life will throw at you.
Calculus discusses the relationship between a quantity and its rate of change, the applications
of which are manifold: distance/velocity, charge/current, population/birth-rate, etc. Elementary
calculus is all about solving problems: What is the area under the curve? How far has the projec-
tile traveled? How much charge is in the capacitor? By now you will likely have computed many
integrals and derivatives, but perhaps you have not looked beyond such computations. A mathe-
matician explores the theory behind the calculations. From an abstract standpoint, calculus is the
beautiful structure of the Riemann integral and the Fundamental Theorem, understanding why we
can use anti-derivatives to compute area. To an engineer, the fact that integrals can be used to model
the bending of steel beams is crucial, while this might be of only incidental interest to a mathemati-
cian. Perhaps the essential difference between college calculus and abstract mathematics is that the
former is primarily interested in the utility of a technique, while the latter focuses on structure, ve-
racity and the underlying beauty. In this sense, abstract mathematics is much more of an art than a
science. No-one measures the quality of a painting or sculpture by how useful it is, instead it is the
structure, the artist’s technique and the quality of execution that are praised. Research mathemati-
cians, both pure and applied, view mathematics the same way.
In areas of mathematics other than Calculus, the link to applications is often more tenuous. The
structure and distribution of prime numbers were studied for over 2000 years before, arguably, any
serious applications were discovered. Sometimes a real-world problem motivates generalizations
that have no obvious application, and may never do so. For example, the geometry of projecting
3D objects onto a 2D screen has obvious applications (TV, computer graphics/design). Why would
anyone want to consider projections from 4D? Or from 17 dimensions? Sometimes an application
will appear later, sometimes not.1 The reason the mathematician studies such things is because the
structure appears beautiful to them and they want to appreciate it more deeply. Just like a painting.
1There are very useful applications of high-dimensional projections, not least to economics and the understanding of
sound and light waves.
3
, The mathematics you have learned so far has consisted almost entirely of computations, with
the theoretical aspects swept under the rug. At upper-division level, the majority of mathematics
is presented in an abstract way. This course will train you in understanding and creating abstract
mathematics, and it is our hope that you will develop an appreciation for it.
Proof
The essential concept in higher-level mathematics is that of proof. A basic dictionary entry for the
word would cover two meanings:
1. An argument that establishes the truth of a fact.
2. A test or trial of an assertion.2
In mathematics we always mean the former, while in much of science and wider culture the second
meaning predominates. Indeed mathematics is one of the very few disciplines in which one can
categorically say that something is true or false. In reality we can rarely be so certain. A greasy sales-
man in a TV advert may claim that to have proved that a certain cream makes you look younger; a
defendant may be proved guilty in court; the gravitational constant is 9.81ms—2. Ask yourself what
these statements mean. The advert is just trying to sell you something, but push harder and they
might provide some justification: e.g. 100 people used the product for a month and 75 of them claim
to look younger. This is a test, a proof in the second sense of the definition. Is a defendant really
guilty of a crime just because a court has found them so; have there never been any miscarriages
of justice? Is the gravitational constant precisely 9.81ms—2, or is this merely a good approximation?
This kind of pedantry may seem over the top in everyday life: indeed most of us would agree that
if 75% of people think a cream helps, then it probably is doing something beneficial. In mathematics
and philosophy, we think very differently: the concepts of true and false and of proof are very precise.
So how do mathematicians reach this blissful state where everything is either right or wrong and,
once proved, is forever and unalterably certain? The answer, rather disappointingly, is by cheating.
Nothing in mathematics is true except with reference to some assumption. For example, consider the
following theorem:
Theorem 1.1. The sum of any two even integers is even.
We all believe that this is true, but can we prove it? In the sense of the second definition of proof,
it might seem like all we need to do is to test the assertion: for example 4 + 6 = 10 is even. In the first
sense, the mathematical sense, of proof, this is nowhere near enough. What we need is a definition of
even.3
Definition 1.2. An integer is even if it may be written in the form 2n where n is an integer.
The proof of the theorem now flows straight from the definition.
2It is this notion that makes sense of the seemingly oxymoronic phrase The exception proves the rule. It is the exception
that tests the validity of the rule.
3And more fundamentally of sum and integer.
4
Neil Donaldson & Alessandra Pantano
May 30, 2016
Contents
1 Introduction 3
2 Logic and the Language of Proofs 9
2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Methods of Proof............................................................................................................................. 21
2.3 Quantifiers ........................................................................................................................................ 36
3 Divisibility and the Euclidean Algorithm 45
3.1 Remainders and Congruence ......................................................................................................... 45
3.2 Greatest Common Divisors and the Euclidean Algorithm ......................................................... 52
4 Sets and Functions 58
4.1 Set Notation and Describing a Set ................................................................................................ 58
4.2 Subsets .............................................................................................................................................. 65
4.3 Unions, Intersections, and Complements ..................................................................................... 68
4.4 Introduction to Functions ............................................................................................................... 74
5 Mathematical Induction and Well-ordering 85
5.1 Investigating Recursive Processes ................................................................................................ 85
5.2 Proof by Induction........................................................................................................................... 89
5.3 Well-ordering and the Principle of Mathematical Induction ..................................................... 95
5.4 Strong Induction ............................................................................................................................ 104
6 Set Theory, Part II 109
6.1 Cartesian Products ........................................................................................................................ 109
6.2 Power Sets...................................................................................................................................... 113
6.3 Indexed Collections of Sets .......................................................................................................... 118
7 Relations and Partitions 130
7.1 Relations ......................................................................................................................................... 130
7.2 Functions revisited ........................................................................................................................ 135
7.3 Equivalence Relations................................................................................................................... 141
7.4 Partitions ........................................................................................................................................ 147
7.5 Well-definition, Rings and Congruence ...................................................................................... 155
7.6 Functions and Partitions .............................................................................................................. 159
1
,8 Cardinalities of Infinite Sets 164
8.1 Cantor’s Notion of Cardinality .................................................................................................... 164
8.2 Uncountable Sets........................................................................................................................... 172
Useful Texts
• Book of Proof, Richard Hammack, 2nd ed 2013. Available free online! Very good on the basics: if
you’re having trouble with reading set notation or how to construct a proof, this book’s for you!
These notes are deliberately pitched at a high level relative to this textbook to provide contrast.
• Mathematical Reasoning, Ted Sundstrom, 2nd ed 2014. Available free online! Excellent resource.
If you would like to buy the actual book, you can purchase it on Amazon at a really cheap price.
• Mathematical Proofs: A Transition to Advanced Mathematics, Chartrand/Polimeni/Zhang, 3rd Ed
2013, Pearson. The most recent course text. Has many, many exercises; the first half is fairly
straightforward while the second half is much more complex and dauntingly detailed.
• The Elements of Advanced Mathematics, Steven G. Krantz, 2nd ed 2002, Chapman & Hall and
Foundations of Higher Mathematics, Peter Fletcher and C. Wayne Patty, 3th ed 2000, Brooks–Cole
are old course textbooks for Math 13. Both are readable and concise with good exercises.
Learning Outcomes
1. Developing the skills necessary to read and practice abstract mathematics.
2. Understanding the concept of proof, and becoming acquainted with several proof techniques.
3. Learning what sort of questions mathematicians ask, what excites them, and what they are
looking for.
4. Introducing upper-division mathematics by giving a taste of what is covered in several areas of
the subject.
Along the way you will learn new techniques and concepts. For example:
Number Theory Five people each take the same number of candies from a jar. Then a group of
seven does the same. The, now empty, jar originally contained 239 candies. Can you decide
how much candy each person took?
Geometry and Topology How can we visualize and compute with objects like the Mobius strip?
Fractals How to use sequences of sets to produce objects that appear the same at all scales.
To Infinity and Beyond! Why are some infinities greater than others?
,1 Introduction
What is Mathematics?
For many students this course is a game-changer. A crucial part of the course is the acceptance that
upper-division mathematics is very different from what is presented at grade-school and in the cal-
culus sequence. Some students will resist this fact and spend much of the term progressing through
the various stages of grief (denial, anger, bargaining, depression, acceptance) as they discover that
what they thought they excelled at isn’t really what the subject is about. Thus we should start at the
beginning, with an attempt to place the mathematics you’ve learned within the greater context of the
subject.
The original Greek meaning of the word mathemata is the supremely unhelpful, “That which is to
be known/learned.” There is no perfect answer to our question, but a simplistic starting point might
be to think of your mathematics education as a progression.
Arithmetic College Calculus Abstract Mathematics
In elementary school you largely learn arithmetic and the basic notions of shape. This is the mathe-
matics all of us need in order to function in the real world. If you don’t know the difference between
15,000 and 150,000, you probably shouldn’t try to buy a new car! For the vast majority of people,
arithmetic is the only mathematics they’ll ever need. Learn to count, add, and work with percent-
ages and you are thoroughly equipped for most things life will throw at you.
Calculus discusses the relationship between a quantity and its rate of change, the applications
of which are manifold: distance/velocity, charge/current, population/birth-rate, etc. Elementary
calculus is all about solving problems: What is the area under the curve? How far has the projec-
tile traveled? How much charge is in the capacitor? By now you will likely have computed many
integrals and derivatives, but perhaps you have not looked beyond such computations. A mathe-
matician explores the theory behind the calculations. From an abstract standpoint, calculus is the
beautiful structure of the Riemann integral and the Fundamental Theorem, understanding why we
can use anti-derivatives to compute area. To an engineer, the fact that integrals can be used to model
the bending of steel beams is crucial, while this might be of only incidental interest to a mathemati-
cian. Perhaps the essential difference between college calculus and abstract mathematics is that the
former is primarily interested in the utility of a technique, while the latter focuses on structure, ve-
racity and the underlying beauty. In this sense, abstract mathematics is much more of an art than a
science. No-one measures the quality of a painting or sculpture by how useful it is, instead it is the
structure, the artist’s technique and the quality of execution that are praised. Research mathemati-
cians, both pure and applied, view mathematics the same way.
In areas of mathematics other than Calculus, the link to applications is often more tenuous. The
structure and distribution of prime numbers were studied for over 2000 years before, arguably, any
serious applications were discovered. Sometimes a real-world problem motivates generalizations
that have no obvious application, and may never do so. For example, the geometry of projecting
3D objects onto a 2D screen has obvious applications (TV, computer graphics/design). Why would
anyone want to consider projections from 4D? Or from 17 dimensions? Sometimes an application
will appear later, sometimes not.1 The reason the mathematician studies such things is because the
structure appears beautiful to them and they want to appreciate it more deeply. Just like a painting.
1There are very useful applications of high-dimensional projections, not least to economics and the understanding of
sound and light waves.
3
, The mathematics you have learned so far has consisted almost entirely of computations, with
the theoretical aspects swept under the rug. At upper-division level, the majority of mathematics
is presented in an abstract way. This course will train you in understanding and creating abstract
mathematics, and it is our hope that you will develop an appreciation for it.
Proof
The essential concept in higher-level mathematics is that of proof. A basic dictionary entry for the
word would cover two meanings:
1. An argument that establishes the truth of a fact.
2. A test or trial of an assertion.2
In mathematics we always mean the former, while in much of science and wider culture the second
meaning predominates. Indeed mathematics is one of the very few disciplines in which one can
categorically say that something is true or false. In reality we can rarely be so certain. A greasy sales-
man in a TV advert may claim that to have proved that a certain cream makes you look younger; a
defendant may be proved guilty in court; the gravitational constant is 9.81ms—2. Ask yourself what
these statements mean. The advert is just trying to sell you something, but push harder and they
might provide some justification: e.g. 100 people used the product for a month and 75 of them claim
to look younger. This is a test, a proof in the second sense of the definition. Is a defendant really
guilty of a crime just because a court has found them so; have there never been any miscarriages
of justice? Is the gravitational constant precisely 9.81ms—2, or is this merely a good approximation?
This kind of pedantry may seem over the top in everyday life: indeed most of us would agree that
if 75% of people think a cream helps, then it probably is doing something beneficial. In mathematics
and philosophy, we think very differently: the concepts of true and false and of proof are very precise.
So how do mathematicians reach this blissful state where everything is either right or wrong and,
once proved, is forever and unalterably certain? The answer, rather disappointingly, is by cheating.
Nothing in mathematics is true except with reference to some assumption. For example, consider the
following theorem:
Theorem 1.1. The sum of any two even integers is even.
We all believe that this is true, but can we prove it? In the sense of the second definition of proof,
it might seem like all we need to do is to test the assertion: for example 4 + 6 = 10 is even. In the first
sense, the mathematical sense, of proof, this is nowhere near enough. What we need is a definition of
even.3
Definition 1.2. An integer is even if it may be written in the form 2n where n is an integer.
The proof of the theorem now flows straight from the definition.
2It is this notion that makes sense of the seemingly oxymoronic phrase The exception proves the rule. It is the exception
that tests the validity of the rule.
3And more fundamentally of sum and integer.
4
