MA 120-50 FA 05 Supplementary Notes
MA 120 Notes
Table of Contents
Section Page
Introduction to the course 2
Chapter 1 Logic………………………………………………………………………5
1.1 Introduction to logic, propositions, connectives, truth tables 5
1.2 Our first proofs 13
1.3 Proof by cases and contradiction 24
1.4 Open Sentences, Free and Bound Variables, and Quantifiers 31
1.5 Negations and Contrapositives 39
Chapter 2 Introduction to Number Theory………………………………………..43
2.1 Even and Odd Integers 43
2.2 “Divides” 48
2.3 Modular arithmetic 51
2.4 Congruence mod n 53
2.5 Getting Ready for Induction 55
2.6 The Square Root Is Not A Fraction (“[pic] is irrational”) 56
2.7 Proofs using Mathematical Induction 57
Chapter 3 Set Theory………………………………………………………………..60
3.1 Introduction to Set Theory 60
3.2 Finishing set theory proofs 65
3.3 Using Sets Defined by Set-Description Notation 76
3.4 Collections of sets subscripted by {1, 2, 3, … n} 82
3.5 Ordered Pairs, Cartesian Product, Power Set 85
Chapter 4 Combinatorics……………………………………………………………93
4.1 Bit Strings and Recursive Definitions 93
4.2 Factfunction 97
4.3 The Binomial Theorem 101
Chapter 5 Functions and Permutations…………………………………………...104
5.1 Relations 104
5.2 Functions 106
5.3 Functions: one-to-one, onto, bijections 108
5.4 Proofs of one-to-one and onto 112
5.5 Composition of functions, inverses 115
5.6 Image and pre-image 116
5.7 Permutations 125
5.8 Transpositions and the order of a permutation 129
5.9 Odd and Even Permutations 130
Chapter 6 Graph Theory…………………………………………………………..133
6.1 Graphs 133
6.2 Walks, paths, connected graphs, Euler circuits 141
6.3 Planar graphs, bipartite graphs, Euler numbers 146
6.4 Trees and Graph Coloring 150
Appendix……………………………………………………………………………153
Introduction to the course
“Mathematical ideas are the building blocks of mathematical thought. Every mathematical concept is an idea; every proof is build around an idea. The mathematical idea is an answer to the question, ‘What is going on here?’ The practice of mathematics involves the interaction between ideas and logical rigor.” – William Byers, How Mathematicians Think
Mathematics appears to be the most stable form of human knowledge. The scientific beliefs of the ancient Greeks have long ago been discarded as superstitions, not science. Yet mathematical discoveries of the ancient Greeks (and even before) are still viewed as valuable today. This is perhaps due, in part, to the nature of the subject matter, but it is due also, at least in part, to the way we determine whether a mathematical statement is true or false.
In your other mathematics courses (starting with precalculus and calculus), you will encounter a wide range of mathematical ideas. However, to be able to make effective use of these ideas, you need to understand how we decide whether proposed relationships among these ideas are correct or not. In this course, you will begin your systematic study of how to decide, for a given mathematical statement, whether it is true or false. You will also begin to learn how to develop such a statement on your own, and how to use mathematical language sufficiently clearly that others can determine for themselves whether mathematical statements you make are correct. Your work on these skills will continue through your years as a mathematics major.
At many universities, students take a course somewhat similar to this one, but usually it is taken in the second semester of the sophomore year, or in the junior year. One reason for this is that, at many universities, students are enouraged to wait for declaring a major until that stage. In any case, because it is unusual to have freshmen taking an Introduction to Mathematical Reasoning course, most textbooks written for such a course (including the one we recommend as an optional purchase, How to Prove It, by Daniel Velleman) assume a broader mathematical background than that of most freshmen. Thus we have written our own notes that serve as the main text for MA 120.
Most mathematical statements are of the form “For every [some kind of mathematical object], if [something is true of that type of object] then [something else is also true of them]. An example (not using mathematical objects) of this kind of statement is “Every student in this class is at least twenty years old.” It doesn’t quite sound like the type of statement we want to discuss, but let’s rephrase it: “For every person, if that person is in this class, then that person is at least twenty years old.” This is probably a false statement: there are freshmen in this class, and many freshmen are eighteen or nineteen. To show that a “for every…” statement is false, all you have to do is fine ONE “counter-example” – that is, in this case, one student in the class who is not at least twenty years old. So very often, if a mathematical statement is false, it is easy to show it. But NOT always. Sometimes the “counterexample” is a very large number, or other hard-to-find object. For example, “for every integer n, there is no integer m such that m2 = 1141n2 + 1” is a false statement. However, you are unlikely to find an integer n for which such an m exists, since the first such n is larger than 1025 (in particular, it’s 30,693,385,322,765,657,197,397,208). (See P. Davis, “Are there Coincidences in Mathematics,” American Mathematical Monthly 88 (1981), p. 313)
It is much harder to show that a mathematical statement of this kind is true. It’s probably true that “Every student in this class is at least fifteen years old.” But to show it, we’d have to find out the age of every single student in this class, and compare all those numbers to fifteen. That’s not such a big task – the class is capped at twenty students – but it’s often quite a bit more work than just finding one. Further, most of these kinds of mathematical objects have an infinite other objects of the same kind: there are infinitely many counting numbers, rational numbers, real numbers, functions, graphs, and so on. You cannot possibly check every one individually. This is why proof will be so crucial.
Throughout this course, we will use N to stand for the set of all natural numbers (the numbers we count with: 1, 2, 3, …), Z to stand for the set of all integers (natural numbers, additive inverses (negatives) of natural numbers, and 0), Q to stand for the set of all rational numbers (ratios of integers, except those with 0 in the denominator), R to stand for the set of all real numbers, and C to stand for the set of all complex numbers.
Assignment:
Objective: Figure out the meaning of each statement and then determine whether it is true or false. Try to justify your answers by a convincing argument, one that would convince a hardened skeptic. Work with pencil and paper and keep notes. (We will return to many of these problems in the coming weeks.)
1. If x is an integer, then x2 > x.
2. If x is a real number, then x2 > x.
3. If x is an integer, then x3 > x.
4. For all integers x, y, and z, if x + y is odd and y + z is even, then x + z is odd.
5. For all rational numbers x and y, x + y is rational.
6. For all rational numbers x and y, xy is rational.
7. For all irrational numbers (numbers that are real but not rational) x and y, xy is irrational.
8. For all rational numbers x, y, and z, if x + y is an integer and y + z is an integer, then x + z is an integer
9. For all real numbers x, x3 = x.
10. There exists a real number x such that x3 = x.
11. [pic] is an irrational number.
12. If x is an even integer, then x2 is an even integer.
13. If x is an integer, then x is even or x is odd.
14. If x is an integer, then x cannot be both even and odd.
15. There are infinitely many prime numbers.
16. For any natural number x there exists a natural number y such that y2 = x.
17. For any natural number x there exists a positive real number y such that y2 = x.
18. For any positive real number x there exists a positive real number y such that y2 = x.
19. If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
20. If xy is an even integer, then x is an even integer or y is an even integer.
21. All nonnegative integers of the form n2 + n + 11 are prime.
22. All nonnegative integers of the form n2 + n + 41 are prime.
23. There are odd integers x, y, and z such that x2 + y2 = z2.
24. For all integers x, y, and z, if y is not evenly divisible by x and z is not evenly divisible by x, then yz is not evenly divisible by x.
Chapter 1: Logic
Section 1.1 Introduction to logic, propositions, connectives, truth tables
The following notes are from Professor Smith; copyright Thomas Smith, 2004, all rights reserved.
Logic and Reasoning
A proposition is a statement that has exactly one logical value: true or false.
Example: “John is divisible by 7” is a statement but not a proposition. This statement is neither true nor false: it is meaningless. John (presumably a person) is not the kind of object that can be divisible by 7. Similarly, “23 has brown hair” is not a proposition. Nor is “When will you eat dinner tonight?” – it’s a question, and cannot be true or false. However, “There are currently 20 students in MA 120-01” is a proposition: you may not know whether it is true or false, but at the time the statement is made, it is either true or false.
Example: “Three is an even integer” is definitely a proposition, a false one.
Example: “x is an even integer” is not a proposition. Why is that?
We will represent propositions by capital letters. For example: P : = 3 is an even integer. This makes the proposition letter P stand for “3 is an even integer.”
Further we will represent the logical value of false by 0 and true by 1. In the case where P : = 3 is an even integer, then we would say P’s logical value is 0.
Algebra of Propositions
There are several ways to combine propositions to form new propositions. If P and Q represent propositions, then ~P, P ( Q, P ( Q, P ( Q and P ( Q each represent a new proposition whose logical value depends upon the logical value of P and Q. The symbols ~, (, (, ( and ( are called connectives, and each is discussed below the table. We introduce truth tables to explain how the logical value of each of the new propositions depends on the logical value of P and Q.
|P |Q |~P |P ( Q |P ( Q |P ( Q |P ( Q |
|0 |0 |1 |0 |0 |1 |1 |
|0 |1 |1 |1 |0 |1 |0 |
|1 |0 |0 |1 |0 |0 |0 |
|1 |1 |0 |1 |1 |1 |1 |
Explanation of ~: ~P (read “not P”) is a proposition whose logical value is the opposite of the value of P. We need to be a little careful in relating P and ~P to our usual English.
P : = 3 is an even integer and ~P : = 3 is not an even integer works fine.
P : = 1/2 is an even integer and ~P : = 1/2 is not an even integer leaves much to be desired.
One reason there is a problem there is “3 is an even integer” is really a conjunction: it is saying “3 is an integer and 3 is even.” There are two ways this could be false: 3 could not be an integer (as is the case with 1/2), or 3 could not be even (as happens to be the case). But this isn’t quite the whole story. When we say of something that it is an even integer, we often are assuming that our whole domain of discourse is the set of integers, and that we’re not even discussing non-integers such as 1/2. In this context, “3 is an even integer” and “3 is even” are the same proposition, and it is not treated as a conjunction. And in this context, “1/2 is an even integer” is meaningless, because 1/2 isn’t in the domain of discourse.
Symbolically, there is a way of telling what the context is, which we’ll introduce in section 1.4.
One big problem students have learning mathematics is that mathematicians tend to talk in context, and often forget that students do not necessarily know what the context is. In this course, we will try to point out when we are doing this, and how to tell which context we are working in. But sometimes we will forget. Please ask, if the context is not clear.
Negating propositions can be quite complicated, and we will discuss this more in section 1.5.
Explanation of (: The connective ( has the formal name “disjunction” and is closely related to the English word “or”. The table says that P ( Q (read “P or Q”) is true as long as at least one of the input propositions is true. “2 is an odd integer or 3 is an even integer” is a false proposition since both its parts are false. The use of “or” in English is somewhat different from its use in mathematics. In English, “or” usually means one, the other, but not both. This is called the “exclusive or.” In mathematics, for reasons you’ll gradually see as the semester goes on, “or” is “inclusive.” An “or” proposition is true when either one of the “disjuncts” is true, but it is also true when both are true.
There are times we do that in English: when the waitress asks if you would like sugar or cream with your coffee, she does mean that you can have both, or just sugar, or just cream (or, in fact, neither). But if she asks if you would like a soda or iced tea, she means that you should choose just one.
Explanation of (: The connective ( has the formal name “ conjunction” and is closely related to the English word “and”. Again, reading from the table P ( Q (read “P and Q”) is false most of the time. It is true only if both parts are true.
“2 is an even integer and 3 is an odd integer” is certainly a true statement.
Explanation of (: P ( Q, called “implication” and is related to the English “if P then Q” as in “If the sun is shining then Joe is warm” where P : = the sun is shining and Q : = Joe is warm. There are many, many ways to read P ( Q. It can read “P implies Q”, “P only if Q”, “P is sufficient for Q”, “Q is necessary for P”, “whenever P then Q”, and even “Q, unless not P.” Thus, a second English translation of the particular case here is “The sun is shining implies Joe is warm.” P is called the antecedent in P ( Q, and Q is called the consequent. Note that it is difficult to have P ( Q be false. The only way for that to happen is for P = 1 and Q = 0.
Again, this is different from its use in English. In English, there is an implied connection between the antecedent and the consequent. Many people would say that, when the sun is not shining and Joe is not warm, that “If the sun is shining then Joe is warm” is false. But in mathematics, you can never make the implication false by making the antecedent false. Again, you will see, as the semester progresses, why this is needed in mathematics. Also, in English we often say “if P then Q” when we mean “P if and only if Q.” For example, when a parent says to a child “If you eat your vegetables, you can have dessert”, they really mean BOTH that if you do eat your vegetables, you will get dessert, AND that if you do NOT eat your vegetables, you wil not get dessert. In mathematics we symbolize that by P ( Q, not by P ( Q.
Suppose P : = you study and Q : = you pass. What English statement does P ( Q represent? Suppose you don’t study and yet manage to pass. What is the logical value of the sentence P ( Q?
Explanation of (: P ( Q is referred to as a “biconditional” and is simple to explain. From the table we can see, that it means that both P and Q are of the same value: both true, or both false. It’s generally read “P if and only if Q.”
2 is an odd integer ( 3 is an even integer is a true statement.
|Symbol |Formal Name |English Approximates |Keys |
|~P |Negation |not P | |
|P ( Q |Disjunction |P or Q |Hard to make 0. |
|P ( Q |Conjunction |P and Q |Hard to make 1 |
|P ( Q |Implication |if P then Q |Hard to make 0 |
| | |whenever P then Q | |
| | |P is sufficient to guarantee Q | |
|P ( Q |Bi-conditional |P has the same value as Q | |
| | |P if and only if Q | |
How to construct a truth table for more complicated logical statements.
Find the truth table for (P ( Q) ( (P ( ~Q).
The truth table will have six columns; one for each variable and each connective.
|P |Q |P ( Q |~Q |P ( ~Q |(P ( Q) ( (P ( ~Q) |
|0 |0 | | | | |
|0 |1 | | | | |
|1 |0 | | | | |
|1 |1 | | | | |
The columns under the variables are the input values. They start with all 0s in the first row and have all 1s in the last row. It is simply counting in base 2. We will determine the order of the columns for (P ( Q) ( (P ( ~Q). In general we work from left to right, but we need to be sensitive to parentheses. The 3rd column is for P ( Q. But the 4th column is for ~Q. The ( cannot be determined until (P ( ~Q) is known and the ( cannot be determined until ~Q is known.
To verify a statement with three variables, we’ll need eight rows (in addition to the title row). For example, consider the truth table for ((P ( Q) ( (~Q ( R)) ( (P ( R), below.
|P |Q |R | | | | |
|0 |0 |0 | | | | |
|0 |0 |1 | | | | |
|0 |1 |0 | | | | |
|0 |1 |1 | | | | |
|1 |0 |0 | | | | |
|1 |0 |1 | | | | |
|1 |1 |0 | | | | |
|1 |1 |1 | | | | |
4. Determine the truth table for the statement (P ( R) ( (Q ( ~R)
|P |Q |R | | | | |
|0 |0 |0 | | | | |
|0 |0 |1 | | | | |
|0 |1 |0 | | | | |
|0 |1 |1 | | | | |
|1 |0 |0 | | | | |
|1 |0 |1 | | | | |
|1 |1 |0 | | | | |
|1 |1 |1 | | | | |
5. Use truth tables to determine which of the following statements are equivalent to which others: (a) ~P ( ~Q, (b) ~(P ( Q), (c) ~P ( ~Q, (d) ~(P ( Q). Describe in English what this tells you.
6. Show that two statements, A and B, are equivalent if and only if A ( B is a tautology.
7. Determine, using truth tables, which of the following statements are tautologies:
a) (P ( (Q ( R)) ( ((P ( Q) ( (P ( R))
b) (P ( (Q ( R)) ( ((P ( Q) ( (P ( R))
c) ~(P ( Q) ( (~P ( ~Q)
d) ((P ( Q) ( (P ( ~Q)) ( ~P
e) ((P ( Q) ( (P ( ~Q)) ( P
f) (P ( (Q ( R)) ( ((~Q ( ~R) ( ~P)
g) (P ( Q) ( (Q ( P)
8. Assume the universe of discourse is the set of all integers. Let E stand for “x is even,” O stand for “x is odd,” P stand for “x is prime,” G stand for “x is greater than 2,” and Z stand for “x = 0.” Translate the following sentences into English, first directly translating word for word, and then a second version that is more fluid English. Not all of these sentences are true for every x, but some are, and some are true for some values of x. Say, briefly, why each is or is not true, and whether for specific values or for all values.
(a) E ( ~O (d) ~(E ( P ( ~G)
(b) (E ( G) ( ~P (e) (E ( ~G) ( O
(c) Z ( ~(E ( O) (f) Z ( E ( P
9. Let S stand for “Sal is in this class” and E stand for “Evelyn is in this class.” Translate each of the following complex sentences into symbolic form.
a. Both Sal and Evelyn are in this class.
b. Neither Sal nor Evelyn are in this class.
c. Sal and Evelyn are both not in this class.
d. Exactly one of Sal and Evelyn is in this class.
e. Sal and Evelyn are not both in this class.
f. Either Sal is not in this class or Evelyn is not in this class.
g. If Sal is in this class, then Evelyn isn’t.
10. (a) Translate the following argument into symbolic form. Say what each of your proposition letters stands for. (b) Then, using a truth table, determine whether the conclusion necessarily follows from the hypotheses: that is, whenever all of the hypotheses are true, is the conclusion always true?
Hypotheses:
If today is not Sunday, I don’t work in my garden.
It is not Sunday or I go to my office.
I work in my garden.
Conclusion:Therefore, I go to my office.
11. Translate each of the following complex sentences into symbolic form by assigning a distinct variable letter to each substatement. In each case, first say what each letter stands for, and then write the translated statement. If you can use a logical connective for part of a substatement, it should NOT be part of that substatement.
a) If John watches TV, then he neither does his homework nor gets any exercise.
b) If n is divisible by 6, then n is divisible by 3 and n is divisible by 2.
c) If you come to class late or need to leave early, you should sit near the door.
d) If n is divisible by ab, then n is divisible by a or n is divisible by b.
e) If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
f) If y is not evenly divisible by x and z is not evenly divisible by x, then yz is not evenly divisible by x.
g) If you get an A on the next exam, you can skip one homework assignment or you can skip one class, unless you want an A for the course.
12. How many rows would a truth table for a statement with 5 different letters need to have? Why?
13. A Wason card is a card that has a number on one side, a letter on the other, and obeys the following rule: if there is a vowel on one side, there is an even number on the other. You have before you four cards, and are told that they each have a number on one side and a letter on the other. On one of them, you see an E, on the second, a K, on the third, a 4, and on the fourth, a 7. Which of these cards MUST you examine the other side of, to determine whether they are ALL Wason cards? Explain.
14. ↓ is often used to mean “nor”: that is, P ↓ Q means “neither P nor Q is true”.
(a) Write the truth table for P ↓ Q.
(b) Find an expression involving (some of) ~, (, (, (, and ( that is equivalent to P ↓ Q, and, by using truth tables, show it is equivalent.
15. The symbol | is often used to mean “not and”, often abbreviated “nand”: that is, P | Q means “not both P and Q are true”.
(a) Write the truth table for P | Q.
(b) Find an expression involving (some of) ~, (, (, (, and ( that is equivalent to P | Q, and, by using truth tables, show it is equivalent.
16. Find an expression involving (some of) ~, (, (, (, and ( that has, as truth table,
|P |Q |? |
|0 |0 |0 |
|0 |1 |1 |
|1 |0 |0 |
|1 |1 |0 |
17. Find an expression involving (some of) ~, (, (, (, and ( that has, as truth table,
|P |Q |? |
|0 |0 |0 |
|0 |1 |1 |
|1 |0 |1 |
|1 |1 |0 |
18. (a) Show that P ( Q is equivalent to ~(~P ( ~Q). Thus, we really don’t need both ( and (: we could always replace one by a more complicated expression using the other.
(b) For example, rewrite (P ( Q) ( R just using ~ and (.
(c) Translate ~(~P ( ~Q) into English: does it mean the same thing as P ( Q?
19. (a) Show that P ( Q is equivalent to ~P ( Q, and also to ~(P ( ~Q). Thus, we really don’t need (: we could always replace it by a more complicated expression using ( or (. (In fact, we will often do this, or the reverse, in our proofs.)
(b) For example, rewrite (P ( Q) ( R just using ~ and (; using just ~ and (.
(c) Translate ~P ( Q, and ~(P ( ~Q) into English: do they mean the same thing as
P ( Q?
20. (a) Show that you can represent each of P ( Q, P ( Q, and ~P using just “nand” (see problem 15 for the definition). Thus, since (by problem 19) we can replace ( by ( or (, we can replace all the logical connectives by more complicated expressions just using | (that is, “nand”).
(b) Using what you did in (a), find an expression that is equivalent to ~(P ( Q) ( R that only uses the connective | (that is, “nand”).
Section 1.2 Our first proofs
A proof in mathematics is an argument to convince others that a mathematical proposition is true. Hodgson and Morandi, in “Exploration, Explanation, Formalization: A Three-Step Approach to Proof,” suggest that in developing a proof, you should first convince yourself the statement is true (this they call “exploration”), then develop an informal argument that would convince a friend that the statement is true (“explanation”) and finally develop a water-tight argument that would convince an enemy that it is true (“formalization”). All of these are important skills for a mathematics major to develop. You need to be able to decide, independently of authorities such as teachers or books, whether you believe a mathematical statement is true, because whatever mathematical career you follow when you graduate, you will need to decide whether some mathematical statements are true or not. If you become a teacher, you will find that there are errors in the textbooks you use, and you will be the authority who must respond to a bright child who asks, “On page … it says one thing, and on page … it says the opposite: which is right?” If you work as a mathematician in industry, you will need to check the mathematics your non-mathematical colleagues want to use to be sure it is correct, and may need to develop new mathematics for them to use.
The department’s goals for its majors include that you develop “the ability to reason mathematically, both formally and intuitively.” By the time you leave here, we want you to develop “the ability to make mathematically sound conjectures,” “the ability to state mathematical definitions correctly,” and the ability “to develop and present a range of mathematical proofs.” (from the mathematics department mission statement and assessment plan). We will work on all three aspects of proof – exploration, explanation, and formalization – during this course, but we will primarily focus on the third. You will do more work on the first two in Linear Algebra (MA 221), Number Theory (MA 314), Modern Algebra (MA 410) and Real Analysis (MA 415), among others.
The reason we are primarily focusing on the formalization aspect is that you need to understand what mathematical language is saying to even begin to think about a mathematical statement effectively. Students’ initial response to a request to prove a proposition is often, “I just don’t know where to start!” You will start learning how to unpack mathematical language into statements that are in a form that makes it clear what must be proven. You will also learn how to work both forward from the hypotheses – the “givens” – in the statement and to work backwards from what you are trying to prove – your eventual conclusion – so that, in the end, you often only need to fill in a small gap with an understanding of the relation between them.
Mathematical propositions are quite complicated statements, and their quantifier structure (the little words such as “for all” or “there is”) makes them more complicated. We will therefore start our proofs with simpler ones that do not involve quantifiers, proofs that involve statements like those you worked with in the truth tables in the previous section. Then, in section 1.4 we will add quantifiers and a few additional axioms that will allow us to begin real mathematical proofs.
The following list of Axiom Schemas is for the most part a list of tautologies. Each is useful from time to time; among the most often used are Contrapositive and Alternate Implies. You should spend several minutes thinking about each of them, and why it is true. We will investigate how to use these rules to argue.
|Axiom Schemas | |Notation |
|Excluded Middle |P ( ~P |EM |
|Double negation |~(~P) ( P |~ ~ (line #) |
|Commutative |(P ( Q) ( (Q ( P) |Comm(line #) |
| |(P ( Q) ( (Q ( P) | |
|Associative |((P ( Q) ( R) ( (P ( (Q ( R)) |Assoc(line #) |
| |((P ( Q) ( R) ( (P ( (Q ( R)) | |
|Distributive |(P ( (Q ( R)) ( ((P ( Q) ( (P ( R)) |Dist(line #) |
| |(P ( (Q ( R)) ( ((P ( Q) ( (P ( R)) | |
|De Morgan |(~(P ( Q)) ( (~P ( ~Q) |DM(line #) |
| |(~(P ( Q)) ( (~P ( ~Q) | |
| |(~(P ( ~Q)) ( (~P ( Q) | |
|Contrapositive |(P ( Q) ( (~Q ( ~P) |Contra(line #) |
| |(~P ( Q) ( (~Q ( P) | |
| |(P ( ~Q) ( (Q ( ~P) | |
|Alternate Implies |(P ( Q) ( (~P ( Q) |AI(line #) |
| |(~P ( Q) ( ( P ( Q) | |
|Equivalence |(P ( Q) ( ((P ( Q) ( (Q ( P)) |Equiv(Line#) |
|Addition |P ( (P ( Q) |Add(line #) |
|Simplification |(P ( Q) ( P |Simp(line #) |
|Transitive |[(P ( Q) ( (Q ( R)] ( (P ( R) |Tran(line #, line #) |
|Detachment |P, (P ( Q) ( Q |Det(line #, line #) |
|Conjunction |P, Q ( (P ( Q) |Conj(line #, line #) |
|Implies |Given P, arrive at Q, conclude |Implies(line #, line # |
| |P ( Q | |
Rules of deduction
1. Any instance of any axiom scheme may be put on any line of a proof. That is, you are allowed to replace every occurrence of any letter in an axiom scheme by the same letter throughout, and the place the result on any line of a proof. For example, if you have, line 5 of a proof, ~Q ( (R ( ~P), you can take the axiom scheme (P ( Q) ( (~P ( Q) (Axiom AI), replace all the Ps with Q and all the Q’s with (R ( ~P). It then becomes the axiom (Q ( (R ( ~P)) ( (~Q ( (R ( ~P)). You can also write this on some line of a proof, and just say AI without any line number as the reason.
2. (use of () Any expression in a proof may be replaced by another that is equivalent to it, whether the expression is the whole line or simply part of a line. That is, if an expression V is on one line of a proof, and if one of the axiom schemes says V ( W, the expression with V replaced by W can be a future line of a proof. For example, if you have, line 5 of a proof, ~Q ( (R ( ~P), as above you can take the axiom scheme (P ( Q) ( (~P ( Q) (Axiom AI), replace all the Ps with Q and all the Q’s with (R ( ~P). It then becomes the axiom (Q ( (R ( ~P)) ( (~Q ( (R ( ~P)). Since the right side, ~Q ( (R ( ~P), is already on line 5 of your proof, on a later line you may write Q ( (R ( ~P), and, as your reason, write AI (5), saying that you’ve taken what was on line 5, and used the axiom Alternate Implies (AI) to replace it with an equivalent statement.
3. If the left side of an axiom scheme whose main connective is ( appears alone on any line of a proof (not inside another expression) – or, in the case of Detachment or Conjunction, each of the two statements on the left of side of ( appear alone on separate lines of a proof – the right side of the axiom scheme (the part after the () may be a future line of the proof. Important: With ( you are not allowed to go from the right side to the left side.
All the axioms are tautologies; that is, no matter what P, Q, and R are (even if they are more complicated statements), the axiom has the value true.
Example: Verify that De Morgan is a tautology: (~(P ( Q)) ( (~P ( ~Q)
|P |Q |P(Q |~(P ( Q) |~P |~Q |~P ( ~Q |(~(P ( Q)) ( (~P ( ~Q) |
|0 |0 | | | | | | |
|0 |1 | | | | | | |
|1 |0 | | | | | | |
|1 |1 | | | | | | |
So we see that if we know that ~(P ( Q) is true, then we know that ~P ( ~Q is also true.
Formal deduction problems:
Let’s try to put all this in context by an example of deductive reasoning.
Example: We are assured that the following three statements are true. What can we conclude?
Joe studies hard.
If Joe flunks English then Joe didn’t study hard.
Joe flunks English or Joe goes to Daytona on break.
We assign letters to the primitive statements:
P :=Joe studies hard.
Q := Joe flunks English.
R := Joe goes to Daytona
Our three true statements become P, Q ( ~P, Q ( R. What can we deduce?
Given: P, Q ( ~P, Q ( R.
Joe is off to Daytona.
Formal Logical Arguments
We want to concentrate on the formal deductive process as shown in the previous table.
Problem: Fill in the reasons for the following argument.
Given: P ( R, ~P ( S, (T ( ~Q) ( U, Q ( ~ S, T. Get U.
|1 |P ( R | |
|2 |~P ( S | |
|3 |(T ( ~Q) ( U | |
|4 |Q ( ~ S | |
|5 |T | |
|6 |P | |
|7 |P ( S | |
|8 |S ( ~Q | |
|9 |P ( ~Q | |
|10 |~Q | |
|11 |T ( ~Q | |
|12 |U | |
We can view De Morgan’s law as a way to change an ( statement to an ( statement.
Example: Rewrite the (~P ( (Q ( R)) ( P as a new statement that is logically equivalent and does not have an (.
1. Using AI, (~P ( (Q ( R)) ( P can be replaced by ~ (~P ( (Q ( R)) ( P.
2. Distributing the first ~ across the ( using De Morgan, we get:
(~ ~P ( ~(Q ( R)) ( P
3. Remove the double ~ next to the P using Double Negation:
(P ( ~(Q ( R)) ( P
Often we will use commutative and associative without mentioning them; it saves a few lines. However, it’s always correct to mention them if you wish; and you need to be careful that they only work on ( and (, not with (.
Given: P ( Q, S ( (T ( U), ~( Q ( T) Get: P
|1 |P ( Q | |
|2 |S ( (T ( U) | |
|3 |~( Q ( T) | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
The Bottom-UP Approach.
Example: Given: P, P ( (A ( B), B ( C, ~(A ( ~R), S ( B. Get R ( S.
We look at what we are trying to get: R ( S. If we could get an R, we could use addition to get R ( S and similarly if we could get an S. We scan the givens for an S and begin to think that is not the answer. S only appears once and it is on the wrong side of the “(”. So we concentrate on getting R. R is also mentioned once but we will need to unravel it to find out if it is useful. ~(A ( ~R) ( ~A ( R ( (A ( R). This is promising, but only if we can get an A. A ( B produce an A and we can get A ( B. Now we are ready to do the proof.
|1 |P | |
|2 |P ( (A ( B) | |
|3 |B ( C | |
|4 |~(A ( ~R) | |
|5 |S ( B | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 |R ( S | |
To prove a statement in the form of an implication (that is, something of the form A(B), one method is to assume the left side (A) as a given, and “get” B. You can then conclude A(B using “Implies”. Alternatively, you can show ~A(B and use AI to conclude A(B. To prove a statement involving ( (that is, something of the form A ( B) you may have to prove two separate statements: first prove A ( B, then prove B ( A. You can then conclude that A ( B using the rule “Equivalence.” (Other times, you can simply use, at each stage, only rules on the list of axioms above “Addition”, which all are themselves equivalences.) For example, let’s prove a version of a theorem called “idempotence”: P ( P ( P
|1 |P ( P |Given |
|2 |P |Simp (1) |
|3 |P ( P ( P |Implies (1-2) |
|4 |P |Given |
|5 |P ( P |Conj (4, 4) |
|6 |P ( P ( P |Implies (4 - 5) |
|7 |P ( P ( P |Equiv (3, 6) |
Assignment:
1. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given: R ( P, ~ R ( Q, ~P ( T, (T ( ~Q) ( U. Get U.
|1 |R ( P |Given |
|2 |~ R ( Q |Given |
|3 |~P ( T |Given |
|4 |(T ( ~Q) ( U |Given |
|5 |R |Simp (1) |
|6 |R ( ~Q |Contra (2) |
|7 |~Q |Det(5,6) |
|8 |~Q ( T |Add(7) |
|9 |T ( ~Q |Comm(8) |
|10 |U |Det(4,9) |
2. The proof below has two serious errors. First, find the errors and explain what’s wrong. Then write a correct proof.
Given P ( ~(S ( ~U), P ( Q, ~R ( S, ~U ( R, ~Q. Get R.
|1 |P ( ~(S ( ~U) |Given |
|2 |P ( Q |Given |
|3 |~R ( S |Given |
|4 |~U ( R |Given |
|5 |~Q |Given |
|6 |Q ( P |Comm (2) |
|7 |~Q ( P |AI (6) |
|8 |P |Det (5, 7) |
|9 |~(S ( ~U) |Det (1, 8) |
|10 |~S ( U |DM (9) |
|11 |U |Simp (10) |
|12 |U ( R |AI (4) |
|13 |R |Det (11, 12) |
3. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given ~P ( (S ( U), P ( Q, ~R ( S, ~(R ( P) . Get Q.
|1 |~P ( (S ( U) |Given |
|2 |P ( Q |Given |
|3 |~R ( S |Given |
|4 |~ (R ( P) |Given |
|5 |~ R ( ~P |DM (4) |
|6 |~R |Simp (5) |
|7 |S |Det (3, 6) |
|8 |S ( U |Add (7) |
|9 |~P |Det (1, 8) |
|10 |~P ( Q |AI (2) |
|11 |Q |Det (9, 10) |
4. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given (~U ( S) ( P, ~U ( Q, ~R ( S, ~(Q ( R). Get P.
|1 |(~U ( S) ( P |Given |
|2 |~U ( Q |Given |
|3 |~R ( S |Given |
|4 |~(Q ( R) |Given |
|5 |~Q ( ~R |DM (4) |
|6 |~Q |Simp (5) |
|7 |Q ( ~U |Comm (2) |
|8 |~Q ( ~U |AI (7) |
|9 |~U |Det (6, 8) |
|10 |~U ( S |Add (9) |
|11 |P |Det (1, 10) |
5. Given ~Q ( (P ( ~R), (Q ( P) ( S, R, get S.
|1 |~Q ( (P ( ~R) |Given |
|2 |(Q ( P) ( S |Given |
|3 |R |Given |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
6. Given: Q, P ( ~Q, R ( P. Get ~R.
|1 |Q |Given |
|2 |P ( ~Q |Given |
|3 |R ( P |Given |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
7. P ((P ( R), P ( Q. Get R
|1 |P ((P ( R) |Given |
|2 |P ( Q |Given |
|3 | | |
|4 | | |
|5 | | |
8. Given: P ( (Q ( R), Q (S, R ( U, (S ( U) ( W, ~P. Get W.
|1 |P ( (Q ( R) |Given |
|2 |Q (S |Given |
|3 |R ( U |Given |
|4 |(S ( U) ( W |Given |
|5 |~P |Given |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
9. Let P:= People breathe air, Q:= Monmouth University is in New Jersey, R:= It rains daily in the desert, S:= Dogs fly. Which of the following are true, which false: (a) P ( Q, (b) P ( R, (c) S ( Q, (d) R ( S, (e) Q ( R
10. Given: ~P ( ~Q, ~R, P ( S, Q ( R. Get S.
|1 |~P ( ~Q |Given |
|2 |~R |Given |
|3 |P ( S |Given |
|4 |Q ( R |Given |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
11. (a) Find a simpler expression that is equivalent to ~(~P ( ~Q), and show they are equivalent using truth tables.
(b) Prove, using our axioms, that your expression implies ~(~P ( ~Q).
(c) Prove, using our axioms, that ~(~P ( ~Q) implies your expression.
12. (a) Find a simpler expression that is equivalent to ~(~P ( Q) ( (P ( ~R), and show they are equivalent using truth tables.
(b) Prove, using our axioms, that your expression implies ~(~P ( Q) ( (P ( ~R).
(c) Prove, using our axioms, that ~(~P ( Q) ( (P ( ~R) implies your expression.
Section 1.3 Proof by cases and by contradiction
Proof by cases
Very often in mathematics, we argue by cases. We list all the possibilities that can occur, and prove that, in each of them, our conclusion is true. An example of this is the proof of problem 1 on page 3. To prove that, if x is an integer, then x2 > x, we look at three cases. If x is an integer, it must either be positve, or negative, or zero. Notice that x2 > x means (x2 > x) ( (x2 = x). So, by Addition, if we can prove either x2 > x or x2 = x, we’ve proven x2 > x.
Case 1: x is zero. That is, x = 0. Then x2 = 0 also. So, since 0 > 0, in this case, x2 > x.
Case 2: x is negative. That is, x < 0. On the other hand, the square of every (real) non-zero number is positive. Hence, x2 > 0. So x < 0 < x2 , that is, x2 > x, and thus x2 > x.
Case 3: x is positive. Therefore, since x is an integer, x > 1. Multiplying both sides by x (which is positive, and hence doesn’t change the direction of the inequality), we get x2 > x.
Since in all the possible cases for what an integer can be, we always find that x2 > x, we can conclude that x2 > x for all integers x.
In our simplified proofs, we will often use cases when we have several statements involving ( or (, especially if we don’t have a single letter among our givens. Whenever we’re given a statement with an ( as its major connective, such as P ( Q, we can turn it into cases by taking P as one case, and Q as the other. However, when we do an argument by cases it essentially takes twice as long, because we must arrive at our “get” in each case before going on to the next one. So when we can avoid cases, we do. The next example makes good use of a “case argument”.
Example: Given: P ( Q, ~Q ( R. Get P ( R.
Bottom up analysis leads us to two simple tacks. If we know P we get P ( R and, of course, if we know R we get P ( R. Looking at the givens. We see neither. We do see P ( Q. One of them is true, but we don’t know which one. Time for a case argument.
|1 |P ( Q |Given |
|2 |~Q ( R |Given |
|3 |Q ( R |AI(2) |
|I4 |P |Case I(1) |
|I5 |P ( R |Add(I4)(end case I) |
|II6 |Q |Case II(1) |
|II7 |R |Det(II6,3) |
|II8 |P ( R |Add(II7)(end case II) |
(Notice that we could have avoided cases by using AI and Transitive. But since many mathematical arguments are most easily done by cases, it’s worthwhile to get comfortable with this type of argument.)
As another example of proof by cases, we’ll prove the other version of idempotence,
P ( P ( P
|1 |P ( P |Given |
|2 |P |Case 1 (1) |
|3 |P ( P ( P |Implies (1-2) End case 1 |
|4 |P |Case 2 (1) |
|5 |P ( P ( P |Implies (1,4) End case 2 |
| | |(We’ve now shown that P ( P ( P is true and need to show the other direction.) |
|6 |P |Given |
|7 |P ( P |Add (6) |
|8 |P ( P ( P |Implies (6 - 7) |
|9 |P ( P ( P |Equiv (5, 8) |
Notice that, on line 2 we’re using the left P in line 1, while on line 4 we’ve used the right P (making it case 2). Thus in either case (whether P is true or P is true), we conclude P is true! Thus, by line 5 we’ve proven in all situations that P ( P ( P.
What we’ve been calling the “given” is usually called the hypotheses; what we’ve been calling the “get” is usually called the conclusion. In the statement P ( Q, P is the hypothesis, and Q is the conclusion.
Proof by contradiction
Another proof technique that is often helpful when you are stuck is proof by contradiction. We mention it last because students find it confusing initially. However, it is a useful method because it adds one more hypothesis and thus gives you more ammunition to work with. In a proof by contradiction, you assume all the hypotheses and the negation of the conclusion. This sounds bizarre: how can you assume that what you’re trying to prove is false, and how could this be helpful? Well, the idea is, if the hypotheses and the negation of the conclusion lead to a contradiction, then the hypotheses and the negation of the conclusion cannot all be true at once. Hence, if the hypotheses are true, the conclusion must also be true. Thus, the hypotheses imply the conclusion, exactly what we’re trying to show. Symbolically, say the hypotheses are H, the conclusion C, and the contradiction we get will be P ( ~P. What we show, therefore, is that (H ( ~C) ( (P ( ~P). However, P ( ~P is the negation (using DeMorgan and double negation) of Excluded Middle (EM), P ( ~P, which is an axiom. Using Contrapositive on (H ( ~C) ( (P ( ~P), we see it’s the equivalent of
~(P ( ~P) ( ~(H ( ~C). That is, it’s equivalent (using DeMorgan and double negation) to (P ( ~P) ( (~H ( C). Using Detachment, since P ( ~P is an axiom, we get ~H ( C, which, via AI, is H ( C, exactly what we’re trying to prove.
Let’s see an example:
Given ~(Q ( ~T), S ( T, ~S ( ~P, Q ( P, get T. To do a proof by contradiction, we add ~T to the givens and try to get a contradiction.
|Line # |Statement |Reason |
|1 |~(Q ( ~T) |Given |
|2 |S ( T |Given |
|3 |~S ( ~P |Given |
|4 |Q ( P |Given |
|5 |~T |Given (for proof by contradiction) |
|6 |~Q ( ~ ~T |DM (1) |
|7 |~ ~T ( ~Q |Comm (6) |
|8 |~T ( ~Q |AI (7) |
|9 |~Q |Det (5, 8) |
|10 |~T ( ~S |Contra (2) |
|11 |~S |Det (5,10) |
|12 |~P |Det (3,11) |
|13 |P ( Q |Comm (4) |
|14 |~P ( Q |AI (13) |
|15 |Q |Det (12, 14) |
|16 |Q ( ~Q |Conj (15, 9), contradiction |
|17 |T |Proof by contradiction |
Since adding the assumption of ~T led to a contradiction, we can conclude that T must follow from our givens.
We will not use a large number of proofs by contradiction in this course, as it’s a relatively sophisticated technique, but you are might like to try this method when you don’t seem to be getting anywhere from your givens – it is a good alternative to proof by cases.
Assignment:
1. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given (Q ( R) ( P, Q ( S, R ( U, ~(P ( ~W), (S ( U) ( W. Get W.
|1 |(Q ( R) ( P |Given |
|2 |Q ( S |Given |
|3 |R ( U |Given |
|4 |~(P ( ~W) |Given |
|5 |(S ( U) ( W |Given |
|6 |Q ( R |Case 1 (1) |
|7 |Q |Simp (6) |
|8 |S |Det(2, 7) |
|9 |R |Simp (6) |
|10 |U |Det (3, 9) end case 1 |
|11 |P |Case 2 (1) |
|12 |~P ( W |DM (4), ~ ~ |
|13 |P ( W |AI (12) |
|14 |W |Det (11, 13) end case 2 |
2. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given Q ( P, ~Q ( S, ~R ( ~S, ~(P ( ~R). Get R.
|1 |Q ( P |Given |
|2 |~Q ( S |Given |
|3 |~R ( ~S |Given |
|4 |~(P ( ~R) |Given |
|5 |Q |Case 1 (1) |
|6 |Q ( S |AI (2) |
|7 |S |Det (5, 6) |
|8 |S ( R |Contra (3) |
|9 |R |Det (7, 8) |
3. The proof below has a serious error. First, find the error and explain what’s wrong. Then write a correct proof.
Given P ( R, P ( (S ( T), ~P ( S, ~S ( ~R, R ( (~S ( T). Get T.
|1 |P ( R |Given |
|2 |P ( (S ( T) |Given |
|3 |~P ( S |Given |
|4 |~S ( ~R |Given |
|5 |R ( (~S ( T) |Given |
|6 |P |Case 1 (1) |
|7 |S ( T |Det (2, 6) |
|8 |P ( S |AI (3) |
|9 |S |Det (6, 8) |
|10 |T |Det (7, 9) end case 1 |
|11 |R |Case 2 (1) |
|12 |~S ( T |Det (5, 11) |
|13 |S ( T |AI (12) |
|14 |T |Det (9, 13) end case 2 |
4. What’s wrong with the following proof by contradiction:
Proof that if x and y are integers, and x + y = 9, then x ( 2 and y ( 8
|1 |x and y are integers |Given |
|2 |x + y = 9 |Given |
|3 |~( x ( 2 ( y ( 8) |Given (for proof by contradiction) |
|4 | x = 2 ( y = 8 | DM (3) |
|5 | x = 2 | Simp (4) |
|6 | y = 8 | Simp (4) |
|7 | x + y = 10 |Algebra (5, 6) |
|8 | (x + y = 9) ( (x + y = 10) | Conj (2,7), contradiction |
|9 | x ( 2 and y ( 8 | Proof by contradiction |
5. Given: ~P ( Q, ~P ( R, ~Q ( R. Get: R
|1 |~P ( Q |Given |
|2 |~P ( R |Given |
|3 |~Q ( R |Given |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
6. Given: P ( R, W ( ~R, Q ( W, ~P. Get ~Q.
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
| | | |
| | | |
| | | |
| | | |
7. Prove that ((P ( Q) ( (P ( ~Q)) ( (R ( ~R) is logically equivalent to one single letter. To figure out which letter it’s equivalent to, make a truth table, with this statement as its final column. That column will end up the same as one of the three letters, P, Q, or R. Therefore, it’s equivalent to that letter. Now, (a) prove that with the above proposition as the “given” you can “get” the single letter; and (b) prove that with the single letter as the “given” you can “get” the above proposition. For (b), you’ll need to use EM (Excluded Middle), which we’ve not yet used.
8. (a) Show that “if x is an integer, then x3 > x” is false.
(b) Explain, in terms of the hypothesis and the conclusion in the statement in (a), what you did to show that the statement was false.
9. Prove ~(P ( ~P). (Hint: Start with EM, and use ~ ~ (double negation).) this tells us that a statement and its negation can’t both be true. We will use this fact in proof by contradiction.
10. (a) Given P ( Q, get (P ( Q) ( (~P ( ~Q) (Hint: use Equiv, and then EITHER a proof by cases, or use Dist, and then # 9.)
(b) Given (P ( Q) ( (~P ( ~Q), get P ( Q
11. Consider the argument from problem 10 in section 1.1 of these notes. Give a proof, in our style, that “gets” the conclusion, taking the hypotheses as “givens”.
12. Prove that P ( (Q ( R) is equivalent to a proposition in which the symbol ( does not occur. That is, find another proposition, call it X, that does not have any ( in it and then
(a) prove that, “given” P ( (Q ( R) you can “get” X
(b) “given” X you can “get” P ( (Q ( R).
13. Identify the hypotheses and conclusion in the following statements (they are statements 1, 4, 13, 19, and 20 from the introduction exercises).
(a) If x is an integer, then x2 > x.
(b) For all integers x, y, and z, if x + y is odd and y + z is even, then x + z is odd.
(c) If x is an integer, then x is even or x is odd.
(d) If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
(e) If xy is an even integer, then x is an even integer or y is an even integer.
Section 1.4 Open Sentences, Free and Bound Variables, and Quantifiers
Here is a proposition: 2 < (. Here is an open sentence: x < 3. Open sentences are also often called predicates. Notice that x < 3 is not a proposition because it doesn’t have a truth value. The x in “x < 3” is called a free variable because nothing restricts what it could be. We can turn x < 3 into a proposition in several ways. One is by substituting a specific value for x. For example, if we substitute 2 for x, we get “2 < 3”, which is a true statement. If we substitute 5 for x, we get “5 < 3”, which is a false statement.
In mathematics, an even more important way to turn an open sentence into a proposition is by using a quantifier. For example:
“For every natural number x, x < 3.”
The variable x is no longer free in this proposition, but bound by the quantifier “for every natural number x”. To determine whether the statement is true or false, we must mentally substitute every natural number in for x, and see if it is true for all of them. If it is, then the statement is true. Thus, in effect “for every…” is a big conjunction. If it fails for even one natural number, it is false. “For every natural number x, x < 3” is a proposition, and a false one to boot. Not all natural numbers are less than 3. On the other hand, “there is a natural number x such that x < 3” is also a proposition and this one is of course true. (For example, x could be 2.) Because mathematics investigates properties of systems of mathematical objects, being able to talk about all elements in such a system is very important.
The quantifiers in these propositions are the phrases “There is a natural number x such that” and “For every natural number x”. These quantifiers are used so often that there are symbols that are used to represent them. “(” is read “there is”. When put together with some statement P(x), to make (( x) P(x), it’s read “there is an x such that P(x).” It does not say that there is just one – there may be many, and it may even be true for everything. (This differs from standard English, where, if you say “there is a white dog” you imply that not all dogs are white.) If you add a set A which x must be a member of, you write it (( x ( A) P(x), which is read “there is an x in A, such that P(x).” (( x ( A) P(x) is actually shorthand for (( x) (x ( A ( P(x)), and there will be a need, occasionally to replace one form by the other; the reason would be “Definition of (( x ( A).” “(” is read “for every” or “for all”. (( x) P(x) is read “for every x, P(x)” or “for all x, P(x)” and (( x ( A) P(x) is read “for every x in A, P(x).” (( x ( A) P(x) is actually shorthand for (( x) (x ( A ( P(x)), and there will be a need, occasionally to replace one form by the other; the reason would be “Definition of (( x ( A).” ( is called the existential quantifier and ( is called the universal quantifier. You should only write (( x) P(x) rather than (( x ( A) P(x) (and similarly for the existential quantifier) if it is completely obvious to everyone who will be reading the statement what the context – the set A in which we’re working – is. You may wonder why we haven’t introduced a quantifier that says “there are no x such that….” This will be discussed in the next section (next class).
Some sets we’ll use as the set A above are N (standing for the natural numbers: 1, 2, 3, …), Z (standing for the integers: natural numbers, negatives of natural numbers, and 0), Q (standing for the rational numbers: ratios of integers except those with 0 in the denominator), R (standing for the real numbers), and C (standing for the complex numbers).
Generally, an open statement in mathematics – one with an unquantified (also called “free”) variable in it, such as “x is even or x is odd” is understood to be short for the statement with a universal quantifier, over some understood set. In this case,
“(( x ( Z)( x is even or x is odd).”
We can use more than one quantifier in a statement. They are read from left to right, as in ordinary English.
Example: Suppose that A = {1, 2, 3, 4}. Determine whether each of the following is true of false. ( x ( A is read as “x is a member of A”, or, more casually, “x is in A”.)
(( x ( A) x < 3. (This is read, “for all x in A, x is less than 3.” That is, here P(x) is “x < 3.”)
(( x ( A) x < 3. (This is read, “there is an x in A such that x is less than 3.”)
(( x ( A) x2 ( A.
(( x ( A) x2 ( A.
(( x ( A) (( y ( A) y < x. (“For all x in A, there is a y in A such that y is less than x.”)
(( x ( A) (( y ( A) y ( x.
If you have two quantifiers of the same kind, it doesn’t matter which goes first. For example, (( x ( N) (( y ( N)(x = y2) says there are two natural numbers, one of which is the square of the other. This is a true statement: for example, x could be 4 and y could be 2. (( y ( N) (( x ( N)(x = y2) says exactly the same thing. Similarly, you can interchange two universal quantifiers.
However, you cannot interchange a universal and existential quantifier without changing the meaning dramatically and, thus, usually the truth value. For example,
(( x ( N) (( y ( N)(x = y2) says that there is one natural number x that is the square of every natural number. It’s a very false statement. But interchange them:
(( y ( N) (( x ( N)(x = y2). Now it’s true: this statement says that for every natural number y, there is a natural number, x, which is its square. Of course, sometimes both ways of ordering the quantifiers may be true, or both may be false. But they always mean something different, in any case.
To do proofs involving quantifiers, we need some new rules of inference allowing us to simplify statements involving quantifiers so that they don’t have quantifiers any more, and to put quantifiers into statements that don’t have them. These rules are in general more complicated than the rules we’ve already seen. One rule that we want is that often we want to replace a long algebraic quantity by a new name; for example, we might want to shorten a proof by replace 2x2 – 4x + 1 by a single variable. As long as that variable
has not yet been used in the proof, this is OK; we call it “introduction of a new variable”.
If on one line of a proof you have a statement that starts with a universal quantifier, such as ((x) P(x), then at that stage in the proof, P is true for all values of x. Therefore, it’s legitimate to remove the quantifier and replace the x by anything that makes sense to think of applying P to. This rule is called Exemplification (Exem).
On the other hand, if you have a statement that starts with an existential quantifier, such as (( x) P(x), you know something has property P, but you don’t know which thing it is. So you can only replace the x by a new variable which hasn’t already been used; later, it may turn out that, from other things in the proof, that variable must also equal something else you’ve already used, but you don’t know that simply from (( x) P(x). This rule is called Witness (Witn), because the new variable is the witness to the existence of something with property P.
To be able to conclude that something is true for all possible values of a variable (usually such a conclusion will be an implication, such as “for all integers x, if x is odd then 2x is even”), you must start with a new variable letter that hasn’t previously been used, assume that it has the properties in the hypotheses, and show that it must then have the properties in the conclusion. You can then conclude that the statement is true for all x. Doing this is called Universal Generalization (UG). That is, if we let E(x) stand for “x is even,” and O(x) stand for “x is odd,” our proof would go something like:
|1 |O(x) |given |
|… |(some inbetween stuff: see section 2.1) | |
|n |E(2x) | |
|n + 1 |O(x) ( E(2x) |implies (1,n) |
|n + 2 |((x)( O(x) ( E(2x)) |UG(1,n+1) |
On the other hand, to be able to conclude that something is true for some value of a variable, you just have to have shown that it is true for any variable. That is, if at any stage in a proof you know P(x), you can conclude at the next step (( x) P(x); the rule allowing this is called Existential Quantification (EQ)
Thus, our six rules of quantifiers are:
|Axiom Schemas | |Notation |
|Introduction of new variable |Let c = (expression) * |NewVar |
|Generalized DeMorgan |~((x(A) P(x) ( ((x(A) (~P(x)) |GenDM(line #) |
| |~((x(A) P(x) ( ((x(A) (~P(x)) | |
|Exemplification |((x) P(x) ( P(a) |Exem(line #) |
|Witness |(( x) P(x) ( P(c) * |Witn(line #) |
|Universal Generalization |(P(y) ( Q(y)) ( |UG(line #, line#) |
| |((x) (P(x) ( Q(x)) ** | |
|Existential Quantification |P(a) ( (( x) P(x)*** |EQ (line #) |
*where c has not been used so far in the proof
** where you started with a new variable y, assumed P(y), and proved Q(y)
*** where a is any variable
Translating between English and mathematics is not easy: we will work on this all semester, and you will continue to work on this in your later courses. Here’s an example of translating and then proving that a deduction is correct using quantifiers.
Example: Determine whether the following is a valid argument:
Given: No basketball players are weak students.
Some mathematics majors are weak students.
Conclusion: Some mathematics majors are not basketball players.
First we translate this into quantifier language: “No basketball players are weak students” can be rewritten “If x is a basketball player, then x is not a weak student” OR to “x is not both a basketball player and a weak student.” To handle the argument in symbols, we’ll introduce three predicates, for each of the properties involved: Let B(x) stand for “x is a basketball player,” let W(x) stand for “x is a weak student”, and let M(x) stand for “x is a mathematics major.” Then “If x is a basketball player, then x is not a weak student” becomes, in symbols, with quantifiers, ((x)(B(x) ( ~ W(x)).
[Alternatively, “x is not both a basketball player and a weak student” would become ((x)~(B(x) ( W(x)). This statement could also be translated as ~ ((x)(B(x) ( W(x)) – there is no one who is both a basketball player and a weak student. All three of these statements are equivalent, using GenDM, AI and ~ ~)]
Similarly, our second hypothesis, “Some mathematics majors are weak students,” becomes ((x)(M(x) ( W(x)). And our purported conclusion, “Some mathematics majors are not basketball players,” becomes ((x)(M(x) ( ~B(x)). Now for the proof:
|1 |((x)(B(x) ( ~ W(x)) |Given |
|2 |((x)(M(x) ( W(x)) |Given |
|3 |M(a) ( W(a) |Witn (2) |
|4 |M(a) |Simp (3) |
|5 |W(a) |Simp (4) |
|6 |B(a) ( ~ W(a) |Exem (1) |
|7 |W(a) ( ~ B(a) |Contra (6) |
|8 |~ B(a) |Det (5, 7) |
|9 |M(a) ( ~B(a) |Conj(4, 8) |
|10 |((a)(M(a) ( ~B(a)) |EQ (9) |
Several comments about this proof. First, notice that the last line doesn’t appear to be quite the same as the desired conclusion, ((x)(M(x) ( ~B(x)). However, since the variable x here is simply saying, there’s something doing this, it doesn’t matter whether it’s called x or a. In fact, any time a variable is “bound” – within the scope of a quantifier – it’s legitimate to replace all occurrences of it that are bound with any other variable that is not being used otherwise free in the proof. Second, notice that we FIRST used “witness” for the second given, and later used Exem for the first given: you generally need to get rid of existential quantifiers via witness before getting rid of universal quantifiers, because you can’t use a letter that’s already in use with Witness, but you CAN use a letter already in use with Exem.
What do you do when the argument is NOT valid, to show it isn’t? Here’s an example:
Example: Determine whether the following is a valid argument:
Given: No basketball players are weak students.
Some mathematics majors are weak students.
Conclusion: Some basketball players are not mathematics majors.
We try the same approach – it’s only slightly different from the previous problem. In fact, the only difference is in the conclusion.
|1 |((x)(B(x) ( ~ W(x)) |Given |
|2 |((x)(M(x) ( W(x)) |Given |
|3 |M(a) ( W(a) |Witn (2) |
|4 |M(a) |Simp (3) |
|5 |W(a) |Simp (4) |
|6 |B(a) ( ~ W(a) |Exem (1) |
Oh dear! we’re stuck. We want to get B(a) ( ~ M(a). But we have M(a), not its negation! Also, there’s no way to get B(a) because we can’t get something from the left side of an implication. When you get stuck like this, it’s worth considering the possibility that it’s NOT a valid argument. And, in fact, it isn’t. Consider the following possible scenario: all members of the basketball team are math majors, and all are strong students. There are also some other math majors who are strong students, and a few who are weak students. (Some years at some schools, both the student with the highest GPA in the graduating class, AND the student with the lowest, are math majors!) Then our two hypotheses would be true, but our conclusion would be false. Hence, the argument is not valid. All you have to do to show that an argument is not valid is give a specific situation (such as the one described in this paragraph) in which the hypotheses (the “givens”) are true, but the conclusion is false.
Often, translating from English to mathematical symbols requires first rephrasing the English sentence into the standard connectives we use. For example, “There is a largest natural number,” a false statement, clearly will have an ( in it; so let’s start with ((x( N). But now what? How do we say it’s the largest? What that means is that, given any other natural number, x is larger than it. Rephrasing this some more, it says “there is a natural number x such that, for every other natural number y, x is larger than y.” But how do we include the “other” part. (Be careful: in English, we often ignore the fact that, if you’re talking about every natural number y, you need to include the possibility that x and y are the same number. For example, we often say something like “Dan is taller than everyone in the class” even if he is himself in the class. Strictly speaking (and in mathematics, we are strict about such things), the correct statement is “Dan is taller than everyone in the class except himself.”) So here’s our last reformulation before we turn the statement into symbols: “There is a natural number x such that for every natural number y, if x is not the same as y, then x > y.” This is easy to write symbolically:
((x( N) ((y( N)(x ( y ( x > y). Alternatively, ((x( N) ((y( N)(x = y ( x > y), usually written ((x( N) ((y( N)( x > y).
But, again, it’s a false statement. So what is its negation? In English, “There is no largest natural number,” a true statement. Symbolically, now that we have written the original symbolically, we just need a ~ in front of it: ~((x( N) ((y( N)(x ( y ( x > y).
Using Generalized DeMorgan, we can move the ~ inside, switching ( to ( and vice versa:
~((x( N) ((y( N)(x ( y ( x > y) ( ((x( N) ~((y( N)(x ( y ( x > y) (
((x( N) ((y( N)~(x ( y ( x > y) ( ((x( N) ((y( N)(x ( y (~ x > y)
(This last used the fact that the negation of a P ( Q statement is P (~Q, via AI and DM.)
Rewriting the last, we see that the negation of ((x( N) ((y( N)(x ( y ( x > y) is
((x( N) ((y( N)( x < y) (since if x is not less than y, and it’s not greater than y, it must be less than y). That is, if there is no largest natural number, then for every natural number x, there is a natural number y that is larger than x.
Assignment:
In problems 1 – 3, Let N = {1, 2, 3, 4, …}, A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 6, 8, 10}. Let P(x):= “x is a prime” and E(x) := “x is even”.
1. Determine if true or false; give reasons justifying each decision.
a. (( x ( N) P(x).
b. (( x ( N) (P(x) ( E(x))
c. (( x ( N) 5 < x.
d. (( x ( N) (P(x) ( E(x)).
2. Translate each of the following into ( or ( statements, using the symbols above.
a. Some primes are even.
b. All even numbers are greater than 1.
c. Even numbers are prime only if they are less than three.
d. There is no prime less than 3.
e. There is an even prime.
f. No primes bigger than 2 are even.
g. Every natural number is prime or even.
h. Some natural number is neither prime nor even.
i. Some members of B are greater than all members of A.
3. Determine whether each of the following is true or false, and give a reason to justify your answer:
a. (( y ( B) (y is 6).
b. (( x ( A) x2 is not in B.
c. (( x ( A) x > 4.
d. ~(( x ( A) x > 1
e. ~ (( x ( A) x2 =1.
f. (( x ( B) ~(x2 > 1)
g. (( x ( A) ~(x ( B ( x < 2).
h. (( x ( A) (( y ( B)(y > x)
i. (( x ( B) (( y ( A)(y > x)
j. (( y ( B) (( x ( A) (y > x)
k. (( x ( N) (( y ( N)(y > x)
l. (( y ( N) (( x ( N) (y > x)
4. Assume the universe of discourse is the set of all integers. Let E(x) stand for “x is even,” O(x) stand for “x is odd,” P(x) stand for “x is prime.” Translate the following sentences into English, first directly translating word for word, and then a second version that is more fluid English.
(a) ((x) (E(x) ( ~O(x)) (d) ~(( x) (E(x) ( P(x) ( x > 2)
(b) ((x) ((E(x) ( x > 2) ( ~P(x)) (e) ((x)(x > 2 ( ~ (E(x) ( P(x)))
(c) ((x)(x = 0 ( ~(E(x) ( O(x))) (f) ((x)(x = 0 ( E(x) ( P(x))
5. Assume the universe of discourse is the set N of all natural numbers. Translate each statement into English. Then decide whether the statement is true or false. Justify your answer with an example making the statement false, or a reason why it is true.
(a) ((x) (( y) (x = 2y) (d) (( x) ((y) (x = 2y)
(b) ((y) (( x) (x = 2y) (e) ((x) (( y) (x + y = 10)
(c) (( y) ((x) (x = 2y) (f) ((x)(x < 6 ( (( y) (y < x ( y < 5))
6. Assume the universe of discourse is the set Z of all integers. Translate each statement into English. Then decide whether the statement is true or false. Justify your answer with an example making the statement false, or a reason why it is true.
(a) ((x) (( y) (x = 2y) (d) (( x) ((y) (x = 2y)
(b) ((y) (( x) (x = 2y) (e) ((x) (( y) (x + y = 10)
(c) (( y) ((x) (x = 2y) (f) ((x)(x < 6 ( (( y) (y < x ( y < 5))
7. Assume the universe of discourse is the set Q of all rational numbers. Translate each statement into English. Then decide whether the statement is true or false. Justify your answer with an example making the statement false, or a reason why it is true.
(a) ((x) (( y) (x = 2y) (d) (( x) ((y) (x = 2y)
(b) ((y) (( x) (x = 2y) (e) ((x) (( y) (x + y = 10)
(c) (( y) ((x) (x = 2y) (f) ((x)(x < 6 ( (( y) (y < x ( y < 5))
8. (a) Translate into a statement using quantifiers: Every integer is smaller than some other integer.
(b) Translate into English, and decide whether it is true or false (and justify your answer):
(i) ((x ( N)((y (N)(x < y) (iv) ((x ( Z)((y (Z)(y2 < x)
(ii) ((x ( Z)((y (Z)(x < y) (v) ((x ( N)((y (Z)(y2 < x)
(iii) ((x ( N)((y (N)(y < x) (vi) ((x ( Z)((y (Z)(y < x)
9. Determine whether the following is a valid argument:
Given: All commuters are hard-working.
Some students are not commuters.
Conclusion: Some students are not hard-working.
10. Determine whether the following is a valid argument:
Given: All commuters are hard-working.
Some students are commuters.
Conclusion: Some students are hard-working.
11. Determine whether the following is a valid argument:
Given: No oranges are apples.
No lemons are oranges.
Conclusion: No apples are lemons.
Section 1.5 Negations and Contrapositives
The ability to negate statements is essential for doing mathematics. If a statement is true, you don’t need negation. But as soon as you want to claim that a statement is false, you do this by asserting its negation is true. So you need to know what its negation is. To negate a simple statement, you simply put in a “not” in the appropriate place for the English to read correctly. For example, to negate “5 is even”, you would say “5 is not even.” Often we have specific words for the negation. For example, rather than “5 is not even”, we can say “5 is odd.” However, you need to be careful in doing this to be sure that some case isn’t left out. For example, the negation of “6 is prime” is “6 is not prime.” Most numbers that are not prime are “composite” – that is, the product of other numbers not including 1. So you might be inclined to replace “6 is not prime” by “6 is composite.” However, 1 is neither prime nor composite. So to be sure you are including all possible cases, the correct equivalent to “6 is not prime” is “6 is composite or 6 = 1.” In the case of 6, of course, it is the first part of the “or” that is true. But if you replace 6 by x, you need both options. The negation of “x is prime” is “x is composite or x = 1.”
De Morgan tells you how to negate “(” and “( ” statements. Why is the negation of “x is prime or x is even” “x is not prime and x is not even” (more normally said, “x is neither prime nor even”)? Well, if x doesn’t satisfy either part of the “or”, which is needed for it to be false and its negation true, then it doesn’t satisfy being prime and it doesn’t satisfy being even.
What about negating an implication? Well, by AI, ~(P ( Q) ( ~(~P ( Q). The right-hand side, by De Morgan, is equivalent to ~ ~P ( ~Q, which, by ~ ~, is equivalent to
P ( ~Q. So to negate an implication, you take the hypothesis AND the negation of the conclusion. That is, the negation of P ( Q is P ( ~Q. That makes sense: the only way an implication is false is if the hypothesis is true but the conclusion is false.
This seems to be the most difficult negation for MA120 students to learn. We will work on this quite a lot over the next few weeks, because it is very important in determining mathematical truth. It’s so important because most mathematical statements are of the form ((x ( A)(P(x) ( Q(x)). So if you want to say that a statement of this form is false, you need to know how to negate it. See two paragraphs below for negating quantified statements: The ~ ((x ( A) (P(x) ( Q(x)) turns into (( x ( A) ~(P(x) ( Q(x)). Now you need to know how to simplify ~(P(x) ( Q(x)). By what we just said, it becomes
P(x) ( ~Q(x). Therefore, the negation of ((x ( A)(P(x) ( Q(x)) is
(( x ( A)(P(x) ( ~Q(x)). Thus, to show that a statement of the form
((x ( A)(P(x) ( Q(x)) is false, you have to FIND an x in A such that P(x) is true and Q(x) is false.
For example, consider the statement “Every odd integer greater than 1 is prime.” Letting O(x) stand for “x is an odd integer” and P(x) stand for “x is prime”, this statement becomes ((x ( Z)((O(x) ( x > 1) ( P(x)). But it’s a false statement. How can we see it’s false? Well, the negation of the statement is ((x ( Z)((O(x) ( x > 1) ( ~P(x)). So to show that “Every odd integer greater than 1 is prime” is false, we must show there is an integer x such that x is odd, x > 1, and x is not prime. Oh – now that we know what we have to show, it’s easy! 9 is odd, 9 > 1, and 9 is not prime (since 9 = 3 ( 3). So 9 is the x that shows that “Every odd integer greater than 1 is prime” is false.
There is a cook book process for negating quantified statements.
~((( x ( A) P(x)) ( (( x ( A) ~P(x)
~((( x ( A) P(x)) ( (( x ( A) ~P(x)
Because an existential quantifier is sort of an “or” over a lot of things (saying “there exists a professor in the department with a beard” means “Bodner has a beard, or Coyle has a beard or …”), and a universal quantifier is sort of an “and” over a lot of things, these rules are called “Generalized DeMorgan” laws (GenDM).
Every body in this class is rich ( (( x ( class) x is rich. The negation of this statement is ( x in class such that x is not rich ( Some one in the class is not rich. Notice that “Someone in the class is poor” in not quite accurate. “Not rich” is not the same as poor.
We’re now able to discuss why we don’t have a quantifier saying “there are no x’s such that P(x).” There isn’t a separate quantifier saying it because you can say this by negating “There are x’s such that P(x).” That is, ~((x) P(x). This, by GenDM, is the same as (( x) ~P(x). In other words, for every x, P(x) is false. That’s what we mean when we say there are no x’s such that P(x).
In the statement P ( Q, P is the hypothesis, and Q is the conclusion. In addition to negating the statement, as P ( ~Q, we can get three other statements that are related to this one. The converse interchanges hypothesis and conclusion: Q ( P. The inverse negates both hypothesis and conclusion: ~P ( ~Q. Neither the converse nor the inverse are equivalent to the original statement – a statement may be true and its inverse and converse false, or all may be true, or all may be false, or the inverse and converse may be true and the original false – they’re independent of each other. (However, the inverse and converse, by “contra”, are equivalent.)
The contrapositive does both: ~Q ( ~P. The contrapositive is equivalent to the original statement. That’s what the rule “contrapositive” (Contra) says! This fact is extremely important and useful in mathematics. Often it is much easier to prove
~Q ( ~P than to prove P ( Q, in which case that’s what you do. Why are they the same? If, whenever P is true, Q must also be true (i.e., P ( Q is true), then if Q is false, P can’t be true (since then Q would be true), so P must also be false. Of course, if Q is false, ~Q is true. So, if Q is false, ~Q is true, and it makes ~P also be true (since it makes P false). For example, “if today is Monday, then you have a MA 120 class meeting today” is a true statement, at least this semester (FA08). Its contrapositive is “If you do not have a MA120 class meeting today, then today is not Monday” which is also true. (On the other hand, the converse, “If you have a MA 120 class meeting today, then today is Monday” is NOT true: it might be Tuesday or Thursday. Nor is the inverse true: “If today is not Monday, you do not have a MA 120 class meeting today” is also false, for the same reason – you also have classes on Tuesday and Thursday.)
Assignment:
1. Your house has, unfortunately, just been burglarized. The police come to investigate. After they finish, they tell you, “You left the back door unlocked or you left a window open.” As you think back to before the burglary, you become convinced the police are wrong. What would have to be true to make you sure that the police are wrong? (Write your answer in a complete sentence.)
2. In one of your courses, the professor promises that if you get an A on all three midterms and on the final exam, you will get an A for the course. If y ou don’t get an A for the course, what had to have happened, assuming the professor keeps her promise? (Write your answer in a complete sentence.)
3. Consider the following sentences. What exactly would it mean for each one to be false?
(a) All butterflies have four wings.
(b) Some students live off campus.
(c) If an integer is even, then it is not prime.
For problems 4 and 5, let N = {1, 2, 3, 4, …}, A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 6, 8, 10}. P(x):= “x is a prime”, E(x) := “x is even”.
4. Negate and then turn the negation into decent English:
a. x is in A or x is not in B
b. x is in A and x is prime
c. I walk or take my bike to work.
d. If it is not raining, I walk or take my bike to work.
e. If I walk or take my bike to work, it is not raining.
5. Negate each of the following statements. Use AI, DeMorgan and Generalized De Morgan to move the “~” as far inside the statement as possible. Then translate them into English.
a. (( y ( B) (y is 6). f. (( x ( N) (P(x) ( E(x))
b. (( x ( A) x2 is not in B. g. (( x ( A) (x ( B ( x < 2)
c. (( x ( N) P(x). h. (( x ( N) (P(x) ( ~E(x))
d. (( x ( A) x > 1 i. (( x ( N) ((x > 2 ( P(x)) ( ~E(x))
e. (( x ( N) (P(x) ( E(x))
6. Write, in English, the converses of the following statements. Then explain briefly why the original statement is or is not true, and why the converse is or is not true.
(a) If x is an integer, then x2 > x.
(b) If x + y is odd and y + z is even, then x + z is odd. (Assume x, y, and z are integers.)
(c) If x is an integer, then x is even or x is odd.
(d) If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
(e) If xy is an even integer, then x is an even integer or y is an even integer.
7. Write, in English, the inverses of the following statements. Rewrite them in a positive fashion if possible. Then explain briefly why the original statement is or is not true, and why the inverse is or is not true. (If you’ve already explained, in 2, the original, you don’t have to do that again.
(a) If x is an integer, then x2 > x.
(b) If x + y is odd and y + z is even, then x + z is odd. (Assume x, y, and z are integers.)
(c) If x is an integer, then x is even or x is odd.
(d) If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
(e) If xy is an even integer, then x is an even integer or y is an even integer.
8. Write, in English, the contrapositives of the following statements. Then rewrite them in positive terms as much as possible.
(a) If x is an integer, then x2 > x.
(b) If x + y is odd and y + z is even, then x + z is odd. (Assume x, y, and z are integers.)
(c) If x is an integer, then x is even or x is odd.
(d) If x + y is an odd integer, then x is an odd integer and y is an even integer, or x is an even integer and y is an odd integer.
(e) If xy is an even integer, then x is an even integer or y is an even integer.
9. Consider the following statements. Explain, in language a mathematics student who has not yet taken this class would understand, what you would have to do to show it is true, and what you would have to do to show it is false. Then determine whether it is true or false, and give a reason.
(a) For positive real numbers x, there exists a positive real number y such that y < x.
(b) For real numbers x, there exists a real number y such that y < x.
(c) There is a positive real number x, such that for all positive real numbers y, x < y.
(d) There is a real numbers x, such that for all positive real numbers y, x < y.
(e) For positive integers x, there exists a positive integer y such that y < x.
(f) For integers x, there exists an integer y such that y < x.
Chapter 2 Introduction to Number Theory
Section 2.1 Even and Odd Integers
We will use Z for the name of the set of integers. Z := {..., -2, -1, 0, 1, 2, ...}, and N for the set of positive integers (natural numbers), {1, 2, 3, …}. We are going to assume that we know basic facts about the structure of N and Z. For example, if we add two integers together the result is another integer as opposed to a fraction or complex number. We need to have a common basis of understanding about Z so that we can hold a conversation. One fact that we point out is that sum of two integers is again an integer. This fact is referred to by saying the closure of addition on the integers. We also have the closure of multiplication on the integers. One common property that we will need to define carefully is the concept of an even integer.
Definition: An integer j is called even if there is some integer, call it x, such that j = 2*x. That is, if j is even ( (( x ( Z) (j = 2*x).
Pick an even integer. What is the second integer (the x) that makes the first even? For example 10 is even because of 5. That is 10 = 2*5. Indeed we just proved that 10 is even. In general to show an integer j is even we need to find an integer x so that j = 2*x.
Prove that –12 is even:
While we are at it we might as well say what it means for an integer to be odd. It is tempting to say that non-even integers are odd, but that would lead to trouble. We use a more constructive approach.
Definition: An integer j is called odd if there is some integer, call it x, such that j = 2*x + 1. That is, j is odd (
Just to get a sense of where we are going let’s examine the proof of a well-known fact. If you add an odd integer to itself, what can you say about the sum?
Theorem: If j is an odd integer then j + j is an even integer.
Discussion: This theorem can be brought closer to our logical form by rewriting as
(( j ( Z) ((j is odd) ( (j + j is even)). Or even more abstractly: (( j ( Z)(P ( R). This is interesting for we are trying to prove that an implication is true. Now we recall that implications are true most of the time. That is, implications are true in 3 of the 4 situations. If P is false, P ( Q is automatically true. It follows that, we need only consider what happens if P is true.
Therefore P is true becomes a given. Naturally Q becomes the get.
Proof. Assume that j is an odd integer. We need to show that j + j is an even integer. Since j is odd we know j = 2*a + 1 for some integer a. Now
j + j = 2*a + 1 + 2*a + 1 = 2*a + 2 = 2*(a + 1).
Since a and 1 are integers we can choose a new integer, which we’ll call c, defined by c = a + 1. Therefore we know that j + j = 2*c and j + j is even.
Let us put this prove in a table to better see how everything fits.
|1 |j is odd |given |
|2 |(( x ( Z) (j = 2*x + 1) |definition of odd |
|3 |j = 2*a + 1 |Witn(2) |
|4 |j + j = (2*a + 1) + (2*a + 1) |algebra |
|5 |j + j = (2*a + 2*a + 2) |algebra |
|6 |j + j = 2*(a + a + 1) |algebra |
|7 |Let c = a + a + 1 |NewVar |
|8 |j + j = 2*c |substitution |
|9 |(( c ( Z) (j + j = 2*c) |EQ(8) |
|Q |j + j is even |definition of even. |
Notice that, to make it clear that j + j is even we introduced a new variable, c, to replace the a + a + 1.
Your turn:
Theorem: If j is even and k is even then j + k is even.
Proof:
| |j is even |Given |
| |k is even |Given |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
Discussion: Givens: j is even and k is even. Note that Witness requires that each time you drop an existential quantifier, you must use a letter that hasn’t appeared in the proof yet. We will use the definition of even twice. j even means there is an integer a such that j = 2*a and k even means there is a second integer b such that k = 2*b. We can’t be sure a is different from b, but we also can’t be sure they are equal.
Try another:
Theorem: If j is odd and k is even then j + k is odd.
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
Next we look at a theorem involving multiplication.
Theorem: If j is even and k is odd then j*k is even.
Proof:
|1 |j is even |Given |
|2 |k is odd |Given |
|3 |(( x ( Z) (j = 2*x) |Def of even (1) |
|4 |(( x ( Z) (k = 2*x + 1) |Def of odd (2) |
|5 |j = 2*a |Witness (3) |
|6 |k = 2*b + 1 |Witness (4) |
|7 |j*k =(2*a)*(2*b + 1) |Algebra (subst)(5, 6) |
|8 |j*k = 2*(a*(2*b + 1)) |Algebra (7) |
|9 |Let c = a*(2*b + 1) |New Var |
|10 |j*k = 2*c |Substitution |
|11 |(( c ( Z) (j*k = 2*c) |EQ (10) |
|12 |j*k is even |Def. of even |
This same proof can be written in more prose-like form as follows:
Proof: We assume j is even and k is odd and show that j*k is even. To do this we need to find an integer c so that j*k = 2*c.
Since j is even j = 2*a for some integer a. Further, k odd implies k = 2*b + 1 for some? integer b. Therefore, j*k = (2*a)*(2*b+1) = 2*(a*(2*b + 1)). So we take c = (a*(2*b + 1)). We are sure that a is an integer and we have our proof.
Assignment
1. Find the error in the following proof. Explain why it is an error (what axiom or definition has been used incorrectly) and give a correct proof, if it’s true, or a counter-example, if it’s false.
To prove: if j is odd and k is even, then j 2 – k 2 = j + k.
|1 |j is odd |given |
|2 |k is even |given |
|3 |(( x ( Z) (j = 2*x + 1) |definition of odd (1) |
|4 |(( x ( Z) (k = 2*x) |definition of even (2) |
|5 |j = 2*a + 1 |Witn(3) |
|6 |k = 2*a |Witn(4) |
|7 |j 2 – k 2 = (2*a + 1) 2 - (2*a) 2 |algebra (substitution) |
|8 |j 2 – k 2 = 4*a 2 + 4*a + 1 - 4*a 2 |algebra |
|9 |j 2 – k 2= 4*a + 1 |algebra |
|10 |j 2 – k 2 =(2*a + 1) + (2*a) |algebra |
|11 |j 2 – k 2 = j + k |algebra (substitution) |
2. Find the error in the following proof. Explain why it is an error (what axiom or definition has been used incorrectly) give a correct proof, if it’s true, or a counter-example, if it’s false.
To prove: if j is odd and k is odd, then (j – 1)k is odd
|1 |j is odd |given |
|2 |k is odd |given |
|3 |(( x ( Z) (j = 2x + 1) |definition of odd (1) |
|4 |(( x ( Z) (k = 2x + 1) |definition of odd (2) |
|5 |j = 2a + 1 |Witn(3) |
|6 |k = 2b + 1 |Witn(4) |
|7 |(j – 1)k = ((2a + 1) - 1)(2b + 1) |algebra (substitution) |
|8 |(j – 1)k = (2a)*(2b + 1) |algebra |
|9 |(j – 1)k = 2ab + 1 |algebra |
|10 |Let c = ab |New Var |
|11 |(j – 1)k = 2c + 1 |algebra (substitution) |
|12 |(( x ( Z) ((j – 1)k = 2x + 1) |EQ (11) |
|13 |(j – 1)k is odd |definition of odd (12) |
In problems 3 – 5, (a) prove each in table-form, and (b) rewrite the proof in paragraph form.
3. Theorem: If j is odd and k is odd then j + k is even.
4. Theorem: If j is even and k is even then j*k is even.
5. Theorem: If j is odd and k is odd then j*k is odd.
In problems 6 and 7, investigate the truth of the statement. If it is true, prove it. If it is false, give a counter-example.
6. If j + k is even and k + m is even, then j + m is even.
7. If j + k is odd and k + m is odd, then j + m is odd.
8. A Pythagorean triple is a three-tuple of natural numbers (a, b, c) such that a2 + b2 = c2. For example, if a = 3, b = 4, and c = 5, 32 + 42 = 52; so (3, 4, 5) is a Pythagorean triple. These come from the Pythagorean theorem relating the sides and hypothenuse of a right triangle. Junior mathematics majors in Number Theory explore these triples, and you’re going to help them.
(a) They have a conjecture that if b is not even, then a must be even. They would like some help checking this conjecture. They’ve put the a and b values of some Pythagorean triples on some cards, with the a value on one side, and the b value on the other. Which of the following cards must you check to see whether their conjecture holds for the cases on these cards? Explain in each case why it must be checked, or why it needn’t be checked:
Card 1: a = 542 Card 2: b = 673 Card 3: a = 351 Card 4: b = 282
(b) Translate into symbols “a and b are members of a Pythagorean triple.” You may use symbols such as + and =, but not some special letters. You’ll have to get c involved somehow: use an appropriate quantifier.
(c) Using the same idea as in (b), translate “Every natural number greater than 2 is a member of some Pythagorean triple” into symbols. Be careful: that number might be the a or b (that is, the left side), but it also might be the c – so you’re going to need two cases (connected by an “or”). You will need at least 3 quantifiers in your statement.
(d) What is the negation of the statement in (c)? Write it both symbolically and in words.
Section 2.2 “Divides”
Definition: If a and b are integers and a ( 0 we write a|b, read “a divides b evenly” or simply “a divides b”, if there is a k ( Z such that ak = b. That is, the definition of a|b is ((k ( Z) ak = b.
Ex. 5|35 because 7 ( Z and 5*7 = 35.
Notice that a|b is completely different from a/b. a|b is a statement, a full sentence, with a verb (“divides”). a/b is simply a number, the result of dividing a by b. 5|35 is a true statement: it is NOT the number 7, nor is it the number 1/7. 5/35 is a number, the number 1/7. 35/5 is also a number, the number 7.
We know a lot about the integers. For example a,b ( Z ( a + b ( Z and ab ( Z. We can use these and other “common” facts in our proofs.
Theorem D0: ((a ( Z) ( a ( 0 ( a|0).
Theorem D1: ((a ( Z) (a ( 0 ( a|a).
Theorem D2: ((a ( Z) ( a ( 0 ( a|(-a)).
(From here on, we won’t mention that a, b, and c are non-zero integers, but will assume that they are. Also, as is standard mathematical practice, when the statement appears to have free variables, all variables are understood to be universally quantified over the domain under discussion. Thus, usually Theorem D0 is written simply a ( 0 ( a|0, and when properly quantified, Theorem D3, below, is written
((a ( Z) ((b ( Z) ((c( Z) (a|b and a|c ( a|(b+c)).)
Theorem D3: a|b and a|c ( a|(b+c)
Theorem D4: a|b and b|c ( a|c.
Theorem D5: a|b and c ( Z ( a|(cb).
Facts we will need:
Any non empty subset of N ( {0} has a smallest member.
If a ( Z then there is a s ( N such that s > |a|.
ab = 0 ( a = 0 or b = 0.
Lemma: If 0 ( a < b and b | a then a = 0.
Proof: Assume 0 ( a < b and b | a
b | a ( bk = a for some k ( Z.
Since b > 0 and a ( 0 then k ( 0.
0 ( a < b ( 0 ( bk < b ( b – bk > 0 ( b(1 – k) > 0 ( (1 – k) > 0 ( 1 > k
So 0 ( k < 1 and k ( Z ( k = 0.
So a = bk = 0.
Notice that this proof wasn’t written in our two-column format. Generally when you read mathematics proofs in books, they will be written in a paragraph format such as above, not in a two-column format. However, for the remainder of this course, you are encouraged to continue to use the two-column format, as it requires you make clear the reasons that justify each step. However, sometimes proofs in these notes will be in paragraph format.
Division Algorithm Suppose a, b ( Z and b > 0. Then there is exactly one q and exactly one r in Z such that a = bq + r and 0 ( r < b.
Proof: Let A = {a – bx | x ( Z and a – bx ( 0}.
We first show A is not empty.
Case 1. a ( 0. In this case a – b( 0 = a so a ( A.
Case 2. a < 0. Choose s so that s > –a. Then bs > –a. b(–s) < a and
so a – b(–s) > 0 and a – b(–s) ( A.
So A, being non-empty and consisting of non-negative integers, has a smallest element. Call the smallest member of A, r.
Everything in A has the form a – bx. So the x that satisfies a – bx = r will be our q. Show r = a – bq has the property 0 ( r < b:
a – bq ( A; so a – bq ( 0.
Suppose a – bq ( b. Then a – bq – b ( 0. So a – b(q – 1) ( 0.
It follows that a – b(q – 1) ( A. This contradicts the fact that a – bq is the smallest member of A.
So that means we can find a q and r to do the job. Next we need to see why there is only one choice for q and r.
Suppose a = bq + r and a = b[pic] + [pic] and 0 ( r ( [pic] < b.
0 ( r ( [pic] < b ( 0 ( [pic] – r < b.
0 = a – a = (bq+ r) – (b[pic] + [pic]). So 0 = bq – b[pic] + r – [pic]. Then b(q – [pic]) = [pic] – r. So b | [pic] [pic] r. By lemma [pic] [pic] r = 0. So [pic] = r.
It follows that bq = b[pic] and b(q – [pic]) = 0. So q = [pic], since b ( 0.
Assignment:
1. Prove D0
2. Prove D1
3. Prove D2
4. Prove D3
5. Prove D4
6. Prove D5
7a. If a = 27 and b = 5 find q and r. d. If a = -27 and b = 5 find q and r.
b. If a = 27 and b = 42 find q and r. e. If a = -273 and b = 72 find q and r.
c. If a = 271 and b = 97 find q and r.
8. Prove that every natural number is either even or odd. Hint: use the division algorithm, with q = 2. Then r = 0 or 1. What does this tell you?
9. Prove that if ac|bc and c ≠ 0, then a|b.
10. Continuing the discussion of Pythagorean triples from problem 8 of section 2.1, another conjecture is that in any Pythagorean triple, either a or b must be divisible by 3.
(a) Translate this into symbols. Use the concept of “divides” from this section. (How is it related to “is divisible by 3”?) You need first to say that you have a Pythagorean triple, as part of your statement.
(b) What is the negation of the statement in (a), both in symbols and in words?
(c) So what would you have to do to show that the statement in (a) is false?
Section 2.3 Modular arithmetic
Definition: Suppose a ( Z and n ( N then a mod n is the remainder when a is divided by n. That is, using the Division Algorithm to find the q and r such that a = nq + r,
(a mod n) is the r.
Example: 10 mod 3 = 1.
Define a (n b = (a + b) mod n
a (n b = (a ( b) mod n
We are usually working mod n for a fixed value of n and, when we are, we don’t write the subscript.
Example: Suppose we are working mod 11, then we will usually write 6 ( 8 = 4 instead of writing 6 (11 8 = 4.
Ideas: Let’s work mod 11 and do a little investigating. The only numerals we need are {0,1,2,…,10}. This new number system is called Z11.
Let’s check the properties that we have.
| |Addition |Multiplication |
|Associative | | |
|Commutative | | |
|Identity | | |
|Inverse | | |
Assignment:
Solve each of the following for x. Don’t ignore “order of operations!”
1. a. 2 (11 x = 7. b. 8 (11 x = 3 c. 9 (11 x = 7. d. 10 (11 x = 3
e. 6 (11 x = 3. f. 4 (11 x = 3 g. 2 (11 3(11x = 7. h. 8 (11 5(11x = 3
i. 9 (11 4(11x = 7. j. 10 (11 7(11x = 3 k. 6 (11 10(11x = 3. l. 8 (11 3(11x = 3
2. List all the perfect squares mod 11.
3. List all the perfect cubes mod 11.
4. Solve (if possible)
a. 1(11x2 (11 5 = 0 b. 1(11x2 (11 7 = 0 c. 3(11x2 (11 2 = 0
d. 2(11x2 (11 1 = 0 e. 5(11x2 (11 7 = 0 f. 3(11x2 (11 5 = 0
5. Write out addition and multiplication tables mod 6, that is, for Z 6.
6. Solve (if possible) a. 2 (6 x = 5. b. 5 (6 x = 2. c. 2 (6 x = 5. d. 5 (6 x = 2.
e. 4 (6 5 (6 x = 2 f. 5 (6 3 (6 x = 2 g. 5 (6 2 (6 x = 2
Section 2.4 Congruence mod n
Definition: a ( b (mod n) ( n | (a – b).
Example: 5|(27 – 12) since 27 – 12 = 15 = 5*3; so 12 ( 27 (mod 5).
How is this new definition related to a(mod n) of the last section?
Theorem: a ( b (mod n) ( a mod n = b mod n.
Proof: By the Division Algorithm there are numbers q1, r1, q2, and r2 so that
a = nq1 + r1 and b = nq2 + r2. Recall that r1 = a mod n and r2 = b mod n.
So a - b = nq1 + r1 – nq2 – r2 = n(q1 – q2) + (r1 – r2). Now, a ( b (mod n) ( n | (a – b). Thus, if a ( b (mod n), then n | (a – b) and n | n(q1 – q2), so n | (r1 – r2). But since r1 and r2 are both less than n, n can’t divide their difference unless r1 – r2 = 0, that is r1 = r2. So a mod n = b mod n . In the other direction, if a mod n = b mod n, then r1 = r2, so r1 – r2 = 0. Hence, n(q1 – q2) + (r1 – r2) = n(q1 – q2) = a – b. Therefore n | (a – b).
Example: Find all x such that x ( 3 (mod 11). We rephrase as find all x such that
11 | (x – 3). This means x – 3 = 11k for some k. That is, all k such that x = 3 + 11k satisfy x ( 3 (mod 11).
Theorem: a ( b (mod n) ( ak ( bk (mod n)
Proof: a ( b (mod n) ( n | a – b ( n | (a – b)k ( n | ak – bk ( ak ( bk (mod n).
Example: Solve 2x ( 7 (mod 11). In Z11, 2-1 = 6. We multiply both sides by 6. So 12x ( 42 (mod 11). Therefore 11 | 12x – 42. 11 | 12x – 42 ( 11 | 11x + x – 33 – 9 ( 11 | x – 9 ( x ( 9 (mod 11).
The solution then is 9 + 11k for each k in Z.
Assignment:
1. Prove:
a. If a ( b (mod n) and c ( d (mod n), then a + c ( b + d (mod n).
b. If a ( b (mod n) and b ( c (mod n), then a ( c (mod n).
c. If If a ( b (mod n) and c ( d (mod n), then a c ( b d (mod n).
d. If a ( b (mod n), then b ( a (mod n).
e. If a ( b (mod n), then a2 ( b2 (mod n)
2. If a2 ( b2 (mod n), must a ( b (mod n)? Either prove it or give a counter-example.
3. Solve each of the following, if possible; if impossible, explain why.:
a. 5x ( 1 (mod 6) b. 2x ( 5 (mod 11)
c. 3x ( 0 (mod 11) d. 5x ( 2 (mod 6)
e. 29x ( 17 (mod 11) f. 2x ( 5 (mod 6)
g. 4x ( 2 (mod 6) h. 17x ( 27 (mod 6)
Section 2.5 Getting Ready for Induction
Rather than a reading for today, think about (and come to class prepared to discuss with your group) the following problems. First DO them for the first few cases, and then think about how to do the general cases.
A. Find an upper bound to the sequence [pic], [pic], [pic], … .
B. You are given 3n coins, all identical except for one, which is heavier. Using a balance, prove that you can find the heavy coin in n weighings.
C. Into how many regions is the plane cut by n lines, assuming no two lines are parallel and no three lines intersect in a point?
Assignment: Prove by induction on n that:
1. for all n ( N, 2|( n2 – n);
2. that our answer to C is correct;
3. that 1 + 2 + 3 + … + n = n(n + 1)/2.
Section 2.6 The Square Root Is Not A Fraction (“[pic] is irrational”)
Before starting on our next topic we look at one of the classic proofs. This proof is predicated on the fact that every fraction [pic] can be reduced so that the top is odd or the bottom is odd. That is, either a or b is not even.
Further the theorem, c odd and d odd ( cd odd plays a role. This tells us that;
c is odd ( c2 is odd.
Using the contrapositive;
c2 is even ( c is even.
We assume [pic] = [pic].
|1 |[pic] = [pic] | |
|2 |[pic]b = a | |
|3 |2[pic]b2 = a2 | |
|4 |a2 is even | |
|5 |a is even | |
|6 |a = 2[pic]k for some k | |
|7 |a2 = 4[pic]k2 | |
|8 |2[pic]b2 = a2 and a2 = 4[pic]k2 | |
|9 |2[pic]b2 = 4[pic]k2 | |
|10 |b2 = 2[pic]k2 | |
|11 |b2 is even | |
|12 |b is even | |
|13 |a is even and b is even | |
What we have shown then is: if a is not even or b is not even then [pic] ( [pic].
Yet every rational number can be written in lowest terms; thus, if [pic] is rational, it can be written in the form [pic], where not both a and b are even. Thus, it must be irrational.
Section 2.7 Proofs using Mathematical Induction
Principle of Mathematical Induction: The set of natural numbers N = {1, 2, 3, .... }, has the following property: Suppose S is any subset of N such that 1 is in S and whenever any number k is in S you can be sure that k + 1 is also in S; then S = N.
Consider this theorem:
Theorem: 1 + 3 + 5 + ... + (2n – 1) = n2.
In one sense this is really an infinite number of theorems.
P(1):= 1 = 12.
P(2):= 1 + 3 = 22
P(3):= 1 + 3 + 5 = 32
and so forth. Proving each of these individually would take some time. But since N has the property known as the axiom of induction, we have a better way.
Let S = {n ( N | P(n) is true}. Then to prove that S is all of N, that is that S(n) is true for all n, we have two steps.
Step 1: Show P(1) is true.
Step 2: Using that P(k) is true, get that P(k+1) must be true.
So here is the proof.
Proof: This is a proof by induction and therefore involves two steps.
Step 1. Show P(1). Left side of P(1) is 1. The right side of P(1) is 12. So they are equal. P(1) is true.
Step 2. Assume P(k) is true. That allows us to write 1 + 3 + 5 + ... + (2k – 1) = k2.
Now, add the next term (that is, what would be the final term of the left side for P(k+1)) to both sides, and manipulate the right side until the equation becomes that for P(k+1). Since the last term of P(k) is (2k – 1), the last term of P(k+1) is (2(k+1) – 1):
|1 + 3 + 5 + ... + (2k – 1) = k2 |Given |
|1 + 3 + 5 + ... + (2k – 1) + (2(k + 1) – 1) = |Adding same thing to both sides |
|k2 + (2(k + 1) – 1) | |
|1 + 3 + 5 + ... + (2(k + 1) – 1) = k2 + (2(k + 1) – 1) |Hiding k-th term on left. |
|1 + 3 + 5 + ... + (2(k + 1) – 1) = k2 + 2k + 1 |Algebra |
|1 + 3 + 5 + ... + (2(k + 1) – 1) = (k + 1)2 |Algebra: so P(k+1) is true! |
That is the entire proof.
Suppose you were looking at a very long stairway. You are certain that you can make it up the first step. You are just as certain that if you can climb a step then you can climb the next one. Then you can climb all the entire stairway.
Your turn.
Prove: 1.2 + 2.3 + 3.4 + … + n(n+1) = [pic].
Assignment: In problems 1 – 11, prove by induction on n:
1. x0 + x1 + x2 + ... + xn-1 = [pic], where x is any real number except 0 or 1, and n is a natural number
2. (-1)012 + (-1)122 + (-1)232 + ... + (-1)n-1n2 = (-1)n+1[pic].
3. 12 + 42 + 72 + … + (3n – 2)2 = [pic].
4. 1[pic]1! + 2[pic]2! + 3[pic]3! +[pic]+ n[pic]n! = (n+1)! – 1
5. 3|(n3 - n).
6. 5|(n5 - n).
7. 6|(n3 - n).
8. n2 > n + 1, if n > 1
9. n2 > 2n + 1, if n > 2
10. 2n > n2, if n > 4.
11. 2n < n!, if n > 3.
12. Prove by induction on k that if a ( b (mod n), then ak ( bk (mod n), for all natural numbers k and n and integers a and b.
13. Prove that, for all natural numbers n,
[pic]
14. (a) What is wrong with the following proof (Vellemann 266 #17) that
[pic]?
Proof by induction: Assume that, for some natural number k,
[pic]
Adding [pic] to both sides gives
[pic]
The left side is now correct; so we work on the right side:
[pic]
Thus, [pic]
which is the k + 1 case. Thus the theorem is proven.
(b) Show the statement isn’t even true, by giving a counter-example/
(c) Modify the statement by giving a correct right side to the equation (the correct formula is not very different) and prove, by induction, that it is correct.
Chapter 3 Set Theory
Section 3.1 Introduction to Set Theory
We are going to assume that we all know what is meant by a “set”. When we write, “A = {1,2,3,6,9}”, we are declaring that A is a set in which there are 5 distinct objects, in this case natural numbers. “2 ( A” is read the “2 is a member of the set A”. The statement “2 ( A” is as simple a statement as there is in set theory. The other side of the coin are statements of the form “7 ( A”, means that 7 is not a member of A. This is the same as ~ 7 ( A. All statements in set theory arise from these two types of statements. They are the atoms of the theory, in the Greek sense.
In any set theory discussion we will assume that there is a set that has all possible elements involved in the discussion. This set will be called U, the universe of discourse.
Definiton: Two sets are equal if they have exactly the same elements: A = B (
(( p)( p ( A ( p ( B).
A third set can be designated by combining two sets in various ways.
Definition: If A and B are sets then A ( B = { p ( U | p ( A or p ( B}. “A ( B” is read “A union B”. So p ( A ( B ( p ( A ( p ( B
If in a proof we arrive at the fact that p ( A ( B, by applying the “Def. (” we get the new statement p ( A ( p ( B. Equivalently, if we wish to conclude that p ( A ( B we must have p ( A ( p ( B.
Definition: If A and B are sets then A ( B = { p ( U | p ( A and p ( B}. “A ( B” is read “A intersection B”. So p ( A ( B (
Definition: If A and B are sets then A ( B = { p ( U | p ( A and p ( B}. “A ( B” is read “A minus B”. So p ( A ( B (
Definition: Def: Ac = { p ( U | p ( A}. So p ( Ac ( ~(p ( A).
Ac is read “the complement of A” or simply “A complement”. (There is no agreed-on notation for the complement of a set. Some books use [pic], and some books use [pic]. Our text uses a very large, curly C. Since Ac, unlike the others, is rarely used for anything else and is easy to type, we’ll use this notation in these notes.)
Let the universe of discourse (U) be N. Notice that p ( {1,2,3} ( {5,6} is always false. This leads us to introduce the notion of Ø; the empty set.
Definition: Ø is defined by ((p ( U) p ( Ø. Ø is called “the empty set.”
Suppose that U = {1,2,3,...,10}, A = {1,3,5,7,9}, B = {5,6,7,8}, C = {2,3,5,7}. Then
A ( B = {1,3,5,6,7,8,9}, A ( B = {5,7}, A – B = {1,3,9}, and Ac = {2,4,6,8,10}.
Definition: If A and B are sets then "A ( B", read "A is a subset of B" is true if and only if (( p ( U)( p ( A ( p ( B).
Example: Let U = {1, 2, 3, 4}. We consider the statement {1,2} ( {1,2,3}. We can prove this is indeed true by considering four statements ... one for each element of U.
1 ( {1,2} ( 1 ( {1,2,3}, 2 ( {1,2} ( 2 ( {1,2,3},
3 ( {1,2} ( 3 ( {1,2,3} and 4 ( {1,2} ( 4 ( {1,2,3}.
All of these statements are true. Hence, {1,2} ( {1,2,3} is also true. Notice that 3 ( {1,2} ( 3 ( {1,2,3} and 4 ( {1,2} ( 4 ( {1,2,3} are true because their hypotheses are false.
First Half of a Proof in Set Theory
This leads us to a strategy of proving statements of the type A ( B. We can take p ( A as a given and take p ( B as the “get”.
The first batch of set theory proofs that we will tackle begin with a statement of the form p ( (A – B) ( C. The first phase of the proof can be viewed as a process of simplification. In set theory the simplest statement has the form a ( S. We will call this a level 1 statement. Other level 1 statements are ~(b ( S), or, equivalently, b ( S. On the other hand, p ( A - B is a level 2 statement and p ( (A - B) ( C is a level 3. The initial phase of a proof can be regarded as taking high-level statements down to lower levels. Here is an Example of what I mean.
|1 |p ( (A – B) ( C. |Given |
|2 |p ( (A – B) ( p ( C. |Def. ((1) |
|3 |p ( C. |simp (2) |
|4 |p ( A – B. |simp (2) |
|5 |p ( A ( p ( B. |Def. – (4) |
|6 |p ( A. |simp(5) |
|7 |p ( B. |simp(5) |
Table 1: conclusion p ( C, p ( A, p ( B
Lines 3, 6 and 7 are the level 1 results of this process. They actually contain all the information that you are given in its simplest form.
Let’s do the same for a similar problem:
|1 |p ( A – (B ( C). | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
Conclusion: p ( A, p ( B, p ( C
The union operation complicates the issue slightly as seen below.
|1 |p ( A ( (B – C). |Given |
|2 |p ( A or p ( B – C |Def ( (1) |
|3 |Case 1. p ( A. | |
|4 | | |
|5 | | |
|6 |Case 2. p ( B – C | |
|7 |p ( B and p ( C |Def – (4) |
|8 |p ( B. |simp (5) |
|9 |p ( C. |simp (5) |
Practice!.
|1 |p ( A ( (B ( C) |Given |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
Case 1: p ( A Case 2: p ( B, p ( C
Assignment:
1. Let U = {1,2,3,...,10}, A = {1,3,5,7,9}, B = {5,6,7,8}, C = {2,3,5,7}.
Determine each of the following.
a. C ( B b. C ( B
c. A – (B ( C) d. A ( (B ( C)
e. A ( (B – C) f. (A – B) ( C
g. (A ( B) ( C h. (A ( B) – C
i. A – (B – C) j. (A – B) – C
2. Let U = R, A = {p ( R : 1 < p < 10}, B = { p ( R : p > 6}, C = { p ( R : 3 < p < 7}.
Determine each of the following.
a. C ( B b. C ( B
c. A – (B ( C) d. A ( (B ( C)
e. A ( (B – C) f. (A – B) ( C
g. (A ( B) ( C h. (A ( B) – C
i. A – (B – C) j. (A – B) – C
3. If A = {1,3,6,10}, B = {2,5,6,10}, C = {x ( N: x is prime}, find the following sets:
(a) A ( C (b) (A ( B) ( C (c) (A ( B) – C (d) C – (A ( B)
In exercises 4 – 7, fill in the tables for the half-proofs:
|1 |p ( A ( (B – C) | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
4. conclusion: p ( A, p ( B, p ( C
|1 |p ( (A ( B) – C. | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
5. conclusion: .
|1 |p ( (A ( B) – C. |Given |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
6. p ( C, Case 1: p ( A Case 2: p ( B
|1 |p ( A ( (B – C). |Given |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
7. Case 1: , Case 2:
Section 3.2 Finishing set theory proofs
Once you are able to extract all the information from the givens, then you are in a position to make up theorems. We revisit table 1 (p. 39).
|1 |p ( (A – B) ( C. |Given |
|2 |p ( (A – B) and p ( C. |Def. ((1) |
|3 |p ( C. |simp (2) |
|4 |p ( A – B. |simp (2) |
|5 |p ( A and p ( B. |Def. – (4) |
|6 |p ( A. |simp(5) |
|7 |p ( B. |simp(5) |
|8 | | |
Table 2a
We know the information in lines 3, 6 and 7. Using that information what can we say about p? How about p ( (A ( C) ( B. There you go. We have a theorem.
Theorem: (A – B) ( C ( (A ( C) ( B
The proof is a continuation of table 2a.
|8 | p ( A and p ( C | conj (3,6) |
|9 |p ( A ( C |Def ( (8) |
|10 |p ( (A ( C) and p ( B |conj (9,7) |
|11 |p ((A ( C) ( B |Def ( (10) |
|12 |(( p ( U)( p ( (A – B) ( C ( p ( (A ( C) ( B) |UG (1,11) |
|13 |(A – B) ( C ( (A ( C) ( B |Def ( (12) |
Table 2b
We have seen how to a statement in which an element p is a member of a complicated set and extract from this information about p’s membership in simple sets. The second part is building back up from the simple to the desired set. Usually, it is simpler to start with what you are trying to get and determine what you need to get it.
Example: Suppose we wish to get p ( A ( (B – C). To be able to write this we would need to know that p ( A and p ( B – C. We can do this by putting what we want to obtain at the bottom of the proof, and working backwards, as long as we’re using definitions, which go both ways. (That is, all definitions are “if and only if” statements.) You must be careful if you’re using theorems, rather than definitions, to be sure that they are “if and only if” statements, or, if you’re working backwards, that the statement on the lower line comes after the “then” and the statement on the higher line comes after the “if”.
| | |
|11 |p ( C. |
|12 |p ( B. |
|13 |p ( A. |
|14 |p ( B – C. |
|15 |p ( A and p ( B – C. |
|16 |p ( A ( (B – C). |
The idea is that we would need to know lines 11, 12 and 13 to be able to write line 16.
Practice
| | |
|11 | |
|12 | |
|13 | |
|14 | |
|15 | |
|16 |p ( A – (B ( C). |
The presence of ( makes the job of proving somewhat simpler.
Example: Suppose that our get statement is p ( A ( (B ( C). Keep in mind we are reversing our thinking. That is we are working from the bottom up.
| | | |
| | | |
| | | |
|15 |p ( A or p ( (B ( C) | |
|16 |p ( A ( (B ( C). | |
What we have discovered is that there are two ways to be able to write p ( A ( (B ( C). If we know p ( A or p ( A ( B we would have it.
Some Complete Proofs
A ( (B ( C) ( B ( (A ( C)
|1 |p (A ( (B ( C) | |
|2 |p ( A and p ( (B ( C) | |
|3 |p ( A | |
|4 |p ( B ( C | |
|5 |p ( B or p ( C | |
|6 |Case 1: p ( B | |
|7 |p ( B or p ( (A ( C) | |
|8 |p ( B ( (A ( C) | |
|9 |Case 2: p ( C | |
|10 |p ( A and p ( C | |
|11 |p ( A ( C | |
|12 |p ( B or p ( (A ( C) | |
|13 |p ( B ( (A ( C) | |
|14 |p ( A ( (B ( C) ( p ( B ( (A ( C) | |
|15 |(( p ( U)( p ( A ( (B ( C) ( p ( B ( (A ( C)) | |
|16 |A ( (B ( C) ( B ( (A ( C) | |
Let’s look at how to write this in paragraph format:
To prove that A ( (B ( C) ( B ( (A ( C), we begin with an element p which is in
A ( (B ( C). By the definition of the intersection of two sets, p ( A and p ( (B ( C). Using next the definition of union of two sets, p ( B or p ( C. So we must consider each case separately. If p ( B , then certainly p ( B OR p ( A ( C; hence, by the definition of union, p ( B ( (A ( C). If, on the other hand, p ( C, then since p was already in A,
p ( A AND p ( C, and thus p ( A ( C. Hence, p ( B OR p ( A ( C and thus again by the definition of union, p ( B ( (A ( C) and we’re done.
Theorem: A = B ( (A ( B and B ( A).
Proof: To prove an “if and only if” statement, we need to prove both directions of the implication: A = B ( (A ( B and B ( A), and (A ( B and B ( A) ( A = B
|1 |A = B |Given |
|2 |(( p)( p ( A ( p ( B) |Def = (1) |
|3 |(( p)(( p ( A ( p ( B) ( ( p ( B ( p ( A)) |Equiv (2) |
|4 |( r ( A ( r ( B) ( ( r ( B ( r ( A) |Exem (3) |
|5 | r ( A ( r ( B |Simp (4) |
|6 |(( r)( r ( A ( r ( B) |UG (5) |
|7 |A ( B |Def ( (6) |
|8 |( r ( B ( r ( A) |Simp (4) |
|9 |(( r)( r ( B ( r ( A) |UG (8) |
|10 |B ( A |Def ( (9) |
|11 |A ( B and B ( A |Con (7, 10) |
|12 |A = B ( (A ( B and B ( A) |Implies (1, 12) |
|13 |A ( B and B ( A |Given |
|14 |A ( B |Simp (13) |
|15 |B ( A |Simp (13) |
|16 |(( p)( p ( A ( p ( B) |Def ( (14) |
|17 |r ( A ( r ( B |Exem (16) |
|18 |(( p) ( p ( B ( p ( A) |Def ( (15) |
|19 |r ( B ( r ( A |Exem (18) |
|20 |( r ( A ( r ( B) ( ( r ( B ( r ( A) |Con (17, 19) |
|21 |r ( A ( r ( B |Equiv (20) |
|22 |(( r)( r ( A ( r ( B) |UG (21) |
|23 |A = B |Def = (22) |
|24 |(A ( B and B ( A) ( A = B |Implies (13, 23) |
|25 |A = B ( (A ( B and B ( A) |Equiv (12, 24) |
This theorem tells us that, to prove two sets are equal, we can prove that each is a subset of the other. This is often what is done.
Assignment:
In 1 - 4, fill in what previous lines will be needed to get the conclusion on line 16:
| | |
|11 | |
|12 | |
|13 | |
|14 | |
|15 | |
|16 |p ( (A ( B) – C. |
1.
(In # 2, be careful: ~(P(Q) is NOT ~P ( ~Q! Use DeMorgan.)
| | |
|11 | |
|12 | |
|13 | |
|14 | |
|15 | |
|16 |p ( A – (B ( C). |
2.
| | | |
| | | |
| | | |
| | | |
|14 | | |
|15 | | |
|16 |p ( (A – B) ( C. | |
3.
| | | |
| | | |
| | | |
| | | |
|14 | | |
|15 | | |
|16 |p ( (A ( B) ( C. | |
4.
5. Use Venn diagrams to establish the following identities:
(a) A – (A ( B) = A – B
(b) A ( (B ( C) = (A ( B) ( (A ( C)
(c) (A ( B) – C = (A – C) ( (B – C)
(d) A ( (B – C) = (A ( B) – (C – A)
6. Find the error in the following proof. Explain why they are errors (what axioms or definitions have been used incorrectly) and give a correct proof.
(Ac ( B)c ( A ( Bc
|1 |(Ac ( B)c |given |
|2 |~(Ac ( B) |definition Ac (1) |
|3 |~Ac ( ~ B |DM (2) |
|4 |~ ~ A ( Bc |definition Ac (twice)(3) |
|5 |A ( Bc |~ ~ (4) |
7. Find the errors in the following proof. Explain why they are errors (what axioms or definitions have been used incorrectly) and give a correct proof.
(Ac ( B)c ( A ( Bc
|1 |p ( (Ac ( B)c |given |
|2 |~(p ( Ac ( B) |definition Ac (1) |
|3 |~(p ( Ac ( B) |definition of ( (2) |
|4 |~ p ( Ac ( ~ B |DM (3) |
|5 |p ( A ( Bc |~ ~ and definition Ac (4) |
|6 |p ( A ( Bc |definition of ( (5) |
8. Prove A ( (B ( C) ( (A ( B) ( (A ( C)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
9. Prove (A ( B) ( (A ( C) ( A ( (B ( C)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
|21 | | |
|22 | | |
10. Find the errors in the following proof. Explain why they are errors (what axioms or definitions have been used incorrectly) and give a correct proof.
(A ( B) ( (A ( Bc) ( A
|1 |p ( (A ( B) ( (A ( Bc) |given |
|2 |(p ( A ( p ( B) ( (p (A ( p ( Bc) |definition of ( (1) |
|3 |p ( A |case 1 (2), end case 1 |
|4 |p ( B ( p ( Bc |case 2 (2) |
|5 |p ( B and p ( Bc |definition of ( (4) |
|6 |p ( B |simp (5) |
|7 |p ( Bc |simp (5) |
|8 |~ p ( B |definition of Ac (7) |
|9 |(6) and (8) are a contradiction, so case 2 doesn’t happen |
11. Find the errors in the following proof. Explain why they are errors (what axioms or definitions have been used incorrectly) and give a correct proof.
(A ( B) ( (A ( C) ( A ( (B ( C)
|1 |p ( (A ( B) ( (A ( C) |given |
|2 |p ( (A ( B) ( (A ( C) |Definition of ( (1) |
|3 | p ( (A ( B) ( (A ( C) |Definition of ( (2) |
|4 |p ( A ( (B ( C) |Dist (3) |
|5 |p ( A ( (B ( C) |Definition of ( (4) |
|6 |p ( A ( (B ( C) |Definition of ( (5) |
12. (a) Prove A ( (B ( C) ( (A ( B) ( (A ( C) in tabular form:
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
|21 | | |
|22 | | |
(b) Give a paragraph-form proof of A ( (B ( C) ( (A ( B) ( (A ( C).
Notice that, from 11 and 12, we can conclude A ( (B ( C) = (A ( B) ( (A ( C). This is the set-theoretic version of the logical axiom schema “Distributive”. In fact, there is a very easy proof of A ( (B ( C) = (A ( B) ( (A ( C) by using Distributive directly.
13. Find the errors in the following proof. Explain why they are errors (what axioms or definitions have been used incorrectly) and give a correct proof.
A – (B ( C) ( (A – B) ( (A – C)
|1 |p ( (A – B) ( (A – C) |given |
|2 |p ( (A – B) and p ( (A – C) |definition of ( (1) |
|3 |p ( (A – B) |simp (2) |
|4 |p ( (A – C) |simp (2) |
|5 |p ( A and p ( B |definition of A – B (3) |
|6 |p ( A and p ( C |definition of A – C (4) |
|7 |p ( A |simp (5) |
|8 |p ( B |simp (5) |
|9 |p ( C |simp (6) |
|10 |p ( B and p ( C |conj (8, 9) |
|11 |~ (p ( B or p ( C) |DM (10) |
|12 |p ( B ( C |definition of ( (11) |
|13 |p ( A and p ( B ( C |conj (7, 12) |
|14 |p ( A – (B ( C) |definition of A – B (13) |
14. (a) What’s wrong with the following proof of the statement: “Suppose A ( C, B ( C, and x ( A. Then x ( B”?
“Proof”: Suppose x ( B. Since x ( A and A ( C, x ( C. Since x ( B and B ( C, x ( C. This is a contradiction. Therefore x ( B.
(b) Either give a correct proof of the statement in (a) or give a counter-example.
Section 3.3 Using Sets Defined by Set-Description Notation
One very common way to define new mathematical objects is to pick out, from a set that has already been defined, a subset consisting of all elements with a particular property. The format for such a definition is {a ( A | P(a)}, where A is the set that has already been defined, P is a property that it makes sense to inquire whether elements of A have, and a (or any other letter) is a variable which, in this context, is bound in both its occurrences. This format is called “set description notation.” It is read, “The set of all a in A which have the property P(a).” The expression to the right of the vertical line is called the “defining criterion of the set.” For example, E = {n ( N | (( m ( N) n = 2m} defines the even natural numbers: the set of all n in the natural numbers such that there is an m in the natural numbers such that n is twice m. “(( m ( N) n = 2m” is the defining criterion of E. We have already used this notation when we first introduced set theory. For example, we defined A ( B = { p ( U | p ( A or p ( B}, where U was the universe under discussion.
The purpose of this section is to have you start learning how to respond when you are given a definition in this form. The first thing you should do, when you meet an object defined using set-description notation, is to figure out what it means. In particular, find two or three objects that are in the new set, and two or three that are not in it, and what is the criterion that separates things in it from things not in it.
Let’s do that for E, defined above. We see that the set from which we’re taking our possible elements is N. We see this because the first expression after “{“ is n ( N. Whatever is to the left of the vertical line (and sometimes, rather than a vertical line, a colon (“:”) is used instead) tells you what set you are taking your objects from, that is, what set your new set is a subset of. Thus, E will be a subset of N, the natural numbers. So candidates to be members of E must be natural numbers. So we can try 1, 2, 3, etc., to see whether they are in E. It’s usually best to try a typical member of your larger set, rather than a special one, at least at first. So rather than starting with 1, let’s start with 3. (There is an interesting argument, by induction, that there is no “typical” natural number. In particular, 3 is special in that it is the first odd prime. So it might have been better to start with 5, or 22.) To check, say, whether 3 is in E, we look at the expression to the right of the vertical line (or colon). That is, in this case, we look at (( m ( N) n = 2m. This appears to be an open sentence, with n as a free variable. However, when we are checking that 3 is in E, we are taking 3 to be one of the things in N, that is, we are letting n = 3. Thus, the statement to the right of the vertical line has had n replaced by 3. So to determine whether 3 ( E, we must determine whether (( m ( N) 3 = 2m. So now we need to figure out what this says. It says, “there is a natural number m” (this is the translation of (( m ( N)) “such that 3 = 2m”. Now, can we find such an m? No: if we try to solve 3 = 2m, we get m = 3/2, and 3/2 is not a natural number. Thus, there is no such m, and 3 is not in E. On the other hand, when we try to determine whether 10 ( E, we replace n by 10, giving us (( m ( N) 10 = 2m. This does have a solution in natural numbers: m = 5. Therefore, 10 is in E.
Find two more elements of E (and show they are elements of E) and two more natural numbers that are not in E (and show they are not in E).
In this case, I already told you that E is the set of even integers, and so figuring out a criterion that separates things in it from those not in it is easy. In fact, in one sense it is always easy: the expression on the right side of the vertical line is the criterion that separates what is in the subset from what is not. However, some work is often involved to move from that formal expression to an understanding of what the set is.
Let’s try a second example. Here’s a new set: let B = { x ( R : |x – 4| < |x + 3|}. (Recall that the absolute value function is defined by [pic] .) OK, what kinds of objects are we considering for possible membership in B: that is, what set is B a subset of? Yes, the real numbers, since on the left of the colon, it says “x ( R”. So let’s pick a few real numbers and try them out. 4.52 is a good real number. (It’s not quite typical, since it’s a rational number, but it’s more typical than, say, 3, which is an integer.) Thus, we’re going to let x = 4.52. Is |4.52 – 4| < |4.52 + 3|? Yes, 0.52 < 7.52. So 4.52 ( B. What about -2.3? Is |-2.3 – 4| < |-2.3 + 3|? No, 6.3 > 0.7. So -2.3 ( B. Similarly, 0 ( B, 0.34 ( B, 1.1 ( B, 0.9 ( B. We’re narrowing in. You may need to check more examples. Once you start to get a feel for what is and what is not in the set, you’re ready to start thinking about what the criterion on the right of the colon is saying. One good way to interpret |x – 4| < |x + 3| is as a statement about distances. |x – a| translates both as “the absolute value of x minus a” and as “the distance between x and a.” Thus, rewriting |x + 3| in the form |x – (-3)|, we see that |x – 4| < |x + 3| translates to
|x – 4| < |x – (-3)|, and that turns into “the distance between x and 4 is less than the distance between x and -3.” On the number line,
__________________________________________________
-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
anything closer to 4 than to -3 meets our criterion. What’s exactly the same distance to 4 as to -3? Their average: 0.5. Thus, anything to the right of 0.5 is in our set B. Now, having reasoned this out, let’s look at our examples: yes, those that ended up in B were to the right of 0.5, and anything that ended up not in B was to the left of 0.5. What about 0.5 itself? Is |0.5 – 4| < |0.5 + 3|?
As you realize by now, much of this course is devoted to learning how to prove mathematical statements. But before you can prove a statement, it is important to understand what it is saying. Also, before you even try to prove a statement, it is worthwhile to convince yourself that it is probably true, by checking that, for a number of typical examples of the hypotheses, the conclusion is true.
Now let’s turn to proving statements about sets defined using set-description notation. Proving theorems about such sets often involves proving that every element has a particular property. To do this, you take an “arbitrary” element of the given set, and show that, because of the defining criterion of the set, it must have the desired property. You MAY first want to check that a few typical elements of the set have the property. Here’s an example of this process.
Prove that the set B, defined above, is a subset of the positive real numbers.
First, let’s check a few examples. We know that 4.52, 1.1, and 0.9 are in B, and they are all indeed positive real numbers. But we cannot stop there! This is checking cases, not giving a proof. Here’s a proof:
Let x ( B. Then (using the defining criterion of B), |x – 4| < |x + 3|. We’re trying to prove that x is positive; that is, we want to prove that x > 0. If there were just one expression involving absolute value, we could simply use the definition of absolute value. However, with two, this gets a bit messy. So let’s break one of the absolute values into two cases.
Case 1: x – 4 > 0. Then x > 4. In this case, certainly x > 0, since 4 > 0 and the relation > is transitive.
Case 2: x – 4 < 0. That is, x < 4. Then, using the definition of absolute value, |x – 4| = - (x – 4) = 4 – x. Thus, |x – 4| < |x + 3| becomes 4 – x < |x + 3|. Now, this again breaks into two cases:
Case 2a: x + 3 > 0. Then 4 – x < |x + 3| becomes 4 – x < x + 3. Solving for x, we get 1 < 2x, and thus x > ½. Since ½ > 0, we have proved x > 0 in this case.
Case 2b: x + 3 < 0. Then 4 – x < |x + 3| becomes, as above, 4 – x < - (x + 3); that is,
4 – x < - x - 3. Adding x to both sides, we end up with 4 < -3. This is a false statement. That means that case 2b never in fact happens. Since in both case 1 and case 2a, x > 0, and these are the only cases that can happen, we have proved that if x ( B, x is positive. Thus, we’ve proved that B is a subset of the positive numbers.
This can, of course, be done in our two-column format. Here is a two-column version of the same proof:
|1 |x ( B |Given |
|2 ||x – 4| < |x + 3| |B’s defining criterion (1) |
|3 |(x – 4 > 0) ( (x – 4 < 0) |EM |
|4 |x – 4 > 0 |Case 1 of (3) |
|5 |x > 4 |Algebra (4) |
|6 |4 > 0 |Arithmetic |
|7 |x > 0 |Transitivity of > (5, 6), end case 1 (3) |
|8 |x – 4 < 0 |Case 2 of (3) |
|9 |4 – x < |x + 3| |Definition of |x - 4|, (2) |
|10 |(x + 3 > 0) ( (x + 3 < 0) |EM |
|11 |x + 3 > 0 |Case 1 of (10) |
|12 |4 – x < x + 3 |Definition of |x + 3|, (9) |
|13 |1 < 2x |Algebra (12) |
|14 |x > ½ |Algebra (13) |
|15 |½ > 0 |Arithmetic |
|16 |x > 0 |Transitivity of > (14, 15), end case 1 (10) |
|17 |x + 3 < 0 |Case 2 of (10) |
|18 |4 – x < - (x + 3) |Definition of |x + 3|, 9 |
|19 |4 – x < - x - 3 |Algebra (18) |
|20 |4 < -3 |Algebra (19), Contradiction, end case 2 (10), end case 2 (3) |
For a second example of a proof involving a set defined using set-description notation, consider the following set: Define A ( B = {x ( U | (x ( A – B) ( (x ( B – A)}. We’ll prove A ( B ( A ( B.
|1 |x ( A ( B |Given |
|2 |(x ( A – B) ( (x ( B – A) |A ( B’s defining criterion (1) |
|3 |x ( A – B |Case 1 (2) |
|4 |x ( A ( ~ x ( B |Definition of A – B (3) |
|5 |x ( A |Simp (4) |
|6 |x ( A ( x ( B |Add (5) |
|7 |x ( A ( B |Definition of A ( B (6), end case 1 (2) |
|8 |x ( B – A |Case 2 (2) |
|9 |x ( B ( ~ x ( A |Definition of B – A (8) |
|10 |x ( B |Simp (9) |
|11 |x ( B ( x ( A |Add (10) |
|12 |x ( A ( x ( B |Comm (11) |
|13 |x ( A ( B |Definition of A ( B (12) |
As the course progresses, we will see more examples of this kind of definition, and its uses.
Assignment
1. Write the definitions of these sets using set description notation:
(a) {1, 4, 9, 16, 25, 36, …}
(b) {1, 2, 4, 8, 16, 32, …}
(c) {8, 9, 10, 11, 12, 13, …}
(d) {8, 9, 10, 11, …, 19}
(e) {6, 9, 12, 15, 18, …}
(f) {1, 4, 7, 10, 13, 16, …}
2. Determine whether each of the following statements is true or false; justify your decision:
(a) -2 ( {x ( Q: 10 – 3x > 1}
(b) 5 ( {x ( Q: 10 – 3x > 1}
(c) 3 ( {x ( Q: 10 – 3x > 1}
(d) π ( {x ( Q: 10 – 3x > 1}
3. Determine whether each of the following statements is true or false; justify your decision:
(a) -2/3 ( {x ( Q: |10 – 3x| > 1}
(b) 5 ( {x ( Q: |10 – 3x| > 1}
(c) 3.5 ( {x ( Q: |10 – 3x| > 1}
(d) 9/2 ( {x ( Q: |10 – 3x| > 1}
4. For each of the following sets, find 3 examples of mathematical objects that are in the sets, and 3 that are not. Then give an accurate description in words of what the criterion for membership in the set is.
a. A = { n ( N : (4 | n )}
b. B = { n ( N : ~ (3 | n )}
c. C = { n ( N : ~(3 | n ) ( (4 | n )}
d. D = { n ( N : n ( 3 (mod 4)}
e. E = { n ( N : n ( 3 (mod 9)}
f. F = { n ( N : n ( 3 (mod 4) ( n ( 3 (mod 9) }
g. G = { n ( N : ((m ( N ) n = m2}
h. H = { n ( N : (((m ( N ) n = m2) ( (((s ( N ) n = 2s )}
i. I = { x ( N : ((y ( N )( x2 + y2 < 50 )}
j. J = { x ( N : ((y ( N )( x + y2 = 13)}
5. Prove:
a. Every element of A (in problem 4a, above) is even.
b. No element of B (in problem 4b, above) is divisible by 9. (Hint: prove this by contradiction.)
c. No element of C (in problem 4c, above) is divisible by 24.
d. Every element of D (in problem 4d, above) is odd.
e. Every element in E (in problem 4e, above) is divisible by 3.
f. No element of F (in problem 4f, above) is divisible by 9.
6. Prove, by induction, that there is no “typical” natural number. Hint: what is meant by typical? That it has no special properties that distinguish it from other natural numbers. So why is 1 not “typical”?
Section 3.4 Collections of sets subscripted by {1, 2, 3, … n}
We look at a collection of sets A1, A2, A3, …, An. By the symbols [pic]and [pic]we mean sets defined as follows.
Definition: [pic]= {x | ( k ( {1, 2, … , n}, x ( Ak}.
Definition: [pic]= {x | ( k ( {1, 2, … , n} such that x ( Ak}.
Example: These idea are almost too easy for an examples, but it will take at least one before we know that. Is that a contradiction? A1 = {1, 2, 3, 4, 5, 6, 7, 8}, A2 = {2, 4, 6, 8, 10} and A3 = {3, 6, 9}. Then [pic]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Why is 4 in [pic]? Because 1 ( {1, 2, 3} and 4 ( A1. Why is 8 ( [pic]?
Make sure you understand why this statement is true:[pic]= {6}.
Let’s get the working definition of these things on the table
x ( [pic]( (( k ( {1, 2, 3, …, n}) x ( Ak.
x ( [pic](
x ( [pic](
x ( [pic](
Example: Prove: B ( [pic]( [pic].
There is a usual attack for “(” proofs. Let p be an element of the “left” and show it is in the “right”. So our given is: p ( B ( [pic].
p ( B ( [pic]
p ( B and p ( [pic].
p ( B.
p ( [pic].
(( k ( {1, 2, …, n}) p ( Ak.
p ( Ai , for some i.
p ( B and p ( Ai , for some i.
(( k ( {1, 2, …, n}) p ( B ( Ak.
p ( [pic]
Let’s prove: [pic]( B ( [pic].
p ( [pic]
Assignment:
In problems 1-6, identify the sets. That is, what are the elements? Note [2, 4.5] = {x ( R | 2 ( x ( 4.5}. (R is the set of real numbers.) Thus, for example, 2.3 is in this set.
1. [pic]= 2. [pic]=
3. [pic]= 4. [pic]
5. [pic]= 6. [pic]
7. Let A1 = {2,5,13, 19}, A2 = {2, 13, 25, 37, 81}, A3 = {2, 4, 6, 9, 13, 16},
A4 = { x ( N: 2 < x < 14}. Find [pic]and [pic]
For problems 8 - 17, decide whether the statement is true for all sets A, B, and C, is false for all sets A, B, and C, or is true for some sets and false for others. In the first two situations, give a brief justification via Venn diagrams or an informal proof. In the last situation, give both some sets for which it’s true (and show that it is) and some for which it is false (and show it’s false).
8. (A – B) ( (B – A) = Ø 9. A = (A ( B) ( (A – B)
10. A ( (B ( C) ( B 11. A – (A – A) = Ø
12. A – (A – A) = (A – A) – A 13. A – (B – C) = (A – B) - C
14. A ( (B ( C) ( (A ( B) ( C 15. A ( Ø ( Ø
16. Ø ( A 17. Ø ( A
18. Prove: [pic]( B ( [pic].
19. Prove: B ( [pic]( [pic].
20. Prove by induction on n that, for all natural numbers n and all sets Ai,
(A1 ( A2 ( … ( An) = (An ( … ( A2 ( A1).
Section 3.5 Ordered Pairs, Cartesian Product, Power Set
Definition: If a, b ( U then we define the ordered pair (a, b) to be {{a}, {a, b}}.
If this seems to be a very bizarre definition, it is. Its sole purpose is to ensure that (a,b) = (c,d) if and only if both a = c and b = d. Check that this must be true.
Cartesian Product
Def: A ( B = {(a, b) | a ( A and b ( B}
(a, b) ( A ( B ( a ( A and b ( B.
(a, b) ( A ( B ( ~(a ( A and b ( B) ( a ( A or b ( B.
An element of a cartesian product is a pair, not a single element. This is essential when starting a proof involving them. So, below, the first step is not p ((A – C) ( (B – D)!
Example: Show : (A – C) ( (B – D) ( (A ( B) – (C ( D)
|1 |(a, b) ((A – C) ( (B – D) |Given |
|2 |a ( (A – C) and b ( (B – D) |Def. ( (1) |
|3 |a ( (A – C) | |
|4 |a ( A and a ( C | |
|5 |a ( A | |
|6 |a ( C | |
|7 |b ( (B – D) | |
|8 |b ( B and b ( D | |
|9 |b ( B | |
|10 |a ( C or b ( D | |
|11 |~(a ( C and b ( D) | |
|12 |(a, b) ( C ( D | |
|13 |a ( A and b ( B | |
|14 |(a, b) ( A ( B | |
|15 |(a, b) ( A ( B and (a, b) ( C ( D | |
|16 |(a, b) ( (A ( B) – (C ( D) | |
Definition. Given any set A, the power set of A, written P(A), is the set of all subsets of A. That is, P(A) = {B: B ( A}.
Example: P({a,b,c}) = { Ø, {a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.
Assignment:
1. Let A = {1, 2}, B = {a, b, c}Write out all the elements of
a. A ( B b. A ( A c. B ( A d. P(A) e. P(B)
Prove the following theorems:
2. Prove that, for all sets A, (a) Ø ( P(A) and (b) A ( P(A).
3. If A ( B, P(A) ( P(B).
4. P(A ( B) ( P(A) ( P(B).
5. P(A) ( P(B) ( P(A ( B).
6. What can you conclude from 4 and 5?
7. P(A) ( P(B) ( P(A ( B).
8. Show by a counter-example that P(A ( B) is not always a subset of P(A) ( P(B).
9. Let C ( A and D ( B, and E = {(x,y) ( A ( B | x ( C ( y ( D}. Prove that E ( C ( B.
10. If A has m elements and B has n elements, how many elements does A ( B have? Why?
11. Prove (A ( B) ( C ( (A ( B) ( C
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
12. Find the error in the following proof that (A ( B) ( (C ( D) ( (A ( C) ( (B ( D).
Explain why it is an error (what axiom or definition has been used incorrectly) and give a correct proof.
|1 |p ( (A ( B) ( (C ( D) |Given |
|2 |p ( (A ( B) or p ( (C ( D) |Definition of ( (1) |
|3 |p ( A ( B |Case 1 (2) |
|4 |p ( A and p ( B |Definition of ( (3) |
|5 |p ( A |Simp (4) |
|6 |p ( A or p ( C |Add (5) |
|7 |p ( A ( C |Definition of ( (6) |
|8 |p ( B |Simp (4) |
|9 |p ( B or p ( D |Add (8) |
|10 |p ( B ( D |Definition of ( (9) |
|11 |p ( A ( C and p ( B ( D |Conj (7, 10) |
|12 |p ( (A ( C) ( (B ( D) |Definition of ( (11), end case 1 |
|13 |p ( (C ( D) |Case 2 (2) |
|14 |p ( C and p ( D |Definition of ( (13) |
|15 |p ( C |Simp (14) |
|16 |p ( A or p ( C |Add (15) |
|17 |p ( A ( C |Definition of ( (16) |
|18 |p ( D |Simp (14) |
|19 |p ( B or p ( D |Add (18) |
|20 |p ( B ( D |Definition of ( (19) |
|21 |p ( A ( C and p ( B ( D |Conj (17, 20) |
|22 |p ( (A ( C) ( (B ( D) |Definition of ( (21), end case 2 |
13 (a) Find the error in the following proof that (A ( C) - (B ( D) ( (A - B) ( (C – D). Explain why it is an error (what axiom or definition has been used incorrectly).
|1 |(a,b) ( (A ( C) - (B ( D) |Given |
|2 |a ( A and b ( C |Definition of ( (1) |
|3 |a ( B and b ( D |Definition of ( (1) |
|4 |a ( A |Simp (2) |
|5 |b ( C |Simp (2) |
|6 |a ( B |Simp (3) |
|7 |b ( D |Simp (3) |
|8 |a ( A and a ( B |Conj (4, 6) |
|9 |b ( C and b ( D |Conj (5, 7) |
|10 |a ( A – B |Definition of A – B (8) |
|11 |b ( C – D |Definition of A – B (9) |
|12 |a ( A – B and b ( C – D |Conj (10, 11) |
|13 |(a,b) ( (A – B) ( (C – D) |Definition of ( (12) |
(b) (A ( C) - (B ( D) ( (A - B) ( (C – D) is, in fact, false. Give a counter-example. (One possibility would be to draw A and C as intervals (overlapping) on the x axis, and B and D on the y axis. Draw two versions, one for the left side, the other for the right. Then shade in the relevant sets.)
14. (a) Find the error in the following proof that (A ( C) ( (B ( D) ( (A ( B) ( (C ( D). Explain why it is an error (what axiom or definition has been used incorrectly).
|1 |(a,b) ( (A ( C) ( (B ( D) |Given |
|2 |a ( (A ( C) and b ( (B ( D) |Definition of ( (1) |
|3 |a ( (A ( C) |Simp (2) |
|4 |b ( (B ( D) |Simp (2) |
|5 |a ( A or a ( C |Definition of ( (3) |
|6 |a ( A |Case 1 of (5) |
|7 |b ( B or b ( D |Definition of ( (4) |
|8 |b ( B |Case 1 of (7) |
|9 |a ( A and b ( B |Conj (6, 8) |
|10 |(a,b) ( A ( B |Definition of ( (9) |
|11 |(a,b) ( A ( B or (a,b) ( C ( D |Add (10) |
|12 |(a,b) ( (A ( B) ( (C ( D) |Definition of ( (11), end case 1 |
|13 |a ( C |Case 2 of (5) |
|14 |b ( D |Case 2 of (7) |
|15 |a ( C and b ( D | Conj (13, 14) |
|16 |(a,b) ( C ( D |Definition of ( (15) |
|17 |(a,b) ( A ( B or (a,b) ( C ( D |Add (16) |
|18 |(a,b) ( (A ( B) ( (C ( D) |Definition of ( (17), end case 2 |
(b) (A ( C) ( (B ( D) ( (A ( B) ( (C ( D) is, in fact, false. Give a counter-example.
15. a. Prove (A ( B) ( (C ( D) ( (A ( C) ( (B ( D) using tabular format:
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
b. Prove (A ( B) ( (C ( D) ( (A ( C) ( (B ( D) using paragraph format.
16. Prove (A ( C) ( (B ( D) ( (A ( B) ( (C ( D)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
Notice that, putting 15 and 16 together, we’ve proved
(A ( C) ( (B ( D) = (A ( B) ( (C ( D).
17. Prove (A - B) ( (C - D) ( (A ( C) - (B ( D)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
|16 | | |
|17 | | |
|18 | | |
|19 | | |
|20 | | |
Chapter 4 Combinatorics
Section 4.1 Bit Strings and Recursive Definitions
Let’s take a short break from logic and proofs and look at some ideas that we sidestepped when we introduced truth tables. The problem of finding all possible input rows, to go under the P, Q, R columns.
A “bit” is either a zero or a one. A “bit string” is simply an expression of the form; 1100101, 11111 or 001.
S(j,k) is the number of bit strings which have (in some order) j 0s and k 1s.
Example: In a truth table with three input rows we recall there had to be 8 rows and they were 000, 001, 010, 011, 100, 101, 110, 111. These are all possible bit strings of length 3. S(3,0) = 1, S(2,1) = 3, S(1,2) = 3 and S(0,3) = 1. We see immediately that
S(3,0) + S(2,1) + S(1,2) + S(0,3) = 8.
One can see questions to be answered. For example, determine S(2,2). That is how many bit strings can you make with 2 0s and 2 1s. That’s not so easy, unless we simply list them and count. Let’s see if we can recognize a pattern. Each string contributing to the count of S(2,2) is of length 4. Some of them end in 0 and some end in 1. Well, if they end in 0, the first three entries must consist of 2 1s and a 0. There are S(1,2) = 3 of these. So the number of the strings counted by S(2,2) which end in 0 equals S(1,2). Similarly, the number of the strings counted by S(2,2) which end in 1 equals S(2,1). Therefore S(2,2) = S(2,1) + S(1,2). It's pretty clear that this argument extends to S(4,3) and we can see that S(4,3) = S(3,3) + S(4,2).
Notice that this formula does not make sense for S(3,0). We can write S(3,0) = S(3,-1) + S(2,0) but it is difficult to give a meaning to S(3,-1). On the other hand S(3,0) is the number of bit strings that can be constructed using 3 0s and 0 1s. It follows that S(3,0) = 1. Similarly, S(0,5) = 1 (and so does S(0,n) and S(n,0) for any n).
Example: Determine S(4,2). S(4,2) = S(4,1) + S(3,2) =
S(4,0) + S(3,1) + S(3,1) + S(2,2) =
S(4,0) + S(3,0) + S(2,1) + S(3,0) + S(2,1) + S(2,1) + S(1,2) =
1 + 1 + 3 + 1 +3 + 3 + 3 = 15
Fun is fun, but there must be an easier way. Consider the following table;
S(1,0) S(0,1)
(
S(2,0) S(1,1) S(0,2)
( (
S(3,0) S(2,1) S(1,2) S(0,3)
( ( (
S(4,0) S(3,1) S(2,2) S(1,3) S(0,4)
1 1
(
1 2 1
( (
S(3,0) S(2,1) S(1,2) S(0,3)
( ( (
And indeed we begin to see an old friend appearing. You might know this display as Pascal's triangle.
1 1
(
1 2 1
( (
1 3 3 1
( ( (
1 4 6 4 1
If we added a fifth row, it would be related to bit strings of length 5 and would tell us S(5,0) = 1, S(4,1) = 5, S(3,2) = 10 and so on. For the time being we will be content with this process of determining S(j,k), but finding S(6,9) would be tedious. Eventually we will need to find a more direct solution.
We are in a position to answer the following questions:
How many bit strings of length 6 have exactly two ones?
How many bit strings of length 6 have at least two ones?
Example: Assume that you have six people in an office and you wish to choose two to assign to a project. How may way can you make the choice. For brevity, we designate the individuals by a, b, c, d, e, f. Then 101000. Represents the choice of a and c working on the project. There you go. Every bit string of 4 0s and 2 1s represents a choice. The number of ways to assign the project is simply S(4,2).
Notice that the fact that S(4,3) = S(3,3) + S(4,2), which we observed on the last page, is not a special case, but describes one way of getting later rows in Pascal’s triangle. S(4,3) is on the seventh row of Pascal’s triangle, and just above it (on the sixth row) to its left is S(4,2) and to its right is S(3,3). So, we can get a succeeding row of Pascal’s triangle by putting 1s half a step to the right of the ends of the row above, and in all the inbetween places, we use this method, of adding the two items next to each other, and putting their sum below, inbetween them. That is, in general, S(n + 1,0) = 1 = S(0,n + 1) gives us the two ending 1s, and S(n + 1, k + 1) = S(n, k + 1) + S(n + 1, k) gives us a formula for getting all the inbetween elements of row n + k + 2 from row n + k + 1. This is reminiscent of induction, and indeed, it is a way of using induction to define objects. However, it has a different name: definition by recursion. That is, a definition given by giving a base case, and then how to get the next case from previous ones is called a recursive definition. Let’s look at some more recursive definitions.
We can define exponential functions recursively as follows:
For any a ≠ 0, let a0 = 1, and let an+1 = [pic].
This tells us, letting n = 0, that a1 = [pic], and then letting n = 1, a1+1 = [pic], and then letting n = 2, a2+1 = [pic], and so on: each one is defined from the previous one.
For a more interesting example, we can define the sequence 1, 3, 5, 7, 9, … recursively by: a1 = 1, an+1 = an + 2. Then, letting n = 1, we get a2 = a1 + 2 = 1 + 2 = 3; letting n = 2, we get a2+1 = a3 = a2 + 2 = 3 + 2 = 5; letting n = 3, we get
a3+1 = a4 = a3 + 2 = 5 + 2 = 7, and so on.
Still more interesting, we get the sequence 1, 2, 4, 7, 11, 16, … this way. Notice that, each time we’re adding the next higher integer: we add 1 to 1 to get 2, then we add 2 to the result to get 4, then we add 3 to the result, giving 7, etc. So, we define this sequence recursively by a1 = 1, an+1 = an + n. Check that this does give the correct sequence.
Not only can we define sequences this way, we can define all kinds of concepts. For example, we can define [pic] (which represents the product f(1) ( f(2) ( … ( (f(n)) by recursion, as follows: [pic] = f(1), [pic].
Similarly, we can define [pic] recursively:
Assignment:
1. Assume that you have 5 bins. The bins contain in sequence an unlimited number of a's, b's, c's d's and e's. You get to choose 8 letters. In how many different ways can this choice be made? The answer is S(4,8). How can you explain that?
2. List the first six rows of Pascal's triangle. Add up the members of each row. What is going on here. How many rows would there need to be in a truth table with 7 variables?
3. Define each of the following sequences recursively:
(a) 3, 6, 12, 24, 48, …. (b) 1, 3, 6, 10, 15, …
(c) [pic] , [pic], [pic], [pic], … (d) [pic], [pic], [pic], [pic], …
(e) 3, 1, -1, -3, -5, … (f) [pic], [pic], [pic], [pic], [pic], …
4. Define recursively
(a) [pic] , which represents the sum of n numbers, a1, a2, a3, … , an.
(b) [pic].
5. The sequence a1, a2, a3, … is defined recursively as follows:
a1 = 0; for every n ( N, an+1 = an + n.
Prove by induction that for every n, an = n (n – 1)/2.
6. The sequence a1, a2, a3, … is defined recursively as follows:
a1 = 0; for every n ( N, an+1 = 2 an + n.
Prove by induction that for every n, an = 2n – n – 1.
7. The sequence a1, a2, a3, … is defined recursively as follows:
a1 = 2; for every n ( N, an+1 = (an)2.
Prove by induction that for every n, an = [pic].
8. The sequence a1, a2, a3, … is defined recursively as follows:
a1 = 2; for every n ( N, an+1 = 2 an – n.
Prove by induction that for every n, an = n + 1.
Section 4.2 Factfunction
We are about to define a function F:{0,1,2,3,4, …} ( {0,1,2,3,4, …}. We are going to use a process similar to induction to make the definition. That is, I’ll tell you what F(0) is and then assuming that you know F(n), I will tell you how to find F(n+1). This is called a “recursive definition” of a function. Here goes.
F(0) = 1
F(n+1) = (n + 1)[pic]F(n)
The question is, have I really told you anything at all? Let’s see.
What is F(1)? Let n = 0 in F(n+1) = (n + 1)[pic]F(n). What is the resulting equation?
What is F(2)? Let n = 1 in F(n+1) = (n + 1)[pic]F(n). What is the resulting equation?
What is F(3)?.
So we see that F(5) = 5[pic] F(4) = 5[pic]4[pic]F(3) = 5[pic]4[pic]3[pic]F(2) = 5[pic]4[pic]3[pic]2[pic]1 = 5!.
=
Example: 3! = 3(2!) = 3(2(1!) = 3(2(1(0!)= 3(2(1(1 = 6
4! = 4(3!) = 4(6
You probably already knew that 5! is a short way of writing the product of the first five positive integers. That is 5! = 5(4(3(2(1. Similarly 3!2! = 3(2(1(2(1. So 3!2! = 12 but in most of the following we are more interested in the pattern than the value. For that reason we keep the 1’s in an expression of the form 3(2(1(2(1 even though they don’t change the value. Don’t forget that 0! = 1. Why we have this counterintuitive equation may become more apparent as you work these problems.
Write as n! for some n.
8(7! 21(20! 4(5! + 2(5! 8(10! + 3(10! 4(12! + 5(12! + 4(12!
Which of the below is a different pattern from the other three? In English, please explain why.
[pic] [pic] [pic] [pic] [pic]
Evaluate each of the following.
[pic] [pic]
[pic] [pic]
[pic] [pic]
One handy trick is that 8(7! = 8!. Why would you find this useful?
Ex. [pic] = [pic] = [pic] = [pic]
Perform the operation: [pic]
Assignment: perform the operation:
1a. [pic] b. [pic] c. [pic] d. [pic]
Ex. We can easily demonstrate that [pic] = [pic]
[pic] = [pic] = [pic] = [pic] = [pic] = [pic]
2. Investigate which of the following are true and prove your conclusions.
a. [pic]+[pic] = [pic] b. [pic]+[pic] = [pic] c. [pic]+[pic] = [pic]
3. Complete each of the following maintaining the pattern of the true statements in the problem above.
a. + = [pic]
b. + = [pic]
c. + = [pic]
4. Write as the sum of three fractions expanding the pattern in problems 2 and 3. Show why your answer works.
+ + = [pic]
5. Write as the sum of four fractions.
+ + + = [pic]
Our objects have a factorial on top, several factorials on the bottom and the sum of the numbers on the bottom equal the number on the top. And we can display the sum relationship in the following diagram.
[pic] [pic]
/ \ / \
[pic] [pic] [pic]
/ \ / \ / \
[pic] [pic] [pic] [pic]
/ \ / \ / \ / \
[pic] [pic]
We know that S(j,k) = S(j-1,k) + S(j,k-1). Each bit string with j zeros and k ones either begins in zero or one. If it begins in zero it can be thought of as a bit string with j-1 zeros and k ones with a zero appended. If it begins in one it can be thought of as a bit string with j zeros and k-1 ones with a one appended. We are now in position to give a proof of the theorem that S(j,k) = [pic]. Note that another common notation for S(j,k) is [pic] Definition:[pic] = [pic] is the binomial coefficient, and is read “n choose j.
Theorem: S(j,k) = [pic] = [pic] = [pic].
Proof: Let n = j + k; we’ll do the proof by induction on n.
If n = j + k = 1, S(j,k) = S(0,1) = S(1,0) = 1. But [pic] = 1 and [pic]= 1.
Assume that S(j,k) =[pic] is true when j + k = n. Suppose now that j + k = n + 1. Then
S(j,k) = S(j-1,k) + S(j,k-1) = (using the fact that, since j + k = n + 1, j – 1 + k = j + k – 1 = n, and thus we can use our assumption on both S(j-1,k) and S(j,k-1))
[pic] + [pic] = [pic] + [pic] =
[pic] = [pic] = [pic]
How do we use this information? Let's look at an Example.
Ex. How many subsets of size 7 are there in a set of size 10? Since each bit string with 7 ones and 3 zeros can be use to choose a unique subset, the answer is S(7,3) which we now know is[pic] = [pic] = 10[pic]3[pic]4 = 120.
Make sure that you reread the previous pages and are able to answer the questions posed throughout.
6. In the expansion of (a + b)(c + d)(e + f) you need to insure that you form all possible distinct products choosing one element from each of the three factors. How could bit strings be used in this process?
|a ( b |c ( d |e ( f |Product |
|0 |0 |0 | |
|0 |0 |1 | |
|0 |1 |0 | |
|0 |1 |1 | |
|1 |0 |0 | |
|1 |0 |1 | |
|1 |1 |0 | |
|1 |1 |1 | |
7. Use the technique of problem 7 to determine the expansion of (p + y)3.
|p ( y |p ( y |p ( y |Product |
|0 |0 |0 | |
|0 |0 |1 | |
|0 |1 |0 | |
|0 |1 |1 | |
|1 |0 |0 | |
|1 |0 |1 | |
|1 |1 |0 | |
|1 |1 |1 | |
So (p + y)3 =
8. Use the theorem of this section to show that if p = m + n, where p is prime and m and n are both at least 1, then p | S(m,n).
Section 4.3 The Binomial Theorem
We are now in a position to state and prove the binomial theorem.
Binomial Theorem. Let a, b ( R and n ( N. Then
[pic]
Proof: By induction on n. If n = 0, this says [pic]. Since the only value k can have is 0, ak = a0 = 1, b0-k = b0 = 1. [pic] = S(0,0) is the number of bit strings with no 0s and no 1s: there is exactly one, the empty string (the string with nothing in it). So the right side equals 1, as does the left side.
Assume the theorem is true for some particular value of n, say N. We need to show it is true for the next value, n = N + 1. So let’s start with what we’re given, the theorem in the case n = N:
[pic]. Multiplying both sides of the equation by (a + b), we get
[pic]. Simplifying the left side, we get
[pic], so the left side looks like the theorem for the case
n = N + 1. Now we need to work on the right side. Distributing the sum across (a + b), we get [pic]. Now we distribute the a and b across the sums they’re multiplied by:
[pic]. We now want to put the two right-side sums back together. But we can’t, as is, because the as and bs have different exponents. But the exponents aren’t really all that different. To see this, let’s look at one example, when N = 3. In that case, the right side of the equation is:
[pic]
Notice that a1b3 appears in both sums: as the first term in the first sum, and the second term in the second sum. So we can put the sums together, except for the first term of the second sum and the last term of the first sum:
[pic][pic]. But N – k + 1 = (N +1) – k, and
[pic] = S(N-(k-1),k-1) + S(N-k,k), which is the right side of the identity (see p. 65) S(j,k) = S(j-1,k) + S(j,k-1), in the case where j is replaced by N-(k-1). So
[pic] = S(N-(k-1),k) = [pic]. Putting this in the above formula,
[pic]. We’re almost there. Now, every [pic] and every [pic] equal 1; so we can replace [pic] by [pic] and we can replace [pic] by [pic]. Doing this gives us
[pic]. But look: those last two terms can be put in the sigma, because they’re the case of k = N + 1 and k = 0, respectively. So we get [pic], which is exactly the n = N+1 case of our theorem. Whew! We’re done!
Assignment:
1. Expand (a + b)5 without multiplying it out (using the Binomial Theorem).
2. What is the coefficient of a7b8 in the expansion of (a + b)15 ?
3. What is the coefficient of x4 in (x + 1)9 ? (Use the Binomial Theorem; what is a? b?)
4. What is the coefficient of x5 in (x + 3)9 ? (Be careful: the power of 3 is also part of the coefficient.)
5. What is the coefficient of x6 in (2x + 3)9 ?
6. What is the term with x7 in it in (2x - 3y)9 ?
7. What is the term with x21 in it in (2x3 + 3y)9 ?
8. What is the term with x14 in it in (2x2 - 3y3)9 ?
9. Prove [pic] = [pic]. How is this related to Pascal’s triangle?
10. Prove, by induction on n, that [pic].
11. Prove [pic] quickly by using the binomial theorem. (Hint: 1 + 1 = 2.)
12. Prove [pic]quickly by using the binomial theorem with the right values of a and b.
13. Let An = {m ( N | m ≠ 1 ( m is a binomial coefficient in the expansion of (a + b)n}.
a. Write out the elements of A15; of A10.
b. Find a common property of all elements of A15 and check if some variation of this property holds true of all elements of A10 also. Then, make a conjecture based on your observations, and check it for several additional An.
Chapter 5 Functions and Permutations
Section 5.1 Relations
A relation R on a set S is a subset of [pic]; that is, it is a collection of ordered pairs of elements of S. For example, consider the set of points {(x2,x)|x ( R}. One can graph this relation: it is the points on the graph of x = y2
[pic]
This relation is not a function (we’ll define functions more carefully in our next class) because there are two values of y for each value of x (except 0). But, since it’s a subset of [pic], it’s a perfectly good relation on the real numbers.
If an ordered pair (x,y) ( R, then we usually write it xRy and say x is related to y by R. Given any relation R, we can define the inverse relation R-1 by (x,y) ( R-1 if and only if (y,x) ( R . Thus, the inverse relation interchanges the first and second variables.
There are four properties that relations may have that are frequently studied in mathematics. A relation R on a set S is called reflexive if, for all x ( S, xRx. It is called symmetric if, for all x,y ( S, xRy ( yRx. It is antisymmetric if (xRy ( yRx) ( x = y. It is called transitive if for all x,y,z ( S, xRy ( yRz ( xRz. A relation that is reflexive, symmetric, and transitive is called an equivalence relation. For example, equality of numbers (or sets, or just about anything) and similarity and congruence of triangles are equivalence relations.
Example: Let S be the set of natural numbers, and let the relation R be “less than or equal to.” Then (x,y) ( R if and only if x < y. Thus, (3,8) ( R because 3 < 8. This relation is reflexive. We can prove this in one step. To prove it, we must prove that for all x ( N, x < x. Since x = x, this is true. This R is not symmetric, because, for example, 3 < 8 but ~ 8 < 3. It is antisymmetric: if x < y and y < x, then x = y. It is also transitive: If x < y and y < z, then x < z.
Assignment:
For each of the following relations, (i) give three pairs that are in the relation, and three pairs that are not in the relation; (ii) determine whether or not the relation (a) reflexive, (b) symmetric, (c) antisymmetric, (d) transitive. Give brief explanations both in the case the relation has the property, and when it doesn’t.
1. Let S = R, and R be the relation “less than.”
2. Let S = Z, and R be the relation “greater than or equal to.”
3. Let S = Z, and R be the relation “divides.”
4. Let S be the set of all straight lines in the plane, and R be the relation “parallel to.” (We’ll say that a line is parallel to itself.)
5. Let S be the set of all straight lines in the plane, R be the relation “perpendicular to.”
6. Let S = Z, and R be the relation “congruent to (mod 11).”
7. Let S = Z, and let R(x,y) = {(x,y) | x + y is even}.
8. Let S = Z, and let R(x,y) {(x,y) | x + y is odd}.
9. Let S = R, and let R(x,y) = {(x,y) | x = 2y}.
10. Let S = P(N), and let R(x,y) = {(x,y) | x ( y}.
Section 5.2 Functions
We are all comfortable working with functions such as f(x) = x2. These are commonplace in algebra and calculus. They are equally useful in more advanced math courses. However, for your future mathematics courses you need to need to broaden your ideas about the nature of functions.
Definition: Suppose A and B are sets. We write f : A ( B, read f is a function from A to B, if
1) f ( A ( B
2) ((x ( A) (( y ( B)( (x, y) ( f ). (Roughly translates to everything in A is used.)
3) ((x, y, y’ )(((x, y) ( f ( (x, y () ( f ) ( y = y (). (Nothing in A is used twice.)
A is called the domain of the function, and B is called the codomain. Generally we will write f (x) = y rather than (x, y) ( f .
Example: The picture to the right represents [pic]
f :{1, 2, 3} ( {4, 5, 6}, where f = {(1, 6), (2, 6), (3, 6)}. The domain is {1,2,3}; the codomain is {4,5,6}. The rule for this function is f (x) = 6.
Example: If A = {1, 2, 3} and B = {a, b, c, d}, then f = {(1, a), (2, b), (3, a)} is considered a function with domain A and codomain B. The image of f is {a, b}. To relate these ideas to older notions of functions, we can write f(1) = a, f(2) = b and f(3)= a. What is the rule? How about f(x) = xth letter of “aba”.
A rule is not really necessary for a function. As the definition above shows, functions are simply certain types of sets. However, for the purpose of your undergraduate mathematics courses, functions are specified by giving a domain, a codomain, and a rule that tells you, given an element of the domain, which element of the codomain you are mapping it to. The domain and the codomain must be sets, but they can be any kind of set: a set of letters, or names, or numbers, or even a set of ordered pairs. (In MA225, multivariable calculus, the domain is often the plane, that is, R ( R. As a result, elements of the domain are ordered pairs of real numbers.) The only thing needed to make sure you have a function is to be sure that the rule works on everything in the domain, and that the result of applying the rule always gives you something in the codomain.
Assignment: Look at each of the following situations and decide if it is possible to use one or more functions to describe it. If it is, describe your function(s) giving domain, codomain, and rule associating each element in the domain with something in the codomain. If it is not possible to describe it using functions, explain why not.
1. The set of all ordered pairs, (x,2x+1), where x runs through the set of all integers.
2. The sequence of numbers 2n + n3, where n = 1, 2, …
3. [pic]
4. y4 = x2.
5. “Monmouth University has a very good basketball team.”
6. Look at the real number x. If it is positive, then write x2 + 1; if it is 0, then write 1; otherwise, write x + 1.
7. The set of ordered pairs (1,2x), x = 1, 2, …,100.
8. x2 + 3x + 2 = 0.
9. 2n > n2 + 3n, n = 1, 2, …
10. [pic]
11. A square in the plane, centered at the origin, is rotated clockwise by 90 degrees.
12. An analysis of the US Constitution, giving the frequency of occurrence of each letter of the alphabet.
13. 2x3y - [pic] = 2.
14. The set of ordered pairs, (x2,x2), where x runs through the integers from 1 to 100.
15. The set of ordered pairs (x,y), where x, y are any rational numbers.
16. [pic]
17. t is a real number and
x = t3 + 1
y = 1 – 3t + 2t4
18. A swimmer starts from the shore and swims to the other side of the lake.
19.
|Name |Owed |
|Sue |$17 |
|John |6 |
|Sam |27 |
|Bill |0 |
|Iris |6 |
|Eve |12 |
|Henry |14 |
|Louis |6 |
|Jane |12 |
20. “ELPRHZAUPQDRMW”
21. Take a real number x. Roll a pair of dice, and add the result to the value of x.
[pic]
22.
Section 5.3 Functions: one-to-one, onto, bijections
Definition: A function f:A ( B is said to be onto if y ( B ( ( x ( A such that (x,y) ( f.
Rephrase: f:A ( B is onto if each element in B has a member of A sent to it.
Rephrase: f:A ( B is onto if each y in B has some member x in A such that f(x) = y.
Rephrase: f:A ( B is onto if for each y in B there is some x such that f(x) = y and x ( A.
Definition: A function f:A ( B is said to be one-to-one if (a, c) and (b, c) ( f ( a = b.
Rephrase: f:A ( B is one-to-one different things are sent to different things.
Rephrase: f:A ( B is one-to-one if f(a) = f(b) ( a = b.
Rephrase: f:A ( B is one-to-one if a ( b ( f(a) ( f(b).
Definition: A function f: A ( B is a bijection if it is both one-to-one and onto.
Examples: Let f and g both have domain and codomain the set of all real numbers, and let their rules be f (x) = x2, g(x) = x3. f is neither one-to-one nor onto. To see that it is not one-to-one we only need to observe that f (-3) = f (3), for example (and in general, f (a) = f (-a), for all real numbers a – but ONE example where two different inputs give the same output is enough to make it not one-to-one). So see that it is not onto, we just need to observe that nothing is sent to any negative real number. However, if we change the codomain to being only the non-negative real numbers, then f is onto; and if we change the domain to being only the non-negative real numbers, then f is one-to-one. So one-to-one and onto are not properties only of the rule, but also of the domain and codomain chosen. g, on the other hand, is a bijection: for any real number b in the codomain, there is something in the domain that maps onto b: in particular, the cube root of b. (The cube root is defined for both positive and negative real numbers, unlike the square root.) Further, if g(a) = g(b), then a3 = b3, and taking cube roots of both sides, a = b. This shows that g is one-to-one.
One-to-one is also called injective, onto is also called surjective. A bijection is also called a one-to-one correspondence.
Assignment:
1. Let f : Z ( Z(Z be defined by f (x) = (x-3, x+2). What is f (5)?
2. Let A = {1, 2, 4, 5} and B = {6, 7, 9}. Decide, for each of the following sets of ordered pairs, whether it is a function from A to B. Explain your decision.
(a) {(1,9), (2,7), (4,6), (5,9)}
(b) {(1,9), (2,9), (5,7)}
(c) {(1,6), (2,6), (4,6), (5,6)}
(d) {(1,7), (2,7), (4,9), (5,7), (2,9)}
(e) {(1,6), (2,7), (4,8), (5,9)}
3. Let A = {1, 2, 4, 5} and B = {6, 7, 9, 12, 15}. Decide, for each of the following sets of ordered pairs, whether it is a function from A to B. Explain your decision.
(a) {(1,15), (2,12), (4,9), (5,7), (2,6)}
(b) {(1,9), (2,12), (4,15), (5,6)}
(c) {(1,12), (2,10), (4,9), (5,7)}
(d) {(1,15), (4,12), (5,6)}
(e) {(2,9), (1,9), (5,9), (4,9)}
4. Let A = {1, 2, 4, 5} and B = {6, 7, 9, 15}. Decide, for each of the following sets of ordered pairs, whether it is a function from A to B. Explain your decision.
(a) {(2,15), (1,9), (5,7), (4,6)}
(b) {(1,15), (2,7), (4,6)}
(c) {(1,15), (2,7), (4,9), (2,6)}
(d) {(1,7), (2,6), (4,15), (5,7)}
(e) {(1,15), (2,6), (4,9), (5,8)}
5. For each of the sets of ordered pairs in problem 2 that is a function from A to B, decide whether it is one-to-one, and whether it is onto. Explain your decision.
6. For each of the sets of ordered pairs in problem 3 that is a function from A to B, decide whether it is one-to-one, and whether it is onto. Explain your decision.
7. For each of the sets of ordered pairs in problem 4 that is a function from A to B, decide whether it is one-to-one, and whether it is onto. Explain your decision.
In 8 – 16, Give brief explanations of how you get your answers.
8. How many functions f:{1,2,3,4,5} ( {1,2,3,4,5} exist?
9. How many of the functions f:{1,2,3,4,5} ( {1,2,3,4,5} are one-to-one?.
10. How many of the functions f:{1,2,3,4,5} ( {1,2,3,4,5} are onto?.
11. How many functions f:{1,2,3,4,5} ( {1,2,3,4} exist?
12. How many of the functions f:{1,2,3,4,5} ( {1,2,3,4} are one-to-one?.
13. How many of the functions f:{1,2,3,4,5} ( {1,2} are onto?.
14. How many functions f:{1,2} ( {1,2,3,4,5} exist?
15. How many of the functions f:{1,2} ( {1,2,3,4,5} are one-to-one?.
16. How many of the functions f:{1,2} ( {1,2,3,4,5} are onto?
For problems 17-22, before doing each, rephrase it in terms of a question about functions.
17. How many bit strings of length 5 are there?
18. How many bit strings of length 5 have exactly 3 ones?
19. How many bit strings of length 5 have at least 3 ones?
20. How many ways can all of the six blocks AAABBC be placed in a row?
21. How many ways can all of the six blocks AAABBB be placed in a row?
22. How many ways can all of the six blocks AABBCC be placed in a row?
Example: 22 mod 5 is a numeral which represents the remainder when 5 divides 22. That is 22 mod 5 = 2. What is 47 mod 11 = 3. We can define functions using mod.
If g(x) = x + 3 mod 5 then g:{0,1,2,3,4} ( {0,1,2,3,4}. g = {(0,3),(1,4),(2,0),(3,1),(4,2)}. Wow! g is one-to-one and onto.
Let h(x) = 2x + 1 mod 5. Then h = {(0,1),(1,3),(2,0),(3,2),(4,4)}.
Let f (x) = x2 mod 5. Then f : {0,1,2,3,4} ( {0,1,2,3,4}
f (0) = 0, f (1) = 1, f (2) = 4, f (3) = 4, f (4) = 1.
Definitely not onto.
Let f (x) = x2 +2x
f (0) = 0, f (1) = 3, f (2) = 2, f (3) = 0, f (4) = 4. Also not onto.
23. Does there exist a quadratic function f : {0,1,2,3,4} ( {0,1,2,3,4} that is onto?
24. Is f (x) = x3 + x2 + 2x mod 5 one-to-one?
25. Is f (x) = x3 + 2x2 + 3x mod 5 one-to-one?
26. Is f (x) = x3 + 2x2 + x mod 5 one-to-one?
Section 5.4 Proofs of one-to-one and onto
Example: Suppose f : Z ( Z is defined by f (x) = x + 3. Show f is one-to-one.
|1 |f(a) = f(b) |given |
|2 |a + 3 = b + 3 |definition of f (1) |
|3 |a = b |algebra (2) |
|4 |f is one-to-one |definition of one-to-one (1-3) |
Next, show f is onto. To show this, we start with an element in our codomain and try to find something in the domain that maps onto it. So y ( Z is our given, and f(x) = y ( x ( Z is what we want to get. Working from bottom to top, if f(x) is going to equal y, that means, using the definition of f, that x + 3 = y. Subtracting 3 from both sides, we see that x must equal y – 3. Since y is an integer, so is y – 3. Thus, x is in our domain. So now, we can put this together forwards in a proof:
|1 |y ( Z |given |
|2 |Let x = y - 3 |Introduction of new variable |
|3 |x ( Z |Definition of Z: if y is an integer, so is y - 3 |
|4 |f(x) = f(y – 3) |Property of equality (2) |
|5 |f(x) = (y – 3) + 3 |Definition of f (4) |
|6 |f(x) = y |algebra (5) |
|7 |f(x) = y ( x ( Z |Con(3,6) |
|8 |f is onto |definition of onto (1-7) |
Some functions are one-to-one but not onto, some are onto but not one-to-one, and some are neither. For example, consider the function above, but now from N to N. It is still one-to-one, but is no longer onto. The x defined on line 2 of the onto proof is not necessarily a natural number when y is a natural number. For example, if y = 2, x = -1, which is not in N. Thus, nothing in N maps onto 2, and the function is not onto.
Example: Show that f: Z ( Z defined by f(x) = 2x is one-to-one but not onto.
We show it’s one-to-one just as we did above:
|1 |f(a) = f(b) |given |
|2 | | |
|3 | | |
|4 | | |
To show it’s not onto, we just need to find one element of Z that f doesn’t map onto. Let’s find one:
Let’s do a more complicated example. Let f: (0,∞) → (0,1) be given by f(x) = [pic]. We’ll prove that f is a bijection.
One-to-one:
|1 |f(a) = f(b) |given |
|2 | |definition of f (1) |
|3 | |Algebra |
|4 | |Algebra |
|5 | |Algebra |
|6 | |Algebra |
|7 |a = b |Algebra |
| |f is one-to-one | |
Onto:
This one needs some backwards work to get a proof. We want to find, given any y in (0,1) (which is our B), an x in (0,∞), so that f(x) = y. That is, given y, we need to find an x so that f(x) = [pic] = y. That is, we need to solve [pic] = y for x. So let’s do so:
Now we’re ready for our proof:
|1 |y ( (0,1) |given |
|2 | |Introduction of new variable |
| |Let x = | |
|3 |x ( A | |
|4 |f(x) = f( ) |Property of equality (2) |
|5 |f(x) = (y – 3) + 3 |Definition of f (4) |
|6 |f(x) = y |algebra (5) |
|7 |f(x) = y ( x ( A |Con(3,6) |
| |f is onto | |
Assignment:
The purpose of these exercises is both to give you practice proving functions are one-to-one and onto, and to show that these properties are as dependent on domain and codomain as on the function’s rule.
Let f(x) = 2x + 1, g(x) = x3 – 2, h(x) = x – 4, j(x) = x2 + 2
1. If f: R ( R, show that f is (a) one-to-one and (b) onto.
2. If f: Z ( Z, show that f is (a) one-to-one and (b) not onto.
3. If f: Z ( odd integers, show that f is (a) one-to-one and (b) onto.
4. If f: N ( odd natural numbers, show that f is (a) one-to-one and (b) not onto.
5. If g: R ( R, show that g is (a) one-to-one and (b) onto.
6. If g: Z ( Z, show that g is (a) one-to-one and (b) not onto.
7. If g: {-2,-1,0,1,2}( {-10,-3,-2,-1,6}, show that g is (a) one-to-one and (b) onto.
8. If h: Z ( Z, show that h is (a) one-to-one and (b) onto.
9. If h: N ( N, show that h is not even a function.
10. If h: N ( Z, show that h is (a) one-to-one and (b) not onto.
11. If j: R ( R, show that j is (a) not one-to-one and (b) not onto.
12. If j: [0,() ( R, show that j is (a) one-to-one and (b) not onto.
13. If j: [0,() ( [2,(), show that j is (a) one-to-one and (b) onto.
14. If j: R ( [2,(), show that j is (a) not one-to-one and (b) onto.
Section 5.5 Composition of functions, inverses
Definition: Given two functions h: A ( B and g: B ( C, the composition of the functions g and h, written g[pic]h is defined by g[pic]h = {(a,c) ( A(C | (( b ( B) ( (a,b) ( h and (b,c) ( g)}. In other words, g[pic]h(x) = g(h(x)).
Example: Let f: R ( R be defined by f(x) = x3 + x, and g: R ( R be defined by
g(x) = sin x. Then f[pic]g = sin3x + sin x, and g[pic]f = sin (x3 + x). f is onto, but not one-to-one. g is neither one-to-one nor onto. Neither f[pic]g nor g[pic]f is one-to-one or onto.
If a function f : A ( B is a one-to-one correspondance, it has an inverse, called f -1, from B to A, with the property that f -1[pic]f(x) = x for all x in A, and f [pic] f -1(y) = y for all y in B.
Example: f : Z ( Z given by f(x) = x + 3 is a one-to-one correspondance. To find its inverse, start with the equation f [pic] f -1(y) = y. Apply the definition of composition, then of f: f [pic] f -1(y) = f(f -1(y)) = f -1(y) + 3 = y. Solving this last for f -1(y), we get
f -1(y) = y – 3.
Assignment.
In problems 1 – 9, Let f, g, and h from Z to Z be defined by f(x) = x + 3, g(x) = 2x, h(x) = x3 - x. Find each of the following compositions, and, for 1-4 only, determine (with proof) whether it is one-to one and whether it is onto:
1. f[pic]g 2. g[pic]f 3. f[pic]f 4 g[pic]g 5. f[pic]h 6. h[pic]f 7. h[pic]g 8. g[pic]h 9 h[pic]h.
10. Suppose f(x) = x3 + 2x2 + 3x mod 5 and g(x) = x3 + 2x2 + 3 mod 5. List the pairs in each of the following. Which are one-to-one? Which are onto?
a) f[pic]g b) g[pic]f c) f[pic]f d) g[pic]g.
11. Let [pic] , and g(x) = x + 3. Assume the domain of f and g is the largest subset of R for which the formula can be calculated. What is the domain of f ? of g? Find f[pic]g and g[pic]f. What is the domain of each?
12. If g(x) = cos x, and f[pic]g(x) is the function given below, find f(x).
(a) 2 cos2x + 3 cos x – 4; (b) [pic] ; (c) [pic]
13. Decompose each of the following functions h(x) into two functions, f(x) and g(x) such that h(x) = f[pic]g(x): (a) h(x) = [pic] ; (b) h(x) = [pic] ;
(c) h(x) = [pic] (this last can be done in two different ways: give both possibilities)
14. Find the inverse of each of the following functions from R to R:
(a) f(x) = x – 4; (b) f(x) = 2x + 7; (c) f(x) = x3 + 4
Section 5.6 Image and pre-image
Definition: If X ( A and f : A ( B then f (X) ={y ( B | (( x ( X) (x, y) ( f } (or, more informally, {y ( B | (( x ( X) f (x) = y }. f (X), called the image of X under f (usually just abbreviated the “image of X” when it’s clear what map f is under discussion). It consists of all the objects in B that elements of X get sent to.
y ( f (X) means “something in X is sent to y”.
Example: Let f : N ( N by f (x) = x2. Further let X = {2, 3, 4}. Then f (X) = {4, 9, 16}. Why is 9 ( f (X)? Because 3 ( X and (3, 9) ( f.
Definition: Y ( B and f : A ( B then f -1(Y) = {x | (( y ( Y) (x, y) ( f} (or, more informally, {x ( A| f (x) ( Y }. f -1(Y) is called the pre-image of Y under f (usually just abbreviated the “pre-image of Y).
x ( f -1(Y) means “x is sent into Y”.
Generally, even if Y only has one element, f -1(Y) may have several elements. In particular, f is one-to-one if and only if for all y ( Y, f -1({y}) has just one element.
Example: Let f : N ( N be defined by f (x) = x2. Further let Y = {2, 3, 4}. Then f -1(Y) = {2}. Why is 2 ( f -1(Y)? Because (2, 4) ( f and 4 ( Y. Why is it the only element of
f -1(Y)? Because neither 2 nor 3 are squares of integers; that is, nothing in N is sent by f to either 2 or 3.
Assignment:
1. Let f : R ( R be defined by f (x) = x2 - 2. Find each of the following sets (square and round brackets denoting interval notation):
(a) f ([0,5]) (b) f ([-2,5]) (c) f ((-7,5]) (d) f ({3}) (e) f -1({3}) (f) f -1({-2})
(g) f -1({0}) (h) f -1({-3}) (i) f -1([-2,7]) (j) f -1((-2,7]) (k) f -1([-4,7]) (l) f -1([-1,7])
(m) f -1([3,7])
2. Prove f -1(Y) ( f -1(W) ( f -1(Y ( W)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
3. a. Prove f -1(Y ( W) ( f -1(Y) ( f -1(W) in tabular format.
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
b. Prove f -1(Y ( W) ( f -1(Y) ( f -1(W) in paragraph format.
4. f -1(Y) ( f -1(W) ( f -1(Y ( W).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
5. f -1(Y ( W) ( f -1(Y) ( f -1(W).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
| | | |
| | | |
6. f (X ( Z) ( f (X) ( f (Z).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
7. f (X) ( f (Z) ( f (X ( Z).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
8. f (X ( Z) ( f (X) ( f (Z).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
|11 | | |
|12 | | |
|13 | | |
|14 | | |
|15 | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
9. f -1(Y – W) ( f -1(Y) – f -1(W)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
10. f -1(Y) – f -1(W) ( f -1(Y – W)
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
|8 | | |
|9 | | |
|10 | | |
11. f (f -1(Y)) ( Y.
|1 |q ( f (f -1(Y)) | |
|2 |( p ( f -1(Y) and f (p) = q | |
|3 |p ( f -1(Y) | |
|4 |f (p) = q | |
|5 |f (p) ( Y | |
|6 |f (p) = q and f (p) ( Y | |
|7 |q ( Y | |
|8 | | |
12. Given: f : A ( B and X ( A. Get: X ( f -1(f (X)).
|1 | | |
|2 | | |
|3 | | |
|4 | | |
|5 | | |
|6 | | |
|7 | | |
| | | |
| | | |
| | | |
13. Given: f : A ( B, f onto and Y ( B. Get: Y ( f (f -1(Y))
|1 |Assume q ( Y | |
|2 |f is onto | |
|3 |(( x)(x ( A and f (x) = q) | |
|4 |p ( A and f (p) = q | |
|5 |f (p) = q | |
|6 |f (p) = q and q ( Y | |
|7 |f (p) ( Y | |
|8 |p ( f -1(Y) | |
|9 |p ( f -1(Y) and f (p) = q | |
|10 |(( p)( p ( f -1(Y) and f (p) = q) | |
|11 |q ( f (f -1(Y)) | |
14. Given: f : A ( B, f one-to-one and X ( A. Get: f -1(f (X)) ( X.
|1 |f one-to-one | |
|2 | p ( f -1(f (X)) | |
|3 |f (p) ( f (X) | |
|4 |(( x)( x ( X and f (x) = f (p)) | |
|5 |p( ( X and f (p() = f (p) | |
|6 |f (p() = f (p) | |
|7 |p( = p | |
|8 |p( ( X | |
|9 |p( = p and p( ( X | |
|10 |p ( X | |
Section 5.7 Permutations
Envision room with five chairs. Each chair is numbered; from one to five. There is one person sitting in each chair. In front of the room and visible to each person is displayed the following array.
[pic]
A bell sounds. At that instant, all five people stand up and move to the seat as indicated by the display. The person in chair 1 moves to chair 3. The person in chair 2 sits back down in chair 2. The person in chair 3 moves to chair 4 and so on. The total movement, as described by the array, is called a permutation.
Notice, that there is a difference between the permutation and the result of the permutation. For example, if you were in chair 1, when the bell rang, you would now be in chair 3. But if the bell sounds for a second time you would have to move to chair 4. So, a permutation is not which people are in which chairs but rather the action that rearranges them.
There is a natural way to combine two permutations to produce a third. This operation is called permutation multiplication. It is simply composition of functions. For example,
[pic][pic]=[pic].
From the two permutations being multiplied, the right one operates first. The left follows.
To see this, note that the right instruction causes the person in chair 1 to move to chair 4 and the left instruction causes him to move from 4 to 5. So he moves from 1 to 5 and we place a 5 under the 1. The person in chair 2 goes to chair 1 and then moves to chair 3. The net result is the person in chair 2 goes to chair 3. We say this as “2 goes to 1 and 1 goes to 3 so 2 goes to 3”.
The next definition puts the idea of permutations in more mathematically precise terms.
Definition: By a permutation on a set A is a function from A to A which is one-to-one and onto.
Usually we will only be considering permutations on sets of the form {1, 2, ... , n}. Since these sets are finite, functions on them are one-to-one if and only if they are onto.
In what sense is the permutation [pic] a one-to-one function? Let’s call it f. That is f = [pic]. Then, f (1) = 3, f (2) = 2, f (3) = 4, f (4) = 5 and f (5) = 1. So we can see that f is indeed a function; f : {1, 2, 3, 4, 5} ( {1, 2, 3, 4, 5}.
Example: : Let f = [pic] and g = [pic]
Following our method of multiplication
[pic][pic]=[pic]
Following our convention the right operand is applied first. In function notation we would write f[pic]g = [pic][pic] Looking at this as composition of functions,
f[pic]g (1) (= f (g(1))) = f (5) = 3 f[pic]g (2) = f (3) = 1
f[pic]g (3) = f (1) = 2 f[pic]g (4) = f (2) = 5
f[pic]g (5) = f (4) = 4
One permutation is special; it is called the identity permutation:
The identity permutation on A, called i, (or, when it might be ambiguous what A is, iA) is the permutation that takes every number to itself.
For example, if the set A is {1, 2, 3, 4, 5}, the identity permutation i is
[pic]
It is called the identity permutation because it acts as a multiplicative identity. That is, if you multiply any permutation f by it, you always get f back again. Try this with our f above:
[pic][pic]
[pic][pic][pic]
Since every bijection has an inverse, every permutation f has an inverse, called f -1.
The inverse, f -1, of a permutation f, is the permutation such that
[pic][pic]i.
f -1 is also a bijection, and is thus also a permuation. For example, for the permutation called f above,
[pic].
You can find f -1 easily by writing the bottom line on top and the top line on bottom, and then interchanging columns until the top line is in the right order.
Representing permutations by disjoint cycles
In addition to representing permutations by listing the values of the function, and by representing them as matrices, there is a more efficient way to represent them, as a product of disjoint cycles.
Example: The permutation g = [pic] can be represented as (1 5)(2 3 4)
One goes to five. Five goes to one. Two goes to three. Three goes to four. Four goes to two
Similarly [pic] can be written as (1 2 4)(3 5). (1 2 4) and (3 5) are referred to as cycles. That is, a cycle is a permutation f such that there is an element of {1,2,…,n}, call it a, such that for all x in {1,2,…,n}, either f (x) = x, or there is a k such that f (x) = f k (a), where f k (a) means f composed with itself k times, applied to a. If a permutation, for example, sends two to two, then the 2 does not appear in any cycle. Thus, we have the permutation below written first in matrix notation, and then in cycle notation:
[pic] = (1 4 3).
When writing a cycle it is customary to begin with the smallest number involved. To represent a permutation as a product of disjoint cycles, start with the smallest number that is moved by the permutation. (Usually this means starting with 1, but not if 1 is sent to 1.) The next number is what that permutation takes the first number to. Then you see what the permutation takes that to. Continue; the last number listed in the cycle is the one that the permutation sends back to the first number. Close the parenthesis. Then start the next cycle with the smallest number not yet listed that doesn’t get sent to itself. So with the permutation g in the above example, we start with 1. g(1) = 5. So the cycle starts “(1 5”. Now, g(5) = 1. We do not write “(1 5 1”; rather, we close the cycle: “(1 5)”. Next we move to 2, and start a new cycle: “(2 “. g(2) = 3; so the cycle becomes “(2 3”. g(3) = 4, and g(4) = 2. Thus, this cycle, when completed, is (2 3 4). Thus, the whole permutation g can be written as a product of disjoint cycles (because the cycles have no elements in common) g = (1 5) (2 3 4). Multiplication of permutations is not commutative, because composition of functions is not commutative. However, because the cycles are disjoint, you can commute them: g is also (2 3 4) (1 5).
Assignment:
1. Multiply the following permutations.
a) [pic][pic] b) [pic][pic]
c) [pic][pic] d) [pic][pic]
2. Write each permutation as a product of disjoint cycles.
a ) [pic] b) [pic] c)[pic]
3. Find the inverse of each of the following permutations.
a) [pic] b) [pic] c) [pic]
4. Prove, by induction on the number n of elements, that the number of permutations on the set {1,2,3, …, n} is n!
5. How many cycles of length n are there on {1,2,...,n}? Prove your answer by induction.
Section 5.8 Transpositions and the order of a permutation
Cycles of length two are called transpositions. Any cycle can be factored into transpositions. This factorization is not unique; there are many such factorizations.
For example, (1 2 3 4 5) = (1 5)(1 4)(1 3)(1 2) = (1 2)(2 3)(3 4)(4 5).
Definition: By a transposition we will mean a permutation that swaps exactly 2 members of {1, 2, ... , k}. By an elementary transposition we mean a transposition in which the two interchanged elements are adjacent.
Example: On the set {1, 2, 3, 4, 5} there are exactly 4 elementary transpositions. They are (1 2),(2 3),(3 4) and (4 5). We can factor (1 3) in to elementary transpositions in many ways. Here is one (1 3) = (1 2)(2 3)(1 2).
The order of a permutation f is the smallest positive power of f that produces the identity.
For example [pic]has order 6 since
[pic]= [pic], and no smaller power of [pic] gives this result.
Assignment:
1. Determine the order of each permutation in problem 2 in section 5.7.
2. Rewrite each of the permutations in problem 3 in section 5.7 in cycle form and determine the order of each. Attempt to generalize the relationship between cycle length and order of a permutation.
3. Write each permutation in problem 3 in section 5.7 as a product of transpositions.
4. Write each permutation in problem 3 in section 5.7 as the product of elementary transpositions.
Section 5.9 Odd and Even Permutations
The practice of reducing complex objects into simpler objects is repeated often in mathematics. For example, factoring natural numbers into primes or breaking a complicated function into simpler steps. We are interested in being able to factor transpositions into elementary transpositions. This technique is based on the following lemma.
Lemma: (k k + n + 1) = (k k + n)(k + n k + n + 1)(k k + n).
Proof: By examination.
Example: Let’s attempt to factor (1 5) into elementary transpositions using the above lemma. (1 5) = (1 4)(45)(1 4). But (1 4) = (1 3)(3 4)(1 3). So we have
(1 5) = (1 3)(3 4)(1 3)( 4 5) (1 3)(3 4)(1 3).
Next we write (1 3) = (1 2)(2 3)(1 2). Substituting once more we get
(1 5) = (1 2)(2 3)(1 2) (3 4) (1 2)(2 3)(1 2)( 4 5)(1 2)(2 3)(1 2) (3 4) (1 2)(2 3)(1 2).
This example contains the basis for a nice induction proof that transpostions can be written as a product of elementary transpoitions.
Lemma: Every transposition factors into an odd number of elementary transpositions.
Proof: We argue inductively. Consider the transpositions of the form (k k+1). Such a transposition is already written as an odd number of elementary transpositions. So we have the first step.
Now assume that, for some n, any transposition of the form (k k+n) can be factored into an odd number, say j, of elementary transpositions. We note that
(k k+n+1) = (k k+n)(k+n k+n+1)(k k+n).
It follows that (k k+n+1) can be factored into 2j + 1 elememtary tranposition.
The previous example led us to the development of a proof. Our next example demonstrates a simpler way of factoring (1 5) into elementary transpositions.
Example: (1 5) = (1 2)(2 3)(3 4)(4 5)(3 4)(2 3)(1 2). To see why this is true we need to remember that (1 5) sends the person in chair 1 to chair 5 and the person in chair 5 to chair 1. (4 5)(3 4)(2 3)(1 2) sends the person in chair 1 to chair 5 and slides the people in chairs 2, 3, 4 and 5 one chair to the left. Importantly, the person in chair 5 has been moved to chair 3. (1 2)(2 3)(3 4) moves the person in chair 4 to chair 1 and slides the people in chairs 1, 2 and one to the right. Notice that this factors (1 5) into an odd number of elementary transpositions.
Lemma: A product of an odd number of transpositions can be written as a product of an odd number of elementary transpositions.
Proof: Each transposition factors into an odd number of elementary transpositions. Each of the odd number of transpostions contributes an odd number of elementary transpositions. The number of the aggregate must be odd.
Lemma: A product of an even number of transpositions can be written as a product of an even number of elementary transpositions.
Example: Let f = [pic]. Then f = (1 3 4 5) is a single cycle. This cycle can be easily factored into transpositions. We notice that the person in chair one is to go to chair three. Our first transposition does just that (1 3). We will leave chair three fixed for the remainder of the construction. The person originally in chair three is now in chair one. It is his fate to end up in chair four and we now do that move. So far we have (1 4)(1 3). But, we have just move the person in chair four to chair one. Where should he go? Well, he should go to chair five. Therefore, (1 3 4 5) = (1 5)(1 4)(1 3). We have factored the cycle (1 3 4 5) into an odd number of transpositions and by the above lemmas we could factor it into an odd number of elementary transpositions. This is easy enough to do:
f = (1 2)(2 3)(3 4)(4 5)(3 4)(2 3)(1 2)(1 2)(2 3)(3 4)(2 3)(1 2)(1 2)(2 3)(1 2)
Notice also, the product of a transposition with itself is the identity. That is (1 2)(1 2) does not result in any person ending up in a new seat. It follows that f can be reduced considerably.
f = (1 2)(2 3)(3 4)(4 5)(1 2)
Notice, that after the simplification, we have again factored f into an odd number of transpositions. The next theorem says that factoring a given permutation into transpositions may be done in many ways, but if one way results in an even number of transpositions, then they all do and, of course, if one has an odd number, they all do.
Theorem 4.1: Suppose f is a permutation that factors into an odd number of transpositions. Then every factorization of f has an odd number of transpositions.
Proof: Assume f:{1, 2, ... , k}({1, 2, ... , k} is a permutation. Consider the relation > on the set {1, 2, … , k}. This relation is the subset of {1, 2, ... , k}({1, 2, ... , k} defined as {(a,b) | a > b }. As an example we write out the pairs in the case where k = 5.
{(2,1),(3,1),(4,1)(5,1),(3,2),(4,2),(5,2),(4,3),(5,3),(5,4)}
Next we form a product by taking the difference of each pair.
(2-1)(3-1)(4-1)(5-1)(3-2)(4-2)(5-2)(4-3)(5-3)(5-4)
In our example we have 10 pairs and corresponding factors. For a general k it is easy to see that we would have 1 + 2 + 3 + … + k-1 = (k-1)(k)/2 such factors. Further each integer from, 1 to k, appears in k ( 1 of the factors. We examine the effect of an elementary transposition on this product. We will see that it changes the sign.
Consider the elementary transpositions (j j+1) and its effect on the product. Each factor that is changed is one the following three types. One type consists of factors that contain j but not j+1, the second are those that contain j+1 and not j and finally the single factor (j ( (j+1)). (j ( (j+1)) simply becomes ((j+1) ( j) changing from 1 to -1. Next, we consider the first type of factor.
Assume (j ( a) is an original factor of the first type. We will show that (j+1 – a) must also be an original factor. j > a implies j + 1 > a. It follows that ((j+1) ( a) is an original factor. The effect of the elementary transposition (j j+1) is to interchange these two factors. This has no effect on the value of the product.
Similarly, if (a ( j) is an original factor then a > j. It follows that a ( j + 1. Since a ( j + 1 we have a > j + 1 and (a – (j+1)) is an original factor also. Again they are simply swapped. The net effect of any elementary transposition on the expression is a sign change.
The effect of applying a sequence of an odd number of elementary transpositions is going to be a change in sign. The effect of f acting on the product is the same unfactored as factored. Therefore, if f changes the sign it can only be factored into an odd number of elementary transpositions.
Because every permutation is thus always the product of an odd number of transpositions, or always the product of an even number of transpositions, we can make the following definition.
Definition: A permutation is even if it is the product of an even number of transpositions. A permutation is odd if it is the product of an odd number of transpositions.
Assignment:
1. Determine which of the permutations in problem 2 in section 5.7 are even, and which are odd.
2. Determine which of the permutations in problem 3 in section 5.7 are even, and which are odd.
3. a. Show that {f | f is an even permutation on {1, 2, …, n}} is closed under composition of functions (multiplication of permutations): that is, if f and g are even permutations, so is fg.
b. Show that {f | f is an odd permutation on {1, 2, …, n}} is not closed under composition of functions.
Chapter 6 Graph Theory
Section 6.1 Graphs
Definition: By a graph G we will mean G = (V, E) where V is a set of points called vertices and E is a set of edges such that E ( {{vj, vk} | vj, vk ( V and vj ( vk}. (Note: sometimes graphs are defined to allow vj = vk; when this happens, that type of edge is called a loop. However, in these notes, we will not allow loops in graphs.)
Example: G = ({1, 2, 3}, {{1, 2}, {1, 3}}). The vertices are numbered 1, 2 and 3. The edges are given by {1, 2} and {1, 3}.
[pic]
Definition: Kn , the complete graph of size n, is the graph
Kn = ({v1, v2, ... , vn}, {{vj, vk } | vj, vk ( V and vj ( vk}). It’s called the complete graph because all possible edges are included. Here is an example, the complete graph of size 4. Thus, K4 = ({1,2,3,4},{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}).
[pic]
Notice that graphs can be given several ways: they can be given by listing the vertices and edges, and they can be given by drawing them, making clear which intersections of edges are real – that is, correspond to vertices – and which are only because of how they’re drawn. Notice that the intersection of the edge between vertices 3 and 1, above, and the edge between vertices 2 and 4, is not really in the graph, since edges only intersect at vertices. We can redraw the graph so that these edges don’t intersect, and we call it the same graph, because the list of vertices and edges are the same:
[pic]
Notice that, because two drawings of the same graph can look different, we need a way of determining whether they in fact are the same graph. When a graph is given, the particular names of the vertices are unimportant. We could have named the vertices of K4 a, b, c, and d instead of 1, 2, 3, 4. Since is symmetric (all the vertices have the same connectivity to each other vertex), which vertex is names what doesn’t matter. But in the first graph in this section, if we rename the vertices so that the vertex that has two edges coming out of it is vertex 3, and the other two are named 1 and 2 (or, for that matter, a and b), it’s still the same graph. To capture that idea, we say two graphs G = (V, E) and
G ‘ = (V’,E’) are isomorphic if there is a one-to-one correspondence f from V to V’ with the property that {vi,vj} ( E ( {f(vi) , f(vj)}( E’. Thus, the two graphs below are isomorphic, with the correspondence f(a) = 2, f(b) = 3, f(c) = 4, f(d) = 5, f(e) = 6, f(f) = 7, f(g) = 1. To be sure, you must check every edge. For example, the edge {a,b} in the first graph maps, via f to {2,3}, and this is indeed an edge of the second graph. On the other hand, {a,c} is not an edge in the first graph, and so {2,4}, which it maps to, must not be an edge in the second graph: and it isn’t. From the second representation (a drawing of a graph in the plane is called a representation), you can see why such graphs are called “wagon wheels”. (The first graph is ({a,b,c,d,e,f,g}, {{a,b},{a,f},{b,c},{c,d},{d,e},{e,f},{g,a},{g,b},{g,c},{g,d},{g,e},{g,f}}). The second is ({1,2,3,4,5,6,7}, {{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{2,3},{2,7},{3,4},{4,5},{5,6},{6,7}}).
[pic] [pic]
It’s much harder to decide that two graphs are not isomorphic than to give an isomorphism if you’re convinced that they are isomorphic. Obviously, if two graphs have different numbers of vertices, or different numbers of edges, they’re not isomorphic. But having the same number is not enough to make them isomorphic. We’ll discuss this a bit later, once we have some terminology that helps us distinguish graphs.
If you start with a graph G = (V,E), and then take a subset of the vertices, V’, and a subset of the edges, E’, that only includes vertices in V’ (though not necessarily all the edges going between members of V’), this forms a new graph, G ‘ = (E’,V’), which is called a subgraph of G. Thus, for example, ({2,3,4,5,6,7}, {{2,3},{3,4},{4,5},{5,6},{6,7},{7,2}}) is a subgraph of the right-hand graph above. So is ({2,3,4,5,6,7}, {{2,3},{3,4},{6,7},{7,2}}) and so is ({1,2,3,4,6}, {{1,2},{1,6},{2,3},{3,4}}), and so on. A graph has many subgraphs. The subgraph with a given subset of vertices that has all the edges between these vertices that the original graph does is called the subgraph generated by those vertices.
A third way we can give a graph is via an adjacency matrix. There are many ways of associating a matrix with a graph. In an adjacency matrix, there is a row and a column for each vertex. The entry in the i-th row and the j-th column is a 1 if vi and vj are adjacent. Otherwise, there is a 0 in this row and column.
The adjacency matrix for the graph shown is
[pic] [pic]
Describe what the adjacency matrix of the complete graph on n vertices will look like:
Definition: Let G = (V, E). If v ( V, then the degree of the vertex v is defined as
deg(v) = the number of elements in {e (E | v ( e}. It is the number of edges that vertex is a member of.
Definition: The vertices vj, vk ( V are called adjacent if {vj, vk} ( E. That is, two vertices are adjacent if there is an edge consisting of those vertices.
Exercise: Give an example of a graph that has two vertices that are not adjacent.
Theorem: Let G = ({v1, v2, v3, ... vn}, {e1, e2, e3, ... em}). The sum of the degrees of all the vertices is equal to twice the number of edges. That is
[pic]= 2[pic]m.
Proof: Each edge adds 2 to the degree count.
Example:
Theorem: Let G a graph. The number of vertices with odd degree is even.
Proof:
One way to tell if two graphs are not isomorphic is if they have a different number of vertices of some degree. For example, if one graph has three vertices of degree 4, and the other only has two, then they’re not isomorphic. Thus, the two graphs below are not isomorphic, because the one on the left has all its vertices of degree 3, while the one on the right has several vertices of degree 4 (for example, vertex 5 and vertex 4)
[pic] [pic]
Another way to tell if two graphs are not isomorphic is if they have different subgraphs, especially different Kn subgraphs. For example, if one graph has a K4 subgraph and the other does not, they are not isomorphic.
Assignment:
[pic]
1. Let G be the graph above.
a. Describe the graph in our form G = (V, E). b. Find the degree of each vertex.
c. How many vertices of odd degree are there? d. How many of even degree?
e. Find [pic]. Is it twice the number of edges?
f. Fill in the adjacency matrix for G.
| |1 |2 |3 |4 |5 |6 |
|1 | | | | | | |
|2 | | | | | | |
|3 | | | | | | |
|4 | | | | | | |
|5 | | | | | | |
|6 | | | | | | |
g. Find three different (non-isomorphic) subgraphs of G whose vertices are {1,2,3,4}. One of them should be the subgraph generated by the vertices {1,2,3,4}.
[pic]
2. Let G’ be the graph above. Clearly V = {1, 2, 3, 4, 5, 6}.
a. List all members of E. b. Find the degree of each vertex.
c. How many vertices of odd degree are there? d. How many of even degree?
e. Find [pic]. Is it twice the number of edges?
f. Fill in the adjacency matrix for G’.
| |1 |2 |3 |4 |5 |6 |
|1 | | | | | | |
|2 | | | | | | |
|3 | | | | | | |
|4 | | | | | | |
|5 | | | | | | |
|6 | | | | | | |
[pic]
3. Let H be the graph above. Clearly V = {a, b, c, d, e, f}.
a. List all members of E. b. Find the degree of each vertex.
c. How many vertices of odd degree are there? d. How many of even degree?
e. Find [pic]. Is it twice the number of edges?
f. Fill in the adjacency matrix for H.
| |a |b |c |d |e |f |
|a | | | | | | |
|b | | | | | | |
|c | | | | | | |
|d | | | | | | |
|e | | | | | | |
|f | | | | | | |
4. a. Draw K5.
b. How many vertices does it have?
c. What is the degree of each vertex?
[pic]
5. Let H’ be the graph above.
a. Describe the graph in our form H’ = (V, E). b. Find the degree of each vertex.
c. How many vertices of odd degree are there? d. How many of even degree?
e. Find [pic]. Is it twice the number of edges?
f. Fill in the adjacency matrix for H’.
| |a |b |c |d |e |f |
|a | | | | | | |
|b | | | | | | |
|c | | | | | | |
|d | | | | | | |
|e | | | | | | |
|f | | | | | | |
6. Are any of the graphs G, G’, H, H’ (from this set of exercises) isomorphic? If they are, give the isomorphism. If they are not, what shows you they are not?
Section 6.2 Walks, paths, connected graphs, Euler circuits
Definition: Let G = ({v1, v2, ..., vn}, E) be a graph. By a walk of length k in G we mean a sequence
S: {0, 1, 2, ..., k} ( V
such that
{S(j-1), S(j)} ( E
for each j ( {1, 2 , ..., k}.
Be careful here. The length denotes the number of edges in the walk, but we usually describe the walk by the vertices.
Definition: A walk in which no vertex appears more than once is called a path.
Exercise: Give an example of a graph that contains a walk of length 4. Be sure to give the (five) values of S.
Definition: G is called connected if for each v, w ( V there is a walk S of (length k, for some k) such that S(0) = v and S(k) = w. If a graph is not connected, it is disconnected. Each connected subgraph is called a component.
Exercise: Give examples of graphs that are connected and not connected.
Definition: A walk S is called simple if
{S(j-1), S(j)} = {S(i-1), S(i)} (( j = i and j-1 = i-1) or ( j = i-1 and i = j-1).
That is, a walk is simple if no edge appears more than once.
Theorem: Suppose the graph G = (V, E) is connected. For every v, w ( V there is a simple walk from v to w.
Proof: By induction on the length of a walk from v to w. If the length of a walk from v to w is 1, then {v,w} is an edge (that is, {v,w} ( E). Since it is a walk of length 1, clearly no edge appears more than once. Hence, it is a simple walk.
Induction step: Suppose that if S :{0, 1, 2, ..., n} ( E is any walk in G and n ( k, then there is a walkS(:{0, 1, 2, ..., n(}( E such that S( is simple and S((0) = S(0) and S((n() = S(n).
Let T:{0, 1, 2, ..., k+1}( E be a walk of length k+1.
Case 1: If {T(k), T(k+1)} appears more than once in the walk, then the walk T visits T(k+1) earlier. That is, ( j < k+1 such that T(j) = T(k+1). Then T:{0, 1, 2, ..., j} is of length k or less and therefore there is a simple walk connecting T(0) to T(j) and therefore to T(k+1).
Case 2: {T(k), T(k+1)} appears in T only once. Thus the walk from T(0) to T(k) is not simple, but by the induction hypothesis, can be replaced by a simple walk, T( beginning at T(0) and terminating at T(k). If T( has {T(k), T(k+1)} as an edge, we return to case 1. If not, we attach {T(k), T(k+1)} to T( to form a simple walk beginning at T(0) and terminating at T(k+1).
Attaching an edge to the end of a walk and, indeed, the idea of combining two walks into a single walk will be examined more rigorously below.
Definition: L(v, w) denotes the length of the shortest path from v to w.
Definition: Let S:{0, 1, 2, ..., j}(E be a walk from v to u and S(:{0, 1, 2, ..., k}(E be a walk from u to w. Define the concatenation of S and S(, concat(S; S(), by
concat(S; S() = [pic]
Example:
Theorem: L(v, w) ( L(v, u) + L(u, w).
Proof: Let S:{0, 1, 2, ..., j}(E be a shortest path from v to u and S(:{0, 1, 2, ..., k}(E be the shortest path from u to w. Then S(( = concat(S; S() is a walk of length j + k from v to w. Hence the shortest path from v to w must be no longer than S((; that is, L(v, w) ( j + k.
Example:
Theorem: If S is a shortest walk from v to w, then S is simple.
Proof: By induction on L(v, w). If L(v, w) = 1 then the shortest walk from v to w has one edge and is of course simple. Suppose every shortest walk of length k or less is simple. Let v, w ( V be such that L(v, w) = k+1. Suppose S:{0, 1, 2, ..., k+1} ( E is a shortest walk from v to w. Then S :{0, 1, 2, ..., k} ( E is the shortest walk from v to S(k) (why?) and is therefore simple. S (k+1) = w and w ( S(j) for any j as otherwise for L(v, w) 0, xu < yu |IM |
When you put these two groups of properties together, you can derive (once you define x < y to be (x < y) ( (x = y)) the following
Properties of <
|Name |Axiom |Abbrev. |
|Reflexive property of < | x < x |LER |
|Antisymmetric property of < |If x < y and y < x, then x = y. |L~S |
|Transitive property of < |If x < y and y < z, then x < z. |LET |
|Addition of < |If x < y and u < v, x + u < y + v |LEA |
|Multiplication of < |If x < y and u > 0, xu < yu |LEM |
| | | |
All of the sets of numbers we use (the natural numbers, the integers, the rational numbers, the real numbers, and the complex numbers) have certain properties in common; we list these first.
Closure: All of these sets are closed under addition and multiplication: that is, given any two members x and y of the set, x + y and xy are also members of the set; these properties are called (set name) ClA and ClM (for closure: addition and closure: multiplication). So, for example, closure of the natural numbers under addition is NClA.
Associativity: Both addition and multiplication are associative in all these sets of numbers. That is, given any numbers x, y, and z in one of these sets,
AssocA: (x + y) + z = x + (y + z)
AssocM: (xy)z = x(yz).
Commutativity: Both addition and multiplication are commutative in all these sets of numbers. That is, given any numbers x and y in one of these sets,
CommA: x + y = y + x
CommM: xy = yx.
Distributivity: In each of these sets, multiplication distributes over addition. That is, given any numbers x, y, and z in one of these sets,
Dist: x(y + z) = xy + xz.
Multiplicative identity: In each of these sets, 1 is the multiplicative identity. That is, given any number x in one of these sets,
MI: x(1 = 1(x = x.
Additive identity: In each of these sets except the natural numbers (because 0 is not a natural number), 0 is the additive identity. That is, given any number x in one of these sets,
AI: x + 0 = 0 + x = x.
(Notice that, since each of these axioms starts with the set you’re working in, this shouldn’t be confused with Alternative Implies, which is just plain AI: each of these will be preceeded by its set name. So QAI is Additive Identity in the rational numbers, for example.)
Now that we’ve listed properties all of the sets have, the remainder vary from set to set.
Additional Properties of N (the natural numbers)
|Name |Axiom |Abbrev. |
|Cancellation of addition |If x + y = x + z, then y = z |NCA |
|Cancellation of multiplication |If xy = xz, then y = z |NCM |
|Induction |Given any property P(x) that can apply to natural numbers, if P(1) is|NInd |
| |true and if, whenever P(x) is true then P(x + 1) is also true, then | |
| |P(x) is true of all natural numbers | |
Notice that cancellation of addition and of multiplication are basically true because the function “adding x”, Ax: N ( N, defined as Ax(y) = x + y, is one-to-one, as is the function “multiplying by x”, Mx: N ( N, defined as Mx(y) = xy. We don’t need cancellation of addition for our other sets, as they all have additive inverses, but since N doesn’t, it needs such a rule. Z is the only other set that doesn’t have multiplicative inverses and thus it needs cancellation for multiplication, but not for addition.
Additional Properties of Z (the integers)
|Name |Axiom |Abbrev. |
|Additive Inverse |For each x ( Z there is a unique y ( Z (this y is called “-x”) such |ZAInv |
| |that x + y = 0. | |
|Cancellation of multiplication |If xy = xz, then y = z |ZCM |
Once we get to the rational numbers, we get inverses for both addition and multiplication – but be careful: there is no multiplicative inverse for 0. Thus, you can have 0(x = 0(y, but yet x ( y.
Additional Properties of Q (the rational numbers)
|Name |Axiom |Abbrev. |
|Additive Inverse |For each x ( Q there is a unique y ( Q (this y is called “-x”) such |QAInv |
| |that x + y = 0. | |
|Multiplicative inverse |For each x ( Q except 0, there is a unique |QMInv |
| |y ( Q (this y is called “x-1” or “1/x”) such that x + y = 0. | |
Additional Properties of R (the real numbers)
|Name |Axiom |Abbrev. |
|Additive Inverse |For each x ( R there is a unique y ( R (this y is called “-x”) such |RAInv |
| |that x + y = 0. | |
|Multiplicative inverse |For each x ( R except 0, there is a unique |RMInv |
| |y ( R (this y is called “x-1” or “1/x”) such that x + y = 0. | |
|Least upper bound |Any set A of real numbers that is bounded above (that is, for which |RLub |
| |there is a real number m such that if x ( A, then x < m) has a least | |
| |upper bound (that is, a smallest such m). | |
Additional Properties of C (the complex numbers)
|Name |Axiom |Abbrev. |
|Additive Inverse |For each x ( C there is a unique y ( C (this y is called “-x”) such |CAInv |
| |that x + y = 0. | |
|Multiplicative inverse |For each x ( C except 0, there is a unique |CMInv |
| |y ( C (this y is called “x-1” or “1/x”) such that x + y = 0. | |
|Contains R |x ( R ( x ( C |R ( C |
|Algebraically closed |Every polynomial with coefficients in C has at least one root in C. |CAC |
-----------------------
|1 |P |given |
|2 |Q ( ~P |given |
|3 |Q ( R |given |
|4 |P ( ~Q |Contra(2) |
|5 |~Q |Det(1, 4) |
|6 |~Q ( R |AI(3) |
|7 |R |Det(5, 6) |
To prove P ( Q we can assume that P is true and show that Q must be true.
(11 |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 | |0 | | | | | | | | | | | | |1 | | | | | | | | | | | | |2 | | | | | | | | | | | | |3 | | | | | | | | | | | | |4 | | | | | | | | | | | | |5 | | | | | | | | | | | | |6 | | | | | | | | | | | | |7 | | | | | | | | | | | | |8 | | | | | | | | | | | | |9 | | | | | | | | | | | | |10 | | | | | | | | | | | | |
(11 |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 | |0 | | | | | | | | | | | | |1 | | | | | | | | | | | | |2 | | | | | | | | | | | | |3 | | | | | | | | | | | | |4 | | | | | | | | | | | | |5 | | | | | | | | | | | | |6 | | | | | | | | | | | | |7 | | | | | | | | | | | | |8 | | | | | | | | | | | | |9 | | | | | | | | | | | | |10 | | | | | | | | | | | | |
x |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 | |x2 | | | | | | | | | | | | |
x |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 | |x3 | | | | | | | | | | | | |
1
y ( f (X) ( (( x ( X)((x, y) ( f ) ( (( x ( X)( f (x) = y)
x ( f -1(Y) ( (( y ( Y)((x, y) ( f ) ( f (x) ( Y
[pic]
[pic]
1
1
4
3
a
2
A
B
C
D
E
F
G
A
B
C
D
E
F
1
2
3
4
5
6
2
1
3
4
5
6
7
8
F
A
B
C
D
E
C
A
D
B
E
F
G
H
I
J
K
6
5
4
3
2
1
3
2
4
1
5
6
1
2
3
4
5
6
3
4
5
6
1
2
3
1
2
3
4
4
1
2
3
b
e
a
f
g
d
c
1
2
3
4
5
6
7
2
3
4
5
6
1
2
3
4
5
6
1
2
3
5
6
4
3
2
4
1
5
6
3
2
4
1
5
6
1
2
3
4
5
6
2
1
1
2
5
4
3
b
c
d
e
f
e
c
b
d
a
f
2
3
4
5
6
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- fa biosynthesis pathway
- supplementary calculator
- supplementary angle calculator
- how to find the supplementary angles
- two supplementary angles calculator
- complementary and supplementary angle calculator
- how to solve supplementary angles
- complementary supplementary and vertical angles
- complementary and supplementary calculator
- supplementary angles calculator
- 120 208 vs 120 240
- fa davis omeprazole