Then xax xax xax xax morgans law morgans law

Ethan D. Bloch

Proofs and Fundamentals

Editorial Board
S. Axler K.A. Ribet

Mathematics Department
San Francisco State University San Francisco, CA 94132

© Springer Science+Business Media, LLC 2011
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

Preface to the Second Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

Preface to the First Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv

Though the bulk of the text has remained unchanged from the first edition, there are a number of changes, large and small, that will hopefully improve the text. As always, any remaining problems are solely the fault of the author.

Changes from the First Edition to the Second Edition

(3) The chapter on the construction of the natural numbers, integers and ratio-nal numbers from the Peano Postulates was removed entirely. That material was originally included to provide the needed background about the number systems, particularly for the discussion of the cardinality of sets in Chapter 6, but it was always somewhat out of place given the level and scope of this text. The background material needed for Chapter 6 has now been summarized in a new section at the start of that chapter, making the chapter both self-contained and more accessible than it previously was. The construction of the number systems from the Peano Postulates more properly belongs to a course in real analysis or in the foundations of mathematics; the curious reader may find this material in a variety of sources, for example [Blo11, Chapter 1].

(4) Section 3.4 on families of sets has been thoroughly revised, with the focus being on families of sets in general, not necessarily thought of as indexed.

(9) Many minor adjustments of wording have been made throughout the text, with the hope of improving the exposition.

Preface to the Second Edition xiii

My appreciation goes to Ann Kostant, now retired Executive Editor of Mathemat-ics/Physics at Birkh¨auser, for her unceasing support of this book, and to Elizabeth Loew, Senior Editor of Mathematics at Springer-Verlag, for stepping in upon Ann’s retirement and providing me with very helpful guidance. I would like to thank Shel-don Axler and Kenneth Ribet, the editors of Undergraduate Texts in Mathematics, for their many useful suggestions for improving the book. Thanks also go to Nathan Brothers and the copyediting and production staff at Springer-Verlag for their ter-rific work on the book; to Martin Stock for help with LATEX; and to Pedro Quaresma for assistance with his very nice LATEX commutative diagrams package DCpic, with which the commutative diagrams in this edition were composed.

I would very much like to thank the Einstein Institute of Mathematics at the Hebrew University of Jerusalem, and especially Professor Emanuel Farjoun, for their very kind hospitality during a sabbatical when this edition was drafted.

This text contains core topics that the author believes any transition course should cover, as well as some optional material intended to give the instructor some flexi-bility in designing a course. The presentation is straightforward and focuses on the essentials, without being too elementary, too excessively pedagogical, and too full of distractions.

Some of the features of this text are the following:

(4) The material is presented in the way that mathematicians actually use it rather than in the most axiomatically direct way. For example, a function is a special type of a relation, and from a strictly axiomatic point of view, it would make sense to treat relations first, and then develop functions as a special case of relations. Most mathematicians do not think of functions in this way (except perhaps for some combinatorialists), and we cover functions before relations, offering clearer treatments of each topic.

(5) A section devoted to the proper writing of mathematics has been included, to help remind students and instructors of the importance of good writing.

Part III, Extras, consists of Chapters 7 and 8, and has brief treatments of a variety of topics, including groups, homomorphisms, partially ordered sets, lattices, combi-natorics and sequences, and concludes with additional topics for exploration by the reader, as well as a collection of attempted proofs (actually submitted by students) which the reader should critique as if she were the professor.

Some instructors might choose to skip Section 4.5 and Section 6.4, the former be-cause it is very abstract, and the latter because it is viewed as not necessary. Though skipping either or both of these two sections is certainly plausible, instructors are urged to consider not to do so. Section 4.5 is intended to help students prepare for dealing with sets of linear maps in linear algebra, and comparable constructions in other branches of mathematics. Section 6.4 is a topic that is often skipped over in the mathematical education of many undergraduates, and that is unfortunate, because

Thanks go to the following individuals for their valuable assistance, and ex-tremely helpful comments on various drafts: Robert Cutler, Peter Dolan, Richard Goldstone, Mark Halsey, Leon Harkleroad, Robert Martin, Robert McGrail and Lau-ren Rose. Bard students Leah Bielski, AmyCara Brosnan, Sean Callanan, Emilie Courage, Urska Dolinsek, Lisa Downward, Brian Duran, Jocelyn Four´e, Jane Gilvin, Shankar Gopalakrishnan, Maren Holmen, Baseeruddin Khan, Emmanuel Kypraios, Jurvis LaSalle, Dareth McKenna, Daniel Newsome, Luke Nickerson, Brianna Nor-ton, Sarah Shapiro, Jaren Smith, Matthew Turgeon, D. Zach Watkinson and Xiaoyu Zhang found many errors in various drafts, and provided useful suggestions for im-provements.

My appreciation goes to Ann Kostant, Executive Editor of Mathematics/Physics at Birkh¨auser, for her unflagging support and continual good advice, for the second time around; thanks also to Elizabeth Loew, Tom Grasso, Amy Hendrickson and Martin Stock, and to the unnamed reviewers, who read through the manuscript with eagle eyes. Thanks to the Mathematics Department at the University of Pennsylva-nia, for hosting me during a sabbatical when parts of this book were written. The commutative diagrams in this text were composed using Paul Taylor’s commutative diagrams package.

To the Student

This book is designed to bridge the large conceptual gap between computational courses such as calculus, usually taken by first- and second-year college students, and more theoretical courses such as linear algebra, abstract algebra and real anal-ysis, which feature rigorous definitions and proofs of a type not usually found in calculus and lower-level courses. The material in this text was chosen because it is, in the author’s experience, what students need to be ready for advanced mathematics courses. The material is also worth studying in its own right, by anyone who wishes to get a feel for how contemporary mathematicians do mathematics.

Prerequisites

A course that uses this text would generally have as a prerequisite a standard calculus sequence, or at least one solid semester of calculus. In fact, the calculus prerequisite is used only to insure a certain level of “mathematical maturity,” which means suf-ficient experience—and comfort — with mathematics and mathematical thinking. Calculus per se is not used in this text (other than an occasional reference to it in the exercises); neither is there much of pre-calculus. We do use standard facts about numbers (the natural numbers, the integers, the rational numbers and the real num-bers) with which the reader is certainly familiar. See the Appendix for a brief list of some of the standard properties of real numbers that we use. On a few occasions we will give an example with matrices, though such examples can easily be skipped.

To the Student xxi

Mathematical Notation and Terminology

What This Text Is Not

Mathematics as an intellectual endeavor has an interesting history, starting in such ancient civilizations such as Egypt, Greece, Babylonia, India and China, progressing through the Middle Ages (especially in the non-Western world), and accelerating up until the present time. The greatest mathematicians of all time, such as Archimedes,

To the Instructor

There is an opposing set of pedagogical imperatives when teaching a transition course of the kind for which this text is designed: On the one hand, students often need assistance making the transition from computational mathematics to abstract mathematics, and as such it is important not to jump straight into water that is too deep. On the other hand, the only way to learn to write rigorous proofs is to write rigorous proofs; shielding students from rigor of the type mathematicians use will only ensure that they will not learn how to do mathematics properly.

One place where too much indulgence is given, however, even in more advanced mathematics courses, and where such indulgence is, the author believes, quite mis-guided, involves the proper and careful writing of proofs. Seasoned mathematicians make honest mathematical errors all the time (as we should point out to our students), and we should certainly understand such errors by our students. By contrast, there is simply no excuse for sloppiness in writing proofs, whether the sloppiness is physical (hastily written first drafts of proofs handed in rather than neatly written final drafts) or in the writing style (incorrect grammar, undefined symbols, etc.). Physical sloppi-ness is often a sign of either laziness or disrespect, and sloppiness in writing style is often a mask for sloppy thinking.

The elements of writing mathematics are discussed in detail in Section 2.6. It is suggested that these notions be used in any course taught with this book (though of course it is possible to teach the material in this text without paying attention to proper writing). The author has heard the argument that students in an introductory course are simply not ready for an emphasis on the proper writing of mathematics, but his experience teaching says otherwise: not only are students ready and able to write carefully no matter what their mathematical sophistication, but they gain much from the experience because careful writing helps enforce careful thinking. Of course, students will only learn to write carefully if their instructor stresses the importance of writing by word and example, and if their homework assignments and tests include comments on writing as well as mathematical substance.

Logic is the hygiene the mathematician practices to keep his ideas healthy and strong.

– Hermann Weyl (1885–1955)

E.D. Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics, 3

Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-7127-2_1, © Springer Science+Business Media, LLC 2011

1.2 Statements

When we prove theorems in mathematics, we are demonstrating the truth of certain statements. We therefore need to start our discussion of logic with a look at state-ments, and at how we recognize certain statements as true or false. A statement is anything we can say, write or otherwise express that is either true or false. For ex-ample, the expression “Fred Smith is twenty years old” is a statement, because it is either true or false. We might not know whether this statement is actually true or not, because to know that would require that we know some information about Fred Smith, for example his date of birth, and that information might not be available to us. For something to be a statement, it has to be either true or false in principle; it does not matter whether we personally can verify its truth or falsity. By contrast, the expression “Eat a pineapple” is not a statement, because it cannot be said to be either true or false.

as “Not Susan likes mushy bananas,” both because that is not proper English, and Let P = “Susan likes mushy bananas.” It would not work in English to write ¬P

because it appears as if the subject of the sentence is someone named “Not Susan.”The most straightforward way of negating P is to write ¬P = “it is not the case that Susan likes mushy bananas.” While formally correct, this last statement is quite awkward to read, and it is preferable to replace it with an easier-to-read expression, for example “Susan does not like mushy bananas.”
Our final two ways of combining statements, both of which are connected to the idea of logical implication, are slightly more subtle than what we have seen so far. Consider the statement “If Fred goes on vacation, he will read a book.” What would it mean to say that this statement is true? It would not mean that Fred is going on vacation, nor would it mean that Fred will read a book. The truth of this statement means only that if one thing happens (namely, Fred goes on vacation), then another thing will happen (namely, Fred reads a book). In other words, the one way in which this statement would be false would be if Fred goes on vacation, but does not read a book. The truth of this statement would not say anything about whether Fred will or will not go on vacation, nor would it say anything about what will happen if Fred does not go on vacation. In particular, if Fred did not go on vacation, then it would not contradict this statement if Fred read a book nonetheless.

1.2 Statements 9

(4) The U.S. has 49 states.

(5) I like to eat fruit, and you often think about traveling to Spain. (6) If we go out tonight, the babysitter will be unhappy.

(4) x+y = z.

(5) (a+b)2= a2+2ab+b2. (6) a2+b2= c2.

(1) Z → X.

(2) X ↔︎ Y.

(1) Fred does not like to eat figs.

(2) Fred has red hair, and does not have a big nose.

(7) It is not the case that Fred has a big nose, or he has red hair.

(8) Fred has a big nose and red hair, or he has a big nose and likes to eat figs.

(4) The house is not ugly if and only if it is 30 years old.

(5) The house is 30 years old if it is blue, and it is not ugly if it is 30 years old. (6) For the house to be ugly, it is necessary and sufficient that it be ugly and 30 years old.

(5) (D∧A)∨(B∧C).
(6) C ∨[D∨(A∧B)].

Exercise 1.2.8. Suppose that X is a false statement, that Y is a true statement, that Z is a false statement and that W is a true statement. Which of the following statements are true, and which are false?

(4) W → (X → ¬W).

(5) [(Y → W) ↔︎ W]∧¬X. (6) (W → X) ↔︎ ¬(Z ∨Y).

(4) Flora likes fruit or nuts, and she likes carrots or rutabagas.

(5) Flora likes rutabagas, or she likes fruit and either carrots or rutabagas.

(5) If Hector likes lentils then he likes sunflower seeds, or Hector likes lentils if and only if he likes peas.

(6) For Hector to like beans and lentils it is necessary and sufficient for him to like peas or sunflower seeds.

Exercise 1.2.12. Make a truth table for each of the following statements.

(1) X → ¬Y.

(1) P∨(¬P∧Q).

(2) (X ∨Y) ↔︎ (¬X → Y).

(7) [(P ↔︎ ¬Q)∧P]∧Q.

Exercise 1.2.14. Which of the following statements are tautologies, which are con-tradictions and which are neither?

(6) The cow is green or the cow is not green, if and only if the goat is blue and the goat is not blue.

Exercise 1.2.15. Let P be a statement, let T be a tautology and let C be a contradic-tion.

The two examples of relations between statements given above represent the two types of such relations we will study, namely, implication and equivalence, which are the meta-statement analogs of conditionals and biconditionals. We start with im-plication.

The intuitive idea of logical implication is that statement P implies statement Q if necessarily Q is true whenever P is true. In other words, it can never be the case that

statement [¬(P → Q)] → (P∨Q) will be a tautology (also in Section 1.2), as can be

1.3 Relations Between Statements 17

(Simplification).

(Addition).

(Hypothetical Syllogism).

(Conditional-Biconditional).

We see in Column 7 that the statement [(P → Q)∧P] → Q is always true, and hence it is a tautology. ///

What interests us are logically equivalent statements that are not simply English variants of the same symbolic statement, but rather are truly different statements. For example, the statement “it is not that case that I do not own a bicycle” will be seen to be equivalent to “I own a bicycle.” If we let P = “I own a bicycle,” then the statement“it is not that case that I do not own a bicycle” is ¬(¬P). This statement is not identi-cal to P. It will be very important to us to be able to recognize that some non-identical statements, for example ¬(¬P) and P, are in fact logically equivalent. Such equiv-alences will allow us to find alternative forms of the statements of some theorems, and these alternative forms are sometimes easier to prove than the originals.

The intuitive idea of equivalence of statements is that to claim that statements P and Q are equivalent means that necessarily P is true if and only if Q is true. Necessity is once again the key here, as can be seen once more using the statements

(Commutative Law).

(Commutative Law).

We see in Column 13 that the statement[P∨(Q∧R)] ↔︎ [(P∨Q)∧(P∨R)], and hence it is a tautology. ///

Part (1) of Fact 1.3.2 might appear innocuous, but this equivalence plays a very important role in standard mathematical proofs. In informal terms, the equivalence of ¬(¬P) and P means that “two negatives cancel each other out.” From the point of view of constructing mathematical proofs, suppose that we want to show that a statement P is true. One method to prove this statement would be to hypothesize that¬P is true, and derive a contradiction. It would then follow that ¬P is false, which implies that ¬(¬P) is true. Because ¬(¬P) and P are equivalent, it would follow that P is true. This methodology of proof might sound rather convoluted, but it is often quite useful, and is called proof by contradiction. A detailed discussion of this method of proof is in Section 2.3.

tant for constructing mathematical proofs, as seen in Section 2.3, relevant terminol-Because the equivalence of the statements P → Q and ¬Q → ¬P will be so impor-

ogy is merited. Given a conditional statement of the form P → Q, we call ¬Q → ¬P the contrapositive of the original statement. For example, the contrapositive of “if I eat too much I will feel sick” is “if I do not feel sick I did not eat too much.”Fact 1.3.2 (9) says that a statement and its contrapositive are always equivalent.

Exercise 1.3.1. Let P, Q, R and S be statements. Show that the following are true.

(1) ¬(P → Q) ⇒ P.

(6) (P ↔︎ R)∧(Q ↔︎ S) ⇒ (P∨Q) ↔︎ (R∨S).

Exercise 1.3.2. [Used in Exercise 1.3.12 and Section 2.4.] Let P, Q, A and B be state-ments. Show that the following are true.

1.3 Relations Between Statements 23

Exercise 1.3.3. Let P be a statement, let T be a tautology and letC be a contradiction.

Exercise 1.3.5. For each pair of statements, determine whether or not the two state-ments are equivalent.

(1) “If it rains, then I will see a movie”; and “it is not raining or I will see a movie.”
(2) “This shirt has stripes, and it has short sleeves or a band collar”; and “this shirt has stripes and it has short sleeves, or it has a band collar.”
(3) “It is not true that I like apples and oranges”; and “I do not like apples and I do not like oranges.”
(4) “The cat is gray, or it has stripes and speckles”; and “the cat is gray or it has stripes, and the cat is gray or it has speckles.”
(5) “It is not the case that: melons are ripe if and only if they are soft to the touch”; and “melons are ripe and soft to the touch, or they are not ripe or not soft to the touch.”

(2) I will go home if it is after midnight.

(3) Good fences make good neighbors.

Exercise 1.3.10. Negate each of the following statements.

(1) e5> 0. (4) If y = 3 then y2= 7.

(4) If I tell you a joke, you will smile.

(5) The play will end on time if and only if the actors are in good spirits. (6) The room will get painted if you buy the paint.

(1) The operations ∧ and ∨ are examples of binary logical operations, in that they take two inputs and give one output; the operation ¬ is an example of a unary logical operation, in that it takes one input and gives one output. How many possible unary and binary logical operations are there? List all of them using truth tables, and give the familiar names to those that we have already seen.

If the poodle-o-matic is cheap or is energy efficient, then it will not make money for the manufacturer. If the poodle-o-matic is painted red, then it will make money for the manufacturer. The poodle-o-matic is cheap. Therefore the poodle-o-matic is not painted red.

