An Infinite Descent Into Pure Mathematics
An Infinite Descent intoPure Mathematics .BYC LIVE N EWSTEADVersion 0.3Last updated on Wednesday 3rd July 2019https://infinitedescent.xyz
c 2019 Clive NewsteadAll Rights Reserved.Preview of First Edition, 2019 (forthcoming)ISBN 978-1-950215-00-3 (paperback)ISBN 978-1-950215-01-0 (hardback)A free PDF copy of An Infinite Descent into Pure Mathematics can beobtained from the book’s website:https://infinitedescent.xyzThis book, its figures and its TEX source are released under a CreativeCommons Attribution–ShareAlike 4.0 International Licence. The full textof the licence is replicated at the end of the book, and can be found on theCreative Commons 0/legalcode0 2 4 6 8 10 9 7 5 3 1
ContentsPrefaceviiAcknowledgementsxi01Getting started0.E Chapter 0 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .17ICore concepts191Logical structure211.1Propositional logic . . . . . . . . . . . . . . . . . . . . . . . . . . . .221.2Variables and quantifiers . . . . . . . . . . . . . . . . . . . . . . . . .421.3Logical equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . .541.E Chapter 1 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .69Sets and functions712.1Sets and set operations . . . . . . . . . . . . . . . . . . . . . . . . . .722.2Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .892.3Injections and surjections . . . . . . . . . . . . . . . . . . . . . . . . .1032.E Chapter 2 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .116Mathematical induction11923iii
Contentsiv4II5673.1Peano’s axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1203.2Weak induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1263.3Strong induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1393.E Chapter 3 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .146Relations1474.1Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1484.2Equivalence relations and partitions . . . . . . . . . . . . . . . . . . .1564.E Chapter 4 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .167Topics in pure mathematics169Number theory1715.1Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1725.2Prime numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1855.3Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . .1945.E Chapter 5 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .217Enumerative combinatorics2196.1Finite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2206.2Counting principles . . . . . . . . . . . . . . . . . . . . . . . . . . . .2296.3Alternating sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2476.E Chapter 6 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .261Real numbers2637.1Inequalities and means . . . . . . . . . . . . . . . . . . . . . . . . . .2647.2Completeness and convergence . . . . . . . . . . . . . . . . . . . . . .2817.3Series and sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3037.E Chapter 7 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .323iv
Contents89vInfinity3258.1Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . .3268.2Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3398.3Cardinal arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . .3488.E Chapter 8 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .359Discrete probability theory3619.1Discrete probability spaces . . . . . . . . . . . . . . . . . . . . . . . .3629.2Discrete random variables . . . . . . . . . . . . . . . . . . . . . . . .3799.E Chapter 9 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .39410 Additional topics39510.1 Orders and lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . .39610.2 Inductively defined sets . . . . . . . . . . . . . . . . . . . . . . . . . .40710.E Chapter 10 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .424v
ContentsviAppendices427A Proof-writing427A.1 Elements of proof-writing . . . . . . . . . . . . . . . . . . . . . . . . .428A.2 Vocabulary for proofs . . . . . . . . . . . . . . . . . . . . . . . . . . .436B Mathematical miscellany449B.1 Set theoretic foundations . . . . . . . . . . . . . . . . . . . . . . . . .450B.2 Constructions of the number sets . . . . . . . . . . . . . . . . . . . . .454B.3 Limits of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .464C Hints for selected exercises469D Typesetting mathematics with LATEX481Indices495Index of topics495Index of vocabulary499Index of notation501Index of LATEX commands504Licence509vi
PrefaceHello, and thank you for taking the time to read this quick introduction to the book! Iwould like to begin with an apology and a warning:This book is still under development!That is to say, there are some sections that are incomplete, as well as other sections whichare currently much more terse than I would like them to be.The most recent version is freely available for download from the following website:https://infinitedescent.xyzAs the book is undergoing constant changes, I advise that you do not print it in itsentirety—if you must print anything, then I suggest that you do it a few pages at a time,as required.This book was designed with inquiry and communication in mind, as they are centralto a good mathematical education. One of the upshots of this is that there are manyexercises throughout the book, requiring a more active approach to learning, rather thanpassive reading. These exercises are a fundamental part of the book, and should becompleted even if not required by the course instructor. Another upshot of these designprinciples is that solutions to exercises are not provided—a student seeking feedback ontheir solutions should speak to someone to get such feedback, be it another student, ateaching assistant or a course instructor.Navigating the bookThis book need not, and emphatically should not, be read from front to back. The orderof material is chosen so that material appearing later depends only on material appearingearlier (with a couple of exceptions, which are pointed out in the text).The majority of introductory pure mathematics courses cover, at a minimum, symboliclogic, sets, functions and relations. This material is the content of Part I. Such coursesvii
Prefaceviiiusually cover additional topics from pure mathematics, with exactly which topics depending on what the course is preparing students for. With this in mind, Part II servesas an introduction to a range of areas of pure mathematics, including number theory,combinatorics, set theory, real analysis, probability theory and order theory.It is not necessary to cover all of Part I before proceeding to topics in Part II. In fact,interspersing material from Part II can be a useful way of motivating many of the abstractconcepts that arise in Part I.The following table shows dependencies between sections. Previous sections within thesame chapter as a section should be considered ‘essential’ prerequisites unless mendedUseful2.22.22.1, 3.34.24.22.32.3, 3.22.22.3, 3.36.16.23.1, 2.12.22.26.24.23.3, 2.37.34.27.17.18.1, 7.35.3, 8.18.110.1Prerequisites are cumulative. For example, in order to cover Section 8.3, you should firstcover Chapters 0, 2 and 3 and Sections 6.1, 6.2, 8.1 and 8.2.What the numbers, colours and symbols meanBroadly speaking, the material in the book is broken down into enumerated items thatfall into one of five categories: definitions, results, remarks, examples and exercises. InAppendix A, we also have proof extracts. To improve navigability, these categories aredistinguished by name, colour and symbol, as indicated in the following lourRedBluePurpleCategoryExamplesExercisesProof extractsviiiSymbol0.}ColourTealGoldTeal
PrefaceixThese items are enumerated according to their section—for example, Theorem 7.2.41 isin Section 7.2. Definitions and theorems (important results) appear in a box .You will also encounter the symbols and C whose meanings are as follows: End of proof. It is standard in mathematical documents to identify when a proof hasended by drawing a small square or by writing ‘Q.E.D.’ (The latter stands for quoderat demonstrandum, which is Latin for which was to be shown.)C End of item. This is not a standard usage, and is included only to help you to identifywhen an item has finished and the main content of the book continues.Some subsections are labelled with the symbol ?. This indicates that the material in thatsubsection can be skipped without dire consequences.LicenceThis book is licensed under the Creative Commons Attribution-ShareAlike 4.0 (CC BYSA 4.0) licence. This means you’re welcome to share this book, provided that you givecredit to the author and that any copies or derivatives of this book are released under thesame licence. The content of the licence can be read in its full glory at the end of thebook, and by following the following Comments and correctionsAny feedback, be it from students, teaching assistants, instructors or any other readers,would be very much appreciated. Particularly useful are corrections of typographicalerrors, suggestions for alternative ways to describe concepts or prove theorems, and requests for new content (e.g. if you know of a nice example that illustrates a concept, orif there is a relevant concept you wish were included in the book).Such feedback can be sent to the author by email (clive@infinitedescent.xyz).ix
Prefacexx
AcknowledgementsWhen I reflect on the time I have spent writing this book, I am overwhelmed by thenumber of people who have had some kind of influence on its content.This book would never have come to exist were it not for Chad Hershock’s course 38-801Evidence-Based Teaching in the Sciences, which I took in Fall 2014 as a graduate studentat Carnegie Mellon University. His course heavily influenced my approach to teaching,and it motivated me to write this book in the first place. Many of the pedagogical decisions I made when writing this book were informed by research that I was exposed toas a student in Chad’s class.The legendary Carnegie Mellon professor, John Mackey, has been using this book (invarious forms) as course notes for 21-128 Mathematical Concepts and Proofs and 15151 Mathematical Foundations of Computer Science since Fall 2016. His influence canbe felt throughout the book: thanks to discussions with John, many proofs have beenreworded, sections restructured, and explanations improved. As a result, there is someoverlap between the exercises in this book and the questions on his problem sheets. I amextremely grateful for his ongoing support.Steve Awodey, who was my doctoral thesis advisor, has for a long time been a sourceof inspiration for me. Many of the choices I made when choosing how to present thematerial in this book are grounded in my desire to do mathematics the right way—it wasthis desire that led me to study category theory, and ultimately to become Steve’s PhDstudent. I learnt a great deal from him and I greatly appreciated his patience and flexibility in helping direct my research despite my busy teaching schedule and extracurricularinterests (such as writing this book).Perhaps unbeknownst to them, many insightful conversations with the following peoplehave helped shape the material in this book in one way or another: Jeremy Avigad, DebBrandon, Heather Dwyer, Thomas Forster, Will Gunther, Kate Hamilton, Jessica Harrell,Bob Harper, Brian Kell, Marsha Lovett, Ben Millwood, David Offner, Ruth Poproski,Hilary Schuldt, Gareth Taylor, Katie Walsh, Emily Weiss and Andy Zucker.The Stack Exchange network has influenced the development of this book in two important ways. First, I have been an active member of Mathematics Stack Exchange (https://math.stackexchange.com/) since early 2012 and have learnt a great deal abouthow to effectively explain mathematical concepts; occasionally, a question on Mathemxi
Acknowledgementsxiiatics Stack Exchange inspires me to add a new example or exercise to the book. Second, Ihave made frequent use of LATEX Stack Exchange (https://tex.stackexchange.com)for implementing some of the more technical aspects of writing a book using LATEX.The Department of Mathematical Sciences at Carnegie Mellon University supported meacademically, professionally and financially throughout my PhD and presented me withmore opportunities than I could possibly have hoped for to develop as a teacher. Thissupport is now continued by the Department of Mathematics at Northwestern University,where I am currently employed as a lecturer.I would also like to thank everyone at Carnegie Mellon’s and Northwestern’s teaching centres, the Eberly Center and the Searle Center, respectively. Through variousworkshops, programs and fellowships at both teaching centres, I have learnt an incredible amount about how people learn, and I have transformed as a teacher. Theirstudent-centred, evidence-based approach to the science of teaching and learning underlies everything I do as a teacher, including writing this book—their influence cannot beunderstated.Finally, and importantly, I am grateful to the 1000 students who have already used thisbook to learn mathematics. Every time a student contacts me to ask a question or pointout an error, the book gets better; this is reflected in the dozens of typographical errorsthat have been fixed as a consequence.Clive NewsteadJuly 2019Evanston, Illinoisxii
Chapter 0Getting startedBefore we can start proving things, we need to eliminate certain kinds of statements thatwe might try to prove. Consider the following statement:This sentence is false.Is it true or false? If you think about this for a couple of seconds then you’ll get into a bitof a pickle.Now consider the following statement:The happiest donkey in the world.Is it true or false? Well it’s not even a sentence; it doesn’t make sense to even ask if it’strue or false!Clearly we’ll be wasting our time trying to write proofs of statements like the two listedabove—we need to narrow our scope to statements that we might actually have a chanceof proving (or perhaps refuting)! This motivates the following (informal) definition.F Definition 0.1A proposition is a statement to which it is possible to assign a truth value (‘true’ or‘false’). If a proposition is true, a proof of the proposition is a logically valid argumentdemonstrating that it is true, which is pitched at such a level that a member of the intendedaudience can verify its correctness.Thus the statements given above are not propositions because there is no possible way ofassigning them a truth value. Note that, in Definition 0.1, all that matters is that it makessense to say that it is true or false, regardless of whether it actually is true or false—thetruth value of many propositions is unknown, even very simple ones.1
Chapter 0. Getting started2. Exercise 0.2Think of an example of a true proposition, a false proposition, a proposition whose truthvalue you don’t know, and a statement that is not a proposition.CResults in mathematical papers and textbooks may be referred to as propositions, but theymay also be referred to as theorems, lemmas or corollaries depending on their intendedusage. A proposition is an umbrella term which can be used for any result. A theorem is a key result which is particularly important. A lemma is a result which is proved for the purposes of being used in the proof of atheorem. A corollary is a result which follows from a theorem without much additional effort.These are not precise definitions, and they are not meant to be—you could call everyresult a proposition if you wanted to—but using these words appropriately helps readerswork out how to read a paper. For example, if you just want to skim a paper and find itskey results, you’d look for results labelled as theorems.It is not much good trying to prove results if we don’t have anything to prove resultsabout. With this in mind, we will now introduce the number sets and prove some resultsabout them in the context of four topics, namely: division of integers, number bases,rational and irrational numbers, and polynomials. These topics will provide context forthe material in Part I, and serve as an introduction to the topics covered in Part II.We will not go into very much depth in this chapter. Rather, think of this as a warm-upexercise—a quick, light introduction, with more proofs to be provided in the rest of thebook.Number setsLater in this chapter, and then in much more detail in Section 2.1, we will encounter thenotion of a set; a set can be thought of as being a collection of objects. This seeminglysimple notion is fundamental to mathematics, and is so involved that we will not treatsets formally in this book. For now, the following definition will suffice.F Definition 0.3 (to be revised in Definition 2.1.1)A set is a collection of objects. The objects in the set are called elements of the set. IfX is a set and x is an object, then we write x X (LATEX code: x \in X) to denote theassertion that x is an element of X.The sets of concern to us first and foremost are the number sets—that is, sets whoseelements are particular types of number. At this introductory level, many details will betemporarily swept under the rug; we will work at a level of precision which is appropriatefor our current stage, but still allows us to develop a reasonable amount of intuition.2
Chapter 0. Getting started3In order to define the number sets, we will need three things: an infinite line, a fixed pointon this line, and a fixed unit of length.So here we go. Here is an infinite line:The arrows indicate that it is supposed to extend in both directions without end. Thepoints on the line will represent numbers (specifically, real numbers, a misleading termthat will be defined in Definition 0.25). Now let’s fix a point on this line, and label it ‘0’:0This point can be thought of as representing the number zero; it is the point against whichall other numbers will be measured. Finally, let’s fix a unit of length:This unit of length will be used, amongst other things, to compare the extent to which theother numbers differ from zero.F Definition 0.4The above infinite line, together with its fixed zero point and fixed unit length, constitutethe (real) number line.We will use the number line to construct five sets of numbers of interest to us: The set N of natural numbers—Definition 0.5; The set Z of integers—Definition 0.11; The set Q of rational numbers—Definition 0.24; The set R of real numbers—Definition 0.25; and The set C of complex numbers—Definition 0.31.Each of these sets has a different character and is used for different purposes, as we willsee both later in this chapter and throughout this book.Natural numbers (N)The natural numbers are the numbers used for counting—they are the answers to questions of the form ‘how many’—for example, I have three uncles, one dog and zero cats.3
Chapter 0. Getting started4Counting is a skill humans have had for a very long time; we know this because thereis evidence of people using tally marks tens of thousands of years ago. Tally marksprovide one method of counting small numbers: starting with nothing, proceed throughthe objects you want to count one by one, and make a mark for every object. When youare finished, there will be as many marks as there are objects. We are taught from a youngage to count with our fingers; this is another instance of making tally marks, where nowinstead of making a mark we
ISBN 978-1-950215-00-3 (paperback) ISBN 978-1-950215-01-0 (hardback) A free PDF copy of An Infinite Descent into Pure Mathematics can be obtained from the book’s website: https://infinitedescent.xyz This book, its figures and its TEX source are released under a Creative Commons Attrib
Mirror descent 5-2 Convex and Lipschitz problems minimizex f (x) subject to x ! C f is convex andLf-Lipschitz continuous Mirror descent 5-35 Outline Mirror descent Bregman divergence Alternative forms of mirror descent Convergence analysis f (xt) !! f (xt),x " xt " " 1 2!t #x " xt#2
and the hubness phenomenon (Section 2.2), which, as we will de-monstrate later, has a significant impact on NN-Descent. 2.1 NN-Descent The main purpose of the NN-Descent algorithm is to create a good approximation of the true K-NNG, and to create it as fast as possi-ble. The basic assumption made by NN-Descent can be summarized
Method of Gradient Descent The gradient points directly uphill, and the negative gradient points directly downhill Thus we can decrease f by moving in the direction of the negative gradient This is known as the method of steepest descent or gradient descent Steepest descent proposes a new point
Advantages when you use the Infinite Campus Gradebook Infinite Campus has a native grade book that integrates with the student information system. While other grade books (Jupiter and Canvas) are still available we hope you will try Infinite Campus' grade book. Advantages of using the Infinite Campus grade book: 1. No sync needed.
Infinite Campus has a native grade book that integrates with the student information system. While other grade books (Jupiter and Canvas) are still available we hope you will try Infinite Campus' grade book. Advantages of using the Infinite Campus grade book: 1. No sync needed. The grade book is part of the core product of Infinite Campus.
2.2 DESCENT THEORY 2.2.1 Development of Descent Theory Descent theory also known as lineage theory came to the fore in the 1940s with the publication of books like The Nuer (1940), African Political Systems (1940) etc. This theory was in much demand in the discussion of social structure in British anthropology after the 2nd World War. It had .
5.4.2 Steepest descent It is a close cousin to gradient descent and just change the choice of norm. Let’s suppose q;rare complementary: 1 q 1 r 1. Steepest descent just update x x t x, where x kuk r u u argmin kvk q 1 rf(x)T v If q 2, then x r f(x), which is exactly gradient descent.
Iowa, 348 P. Sharma, O. P. (1986) Textbook of algae. Tata Mcgrawhill Publishing company Ltd. New Delhi. 396. p. UNESCO (1978) Phytoplankton manual. Unesco, Paris. 337 p. Table 1: Relative abundance of dominant phytoplankton species in water sarnples and stomach/gut of bonga from Parrot Island. Sample Water date 15/1/04 LT (4, 360 cells) Diatom 99.2%, Skeletonema costatum-97.3% HT (12, 152 .
