Math 13 — An Introduction to Abstract Mathematics NeilDonaldson&AlessandraPantano January21,2020 Contents 1 Introduction 3 2 LogicandtheLanguageofProofs 9 2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 MethodsofProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 DivisibilityandtheEuclideanAlgorithm 46 3.1 RemaindersandCongruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 GreatestCommonDivisorsandtheEuclideanAlgorithm . . . . . . . . . . . . . . . . . 53 4 SetsandFunctions 59 4.1 SetNotationandDescribingaSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3 Unions,Intersections,andComplements . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.4 IntroductiontoFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5 MathematicalInductionandWell-ordering 86 5.1 InvestigatingRecursiveProcesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2 ProofbyInduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.3 Well-orderingandthePrincipleofMathematicalInduction . . . . . . . . . . . . . . . . 96 5.4 StrongInduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6 SetTheory,PartII 110 6.1 CartesianProducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.2 PowerSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 IndexedCollectionsofSets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7 RelationsandPartitions 131 7.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.2 Functionsrevisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.3 EquivalenceRelations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.4 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 7.5 Well-definition,RingsandCongruence. . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 7.6 FunctionsandPartitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 1 8 CardinalitiesofInfiniteSets 165 8.1 Cantor’sNotionofCardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.2 UncountableSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 UsefulTexts • BookofProof,RichardHammack,2nded2013. Availablefreeonline! Verygoodonthebasics: if you’rehavingtroublewithreadingsetnotationorhowtoconstructaproof,thisbook’sforyou! Thesenotesaredeliberatelypitchedatahighlevelrelativetothistextbooktoprovidecontrast. • MathematicalReasoning,TedSundstrom,2nded2014. Availablefreeonline! Excellentresource. Ifyouwouldliketobuytheactualbook,youcanpurchaseitonAmazonatareallycheapprice. • MathematicalProofs: ATransitiontoAdvancedMathematics,Chartrand/Polimeni/Zhang, 3rdEd 2013, Pearson. The most recent course text. Has many, many exercises; the first half is fairly straightforwardwhilethesecondhalfismuchmorecomplexanddauntinglydetailed. • The Elements of Advanced Mathematics, Steven G. Krantz, 2nd ed 2002, Chapman & Hall and FoundationsofHigherMathematics,PeterFletcherandC.WaynePatty,3thed2000,Brooks–Cole areoldcoursetextbooksforMath13. Botharereadableandconcisewithgoodexercises. LearningOutcomes 1. Developingtheskillsnecessarytoreadandpracticeabstractmathematics. 2. Understandingtheconceptofproof,andbecomingacquaintedwithseveralprooftechniques. 3. Learning what sort of questions mathematicians ask, what excites them, and what they are lookingfor. 4. Introducingupper-divisionmathematicsbygivingatasteofwhatiscoveredinseveralareasof thesubject. Alongthewayyouwilllearnnewtechniquesandconcepts. Forexample: NumberTheory 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 howmuchcandyeachpersontook? GeometryandTopology HowcanwevisualizeandcomputewithobjectsliketheMobiusstrip? Fractals Howtousesequencesofsetstoproduceobjectsthatappearthesameatallscales. ToInfinityandBeyond! Whyaresomeinfinitiesgreaterthanothers? 1 Introduction WhatisMathematics? 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- culussequence. Somestudentswillresistthisfactandspendmuchofthetermprogressingthrough the various stages of grief (denial, anger, bargaining, depression, acceptance) as they discover that whattheythoughttheyexcelledatisn’treallywhatthesubjectisabout. Thusweshouldstartatthe beginning,withanattempttoplacethemathematicsyou’velearnedwithinthegreatercontextofthe subject. TheoriginalGreekmeaningofthewordmathemataisthesupremelyunhelpful,“Thatwhichisto beknown/learned.” Thereisnoperfectanswertoourquestion,butasimplisticstartingpointmight betothinkofyourmathematicseducationasaprogression. Arithmetic CollegeCalculus AbstractMathematics Inelementaryschoolyoulargelylearnarithmeticandthebasicnotionsofshape. Thisisthemathe- maticsallofusneedinordertofunctionintherealworld. Ifyoudon’tknowthedifferencebetween 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- agesandyouarethoroughlyequippedformostthingslifewillthrowatyou. 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 canuseanti-derivativestocomputearea. Toanengineer,thefactthatintegralscanbeusedtomodel 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,bothpureandapplied,viewmathematicsthesameway. 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 structureappearsbeautifultothemandtheywanttoappreciateitmoredeeply. Justlikeapainting. 1Thereareveryusefulapplicationsofhigh-dimensionalprojections,notleasttoeconomicsandtheunderstandingof soundandlightwaves. 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,anditisourhopethatyouwilldevelopanappreciationforit. Proof The essential concept in higher-level mathematics is that of proof. A basic dictionary entry for the wordwouldcovertwomeanings: 1. Anargumentthatestablishesthetruthofafact. 2. Atestortrialofanassertion.2 Inmathematicswealwaysmeantheformer, whileinmuchofscienceandwiderculturethesecond meaning predominates. Indeed mathematics is one of the very few disciplines in which one can categoricallysaythatsomethingistrueorfalse. Inrealitywecanrarelybesocertain. Agreasysales- 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 mightprovidesomejustification: e.g. 100peopleusedtheproductforamonthand75ofthemclaim 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 if75%ofpeoplethinkacreamhelps,thenitprobablyisdoingsomethingbeneficial. Inmathematics andphilosophy,wethinkverydifferently: theconceptsoftrueandfalseandofproofareveryprecise. Sohowdomathematiciansreachthisblissfulstatewhereeverythingiseitherrightorwrongand, once proved, is forever and unalterably certain? The answer, rather disappointingly, is by cheating. Nothinginmathematicsistrueexceptwithreferencetosomeassumption. Forexample,considerthe followingtheorem: Theorem1.1. Thesumofanytwoevenintegersiseven. Weallbelievethatthisistrue,butcanweproveit? Inthesenseoftheseconddefinitionofproof, itmightseemlikeallweneedtodoistotesttheassertion: forexample4+6 = 10iseven. Inthefirst sense, the mathematical sense, of proof, this is nowhere near enough. What we need is a definition of even.3 Definition1.2. Anintegerisevenifitmaybewrittenintheform2nwherenisaninteger. Theproofofthetheoremnowflowsstraightfromthedefinition. 2ItisthisnotionthatmakessenseoftheseeminglyoxymoronicphraseTheexceptionprovestherule. Itistheexception thatteststhevalidityoftherule. 3Andmorefundamentallyofsumandinteger. 4 Proof. Let xandybeanytwoevenintegers. Wewanttoshowthat x+yisaneveninteger. Bydefinition,anintegerisevenifitcanbewrittenintheform2kforsomeintegerk. Thusthereexist integersn,msuchthat x = 2mandy = 2n. Wecompute: x+y = 2m+2n = 2(m+n). ( ) ∗ Becausem+nisaninteger,thisshowsthat x+yisaneveninteger. Thereareseveralimportantobservations: • ‘Any’ in the statement of the theorem means the proof must work regardless of what even in- tegers you choose. It is not good enough to simply select, for example, 4 and 16, then write 4+16 = 20. Thisisanexample,ortest,ofthetheorem,notamathematicalproof. • Accordingtothedefinition,2mand2ntogetherrepresentallpossiblepairsofevennumbers. • Theproofmakesdirectreferencetothedefinition. Thevastmajorityoftheproofsinthiscourse are of this type. If you know the definition of every word in the statement of a theorem, you willoftendiscoveraproofsimplybywritingdownthedefinitions. • The theorem itself did not mention any variables. The proof required a calculation for which thesewereessential. Inthiscasethevariablesmandncomeforfreeonceyouwritethedefinition of evenness! A great mistake is to think that the proof is nothing more than the calculation ( ). ∗ Thisistheeasybit,anditmeansnothingwithoutthesurroundingsentences. Theimportantlinkbetweentheoremsanddefinitionsismuchofwhatlearninghigher-levelmath- ematicsisabout. Weprovetheorems(andsolvehomeworkproblems)becausetheymakeususeand understandthesubtletiesofdefinitions. Onedoesnotknowmathematics,onedoesit. Mathematicsis apractice;anartasmuchasitisascience. Conjectures In this course, you will discover that one of the most creative and fun aspects of mathematics is the artofformulating,provinganddisprovingconjectures. Togetataste,considerthefollowing: Conjecture1.3. Ifnisanyoddinteger,thenn2 1isamultipleof8. − Conjecture1.4. Foreverypositiveintegern,theintegern2+n+41isprime. Aconjectureisthemathematician’sequivalentoftheexperimentalscientist’shypothesis: astate- ment that one would like to be true. The difference lies in what comes next. The mathematician will try to prove that a conjecture is undeniably true by relying on logic, while the scientist will ap- ply the scientific method, conducting experiments attempting, and hopefully failing, to show that a hypothesisisincorrect. 5 Onceamathematicianprovesthevalidityofaconjectureitbecomesatheorem. Thejobofamath- ematicsresearcheristhustoformulateconjectures,provethem,andpublishtheresultingtheorems. The creativity lies as much in the formulation as in the proof. As you go through the class, try to formulate conjectures. Like as not, many of your conjectures will be false, but you’ll gain a lot from tryingtoformthem. Let us return to our conjectures: are they true or false? How can we decide? As a first attempt, we may try to test the conjectures by computing with some small integers n. In practice this would bedonebeforestatingtheconjectures. n 1 3 5 7 9 11 13 n 1 2 3 4 5 6 7 n2 1 0 8 24 48 80 120 168 n2+n+41 43 47 53 61 71 83 97 − Because 0, 8, 24, 48, 80, 120 and 168 are all multiples of 8, and 43, 47, 53, 61, 71, 83 and 97 are all prime,bothconjecturesappeartobetrue. Wouldyoubet$100thatthisisindeedthecase? Isn2 1a − multipleof8foreveryoddinteger n? Is n2+n+41primeforeverypositiveinteger n? Theonlyway toestablishwhetheraconjectureistrueorfalseisbydoingoneofthefollowing: Proveitbyshowingitmustbetrueinallcases,or, Disproveitbyfindingatleastoneinstanceinwhichtheconjectureisfalse. Let us work with Conjecture 1.3. If n is an odd integer, then, by definition, we can write it as n = 2k+1forsomeintegerk. Then n2 1 = (2k+1)2 1 = (4k2+1+4k) 1 = 4k2+4k. − − − Weneedtoinvestigatewhetherthisisalwaysamultipleof8. Since 4k2+4k = 4(k2+k) isalreadyamultipleof4,itallcomesdowntodecidingwhetherornot k2+k containsafactor2for all possible choices of k; i.e. is k2 +k even? Do we believe this? We can return to trying out some smallvaluesofk: k 2 1 0 1 2 3 4 − − k2+k 2 0 0 2 6 12 20 Onceagain,theclaimseemstobetrueforsmallvaluesof k,buthowdoweknowitistrueforall k? Again,theonlywayistoproveitordisproveit. Howtoproceed? Thequestionhereiswhetherornot k2+kisalwayseven. Factoringoutk,weget: k2+k = k(k+1). We have therefore expressed k2+k as a product of two consecutive integers. This is great, because foranytwoconsecutiveintegers,oneisevenandtheotherisodd,andsotheirproductmustbeeven. Wehavenowprovedthattheconjectureistrue. Conjecture1.3isindeedatheorem! Everythingwe’ve donesofarhasbeeninvestigative,andislaidoutinanuntidyway. Wedon’twantthereadertohave towadethroughallofourscratchwork,soweformalizetheaboveargument. Thisisthefinalresult of our deliberations; investigate, spot a pattern, conjecture, prove, and finally present your work in ascleanandconvincingamannerasyoucan. 6 Theorem1.5. Ifnisanyoddinteger,thenn2 1isamultipleof8. − Proof. Let n be any odd integer; we want to show that n2 1 is a multiple of 8. By the definition of − oddinteger,wemaywriten = 2k+1forsomeintegerk. Then n2 1 = (2k+1)2 1 = (4k2+1+4k) 1 = 4k2+4k = 4k(k+1). − − − Wedistinguishtwocases. Ifkiseven,thenk(k+1)isevenandso4k(k+1)isdivisibleby8. Ifkisodd,thenk+1iseven. Thereforek(k+1)isagainevenand4k(k+1)divisibleby8. Inbothcasesn2 1 = 4k(k+1)isdivisibleby8. Thisconcludestheproof. − ItisnowtimetoexploreConjecture1.4. Thequestionhereiswhetherornotn2+n+41isaprime integerforeverypositiveintegern. Weknowthatwhenn = 1, 2, 3, 4, 5, 6or7theanswerisyes,but examplesdonotmakeaproof. Atthispoint,wedonotknowwhethertheconjectureistrueorfalse. Letusinvestigatethequestionfurther. Supposethatnisanypositiveinteger;wemustaskwhetherit ispossibletofactorn2+n+41asaproductoftwopositiveintegers,neitherofwhichisone.4 When n = 41suchafactorizationcertainlyexists,sincewecanwrite 412+41+41 = 41(41+1+1) = 41 43. · Ourcounterexampleshowsthatthereexistsatleastonevalueofn forwhichn2+n+41isnotprime. Wehavethereforedisprovedtheconjecturethat‘forallpositiveintegersn,n2+n+41isprime,’and soConjecture1.4isfalse! Themoralofthestoryisthis: toshowthataconjectureistrueyoumustprovethatitholdsfor allthecasesinconsideration,buttoshowthatitisfalseasinglecounterexamplesuffices. Conjectures: TrueorFalse? Do your best to prove or disprove the following conjectures. Then revisit these problems at the end ofthecoursetorealizehowmuchyourproofskillshaveimproved. 1. Thesumofanythreeconsecutiveintegersiseven. 2. Thereexistintegersmandnsuchthat7m+5n = 4. 3. Everycommonmultipleof6and10isdivisibleby60. 4. Thereexistintegers xandysuchthat6x+9y = 10. 5. Foreverypositiverealnumber x, x+ 1 isgreaterthanorequalto2. x 6. If xisanyrealnumber,then x2 x. ≥ 4Onceagainwerelyonadefinition:apositiveintegerisprimeifitcannotbewrittenasaproductoftwointegers,both greaterthanone. 7 7. Ifnisanyinteger,n2+5nmustbeeven. 8. If xisanyrealnumber,then x x. | | ≥ − 9. ConsiderthesetRofallrealnumbers. Forall xinR,thereexistsyinRsuchthat x < y. 10. ConsiderthesetRofallrealnumbers. Thereexists xinRsuchthat,forallyinR, x < y. 11. Thesets A = n N : n2 < 25 and B = n2 : n Nandn < 5 areequal. HereNdenotes { ∈ } { ∈ } thesetofnaturalnumbers. Nowweknowalittleofwhatmathematicsisabout,itistimetopracticesomeofit! 8 2 Logic and the Language of Proofs In order to read and construct proofs, we need to start with the language in which they are written: logic. Logic is to mathematics what grammar is to English. Section 2.1 will not look particularly mathematical,butwe’llquicklygettoworkinSection2.2usinglogicinamathematicalcontext. 2.1 Propositions Definition2.1. Apropositionorstatementisasentencethatiseithertrueorfalse. Examples. 1. 17 24 = 7. − 2. 392 isanoddinteger. 3. Themoonismadeofcheese. 4. Everycloudhasasilverlining. 5. Godexists. In order to make sense, these propositions require a clear definition of every concept they contain. TherearemanyconceptsofGodinmanycultures,butonceitisdecidedwhichwearetalkingabout, itisclearthatTheyeitherexistordonot. Thisexampleillustratesthatastatementneednotbeindis- putablytrueorfalse,orevendeterminable,inordertoqualifyasaproposition. Mostlywhenpeople argueoverpropositionsandstatements,whattheyarereallydisagreeingaboutaredefinitions! Notethatanyexpressionthatisneithertruenorfalseisnotaproposition. January1st isnotapropo- sition,neitherisGreen. TruthTables Oneoftenhastodealwithabstractpropositions;thosewhereyoudonotknowthetruthorfalsity,or indeedwhenyoudon’texplicitlyknowtheproposition! Insuchcasesitcanbeconvenienttorepre- sentthecombinationsofpropositionsinatabularformat. Forinstance,ifwehavetwopropositions (P and Q), or even three (P,Q and R) then all possible combinations of truth T and falsehood F are representedinthefollowingtables: P Q P Q R T T T T T T F T T F F T T F T F F T F F F T T F T F F F T F F F Themathematicianinyoushouldbelookingforpatternsandasking: howmanyrowswouldatruth table corresponding to n propositions have, and can I prove my assertion? Right now it is hard to provethattheansweris2n: induction(Chapter5)makesthisveryeasy. 9 ConnectingPropositions: Conjunction,DisjunctionandNegation Wenowdefinehowtocombinepropositionsinnaturalways,modeledonthewordsand,orandnot. Definition 2.2. Let P and Q be propositions. The conjunction (AND, ) of P and Q, the disjunction ∧ (OR, )of PandQ,andthenegationordenial(NOT, , , )of Paredefinedbythetruthtables, ∨ ¬ ∼ P Q P Q P Q P Q P P ∧ ∨ ¬ T T T T T T T F T F F T F T F T F T F F T T F F F F F F It is usually better to use and, or and not rather than conjunction, disjunction and negation: the latter maymakeyousoundeducated,butattheriskofbeingmisunderstood! Example. Let P,Qand Rbethefollowingpropositions: P. IrvineisacityinCalifornia. Q. IrvineisatowninAyrshire,Scotland. R. Irvinehassevenletters. Clearly P is true while R is false. If you happen to know someone from Scotland, you might know thatQistrue.a Wecannowcomputethefollowing(increasinglygrotesque)combinations... P Q P Q P R R ( R) P (R P) ( P) [(( R) P) Q] ∧ ∨ ∧ ¬ ¬ ∧ ¬ ∨ ¬ ∨ ¬ ∨ ∧ T T F T T F T aThesecondsyllableispronouncedliketheiinbinorwin. IndeedthefirstCalifornianantecedentoftheIrvinefamily which gave its name to UCI was an Ulster-Scotsman named James Irvine (1827–1886). Probably the family name was originalypronouncedintheScottishmanner. How did we establish these facts? Some are quick, and can be done in your head. Consider, for instance,thestatement ( R) P. Because R isfalse, R istrue. Thus ( R) P istheconjunctionof ¬ ∧ ¬ ¬ ∧ twotruestatements,henceitistrue. Similarly,wecanarguethatR Pistrue(becauseRisfalseand ∨ Pistrue),sothenegation (R P)isfalse. ¬ ∨ Establishing the truth value of the final proposition ( P) [(( R) P) Q] requires more work. ¬ ∨ ¬ ∨ ∧ Youmaywanttosetupatruthtablewithseveralauxiliarycolumnstohelpyoucompute: P Q R P R ( R) P (( R) P) Q ( P) [(( R) P) Q] ¬ ¬ ¬ ∨ ¬ ∨ ∧ ¬ ∨ ¬ ∨ ∧ T T F F T T T T Theimportance of parentheses in alogical expressions cannot bestressed enough. For example, try buildingthetruthtableforthepropositions P (Q R)and(P Q) R. Aretheythesame? ∨ ∧ ∨ ∧ 10