This collection of statements is an example of a logical argument, which in general is a collection of statements, the last of which is the conclusion of the argument, and the rest of which are the premises of the argument. Clearly, the use of the word“argument” in logic is different from the colloquial use of the word, where it could

A few of the rules of inference listed above were not treated in Fact 1.3.1, al-though they are easily seen to be true. Double Negation is proved in Fact 1.3.2, although here we state it as two implications, rather than one equivalence. Repetition ence. Adjunction is just a glorified version of repetition, because if we stated it in the is evidently true (because P → P is a tautology), but is still useful as a rule of infer-format of Fact 1.3.1, it would look like P∧Q ⇒ P∧Q. We now return to our argument concerning the poodle-o-matic. Using the rules of inference listed above, we can construct a justification for the argument. We use here the two-column format that may be familiar from high school geometry proofs,

28 1 Informal Logic

This sort of justification, often referred to by logicians as a derivation, is a chain of statements connected by meta-statements (namely, the justifications for each line). If an argument has a derivation, we say that the argument is derivable. Observe that the derivability of an argument is one thing, and the truth of the component statements involved is another. We can have a derivable argument with component statements that happen to be true, or happen to be false, and we can have a non-derivable argument with component statements that happen to be true, or happen to be false. The derivability of an argument is only a question of the relation of the conclusion of the argument with the premises, not whether the conclusion or premises are actually true.

For a given argument, there is often more than one possible derivation. The fol-lowing is another derivation for the poodle-o-matic argument, this time making use of the equivalences of statements given in Fact 1.3.2, in addition to our rules of infer-ence. In general, it is acceptable in a derivation to replace one statement with another that is equivalent to it. The alternative derivation is

We now face an important question: given an argument, we have two notions of whether the argument works, which are that it is or is not valid, and that it is or is not derivable. The former notion involves checking truth values (which is done with truth tables), the latter constructing a chain of statements linked by rules of in-ference. What is the relation between these two approaches? Though it is not at all obvious, nor easy to prove, it turns out quite remarkably that these two approaches, while different in nature, always yield the same result. That is, an argument is valid

1.4 Valid Arguments 29

Jethro does not play the guitar, or Susan plays the flute. If Leslie does not play the xylophone, then Susan does not play the flute. Jethro plays the gui-tar, and Leslie does not play the xylophone. Therefore Ferdinand plays the accordion.

The strange thing about this argument is that there is no apparent connection between the conclusion and the premises. However, try as you might, you will not be able to find truth values for the component statements used in the argument for which the premises are all true but the conclusion is false. The argument is in fact valid, as odd as that might appear. Let J = “Jethro plays the guitar,” let S = “Susan plays the flute,”let L = “Leslie plays the xylophone” and let F = “Ferdinand plays the accordion.”A derivation for this argument is

The moral of this story is that we should avoid arguments that have premises that form contradictions. Such premises are often called inconsistent. Premises that are not inconsistent are called consistent. It is not that there is anything logically wrong with inconsistent premises, they are simply of no use to mathematicians, because we can derive anything from them. For example, when non-Euclidean geometry was first discovered in the early nineteenth century, it was important to determine whether the proposed axiom system for such geometry was consistent or not. In many mathemat-ical situations, for example geometry, it is not possible to demonstrate consistency directly via truth tables and the like, but it was eventually shown that non-Euclidean is no less consistent than Euclidean geometry. Because Euclidean geometry is so well studied and so widely used, and its consistency is not generally doubted, it followed that non-Euclidean geometry was no less worthwhile mathematically than Euclidean geometry. See [Tru87, Chapter 7] for details.

Whereas arguments with inconsistent premises are not logically flawed, but rather do not allow for any useful conclusions, we often do encounter logical er-rors in both formal and informal argumentation. We conclude this section with a brief mention of a few common logical errors, often referred to as fallacies, that are regularly found in attempted mathematical proofs (and elsewhere).

Again this argument is invalid. The first premise says what we could conclude if the senator does a certain thing, namely, votes himself a raise. It does not say anything if that certain thing does not happen. Therefore, just because the senator did not vote himself a raise, we cannot conclude anything about his character—there could be many other things that might raise questions about him. In symbols, the argument here is (P → Q) ∧ ¬P ⇒ ¬Q. Again, there is no such implication, as can be seen by checking the appropriate truth table. This fallacy is known as the fallacy of the inverse (and is also known as the fallacy of denying the antecedent).

The third type of error we mention is of a slightly different nature. Consider the following argument.

Exercise 1.4.1. For each of the following arguments, if it is valid, give a derivation, and if it is not valid, show why.

Exercise 1.4.2. For each of the following arguments, if it is valid, give a derivation, and if it is not valid, show why.

(4) If Susan likes fish, then she likes onions. If Susan does not like garlic, then she does not like onions. If she likes garlic, then she likes guavas. She likes fish or she likes cilantro. She does not like guavas. Therefore, Susan likes cilantro.

(5) It is not the case that Fred plays both guitar and flute. If Fred does not play guitar and he does not play flute, then he plays both organ and harp. If he plays harp, then he plays organ. Therefore Fred plays organ.

(3) It is not the case that clothes are annoying or not cheap. Clothes are not cheap or they are unfashionable. If clothes are unfashionable they are silly. There-fore clothes are silly.

(4) If music soothes the soul then souls have ears. Music soothes the soul or musicians are calm. It is not the case that souls have ears or musicians are calm. Therefore musicians have souls.

(3) The cow moos whenever the pig oinks. The cow moos. Therefore the pig oinks.

(4) A nice day is sufficient for frolicking children or napping adults. Adults are napping. Therefore it is a nice day.

Our discussion of logic so far has been missing one crucial ingredient used in the formulation of theorems and proofs. We often encounter in mathematics expressions such as “x3≥ 8,” which we might wish to prove. This expression as written is not precise, however, because it does not state which possible values of x are under con-sideration. Indeed, the expression is not a statement. A more useful expression, which is a statement, would be “x3≥ 8, for all real numbers x ≥ 2.” The phrase “for all real numbers x ≥ 2” is an example of a quantifier. The other type of quantifier commonly used is the first part of the statement “there exists a real number x such that x2= 9.”What is common to both these phrases is that they tell us about the variables under consideration; they tell us what the possible values of the variable are, and whether the statement involving the variable necessarily holds for all possible values of the variable or only for some values (that is, one or more value).

The use of quantifiers vastly expands the range of possible statements that can be formed in comparison with the statements that were made in previous sections of this chapter. Quantifiers are so important that the type of logic that involves quantifiers has its own name, which is “first-order” (and is also known as “predicate”) logic; the type of logic we looked at previously is called “sentential” (and is also known as“propositional”) logic.

As a preliminary to our discussion of quantifiers, consider the expression P =“x + y > 0.” Observe that x and y have the same roles in P. Using P we can form a new expression Q = “for all positive real numbers x, the inequality x+y > 0 holds.”In contrast to P, there is a substantial difference between the roles of x and y in Q. The symbol x is called a bound variable in Q, in that we have no ability to choose which values of x we want to consider. By contrast, the symbol y is called a free variable in Q, because its possible values are not limited. Because y is a free variable in Q, it is often useful to write Q(y) instead of Q to indicate that y is free. In P both x and y are free variables, and we would denote that by writing P(x,y).

The difference between a bound variable and a free one can be seen by changing the variables in Q. If we change every occurrence of x to w in Q, we obtain ˆQ =“for all positive real numbers w, the inequality w + y > 0 holds.” For each possible value of y, we observe that ˆQ and Q have precisely the same meaning. In other words, if Q were part of a larger expression, then the larger expression would be entirely unchanged by replacing Q with ˆQ. By contrast, suppose that we change every occurrence of y to z in Q, obtaining ˜Q = “for all positive real numbers x, the inequality x + z > 0 holds.” Then ˜Q does not have the same meaning as Q, because y and z (over which we have no control in Q and ˜Q respectively) might be assigned different values, for example if Q were part of a larger expression that had both y and z appearing outside Q. In other words, changing the y to z made a difference precisely because y is a free variable in Q.

36 1 Informal Logic

be the case that P(x) is true for some values of x that are not in U, but we cannot tell that from the statement as written.

For the sake of completeness, we need to allow the case where the collection U has nothing in it. In that case, the statement (∀x in U)P(x) is always true, no matter what P(x) is, for the following reason. The statement “(∀x in U)P(x)” is equivalent to the statement “if x is in U, then P(x) is true.” When the collection U has nothing in it, then the statement “x is in U” is false, and hence the conditional statement “if x is in U, then P(x) is true” is true.

For the other type of quantifier we are interested in, once again let P(x) be a statement with free variable x, and let U denote a collection of possible values of x. An existential quantifier applied to P(x) is the statement, denoted (∃x in U)P(x), which is true if P(x) is true for at least one value of x in U. If the collection U is understood from the context, then we will write (∃x)P(x). Observe that if the It is important to note that the phrase “at least one value of x in U” means one or collection U has nothing in it, then the statement (∃x)P(x) is false.

Let Q(r) = “person r has brown hair,” and let W be the collection of all people in the world. Then the statement (∃r in W)Q(r) would mean that “there is some-one with brown hair,” or equivalently “some people have brown hair” (which is a true statement). Let E(m) = “m is an even number” and let M(m) = “m is a prime number,” where the collection of possible values of m is the integers. The statement“some integers are even and prime” can be expressed symbolically by first rephras-ing it as “there exists x such that x is even and x is prime,” which is (∃x)[E(x)∧M(x)] (this statement is true, because 2 is both even and prime).

The reader might wonder why we use only the above two types of quantifiers, and whether other quantifiers are needed. For example, the statement “no dog likes cats” clearly has a quantifier, but which quantifier is it? If we let U be the collection of all dogs, and if we let P(x) = “dog x likes cats,” then our statement is “there is no x in U such that P(x).” However, the expression “there is no x in U,” though certainly a quantifier of some sort, is neither a universal quantifier nor an existential quantifier. Fortunately, rather than needing to define a third type of quantifier to be able to handle the present statement, we can rewrite our statement in English as “every dog does not like cats,” and in symbols that becomes (∀x in U)(¬P(x)). In general, all the quantification that we need in mathematics can be expressed in terms of universal quantifiers and existential quantifiers.

38 1 Informal Logic

lead to mistakes in proving theorems that have statements with multiple quantifiers. A very important occurrence of the importance of the order of multiple quantifiers is in the “ε-δ” proofs treated in real analysis courses; see Section 7.8 for a similar type of proof from real analysis, and see any introductory real analysis text for a detailed discussion of ε-δ proofs.

(3) (∀x)(∃y)L(x,y). This statement can be written as “for each person x, there is a type of fruit y such that x likes to eat y,” and more simply as “every person likes at least one type of fruit.” To verify whether this statement is true, we would have to ask each person in the world if she likes some type of fruit; if at least one person does not like any type of fruit, then the statement would be false.

(4) (∃x)(∀y)L(x,y). This statement can be written as “there is a person x such that for all types of fruit y, person x likes to eat y,” and more simply as “there is a person who likes every type of fruit.” To verify whether this statement is true, we would start asking one person at a time if she likes every type of fruit; as soon as we found one person who answers yes, we would know that the statement is true, and we could stop asking more people. If no such person is found, then the statement would be false.

(7) (∃x)(∃y)L(x,y). This statement can be written as “there is a person x such that there is a type of fruit y such that x likes to eat y,” and more simply as“there is a person who likes at least one type of fruit.” To verify whether this statement is true, we would have to start asking one person at a time if she likes some type of fruit; as soon as we found one person who answers yes, we would know that the statement is true, and we could stop asking more people.

(8) (∃y)(∃x)L(x,y). This statement can be written as “there is a type of fruit y such that there is a person x such that x likes to eat y,” and more simply as“there is a type of fruit that is liked by at least one person.” This statement is equivalent to Statement 7.

40 1 Informal Logic

to recognize that ¬Q is not the same as the statement “all people do not have red hair,” which in symbols would be written (∀x)(¬P(x)). This last statement is much stronger than is needed to say that Q is false. The effect of the negation of Q is to change the quantifier, as well as to negate the statement being quantified.

1. ¬[(∀x in U)P(x)] ⇔ (∃x in U)(¬P(x)).

2. ¬[(∃x in U)P(x)] ⇔ (∀x in U)(¬P(x)).

¬Q ⇔ ¬[(∀w)(∃y)P(w,y)] ⇔ (∃w)¬[(∃y)P(w,y)] ⇔ (∃w)(∀y)(¬P(w,y)).

where b is something of U, and where the symbol “b” does not already have any other meaning in the given argument.

of inference will be used regularly in our mathematical proofs. See [Cop68, Chap-ter 10] for further discussion of these rules of inference.

An example of a simple logical argument involving quantifiers is the following.

Exercise 1.5.1. Suppose that the possible values of x are all people. Let Y(x) =“x has green hair,” let Z(x) = “x likes pickles” and let W(x) = “x has a pet frog.”Translate the following statements into words.

1.5 Quantifiers 43

Exercise 1.5.2. Suppose that the possible values of x and y are all cars. Let L(x,y) =“x is as fast as y,” let M(x,y) = “x is as expensive as y” and let N(x,y) = “x is as old

as y.” Translate the following statements into words.

(2) All cows are four years old.

(3) There is a brown cow with white spots.

(1) There is a fruit such that all fruit taste better than it.

(2) For every fruit, there is a fruit that is riper than it.

(3) Cats like eating fish and taking naps.

(4) I liked one of the books I read last summer. (5) No one likes ice cream and pickles together.

(3) The equation x2−2x > 0 holds for all real numbers x. (4) Every parent has to change diapers.

(5) Every flying saucer is aiming to conquer some galaxy.

(9) At least one person in New York City owns every book published in 1990.

Exercise 1.5.7. Negate the following statement: There exists an integer Q such that for all real numbers x > 0, there exists a positive integer k such that ln(Q − x) > 5 and that if x ≤ k then Q is cacophonous. (The last term used in this exercise is meaningless.)

gelatinous real number x? (The terms used in this exercise are meaningless.)

Exercise 1.5.10. Someone claims that the argument

(1), Existential Instantiation (3), Simplification
(2), Existential Instantiation (5), (4), Adjunction
(6), Existential Generalization.

(1) Every fish that is bony is not pleasant to eat. Every fish that is not bony is slimy. Therefore every fish that is pleasant to eat is slimy.

2

Strategies for Proofs

Be the above as it may, the importance of proofs should be put in the proper perspective. Intuition, experimentation and even play are no less important in today’s mathematical climate than rigor, because it is only by our intuition that we decide what new results to try to prove. The relation between intuition and formal rigor is not a trivial matter. Formal proofs and intuitive ideas essentially occupy different realms,

E.D. Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics, 4 7

Mathematics has moved over time in the direction of ever greater rigor, though why that has happened is a question we leave to historians of mathematics to explain. We can, nonetheless, articulate a number of reasons why mathematicians today use proofs. The main reason, of course, is to be sure that something is true. Contrary to popular misconception, mathematics is not a formal game in which we derive theorems from arbitrarily chosen axioms. Rather, we discuss various types of mathe-matical objects, some geometric (for example, circles), some algebraic (for example, polynomials), some analytic (for example, derivatives) and the like. To understand these objects fully, we need to use both intuition and rigor. Our intuition tells us what is important, what we think might be true, what to try next and so forth. Unfor-tunately, mathematical objects are often so complicated or abstract that our intuition at times fails, even for the most experienced mathematicians. We use rigorous proofs to verify that a given statement that appears intuitively true is indeed true.

Another use of mathematical proofs is to explain why things are true, though not every proof does that. Some proofs tell us that certain statements are true, but shed no intuitive light on their subjects. Other proofs might help explain the ideas that underpin the result being proved; such proofs are preferable, though any proof, even if non-intuitive, is better than no proof at all. A third reason for having proofs in mathematics is pedagogical. A student (or experienced mathematician for that matter) might feel that she understands a new concept, but it is often only when attempting to construct a proof using the concept that a more thorough understanding emerges. Finally, a mathematical proof is a way of communicating to another person an idea that one person believes intuitively, but the other does not.

niently broken down into the two-column (statement-justification) format. Second, the mathematical ideas of the proof, not its logical underpinnings, are the main is-sue on which we want to focus, and so we do not even mention the rules of logical inference used, but rather mention only the mathematical justification of each step. Second, mathematicians who are not logicians, which means most mathematicians, find long strings of logical symbols not only unpleasant to look at, but in most cases rather difficult to follow. See [EFT94, pp. 70–71] for a fully worked out example of putting a standard mathematical proof in group theory into a two-column format using formal logic. The mathematical result proved in that example is given in Ex-ercise 7.2.8; see Sections 7.2 and 7.3 for a brief introduction to groups. One look at the difference between the mathematicians’ version of the proof and the logicians’version, in terms of both length and complexity, should suffice to convince the reader why mathematicians do things as they do.

To some extent mathematicians relate to proofs the way the general public often reacts to art—they know it when they see it. But a proof is not like a work of modern art, where self-expression and creativity are key, and all rules are to be broken, but rather like classical art that followed formal rules. (This analogy is not meant as an endorsement of the public’s often negative reaction to serious modern art—classical art simply provides the analog we need here.) Also similarly to art, learning to recog-nize and construct rigorous mathematical proofs is accomplished not by discussing the philosophy of what constitutes a proof, but by learning the basic techniques, studying correct proofs, and, most importantly, doing lots of them. Just as art criti-cism is one thing and creating art is another, philosophizing about mathematics and doing mathematics are distinct activities (though of course it helps for the practi-tioner of each to know something about the other). For further discussion about the conceptual nature of proofs, see [Die92, Section 3.2] or [EC89, Chapter 5], and for more general discussion about mathematical activity see [Wil65] or [DHM95].

Theorem 2.1.1 (Pythagorean Theorem). Let △ABC be a right triangle, with sides of length a, b and c, where c is the length of the hypotenuse. Then a2+b2= c2.

When asked what the Pythagorean Theorem says, students often state “a2+b2= c2.” This expression alone is not the statement of the theorem—indeed, it is not a statement at all. Unless we know that a, b and c are the lengths of the sides of a right triangle, with c the length of the hypotenuse, we cannot conclude that a2+b2= c2. (The formula a2+ b2= c2is never true for the sides of a non-right triangle.) It is crucial to state theorems with all their hypotheses if we want to be able to prove them.

informally familiar with these numbers. See the Appendix for a brief list of some of the standard properties of the real numbers.

We conclude this section with our first example of a proof. You are probably familiar with the statement “the sum of even numbers is even.” This statement can be viewed in the form P → Q if we look at it properly, because it actually says “if n and m are even numbers, then n + m is an even number.” To construct a rigorous proof of our statement (as well as the corresponding result for odd numbers), we first need precise definitions of the terms involved.

We are now ready to state and prove our theorem. This result may seem rather trivial, but our point here is to see a properly done proof, not to learn an exciting new result about numbers.

Theorem 2.1.3. Let n and m be integers.

Because k and j are integers, so is k + j. Hence m+n is even.

(2) & (3). These two parts are proved similarly to Part (1), and the details are left to the reader. ⊓⊔

An important consideration when writing a proof is recognizing what needs to be proved and what doesn’t. There is no precise formula for such a determination, but the main factor is the context of the proof. In an advanced book on number theory, it would be unnecessary to prove the fact that the sum of two even integers is even; it would be safe to assume that the reader of such a book would either have seen the proof of this fact, or could prove it herself. For us, however, because we are just learning how to do such proofs, it is necessary to write out the proof of this fact in detail, even though we know from experience that the result is true. The reasons to prove facts that we already know are twofold: first, in order to gain practice writing proofs, we start with simple results, so that we can focus on the writing, and not on mathematical difficulties; second, there are cases where “facts” that seem obviously true turn out to be false, and the only way to be sure is to construct valid proofs.

Though mathematical proofs are logical arguments, observe that in the proof of Theorem 2.1.3 we did not use the logical symbols we discussed in Chapter 1. In general, it is not proper to use logical symbols in the writing of mathematical proofs. Logical symbols were used in Chapter 1 to help us become familiar with informal logic. When writing mathematical proofs, we make use of that informal logic, but we write using standard English (or whatever language is being used).

(4) ex+y= exey.

54 2 Strategies for Proofs

For example, each of the three parts of Theorem 2.1.3 is of the form P → Q. To prove theorems, we therefore need to know how to prove statements of the form P → Q. The simplest form of proof, which we treat in this section, is the most obvious one: assume that P is true, and produce a series of steps, each one following from the previous ones, which eventually lead to Q. This type of proof is called a direct proof. That this sort of proof deserves a name is because there are other approaches that can be taken, as we will see in Section 2.3. An example of a direct proof is the proof of Theorem 2.1.3.

(argumentation)

integer a divides the integer b.” For example, even though it is not sensible to write the fraction 7/0, it is perfectly reasonable to write the expression 7|0, because 7 does in fact divide 0, because 7 · 0 = 0. Because of this potential confusion, and also to avoid ambiguous expressions such as 1/2+3 (is that1 2+ 3 or 2+3?), we suggest writing all fractions asa brather than a/b.

We now have two simple results about divisibility. The proof of each theorem is preceded by scratch work, to show how one might go about formulating such a proof.

Compare the proof with the scratch work. The proof might not appear substan-tially better than the scratch work at first glance, and it might even seem a bit mys-terious to someone who had not done the scratch work. Nonetheless, the proof is better than the scratch work, though in such a simple case the advantage might not be readily apparent. Unlike the scratch work, the proof starts with the hypotheses and proceeds logically to the conclusion, using the definition of divisibility precisely as stated. Later on we will see examples where the scratch work and the proof are more strikingly different.

Theorem 2.2.3. Any integer divides zero.

In sum, there are two main steps to the process of producing a rigorous proof: formulating it and writing it. These two activities are quite distinct, though in some very simple and straightforward proofs you might formulate as you write. In most cases, you first formulate the proof (at least in outline form) prior to writing. For a difficult proof the relation between formulating and writing is essentially dialectical. You might formulate a tentative proof, try writing it up, discover some flaws, go back to the formulating stage and so on.

Exercise 2.2.1. Outline the strategy for a direct proof of each of the following state-ments (do not prove them, because the terms are meaningless).

(1) Prove that 1|n.

(2) Prove that n|n.

(1) Prove that n+m is divisible by 3.
(2) Prove that nm is divisible by 3.

Exercise 2.2.6. Let a, b, c, m and n be integers. Prove that if a|b and a|c, then a|(bm+cn).

There is no foolproof method for knowing ahead of time whether a proof on which you are working should be a direct proof or a proof by one of these other methods. Experience often allows for an educated guess as to which strategy to try first. In any case, if one strategy does not appear to bear fruit, then another strategy should be attempted. It is only when the proof is completed that we know whether a given choice of strategy works.

Both strategies discussed in this section rely on ideas from our discussion of equivalence of statements in Section 1.3. For our first method, recall that the contra-positive of P → Q, the statement ¬Q → ¬P, is equivalent to P → Q. Hence, in order

Proof. Suppose that Q is false.

...

Theorem 2.3.1. Let n be an integer. If n2is odd, then n is odd.

Scratch Work. If we wanted to use a direct proof, we would have to start with the

start such a proof by observing that if n is even, then there is some integer k such that

n = 2k, and we then compute n2in terms of k, leading to the desired result. ///

it is often helpful to the reader to have the method of proof stated explicitly.

looks similar to proof by contrapositive but is actually distinct from it, is proof by Another method of proof for theorems with statements of the form P → Q, which

by contradiction.

Recall from Section 1.3 that ¬(P → Q) is equivalent to P∧¬Q. Suppose that we could prove that P∧¬Q is false. It would follow that ¬(P → Q) is false, and hence that ¬(¬(P → Q)) is true. Then, using Double Negation (Fact 1.3.2 (1)), we could conclude that P → Q is true.

Proof. We prove the result by contradiction. Suppose that P is true and that Q is false.

...

Proof. We prove the result by contradiction. Suppose that a, b and c are non-negative consecutive integers other than 3, 4 and 5, and that a2+ b2= c2. Because a, b and c are not 3, 4 and 5, we know that a ̸= 3, and because the three numbers are con-secutive, we know that b = a + 1 and c = a + 2. From a2+ b2= c2we deduce that a2+(a+1)2= (a+2)2. After expanding and rearranging we obtain a2−2a−3 = 0. This equation factors as (a − 3)(a + 1) = 0. Hence a = 3 or a = −1. We have al- ⊓⊔ready remarked that a ̸= 3, and we know a is non-negative. Therefore we have a contradiction, and the theorem is proved.

Our next two theorems are both famous results that have well-known proofs by contradiction. These clever proofs are much more difficult than what we have seen so far, and are more than would be expected of a student to figure out on her own at this point.

62 2 Strategies for Proofs

The first few prime numbers are 2,3,5,7,11,.... The study of prime numbers is quite old and very extensive; see any book on elementary number theory, for example [Ros05], for details.

Theorem 2.3.7. There are infinitely many prime numbers.

Preliminary Analysis. We have not yet seen a rigorous treatment of what it means for there to be infinitely many of something, and so for now we need to use this concept in an intuitive fashion. A thorough discussion of finite vs. infinite is found in Chapter 6. The essential idea discussed in that chapter is that if a collection of objects can be listed in the form a1,a2,...,an for some positive integer n, then the collection of objects is finite; if the collection of objects cannot be described by any such list, then it is infinite. In Chapter 6 we will see a rigorous formulation of this idea in terms of sets and functions, but this intuitive explanation of finite vs. infinite completely captures the rigorous definition.

is a prime number that is not in the collection P1,P2,...,Pn, and we will therefore know that the collection P1,P2,...,Pn does not contain all prime numbers, which is a contradiction. It will then follow that if n is a positive integer, and P1,P2,...,Pn are prime numbers, then P1,P2,...,Pn does not include all prime numbers, and we will conclude that there are infinitely many prime numbers.

To show that Q is a prime number, we use proof by contradiction. Suppose that Q is not a prime number. Therefore Q is a composite number. By Theorem 6.3.10 we deduce that Q has a factor that is a prime number. (Though this theorem comes later in the text, because it needs some tools we have not yet developed, it does not use the result we are now proving, and so it is safe to use.) The only prime numbers are P1,P2,...,Pn, and therefore one of these numbers must be a factor of Q. Suppose that Pk is a factor of Q, for some integer k such that 1 ≤ k ≤ n. Therefore there is some integer R such that PkR = Q. Hence

We conclude this section with the observation that proof by contradiction implic-itly uses Double Negation, which ultimately relies upon the Law of the Excluded Middle, which says that any statement is either true or false. (See Section 1.2 for more discussion of this issue.) Any mathematician who does not believe in the Law of the Excluded Middle would therefore object to proof by contradiction. There are such mathematicians, though the majority of mathematicians, including the author of this book, are quite comfortable with the Law of the Excluded Middle, and hence with proof by contradiction.

Exercise 2.3.5. Let a, b and c be integers. Suppose that there is an integer d such that d|a and d|b, but that d does not divide c. Prove that the equation ax+by = c has no solution such that x and y are integers.

Exercise 2.3.6. Let c be an integer. Suppose that c ≥ 2, and that c is not a prime number. Prove that there is an integer b such that b ≥ 2, that b|c and that b ≤ √c. Exercise 2.3.7. Let q be an integer. Suppose that q ≥ 2, and that for any integers a and b, if q|ab then q|a or q|b. Prove that√q is irrational.

and so on). Formally, we use proof by cases when the premise P can be written in the form A ∨B. We then use Exercise 1.3.2 (6) to see that (A ∨ B) → Q is equivalent to (A → Q)∧(B → Q). Hence, in order to prove that a statement of the form (A∨B) →Q is true, it is sufficient to prove that each of the statements A → Q and B → Q is true. The use of this strategy often occurs when proving a statement involving a quantifier of the form “for all x in U,” and where no single proof can be found for all such x, but where U can be divided up into two or more parts, and where a proof can be found for each part.

For the following simple example of proof by cases, recall the definition of even and odd integers in Section 2.1.

n2+n = (2k)2+2k = 4k2+2k = 2(2k2+k).

Because k is an integer, so is 2k2+k. Therefore n2+n is even.

It is not really necessary to define A and B explicitly as we did in the scratch work for Theorem 2.4.1, and we will not do so in the future, but it was worthwhile doing it once, just to see how the equivalence of statements is being used.

In the proof of Theorem 2.4.1 we had two cases, which together covered all pos-sibilities, and which were exclusive of each other. It is certainly possible to have more than two cases, and it is also possible to have non-exclusive cases; all that is needed is that all the cases combined cover all possibilities. The proof of Theorem 2.4.4 below has two non-exclusive cases.

tional.

Preliminary Analysis. The statement of this theorem has the form P → (A∨B). We will prove (P∧¬A) → B, which we do by assuming that xy is irrational and that x is rational, and deducing that y is irrational. ///

Having discussed the appearance of ∨ in the statements of theorems, we could also consider the appearance of ∧, though these occurrences are more straightfor-ward. As expected, a theorem with statement of the form (A∧B) → Q is proved by assuming A and B, and using both of these statements to derive Q. To prove a theo-

rem with statement of the form P → (A ∧ B), we can use Exercise 1.3.2 (4), which states that P → (A ∧ B) is equivalent to (P → A) ∧ (P → B). Hence, to prove a the-orem with statement of the form P → (A ∧ B), we simply prove each of P → A and P → B, again as expected. Not only are there a variety of ways to structure proofs, but there are also variants

divisibility of integers in Section 2.2.

Theorem 2.4.3. Let a and b be non-zero integers. Then a|b and b|a if and only if a = b or a = −b.

⇐. Suppose that a = b or a = −b. First, suppose that a = b. Then a · 1 = b, so a|b, and b·1 = a, so b|a. Similarly, suppose that a = −b. Then a·(−1) = b, so a|b, and b·(−1) = a, so b|a. ⊓⊔

2.4 Cases, and If and Only If 67

the assumption that mn is odd, which would mean that mn = 2p+1 for some integer p, but it is not clear how to go from there to the desired conclusion. It is easier to make assumptions about m and n and proceed from there, so we will prove this part of the theorem by contrapositive, in which case we assume that m and n are not both odd, and deduce that mn is not odd. When we assume that m and n are not both odd, we will have two (overlapping) cases to consider, namely, when m is even or when n is even. Alternatively, it would be possible to make use of three non-overlapping cases, which are when m is even and n is odd, when m is odd and n is even, and when m and n are both even; however, the proof is no simpler as a result of the non-overlapping cases, and in fact the proof would be longer with these three cases rather than the two overlapping ones as originally proposed, and so we will stick with the latter. ///

Proof.

at least one of them is even. Suppose first that m is even. Then there is an integer p such that m = 2p. Hence mn = (2p)n = 2(pn). Because p and n are integers, so is pn. Therefore mn is even. Next assume that n is even. The proof in this case is similar to the previous case, and we omit the details. ⊓⊔

A slightly more built-up version of an if and only if theorem is a theorem that states that three or more statements are all mutually equivalent. Such theorems often include the phrase “the following are equivalent,” sometimes abbreviated “TFAE.”The following theorem, which involves 2×2 matrices, is an example of this type of result. For the reader who is not familiar with matrices, we summarize the relevant notation. A 2 × 2 matrix is a square array of numbers of the form M = some real numbers a, b, c and d. The determinant of such a matrix is defined by� a b�, for

Exercise 2.4.1. Outline the strategy for a proof of each of the following statements (do not prove them, because the terms are meaningless).

(1) If an integer is combustible then it is even or prime.

Exercise 2.4.2. Let a, b and c be integers. Suppose that c ̸= 0. Prove that a|b if and only if ac|bc.

Exercise 2.4.3. [Used in Exercise 4.4.8, Exercise 6.7.9 and Section 8.8.] Let a and b be integers. The numbers a and b are relatively prime if the following condition holds: if n is an integer such that n|a and n|b, then n = ±1. See Section 8.2 for further discussion and references.

d. a−b and b are relatively prime.

Exercise 2.4.4. Let n be an integer. Prove that one of the two numbers n and n+1 is even, and the other is odd. (You may use the fact that every integer is even or odd.)

Exercise 2.4.6. Are there any integers p such that p > 1, and such that all three numbers p, p +2 and p +4 are prime numbers? If there are such triples, prove that you have all of them; if there are no such triples, prove why not. Use the discussion at the start of Exercise 2.4.5.

Exercise 2.4.7. Let n be an integer. Using only the fact that every integer is even or odd, and without using Corollary 5.2.5, prove that precisely one of the following holds: either n = 4k for some integer k, or n = 4k+1 for some integer k, or n = 4k+2 for some integer k, or n = 4k +3 for some integer k.

y, if x ≥ y if x ≤ y, and x ⌣ y =�y,

x, if x ≥ y if x ≤ y.

2.5 Quantifiers in Theorems

A close look at the theorems we have already seen, and those we will be seeing, shows that quantifiers (as discussed in Section 1.5) appear in the statements of many theorems—implicitly if not explicitly. The presence of quantifiers, and especially multiple quantifiers, in the statements of theorems is a major source of error in the construction of valid proofs by beginners. So, extra care should be taken with the material in this section; mastering it now will save much difficulty later on. Before proceeding, it is worth reviewing the material in Section 1.5. Though we will not usually invoke them by name, to avoid distraction, the rules of inference for quanti-fiers discussed in Section 1.5 are at the heart of much of what we do with quantifiers in theorems.

Proof. Let x0 be in U.

...

rect proof. For example, the proof of such a statement using proof by contradiction Statements of the form (∀x in U)P(x) can be proved by strategies other than di-

typically has the following form.

2.5 Quantifiers in Theorems 73

Because we want a, b, c and d to be integers, we need to find integer values of b and c such that 33−4bc is the square of an odd integer. Trial and error shows that b = 2 and c = 3 yield either a = 5 and d = 2, or a = 2 and d = 5. (There are other possible solutions, for example b = −2 and c = 2, but we do not need them). ///

Let us examine two simple examples of backwards proofs. First, suppose that we are asked to solve the equation 7x + 6 = 21 + 4x. A typical solution submitted by a high school student might look like

7x+6 = 21+4x

logically irrelevant (though, of course, of great pedagogical interest). A logically correct “forwards” write-up of the solution to 7x+6 = 21+4x would be as follows.

“Let x = 5. Plugging x = 5 into the left-hand side of the equation yields 7x + 6 = 7 · 5 + 6 = 41, and plugging it into the right-hand side of the equation yields 21 + 4x = 21 + 4 · 5 = 41. Therefore x = 5 is a solution. Because the equation is linear, it has at most one solution. Hence x = 5 is the only solution.”

The following theorem concerns inverse matrices. Given a 2 × 2 matrix A, an inverse matrix for A is a 2 × 2 matrix B such that AB = I = BA. Does every 2 × 2 matrix have an inverse matrix? The answer is no. For example, the matrix no inverse matrix, as the reader may verify (by supposing it has an inverse matrix, and seeing what happens). The following theorem gives a very useful criterion for�3 0�has

the existence of inverse matrices. In fact, the criterion is both necessary and sufficient for the existence of inverse matrices, and its analog holds for square matrices of any size, but we will not prove these stronger results.

which yields
� ax+bz ay+bw cx+dz cy+dw�=� 1 0 0 1�.

This matrix equation yields the four equations

cy+dw = 1,

1) > 0) is true, and hence we need to find a real number x0, such that if we pick an arbitrary real number y0, then (3 − x0)((y0)2+ 1) > 0 will hold. Again we do our scratch work backwards. Observe that (y0)2+1 > 0 for all real numbers y0, and that 3 − x0 > 0 for all x0 < 3. We need to pick a single value of x0 that works, and we randomly pick x0 = 2. ///

Proof. Let x0 = 2. Let y0 be a real number. Observe that (y0)2+1 > 0. Then

(1) If a 5×5 matrix has positive determinant then it is bouncy. (2) There is a crusty integer that is greater than 7.

(3) For each integer k, there is an opulent integer w such that k|w.

(the number x does not have to be given explicitly in decimal expansion).

Exercise 2.5.3. Prove or give a counterexample to each of the following statements.

t, the inequality s ≥ t holds.

Exercise 2.5.4. Prove or give a counterexample to each of the following statements.

(1) For each real number x, there exists a real number y such that ex−y > 0. (2) There exists a real number y such that for all real numbers x, the inequality

ex−y > 0 holds.

1 1

2b2+b< ab2 .

Exercise 2.5.9. Prove or give a counterexample to the following statement. For each� r 5�= p.

integer x, and for each integer y, there exists an integer z such that z2+2xz−y2= 0.

d. Prove that this least P-number is unique.

80 2 Strategies for Proofs

Exercise 2.5.12. Look through mathematics textbooks that you have previously used (in either high school or college), and find an example of a backwards proof.

2.6 Writing Mathematics

2.6 Writing Mathematics 81

2. Write Precisely and Carefully

3. Prove What Is Appropriate

A good proof should have just the right amount of detail—neither too little nor too much. The question of what needs to be included in a proof, and what can be taken as known by the reader, is often a matter of judgment. A good guideline is to assume that the reader is at the exact same level of knowledge as you are, but does not know the proof you are writing. It is certainly safe to assume that the reader knows elementary mathematics at the high school level (for example, the quadratic formula). In general, do not assume that the reader knows anything beyond what has been covered in your mathematics courses. When in doubt—prove.

The words “trivial” and “obvious” mean different things when used by math-ematicians. Something is trivial if, after some amount of thought, a logically very simple proof is found. Something is obvious if, relative to a given amount of math-ematical knowledge, a proof can be thought of very quickly by anyone at the given level. According to an old joke, a professor tells students during a lecture that a certain theorem is trivial; when challenged by one student, the professor thinks and thinks, steps out of the room to think some more, comes back an hour later, and an-nounces to the class that the student was right, and that the result really is trivial. The joke hinges on the fact that something can be trivial without being obvious.

5. Use Full Sentences and Correct Grammar

2.6 Writing Mathematics 83

The first version is genuinely awful, though for reasons the author does not un-derstand, some students seem to be given the impression in high school that this sort of writing is acceptable.

Mathematicians do not write papers and books this way; please do not write this way yourself!

84 2 Strategies for Proofs

Another common type of error involving “=” signs involves lengthier calcula-tions. Suppose that a student is asked to show that

Another incorrect way of writing this same calculation, and also one that the author has seen regularly, is

(x2+2x)(x2−4)(x2−2x)
x(x+2)(x−2)(x+2)x(x−2)
x2(x+2)2(x−2)2
[x(x−2)(x+2)]2
(x3−4x)2.

(x2+2x)(x2−4)(x2−2x) = x(x+2)(x−2)(x+2)x(x−2) = x2(x+2)2(x−2)2
= [x(x−2)(x+2)]2
= (x3−4x)2,

and

The need to define variables can get a bit tricky when quantifiers are involved. It is important to understand the scope of any quantifier being used. Suppose that somewhere in a proof you have the statement “for each positive integer n, there is an integer p such that ....” The variables n and p are bound variables, and are defined only inside that statement. They cannot be used subsequently, unless they are redefined. If you subsequently want to use a positive integer, you cannot assume that the symbol n has already been defined as such. You would need to define it for the current use, by saying, as usual, something such as “let n be a positive integer.” Finally, it is tempting in the course of a complicated proof to make up new words and symbols, and to use all sorts of exotic alphabets. For the sake of readability, avoid

86 2 Strategies for Proofs

Writing mathematics involves both formal and informal writing. Formal writing is used for definitions, statements of theorems, proofs and examples; informal writing is for motivation, intuitive explanations, descriptions of the mathematical literature, etc. When writing up the solution to an exercise for a mathematics course, the writ-ing should be a formal proof. A lengthier exposition (such as a thesis or a book) will make use of both kinds of writing—formal writing to make sure that mathemat-ical rigor is maintained, and informal writing to make the text understandable and interesting. Do not confuse the two types of writing, or each will fail to do what it is supposed to do. Intuitive aids such as drawings, graphs, Venn diagrams and the like are extremely helpful when writing up a proof, though such aids should be in addition to the proof, not instead of it.

10. Miscellaneous Writing Tips

Exercise 2.6.1. State what is wrong with each of the following write-ups; some have

x2+6x−16 = 0

(x−2)(x+8) = 0

(7+2y)(y2+5y−6)

7y2+35y−42+2y3+10y2−12y

(7) Let x be a real number. Then x2≥ 0 for all real numbers x, ... . (8) It is known that√a < a for all a > 1. Hence√a + 3 < a + 3. Hence (√a +

3)2< (a+3)2.

No one shall expel us from the paradise that Cantor created for us.
– David Hilbert (1862–1943)

3.1 Introduction

92 3 Sets

start with some undefined terms. Even analytic geometry (invented long after Eu-clid), which appears to do geometry without the use of axioms about geometry, ul-timately relies upon some axioms and undefined terms regarding the real numbers. Axioms and undefined terms are unavoidable for rigorous mathematics. The modern approach in mathematics accepts the existence of undefined terms, as long as they are used properly. Ultimately, undefined objects do not bother us because such ob-jects do not so much exist in themselves as they are determined by the axiomatic properties hypothesized for them, and it is these properties that we use in proofs.

3.2 Sets—Basic Definitions

The basic undefined term we will use is that of a set, which we take to be any col-lection of objects, not necessarily mathematical ones. For example, we can take the set of all people born in San Francisco in 1963. The objects contained in the set are called the elements or members of the set. If A is a set and a is an element of A, we write
a ∈ A.

{...,−2,−1,0,1,2,...},

denoted Z; the set of rational numbers, denoted Q, which is the set of fractions; the set of real numbers, denoted R, which is the set of all the numbers that are informally thought of as forming the number line.

which is read “the set of all n in Z such that n is a perfect square.” Some books use a colon “:” instead of a vertical line in the above set notation, though the meaning is exactly the same, namely, “such that.” If we want to write the above set even more carefully we could write

S = {n ∈ Z | n = k2for some k ∈ Z}.

The above method of defining sets is quite straightforward, but there is one point about this method that needs to be stressed. Because the letters x and r in Equa-tion 3.2.2 are dummy variables, we cannot use them outside the “{ | }” notation without redefinition. Hence, if we want to refer to some element of the set defined in Equation 3.2.1 and Equation 3.2.2, for example pointing out that such elements must be non-negative, it would not be correct to say simply “observe that x ≥ 0.” By contrast, it would be correct to say “observe that x ≥ 0 for all x ∈ S.” However, this latter formulation has the defect that if we want to continue to discuss elements in S, we would have to define x once again, because the x in “x ≥ 0 for all x ∈ S” is bound by the quantifier. A better approach would be to write “let x ∈ S; then x ≥ 0.” Now that x has been defined as an element of S, not bound by a quantifier, we can use it as often as we wish without redefinition.

An example of the above method of defining sets is seen in the following widely used definition.

there is no interval of the form [a,∞], because “∞” is not a real number, and therefore Observe that there are no intervals that are “closed” at ∞ or −∞, for example

it cannot be included in an interval contained in the real numbers. The symbol “∞”

the elements of A are in B, just not all. See Figure 3.2.1 for a schematic drawing of Observe that if A and B are sets and if A ̸⊂ B, then it is still possible that some of

A ⊆ B and A ̸⊆ B.

There is a standard strategy for proving a statement of the form “A ⊆ B,” which is to take an arbitrary element a ∈ A, and then to use the definitions of A and B to deduce that a ∈ B. Such a proof typically has the following form.

prove a statement of the form “A ̸⊆ B,” by contrast, we simply need to find some a ∈ A such that a /∈ B, a fact that seems intuitively clear, and that can be seen formally as follows. The statement A ⊆ B can be written as (∀x)([x ∈ A] → [x ∈ B]). Then A ̸⊆ B

96 3 Sets

lemma, our first proof about sets, makes repeated use of the strategy mentioned above

for showing that one set is a subset of another set.

Proof.

(1). To show that A ⊆ A, we start by choosing an arbitrary element a ∈ A, where we think of this “A” as the one on the left-hand side of the expression “A ⊆ A.” It then follows that a ∈ A, where we now think of this “A” as the one on the right-hand side of the expression “A ⊆ A.” Hence A ⊆ A, using the definition of subsets.

proofs as described in Section 2.3, because it does not appear as if we are viewing

the statement being proved as having the form P → Q. In fact, there are two ways of viewing the statement being proved as having this form. For the direct proof given

3.2 Sets—Basic Definitions 97

Definition 3.2.5. Let A and B be sets. The set A equals the set B, denoted A = B, if

(1) Let A and B be the sets in Example 3.2.3 (1). Then B is a proper subset of A.

X = Y. (2) Let X = {a,b,c}, and let Y = {c,b,a}. Then clearly X ⊆ Y and Y ⊆ X, so

We will show that P = Q, putting in more detail than is really necessary for a prob-

lem at this level of difficulty, but we want to make the proof strategy as explicit as

proved is trivial, but the strategy used is not. Virtually every time we show that two

sets A and B are equal, we go back to the definition of equality of sets. The strategy

...

Then a ∈ B. Therefore A ⊆ B.
Next, Let b ∈ B.
...

We will see a number of examples of this strategy, starting with the proof of Theorem 3.3.3 (4) in the next section.

The following lemma gives the most basic properties of equality of sets. The three parts of the lemma correspond to three properties of relations we will discuss in Sections 5.1 and 5.3.

Proof. All three parts of this lemma follow straightforwardly from the definition of equality of sets together with Lemma 3.2.4. Details are left to the reader. ⊓⊔ In some situations we will find it useful to look at not just one subset of a given set, but at all subsets of the set. In particular, we can form a new set, the elements of which are the subsets of the given set.

(1) 3 ∈ (3,5].

(2) 10 /∈ (−∞,π2].

(7) {−1,0,1} ⊆ [−1,1).

(8) [5,7] ⊆ (4,∞).

(3) {x ∈ R | there exist a,b ∈ Z such that b ̸= 0 and x =a b}.

Exercise 3.2.4. Let P be the set of all people, let M be the set of all men and let F be the set of all women. Describe each of the following sets with words.

(6) {x ∈ P | there exist n ∈ M such that x is the child of n, and x is older than n}.

Exercise 3.2.5. Describe the following sets in the style of Equation 3.2.1.

Exercise 3.2.6. We assume for this exercise that functions are intuitively familiar to the reader (a formal definition will be given in Chapter 4). Let F denote the set of all functions from the real numbers to the real numbers; let D denote the set of all differentiable functions from the real numbers to the real numbers; let P denote the set of all polynomial functions from the real numbers to the real numbers; let C denote the set of all continuous functions from the real numbers to the real numbers; let E denote the set of all exponential functions from the real numbers to the real numbers. Which of these sets are subsets of which?

Exercise 3.2.7. Among the following sets, which is a subset of which?

F is the set of all fathers;

U is the set of all uncles;

C = {n ∈ Z | there exists k ∈ Z such that n = k4}; E = {n ∈ Z | there exists k ∈ Z such that n = 2k}; P = {n ∈ Z | n is a prime number};
N = {n ∈ Z | there exists k ∈ Z such that n = k8}; S = {n ∈ Z | there exists k ∈ Z such that n = 6k}; D = {n ∈ Z | there exists k ∈ Z such that n = k −5}; B = {n ∈ Z | n is non-negative}.

Exercise 3.2.9. Find sets A and B such that A ∈ B and A ⊆ B. (It might appear as if we are contradicting what was discussed after Example 3.2.3; the solution, however,

Exercise 3.2.12. Let A and B be any two sets. Is it true that one of A ⊆ B or A = B or A ⊇ B must be true? Give a proof or a counterexample.

Exercise 3.2.13. Let A = {x,y,z,w}. List all the elements in P(A)?

(1) {/0} ⊆ G for all sets G.

(2) /0 ⊆ G for all sets G.

3.3 Set Operations

There are a number of ways to make new sets out of old, somewhat analogous to combining numbers via addition and multiplication. A closer analogy is the way in which we combined statements in Section 1.2. The two most basic set operations, which we now describe, correspond to the logical operations “or” and “and.”

Venn diagrams can be useful for convincing ourselves of the intuitive truth of var-ious propositions concerning sets. For instance, we will prove in Theorem 3.3.3 (5) that A∩(B∪C) = (A∩B)∪(A∩C) for any three sets A, B and C. To gain an intuitive feeling for this result, we can find the region in a Venn diagram for each of the two sides of the equation, and then observe that the two regions are the same, namely, the shaded region in Figure 3.3.2. Although Venn diagrams seem much easier to use

at a time, and this severely limits their use.

Fig. 3.3.2.

Theorem 3.3.3. Let A, B and C be sets.

1. A ∩ B ⊆ A and A ∩ B ⊆ B. If X is a set such that X ⊆ A and X ⊆ B, then X ⊆ A∩B.

(Associative Laws).

(Dis-

9. If A ⊆ B, then A∪C ⊆ B∪C and A∩C ⊆ B∩C.

Proof. We will prove Parts (4) and (5), leaving the rest to the reader in Exercise 3.3.6.

3.3 Set Operations 103

We deduce that (A∪B)∪C = A∪(B∪C).

over each other, which is quite different from addition and multiplication of numbers,

where multiplication distributes over addition, but not vice versa.

let P be the set of prime numbers. Then E and O are disjoint, whereas E and P are

not disjoint (because E ∩P = {2}). ♦

Some books use the notation A \ B instead of A − B. The set A − B is the set containing everything that is in A but is not in B. The set A−B is defined for any two sets A and B; it is not necessary to have B ⊆ A. See Figure 3.3.3 for a Venn diagram of the A−B.

A−B = {y,z, p}. ♦

The following theorem gives some standard properties of set difference.

Definition 3.3.9. Let A and B be sets. The product (also called the Cartesian prod-uct) of A and B, denoted A×B, is the set

3.3 Set Operations 105

(2) Roll a pair of dice. The possible outcomes are

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
(2,1) (2,2) (2,3) (2,4) (2,5) (2,6)
(3,1) (3,2) (3,3) (3,4) (3,5) (3,6)
(4,1) (4,2) (4,3) (4,4) (4,5) (4,6)
(5,1) (5,2) (5,3) (5,4) (5,5) (5,6)
(6,1) (6,2) (6,3) (6,4) (6,5) (6,6).

106 3 Sets

4. A× /0 = /0 and /0×A = /0.

(4) F ∩(D∪E).

(5) (F ∩D)∪E.

Exercise 3.3.4. Let

(2) G∩I. (5) I −H.

(3) G∩H. (6) J ∩(G−H).

Exercise 3.3.8. [Used in Theorem 3.3.12.] Prove Theorem 3.3.12 (1) (2) (4) (5).

Exercise 3.3.9. [Used in Theorem 7.6.7.] Let A and B be sets. Prove that (A∪B)−A = B−(A∩B)

Exercise 3.3.13. [Used in Exercise 6.5.15.] For real numbers a, b and c, we know that

a−(b−c) = (a−b)+c. Let A, B and C be sets.

A △ B, is the set A △ B = (A−B)∪(B−A). Let X, Y and Z be sets. Prove the following statements.

(1) X △ /0 = X.

Exercise 3.3.16. Prove or find a counterexample to the following statement. Let A, B and C be sets. Then (A∪C)−B = (A−B)∪(C −B).

Exercise 3.3.17. Let A, B and C be sets. Prove that A ⊆C if and only if A∪(B∩C) = (A∪B)∩C.

Exercise 3.3.19. Let A, B and C be sets. Prove that A×(B−C) = (A×B)−(A×C). Exercise 3.3.20. Let A and B be sets. Suppose that B ⊆ A. Prove that A×A−B×B = [(A−B)×A]∪[A×(A−B)].

Exercise 3.3.21. Let A and B be sets. Suppose that A ̸= B. Suppose that E is a set such that A×E = B×E. Prove that E = /0.

For two sets A1 and A2, the union A1 ∪ A2 is the set of all elements x such that x ∈ A1 or x ∈ A2. We cannot directly generalize the notion of “or” directly to an infinite collection of sets, because “or” is also defined for only two things at a time, but let us look at A1 ∪ A2 slightly differently. Recall that for mathematics, the word“or” always means the inclusive or, that is, one or the other or both. Hence, instead of thinking of A1 ∪A2 as the set of all elements x such that x ∈ A1 or x ∈ A2, we can In other words, we have replaced the use of “or” in the definition of the union of two just as well think of it as the set of all elements x such that x ∈ Ai for some i ∈ {1,2}. sets with an existential quantifier. The advantage of this approach is that whereas “or”cannot be generalized to more than two things at a time, the existential quantifier can be used on sets of arbitrary size. Hence, if we have an infinite collection of sets A1,A2,A3,..., we can define the union of these sets as the set of all elements x such that x ∈ Ai for some i ∈ N. Using notation that is analogous to the notation for series of numbers, we then write

∞

a universal quantifier. If we have an infinite collection of sets A1,A2,A3,..., we can

define the intersection of these sets as the set of all elements x such that x ∈ Ai for

On the one hand, families of sets are just sets, and hence everything that we have previously said about sets still holds for families of sets. For example, given two families of sets, we could ask whether one is a subset of the other. On the other hand, because all the elements of a family of sets are themselves sets, then we can do something special with families of sets, which is to take the union and intersection of all the elements of the family of sets, which we define as follows.

Definition 3.4.3. Let A be a family of sets. The union of the sets in A, denoted�X∈AX, is defined as follows. If A ̸= /0, then

�Ai = {x | x ∈ Ai for some i ∈ I} and �Ai = {x | x ∈ Ai for all i ∈ I}

to denote the union and intersection of the sets in A, respectively. △

Example 3.4.4.

and�

♦

tersections of arbitrary families of sets, generalizing various properties we saw in

(usually the indexed notation), leaving it to the reader to convert it to the other style

as needed.

X∈A(B−X)

X∈A(B−X)
(De Morgan’s Law).

i∈I(B−Ai)
(De Morgan’s Law).

(De Morgan’s Law).
i∈IAi⊆ B.
i∈IAi.

i∈IAiby Part (2) of this theorem. It follows that y ∈ B ∩ (�i∈I(B∩Ai). Then y ∈ B∩A jfor some j ∈ I. Hence y ∈ B and y ∈ A j.

i∈IAi). Then x ∈ B and x ∈ �

sets indexed by I. Suppose that Ai ⊆ Bi for all i ∈ I.

Exercise 3.4.6. Let A be a non-empty family of sets and let B be a set. (1) Prove that�(2) Prove that�i∈IAi⊆ �i∈IAi⊆ �i∈IBi.

i∈I(B×Ai).

finite). A subset X ⊆ R is called co-W if R−X has property W . Let A be a non-empty family of sets. Suppose that X is a co-W subset of R for all

(3) A subset of R has property W if and only if it has precisely 7 elements.

(4) A subset of R has property W if and only if it contains only integers.

that it is used as the basis for modern mathematics. Unfortunately, however, it does

not work quite as nicely as we might have made it appear in the previous sections of

Suppose first that T /∈ T. Then T ∈ T. Now suppose that T ∈ T. Then T /∈ T. There is something wrong here. The problem is that we are trying to use a set of all sets, and

more generally the problem is that we have to be more careful how we quantify over

The ZF axioms are properly formulated in the context of symbolic logic, in which case the axioms are written out in logical notation. Because our purpose here is just to gain an informal familiarity with the ZF axioms, and because it would take us too far afield to develop the needed logic, we will write the axioms informally (though we will write the first one in logical symbols just to show that it can be done).

We need two additional comments before listing the axioms. First, whereas in-formally we tend to distinguish between sets and elements, for example we think of A = {1,2} as a set and each of 1 and 2 as elements, in the ZF axioms we make no such distinction. Everything in the ZF axioms is a set. It might seem strange to think of the numbers 1 and 2 as sets, but from the perspective of the ZF axioms the bit more about this idea shortly.) symbols “1” and “2” denote the sets {/0} and {/0,{/0}}, respectively. (We will say a Once we assume that everything in the ZF axioms is a set, then the relation of elementhood, which is denoted by the symbol ∈, is a relation between sets. That is, given two sets x and y, it might or might not be the case that x ∈ y. However, even if x ∈ y, we still think of both x and y as sets, regardless of whether or not one is an element of the other. Of course, if everything is a set, and we do not distinguish between what is a set and what is an element, we have to worry about potentially is, because x is defined in terms of itself. Fortunately, the ZF axioms are designed problematic constructions such as x = {x}, which would not specify what the set x to prevent such problems; this particular problem is disallowed by the Axiom of Regularity.

Axiom of Extensionality Let x and y be sets. If x and y have the same elements, then x = y.

This axiom is simply another way of stating the definition of the equality of sets that we saw in Definition 3.2.5. This axiom can be written in logical notation as

Axiom of Pairing Let x and y be sets. There is a set z such that w ∈ z if and only if w = x or w = y.

The set z described in the axiom is unique by the Axiom of Extensionality, and it is denoted {x,y}. In this axiom it is not required that x ̸= y, and we abbreviate {x,x} by {x}.

Axiom of Regularity Let x be a set. Suppose that x ̸= /0. Then there is some y ∈ x such that x∩y = /0.

118 3 Sets

�Ai = {x | x ∈ Ai for some i ∈ I} and �Ai = {x | x ∈ Ai for all i ∈ I}.

In fact, Definition 3.4.3 is not valid as stated if we adhere to the Axiom of Se-lection, because we are not specifying which set the element x belongs to. It would be tempting to write something such as “let S be the set of all sets, and let�at the start of this section that the set of all sets is not a concept we can use. The i∈IAi= {x ∈ S | x ∈ Aifor some i ∈ I}, but that would not be valid, because we saw

Axiom of Infinity There is a set z such that /0 ∈ z, and if x ∈ z then x∪{x} ∈ z.

We can make use of /0 and ∪ in the Axiom of Infinity because of the Axiom of Empty Set and the Axiom of Union, and we can make use of {x} because of the Axiom of Power Set and the Axiom of Selection, though we omit the details of the latter. The set z in this axiom, which is not necessarily unique, can be thought of informally as a set that contains the sets

The ZF axioms can be used not only to prove many useful facts about sets, but also to construct many familiar mathematical objects, for example the set of natural numbers. The basic idea of this construction is found in the list of sets in Equa-tion 3.5.1. These sets should remind the reader of the numbers 0,0+1,0+1+1,0+ 1 + 1 + 1,..., which intuitively are the non-negative integers; the natural numbers are then obtained by removing 0 from this set. The Axiom of Infinity guarantees the existence of at least one set w that contains these “numbers,” though the set w is not necessarily unique. We then let z be the intersection of all subsets of w that contain these “numbers,” and it can be seen that z is then the minimal such set. With some work, the set z is seen to contain precisely the sets listed in Equation 3.5.1, and is seen to behave just as one would expect the set of natural numbers together with 0 to behave; the choice of w turns out not to matter. The details of this construction may be found in [End77, Chapter 4].

Once the natural numbers have been defined, it is possible to construct the in-tegers, the rational numbers and the real numbers from the natural numbers. See [Blo11, Chapter 1] for the construction of these number systems. Moreover, many branches of mathematics such as real analysis (the rigorous study of calculus) and Euclidean geometry are based upon the properties of the real numbers. Hence, if we

Similarly, though of a more technical nature, it is shown in [Lev02, Section I.5] that the Axiom of Selection can be proved using the Axiom of Replacement and other axioms, which means that the Axiom of Selection is redundant. In practice, however, the Axiom of Selection is used frequently throughout mathematics, whereas the Ax-iom of Replacement is not used nearly as often, so both axioms are included in the ZF axioms, the former to emphasize its usefulness, and the latter because it is needed for some technicalities.

Are the ZF axioms consistent? That is, are we certain that if we deduce every-thing that can be deduced from the ZF axioms, we would never encounter a logical contradiction? The answer is that we cannot be completely sure. In general, if some-one starts with a set of axioms and deduces a specific logical contradiction, then we know that the set of axioms is inconsistent; on the other hand, if no one has yet produced a logical contradiction from a set of axioms, we cannot know if that is be-cause no logical contradiction can possibly be deduced, or if that is because there is a logical contradiction waiting to be found and it has just not been found yet.

Although we do not recommend getting too caught up in the details of the ZF axioms at this point, there is one additional axiom for set theory with which it is worth spending more time, namely, the famous Axiom of Choice. In contrast to the axioms of ZF, which arouse little controversy and are used implicitly by most math-ematicians, the Axiom of Choice is thought by some to be controversial, and when used by mathematicians (and most do use it), it is used much more explicitly than the ZF axioms. The Axiom of Choice is often abbreviated as “AC,” and when ZF is combined with AC, the resulting collection of axioms is often abbreviated as “ZFC.”Intuitively, the Axiom of Choice states that if we have a family of non-empty sets, we can simultaneously choose one element from each of the sets in the family. For a single non-empty set, there is no problem choosing an element from the set. Indeed, we regularly say things such as “let A be a non-empty set, and let a ∈ A.” For a finite family of non-empty sets, we can choose an element from the first set, and then an element from the second set, and so on, and we will be done after a finite number of steps. Again, there is no problem in making such choices. The problem arises when we have an infinite family of sets (particularly an uncountable family—uncountability will be defined in Section 6.5). From both a practical and a logical point of view, we cannot assume that it is possible to perform an infinite number of steps one at a time, and expect the process ever to be completed. In particular, we cannot choose one element from each set in an infinite family of non-empty sets by making the choices one at a time. If we want to choose one element from each set in an infinite family of non-empty sets, we need to make the choices simultaneously. Such a simultaneous choice is not something we could physically do, and the ability to do so mathematicially does not follow from the other axioms of set theory. There-fore, we need an additional axiom to guarantee our ability to make such choices, and that axiom is the Axiom of Choice.

There are a number of equivalent variants of the Axiom of Choice; we use the following. The most convenient, and useful, way of phrasing the Axiom of Choice is with the help of functions, but because we have not defined functions yet, we use the following version that is stated strictly in terms of sets. We will restate the Axiom of

The set z in the Axiom of Choice contains one element from each set in x, and these elements can be thought of as having been “chosen” by z, which leads to the name of the axiom, though of course sets do not actually make choices. The re-quirement that if y,w ∈ x, then y ̸= /0 and y∩w = /0 guarantees that every set in x has something in it that can be chosen, and that nothing in z could belong to two different sets in x, so that there is genuinely one element in z for each set in x.

For practical applications, it is convenient to reformulate the Axiom of Choice in terms of families of sets indexed by a set. We start with the following definition.

The Axiom of Choice is to be used only when there is no way to avoid it; that is, when we need to choose a single element from each set of a family of non-empty sets and when there is no explicit procedure for such a choice. This point was described amusingly by Bertrand Russell in [Rus19, Chapter 12] as follows. Suppose that a millionaire possesses an infinite number of pairs of boots, and an equal number of pairs of socks. If the millionaire wants to select one boot from each pair, he can

3.5 Axioms for Set Theory 123

The author, and the majority of mathematicians, have no qualms about using the Axiom of Choice. Indeed, we will use the Axiom of Choice in a few places in this text, for example in the proof of Zorn’s Lemma (Theorem 3.5.6) later in this section, and in the proof of Theorem 4.4.5. However, because some mathematicians have reservations about the Axiom of Choice, this axiom should always be mentioned when it is used.

In addition to using the Axiom of Choice directly, we will need a technical fact about sets that is known as Zorn’s Lemma, and that is equivalent to the Axiom of Choice. We start with the following definition.

124 3 Sets

Example 3.5.5.

{{1},{1,2},{1,2,3}}.

(2) Let Q = P(N), let S denote the family of all finite subsets of N and let C =

C is in Q , and that Q has a maximal element; in S, by contrast, neither of these facts

holds. Zorn’s Lemma, which we now state, shows that the situation just observed

for each chain C in P, the set�C∈CC is in P. Then P has a maximal element.

Proof. Suppose that P does not have a maximal element. Then for every A ∈ P, the

Let R ⊆ P. We say that the family R is chain-closed if for each chain C in R ,

the set�By hypothesis the family P is chain-closed. Let M be the intersection of all C∈CC is in R .

Let A ∈ P. Let A = {X ∈ P | SA ⊆ X}. Then A ⊆ P. Let C be a chain in A.

Then C is a chain in P, and hence�and hence SA ⊆�Therefore M ⊆ A. However, we note that A /∈ A, because otherwise we would have

3.5 Axioms for Set Theory 125

The statement of Zorn’s Lemma in Theorem 3.5.6 is not the most general form of the Lemma. The most general version is stated in terms of partially ordered sets (also called posets), which we define in Section 7.4, rather than the more narrow context of set inclusion. Moreover, the most general version requires only that every chain has an upper bound, not necessarily a least upper bound; see Exercise 3.5.7 for the definitions of these terms in the context of set inclusion, and Section 7.4 for the definitions for posets. However, even though our version of Zorn’s Lemma is not the strongest possible version, it suffices for our purposes, and it is easier to prove. Moreover, it turns out that our version of Zorn’s Lemma is actually equivalent to the more general version; see [RR85, Section I.4] for details. Hence, we name Theo-rem 3.5.6 “Zorn’s Lemma” without mentioning the fact that its statement is weaker than other versions. Also, we remark that Zorn’s Lemma is not really a lemma, but is rather a very important theorem; the name of this theorem is standard, however, and we will stick with it.

There are also a number of other important facts in mathematics that are equiv-alent to the Axiom of Choice, a few of which are the following. See [RR85] for an extremely extensive list of statements that are equivalent to the Axiom of Choice.

1. The Trichotomy Law for Sets. See Theorem 6.5.13 for the statement of this theorem and a proof of it using Zorn’s Lemma, and see [Sto79, Section 2.9] or [RR85, Section I.3] for the other implication.

We conclude this section with two quotes illustrating the controversy and confu-sion surrounding the Axiom of Choice.

has the same cardinality as A” implies the Axiom of Choice. This fact is due to As mentioned in Item (4) above, the statement “if A is an infinite set then A×A

(1) Let {(ai,bi)}i∈I be a family of non-degenerate open bounded intervals in R. (2) Let {(ci,∞)}i∈I be a family of open unbounded intervals in R.

Exercise 3.5.2. [Used in Section 3.5 and Exercise 4.4.19.] Prove that the version of the Axiom of Choice that assumes pairwise disjoint sets (Axiom 3.5.2) implies the ver-sion of the Axiom of Choice that does not make such an assumption (Theorem 3.5.3). The idea of the proof is that if we are given a non-empty set J, and a (not necessarily pairwise disjoint) family of sets

Exercise 3.5.7. [Used in Section 3.5.] Let P be a non-empty family of sets, let C ⊆ P (1) Is�(2) Is�i∈ICialways a chain in P? Give a proof or a counterexample. i∈ICialways a chain in P? Give a proof or a counterexample.

be a chain and let A ∈ P. The set A is an upper bound of C if X ⊆ A for all X ∈ C.

128 3 Sets

(4) Give an example of a non-empty family Q of subsets of R, and a chain D ⊆ Q , such that D has an upper bound in Q but not a least upper bound.

4.1 Functions

The reader has encountered functions repeatedly in previous mathematics courses. In high school one learns about polynomial, exponential, logarithmic and trigonomet-ric functions, among others. Although logarithms and trigonometry are often first encountered without thinking about functions (for example, sines and cosines are thought of in terms of solving right triangles), in calculus courses and above the focus shifts to the point of view of functions (for example, thinking of sine and co-sine as functions defined on the entire real number line). The operation of taking a derivative, for example, is something that is done to functions. In applications of calculus, such as in physics or chemistry, it is crucial to think of exponentials, sines and cosines as functions. For example, sine and cosine functions are used to describe simple harmonic motion.

© Springer Science+Business Media, LLC 2011

For example, consider the set F = {(n,n2) | n ∈ Z}. The set F is a subset of Z × Z that satisfies the conditions given in Definition 4.1.1, and hence F can be thought

of as defining a function Z → Z. However, the set F is also a subset of Z × R that satisfies the conditions in the definition of a function, and hence F can be thought

certain elements of B, where there is an arrow from a to b when (a,b) is in the subset.

For example, let A = {a,b,c,d} and B = {1,2,3,4}. Two diagrams with arrows from A to B are seen in Figure 4.1.2. In Part (i) of the figure the diagram corresponds to the

4 4

(i) (ii)

tainly do not have a function, because not everyone has a sister. Even if we restrict

the domain to all people with sisters there is a problem, because some people have

As we noted earlier, a function consists of three things: a domain, a codomain and a subset of the product of the domain and the codomain satisfying a certain

Therefore the domain of f is the same as the domain of g.

...

(argumentation)
...

Then f(a) = g(a).

2. The identity map on A is the function 1A : A → A defined by 1A(x) = x for all x ∈ A.

3. The inclusion map from S to A is the function j: S → A defined by j(x) = x for all x ∈ S.

Exercise 4.1.1. Let A = {a,b,c} and B = {1,2,3}. Which of the following subsets of A×B are functions A → B?

138 4 Functions

(1) f(a) is the mother of a.

(2) g(a) is a brother of a.

(1) Let f(x) = cosx.

(2) To every person a, let g(a) be the height of a in inches.

Exercise 4.1.9. [Used in Section 4.1.] Restate Theorem 4.1.5 in a non-indexed ver-sion.

the latter in the proof of the former, it will follow that the two results are equivalent. We make use here of the version of the Axiom of Choice stated in Theorem 4.1.5. Let I be a non-empty set, and let {Ai}i∈I be a family of non-empty sets indexed by I. Assume Zorn’s Lemma. We will show that there is a choice function for {Ai}i∈I. (1) A partial choice function for {Ai}i∈I is a function fJ : J →�J ⊆ I such that fJ(j) ∈ A j for all j ∈ J. If fJ is a partial choice function for j∈JAjfor some

(2) Let P be the set of all partial choice functions for {Ai}i∈I, and let C be a chain

We might also want to find all the adults whose heights are at least 6 ft. and no more than 6 ft. 3 in. Because we are working in inches, we therefore want to find all people whose heights are in the interval [72,75]. Hence, we want the set {x ∈ A | h(x) ∈ [72,75]}. In this case we are taking a subset of the codomain, namely, a certain set of possible heights, and finding the corresponding subset of the domain, namely, all people whose heights are as desired.

B, we want to take each subset P of A, and see where f sends all of its elements The following definition generalizes the above process. Given a function f : A →

However, the method of defining these sets given in Definition 4.2.1 will be more useful to us than these alternatives.

The terms “range” and “codomain” are often confused, so precise use of language is needed.

similar to the notation f−1(Q), the concept of an inverse image of a set and the

concept of an inverse function are quite different, and it is the similarity of notation

set Q under f−1, because f−1(Q) is used even in cases where the function f−1does

not exist. Proofs about sets of the form f−1(Q) should not make use of an inverse

Example 4.2.3. Let h: R → R be defined by h(x) = x2for all x ∈ R. It is straightfor-ward to compute that h([0,3]) = [0,9] and h([−2,2]) = [0,4]. Then h−1(h([0,3])) = h−1([0,9]) = [−3,3]. We therefore see that h−1(h([0,3])) ̸= [0,3]. Similarly, we compute that h(h−1([−4,4])) = h([−2,2]) = [0,4], and hence h(h−1([−4,4])) ̸= [−4,4]. ♦

For the proof of the following theorem, as well as for subsequent results involving

sort of thing to which they could be equal), we use the standard strategy for proving

equality of sets, which is showing that each set is a subset of the other.

“x = f(a) for some a ∈ P” can be rewritten as “x ∈ f(P).” Similarly, suppose that we start with a statement of the form “z ∈ f−1(Q).” The definition of f−1(Q) allows us to rewrite the statement as “f(z) ∈ Q,” which again is easier to work with than the original statement. Conversely, a statement of the form “ f(z) ∈ Q” can be rewritten as “z ∈ f−1(Q).” As is the case with many problems in mathematics, going back to the definitions is often the best way to start creating a proof.

The following theorem, the proof of which uses the above mentioned strategies,

(3) Let h: R → (0,∞) be defined by h(x) = ex−1+3 for all x ∈ R. (4) Let p: R → R be defined by p(x) =√x4+5 for all x ∈ R.

(5) Let q: R → [−10,10] be defined by q(x) = sinx+cosx for all x ∈ R.

(4) m−1([−5,3]).
(5) m−1({0}).

Exercise 4.2.3. For each of the following functions f : R → R and each set T ⊆ R, find f(T), f−1(T), f(f−1(T)) and f−1(f(T)).

(2) g−1([−1,1]).

Exercise 4.2.5. Let X and Y be sets, let A ⊆ X and B ⊆ Y be subsets and let π1 : X ×Y → X and π2 : X ×Y → Y be projection maps as defined in Section 4.1.

(9).

Exercise 4.2.7. Find the flaw(s) in the following alleged proof of Theorem 4.2.4 (8),

k∈KVk.

Exercise 4.2.8. In this exercise we show that it is not possible to strengthen Theo-

Exercise 4.2.9. Find an example to show that the “⊆” in Theorem 4.2.4 (7) cannot be replaced with “=.” It is sufficient to use the intersection of two sets.

Exercise 4.2.10.

(1) Prove that f(P)− f(Q) ⊆ f(P−Q).
(2) Is it necessarily the case that f(P − Q) ⊆ f(P) − f(Q)? Give a proof or a counterexample.

Exercise 4.2.12. Let A and B be sets, let C,D ⊆ B be subsets and let f : A → B be a function. Prove that f−1(D−C) = f−1(D)− f−1(C).

(6) Prove that f−1(f(f−1(Y))) = f−1(Y).

Exercise 4.2.14. Let A and B be sets, and let f,g: A → B be functions. Think of these functions as inducing functions f∗,g∗ : P(A) → P(B), and functions f∗,g∗: P(B) →P(A). Prove that f∗ = g∗ if and only if f∗= g∗if and only if f = g.

(2) Prove that there is some T ∈ P(A) such that g(T) = T. Such an element T is called a fixed point of g. Use Part (1) of this exercise.

146 4 Functions

(g◦ f)(x) = g(f(x))

for all x ∈ A. △

because g◦ f means doing f first and then g even though we generally read from left to right in English. Think of “◦” as meaning “following.” We will stick with the “◦”notation in spite of any slight confusion it might cause at first, because it is extremely

widespread, and because the reader will find that it works well once she is used to it.

4.3 Composition and Inverse Functions 147

One way to visualize the composition of functions is to use “commutative dia-grams.” If f : A → B and g: B → C are functions, then we can form g◦ f : A → C, and we can represent all three of these functions in the following diagram.

Definition 4.3.3. Let B be a set, let A1,...,An be sets for some n ∈ N and let f : B → A1 ×···×An be a function. For each i ∈ {1,...,n}, the i-th coordinate function of f, denoted fi, is the function fi : B → Ai defined by fi = πi ◦ f, where πi : A1 ×···×An → Ai is the projection map. △ The fact that fi = πi ◦ f for all i ∈ {1,...,n}, as given in Definition 4.3.3, means that f(x) = (f1(x),..., fn(x)) for all x ∈ B. In some texts this fact is abbreviated by writing f = (f1,..., fn), or alternatively by writing f = f1 × ··· × fn. How-ever, although the notations (f1,..., fn) and f1 × ··· × fn could be formally de-fined to be the function we have denoted f, the reader is urged to use these two notations with caution, or to avoid them at all, for the following reason. Whereas writing f(x) = (f1(x),..., fn(x)) is perfectly sensible, the two sides of the equa-tion being different expressions for the same element of A1 × ··· × An, using the notation f = (f1,..., fn) might mistakenly suggest that the function f is an ele-ment of the product of n sets, which is not necessarily true, and using the notation

also not necessarily true. f = f1 × ··· × fn might mistakenly suggest that f is the product of n sets, which is

Example 4.3.4. Let f : R2→ R3be defined by

f((x,y)) = (xy,sinx2,x+y3)

1. (h◦g)◦ f = h◦(g◦ f) 2. f ◦1A = f and 1B ◦ f = f (Associative Law). (Identity Law).

Proof.

Do functions have inverses under composition? That is, for any given function is there another that “cancels it out” by composition? In arithmetic, for example, we can cancel out the number 3 by adding −3 to it, which yields 0. For functions, the operation addition and the number 0 are replaced with composition of functions and the identity map, respectively. However, the non-commutativity of composition means that we need a bit more care when we define “canceling out” for functions than we do with addition (which is commutative).

Definition 4.3.6. Let A and B be sets, and let f : A → B and g: B → A be functions. 1. The function g is a right inverse for f if f ◦g = 1B.
2. The function g is a left inverse for f if g◦ f = 1A.

2. If f has a right inverse g and a left inverse h, then g = h, and hence f has an inverse.

3. If g is an inverse of f, then f is an inverse of g.

By the definition of inverses, it follows that f is an inverse of g. (3). Suppose that g: B → A is an inverse of f. Then g ◦ f = 1A and f ◦ g = 1B.⊓⊔

Observe that the proof of Lemma 4.3.7 (1) is virtually identical to the proof of the uniqueness part of Theorem 2.5.2. The same proof in a more generalized setting is also used for Lemma 7.2.4. Lemma 4.3.7 (1) allows us to make the following definition.

We note that if f : A → B has an inverse f−1: B → A, then f−1(f(x)) = x for all x ∈ A and f(f−1(x)) = x for all x ∈ B. Another way of stating the relation between

This latter formulation will not be particularly useful to us in the construction of f and f−1is to say that y = f−1(x) if and only if x = f(y) for all y ∈ A and x ∈ B.

that k has an inverse, the function j: (3,5) → (0,1) defined by j(x) =x−3 (1) Let k: (0,1) → (3,5) be defined by k(x) = 2x+3 for all x ∈ (0,1). We claim for all x ∈ (3,5). We compute j(k(x)) =(2x+3)−3 = x for all x ∈ (0,1), and hence j ◦ k = 1(0,1). Similarly, we compute k(j(x)) = 2 ·x−3 2+ 3 = x for all x ∈ (3,5), and hence

Exercise 4.3.1. For each pair of functions f and g given below, find formulas for

f ◦g and g◦ f (simplifying when possible).

(4) Let f : R → R be defined by f(x) = ⌊x⌋ for all x ∈ R, and let g: R → R be defined by g(x) = ⌈x⌉ for all x ∈ R, where ⌊x⌋ and ⌈x⌉ are respectively the greatest integer less than or equal to x and the least integer greater than or

equal to x.

x, if 0 ≤ x if x < 0.

Exercise 4.3.3. Let f,g: R → R be defined by

(2) Find two functions s,t : R → R such that s ̸= 1R and t ̸= 1R, but t ◦s = 1R. Exercise 4.3.5. [Used in Theorem 6.3.11 and Theorem 6.6.5.] Let A and B be sets, let U ⊆ A and V ⊆ C be subsets, and let f : A → B and g: B → C be functions. Prove that
(g◦ f)−1(V) = f−1(g−1(V)). (g◦ f)(U) = g(f(U)) and
Exercise 4.3.6. Let A, B and C be sets, and let f : A → B and g: B →C be functions. Suppose that f and g have inverses. Prove that g ◦ f has an inverse, and that (g ◦f)−1= f−1◦g−1.

Exercise 4.3.7. Find two right inverses for each of the following functions.

4.3 Composition and Inverse Functions 153

Exercise 4.3.9. Let h,k: R → R be defined by

Exercise 4.3.10. Let A and B be sets, and let f : A → B be a function. Prove that if f has two distinct left inverses then it has no right inverse, and that if f has two distinct right inverses then it has no left inverse.

Exercise 4.3.11. Let B be a set, let A1,...,Ak be sets for some k ∈ N, let Ui ⊆ Ai be a subset for all i ∈ {1,...,k} and let f : B → A1 ×···×Ak be a function. Prove that

Ai

Exercise 4.3.13. This exercise and the next give examples of definitions of functions by universal property. Rather than defining what a certain function is, we state how it should behave, and then prove that there exists a function satisfying the given be-havior. Such constructions are important in category theory, a branch of mathematics that provides a useful (though abstract) language for many familiar mathematical ideas, and has applications to various aspects of mathematics, logic and computer science. See [AM75] or [Kri81] for an introduction to category theory, and [Pie91] for some uses of category theory in computer science.

Exercise 4.3.14. This exercise is similar to Exercise 4.3.13. Let A, B and C be sets, and let f : A → C and g: B → C be functions. Prove that there exist a set P and functions h: P → A and k: P → B such that f ◦h = g◦k, and that for any set X and functions s: X → A and t : X → B such that f ◦ s = g ◦t, there is a unique function u: X → P such that s = h◦u and t = k ◦u. This last condition is represented by the following commutative diagram. The set P together with the functions h and k are called a pullback of f and g. To define P, consider subsets of A×B.

X
......................................................................................................................................................................................................................................................................... ............ P ................................................................................................................ ............ k B

To understand the criteria for the existence of right inverses and left inverses, we start with an example.

Example 4.4.1. Let P be the set of all people, and let m: P → P be the function that assigns to each person her mother. Does this function have a right inverse or a left inverse? Suppose first that g: P → P is a right inverse for m. That would mean that

It turns out that the two problems identified in Example 4.4.1 are the only obsta-cles to finding right inverses and left inverses, respectively. We now give names to functions that do not have these problems.

Definition 4.4.2. Let A and B be sets, and let f : A → B be a function.

156 4 Functions

4.4 Injectivity, Surjectivity and Bijectivity 157

Proof. Let x,y ∈ A. Suppose that f(x) = f(y).

...

We will use the above strategies repeatedly, starting with the proof of the follow-ing lemma, which shows that composition of functions behaves nicely with respect to injectivity, surjectivity and bijectivity.

Lemma 4.4.4. Let A, B and C be sets, and let f : A → B and g: B →C be functions. 1. If f and g are injective, then g◦ f is injective.
2. If f and g are surjective, then g◦ f is surjective.
3. If f and g are bijective, then g◦ f is bijective.
Proof.

The following theorem, which is extremely useful throughout mathematics (and is perhaps the author’s favorite theorem in this text), answers the question posed at the start of this section concerning criteria for the existence of inverse functions.

Theorem 4.4.5. Let A and B be non-empty sets, and let f : A → B be a function. 1. The function f has a right inverse if and only if f is surjective.
2. The function f has a left inverse if and only if f is injective.

which means that we need to find a function h: B → A such that f ◦ h = 1B. We define h as follows. For each b ∈ B, the surjectivity of f implies that there is at least one element a ∈ A such that f(a) = b; let h(b) = a for some choice of such a (it doesn’t matter which one). It is now true by definition that f(h(b)) = b for all b ∈ B. Hence f ◦h = 1B.

(2). Left to the reader in Exercise 4.4.9.

for the sake of brevity and in order to avoid distraction from the essential idea of the

proof of Theorem 4.4.5, we did not explicitly make use of the Axiom of Choice in

of Choice or something equivalent, but it turns out that that would not have been pos-

sible, because Theorem 4.4.5 (1) is in fact equivalent to the Axiom of Choice, as seen

Theorem 4.4.6. Let A and B be non-empty sets, and let f : A → B be a function.

1. The function f is injective if and only if f ◦ g = f ◦ h implies g = h for all functions g,h: Y → A for all sets Y.

(3) Let g: [0,∞) → [0,1) be defined by g(x) =
(4) Let k: R2→ R be defined by k((x,y)) = x2+y2for all (x,y) ∈ R2.

(5) Let Q: N → P(N) be defined by Q(n) = {1,2,...,n} for all n ∈ N.

Prove that f is bijective. Use only the methods we have used in this text, including the standard algebraic properties of the real numbers; do not use calculus.

Exercise 4.4.5. Let A and B be sets. Prove that there is a bijective function f : A×B →B×A.

Exercise 4.4.6. [Used in Section 3.3.] Let A, B and C be sets. Prove that there is a bijective function g: (A×B)×C → A×(B×C).

(2) Prove that U((a,b)) ̸= (a,b) and D((a,b)) ̸= (a,b) for all (a,b) ∈ L. (3) Prove that U and D are injective.

(4) Prove that U(L)∩D(L) = /0.

Exercise 4.4.12. Let A and B be sets, and let f : A → B be a function.

(1) Prove that f is injective if and only if E = f−1(f(E)) for all subsets E ⊆ A.

162 4 Functions

Exercise 4.4.14. [Used in Section 4.4.] Let A, B and C be sets, and let f : A → B and g: B → C be functions.

this exercise are the best possible results.

Exercise 4.4.15. [Used in Theorem 4.4.6.] Prove Theorem 4.4.6 (1).

(4) Prove that f∗is surjective if and only if f is injective.

(5) Prove that f∗ is bijective if and only if f∗is bijective if and only if f is

is sufficient to prove the Axiom of Choice for Pairwise Disjoint Sets. Although Ex-

ercise 3.5.2 was stated for the family of sets versions of the Axiom of Choice, that

Theorem 4.1.5), and make use of that version in this exercise.

Exercise 4.4.20. [Used in Exercise 4.4.21.] Let A be a non-empty set, and let f : A →A be a function. Suppose that f is bijective. For each n ∈ N, let fndenote the function A → A given by fn= f ◦···◦ f .

For each n ∈ N, let f−n= (fn)−1. It can be verified that fa◦ fb= fa+band (fa)b=

part of this exercise; the interested reader can find the details of the first of these fabfor all a,b ∈ Z, though we omit the details for the sake of getting to the interesting

c. If y = fn(x) for some n ∈ Z, and z = fm(y) for some m ∈ Z, then z =

(In Section 5.3 we will see that these three properties are particularly impor-fp(x) for some p ∈ Z.

Putting these observations together, we see that A can be broken up into dis-d. A =�x∈AOx.

joint sets, each of which is the orbit of all its members. (Using the terminol-

(1) Prove that fm= 1A for some m ∈ N. Use the fact that because A is finite, there are only finitely many bijective functions A → A; this fact is proved in Theorem 7.7.4 (3). Let r ∈ N be the smallest natural number such that fr= 1A. (It makes sense intuitively that there is such a smallest natural number;

formally we make use of the Well-Ordering Principle (Theorem 6.2.5).)

164 4 Functions

(7) Prove that nx|r.

(12) For each m ∈ {0,...,r−1}, the fixed set of m, denoted Am, is the set defined by Am = {z ∈ A | fm(z) = z}. Prove that r · B = ∑r−1 special case of Burnside’s Formula; see [Fra03, Section 17] for details. i=0|Ai|. This result is a

4.5 Sets of Functions

will use sets of functions briefly at the end of Section 6.7, and a bit more exten-

sively in Section 7.7. The material in this section is among the most conceptually

For any set A and B, we observe that F (A,B) is also a set, where each element of

the set F (A,B) is a function A → B. There is no theoretical problem with having a set that has elements that are functions, though sometimes it is hard to get an intuitive

(1) If A ̸= /0 and B = /0, then F (A,B) = /0. If A = /0, then F (A,B) = {/0}. If A ̸= /0 and B ̸= /0, then F (A,B) ̸= /0, because there is at least one constant map A → B. (2) Let A = {1,2} and B = {x,y}. Then F (A,B) = {f,g,h,k}, where the func-tions f,g,h,k: A → B are defined by f(1) = x and f(2) = x, by g(1) = x and g(2) = y, by h(1) = y and h(2) = x, and by k(1) = y and k(2) = y.

(3) The set F (R,R) has a number of useful subsets, including the set C(R,R) of

(4) We can give an intuitive interpretation of the set F (N,R) as follows. Let

f ∈ F (N,R). Then we obtain a sequence of real numbers by writing f(1), f(2), f(3), .... Conversely, given a sequence of real numbers a1, a2, a3, ..., we can define

we give two typical results. We start with a relatively simple lemma, which will be

of use later on.

A ......................................................................................................................................... ............ h B

f ..................................................................................................................................................... ..................................................................................................................................................... g

The theorem says that there is a bijective function from P(A) to F (A,{0,1}). What, intuitively, is the relation between elements of P(A), each of which is a subset of A,

and elements of F (A,{0,1}), each of which is a function A → {0,1}? Let S ∈ P(A), so that S ⊆ A. We want to associate with this set S a function A → {0,1}. To do so, observe that we can divide A into the two disjoint subsets S and A−S. We then define a function from A to {0,1} by assigning the value of 1 to every element in S, and 0 to

Theorem 4.5.4. Let A be a set. Then there is a bijective function from P(A) to

F (A,{0,1}).

surjective, starting with the former. Let S,T ∈ P(A). Suppose that Φ(S) = Φ(T). Then χS = χT, and it follows from Exercise 4.1.8 that S = T. Therefore Φ is injective.

We now show that Φ is surjective. Let f ∈ F (A,{0,1}). Let S = f−1({1}), so that S ∈ P(A). We will show that Φ(S) = f, which is the same as showing that χS = f. Both χS and f are functions A → {0,1}. Observe that A − S = f−1({0}). Then, if y ∈ A, we see that

=�1,

0,
if f(y) = 1

Ψ ◦Φ = 1P(A) and Φ ◦Ψ = 1F (A,{0,1}).

Let S ∈ P(A). Then

(1) Let A and B be the sets given in Example 4.5.2 (2). It is seen that B(A,B) = I(A,B) = {g,h}.

show in Exercise 4.5.8, it turns out that I(A,C) has six elements. This example is a (2) Let A = {1,2} and C = {x,y,z}. Then B(A,C) = /0. As the reader is asked to

element f(1) is the first element in the ordered pair, and f(2) is the second element in the ordered pair. Hence the product A×B can be thought of as the set of functions

{ f ∈ F ({1,2},A∪B) | f(1) ∈ A and f(2) ∈ B}.

Choice, and that is what looks so familiar in Definition 4.5.7. If the reader compares the statement of the Axiom of Choice given in Theorem 4.1.5 with Definition 4.5.7, it is immediately evident that not only does the Axiom of Choice imply the following theorem, but the following theorem implies the Axiom of Choice; that is, the Axiom of Choice and the following theorem are equivalent.

Theorem 4.5.8. Let I be a non-empty set, and let {Ai}i∈I be a family of non-empty sets indexed by I. Then ∏i∈I Ai ̸= /0.

(1) Prove that F (C,A) ⊆ F (C,B).

(2) Prove that there is an injective function F (A,C) → F (B,C).

Exercise 4.5.7. Let A be a set, and let g: A → A be a function. Suppose that g is bijective.

(1) Let Ωg : F (A,A) → F (A,A) be defined by Ωg(f) = g◦ f for all f ∈ F (A,A). Prove that Ωg is bijective.

(2) Prove that there is a bijective function from B(A,B) to B(C,D).

Exercise 4.5.10. [Used in Theorem 7.7.4 and Theorem 7.7.12.] Let A and B be sets,

Exercise 4.5.11. Let A be a set. Let Φ : B(A,A) → B(A,A) be defined by Φ(f) = f−1for all f ∈ B(A). Prove that Φ is bijective.

Exercise 4.5.12. Let A be a set. A Z-action on A is a function Γ : Z → B(A,A) that satisfies the following two properties: (1) Γ (0) = 1A, and (2) Γ (a+b) = Γ (a)◦Γ (b) for all a,b ∈ Z.

Mathematicians do not study objects, but relations between objects.
– Henri Poincar´e (1854–1912)

5.1 Relations

Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-7127-2_5,

© Springer Science+Business Media, LLC 2011

{(1,y),(1,z),(2,y)}. Then 1 E y, and 1 E z, and 2 E y, but 3 ̸E x. (2) Let P be the set of all people. Define a relation on P by having person x related to person y if and only if x and y have at least one parent in common. (3) The symbols < and ≤ both represent relations on R. (4) Let P be the set of all people, and let B be the set of all books. Define a relation from P to B by having person x related to book b if and only if x has read b. (5) Let A be a set. The symbol “⊆” represents a relation on P(A), where P,Q ∈P(A) are related if and only if P ⊆ Q.

a certain condition. Hence f is also a relation from A to B. The concept of a relation (6) Let f : A → B be a function. Then f is defined by a subset of A×B satisfying

Then x S y.

Second, suppose that x S y.
...

Just as a person might wish to find out who all of her relatives are, if we have a relation from a set A to a set B, it is sometimes useful to find all the elements of B that are related to a given element in A.

Definition 5.1.3. Let A and B be non-empty sets, let R be a relation from A to B, and let x ∈ A. The relation class of x with respect to R, denoted R[x], is the set defined by
R[x] = {y ∈ B | x R y}.

In the following definition we give three such properties of relations that will be useful to us in the next two sections, and in many parts of mathematics.

Definition 5.1.5. Let A be a non-empty set, and let R be a relation on A.

Example 5.1.6.

(1) The relation of congruence of triangles in the plane is reflexive, symmetric and transitive.

(7) The relation < on R is transitive, but neither reflexive nor symmetric. Let x,y,z ∈ R. The relation is transitive, because if x,y,z ∈ R, and if x < y and y < z, then x < z. The relation is not reflexive, because it is never the case that x < x, for any x ∈ R. (Observe that we have much more here than the minimum needed to prove that the relation < is not reflexive; it would have sufficed to know that z ≮ z for a single z ∈ R.) The relation is not symmetric, because if x,y ∈ R, and x < y, it is never the case that y < x. (Again, we have much more than is minimally needed to prove that < is not symmetric.)
(8) The relation of one person being the daughter of another person is neither reflexive, symmetric nor transitive. ♦

There are standard proof strategies for proving that a relation is reflexive, sym-metric or transitive. Let A be a non-empty set, and let R be a relation on A.

(argumentation)
...

Then x R x. Hence R is reflexive. ⊓⊔ If we wish to prove that R is symmetric, we need to show that x R y implies y R x for every x,y ∈ A. Observe that to prove that R is symmetric, we do not prove that

Exercise 5.1.1. For each of the following relations on Z, find the relation classes [3] and [−3] and [6].

(1) Let S be the relation defined by a S b if and only if a = |b|, for all a,b ∈ Z.

(3) Let Z be the relation defined by (x,y) Z (z,w) if and only if x = z or y = w, w2, for all (x,y),(z,w) ∈ R2.

for all (x,y),(z,w) ∈ R2.

(4)¯P = {(1,1),(2,2),(3,3)}.

(5)¯Q = {(1,2),(2,1),(1,3),(3,1),(1,1)}.

(1) Let S be the relation on R defined by x S y if and only if x = |y|, for all x,y ∈ R. (2) Let P be the set of all people, and let R be the relation on P defined by x R y

(3) Let T be the set of all triangles in the plane, and let G be the relation on T if and only if x and y were not born in the same city, for all x,y ∈ P.

(6) Let D be the relation on N defined by a D b if and only if a|b, for all a,b ∈ N.

(7) Let T be the relation on Z × Z defined by (x,y) T (z,w) if and only if there is a line in R2that contains (x,y) and (z,w) and has slope an integer, for all

essarily either?

(2) If R symmetric, is R′necessarily symmetric, necessarily not symmetric or not

metric and transitive. Find the flaw in the following alleged proof that this relation is

necessarily reflexive; there must be a flaw by Example 5.1.6 (4). “Let x ∈ A. Choose

x,y ∈ A.

(3) Suppose that R is transitive. Prove that if x R y, then [y] ⊆ [x], for all x,y ∈ A.

(4) Let k: R2→ R be defined by k((x,y)) = 3x2+6xy+3y2for all (x,y) ∈ R2; let M be the relation on R2defined by (x,y) M (z,w) if and only if x+y = z+w, for all (x,y),(z,w) ∈ R2.

Exercise 5.1.10. Let A and B be sets, let R be a relation on A and let f : A → B be a function. Suppose that f is injective, and that it respects the relation R, as defined in Exercise 5.1.9. What, if anything, can be proved about the relation R?

In this section we discuss a very important type of relation on the set of integers, which will serve to illustrate the general topic discussed in the next section, and is also a valuable tool in various parts of mathematics and its applications, for example number theory, cryptography and calendars. See [Ros05, Chapters 4 and 5] for fur-ther discussion of congruence and its applications, and see [Kob87] for a treatment of congruence and cryptography.

The idea of congruence is based upon the notion of “clock arithmetic,” a term sometimes used in elementary mathematics. (For the reader who has not seen “clock arithmetic,” it will be sufficient to have seen a clock). For the sake of uniformity, we will make all references to time using the American 12-hour system (ignoring a.m. vs. p.m.), as opposed to the 24-hour system used many places around the world, and in the U.S. military.

Definition 5.2.1. Let n ∈ N, and let a,b ∈ Z. The number a is congruent to the number b modulo n, denoted a ≡ b (mod n), if a−b = kn for some k ∈ Z. △Example 5.2.2. We see that 19 ≡ −5 (mod 4), because 19−(−5) = 24 = 6·4; and 7 ≡ 7 (mod 3), because 7−7 = 0 = 0·3; and 13 ̸≡ 2 (mod 9), because 13−2 = 11 and 11 is not a multiple of 9. ♦

following lemma shows that for each n, this relation is reflexive, symmetric and For each n ∈ N, we obtain a relation on Z given by congruence modulo n. The

3. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n). Proof.

(1). Observe that a−a = 0·n.

this theorem makes use of an important fact about the integers known as the Division

Algorithm, which is stated as Theorem A.5 in the Appendix.

Corollary 5.2.5. Let n ∈ N, and let a ∈ Z. Then precisely one of the following holds: either a = nk for some k ∈ Z, or a = nk +1 for some k ∈ Z, or a = nk +2 for some k ∈ Z, ..., or a = nk +(n−1) for some k ∈ Z.

If we use n = 2 in Corollary 5.2.5, we deduce the following familiar result.

...

[0] = {...,−10,−5,0,5,10,...}

[5] = {...,−5,0,5,10,15...}.

...

tinct classes. Moreover, these classes are disjoint, and their union is all of Z. The

analogous result holds for arbitrary n, as stated in the following theorem.

(1). Suppose that a ≡ b (mod n). Let x ∈ [a]. Then by the definition of relation classes we know that a ≡ x (mod n). By Lemma 5.2.3 (2) it follows that b ≡ a (mod n), and hence by Lemma 5.2.3 (3) we deduce that b ≡ x (mod n). Therefore x ∈ [b], and hence [a] ⊆ [b]. A similar argument shows that [b] ⊆ [a]. We conclude that [a] = [b].

Now assume that a ̸≡ b (mod n). We use proof by contradiction. Suppose that [a]∩[b] ̸= /0. Hence there is some y ∈ [a]∩[b]. Then y ∈ [a] and y ∈ [b], so that a ≡ y (mod n) and b ≡ y (mod n). By Lemma 5.2.3 (2) we see that y ≡ b (mod n), and by Lemma 5.2.3 (3) it follows that a ≡ b (mod n), which is a contradiction. We conclude that [a]∩[b] = /0.

Definition 5.2.8. Let n ∈ N. The set of integers modulo n, denoted Zn, is the set defined by Zn = {[0],[1],...,[n−1]}, where the relation classes are for congruence modulo n. △

The set Zn is also denoted Z/nZ in some texts, for reasons that will become

so Z12 = {[12],[1],...,[11]}, which is what we see on the face of a clock. For math-ematical purposes it is more convenient to write [0] rather than [12], and so we will

continue to write Z12 as we did originally; it would also be nice to have the 12 on

are many sets with n elements, but what makes Zn particularly useful is that there For each n ∈ N, the set Zn has n elements. Of course, for each n ∈ N, there

is a natural way to define addition and multiplication on it, as seen in the follow-

Definition 5.2.10. Let n ∈ N. Let + and · be the binary operations on Zn defined by [a]+[b] = [a+b] and [a]·[b] = [ab] for all [a],[b] ∈ Zn. △

As reasonable as Definition 5.2.10 seems, there is a potential problem. Let n ∈N, and let [a],[b],[c],[d] ∈ Zn. Suppose that [a] = [c] and [b] = [d]. Do [a+b] = [c+d] and [ab] = [cd] necessarily hold? If not, then we could not say that [a] +

we verify using the following lemma.

Lemma 5.2.11. Let n ∈ N, and let a,b,c,d ∈ Z. Suppose that a ≡ c (mod n) and b ≡ d (mod n). Then a+b ≡ c+d (mod n) and ab ≡ cd (mod n).

From Lemma 5.2.11, together with Theorem 5.2.7 (1), we deduce the following

corollary, which we state without proof. This corollary tells us that + and · as given in Definition 5.2.10 are indeed well-defined for each Zn.

182 5 Relations

(See Section 7.1 for more discussion of such operation tables.) Consider the follow-

the form ax = b, always has a unique solution whenever a ̸= 0. The situation in Zn is more complicated. Consider the equation [4] · x = [3]. In Z11 there is a unique solution, which is x = [9], as can be verified simply by trying each element of Z11 as a possible candidate for x. In Z12 the same equation has no solution, as can again be verified by trying each element of Z12. The equation [3]·x = [0] has three solutions in Z6, which are x = [0],[2],[4], as can be seen using the operation table for · for Z6. We therefore see that in Z6 it is possible to have two non-zero elements such that their product is [0], in contrast to the situation for multiplication of real numbers. See [Fra03, Section 20] for further discussion of this type of equation in Zn.

Our final comment about Zn takes us back to our initial discussion of clocks, where we took the number 41 (which was the result of starting at 11 o’clock and adding 30 hours), and we then subtracted the number 12 as many times as needed from 41 until a number in the 1 to 12 range was obtained; in this case we obtained the number 5. There are, of course, infinitely many numbers in Z that, when treated in this same way, will yield the number 5. Rather than thinking of the number 5 here as an integer, it is more correct to think of it as an element of Z12. That is, we think of taking infinitely many elements of Z, and we send them all to a single element in Z12. Of course, there is nothing special about the number 5, and there is nothing special about working modulo 12. We now use functions to formalize this process.

ical map that will be seen in Definition 5.3.8. The canonical map γ : Z → Zn is a special case of a more general type of canon-

We now see two simple results about the canonical map that are examples of more general, though rather different, phenomena we will see subsequently.

γ ................................................................................................... ..........................................................................................................................................................................................................................................
Zn

In contrast to Lemma 5.2.14, which can be generalized to all equivalence re-lations, as seen in Lemma 5.3.9, the following property of the canonical map for congruence modulo n is not applicable to most equivalence relations, though it can be generalized in a very different way, as discussed in Section 7.3.

Exercise 5.2.2. Solve each of the following equations in the given set Zn. (In some cases there is no solution.)

184 5 Relations

Exercise 5.2.4. Let n,q ∈ N, and let a,b ∈ Z. Suppose that a ≡ b (mod n), and that q|n. Prove that a ≡ b (mod q).

Exercise 5.2.5. Let n ∈ N, and let a,b ∈ Z. Suppose that a ≡ b (mod n). Prove that n|a if and only if n|b.

the “···” are avoided.

prime number. The converse to this result, known as Wilson’s Theorem, is also true, Let n ∈ N. Suppose that n > 1, and that (n−1)! ≡ −1 (mod n). Prove that n is a

Exercise 5.2.10. [Used in Lemma 5.2.14.] Prove Lemma 5.2.14.

Exercise 5.2.11. [Used in Lemma 5.2.15.] Prove Lemma 5.2.15.

You may use the fact that the statement of Lemma 5.2.11 can be extended to sums

and products of any finite number of integers.

(3) Let ¯Σ(a) be an abbreviation for ΣM(a)(a); that is, the number ¯Σ(a) is the result of repeatedly adding the digits of the number a until a single digit remains. (This process is used in gematria, a method employed in Jewish mysticism, as well as in similar constructions in Greek and Arab traditions; see [Ifr85, Chapter 21] for details.) Does ¯Σ(a + b) =¯Σ(a) +¯Σ(b) always hold? Give a proof or a counterexample. Does ¯Σ(ab) =¯Σ(a) ·¯Σ(b) always hold? Give a proof or a counterexample.

(4) Prove that ¯Σ(a+b) =¯Σ(¯Σ(a)+¯Σ(b)) and ¯Σ(ab) =¯Σ(¯Σ(a)·¯Σ(b)).

Definition 5.3.3. Let A be a non-empty set, and let ∼ be an equivalence relation on A. The relation classes of A with respect to ∼ are called equivalence classes. △ For the rest of this section, in order to avoid trivial cases, we will restrict our attention to non-empty sets. We start with the following theorem, which generalizes

186 5 Relations

cise 5.3.6.

By reflexivity we see that q ∼ q, and therefore q ∈ [q] ⊆�We conclude that�(2). By definition [x] ⊆ A for all x ∈ A, and hence�

The following corollary is derived immediately from Theorem 5.3.4 (1).

Corollary 5.3.5. Let A be a non-empty set, let ∼ be an equivalence relation on A and let x,y ∈ A. Then [x] = [y] if and only if x ∼ y.

at another way, each equivalence class is named after each of its elements, so that a

single equivalence class may have many names, but it is still a single set, and a single

In the following definition, which generalizes Definition 5.2.13, we use functions

to relate a set and its quotient set.

Using the terminology of Exercise 5.1.9, we say that the function f in Lemma 5.3.9

respects ∼. The condition f = g◦γ in Lemma 5.2.14 is represented by the following commutative diagram (as discussed in Section 4.3).

Suppose that we have a quotient set A/∼. We see from Theorem 5.3.4 that any two distinct equivalence classes in A/∼ are disjoint, and that the union of all the equivalence classes is the original set A. We can therefore think of A/∼ as the result of breaking up the set A into disjoint subsets. The following definition generalizes

this notion of breaking up a set into disjoint subsets.

188 5 Relations

Definition 5.3.10 (a) can be rephrased more concisely by saying that D is pair-wise disjoint, using the terminology of Definition 3.5.1, though here we use the non-indexed version of the definition. A schematic representation of a partition of a set is seen in Figure 5.3.1. Another way of looking at partitions is to observe that if E is a family of subsets of a set A, then E is a partition of A if and only if for each x ∈ A, there is one and only one P ∈ E such that x ∈ P.

(2) Let C = {[n,n+1)}n∈Z. Then C is a partition of R.

(3) Let G = {(n−1,n+1)}n∈Z. Then G is not a partition of R, because it is not pairwise disjoint. For example, we observe that (1−1,1+1) ∩ (2−1,2+1) = (1,2). ♦

using bijective functions. To state our result, we will need the following definition,

which takes us to one higher level of abstraction than we have seen until now in our

TA are. Each element of E(A) is an equivalence relation on A, which formally is a

subset of A×A that satisfies certain conditions. Each element of TA is a partition of A, which is a family of subsets of A that satisfy certain conditions.

¯R1 = {(1,1),(2,2),(3,3)},
¯R2 = {(1,1),(2,2),(3,3),(1,2),(2,1)},
¯R3 = {(1,1),(2,2),(3,3),(1,3),(3,1)},
¯R4 = {(1,1),(2,2),(3,3),(2,3),(3,2)},
¯R5 = {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}.

It is straightforward to verify that each of the relations Ri listed above is an equiva-

partitions of A. To state this correspondence precisely, we start by defining, for each

non-empty set A, a function from E(A) to TA, and a function in the other direction. It

non-empty set A, but to avoid unnecessarily cumbersome notation (such as ΦA and

ΨA), we will assume that the set A is always known from the context.

these claims follows immediately from the definition of Φ and Corollary 5.3.12. The

second claim is left to the reader in Exercise 5.3.11. ⊓⊔

in Example 5.3.14. It can be verified that Φ(Ri) = Di and Ψ(Di) =Ri for all i ∈{1,...,5}; details are left to the reader. ♦

In Example 5.3.17 (3), we see that Φ and Ψ are inverses of each other. Quite

relation on A there corresponds a unique partition of A, and vice versa. Moreover, not

only do we know in principle that there is such a correspondence, but, even better,

Proof. We need to show that

(4) Let P be the set of all people, and let Z be the relation on P defined by x Z y x,y ∈ R.

(5) Let P be the set of all people, and let R be the relation on P defined by x R y if and only if x and y are first cousins, for all x,y ∈ P.

(1) Let R be the relation defined by a R b if and only if |a| = |b|, for all a,b ∈ R.

(2) Let S be the relation defined by a S b if and only if sina = sinb, for all a,b ∈ R.

(1) Let Q be the relation defined by (x,y) Q (z,w) if and only if x2+y2= z2+w2,

for all (x,y),(z,w) ∈ R2.

Exercise 5.3.4. Let A and B be sets, and let f : A → B be a function. Let ∼ be the relation on A defined by x ∼ y if and only if f(x) = f(y), for all x,y ∈ A.

(1) Prove that ∼ is an equivalence relation.

Exercise 5.3.6. [Used in Theorem 5.3.4.] Prove Theorem 5.3.4 (1).

Exercise 5.3.7. [Used in Lemma 5.3.9.] Prove Lemma 5.3.9.

sponding partition. Your description of each partition should have no redundancy,

and should not refer to the name of the relation.

l1 ≏ l2 if and only if l1 is parallel to l2 or is equal to l2, for all l1,l2 ∈ L.

Exercise 5.3.10. For each of the following partitions, describe the corresponding

origin (the origin is considered a “degenerate” circle).

(4) Let W be the partition of R defined by W = {[n,n+2) | n is an even integer}.

(2) Let γ : X → X/≍ be the canonical map. Let j: h(X) → Y be the inclusion map. Prove that there is a unique bijective function ˆh: X/≍ → h(X) such that h = j ◦ˆh◦γ. This last condition is represented by the following commutative diagram (as discussed in Section 4.3).

f

Observe that γ is surjective (because ≍ is reflexive), that ˆh is bijective and that j is injective. Hence any function can be written as a composition of a

surjective function, a bijective function and an injective function.

(4) Suppose that A is a finite set. Express |R (A)| and |SA| in terms of |A|. Do R (A) and SA have the same number of elements? Use Example 3.2.9 (2) and

Example 3.3.10 (3).

(1) Find a set B and an element D ∈ SB such that�(2) Suppose that A is finite and has at least two elements. Prove that each of�Φ set C and an element E ∈ SC such that� and� Ψ(E) is not transitive.
Ψ(D) is not reflexive. Find a

194 5 Relations

These are among the marvels that surpass the bounds of our imagination, and that must warn us how gravely one errs in trying to reason about infinites by using the same attributes that we apply to finites.

– Galileo Galilei (1564–1642)

Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-7127-2_6, © Springer Science+Business Media, LLC 2011

196 6 Finite Sets and Infinite Sets

The Peano Postulates for the natural numbers are based on the insight that the most fundamental property of the natural numbers is the ability to do proof by in-duction. Although it might seem that in order to do proof by induction it would also be necessary to be able to do other things with the natural numbers such as addition, it turns out that very little indeed is needed to do proof by induction. We need to have a set, denoted N; we need to have a distinguished element in the set, denoted 1, with which to start proof by induction; and we need to have a function from the set

6.2 Properties of the Natural Numbers 197

If we think intuitively of the function s in the Peano Postulates as taking each natural number to its successor, then Part (a) of the postulates says that 1 is the first number in N, because it is not the successor of anything.

Although it does not say in the Peano Postulates (Axiom 6.2.1) that the set N is unique, in fact that turns out to be true. See [Blo11, Exercise 1.2.8] for a proof. We can therefore make the following definition.

If one goes through the full development of the natural numbers starting from the Peano Postulates, the first major theorem one encounters is the one we now state. This theorem is used in particular in the definition of addition and multiplication of the natural numbers, and although we will not go over those definitions (see the reference given above), this theorem has many other applications in many parts of mathematics. This theorem, called Definition by Recursion, is in fact so valuable that it merits a section of its own, Section 6.4.

Definition by Recursion allows us to define functions with domain N by defining a function at 1, and then defining it at n+1 in terms of the definition of the function at n. It is important to recognize that recursion, while intimately related to induction, is not the same as induction (though it is sometimes mistakenly thought to be); the essential difference is that induction is used to prove statements about things that are already defined, whereas recursion is used to define things. The proof of the follow-ing theorem, which relies upon nothing but the Peano Postulates (Axiom 6.2.1), is somewhat tricky; see [Blo11, Theorem 2.5.5] for details.

f ............................................................................................................................ ............................................................................................................................ f

H ................................................................................................................ ............ H
k

1. If a+c = b+c, then a = b.

2. (a+b)+c = a+(b+c).

8. c(a+b) = ca+cb.

9. (ab)c = a(bc).

14. a < b if and only if a+c < b+c. b ≤ c, then a < c; if a ≤ b and b ≤ c, then a ≤ c.

15. a < b if and only if ac < bc.

20. a < b if and only if a+1 ≤ b.

21. If a < b, there is a unique p ∈ N such that a+ p = b.

The hard part of the proof of the Well-Ordering Principle (Theorem 6.2.5) is the

existence of the number m given in the statement of the theorem; the uniqueness is

that writing “...” alone is not rigorous, except when we give it a rigorous meaning

in specific cases, such as the following.

Exercise 6.2.4. [Used in Theorem 6.4.5.] Let H be a non-empty set, let a,b ∈ H and let p: H ×H → H be a function. Prove that there is a unique function g: N → H such that g(1) = a, that g(s(1)) = b and that g(s(s(n))) = p((g(n),g(s(n)))) for all

n ∈ N. The main step of the proof is to apply Definition by Recursion (Theorem 6.2.3)

Mathematical induction is a very useful method of proving certain types of state-ments that involve the natural numbers. It is quite distinct from the informal concept of “inductive reasoning,” which refers to the process of going from specific exam-ples to more general statements, and which is not restricted to mathematics. When we use the phrase “proof by induction” we will always refer to the mathematical sort of induction, not this other use of the term.

More precisely, mathematical induction is a method that can be used to prove able n that is a natural number. For example, we will shortly prove that the statement statements of the form (∀n ∈ N)(P(n)), where P(n) is a statement with a free vari-P(n) = “8n− 3nis divisible by 5” is true for all natural numbers n. How you origi-nally thought of trying to prove such a statement might have occurred in many ways, one of which is by playing around with various numerical examples, for example looking at 81− 31, at 82− 32, and at 83− 33, and then using informal “inductive reasoning” to conjecture that 8n− 3nis divisible by 5 for all natural numbers n. Such reasoning by example does not, of course, constitute a proof that this conjec-ture is really true. For such a proof we will use induction. The formal statement of this method, usually referred to as the Principle of Mathematical Induction, ab-breviated PMI, is stated below. (For a more general look at proof by induction, see [End72, Section 1.2].)
The intuitive notion of PMI is that to show that a statement about the natural numbers is true for all natural numbers, it is sufficient to show that the statement holds for n = 1, and that if it holds for n = 1 then it holds for n = 2, and that if it holds for n = 2 then it holds for n = 3, continuing ad infinitum. Of course, we cannot prove infinitely many such implications, but it is sufficient to prove that the statement is true for n = 1, and that for an arbitrary natural number n, if the statement holds for n then it holds for n+1.

Then G = N.

It is important to make use of Part (b) of PMI precisely as it is written. This part

G = {n ∈ N | 8n−3nis divisible by 5}.

We will use PMI to show that G = N, and it will then follow that 8n−3nis divisible by 5 for all n ∈ N, which is what we need to prove. First, we observe that G ⊆ N by definition, and hence PMI is applicable. To use PMI, we need to show two things,

Because n and k are integers, then 8n+ 3k is an integer, and hence 8n+1− 3n+1is divisible by 5. It follows that n+1 ∈ G. We have therefore proved that Part (b) of the statement of PMI holds. PMI now implies that G = N, and the result is proved. ⊓⊔

The strategy used in the proof of Proposition 6.3.2 is quite typical. We first de-

all n ∈ N. The formal way to proceed would be to define the set G to be those natu-ral numbers for which P(n) is satisfied, and then verify that G = N by showing that

1 ∈ G, and that n ∈ G implies n+1 ∈ G, for all n ∈ N. The less cumbersome, but just as valid, way of proceeding is to state that we are trying to prove that the statement

Proposition 6.3.3. If n ∈ N, then
1+2+···+n =n(n+1) . (6.3.1)

Proof. We prove the result by induction on n. First, suppose that n = 1. Then 1 + 2+···+n = 1, andn(n+1) =1·(1+1) 2 = 1. Therefore Equation 6.3.1 holds for the case n = 1. Now let n ∈ N. Suppose that Equation 6.3.1 holds for this n. It then follows from that equation that

2

This last expression is precisely the right-hand side of Equation 6.3.1 with n + 1 replacing n. Hence we have proved the inductive step. Therefore Equation 6.3.1 holds for all n ∈ N. ⊓⊔ It is important to observe that proof by induction shows only that a statement of the form P(n) is true for each n ∈ N. We cannot prove that P(n) is true for n =∞, whatever this might mean. A proof by induction does show that P(n) holds for infinitely many numbers n, but each such number is a finite number. We do not consider ∞ to be a natural number (or any other type of real number), and so PMI does not apply to it.

the same color,” is true for all n ∈ N. Because there are only finitely many horses in the world, it will then follow that all existing horses have the same color. First,

suppose that n = 1. It is certainly true that for any set of one horse, all the horses

horses H1,...,Hn all have the same color, it follows that H1,...,Hn+1 all have the

same color. We have therefore proved the inductive step. Hence all horses have the

application of Theorem 4.5.4, combined with basic facts about the sizes of products

of finite sets and the sizes of power sets of finite sets, which are proved in Sections 7.6

Variant 2 and Variant 3, respectively, using the abbreviations PMI-V1, PMI-V2 and

PMI-V3. All three variants work similarly to PMI, in that they all have two parts, the

Theorem 6.3.6 (Principle of Mathematical Induction—Variant 1). Let G ⊆ N, and let k0 ∈ N. Suppose that

a. k0 ∈ G;
b. if n ∈ {k0,...} and n ∈ G, then n+1 ∈ G.

on assume that k0 ̸= 1. By Theorem 6.2.4 (12) (21) there is some b ∈ N such that b+1 = k0.

Let G′= {1,...,b} ∪ G. We will show that G′= N. It will then follow that {1,...,b} ∪ G = N, and hence that {k0,...} ⊆ G by using Exercise 6.2.3 and Ex-ercise 3.3.10.

might be the case that the set G contains numbers less than k0, but we cannot deduce Observe that in PMI-V1 we do not deduce that G = N, only that {k0,...} ⊆ G. It

that from the statement of PMI-V1. The following proof is an example of the use

Proof. We prove the result by induction on n, making use of PMI-V1 with k0 = 5. First, suppose that n = 5. Then 45= 1024 > 625 = 54. Hence the desired result holds when n = 5. Now suppose that the result holds for some n ∈ N such that n ≥ 5, which means that 4n> n4for this n. We start with three preliminary observations, which

are
4n> n4> n2≥ 5n = 4n+n > 4n+1, and
4n> n4≥ 52n2> 6n2,
and
4n> n4> 4n3.

Theorem 6.3.8 (Principle of Mathematical Induction—Variant 2). Let G ⊆ N. Suppose that

a. 1 ∈ G;
b. if n ∈ N and {1,...,n} ⊆ G, then n+1 ∈ G. Then G = N.

Proof. Left to the reader in Exercise 6.3.13. ⊓⊔

6.3 Mathematical Induction 209

We conclude this section with the following somewhat technical theorem about functions between sets of the form {1,...,n}; we will need this theorem when we discuss properties of finite sets in Section 6.6.

Theorem 6.3.11. Let n,k ∈ N.

(3). First, suppose that f is bijective. We prove the result by induction on k, where for each k we will assume that n is arbitrary. Suppose that k = 1. Then {1,...,k} = {1}. If p: {1,...,n} → {1,...,k} is a bijective function, then {1,...,n} must also have one element, which implies that n = 1. Hence n = k.

Now suppose that the result is true for some k∈N. Let h: {1,...,n}→{1,...,k+1} be a function. Suppose that h is bijective. We know that k+1 > k ≥ 1. It follows that