DISCRETE MATHMTICS I
DISCRETE MATHMTICS I MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 220 page Class Notes was uploaded by Duncan Hills on Thursday September 17, 2015. The Class Notes belongs to MAD 2104 at Florida State University taught by Penelope Kirby in Fall. Since its upload, it has received 245 views. For similar materials see /class/205558/mad-2104-florida-state-university in Mathematics Discrete at Florida State University.
Reviews for DISCRETE MATHMTICS I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
2 PROPOSITIONAL EQUIVALENCES 32 2 Propositional Equivalences 21 Taut ologyContr39adict ionContingency DEFINITION 211 A tautology is a proposition that is always true EXAMPLE 211 p V p DEFINITION 212 A contradiction is a proposition that is always false EXAMPLE 212 p p DEFINITION 213 A contigency is a proposition that is neither a tautology nor a contradiction EXAMPLE 213 p V q a r Discussion One of the important techniques used in proving theorems is to replace or sub stitute one proposition by another one that is equivalent to it In this section we will list some of the basic propositional equivalences and show how they can be used to prove other equivalences Let us look at the classic example of a tautology p V p The truth table shows that p V p is true no matter the truth value of p Side Note This tautology called the law of epeluded middle is a direct consequence of our basic assumption that a proposition is a statement that is either true or false Thus the logic we will discuss here so called Aristotelian logic might be described as a 2 valued logic and it is the logical basis for most of the theory of modern mathematics at least as it has developed in western culture There is however a consistent logical system known as constructivist or intuitionistic logic which does not assume the law of excluded middle This results in a 3 valued logic in which one allows for 2 PROPOSITIONAL EQUIVALENCES 33 a third possibility namely other7 In this system proving that a statement is not true77 is not the same as proving that it is false77 so that indirect proofs which we shall soon discuss would not be valid If you are tempted to dismiss this concept you should be aware that there are those who believe that in many ways this type of logic is much closer to the logic used in computer science than Aristotelian logic You are encouraged to explore this idea there is plenty of material to be found in your library or through the worldwide web The proposition p V p q is also a tautology as the following the truth table illustrates A W QlepM pVepAQ EXERCISE 211 Build a truth table to verify that the proposition p lt gt q pq is a contradiction WWQQB q T T F F T F F F aaauj aaaa 22 Logically Equivalent DEFINITION 221 Propositions r and s are logically equivalent if the statement r lt gt s is a tautology Notation If r and s are logically equivalent we write r s Discussion A second notation often used to mean statements r and s are logically equivalent is r E 5 You can determine whether compound propositions r and s are logically equivalent by building a single truth table for both propositions and checking to see that they have exactly the same truth values Notice the new symbol r gt s which is used to denote that r and s are logically equivalent is de ned to mean the statement r lt gt s is a tautology In a sense the 2 PROPOSITIONAL EQUIVALENCES 34 symbols lt gt and gt convey similar information when used in a sentence However r gt s is generally used to assert that the statement r lt gt s is in fact true while the statement r lt gt 5 alone does not imply any particular truth value The symbol gt is the preferred shorthand for is equivalent to7 23 Examples EXAMPLE 231 Show that p a q q a p is logically equivalent to p lt gt q Solution 1 Show the truth values of both propositions are identical TruthTable plqlp qlq p paqu p qu T T T T T T T F F T F F F T T F F F F F T T T T Solution 2 Epamine every possible case in which the statement p a q q a p may not have the same truth value as p lt gt q Case 1 Suppose p a q q a p is false andp lt gt q is true 0 Assume p a q is false Then p is true and q is false But if this is the case the p lt gt q is false 0 Assume q a p is false Then q is true andp is false But if this is the case the p lt gt q is false Case 2 Suppose p a q q a p is true andp lt gt q is false If the latter is false the p and q do not have the same truth value 0 Assume p is true andq is false Thenp a q is false the the conjunction is also must be false 0 Assume p is false andq is true Then q a p is false the the conjunction is also must be false We ecchausted all the possibilities so the two propositions must be logically equivalent Discussion 2 PROPOSITIONAL EQUIVALENCES 35 This example illustrates an alternative to using truth tables to establish the equiv alence of two propositions An alternative proof is obtained by excluding all possible ways in which the propositions may fail to be equivalent Here is another example EXAMPLE 232 Show p a q is equivalent to p q Solution 1 Build a truth table containing each of the statements plqlnqlp q npeg pWq T T F T F F T F T F T T F T F T F F F F T T F F Since the truth values for p a q and p q are exactly the same for all possible combinations of truth values of p and q7 the two propositions are equivalent Solution 2 We consider how the two propositions could fail be equivalent This can happen only if the rst is true and the second is false or vice versa Case 1 Suppose p a q is true and p q is false p a q would be true if p a q if false Now this only occurs if p is true and q is false However7 if p is true and q is false7 then p q will be true Hence this case is not possible Case 2 Suppose p a q is false and p q is true p q is true only if p is true and q is false But in this case7 p a q will be true So this case is not possible either Since it is not possible for the two propositions to have different truth values7 they must be equivalent EXERCISE 231 Use a truth table to show that the propositionsp lt gt q and p Bq are equivalent EXERCISE 232 Use the method of Solution 2 in Example 232 to show that the propositions p lt gt q and p 69 q are equivalent 2 PROPOSITIONAL EQUIVALENCES 36 24 Important Logical Equivalences The logical equivalences below are im portant equivalences that should be memorized Identity Laws Domination Laws ldempotent Laws Double Negation Law Commutative Laws Associative Laws Distributive Laws De Morgar s Laws Absorption Laws pTlt p pVFlt p pVT gtT pF gtF PVPltZgtP PAZMZHD upQ gtupv q upVQ gtup q 2 PROPOSITIONAL EQUIVALENCES 37 Implication Law p 1 gt 1 0 V I Contrapositive Law p a q gt g a p Tautology p V p gt T Contradiction p p gt F Equivalence p a q q a p gt p lt gt q Discussion Study carefully what each of these equivalences is saying With the possible exceptions of the De Morgan Laws7 they are fairly straight forward to understand The main dif culty you might have with these equivalences is remembering their names EXAMPLE 241 Use the logical equivalences above and substitution to establish the equivalence of the statements in Example Solution p a q gt bp V q Implication Law gt p q De Morgan s Law gt p q Double Negation Law This method is very similar to simplifying an algebraic expression You are using the basic equivalences in somewhat the same way you use algebraic rules like 2x73p r x 1x 7 3 1 x73 EXERCISE 241 Use the propositional equivalences in the list of important logical equivalences above to prove is t w a t a s a w is a tautology EXERCISE 242 Use tputh tables to verify De Morgan s Laws 25 Simplifying Propositions 2 PROPOSITIONAL EQUIVALENCES 38 EXAMPLE 251 Use the logical equivalences above to show that p V p q is a contradiction Solution up V up A 91 gt p 5 p 1 De Morgan s Law gt p p q Double Negation Law gt p p q Associative Law gt F q Contradiction gt F Domination Law and Commutative Law EXAMPLE 252 Find a simple form for the negation of the proposition quotIf the sun is shining then I am going to the ball game Solution This proposition is of the form p a q As we showed in Example 232 its negation p a q is equivalent to p q This is the proposition quotThe sun is shining and I am not going to the ball game Discussion The main thing we should learn from Examples 232 and 252 is that the negation of an implication is not equivalent to another implication such as If the sun is shining then I am not going to the ball game77 or If the sun is not shining I am going to the ball game77 This may be seen by comparing the corresponding truth tables p q pang TPmQlt10TQ np q T T F F T T F T T T F T T F T F F T F F If you were to construct truth tables for all of the other possible implications of the form r a s where each of r and s is one of p p q or q you will observe that none of these propositions is equivalent to p a q 2 PROPOSITIONAL EQUIVALENCES 39 The rule p a q gt p q should be memorized One way to memorize this equivalence is to keep in mind that the negation of p a q is the statement that describes the only case in which p a q is false EXERCISE 251 Which of the following are equivalent to 51 a r a g There may be more than one or none 1 np e r V q 2 p A r V q 3 n1 r Vq 4 q e p n 7 5 g a n20 r 6 we WW 7 we doe 7quot EXERCISE 252 Which of the following is the negation of the statement quotIf you go to the beach this weekend then you should bring your books and study I If you do not go to the beach this weekend then you should not bring your books and you should not study 2 If you do not go to the beach this weekend then you should not bring your books or you should not study 3 If you do not go to the beach this weekend then you should bring your books and study 4 You will not go to the beach this weekend and you should not bring your books and you should not study 5 You will not go to the beach this weekend and you should not bring your books or you should not study 6 You will go to the beach this weekend and you should not bring your books and you should not study 7 You will go to the beach this weekend and you should not bring your books or you should not study EXERCISE 253 p is the statement quotI will prove this by cases q is the statement quotThere are more than 500 cases and r is the statement quotI can nd another way State the negation of r V g a p in simple English Do not use the eppression quotIt is not the case 26 Implication DEFINITION 261 We say the proposition r implies the proposition 5 and write r i s ifr a s is a tautology This is very similar to the ideas previously discussed regarding the gt verses lt gt We use r i s to imply that the statement r a s is true7 while that statement r a s 2 PROPOSITIONAL EQUIVALENCES 4O alone does not imply any particular truth value The symbol i is often used in proofs as a shorthand for implies EXERCISE 261 Prove p a q g ap 27 Normal or Canonical Forms DEFINITION 271 Every compound proposition in the propositional variables p q r is uniquely equivalent to a proposition that is formed by taking the disjunction of conjunctions of some combination of the variablesp7 q7 r or their negations This is called the disjunctive normal form of a proposition Discussion The disjunctive normal form of a compound proposition is a natural and useful choice for representing the proposition from among all equivalent forms7 although it may not be the simplest representative We will nd this concept useful when we arrive at the module on Boolean algebra 28 Examples EXAMPLE 281 Construct a proposition in disjunctive normal form that is true precisely when I p is true and q is false Solution p g 2 p is true and q is false or when p is true and q is true Solution p q V p q 3 eitherp is true or q is true and r is false Solution p V q r gt p r V q r Distributive Law Notice that the second eccample could be simpli ed to just p Discussion The methods by which we arrived at the disjunctive normal form in these examples may seem a little ad hoc We now demonstrate7 through further examples7 a sure re method for its construction 2 PROPOSITIONAL EQUIVALENCES 41 29 Constructing Disjunctive Normal Forms EXAMPLE 291 Find the disjunctive normal form for the proposition p a q Solution Construct a truth table forp a q p a q is true when either p is true and q is true or p is false and q is true or p is false and q is false The disjunctive normal form is then AvVCwAvVCwA v Discussion This example shows how a truth table can be used in a systematic way to construct the disjunctive normal forms Here is another example EXAMPLE 292 Construct the disjunctive normal form of the proposition vAW Solution Write out the truth table for p a q r 2 PROPOSITIONAL EQUIVALENCES 42 p q rp q TP Q TTT T F F TTF T T T TFT F F F FTT T F F TFF F T F FTF T T T FFT T F F FFF T T T The disjunctive normal form will be a disjunction of three conjunctions one for each row in the truth table that gives the truth value Tfor p a q r These rows have been bored In each conjunction we will use p if the truth value ofp in that row is T and p if the truth value ofp is F q if the truth value ofq in that row is T and no if the truth value ofq is F etc The disjunctive normal form for p a q r is then pAqA r V pAqA r V pA qA r because each of these conjunctions is true only for the combination of truth values of p q and r found in the corresponding row That is p q r has truth value T only for the combination of truth values in row 2 pAqA r has truth value T only for the combination of truth values in row 6 etc Their disjunction will be true for precisely the three combinations of truth values ofp q and r for which p a q r is also true Terminology The individual conjunctions that make up the disjunctive normal form are called minterms In the previous example the disjunctive normal form for the proposition p a q r has three minterms p q r p q r and mp q r 210 Conjunctive Normal Form The conjunctive normal form of a propo sition is another canonical form77 that may occasionally be useful but not to the same degree as the disjunctive normal form As the name should suggests after our discus sion above the conjunctive normal form of a proposition is the equivalent form that consists of a conjunction of disjunctions7 It is easily constructed indirectly using disjunctive normal forms by observing that if you negate a disjunctive normal form you get a conjunctive normal form For example three applications of De Morgan7s Laws gives ohm W V WA 11 lt pV Q10V 1 Florida State University Course Notes MAD 2104 Discrete Mathematics I Florida State University Tallahassee7 Florida 32306 4510 Copyright 2004 Florida State University Written by Dr John Bryant and Dr Penelope Kirby All rights reserved No part of this publication may be reproduced7 stored in a retrieval systern7 or transmitted in any form or by any means without permission from the authors or a license from Florida State University Contents Chapter 1 Introduction to Sets and Functions 1 11 12 13 14 15 16 17 18 19 2 21 22 23 24 25 Introduction to Sets Basic Terminology Notation for Describing a Set Common Universal Sets Complements and Subsets Element Vs Subsets Cardinality Set Operations Example 181 Product Introduction to Functions Function Terminology Related to Functions Example 231 Floor and Ceiling Functions Characteristic Function Chapter 2 Logic 1 11 12 13 14 15 16 21 Logic De nitions Propositions Examples Logical Operators Negation Conjunction Disjunction Exclusive Or lmplications Terminology Example Biconditional NAND and NOR Operators Example Bit Strings Propositional Equivalences TautologyContradictionContingency 3 CONTENTS 22 Logically Equivalent 23 Examples 24 Important Logical Equivalences 25 Simplifying Propositions 26 lmplication 27 Normal or Canonical Forms 28 Examples 29 Constructing Disjunctive Normal Forms 210 Conjunctive Normal Form 3 Predicates and Quanti ers 31 Predicates and Quanti ers 32 Example of a Propositional Function 33 Quanti ers 34 Example 341 35 Converting from English 36 Additional De nitions 37 Examples 38 Multiple Quanti ers 39 Ordering Quanti ers 310 Unique Existential 311 De Morgan7s Laws for Quanti ers 312 Distributing Quanti ers over Operators Chapter 3 Methods of Proofs 1 Logical Arguments and Formal Proofs 11 Basic Terminology 12 More Terminology 13 Formal Proofs 14 Rules of lnference 15 Example 151 16 Rules of Inference for Quanti ers 17 Example 171 18 Fallacies 2 Methods of Proof 21 Types of Proofs 22 Trivial ProofVacuous Proof 23 Direct Proof 24 Proof by Contrapositive 25 Proof by Contradiction 26 Proof by Cases 27 Existence Proofs 28 Constructive Proof 29 Nonconstructive Proof 210 Nonexistence Proofs CONTENTS 5 211 The Halting Problem 74 212 Counterexample 74 213 Biconditional 75 3 Mathematical Induction 76 31 First Principle of Mathematical Induction 76 32 Using Mathematical lnduction 77 33 Example 331 78 34 Example 341 81 35 Example 351 83 36 The Second Principle of Mathematical lnduction 85 37 Well Ordered Sets 87 Chapter 4 Applications of Methods of Proof 89 1 Set Operations 89 11 Set Operations 89 12 Equality and Containment 89 13 Union and lntersection 90 14 Complement 90 15 Difference 90 16 Product 91 17 Power Set 91 18 Examples 91 19 Venn Diagrams 92 110 Examples 93 111 Set ldentities 94 112 Union and Intersection of lndexed Collections 98 113 ln nite Unions and lntersections 99 114 Example 1141 100 115 Computer Representation of a Set 101 2 Properties of Functions 104 21 lnjections7 Surjections7 and Bijections 104 22 Examples 104 23 Example 231 106 24 Example 241 107 25 Example 251 107 26 Example 261 108 27 lnverse Eunctions 108 28 lnverse Image 110 29 Composition 111 210 Example 2101 112 3 Recurrence 113 31 Recursive De nitions 113 32 Recursive de nition of the function fn n 114 33 Recursive de nition of the natural numbers 114 CONTENTS 6 34 Proving assertions about recursively de ned objects 115 35 De nition of f 118 36 Example 361 119 37 Fibonacci Sequence 120 38 Strings 123 39 Bit Strings 124 4 Growth of Functions 128 41 Growth of Functions 128 42 The Big O Notation 128 43 Proofs of Theorems 421 and 422 130 44 Example 441 131 45 Calculus De nition 132 46 Basic Properties of Big O 134 47 Proof of Theorem 463 135 48 Example 481 135 49 Big Omega 136 410 Big Theta 136 411 Summary 137 412 Appendix Proof of the Triangle lnequality 138 Chapter 5 Number Theory 139 1 lntegers and Division 139 11 Divisibility 139 12 Basic Properties of Divisibility 139 13 Theorem 131 The Division Algorithm 140 14 Proof of Division Algorithm 140 15 Prime Numbers7 Composites 141 16 Fundamental Theorem of Arithmetic 142 17 Factoring 142 18 Mersenne Primes 143 19 Greatest Common Divisor and Least Common Multiple 143 110 Modular Arithmetic 144 111 Applications of Modular Arithmetic 146 2 lntegers and Algorithms 148 21 Euclidean Algorithm 148 22 GCD7s and Linear Combinations 149 23 Uniqueness of Prime Factorization 152 3 Applications of Number Theory 156 31 Representation of lntegers 156 32 Constructing Base b Expansion of n 156 33 Cancellation in Congruences 157 34 lnverses mod m 158 35 Linear Congruence 159 36 Criterion for lnvertibility mod m 159 CONTENTS 7 37 Example 371 160 38 Fermat7s Little Theorem 160 39 RSA System 162 4 Matrices 163 41 De nitions 163 42 Matrix Arithmetic 164 43 Example 431 164 44 Special Matrices 166 45 Boolean Arithmetic 168 46 Example 461 169 Chapter 6 Introduction to Graph Theory 171 1 Introduction to Graphs 171 11 Simple Graphs 171 12 Examples 171 13 Multigraphs 172 14 Pseudograph 173 15 Directed Graph 174 16 Directed Multigraph 175 17 Graph lsomorphism 176 2 Graph Terminology 179 21 Undirected Graphs 179 22 The Handshaking Theorem 180 23 Example 231 180 24 Directed Graphs 181 25 The Handshaking Theorem for Directed Graphs 182 26 Underlying Undirected Graph 182 27 New Graphs from Old 182 28 Complete Graphs 183 29 Cycles 184 210 Wheels 184 211 n Cubes 185 212 Bipartite Graphs 186 213 Examples 186 3 Representing Graphs and Graph lsomorphism 188 31 Adjacency Matrix 188 32 Example 321 188 33 lncidence Matrices 190 34 Degree Sequence 191 35 Graph lnvariants 191 36 Example 361 192 37 Example 193 38 Proof of Theorem 351 Part 3 for nite simple graphs 196 Chapter 7 Introduction to Relations 197 CONTENTS Relations and Their Properties De nition of a Relation Examples Directed Graphs Inverse Relation Special Properties of Binary Relations Examples of Relations and their Properties Proving or disproving relations have a property Combining Relations Example of Combining Relations Composition Example of Composition Characterization of Transitive Relations 197 197 198 199 200 201 201 202 204 205 205 206 208 CHAPTER 1 Introduction to Sets and Functions 1 Introduction to Sets 11 Basic Terminology We begin with a refresher in the basics of set theory Our treatment will be an informal one rather than taking an axiomatic approach at this time Later in the semester we will revisit sets with a more formal approach A set is a collection or group of objects or elements or members Cantor 1895 o A set is said to contain its elements 0 In each situation or context7 there must be an underlying universal set U7 either speci cally stated or understood Notation o If x is a member or element of the set S7 we write x E S o If x is not an element of S we write x Z S 12 Notation for Describing a Set EXAMPLE 121 List the elements between braces o S abcd b07a7d7d Specify by attributes o S 2 5 or z lt 07 where the universe is the set of real numbers Use brace notation with ellipses o S 7 73 72 71 the set of negative integers Discussion 9 1 INTRODUCTION TO SETS 10 Sets can be written in a variety of ways One can7 of course7 simply list the elements if there are only a few Another way is to use set builder notation7 which speci es the sets using a predicate to indicate the attributes of the elements of the set For example7 the set of even integers is dlx 27171 E Z or 720246 The rst set could be read as the set of all X7s such that X is twice an integer The symbol l stands for such that A colon is often used for such that as well7 so the set of even integers could also be written zx2nn Z 13 Common Universal Sets The following notation will be used throughout these notes 0 R the real numbers 0 N the natural numbers 07 1237 0 Z the integers 7737 72 710 1237 o ZT the positive integers 1237 Discussion The real numbers7 natural numbers7 rational numbers7 and integers have special notation which is understood to stand for these sets of numbers Corresponding bold face letters are also a common notation for these sets of numbers Some authors do not include 0 in the set of natural numbers We will include zero 14 Complements and Subsets DEFINITION 141 The complement ofA Ax Ulz A DEFINITION 142 A set A is a subset of a set E denoted A Q B if and only if every element ofA is also an element of B DEFINITION 143 IfA Q B but A 31 B then we say A is a proper subset ofB and denote it by ACE 1 INTRODUCTION TO SETS 11 DEFINITION 144 The null set or empty set denoted Q is the set with no members Note 0 Q is a subset of every set 0 A set is always a subset of itself Discussion Please study the notation for elements subsets proper subsets and the empty set Two other common notations for the complement of a set A is A0 and A Notice that we make a notational distinction between subsets in general and proper subsets Not all texts andor instructors make this distinction and you should check in other courses whether or not the notation C really does mean proper as it does here 15 Element Vs Subsets Sets can be subsets and elements of other sets EXAMPLE 151 Let A 0 Then A has two elements Q and 0 and the four subsets 7070 EXAMPLE 152 Pay close attention to whether the symbols means element or subset in this ecoample IfS 23 2 4 then 0 2 E S o 3 E S o 4 Z S o2ES o3 S o4ES o2CS o3CS o4 S 2 C 5 3 5 4 C S EXERCISE 151 Let A 12112 True orfalse a1 A b1gA 026A Mm mow mum 1 INTRODUCTION TO SETS 12 1 6 Cardinality DEFINITION 161 The number of distinct elements in a set A is called the cardinality ofA and is written If the cardinality is a natural number then the set is called nite otherwise it is called in nite EXAMPLE 161 Suppose A a7b Then 1A1 27 EXAMPLE 162 The cardinality of is 0 but the cardinality of is 2 EXAMPLE 163 The set of natural numbers is in nite since its cardinality is not a natural number The cardinality of the natural numbers is a trans nite cardinal number Discussion Notice that the real numbers7 natural numbers7 integers7 rational numbers7 and irrational numbers are all in nite Not all in nite sets are considered to be the same size7 The set of real numbers is considered to be a much larger set than the set of integers ln fact7 this set is so large that we cannot possibly list all its elements in any organized manner the way the integers can be listed We call a set like the real numbers that has too many elements to list uncountable and a set like the integers that can be listed is called countable We will not delve any deeper than this into the study of the relative sizes of in nite sets in this course7 but you may nd it interesting to read further on this topic EXERCISE 161 Let A 12112 B 12 and O 1222 Find the cardinality of each set 17 Set Operations DEFINITION 171 The union of sets A and B denoted by AUB read quotA union B is the set consisting of all elements that belong to either A or B or both In symbols AUBzEAorzEB DEFINITION 172 The intersection of sets A and B denoted by A B read quotA intersection B is the set consisting of all elements that belong both A and B In symbols A Bzz Aandz B DEFINITION 173 The difference or relative compliment of two sets A and B denoted by A 7 B is the set of all elements in A that are not in B AiBzz Aandz ZB 1 INTRODUCTION TO SETS 13 Discussion The operations of union and intersection are the basic operations used to combine two sets to form a third Notice that we always have A Q A U B and A B Q A for arbitrary sets A and B 18 Example 181 EXAMPLE 181 Suppose A 1357911 B 34567 and O 246810 Then 1 AU B 134567911 b Am B 357 0 A U C 1234567891011 d A m o 0 e A i B 1911 EXERCISE 181 Let A 12112 and B 12 True orfalse 126A B b2 AUB 026A7B d 2 EA B e 2 EAUB f 2 EAiB 19 Product DEFINITION 191 The Cartesian Product of two sets A and B is denoted A gtlt B and is de ned by AgtltBabla A andbEB Discussion A cartesian product you have used in previous classes is R gtlt R This is the same as the real plane and is shortened to R2 Elements of R2 are the points in the plane Notice the notation for and element in R gtlt R is the same as the notation for an open interval of real numbers In other words7 35 could mean the ordered pair in R gtlt R or it could mean the interval x 6 RB lt z lt 5 If the context does not make it clear which 37 5 stands for you should make it clear EXAMPLE 191 Let A 1b0d7 e and let B 12 Then 1A gtlt B a71b1c1d1e1a2b2c2d2e2 1 INTRODUCTION TO SETS 14 2 A gtlt B1 10 3 m2 MM 4 072 AUB EXERCISE 191 Let A t1lcd7 e and let B 12 Find 1B gtlt A 2 B x A 3 3 12 6 B gtlt A 4 3 27a 6 B gtlt A 5 Is2a BgtltA9 2 INTRODUCTION TO FUNCTIONS 15 2 Introduction to Functions 21 Function DEFINITION 211 Let A and B be sets A function f A a B is a rule which assigns to every element in A exactly one element in B ff assigns a E A to the element b E B then we write f a b and we call b the image or value off at a Discussion This is the familiar de nition of a function f from a set A to a set E as a rule that assigns each element of A to exactly one element B This is probably quite familiar to you from your courses in algebra and calculus In the context of those subjects7 the sets A and B are usually subsets of real numbers R7 and the rule usually refers to some concatenation of algebraic or transcendental operations which7 when applied to a number in the set A7 give a number in the set E For example7 we may de ne a function f R a R by the formula rule f V1 sinx We can then compute values of f 7 for example7 f0 17 f7r2 f37r2 07 f1 1357 approximately 7 using knowledge of the sine function at special values of z andor a calculator Sometimes the rule may vary depending on which part of the set A the element x belongs For example7 the absolute value function f R a R is de ned by z iwaO7 f x 7x iflt0 The rule that de nes a function7 however7 need not be given by a formula of such as those above For example7 the rule that assigns to each resident of the state of Florida his or her last name de nes a function from the set of Florida residents to the set of all possible names There is certainly nothing formulaic about about the rule that de nes this function At the extreme we could randomly assign everyone in this class one of the digits 0 or 17 and we would have de ned a function from the set of students in the class to the set 01 We will see a more formal de nition of a function later on that avoids the use of the term rule but for now it will serve us reasonably well We will instead concentrate on terminology related to the concept of a function7 including special properties a function may possess 2 INTRODUCTION TO FUNCTIONS 16 22 Terminology Related to Functions Let A and B be sets and suppose f A a B o The set A is called the domain of f o The set E is called the codomain of f o If fx y then x is a preimage of y Note7 there may be more than one preimage of y but only one image or value of x o The set fA E A is called the range of f o If S Q A7 then the image of S under f is the set fS ms 6 s o If T Q B7 then the preimage of T under f is the set f 1T z 6 AW 6 T Discussion Some of the ne points to remember 0 Every element in the domain must be assigned to exactly one element in the codomain 0 Not every element in the codomain is necessarily assigned to one of the elements in the domain 0 The range is the subset of the codomain consisting of all those elements that are the image of at least one element in the domain It is the image of the domain 0 If a subset T of the codomain consists of a single element7 say7 T b7 then we usually write f 1b instead of f 1b Regardless7 f 1b is still a subset of A 23 Example 231 EXAMPLE 231 Let A abcd and B Lg2 The function f is de ned by the relation pictured below 2 INTRODUCTION TO FUNCTIONS 17 o fa z o the image ofd is z o the domain off is A abed o the eodomain is B Lyn 0767 y 2 d 1 72 07570761 96 Discussion This example helps illustrate some of the differences between the codornain and the range fA gz is the range7 while the codornain is all of B Li2 Notice also that the image of a single element is a single element7 but the preirnage of a single element may be more than one element Here is another example EXAMPLE 232 Let f N a R be de ned by fn o The domain is the set of natural numbers 0 The eodomain is the set of real numbers 0 The range is 07 12 257 o The image of5 is o The preimage of5 is 25 o The preimage ofN is the set of all perfect squares in N EXERCISE 231 Suppose f R a R is de ned by fp Find 1 the range off 2 the image of Z the set of integers 3 f 17T39 4 f 1139 5 f KQ where Q is the set of rational numbers 24 Floor and Ceiling Functions DEFINITIONS 241 Floor and ceiling functions 0 The oor function denoted 2 INTRODUCTION TO FUNCTIONS 18 is the function that assigns to z the greatest integer less than or equal to x o The ceiling function denoted f 96 W u ceilingp is the function that assigns to z the smallest integer greater than or equal to x Discussion These two functions may be new to you The oor function W also known as the greatest integer function and the ceiling function Ix are assumed to have domain the set of all reals unless otherwise speci ed and range is then the set of integers EXAMPLE 241 a 35 3 b 35 4 c 735 74 d 735 73 e notice that the floor function is the same as truncation for positive numbers EXERCISE 241 Suppose z is a real number Do you see any relationships among the values Liz fix fix and EXERCISE 242 Suppose f R a R is de ned by u Find 1 the range off 2 the image of Z the set of integers 3 PM a flew 5 f 1N where N is the set of natural numbers 6 f 12555 9 f 1fI2555I 25 Characteristic Function De nition Let U be a universal set and A Q U The Characteristic Func tion of A is de ned by gt71 ifsEA XAS 0 ifs A 2 INTRODUCTION TO FUNCTIONS 19 Discussion The Characteristic function is another function that may be new to you EXAMPLE 251 Consider the set of integers as a subset of the real numbers Then Xzy will be 1 when y is an integer and will be zero otherwise EXERCISE 251 Graph the function XZ given in the previous ecoample in the plane EXERCISE 252 Find CHAPTER 2 Logic 1 Logic De nitions 11 Propositions DEFINITION 111 A proposition is a declarative sentence that is either true denoted either T or Z or false denoted either F or 0 Notation Variables are used to represent propositions The most common variables used are p q and r Discussion Logic has been studied since the classical Greek period 600 300BC The Greeks7 most notably Thales7 were the rst to formally analyze the reasoning process Aristo tle Z y84 Z y22BC7 the father of logic 7 and many other Greeks searched for universal truths that were irrefutable A second great period for logic came with the use of sym bols to simplify complicated logical arguments Gottfried Leibniz 1646 1716 began this work at age 147 but failed to provide a workable foundation for symbolic logic George Boole 1815 1864 is considered the father of symbolic logic He developed logic as an abstract mathematical system consisting of de ned terms propositions7 operations conjunction7 disjunction7 and negation7 and rules for using the opera tions It is this system that we will study in the rst section Boole7s basic idea was that if simple propositions could be represented by pre cise symbols7 the relation between the propositions could be read as precisely as an algebraic equation Boole developed an algebra of logic77 in which certain types of reasoning were reduced to manipulations of symbols 12 Examples EXAMPLE 121 quotDrilling for oil caused dinosaurs to become ECEtiTZCt is a propo sition 20 1 LOGIC DEFINITIONS 21 EXAMPLE 122 quotLook out is not a proposition EXAMPLE 123 quotHow far is it to the nept town is not a proposition EXAMPLE 124 quotz 2 2x is not a proposition EXAMPLE 125 quotp 2 2x when x 72 is a proposition Recall a proposition is a declarative sentence that is either true or false Here are some further examples of propositions EXAMPLE 126 All cows are brown EXAMPLE 127 The Earth is further from the sun than Venus EXAMPLE 128 There is life on Mars EXAMPLE 129 2 gtlt 2 5 Here are some sentences that are not propositions EXAMPLE 1210 quotDo you want to go to the movies Since a question is not a declarative sentence it fails to be a proposition EXAMPLE 1211 quotClean up your room Likewise an imperative is not a declar ative sentence hence fails to be a proposition EXAMPLE 1212 2p 2 x This is a declarative sentence but unless z is assigned a value or is otherwise prescribed the sentence neither true nor false hence not a proposition EXAMPLE 1213 quotThis sentence is false What happens if you assume this state ment is true false This eccample is called a paradocc and is not a proposition because it is neither true nor false Each proposition can be assigned one of two truth values We use T or 1 for true and use F or 0 for false 13 Logical Operators DEFINITION 131 Unary Operator negation quotnotp p DEFINITIONS 131 Binary Operators a conjunction p and q p 1 b disjunction quotp or q pV 1 c exclusive or quotepactly one ofp or q quotp cor q p EBq d implication quotifp then q p 1 e biconditional 2 if and only ifq p lt gt q 1 LOGIC DEFINITIONS 22 Discussion A sentence like I can jump and skip can be thought of as a combination of the two sentences I can jump and I can skip When we analyze arguments or logical expression it is very helpful to break a sentence down to some composition of simpler statements We can create compound propositions using propositional variables7 such as 1041735 and connectives or logical operators A logical operator is either a unary operator7 meaning it is applied to only a single proposition or a binary operator7 meaning it is applied to two propositions Truth tables are used to exhibit the rela tionship between the truth values of a compound proposition and the truth values of its component propositions 14 Negation Negation Operator7 not 7 has symbol EXAMPLE 141 p This book is interesting p can be read as i This book is not interesting ii This book is uninteresting iii It is not the case that this book is interesting Truth Table 10 10 T F F T Discussion The negation operator the a unary operator which7 when applied to a proposition p7 changes the truth value of p That is7 the negation of a proposition p7 denoted by p is the proposition that is false when p is true and true when p is false For example7 if p is the statement I understand this 7 then its negation would be I do not understand this or It is not the case that I understand this Another notation commonly used for the negation of p is N p Generally7 an appropriately inserted not or removed not is suf cient to negate a simple statement Negating a compound statement may be a bit more complicated as we will see later on 1 LOGIC DEFINITIONS 23 15 Conjunction Conjunction Operator7 and has symbol EXAMPLE 151 p This book is interesting q I am staying at home p q This book is interesting and I am staying at home Truth Table Discussion The conjunction operator is the binary operator which7 when applied to two propo sitions p and q yields the proposition p and q denoted pq The conjunction pq of p and q is the proposition that is true when both p and q are true and false otherwise 16 Disjunction Disjunction Operator7 inclusive or has symbol V EXAMPLE 161 p This book is interesting q I am staying at home p V q This book is interesting or I am staying at home Truth Table Discussion The disjunction operator is the binary operator which7 when applied to two propo sitions p and q7 yields the proposition p or q denoted p V q The disjunction p V q of p and q is the proposition that is true when either p is true7 q is true7 or both are true7 and is false otherwise Thus7 the or intended here is the inclusive or In fact7 the symbol V is the abbreviation of the Latin word yel for the inclusive or 1 LOGIC DEFINITIONS 24 L4 17 Exclusive 0139 Exclusive Or Operator7 xor 7 has symbol EB EXAMPLE 171 p This book is interesting q I am staying at home p Equ Either this book is interesting or I am staying at home but not both Truth Table Discussion The emelusive or is the binary operator which7 when applied to two propositions p and q yields the proposition p xor q denoted p 69 q7 which is true if exactly one of p or q is true7 but not both It is false if both are true or if both are false Many times in our every day language we use or77 in the exclusive sense In logic7 however7 we always mean the inclusive or when we simply use or77 as a connective in a proposition If we mean the exclusive or it must be speci ed For example7 in a restaurant a menu may say there is a choice of soup or salad with a meal In logic this would mean that a customer may choose both a soup and salad with their meal The logical implication of this statement7 however7 is probably not what is intended To create a sentence that logically states the intent the menu could say that there is a choice of either soup or salad but not both The phrase either or 77 is normally indicates the exclusive or 18 Implications Implication Operator7 ifthen has symbol a EXAMPLE 181 p This book is interesting q I am staying at home p a q If this book is interesting then I am staying at home Truth Table Equivalent Forms of If p then q 1 LOGIC DEFINITIONS 25 o p implies q o If p7 q o p only if q o p is a suf cient condition for q o q if p o q whenever p o q is a necessary condition for p Discussion The implication p a q is the proposition that is often read if p then qf7 If p then 177 is false precisely when p is true but q is false There are many ways to say this connective in English You should study the various forms as shown above One way to think of the meaning of p a q is to consider it a contract that says if the rst condition is satis ed7 then the second will also be satis ed If the rst condition7 p7 is not satis ed7 then the condition of the contract is null and void In this case7 it does not matter if the second condition is satis ed or not7 the contract is still upheld For example7 suppose your friend tells you that if you meet her for lunch7 she will give you a book she wants you to read According to this statement7 you would expect her to give you a book if you do go to meet her for lunch But what if you do not meet her for lunch She did not say anything about that possible situation7 so she would not be breaking any kind of promise if she dropped the book off at your house that night or if she just decided not to give you the book at all If either of these last two possibilities happens we would still say the implication stated was true7 because she did not break her promise 19 Terminology For the compound statement p a q p is called the premise hypothesis or the antecedent q is called the conclusion or consequent q a p is the converse of p a q p a g is the inverse of p a q q a p is the contrapositive of p a q Discussion We will see later that the converse and the inverse are not equivalent to the original implication7 but the contrapositive q a p is In other words7 p a q and its contrapositive have the exact same truth values 1 LOGIC DEFINITIONS 26 110 Example EXAMPLE 1101 Implication If this book is interesting then I am staying at home 0 Converse IfI am staying at home then this book is interesting 0 Inverse If this book is not interesting then I am not staying at home 0 Contrapositive If I am not staying at home then this book is not inter esting Discussion The converse of your friends promise given above would be if she gives you a book she wants you to read then you will meet her for lunch and the inverse would be If you do not meet her for lunch then she will not give you the book We can see from the discussion about this statement that neither of these are the same as the original promise The contrapositive of the statement is if she does not give you the book then you do not meet her for lunch This is in fact equivalent to the original promise Think about when would this promise be broken It should be the exact same situation where the original promise is broken 111 Biconditional Biconditional Operator if and only if has symbol EXAMPLE 1111 p This book is interesting q I am staying at home p lt gt q This book is interesting if and only if I am staying at home Truth Table Discussion The biconditional statement is equivalent to p a q q a p In other words for p lt gt q to be true we must have both p and q true or both false The difference between the implication and biconditional operators can often be confusing because in our every day language we sometimes say an ifthen statement p a q when we actually mean the bieonditional statement p lt gt q Consider the statement you may have heard from your mother or may have said to your children If you eat your 1 LOGIC DEFINITIONS 27 broccoli then you may have some ice cream77 Following the strict logical meaning of the rst statement the child still may or may not have ice cream even if the broccoli isn7t eaten The ifthen construction does not indicate what would happen in the case when the hypothesis is not true The intent of this statement however is most likely that the child must eat the broccoli in order to get the ice cream When we set out to prove a biconditional statement we often break the proof down into two parts First we prove the implication p a q and then we prove the converse q a p Another type of ifthen77 statement you may have already encountered is the one used in computer languages In this ifthen77 statement the premise is a condition to be tested and if it is true then the conclusion is a procedure that will be performed If the premise is not true then the procedure will not be performed Notice this is different from ifthen77 in logic It is actually closer to the biconditional in logic However it is not actually a logical statement at all since the conclusion77 is really a list of commands not a proposition 112 NAND and NOR Operators DEFINITION 1121 The NAND Operator which has symbol l quotShe er Stroke is de ried by the truth table DEFINITION 1122 The NOR Operator which has symbol 1 quotPeirce Arrow is de ried by the truth table Discussion These two additional operators are very useful as logical gates in a combinatorial circuit a topic we will discuss later 1 LOGIC DEFINITIONS 28 113 Example EXAMPLE 1131 Write the following statement symbolically and then make a truth table for the statement quotIfIgo to the mall or go to the movies then I will not go to the gym Solution Suppose we set 0 p go to the mall o q go to the movies 0 r I will go to the gym The proposition can then be eapressed as quotpr or q then not r or p V q a r Ma 1 TlqulnTlqu nr T T T T F F T T F T T T T F T T F F T F F T T T F T T T F F F T F T T T F F T F F T F F F F T T Discussion When building a truth table for a compound proposition you need a row for every possible combination of T7s and F7s for the component propositions Notice if there is only one proposition involved there are 2 rows If there are two propositions there are 4 rows if there are 3 propositions there are 8 rows EXERCISE 1131 How many rows should a truth table have for a statement in yoloing n di erent propositions propositions p q and r you would in theory only need four columns one for each of p q and r and one for the compound proposition under discussion which is p V q a r in this example In practice however you will probably want to have a column for each of the successive intermediate propositions used to build the nal one In this example it is convenient to have a column for pV q and a column for r so that the truth value in each row in the column for p V q a r is easily supplied from the truth values for p V q and r in that row Another reason why you should show the intermediate columns in your truth table is for grading purposes If you make an error in a truth table and do not give this 1 LOGIC DEFINITIONS 29 extra information7 it will be dif cult to evaluate your error and give you partial credit EXAMPLE 1132 Suppose p is the proposition quotthe apple is delicious and q is the proposition quotI ate the apple Notice the di erence between the two statements below a op q The apple is not delicious and I ate the apple b p q It is not the case that the apple is delicious and I ate the apple EXERCISE 1132 Find another way to eppress Example 1132 Part b without using the phrase quotIt is not the case EXAMPLE 1133 Eccpress the proposition quotIf you work hard and do not get dis tracted then you can nish the job symbolically as a compound proposition in terms of simple propositions and logical operators 0 p you work hard 0 q you get distracted o r you can nish the job In terms of p7 q7 and r7 the given proposition can be written p A w e r The comma in Example 1133 is not necessary to distinguish the order of the operators7 but consider the sentence If the sh is cooked then dinner is ready and I am hungry77 Should this sentence be interpreted as f a r h or f a r h7 where f7 r7 and h are the natural choices for the simple propositions A comma needs to be inserted in this sentence to make the meaning clear or rearranging the sentence could make the meaning clear EXERCISE 1133 Insert a comma into the sentence quotIf the sh is cooked then dinner is ready and I am hungry to make the sentence mean a f m TA1 b f a r h EXAMPLE 1134 Here we build a truth table forp a q a r and p q a r When creating a table for more than one proposition we may simply add the necessary columns to a single truth table 1 LOGIC DEFINITIONS 3O plqlrlq rlpAqlp M HpMn r TTT T T T T TTF F T F F TFT T F T T TFF T F T T FTT T F T T FTF F F T T FFT T F T T FFF T F T T EXERCISE 1134 Build one truth table for f a r h and f a r h 114 Bit Strings DEFINITION 1141 A bit is a U or a Z and a bit string is a list or string of bits The logical operators can be turned into bit operators by thinking of 0 as false and 1 as true The obvious substitutions then give the table U I0 0V00 0A00 0 00 0V11010 011 1V0110 101 1V1111 1 10 Discussion We can de ne the bitwise NEGATION of a string and bitwise OR bitwise AND and bitwise XOR of two bit strings ofthe same length by applying the logical operators to the corresponding bits in the natural way EXAMPLE 1141 a m 00101 b 11010v10001 11011 c 11010 10001 10000 d 11010 619 10001 01011 2 PROPOSITIONAL EQUIVALENCES 31 2 Propositional Equivalences 21 Taut ologyContr39adict ionContingency DEFINITION 211 A tautology is a proposition that is always true EXAMPLE 211 p V p DEFINITION 212 A contradiction is a proposition that is always false EXAMPLE 212 p p DEFINITION 213 A contigency is a proposition that is neither a tautology nor a contradiction EXAMPLE 213 p V q a r Discussion One of the important techniques used in proving theorems is to replace or sub stitute one proposition by another one that is equivalent to it In this section we will list some of the basic propositional equivalences and show how they can be used to prove other equivalences Let us look at the classic example of a tautology p V p The truth table shows that p V p is true no matter the truth value of p Side Note This tautology called the law of epeluded middle is a direct consequence of our basic assumption that a proposition is a statement that is either true or false Thus the logic we will discuss here so called Aristotelian logic might be described as a 2 valued logic and it is the logical basis for most of the theory of modern mathematics at least as it has developed in western culture There is however a consistent logical system known as constructivist or intuitionistic logic which does not assume the law of excluded middle This results in a 3 valued logic in which one allows for 2 PROPOSITIONAL EQUIVALENCES 32 a third possibility namely other7 In this system proving that a statement is not true77 is not the same as proving that it is false77 so that indirect proofs which we shall soon discuss would not be valid If you are tempted to dismiss this concept you should be aware that there are those who believe that in many ways this type of logic is much closer to the logic used in computer science than Aristotelian logic You are encouraged to explore this idea there is plenty of material to be found in your library or through the worldwide web The proposition p V p q is also a tautology as the following the truth table illustrates A W QlepM pVepAQ EXERCISE 211 Build a truth table to verify that the proposition p lt gt q pq is a contradiction WWQQB q T T F F T F F F aaauj aaaa 22 Logically Equivalent DEFINITION 221 Propositions r and s are logically equivalent if the statement r lt gt s is a tautology Notation If r and s are logically equivalent we write r s Discussion A second notation often used to mean statements r and s are logically equivalent is r E 5 You can determine whether compound propositions r and s are logically equivalent by building a single truth table for both propositions and checking to see that they have exactly the same truth values Notice the new symbol r gt s which is used to denote that r and s are logically equivalent is de ned to mean the statement r lt gt s is a tautology In a sense the 2 PROPOSITIONAL EQUIVALENCES 33 symbols lt gt and gt convey similar information when used in a sentence However r gt s is generally used to assert that the statement r lt gt s is in fact true while the statement r lt gt 5 alone does not imply any particular truth value The symbol gt is the preferred shorthand for is equivalent to7 23 Examples EXAMPLE 231 Show that p a q q a p is logically equivalent to p lt gt q Solution 1 Show the truth values of both propositions are identical TruthTable plqlp qlq p paqu p qu T T T T T T T F F T F F F T T F F F F F T T T T Solution 2 Epamine every possible case in which the statement p a q q a p may not have the same truth value as p lt gt q Case 1 Suppose p a q q a p is false andp lt gt q is true 0 Assume p a q is false Then p is true and q is false But if this is the case the p lt gt q is false 0 Assume q a p is false Then q is true andp is false But if this is the case the p lt gt q is false Case 2 Suppose p a q q a p is true andp lt gt q is false If the latter is false the p and q do not have the same truth value 0 Assume p is true andq is false Thenp a q is false the the conjunction is also must be false 0 Assume p is false andq is true Then q a p is false the the conjunction is also must be false We ecchausted all the possibilities so the two propositions must be logically equivalent Discussion 2 PROPOSITIONAL EQUIVALENCES 34 This example illustrates an alternative to using truth tables to establish the equiv alence of two propositions An alternative proof is obtained by excluding all possible ways in which the propositions may fail to be equivalent Here is another example EXAMPLE 232 Show p a q is equivalent to p q Solution 1 Build a truth table containing each of the statements plqlnqlp q npeg pWq T T F T F F T F T F T T F T F T F F F F T T F F Since the truth values for p a q and p q are exactly the same for all possible combinations of truth values of p and q7 the two propositions are equivalent Solution 2 We consider how the two propositions could fail be equivalent This can happen only if the rst is true and the second is false or vice versa Case 1 Suppose p a q is true and p q is false p a q would be true if p a q if false Now this only occurs if p is true and q is false However7 if p is true and q is false7 then p q will be true Hence this case is not possible Case 2 Suppose p a q is false and p q is true p q is true only if p is true and q is false But in this case7 p a q will be true So this case is not possible either Since it is not possible for the two propositions to have different truth values7 they must be equivalent EXERCISE 231 Use a truth table to show that the propositionsp lt gt q and p Bq are equivalent EXERCISE 232 Use the method of Solution 2 in Example 232 to show that the propositions p lt gt q and p 69 q are equivalent 2 PROPOSITIONAL EQUIVALENCES 35 24 Important Logical Equivalences The logical equivalences below are im portant equivalences that should be memorized Identity Laws Domination Laws ldempotent Laws Double Negation Law Commutative Laws Associative Laws Distributive Laws De Morgar s Laws Absorption Laws pTlt p pVFlt p pVT gtT pF gtF PVPltZgtP PAZMZHD upQ gtupv q upVQ gtup q 2 PROPOSITIONAL EQUIVALENCES 36 Implication Law p 1 gt 1 0 V I Contrapositive Law p a q gt g a p Tautology p V p gt T Contradiction p p gt F Equivalence p a q q a p gt p lt gt q Discussion Study carefully what each of these equivalences is saying With the possible exceptions of the De Morgan Laws7 they are fairly straight forward to understand The main dif culty you might have with these equivalences is remembering their names EXAMPLE 241 Use the logical equivalences above and substitution to establish the equivalence of the statements in Example Solution p a q gt bp V q Implication Law gt p q De Morgan s Law gt p q Double Negation Law This method is very similar to simplifying an algebraic expression You are using the basic equivalences in somewhat the same way you use algebraic rules like 2x73p r x 1x 7 3 1 x73 EXERCISE 241 Use the propositional equivalences in the list of important logical equivalences above to prove is t w a t a s a w is a tautology EXERCISE 242 Use tputh tables to verify De Morgan s Laws 25 Simplifying Propositions 2 PROPOSITIONAL EQUIVALENCES 37 EXAMPLE 251 Use the logical equivalences above to show that p V p q is a contradiction Solution np V up A 91 gt p 5 p 1 De Morgan s Law gt p p q Double Negation Law gt p p q Associative Law gt F q Contradiction gt F Domination Law EXAMPLE 252 Find a simple form for the negation of the proposition quotIf the sun is shining then I am going to the ball game Solution This proposition is of the form p a q As we showed in Example 232 its negation p a q is equivalent to p q This is the proposition quotThe sun is shining and I am not going to the ball game Discussion The main thing we should learn from Examples 232 and 252 is that the negation of an implication is not equivalent to another implication such as If the sun is shining then I am not going to the ball game77 or If the sun is not shining I am going to the ball game77 This may be seen by comparing the corresponding truth tables p q pang TPmQlt10TQ np q T T F F T T F T T T F T T F T F F T F F If you were to construct truth tables for all of the other possible implications of the form r a s where each of r and s is one of p p q or q you will observe that none of these propositions is equivalent to p a q 2 PROPOSITIONAL EQUIVALENCES 38 The rule p a q gt p q should be memorized One way to memorize this equivalence is to keep in mind that the negation of p a q is the statement that describes the only case in which p a q is false 26 Implication DEFINITION 261 We say the proposition r implies the proposition 5 and write r i s ifr a s is a tautology This is very similar to the ideas previously discussed regarding the gt verses lt gt We use r i s to imply that the statement r a s is true7 while that statement r a 5 alone does not imply any particular truth value The symbol i is often used in proofs as a shorthand for implies EXERCISE 261 Prove p a q g mp 27 Normal or Canonical Forms DEFINITION 271 Every compound proposition in the propositional variables p q r is uniquely equivalent to a proposition that is formed by taking the disjunction of conjunctions of some combination of the variablesp7 q7 r or their negations This is called the disjunctive normal form of a proposition Discussion The disjunctive normal form of a compound proposition is a natural and useful choice for representing the proposition from among all equivalent forms7 although it may not be the simplest representative We will nd this concept useful when we arrive at the module on Boolean algebra 28 Examples EXAMPLE 281 Construct a proposition in disjunctive normal form that is true precisely when I p is true and q is false Solution p g 2 p is true and q is false or when p is true and q is true Solution p q V p q 3 eitherp is true or q is true and r is false Solution p V q r gt p r V q r Distributive Law Notice that the second eccample could be simpli ed to just p 2 PROPOSITIONAL EQUIVALENCES 39 Discussion The methods by which we arrived at the disjunctive normal form in these examples may seem a little ad hoc We now demonstrate through further examples a sure re method for its construction 29 Constructing Disjunctive Normal Forms EXAMPLE 291 Find the disjunctive normal form for the proposition p a q Solution Construct a truth table forp a q p a q is true when either p is true and q is true or p is false and q is true or p is false and q is false The disjunctive normal form is then AthwAthwAnw Discussion This example shows how a truth table can be used in a systematic way to construct the disjunctive normal forms Here is another example EXAMPLE 292 Construct the disjunctive normal form of the proposition oako Solution Write out the truth table for p a q r 2 PROPOSITIONAL EQUIVALENCES 4O p q rp q TP Q TTT T F F TTF T T T TFT F F F FTT T F F TFF F T F FTF T T T FFT T F F FFF T T T The disjunctive normal form will be a disjunction of three conjunctions one for each row in the truth table that gives the truth value Tfor p a q r These rows have been bored In each conjunction we will use p if the truth value ofp in that row is T and p if the truth value ofp is F q if the truth value ofq in that row is T and no if the truth value ofq is F etc The disjunctive normal form for p a q r is then pAqA r V pAqA r V pA qA r because each of these conjunctions is true only for the combination of truth values of p q and r found in the corresponding row That is p q r has truth value T only for the combination of truth values in row 2 pAqA r has truth value T only for the combination of truth values in row 6 etc Their disjunction will be true for precisely the three combinations of truth values ofp q and r for which p a q r is also true Terminology The individual conjunctions that make up the disjunctive normal form are called minterms In the previous example the disjunctive normal form for the proposition p a q r has three minterms p q r p q r and mp q r 210 Conjunctive Normal Form The conjunctive normal form of a propo sition is another canonical form77 that may occasionally be useful but not to the same degree as the disjunctive normal form As the name should suggests after our discus sion above the conjunctive normal form of a proposition is the equivalent form that consists of a conjunction of disjunctions7 It is easily constructed indirectly using disjunctive normal forms by observing that if you negate a disjunctive normal form you get a conjunctive normal form For example three applications of De Morgan7s Laws gives ohm W V WA 11 lt pV Q10V 1 2 PROPOSITIONAL EQUIVALENCES Thus7 if you want to get the conjunctive normal form of a proposition7 construct the disjunctive normal form of its negation and then negate again and apply De Morgan7s Laws EXAMPLE 2101 Find the conjunctive normalform of the proposition go qVr Solution 1 Negate p q V r gt p V q r 2 Find the disjunctive normal form of p V q r 10 JDV TDVQ A nquot F T l F mamamaae amwaama F QQWQWWW WHQWWQW aamamaa lFF F T T T QWQWWWQW The disjunctive normal form for p V q r is owWTVnpqnTVnpnqnr 3 The conjunctive normal form for p q V r is then the negation of this last expression7 which7 by De Morgan7s Laws7 is pV qu pV qu quVr 3 PREDICATES AND QUANTIFIERS 42 3 Predicates and Quanti ers 31 Predicates and Quanti ers DEFINITION 311 A predicate or propositional function is a description of the property or properties a variable or subject may have A proposition may be created from a propositional function by either assigning a value to the variable or by quanti cation DEFINITION 312 The independent variable of a propositional function must have a universe of discourse which is a set from which the variable can take values Discussion Recall from the introduction to logic that the sentence z 2 2x is not a proposition but if we assign a value for x then it becomes a proposition The phrase z 2 27 can be treated as a function for which the input is a value of z and the output is a proposition Another way we could turn this sentence into a proposition is to quantify its variable For example for every real number x z 2 2x is a proposition which is in fact false since it fails to be true for the number x 0 This is the idea behind propositional functions or predicates As stated above a predicate is a property or attribute assigned to elements of a particular set called the universe of discourse For example the predicate z 2 2a where the universe for the variable x is the set of all real numbers is a property that some but not all real numbers possess In general the set of all z in the universe of discourse having the attibute Pz is called the truth set of That is the truth set of Pz is x E 32 Example of a Propositional Function EXAMPLE 321 The propositional function Pz is given by z gt 0 and the universe of discourse for z is the set of integers To create a proposition from P we may assign a value for x For eccample 0 setting z 73 we get 1373 quot3 gt 0 which is false 0 setting z 2 we get P239 2 gt 0 which is true 3 PREDICATES AND QUANTIFIERS 43 Discussion In this example we created propositions by choosing particular values for x Here are two more examples EXAMPLE 322 Suppose PW is the sentence quotx has fur and the universe of discourse for z is the set of all animals In this eccample PW is a true statement if z is a cat It is false though is z is an alligator EXAMPLE 323 Suppose Qy is the predicate y holds a world record and the universe of discourse for y is the set of all competitive swimmers Notice that the universe of discourse must be de ned for predicates This would be a di erent predicate if the universe of discourse is changed to the set of all competitive runners Moral Be very careful in your homework to specify the universe of discourse pre ciselyl 33 Quanti ers A quanti er turns a propositional function into a proposition without assigning speci c values for the variable There are primarily two quanti ers7 the universal quanti er and the existential quanti er DEFINITION 331 The universal quanti cation of PW is the proposition quotPW is true for all values z in the universe of discourse Notation For all z PW or For every x PW is written VxPW DEFINITION 332 The existential quanti cation of PW is the proposition quotThere epists an element x in the universe of discourse such that PW is true Notation There exists x such that PW or There is at least one x such that PW is written HzPW Discussion 3 PREDICATES AND QUANTIFIERS 44 As an alternative to assigning particular values to the variable in a propositional function we can turn it into a proposition by quantifying its variable Here we see the two primary ways in which this can be done the universal quanti er and the existential quanti er In each instance we have created a proposition from a propositional function by binding its variable 34 Example 341 EXAMPLE 341 Suppose Pz is the predicate z 2 2x and the universe of discourse for z is the set 1 23 Then 0 VzPx is the proposition quotFor every x in 1 2 3 z 2 2x This propo sition is false 0 3xPz is the proposition quotThere epists z in 1 23 such that z 2 2p This proposition is true 35 Converting from English EXAMPLE 351 Assume z is afocc Sz z is sly z is trustworthy and the universe of discourse for all three functions is the set of all animals 0 Everything is afopx VzFx o All forces are sly a o If any focc is sly then it is not trustworthy SW a Tz gt 3xFz SQ Discussion Notice that in this example the last proposition may be written syrnbolically in the two ways given Think about the how you could show they are the same using the logical equivalences in Module 22 3 PREDICATES AND QUANTIFIERS 45 3 6 Additional De nitions 0 An assertion involving predicates is valid if it is true for every element in the universe of discourse 0 An assertion involving predicates is satis able if there is a universe and an interpretation for which the assertion is true Otherwise it is unsatis able o The scope of a quanti er is the part of an assertion in which the variable is bound by the quanti er Discussion You would not be asked to state the de nitions of the terminology given but you would be expected to know what is meant if you are asked a question like Which of the following assertions are satis able777 37 Examples EXAMPLE 371 If the universe of discourse is U 1 23 then 1 Wm a P1 P2 P3 2 3xPp a P1 v P2 v P3 Suppose the universe of discourse U is the set of real numbers I If Pz is the predicate p2 gt 0 then VzPz is false since P0 is false 2 IfPx is the predicate x2 7 3x 7 4 0 then 3xPz is true since 1371 is true 3 IfPz is the predicate p2 z 1 0 then 3xPz is false since there are no real solutions to the equation x2 z 1 0 4 IfPz is the predicate quotIfz 31 0 then x2 2 1 then VzPx is false since P05 is false EXERCISE 371 In each of the cases above give the truth value for the statement if each of the V and 3 quanti ers are reversed 38 Multiple Quanti ers Multiple quanti ers are read from left to right EXAMPLE 381 Suppose Ppy is quotpy 1 the universe of discourse for z is the set of positive integers and the universe of discourse for y is the set of real numbers I VxVyPxy may be read quotFor every positive integer z and for every real number y xy 1 This proposition is false 3 PREDICATES AND QUANTIFIERS 46 2 VxHyPxy may be read quotFor every positive integer z there is a real number y such that zy 1 This proposition is true 3 HnyPzy may be read quotThere epists a real number y such that for every positive integer a zy 1 This proposition is false Discussion Study the syntax used in these examples It takes a little practice to make it come out right 39 Ordering Quanti ers The order of quanti ers is important they may not commute For example 1 VxVyPxy gt VszPy and 2 HzHyPzy gt HnyPzy but 3 VxHyPxy lt gt HszPy Discussion The lesson here is that you have to pay careful attention to the order of the quanti ers The only cases in which commutativity holds are the cases in which both quanti ers are the same In the one case in which equivalence does not hold Vz iPmy 5gt HyWPlt967ygt7 there is an implication in one direction Notice that if 3yVPy is true then there is an element 0 in the universe of discourse for y such that P e is true for all z in the universe of discourse for x Thus for all z there exists a y namely 0 such that Pxy That is VzHyPzy Thus HprPQ y i VxHyPx Notice predicates use function notation and recall that the variable in function notation is really a place holder The statement VxHyPxy means the same as Vs tPs t Now if this seems clear go a step further and notice this will also mean the same as VnyPyx When the domain of discourse for a variable is de ned it is in fact de ning the domain for the place that variable is holding at that time Here are some additional examples 3 PREDICATES AND QUANTIFIERS 47 EXAMPLE 391 Pxy is quotx is a citizen of y Qxy is quotx lives in y The universe of discourse ofx is the set of all people and the universe of discourse for y is the set of US states I All people who live in Florida are citizens of Florida VxQx Florida a Px Florida 2 Every state has a citizen that does not live in that state Vy3zPz7 y A nQW 9 EXAMPLE 392 Suppose Rxy is the predicate quotx understands y the universe of discourse for x is the set of students in your discrete class and the universe of discourse for y is the set of examples in these lecture notes Pay attention to the di erences in the following propositions I HxVyRxy is the proposition quotThere exists a student in this class who un derstands every example in these lecture notes 2 VnyRxy is the proposition quotFor every example in these lecture notes there is a student in the class who understands that example 3 VxHyRxy is the proposition quotEvery student in this class understands at least one example in these notes 4 HnyRxy is the proposition quotThere is an example in these notes that every student in this class understands EXERCISE 391 Each of the propositions in Example 392 has a slightly di erent meaning To illustrate this set up the following diagrams Write the ve letters ABCDE on one side of a page and put the numbers 1 through 6 on the other side The letters represent students in the class and the numbers represent examples For each of the propositions above draw the minimal number of lines connecting people to examples so as to construct a diagram representing a scenario in which the given proposition is true Notice that for any Chosen pair of propositions above you can draw diagrams that would represent situations where the two propositions have opposite truth values EXERCISE 392 Give a scenario where parts 1 and 2 in Example 392 have opposite truth values 310 Unique Existential DEFINITION 3101 The unique existential quanti cation of Px is the proposition quotThere exists a unique element x in the universe of discourse such that Px is true 3 PREDICATES AND QUANTIFIERS 48 Notation quotThere epists unique x such that Pz 07quot quotThere is epaetly one x Pz is written lePx Discussion Continuing with Example 3927 the proposition Vz lyRQy is the proposition Every student in this class understands exactly one example in these notes but not necessarily the same example for all students EXERCISE 3101 Repeat Epepeise 391 for the four propositions Vx lyRxy ElszRzy HxVyRxy and Vy lxRxy Remember A predicate is not a proposition until ail variables have been bound either by quanti cation or by assignment of a value 311 De Morganls Laws for Quanti ers o VxPz gt Hp PQ o HxPQ gt Vp PQ Discussion The negation of a quanti ed statement are obtained from the De Morgan7s Laws in Module 21 So the negation of the proposition Every sh in the sea has gills is the propo sition there is at least one sh in the sea that does not have gills If there is more than one quanti er7 then the negation operator should be passed from left to right across one quanti er at a time7 using the appropriate De Morgan7s Law at each step Continuing further with Example 3927 suppose we wish to negate the proposition Every student in this class understands at least one example in these notes Apply De Morgan7s Laws to negate the symbolic form of the proposition nVz3yRz7i e iRWwD gt Hsz RQy The rst proposition could be read It is not the case that every student in this class understands at least one example in these notes The goal7 however7 is to nd an expression for the negation in which the verb in each predicate in the scope of the 3 PREDICATES AND QUANTIFIERS 49 quanti ers is negated and this is the intent in any exercise quiz or test problem that asks you to negate the proposition 77 Thus a correct response to the instruction to negate the proposition Every student in this class understands at least one example in these notes77 is the proposition There is at least one student in this class that does not understand any of the examples in these notes77 EXERCISE 3111 Negate the rest of the statements in Example 392 It is easy to see why each of these rules of negation is just another form of De Mor gan7s Law if you assume that the universe of discourse is nite U x1z2 For example VzPx gt Pz1 Px2 PW so that VxPQ gt Pz1 Pz2 as Ham v am v v emu gt H PQ If U is an arbitrary universe ofdiscouse we must argue a little differently Suppose VxPQ is true Then VxPz is false This is true if and only if there is some 0 in U such that 130 is false This is true if and only if there is some 0 in U such that Pc is true But this is true if and only if Hz PQ The argument for the other equivalence is similar Here is a formidable example from the calculus Suppose a and L are xed real numbers and f is a real valued function of the real variable x Recall the rigorous de nition of what it means to say the limit of f as x tends to a is L lirn f L gt man for every 6 gt 0 there exists 6 gt 0 such that for every x if0lt lxial lt6then lfx7Ll lt6 Here the universe of discourse for the variables 6 6 and z is understood to be the set of all real numbers What does it mean to say that lirn fx 31 L In order to gure this out it is man useful to convert this proposition into a symbolic proposition So let P66x be the predicate 0 lt lx 7 al lt 6 and let Qe6 be the predicate lfx 7 Ll lt 6 3 PREDICATES AND QUANTIFIERS 50 It is perfectly OK to list a variable in the argument of a predicate even though it doesnt actually appear We can simplify the proposition somewhat by restricting the universe of discourse for the variables 6 and 6 to be the set of positive real numbers The de nition then becomes V636VzP66x a Qe57 Use De Morgan7s Law to negate V636VzP66x a Qe57 gt 36V63xP66x Qe6p and convert back into words There exists 6 gt 0 such that7 for every 6 gt 0 there exists x such that7 0lt lxial lt6and lfx7Ll 26 312 Distributing Quanti ers over Operators 1 VzPx gt VzPx VzQQ but 2 VzPx V lt gt VzPx V VxQz 3 3xPx V gt 3xPz V HpQQ but 4 3xPx lt gt 3xPz HzQQ Discussion Here we see that in only half of the four basic cases does a quanti er distribute over an operator7 in the sense that doing so produces an equivalent proposition EXERCISE 3121 In each of the two cases in which the statements are not equiv alent there is an implication in one direction Which direction In order to help you analyze these two cases consider the predicates Pz x 2 0 and Qp x lt 0 where the universe of discourse is the set of all real numbers CHAPTER 3 Methods of Proofs 1 Logical Arguments and Formal Proofs 11 Basic Terminology 0 An axiom is a statement that is given to be true 0 A rule of inference is a logical rule that is used to deduce one statement from others 0 A theorem is a proposition that can be proved using definitions7 axioms7 other theorems7 and rules of inference Discussion In most of the mathematics classes that are prerequisites to this course7 such as calculus7 the main emphasis is on using facts and theorems to solve problems Theorems were often stated7 and you were probably shown a few proofs But it is very possible you have never been asked to prove a theorem on your own In this module we introduce the basic structures involved in a mathematical proof One of our main objectives from here on out is to have you develop skills in recognizing a valid argument and in constructing valid mathematical proofs When you are rst shown a proof that seemed rather complex you may think to yourself How on earth did someone gure out how to go about it that way77 As we will see in this chapter and the next7 a proof must follow certain rules of inference and there are certain strategies and methods of proof that are best to use for proving certain types of assertions It is impossible7 however7 to give an exhaustive list of strategies that will cover all possible situations7 and this is what makes mathematics so interesting lndeed7 there are conjectures that mathematicians have spent much of their professional lives trying to prove or disprove with little or no success 1 2 More Terminology o A lemma is a pre theorem77 or a result which is needed to prove a theorem 0 A corollary is a post theorem or a result which follows from a theorem or lemma or another corollary 51 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 52 Discussion The terms lemma and corollary are just names given to theorems that play particular roles in a theory Most people tend to think of a theorem as the main result a lemma a smaller result needed to get to the main result and a corollary as a theorem which follows relatively easily from the main theorem perhaps as a special case For example suppose we have proved the Theorem If the product of two integers m and n is even then either m is even or n is even Then we have the Corollary If n is an integer and n2 is even then 71 is even Notice that the Corollary follows from the Theorem by applying the Theorem to the special case in which m 71 There are no rm rules for the use of this terminology in practice what one person may call a lemma another may call a theorem Any mathematical theory must begin with a collection of unde ned terms and axioms that give the properties the unde ned terms are assumed to satisfy This may seem rather arbitrary and capricious but any mathematical theory you will likely encounter in a serious setting is based on concrete ideas that have been developed and re ned to t into this setting To justify this necessity see what happens if you try to de ne every term You de ne a in terms of b and then you de ne b in terms of c etc If a b c are all different terms you are lead to an in nite chain of de nitions otherwise one of them is repeated and you are left with a circular chain of de nitions Neither of these alternatives is logically acceptable A similar criticism can be made for any attempt to prove every assertion Here are a few important examples of mathematical systems and their basic ingredients ln plane geometry one takes point and line as unde ned terms and assumes the ve axioms Euclidean geometry In set theory the concept of a set and the relation is an element of or E are left unde ned There are ve basic axioms of set theory the so called Zermelo Fraenkel axioms which we will use informally in this course rather than giving them a rigorous exposition In particular these axioms justify the set builder notation we discussed in Module 1 Sets and the existence of the power set of a set which we shall discuss later in Module 4 Set Operations The real number system begins with the four Peano Postulates for the positive integers taking the elements numbers in the set of positive integers as unde ned as well as the relation is a successor of between positive integers To say z is a successor of y turns out to mean that z y 1 The fourth Peano Postulate is the Principle of Mathematical lnduction which we shall use extensively in the next module From these modest beginnings and with a little help from set theory one can construct the entire set of real numbers including its order and completeness properties As with our treatment of set theory we shall with the one exception mentioned above use these axioms informally assuming the familiar model of the real 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 53 number line together with its important subsets the natural numbers the integers and the rational numbers Once we have the unde ned terms and axioms for a mathematical system we can begin de ning new terms and proving theorems or lemmas or corollaries within the system 13 Formal Proofs To prove an argument is valid 0 Assume the hypotheses are true 0 Use the rules of inference and logical equivalences to show that the conclusion is true Discussion What is a proof A proof is a demonstration or argument that shows beyond a shadow of a doubt that a given assertion is a logical consequence of our axioms and de nitions Thus in any problem in which you are asked to provide a proof your solution will not simply be a short answer that you circle There are certain rules that must be followed which we will get to shortly and certain basic knowledge must be assumed For example one may assume the axioms and any previously stated theorems unless the instructions state otherwise A large number of proofs simply involve showing that a certain de nition is satis ed In almost every case the assertions we will be proving are of the form if p then q where p and q are possibly compound propositions The proposition p is the hypothesis and q is the conclusion It is almost always useful to translate a statement that must be proved into an if then 77 statement if it is not already in that form To begin a proof we assume the hypotheses For example consider the argument Every dog will have his day Fido is a dog Therefore Fido will have his day The hypotheses of this argument are Every dog will have his day77 and Fido is a dog77 The conclusion is Fido will have his day77 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 54 14 Rules of Inference Modus Ponens or p the Law of Detachment p a q Disjunction Introduction p 39qu Conjunction Elimination p q Modus Tollens g 10 1 X p Hypothetical Syllogism p a q q a r pgt7 Disjunctive Syllogism p V q 1390 Conjunction lntroduction p q 39p q Constructive Dilemma p a q 7quot a s p V r 39q V 5 Discussion An argument is valid if it is uses only the given hypotheses together with the axioms7 de nitions7 previously proven assertions7 and the rules of inference which are listed above In those rules in which there is more than one hypothesis7 the order 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 55 of the hypotheses is not important For example modus tollens could be just as well stated P HJ wI X p The notation used in these slides is commonly used in logic to express an argument symbolically The propositions before the horizontal line are the hypotheses and the proposition below the line is the conclusion The symbol is a common shorthand for therefore Each of the rules of inference is a tautology expressed in a different form For example the rule of modus ponens when stated as a propositional form is the tau tology lPWPmQH g This can be veri ed using a truth table REMARK 141 An argument of the form 711 712 hn 39c s to valid if and only if the proposition hL hg hn a c is a tautology 15 Example 151 EXAMPLE 151 The following is a valid logical argument If the dog eats the cat food or scratches at the door then the parrot will bark If the cat eats the parrot then the parrot will not bark If the cat does not eat the parrot then it will eat the cat food The cat did not eat the cat food Therefore the dog does not eat the cat food either 959165 Discussion Here is how the hypotheses give us the conclusion 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 56 1 Assign propositional variables to the component propositions in the argument 0 d 7 the dog eats the cat food 0 s 7 the dog scratches at the door 0 p 7 the parrot will bark o c 7 the cat eats the parrot o e 7 the cat eats the cat food 2 Represent the formal argument using the variables dV87p C771 7C7e 16 d C40 Use the hypotheses7 the rules of inference7 and any logical equivalences to prove that the argument is valid Assertion Reason 1 no 7 e hypothesis 3 2 e hypothesis 4 3 0 steps 1 and 2 and modus tolleris 4 c 7 p hypothesis 2 5 p steps 3 and 4 and modus porieris 6 d V s 7 p hypothesis 1 7 d V 5 steps 5 and 6 and modus tolleris 8 d s step 7 and De Morgan7s law 9 d step 8 and conjunction elimination We could also determine if the argument is valid by checking if the proposition st 7 pc 7 7p c 7 e e 7 d is a tautology ln practice7 though7 it is more useful to recognize if the rules of inference have been applied appropriately or if one of the common fallacies have been used to determine if an argument is valid or not It will serve you better later on to understand the two column proof of a valid argument and to recognize how the rules of inference are applied EXERCISE 151 Give aformal proof that the following argument is valid Provide TCGSOTZS 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 57 aVb C ib a 16 Rules of Inference for Quanti ers WPW Universal lnstantiation 39Pc PW Universal Generalization 39VzPx 130 Existantial Generalization 393zPx 396P96 EXistential lnstantiation 39Pc Discussion Here is the list of additional rules of inference related to quanti ers The symbol 0 represents some particular element from the universe of discourse for the variable m In Universal lnstantiation7 c may be any element from the universe of discourse for x For exarnple7 suppose the universe of discourse is the set of real nurnbers7 and 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 58 Pz is the predicate x2 2 0 Since x2 2 0 for all s we may conclude a 7 b2 2 0 for arbitrary real numbers a and b Here 0 a 7 b We may also conclude 7702 2 0 ln Existential lnstantiation 0 must be chosen so that 130 is true For example suppose the universe of discourse is the set of integers and let Pz be the predicate z is a divisor of 17283 and 1 lt z lt 1728377 Then 3xPz is a true statement eg P3 We may then assume 0 is a divisor of 17283 and 1 lt c lt 17283 for some integer 0 Sometimes we may know a statement of the form 3xPx is true but we may not know exactly for what z in the domain of discourse gives us that this is true In a proof when we know the truth of 3xPx we can de ne a variable say 0 to stand for a xed element of the domain where 130 is true This is what Existential lnstantiation gives you An example in which we have this situation is by using the Intermediate Value Theorem from algebra Let f R a R be the polynomial fx 73z4 x3 2x 1 Since f1 1 f2 735 and f is continuous there must be a solution to fx 0 in the interval 1 2 It may not possible to nd this solution algebraically though and may only be possible to numerically approximate the root However if we needed to use the solution for some purpose we could simply say let 0 E 1 2 be such that fc 0 and this xes c as the solution we know exists in 1 2 Universal Generalization is a subtle and very useful rule and the meaning may not be clear to you yet The variable x stands for any arbitrary element of the universe of discourse You only assume z is a member of the universe and do not place any further restrictions on x If you can show Pz is true then it will also be true for any other object satisfying the same properties you7ve claimed for x In other words Pz is true for all the members of the universe VxPz You will see a standard approach in proving statements about sets is to use Universal Generalization 17 Example 171 EXAMPLE 171 Here is a simple argument using quanti ers 1 Every dog will have his day 2 Fido is a dog 3 Therefore Fido will have his day Discussion To verify this is a valid argument we use the same technique as before De ne the predicates 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 59 o z is a dog 0 D x has his day and let F represent Fido7 a member of the universe of discourse The argument becomes lt i MW Dl The proof is 1 a hypothesis 1 2 a DF step 1 and universal instantiation 3 hypothesis 2 4 DF steps 2 and 3 and modus ptmens 18 Fallacies The following are not valid argument forms Af rming the p q Consequent p Denying the p q Antecedent q Use the truth of the Begging the Question consequent 1n the or Circular Reasoning argument Discussion There are several common mistakes made in trying to create a proof Here we list three of the most common fallacies or errors in logic Since they are not valid arguments7 obviously you should not use them in a proof Just as important7 you should be able to recognize one of them if you were to encounter it in someone else7s argument 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 60 The fallacy of af rming the consequent occurs when the converse of a premise is used to prove a statement For example here is an argument using the fallacy of af rming the consequent EXAMPLE 181 If Jack lands the new account then he will get a raise Jack got a raise Therefore he landed the new account Note that p a q q a p is not a tautology so this is not a valid argument The if then 77 statement is not equivalent to its converse In the above example just because Jack got a raise you cant conclude from the hypothesis that he landed the new account The fallacy of denying the antecedent comes from the fact that an implication is not equivalent to its inverse Here is an example of incorrect reasoning using the fallacy of denying the antecedent EXAMPLE 182 If the cat is purring then he ate the canary The cat is not purring Therefore the cat didn t eat the canary In this example the hypothesis does not allow you to conclude anything if the cat is not purring only if he is purring The fallacy results from the fact that the propositional form p a q 1390 a g is not a tautology Begging the question or circular reasoning occurs when the conclusion itself is used in the proof Here is an example of this type of fallacy EXAMPLE 183 Prove If zy is divisible by 5 then is divisible by 5 or y is divisible by 5 Incorrect Proof39 If zy is divisible by 5 then zy Bk for some h Then z Bl for some l or y Bl for some l Hence z is divisible by 5 ory is divisible by 5 This argument breaks down once we assert without justi cation that either Bl for some l or y Bl for some l This of course is what we are trying to prove and it doesnt follow directly from xy Bk EXERCISE 181 Give a careful proof of the statement For all integers in and n ifm is odd and n is even then m n is odd EXAMPLE 184 Prove for all real x z lt z 1 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 61 PROOF First we x an arbitrary real number Let x E R We wish to show z lt z1 This inequality is equivalent to 0 lt x1 7x But by the commutative and associative properties of real numbers this inequality is equivalent to 0 lt 1 x 7 p or equivalently 0 lt 1 We know the last inequality is true and so the equivalent expression z lt z 1 is also true D ln the previous example we took the expression we wished to show was true and rewrote it several times until we reached an expression that we knew to be true This is a useful tool but one must be extremely cautious in using this technique Notice we did not actually assume what we wished to prove lnstead we used equivalences to rephrase what we needed to show EXAMPLE 185 Now here is an incorrect quotproo of the same statement in Ecc ercise 184 This proof would be marked wrong INCORRECT PROOF OF EXERCISE 184 Let x e R Then z lt z 1 x 0 lt x 1 7 z i 0 lt p 7 p 1 by the associative and commutative properties of real numbers Olt1 We know 0 lt1 D EXERCISE 182 Consider the following hypotheses If the car does not start today then I will not go to class IfIgo to class today then I will take the quiz IfI do not take the quiz today then I will ask the teacher for an eptra credit assignment I asked the teacher for an eptra credit assignment Determine whether each of the following are valid or invalid conclusions of the above hypotheses Why or why not I I did not go to class today 2 Remove the hypothesis quotI asked the teacher for an eptra credit assignment from the above assumptions Can one now conclude quotIf the car does not start today then I will ask the teacher for an eptra credit assignment for the remaining assumptions EXERCISE 183 Find the error in the proof of the following statement 1 LOGICAL ARGUMENTS AND FORMAL PROOFS 62 Suppose z is a positive real number Claim the sum ofz and its reciprocal is greater than or equal to 2 INCORRECT PROOF Multiplying by x we get 2 1 2 2x By algebra7 x2 7 2x 1 2 0 Thus x 7 12 2 0 Any real number squared is greater than or equal to 2 i 07 so m J1 2 2 1S true EXERCISE 184 Find the fallacy associated with the following Problem Solve for z given the equation xz 7 a 2 where a is a real number Incorrect Solution The given equation also implies that 1 i 1 m 57 so a a x 7 xz 7 7 f xz 7 a 2 Adding the original equation with this one gives 2E 2 a2 and thus a z 1 Notice however ifa 8 then x 9 according to the solution but this does not satisfy the original equation 2 METHODS OF PROOF 63 2 Methods of Proof 21 Types of Proofs Suppose we wish to prove an implication p a q Here are some strategies we have available to try 0 Trivial Proof If we know q is true then p a q is true regardless of the truth value of p o Vacuous Proof lfp is a conjunction of other hypotheses and we know one or more of these hypotheses is false7 then p is false and so p a q is vacuously true regardless of the truth value of q 0 Direct Proof Assume p7 and then use the rules of inference7 axiorns7 de nitions7 and logical equivalences to prove q 0 Indirect Proof or Proof by Contradiction Assume p and g and derive a contradiction r r 0 Proof by Contrapositive Special case of Proof by Contradiction Give a direct proof of t a p Can be thought of as a proof by con tradiction in which you assume p and g and arrive at the contradiction p A oo 0 Proof by Cases If the hypothesis p can be separated into cases p1 V p2 V Vpk7 prove each of the propositions p1 a Q7102 a q7 pk a q7 separately You may use different methods of proof for different cases Discussion We are now getting to the heart of this course methods you can use to write proofs Let7s investigate the strategies given above is some detail 22 Trivial ProofVacuous Proof EXAMPLE 221 Prove the statement If there are 100 students enrolled in this course this semester then 62 36 PROOF The assertion is trivially true7 since the conclusion is true7 independent of the hypothesis which7 may of may not be true depending on the enrollment D EXAMPLE 222 Prove the statement If 6 is a prime number then 62 30 PROOF The hypothesis is false7 therefore the statement is vacuously true even though the conclusion is also false D 2 METHODS OF PROOF 64 Discussion The rst two methods of proof the Trivial Proof and the Vacuous Proof are certainly the easiest when they work Notice that the form of the Trivial Proof q a p a q is in fact a tautology This follows from disjunction introduction since p a q is equivalent to p V q Likewise the Vacuous Proof is based on the tautology p a p a q EXERCISE 221 Fill in the reasons for the following proof of the tautology p a p a 1 W e p a 11 119 V w V Dl lt 19 V w V ell gt T V q lt T EXERCISE 222 Let A 123 and R 2321 A gtlt A Prove if abc E A are such that ab E R and bc E R then ac E R Since it is a rare occasion when we are able to get by with one ofthese two methods of proof we turn to some we are more likely to need In most of the following examples the underlying theorem may be a fact that is well known to you The purpose in presenting them however is not to surprise you with new mathematical facts but to get you thinking about the correct way to set up and carry out a mathematical argument and you should read them carefully with this in mind 23 Direct Proof EXAMPLE 231 Prove the statement For all integers in and n ifm and n are odd integers then m n is an even integer PROOF Assume m and n are arbitrary odd integers Then in and n can be written in the form m2a1andn2b1 where a and b are also integers Then in n 2a 1 2b 1 substitution 2a 2b 2 associative and commutative laws of addition 2a b 1 distributive law 2 METHODS OF PROOF 65 Since mn is twice another integer7 namely7 ab17 mn is an even integer D Discussion The rst strategy you should try when attempting to prove any assertion is to give a direct proof That is7 assume the hypotheses that are given and try to argue directly that the conclusion follows This is often the best approach when the hypotheses can be translated into algebraic expressions equations or inequalities that can be manipulated to give other algebraic expressions7 which are useful in verifying the conclusion Example 231 shows a simple direct proof of a very familiar result We are using the familiar de nitions of what it means for an integer to be even or odd An integer n is even if n 2k for some integer k an integer n is add if n 2k 1 for some integer k Study the form of this proof There are two hypotheses7 m is an odd integer and n is an odd integer and the conclusion is the statement m n is an even integer This theorem is a quanti ed statement for all integers m and n 7 or for all odd integers m and n In the proof we assumed the hypotheses held for arbitrarily integers m and 717 and then we wrote down equations that follow from the de nition of what it means for these integers to be odd Although this looks like a pretty obvious thing to do7 at least when you see someone else do it7 this step7 in which you bring your knowledge to the problem7 may seem like a big one to take7 and you may nd yourself stalling out at this point One possible reason this may happen is that you may be trying to do too much at once The cure for this is to be patient take small steps7 using the appropriate de nitions and previously proven facts7 and see where they lead When we wrote down m 2a 1 and n 2b 17 we did a number of fairly sophisticated things First7 we used our knowledge de nitions of what it means for an integer to be odd Second7 in order for this information to be useful7 we needed to translate this knowledge into a mathematical expression7 or expressions in this case7 that are subject to manipulation And third7 in setting up these expressions7 we needed to use appropriate mathematical notation7 so that we did not introduce any subtle or hidden relationships into the picture that are unwarranted by the hypotheses A common mistake of this type might arise as follows Well m is an odd integer7 so I can write m 2k 17 where k is an integer Since 71 is also an odd integer7 I can write 71 2k 17 where k is an integer Do you see the mistake By allowing the same letter k to represent what might be different integers7 we have inadvertently added another assumption7 namely7 that m 2 METHODS OF PROOF 66 nl Of course we didn7t mean to do this but unfortunately our intentions havent been carried out and so our proof breaks down at this point In order to maintain the arbitrariness of in and n we must allow at the least that they be different We accomplish this by choosing different letters a and b in our representations of in and n as twice an integer plus one There is nothing sacred about a and b we could have used Is and l or z and y or 04 and B or any pair of symbols that have not been appropriated for some other use Upon closer scrutiny this rst step now starts to seem like a big one indeedl Especially if we may not be sure just where it will lead The rest of the proof however proceeds fairly routinely We add in and n and observe that the resulting expression has a factor of 2 We now only have to get past the recognition problem observing that the resulting expression gives us what we were looking for Since we have expressed in n as twice another integer in n is by de nition an even integer By Universal Generalization we may now con dently declare QED the abbreviation of quod erat demonstrandurn or which was to be demonstrated Often a box at the end of a proof or the abbrviation QED is used at the end of a proof to indicate it is nished EXERCISE 231 Give a careful proof of the statement For all integers in and n ifin is odd and n is even then in n is odd 24 Proof by Contrapositive EXAMPLE 241 Prove the statement For all integers in and n if the product of in and n is even then in is even or n is even We prove the contrapositive of the statement fin and n are both odd integers then inn is odd PROOF Suppose that in and n are arbitrary odd integers Then in 2a 1 and n 2b 1 where a and b are integers Then inn 2a 12b 1 substitution 4ab 2a 2b 1 associative commutative and distributive laws 22ab a b 1 distributive law Since inn is twice an integer namely 2ab a b plus 1 inn is odd D Discussion 2 METHODS OF PROOF 67 If a direct proof of an assertion appears problematic the next most natural strat egy to try is a proof of the contrapositive ln Example 241 we use this method to prove that if the product of two integers in and n is even then m or n is even This statement has the form p a r V 5 If you take our advice above you will rst try to give a direct proof of this statement assume inn is even and try to prove in is even or n is even Next you would use the de nition of even to write mn 2k where h is an integer You would now like to conclude that m or n has the factor 2 This can in fact be proved directly but it requires more knowledge of number theory than we have available at this point Thus we seem to have reached a dead end with the direct approach and we decide to try an indirect approach instead The contrapositive ofp a r V s is r V s a p or by De Morgan7s Law r g a mp This translates into the statement If m and n are odd then inn is odd where not even translates to odd This is a good illustration of how the symbolic form of a proposition can be helpful in nding the correct statement we wish to prove In this particular example the necessity of De Morgan7s Law may be more evident in the symbolic form than in the English version Now we give a direct proof of the contrapositive we assume in and n are arbitrary odd integers and deduce inn is odd This proof is carried out in very much the same way as the direct proof in Example 231 The main dif culty we encounter with the problem of proving the original assertion is to realize that a direct proof should be abandoned in favor of some other strategy EXERCISE 241 The following statement is a special case of the proposition proved in Example 24 Give a careful proof of this statement without assuming the result in Example 24 For every integer n if n2 is even then n is even 25 Proof by Contradiction EXAMPLE 251 Prove the statement If 5x 25y 1723 then x ory is not an integer PROOF Assume 5x 25y 1723 and assume that both z and y are integers By the distributive law 5x 5y 1723 Since z and y are integers this implies 1723 is divisible by 5 The integer 1723 however is clearly not divisible by 5 This contradiction establishes the result D 2 METHODS OF PROOF 68 Discussion If we have tried unsuccessfully to nd a direct proof of a statement or its con trapositive7 we might next try to give a proof by contradiction In this method of proof we assume the hypotheses are true and the conclusion is false and try to arrive at a contradiction The validity of proof by contradiction follows from the fact that 51 q is equivalent to p a q if we can show that p q is false7 then 51 q is true7 so that the equivalent proposition p a q is also true In Example 251 we are asked to prove that if 5x 25y 17237 then x is not an integer or y is not an integer This has the same propositional form as the example in Example 241 p a r V 5 If we try to give a direct proof of this statement7 then we are forced to prove a negative7 which can be dif cult If we try to prove the contrapositive7 then knowing that z and y are integers doesnt seem to be helpful in trying to show directly that 5x 25y 31 17237 since we are again trying to prove a negative One the other hand7 if we assume p and r V s which is equivalent to r 55 then we have two positive statements to work with 5 25y 17237 and z and y are integers After a couple of observations we arrive at the contradiction r r where r is the statement 1723 is divisible by 577 This contradiction establishes the truth of the statement7 and we are through EXERCISE 251 Prove For all real numbers z and y if 35x 14y 253 then x is not an integer or y is not an integer Here is another example of a proposition that is best proved by contradiction EXAMPLE 252 For all positive real numbers a b and c ifab c then a S E orbg PROOF Suppose 17 b7 and c are positive real numbers such that ab c and suppose a gt E and b gt Notice the use of De Morgan7s Law again Also7 recall that the symbol E represents the positive square root of c not By order properties of the real numbers7 bgtElt abgtaE sinceagt07 and agtE gtaEgtEEC sinceEgt0 Thus7 ab gt rmE gt E E 0 implies ab gt c 2 METHODS OF PROOF 69 But ab c hence7 ab is not greater than c7 a contradiction This proves our assuption a gt E and b gt E cannot be true when a7 b7 and c are positive real numbers such that ab c Therefore a S E or b S D EXERCISE 252 Consider the statement For all nonnegative real numbers a b andc ifaZ b2 cz then ab 2 c a Give a proof by contradiction b Give a direct proof Hintx The ecctra idea needed for a direct proof should emerge naturally from a proof by contradiction Let7s step back and compare direct proof7 proof by contrapositive7 and proof by contradiction EXERCISE 253 Fill in the blanks If we are proving the implication p a q we assume for a proof by contrapositive 3 7 for a proof by contradiction I p for a direct proof 2 We are then allowed to use the truth of the assumption in Z 2 or 3 in the proof After the initial assumption we prove p a q by showing 4 q must follow from the assumptions for a direct proof 5 must follow the assumptions for a proof by contrapositive 6 must follow the assumptions for a proof by contradiction 26 Proof by Cases x27 1 EXAMPLE 261 Ifx is a real number such that 2 gt 0 then either z gt 1 or p i2ltplt71 PROOF Assume p is a real number for which the inequality holds Factor the numerator of the fraction to get the inequality x 1x 7 1 z 2 For this combination of z 17 z 7 17 and z 2 to be positive7 either all are positive or two are negative and the other is positive This gives four cases to consider gt0 2 METHODS OF PROOF 70 Case 1 z1 gt0x71 gt07 and x2 gt0 lnthis casez gt 71 gt17 andpgt 72 which implies z gt 1 Case 2 z1 gt0x71 lt07 and x2 lt0 lnthis casez gt 71 lt17 andplt 72 and there is no z satisfying all three inequalities simultaneously Case 3 z1 lt0x71 gt07 and x2 lt0 lnthis casez lt 71 gt17 andplt 72 and there is no z satisfying all three inequalities simultaneously Case 4 z1 lt0x71 lt07 and x2 gt0 lnthis casez lt 71 lt17 andpgt 72 which implies that 72 lt z lt 71 Thus7 either z gt 1 Case 1 or 72 lt z lt 71 Case 4 D Discussion Sometimes the hypothesis of a statement can be broken down into simpler cases that may be investigated separately The validity of a proof by eases rests on the equivalence p1VVpn ql lt 191 qVVpn ql ln Example 261 this method is used to verify the solution77 to the inequality7 x2 7 1 EXERCISE 261 Prove For every real number p p2 Hintx Recall as above that x p2 represents the positive square of 2 and look at two cases z 2 0 and z lt 0 A proof by cases can tend to be a little tedious Here is an extreme example of such a proof EXAMPLE 262 Prove that lfn is a natural number less than 41 then n2 7n41 is a prime number PROOF Recall that a prime number is an integer greater than 1 that is only divisible by itself and 1 It would be nice if there was some general line of argument that would work7 but7 unfortunately7 there doesnt seem to be an obvious one As a result7 the proof must be broken down into 41 cases corresponding to n 07 17 27 40 In each case we examine the integer n2 7 n 41 to see if it is prime For example7 we can observe 710 02704141 is prime 711 12714141isprime 712 22724143isprime 2 METHODS OF PROOF 71 713 327341 47 is prime 714 427441 53 is prime As 71 increases it becomes increasingly more time consuming to show that n2 7 n41 is indeed prime For example when n 40 402 7 40 41 1601 The simplest way to show that 1601 is prime is to show that every prime number 3 V1601 fails to be a divisor of 1601 There are 12 such numbers to try and you might as well check them on your calculator Alternatively you could write a computer program or use a symbolic program such as Maple or Mathematica that has a routine to test a number for primality 27 Existence Proofs An existence proof is a proof of a statement of the form HzPQ Existence proofs generally fall into one of the following two types Constructive Proof Establish 130 for some 0 in the universe of discourse Nonconstructive Proof Assume no 0 exists that makes 130 true and derive a contradiction 28 Constructive Proof EXAMPLE 281 Prove the statement There epists a triple abc of positive integers such that a2 b2 02 PROOF Choose a 3 b 4 and c 5 D Discussion In a constructive proof one nds an explicit example in the universe of discourse for which the statement is true Here is another example EXAMPLE 282 Prove If u x3 z 7 5 theri there epists a positive real number 0 such that f c 7 2 METHODS OF PROOF 72 PROOF Calculate the derivative of f f p 3x2 1 Then we want to nd a positive number c such that f c 3c2 1 7 Solving for c 3c2 6 c2 2 c ix2 Then c x2 is a positive real number and f 2 3x22 1 7 D 29 Nonconstructive Proof EXAMPLE 291 Pigeon Hole Principle Ifn 1 objects pigeons are dis tributed into n bocces pigeon holes then some bop must contain at least 2 of the objects PROOF Suppose the boxes are labeled B1B2 BL and assume that no box contains more than 1 object Let k denote the number of objects placed in B Then k S 1 for i 1 n and so k1k2hn3111 71 nterms But this contradicts the fact that k1 k2 kn n 1 the total number of objects we started with D Discussion Sometimes constructing an example may be dif cult if not impossible due to the nature of the problem If you suspect this is the case you should try a proof by contradiction Assume there is no such example and show that this leads to a contradiction If you are successful you have established existence but you have not exhibited a speci c example After you have studied the proof of the basic pigeon hole principal in Example 291 try your hand at the following variations EXERCISE 291 Prove If 2n 1 objects are distributed into n bodes then some bop must contain at least 3 of the objects EXERCISE 292 Fill in the blank in the following statement and then give a proof Suppose h is a positive integer If kn 1 objects are distributed into n bodes then some bop must contain at least of the objects 2 METHODS OF PROOF 73 EXERCISE 293 Suppose that 88 chairs are arranged in a rectangular array of8 rows and 11 columns and suppose 50 students are seated in this array 1 student per chair a Prove that some row must have at least 7 students b Prove that some column must have at most 4 students 210 Nonexistence Proofs Suppose we wish to establish the truth of the statement HxPQ which is equivalent to Vz PQ One way is to assume there is an member7 c7 of the universe of discourse for which Pc is true7 and try to arrive at a contradiction EXAMPLE 2101 Proue there does not ecclst an integer k such that 4k 3 is a perfect square PROOF Proof by Contradiction Assume there is an integer k such that 4h 3 is a perfect square That is7 4k 3 77127 where m is an integer Since the square of an even integer is even and 4h 3 is odd7 m must be odd Then m 2a 1 for some integer a Thus7 4h 3 m2 4k3 2a12 4k3 4a24a1 4k3 4a2a1 371 4a2a74k 2 4a2 a 7 k 1 2a2 a 7 k But this contradicts the fact that 1 is an odd integer D Discussion In order to show some property is false for every member of the universe of dis course it is almost always best to try to use a proof by contradiction Example 2101 illustrates a property of the integers that can be easily proved in this way EXERCISE 2101 Proue There does not ecclst a positive real number a such that a 7 lt 2 a 2 METHODS OF PROOF 74 211 The Halting Problem EXAMPLE 2111 The Halting Problem There does rtot eccist a program which will always determirte if art arbitrary program P halts We say the Haltirtg Problem is urtdecidable Note that this is hot the same as determining if a speci c program or rtite set of programs halts This is decidable PROOF We simplify the proof by only considering input free programs which may call other procedures Assume there is a program called Halt which will deter mine if any input free program P halts HaltP prints yes and halts if P halts HaltP prints no and halts otherwise Now we construct a new procedure procedure Absurd if HaltAbsurd yes then While true do print ha Notice that the procedure Absurd is input free Now we consider two cases Case 1 If Absurd halts then we execute the loop which prints unending gales of laugh ter and thus the procedure does not halt 7 a contradiction Case 2 If Absurd does not halt then we will exit the program and halt Again this is a contradiction Now the only assumption we made was that a program exists which determines if any program will halt Thus this assumption must be false There is no such program D 212 Counterexample Counterexample to VxPd We may disprove a statement of the form VxPx by nding a counterexample That is use the equiva lence VxPz gt Hx PQ and nd a c in the universe of discourse for which Pz is false Discussion From Example 261 one might be led to think that n2 in41 is a prime number for every natural number 71 After all it worked for the rst 41 natural numbers Or so you were led to believe Did you nish the remaining 35 cases Showing that a predicate PW is true for a few perhaps many millions of ms in its universe of discourse however does not constitute a proofof VxPd unless you were able to exhaust all possibilities This of course is not possible if the universe of discourse is 2 METHODS OF PROOF 75 an in nite set such as the set of natural numbers or the set of real numbers Since the negation of VzPx is VzPQ gt Hx PQ it only takes one x for which Pz is false a counterepample to disprove VxPQ The assertion for every natural number n n2 7 n 41 is prime77 is in fact false EXERCISE 2121 Find a counterecoample to the statement For every natural number n n2 7 n 41 is prime 213 Biconditional In order to establish the truth ofthe statement p lt gt q use the fact that p lt gt q is equivalent to p a q q a p and prove both implications using any of the previous methods Discussion We conclude this module with a discussion on proving a biconditional or if and only if 7 statement As pointed out above a proof of a biconditional requires two proofs the proof an implication and a proof of its converse Our example below is very similar to theorems we have proved earlier The point here is that the two implications may be proved independently of each other and the decision on the best strategy to use should be made for each one separately EXAMPLE 2131 Prove For any integer n n is odd if and only ifnz is odd In order to prove this statement we must prove two implications a Ifn is odd then n2 is odd b If n2 is odd then n is odd PROOF OF a We give a direct proof of this statement Assume n is an odd integer Then n 2a 1 for some integer a Then n2 2a 12 4a2 4a 1 22a2 2a 1 which is twice an integer plus 1 Thus n2 is odd D PROOF OF b We give a proof of the contrapositive of this statement If n is even not odd then n2 is even not odd Assume n is an even integer Then n 2a for some integer a Then n2 2a2 4a2 22a2 which is an even integer 3 MATHEMATICAL INDUCTION 76 3 Mathematical Induction 31 First Principle of Mathematical Induction Let Pn be a predicate with domain of discourse over the natural numbers N 0 1 2 If I P0 and ammapmu then VnPn Terminology The hypothesis P0 is called the basis step and the hypothesis Pn a Pn I is called the induction or inductive step Discussion The Principle of Mathematical Induction is an axiom of the system of natural numbers that may be used to prove a quanti ed statement of the form VnPn where the universe of discourse is the set of natural numbers The principle of induction has a number of equivalent forms and is based on the last of the four Peano Axioms we alluded to in Module 3 Introduction to Proofs The axiom of induction states that if S is a set of natural numbers such that 0 E S and ii if n E S then n 1 6 S then S N This is a fairly complicated statement Not only is it an if then statement but its hypotheses also contains an if then statement if n E S then n 1 E S When we apply the axiom to the truth set of a predicate Pn we arrive at the rst principle of mathematical induction stated above More generally we may apply the principle of induction whenever the universe of discourse is a set of integers of the form kk 1k 2 where k is some xed integer In this case it would be stated as follows Let Pn be a predicate over kk 1k 2k 3 where k E Z If I Pk and ammapmu then VnPn In this context the for all n of course means for all n 2 k 3 MATHEMATICAL INDUCTION 77 REMARK 311 While the principle of induction is a very useful technique for proving propositions about the natural numbers it isn t always necessary There were a number of emamples of such statements in Module 32 Methods of Proof that were proved without the use of mathematical induction Why does the principle of induction work This is essentially the domino effect Assume you have shown the premises In other words you know P0 is true and you know that Pn implies Pn I for any integer n 2 0 Since you know P0 from the basis step and P0 a P1 from the inductive step we have P1 by modus ponens Since you now know P1 and P1 a P2 from the inductive step you have P2 Since you now know P2 and P2 a P3 from the inductive step you have 3 And so on ad in nitum or ad nauseum 32 Using Mathematical Induction Steps 1 Prove the basis step 2 Prove the inductive step a Assume Pn for arbitrary n in the universe This is called the induction hypothesis b Prove Pn 1 follows from the previous steps Discussion Proving a theorem using induction requires two steps First prove the basis step This is often easy if not trivial Very often the basis step is P0 but sometimes when the universal set has k as its least element the basis step is Be careful to start at the correct place Next prove the inductive step Assume the induction hypothesis Pn is true You do not try to prove the induction hypothesis Now you prove that Pn1 follows from In other words you will use the truth of Pn to show that Pn I must also be true Indeed it may be possible to prove the implication Pn a Pn 1 even though the predicate Pn is actually false for every natural number n For example suppose 3 MATHEMATICAL INDUCTION 78 Pn is the statement 71 n 7 1 which is certainly false for all 71 Nevertheless it is possible to show that ifyou assume Pn then you can correctly deduce Pn 1 by the following simple argument PROOF If n n 7 1 then after adding 1 to both sides 71 1 n 711 n171 Thus Pn 7Pn1 D It is easy at this point to think you are assuming what you have to prove circular reasoning You must keep in mind however that when you are proving the impli cation Pn 7 Pn 1 in the induction step you are not proving Pn directly as the example above makes clear so this is not a case of circular reasoning To prove an implication all you need to show is that if the premise is true then the conclusion is true Whether the premise is actually true at this point of an induction argument is completely irrelevant EXERCISE 321 Notice in the above ecoample that while we proved VnPn 7 Pn 1 we did riot prove VnPn Why 33 Example 331 1 EXAMPLE 331 Prove 2239 W forn 0123 i0 1 PROOF Let Pn be the statement Zi i0 2 1 Basis Step 71 0 0 Prove Zi 00 12 13 Proof Zi 0 and 00 12 0 i0 Thus P0 2 Induction Step Let n E N At this step we are xing an arbitrary integer n 2 0 and making the following assumption for this xed 71 We then show the statement Pn 1 must also be true In general we assume the induction hypothesis for an integer at least as large as the integer used in the basis case V L i Assume 1371 Zi nn 12 for some integer n 2 0 i0 3 MATHEMATICAL INDUCTION 79 ii Use the induction hypothesis to prove it n 1 12 lid Write out the sum on the left hand side of the statement to be proven TH 2239 0123nn1 i0 0123nn1 n 1 i0 gt equal by the induction hypothesis r nn 1 2 n 1 7n2n2n27n23n2 ifif 7 n1n2 if n1n11 2 1 By the principle of mathematical induction it follows that 2239 W i0 for all natural numbers n D Discussion Example 331 is a classic example of a proof by mathematical induction In this example the predicate Pn is the statement n Z nn12 i0 3 MATHEMATICAL INDUCTION 80 TL Recall the Sigma notation Zai ak 1H1 aw ik It may be helpful to state a few cases of the predicate so you get a feeling for whether you believe its true and for the differences that occur when you change n But keep in mind that exhibiting a few cases does not constitute a proof Here are a few cases for Example 331 Notice what happens to the summation left hand side as you increase n 132 i 0122212 133 Z 01233312 H o In the basis step of an induction proof you only need to prove the rst statement above7 but not the rest In the induction step you assume the induction hypothesis7 Pn7 for some arbi trary integer n 2 0 Write it out so you know what you have to work with Then write out Pn1 so you can see what you need to prove It will be easier to see how to proceed if you write both of these down A common mistake students make is to V L think of Pn as a particular expression say7 Pn instead of as a sentence n i0 nn 1 i i i i 2 Once you have written down the induction hypothesis and what i0 you need to prove7 look for a way to express part of Pn I using In this n1 n example we use the summation notation Zai 11 can This is a typical 390 390 l l n1 step when proving a summation formula of this type After rewriting 2239 this way7 i0 3 MATHEMATICAL INDUCTION 81 71 we can apply the induction hypothesis to substitute nn 12 for 3 Note that 10 you should use the induction hypothesis at some point in the proof Otherwise it is not really an induction proof EXERCISE 331 Prove 22239 7 1 1 3 5 2n 7 1 n2 for all ngt1 DH i1 n 1 n EXERCISE 332 Prove Z 7 11 22 I n 1 EXERCISE 333 Prove 23 2 32 7 1 k1 34 Example 341 EXAMPLE 341 Prove 5n 5 S n2 for all integers n 2 6 PROOF Let Pn be the statement 5n 5 S n2 Basis Step 71 6 Since 56 5 35 and 62 36 this is clear Thus P6 Induction Step Assurne 1371 571 5 S n2 for some integer n 2 6 Use the induction hypothesis to prove 5n I 5 S n I First rewrite 5n I 5 so that it uses 571 5 5n15 5n55 By the induction hypothesis we know 5n55 n25 Now we need to show n25 S n12n22n1 To see this we note that when n 2 2 2n122215 and so this is also valid for n 2 6 Thus when n 2 6 5n15 5n55 5n55 n25 n25 n22n1 n22n1n12 3 MATHEMATICAL INDUCTION 82 Which shows 5n 1 5 S n 12 By the principle of mathematical induction it follows that 5n 5 S n2 for all integers n 2 6 D Discussion In Example 341 the predicate Pn is 5n5 S n2 and the universe of discourse is the set of integers n 2 6 Notice that the basis step is to prove P6 You might also observe that the statement P5 is false so that we cant start the induction any sooner In this example we are proving an inequality instead of an equality This actually allows you more fudge room but sometimes that extra freedom can make it a bit more dif cult to see what to do next In this example the hardest part conceptually is recognize that we need another inequality 5 3 271 1 which holds whenever n 2 2 A good approach to showing fn 1 S gn 1 is to start with fn 1 think of a way express fn 1 in terms of fn so that you can use the induction hypothesis then nd ways to get to gn 1 using further equalities or inequalities that go in the right directionl In the induction step we use the fact that if you know a S b then a 5 S b 5 The induction hypothesis gives us an inequality Then we add 5 to both sides of that inequality prove Pn 1 REMARK 341 In proving an identity or inequality you don t always have to start with the left side and work toward the right In Example 34 you might try to complete the induction step by starting with n 12 and showing that it is greater than or equal to 5n 1 5 The steps would go as follows n12 n22n1 n2 2n 1 2 5n 5 2n 1 by the induction hypothesis 5n52n15n12n1 5n12n125n15 ifnZ2 With this approach the place where the induction hypothesis comes in as well as the fact that we need the inequality 2n 1 2 5 for n 2 2 are perhaps a little more transparent EXERCISE 341 Prove 2n 1 S 2 for all n 2 3 Establish the induction step in two ways as suggested in the remark above Hintx 2 2 2 2 2n1 3 MATHEMATICAL INDUCTION 83 EXERCISE 342 Prove n23 S 2 for all n 2 5 Hintx Look for a place to use the inequality in the exercise above in the induction step 35 Example 351 EXAMPLE 351 Prove A set with n elements n 2 0 has exactly 2 subsets PROOF Let Pn be the statement A set with n elements has 2 subsets77 Basis Step n 0 The only set with 0 elements is the empty set 0 which has exactly one subset namely 0 We also have 20 1 therefore a set with 0 elements has exactly 20 subsets Thus P0 Induction Step Let n E N Assume Pn every set with n elements has 2 subsets Use the induction hypothesis to prove a set with n 1 elements has 2 subsets Suppose A is a set with n 1 elements say A 1102 anan1 Let B be the subset 1102 an of A Since B has n elements we can apply the induction hypothesis to B which says that B has exactly 2 subsets Each subset S of B corresponds to exactly two subsets of A namely S and S U an But every subset of A is of one of these two forms hence A has exactly twice as many subsets as B Thus A has exactly 2 2 2 subsets H E0 By the principle of mathematical induction it follows that a set with n elements has exactly 2 subsets for all n 2 0 D Discussion EXERCISE 351 Let A abcd e and B abcd List all the subsets of A in one column and all the subsets ofB in another column Draw a line connecting every subset ofA to a subset from B to demonstrate the 2 to Z correspondence used in the previous proof Note that an example such as this does not prove the previous Theorem but it does help to illustrate the tools used Induction is used in a variety of situations In Example 351 induction is used to establish a formula for the number of subsets of a set with n elements In this case we are not trying to prove an equality in the sense of establishing an identity as with the summation examples The induction step involves more pure reasoning77 than algebraic manipulation We have to devise a strategy to count the number of subsets of a set with n 1 elements given that we know a formula for the number of subsets of a set with n elements Having devised a strategy we then need to show that the formula works for a set with n 1 elements as well Once you begin to be pro cient in constructing inductive proofs of this type you are well on your way to a complete understanding of the induction process 3 MATHEMATICAL INDUCTION 84 7 1 EXERCISE 352 Prove For all n 2 0 a set with n elements has m subsets with emaetly two elements Hintx In order to complete the induction step try to devise a strategy similar to the one used in the ecoample in Example 35 It is interesting to observe that the formula works for sets with fewer than 2 elements Here is another type of problem from number theory that is amenable to induction EXAMPLE 352 Prove For every natural number n nn2 5 is a multiple of 6 ie nn2 5 equals 6 times some integer PROOF Let Pn be the statement nn2 5 is a multiple of 6 1 Basis Step n 0 002 5 0 0 6 Thus P0 2 Induction Step Suppose n E N and suppose nn2 5 is divisible by 6 Show that this implies n 12 5 is divisible by 6 In order to use the inductive hypothesis we need to extract the expression nn2 5 out of the expression n 1n 1 5 n1n125 n n1251n125 n n22n15n22n15 n n25n2n1n22n6 nn25 2n2nn22n6 n n253n23n6 n n253nn16 By the induction hypothesis the rst term on the right hand side nn2 5 is a multiple of 6 Notice that n and n 1 are consecutive integers hence one of them is even Thus nn 1 is a multiple of 2 and so 3nn 1 is a multiple of 6 If we write nn2 5 6k and 3nn 1 6t then n1n125nn253nn166k6l66kl1 o n 1n12 5 is a multiple of 6 Thus we have shown Pn a Pn 1 By the principle of mathematical induction nn2 5 is a multiple of 6 for every n 2 0 You may have noticed that in order to make the inductive step work in most of the examples and exercises we have seen so far the restriction placed on n is actually 3 MATHEMATICAL INDUCTION 85 used either implicitly or explicitly whereas in the previous example it was not At no place in the inductive step above did we need the assumption that n 2 0 This leaves open the possibility that nn2 5 is a multiple of 6 for someall integers n lt 0 as well Checking some cases we see for 76 is a multiple of 6 5 718 is a multiple of 6 742 is a multiple of 6 784 is a multiple of 6 EXERCISE 353 Use mathematical induction to prove that nn2 5 is a multiple of 6for all n S 0 Hint39 You will have to nd the appropriate predicate Pk EXERCISE 354 Prove 52n 1 1 is divisible by 6 for n E Z5 EXERCISE 355 Prove a 7 b is a factor of a 7 b Hint aki l 7 bk1 aak 7 bk bka 7 b EXERCISE 356 The following is an incorrect proof that any group ofn horses are the same color What is the error in the proof PROOF The basis case is certainly true since any group of 1 horse is the same color Now let n E Z4r and assume any group of n horses are the same color We need to show any group of n 1 horses is the same color Let h1h2 hn1 be a set of n 1 horses The set h1 h2 hn is a set of n horses and so these horses are the same color Moreover the set h2 h3 hn1 is a set of n horses so they are all the same color Therefore the set of horses h1h2 hn1 must all be the same color D 36 The Second Principle of Mathematical Induction Let k be an inte ger and let Pn be a predicate whose universe of discourse is the set of integers kk 1k 2 Suppose I Ph and 2 Pj for h Sj S n implies Pn 1 Then VnPn Discussion 3 MATHEMATICAL INDUCTION 86 The second principle of induction differs from the rst only in the form of the induction hypothesis Here we assume not just Pn but Pj for all the integers j between h and n inclusive We use this assumption to show Pn 1 This method of induction is also called strong mathematical induction It is used in computer science in a variety of settings such as proving recursive formulas and estimating the number of operations involved in so called divide and conquer77 procedures EXERCISE 361 Prove the rst principle of b t39 39 J quot is j 39 39 t to the second principle of mathematical induction EXAMPLE 361 Prove Every integer n 2 2 can be expressed as a product of one or more prime numbers A prime number is de ned to be an integer greater than one that is only divisible by itself and one PROOF Recall that a prime number is an integer 2 2 that is only divisible by itself and 1 The number 1 is not considered to be prime Let Pn be the predicate n can be expressed as a product of prime numbers77 1 Basis Step n 2 Since 2 is prime 2 can be expressed as a product of prime numbers in a trivial way just one factor Thus P2 is true E0 Induction Step Let n be an integer with n 2 2 Suppose that every integer j 2 S j S n can be expressed as a product of prime numbers The integer n 1 is either a prime number or it is not Case 1 If n 1 is a prime number then it is a product of prime numbers in a trivial way Case 2 If n 1 is not a prime number then n 1 a b where a and b are positive integers both different from n 1 and 1 Thus 2 S a S n and 2 S b S n By the induction hypothesis a and b can each be expressed as a product of prime numbers say a p1p2p and b q1q2 q5 Since n 1 a b p1p2pq1q2qs n 1 can also be expressed as a product of prime numbers namely the product of primes that multiply to give a times the product of primes that multiply to give b By the second principle of mathematical induction every n 2 2 can be expressed as a product of prime numbers Discussion In this example the rst principle of induction would be virtually impossible to apply since the integer n is not a factor of n 1 when n 2 2 That is knowing the factors of n doesn7t tell us anything about the factors of n 1 3 MATHEMATICAL INDUCTION 87 37 WellOrdered Sets DEFINITION 371 A set S is wellordered if every subset has a least element Wellordering Principle The set N of natural numbers forms a well ordered set Discussion As we prove below7 the principle of induction is equivalent to the well ordering principle EXAMPLE 371 The set S of integers greater than 75 is a well ordered set EXAMPLE 372 The set P of rational numbers greater than or equal to zero is not a well ordered set EXAMPLE 373 01 is not well ordered The subset 01 does not have a least element in the set You may have to think about this for a moment EXAMPLE 374 The set Z of integers is not well ordered since Z itself does not have a least element Study the proof of the following theorem carefully Although it uses methods of proof discussed in Module 32 its level of abstraction may make it a bit dif cult to absorb at rst THEOREM 371 The seeondprineiple of b 39 quot J quot is j 39 39 to the well ordering principle PROOF We must show that each principle implies the other H Suppose N satis es the principle of mathematical induction7 and suppose that A is a nonempty subset of N We will give a proof by contradiction that A has a least element Suppose A does not have a least element Let Pn be the predicate n Z A Then i 0 Z A Otherwise7 0 would be the least element of A Thus P0 ii Let n E N Suppose Pk for 0 S h S n Then 0n Z A If n 1 were in A7 then n 1 would be the least element of A Thus7 n 1 Z A7 and so Pn 1 This proves that P0 Pn a Pn 1 By the First Principle of Mathematical Induction7 VnPn Vnn Z A But this means that A is empty7 a contradiction Thus N is well ordered Suppose N is well ordered7 and suppose Pn is a predicate over N that satis es the hypotheses of the First Principle of Mathematical Induction That is7 i 1307 and ii P0 Pn a Pn 1 E0 3 MATHEMATICAL INDUCTION 88 We will prove VnPn by contradiction Suppose VnPn Let A be the set of all n E N such that Pn is false ie Pn Then A is nonernpty since VnPn gt Hn Pm Since N is well ordered and A is a nonempty subset of N A has a least elernent k In other words if Pn fails to be true for all n then there is a srnallest natural number k for which Pk is false By i k 31 0 hence k gt 0 which implies k 7 1 is a natural number Since k 7 1 lt k and k is the least element of A k 7 1 Z A so that Pk 7 1 But by ii Pk 7 1 implies Pk or k Z A which contradicts k E A Therefore VnPn and so N satis es the principle of mathematical induction D CHAPTER 4 Applications of Methods of Proof 1 Set Operations 11 Set Operations The set theoretic operations7 intersection7 union7 and complementation7 de ned in Module 1 Introduction to Sets are are analgous to the operations 7 V7 and respectively7 that were de ned for propositions lndeed7 each set operation was de ned in terms of the corresponding operator from logic We will discuss these operations in some detail in this section and learn methods to prove some of their basic properties Recall that in any discussion about sets and set operations there must be a set7 called a universal set7 that contains all others sets to be considered This term is a bit of a misnomer logic prohibits the existence of a set of all sets7 so that there is no one set that is universal in this sense Thus the choice of a universal set will depend on the problem at hand7 but even then it will in no way be unique As a rule we usually choose one that is minimal to suit our needs For example7 if a discussion involves the sets 17 234 and 2468107 we could consider our universe to be the set of natural numbers or the set of integers On the other hand7 we might be able to restrict it to the set of numbers 12734756777879710 We now restate the operations of set theory using the formal language of logic 12 Equality and Containment DEFINITION 121 Sets A and B are equal denoted A B if VEAlt gtEB Note This is equivalent to V A EBEBgtEA DEFINITION 122 Set A is contained in set E or A is a subset of B denoted A g Bif Vzz A z B 1 SET OPERATIONS 90 The above note shows that A B iff A Q B and B Q A 13 Union and Intersection DEFINITIONS 131 o The union ofA and B AUBxz AVEB o The intersection ofA and B A Bxz AEB o IfA B Q then A and B are said to be disjoint 14 Complement DEFINITION 141 The complement ofA AEU z AE Ulz A Discussion There are several common notations used for the complement of a set For exam ple7 Ac iio en used to denote the compliment of A You may nd it easier to type A0 than A7 and you may use this notation in your homework 15 Difference DEFINITION 151 The difference ofA and B or the complement ofB rela tive to A AiBA DEFINITION 152 The symmetric difference ofA and B AEBB AiBUBiA AUB i A B Discussion The difference and symmetric difference of two sets are new operations7 which were not de ned in Module 1 Notice that B does not have to be a subset of A for 1 SET OPERATIONS 91 the difference to bede ned This gives us another way to represent the complement of a set A namely A U 7 A where U is the universal set The de nition of the difference of two sets A and B in some universal set U is equivalent to A 7 B x E Ulx E A z E Many authors use the notation A B for the difference A 7 B The symmetric difference of two sets corresponds to the logical operation 8 the exclusive or The de nition of the symmetric difference of two sets A and B in some universal set U is equivalent to A BzEUld A zEBV z Az B 16 Product DEFINITION 161 The Cartesian Product of two sets A and B is denoted A gtlt B and is de ned by AgtltBabla AbEB 17 Power Set DEFINITION 171 Let S be a set The power set of S denoted 335 is de ned to be the set of all subsets of S Discussion Keep in mind the power set is a set where all the elements are actually sets and the power set should include the empty set and itself as one of its elements 18 Examples EXAMPLE 181 Assume U abcdefgh A abcde B cdef dndC abcg h Then a AUBabcdef b A Bcde C f9h d B 07579771 e A7Bab f BiAf 1 SET OPERATIONS 92 h A U B 0 abe i A X B 07 07d 0767a7ft 570 57d 5767b7f7070707d7 076 67f7d707 617607 d767d7f76707 67d 676 67f 039 WA 7a7b7Elmd767a7b7a70707d7a767b707b7d7b767 cdeedeabeabdabeaedaeeadebed beebdeedeabedabeeabdeaedebede abed e k WM 32 EXERCISE 181 Use the sets given in Example 18 to nd I B gtltA 2 333 3 WW EXAMPLE 182 Let the universal set be U Z4r the set of all positive integers let P be the set of all prime positive integers and let E be the set of all positive even integers Then a P U E n E Zln is prime or even b P o E 2 e P is the set of all positive composite integers d E is the set of all positive odd integers 2n 1ln E N e P 7 E is the set of all positive odd prime numbers all prime numbers ecoeept 2 f EiP46810 inn ZAn2 2 g E EDP n E Zln is prime or even n 31 2 EXERCISE 182 11flAl n and B in how many elements are in A gtlt B 2 US is a set with 8 n what is EXERCISE 183 Does A gtlt B B gtlt A Prove your answer 19 Venn Diagrams A Venn Diagram is a useful geometric Visualization tool when dealing with three or fewer sets The Venn Diagram is generally set up as follows 0 The Universe U is the rectangular box 0 A set are represented by a circle and its interior 0 In the absence of speci c knowledge about the relationships among the sets being represented the most generic relationships should be depicted Discussion 1 SET OPERATIONS 93 Venn Diagrams can be very helpful in visualizing set operations when you are dealing with three or fewer sets not including the universal set They tend not to be as useful however when considering more than three sets Although Venn diagrarns may be helpful in visualizing sets and set operations they will not be used for proving set theoretic identities 110 Examples EXAMPLE 1101 The following Venn Diagrams illustrate generic relationships between two and three sets respectively U U A 1 B A B C EXAMPLE 1102 This Venn Diagram represents the di erenee A7 B the shaded region U AB 2 A A The gures in the examples above show the way you might draw the Venn diagram if you arent given any particular relations among the sets On the other hand if you knew for example that A Q B then you would draw the set A inside of B 1 SET OPERATIONS 94 111 Set Identities EXAMPLE 1111 Prove that the complement of the union is the intersection of the complements AUBZ F Proof 1 One way to show the two sets are equal is to use the fact that Step1 ShowAUB QA P Assume z is an arbitrary element of AU B and show z E A i Since z 6 AU B7 z Z AU B This means z Z A and z Z B De Morgan7s Law Hence z E A F Thus7 by Universal Generalization7 Vxhe AUBgt AW so that7 by de nition7 AuBgZ E Step 2 ShowA FQ AUB Suppose z is an arbitrary element of A F Then z Z A and z Z B Therefore7 z Z A U B De Morgan7s Law This shows z E A U B Thus7 by Universal Generalization7 Vxhe AWPgtEAUB so that7 by de nition7 A FQAUB Proof 2 The following is a second proof of the same result7 which emphasizes more clearly the role of the de nitions and laws of logic We will show Vzx AUBlt gtx A 1 SET OPERATIONS 95 Assertion Reason Vx z E m gt z Z A U B De nition of complement gt x 6 A U B De nition of Z gt z E A V x E B De nition of union gt n z E A z E B De Morgan7s Law gt x E A x E F De nition of complement gt z E A F De nition of intersection Hence Vxlx E A U B lt gt z E A F is a tautology D In practice we usually omit the formality of writing Va in the initial line of the proof and assume that z is an arbitrary element of the universe of discourse Proof 3 A thirgl way to prove this identity is to build a membership table for the sets A U B and A B7 and show the membership relations for the two sets are the same The 17s represent membership in a set and the 07s represent nonmembership lAlBlAUBlAUBlZlF Z F 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 Compare this table to the truth table for the proof of De Morgan7s Law up V 1 H up A W Discussion A set identity is an equation involving sets and set operations that is true for all possible choices of sets represented by symbols in the identity These are analgous to identities such as abaib azib2 1 SET OPERATIONS that you encounter in an elementary algebra course There are various ways to prove an identity7 and three methods are covered here This is a good place to be reminded that when you are proving an identity7 you must show that it holds in all possible cases Remember7 giving an example does not prove an identity On the other hand7 if you are trying to show that an expression is not an identity7 then you need only provide one counterexample Recall the negation of VxPz Proof 1 Proof 2 Proof 3 is Hs Px establishes equality by showing each set is a subset of the other This method can be used in just about any situation Notice that in Proof 1 we start with the assumption7 z is in A U B7 where z is otherwise an arbitrary element in some universal set If we can show that z must then be in A F then we will have established V AUB Z That is7 the modus operandi is to prove the implications hold for an arbitrary element x of the universe7 concluding7 by Universal Generalization7 that the implications hold for all such x Notice the way De Morgan7s Laws are used here For example7 in the rst part of Proof 17 we are given that z Z A U B This means areAUBlt z AVz Blt z Az Bl more clearly exposes the role of De Morgan7s Laws Here we prove the identity by using propositional equivalences in conjunction with Universal General ization When using this method7 as well as any other7 you must be careful to provide reasons provides a nice alternative when the identity only involves a small number of sets Here we show two sets are equal by building a member table for the sets The member table has a 1 to represent the case in which an element is a member of the set and a 0 to represent the case when it is not The set operations correspond to a logical connective and one can build up to the column for the set desired You will have proved equality if you demonstrate that the two columns for the sets in question have the exact same entries Notice that all possible membership relations of an element in the universal set for the sets A and B are listed in the rst two columns of the membership table For example7 if an element is in both A and B in our example7 then it satis es the conditions in the rst row of the table Such an element ends up in neither of the two sets AU B nor A g This is very straight forward method to use for proving a set identity It may also be used to prove containment If you are only trying to show the containment M Q N7 you would build the membership table for M and N as above Then you would look in every row where M has a 1 to see that 1 SET OPERATIONS 97 N also has a 1 However7 you will see examples in later modules where a membership table cannot be created It is not always possible to represent all the different possibilities with a membership table EXAMPLE 1112 Prove the identity A U B 0 A 0 U B 0 Proof 1 Suppose z is an arbitrary element of the universe Assertion Reason z E A U B 0 gt x E A U B x E 0 de nition of intersection gt E A V x E B x E 0 de nition of union gt E A x E 0 V E B x E 0 distributive law of and77 over or gt m E A 0 V E B 0 de nition of intersection gt z E A 0 U B 0 de nition of union Proof 2 Build a membership table A B o AUB A O B O AUB O A OUB O 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Since the columns corresponding to AUB 0 and A 0 U B 0 are identical7 the two sets are equal D 1 SET OPERATIONS 98 EXAMPLE 1113 Prove A 7 B 7 O Q A 7 B 7 O PROOF Consider the membership table A B7A7B B7OA7E7O A7B7O 11 1 0 0 0 1 1 10 0 1 0 0 10 1 1 0 0 1 10 0 1 0 1 1 0 11 0 0 0 0 0 10 0 1 0 0 0 01 0 0 0 0 0 00 0 0 0 0 Notice the only 1 in the column for A7B 7 C is the fourth row The entry in the same row in the column for A7B7C is also 2117 so A7B7C Q A7B7C D EXERCISE 1111 Prove the identitiy A 7 B A WE using the method of Proof 2 in Example 1111 EXERCISE 1112 Prove the identitiy A 7 B A WE using the method of Proof 3 in Example 1111 EXERCISE 1113 Prove the identity A U B 7 C A 7 C U B 7 C using the method of Proof 1 in Example 1111 EXERCISE 1114 Prove the identity A U B 7 C A 7 C U B 7 C using the method of Proof2 in Example 1111 EXERCISE 1115 Prove the identity A U B 7 C A 7 C U B 7 C using the method of Proof3 in Example 1111 112 Union and Intersection of Indexed Collections DEFINITION 1121 The the union and intersection of an indexed collection of sets A17A27A377An can be written as UampampUUampUmuamp i1 1 SET OPERATIONS 99 n AA1 A2 A3 An i1 respectively 113 In nite Unions and Intersections DEFINITION 1131 The the union and intersection of an indeced collection of in nitely many sets A17A27A377 can be written as UA ala E A foiquot somei in Z i1 A ala e A for alli m 2 i1 Discussion If you have a collection of more than two sets you can de ne the intersection and the union of the sets as above Since the operations are associative it isnt necessary to clutter the picture with parentheses The notation is similar to the E notation used for summations The subscript is called an indecc and the collection of sets is said to be indecced by the set of indices In the example the collection of sets is A1A2 AL and the set of indices is the set 1 2 There is no requirement that sets with different indices be different In fact they could all be the same set This convention is very useful when the each of the sets in the collection is naturally described in terms of the index usually a number it has been assigned An equivalent de nition of the union and intersection of an indexed collection of sets is as follows UA xl i E 12 n such that z 6 Ai 1 1 and A 95M 6 12nz 6 Ai 1 1 1 SET OPERATIONS 100 Another standard notation for unions over collections of indices is UampUamp ieZ i1 More generally if 3 is any set of indices we can de ne UA xBi E 3 such that z 6 Al is 114 Example 1141 EXAMPLE 1141 Let A ii 1 wherei is a positive integer Then A 1n 1 and CS i1 o Ai ifngt1 i1 Uampum i1 o 38 E H s l Discussion This is an example of a collection of subsets of the real numbers that is naturally indexed If A ii 1 then A1 1 2 A2 23 A3 34 etc It may help when dealing with an indexed collection of sets to explicitly write out a few of the sets as we have done here EXAMPLE 1142 Suppose C i 7 2i71ii1i 2 where i denotes and arbitrary natural number Then o 00 7271012 o 01710123 o 02 01234 U0727101nn1n2 i0 002 1 SET OPERATIONS 101 o Ci if71gt4 10 UO72710123 EXERCISE 1141 For each positive integer k let Ak E Z For eparnple o A171l71 ZZ 0 A2 271l71 E Z 72 07274767 0 A3 371l71 E Z 730 3 6 9 Find 10 1 Ak k1 m 2 Ak where 711 is an arbitrary positive integer 111 EXERCISE 1142 Use the de nition for Ak in eccercise 114 to answer the fol lowing questions 1 Q A 2 U A 115 Computer Representation of a Set Here is a method for storing sub sets of a given nite universal set Order the elements of the universal set and then assign a bit number to each subset A as follows A bit is 1 if the element corresponding to the position of the bit in the universal set is in A and 0 otherwise EXAMPLE 1151 Suppose U 123456789 10 with the obvious order ing Then 0 The bit string corresponding to A 246810 is 0101010101 0 The bit string corresponding to B 1234 is 1111000000 1 SET OPERATIONS 102 Discussion There are many ways sets may be represented and stored in a computer One such method is presented here Notice that this method depends not only on the universal set but on the order of the universal set as well If we rearrange the order of the universal set given in Example 1151 to U 10987654321 then the bit string corresponding to the subset 1 234 would be 0000001111 The beauty of this representation is that set operations on subsets of U can be carried out formally using the corresponding bitstring operations on the bit strings representing the individual sets EXAMPLE 1152 For the sets AB Q U in Example 115 z m 1010101010 1357 9 A 0 B 0101010101 v 1111000000 1111010101 12346810 A B 0101010101 1111000000 0101000000 274 A 619 B 0101010101 619 1111000000 1010010101 136810 EXERCISE 1151 Let U abcdefghij with the given alphabetical or der Let A 1 ei B abd eg hj and C ac egi I Write out the bit string representations for A B and C 2 Use these representations to nd a C bAUB cA B C 1370 1 SET OPERATIONS 103 2 PROPERTIES OF FUNCTIONS 104 2 Properties of Functions 21 Injections Surjections and Bijections DEFINITION 211 Given f A a B N f is onetoone short hand is 1 7 1 or injective if preimages are unique In this case a 31 b a fa 31 fb f is onto or surjective if every y E B has a preimage In this case the range of f is equal to the eodomain f is bijective if it is surjeetiue and injectiue one to one and onto 16 93 Discussion We begin by discussing three very important properties functions de ned above H A function is injectiue or one to one if the preimages of elements of the range are unique In other words7 if every element in the range is assigned to exactly one element in the domain For exampe7 if a function is de ned from a subset of the real numbers to the real numbers and is given by a formula y x then the function is one to one if the equation u b has at most one solution for every number b A function is surjeetiue or onto if the range is equal to the codomain In other words7 if every element in the codomain is assigned to at least one value in the domain For exampe7 if7 as above7 a function is de ned from a subset of the real numbers to the real numbers and is given by a formula y x then the function is onto if the equation u b has at least one solution for every number b 3 A function is a bijection if it is both injective and surjective E0 22 Examples EXAMPLE 221 Let A abcd and B Lg2 The function f is de ned by the relation pictured below This function is neither injectiue nor surjeetiue a 2 PROPERTIES OF FUNCTIONS 105 EXAMPLE 222 f A a B where A a7b7c7d and B Lyn de ned by the relation below is a surjection but not an injection 1 EXAMPLE 223 f A a B where A a7b7c7d and B y7w7z7y72 de ned by the relation below is an injection but not a surjection 11 2 EXAMPLE 224 f A a B where A a7b7c7d and B y7w7z7y de ned by the relation below both a surjection and an injection and therefore a bijection Notice that for a function to be a bijection the domain and codornain must have the same cardinality a 1 b w C i Discussion 2 PROPERTIES OF FUNCTIONS 106 The examples illustrate functions that are injective7 surjective7 and bijective Here are further examples EXAMPLE 225 Let f 000 a 000 be de ned by fp This function is an injection and a surjection and so it is also a bijection EXAMPLE 226 Suppose fp 2 If the domain and codomain for this function is the set of real numbers then this function would be neither a surjection nor an injection It is not a surjection because the range is not equal to the codomain For epample there is no number in the domain with image 71 which is an element of the codomain It is not an injection since more than one distinct element in the domain is mapped to the same element in the codomain For epample f71 f1 but 71 7 1 EXERCISE 221 What if we say the domain of the function in Example 226 is the set of all reals and the codomain is 0 00 Which properties would the function have injectiue andor surjectiue Emplain EXERCISE 222 Now if we say the domain and the codomain are both 000 What properties does the function in Example 226 have Emplain 23 Example 231 EXAMPLE 231 Prove that the function f N a N be de ned by fn n2 is injectiue PROOF Let ab E N be such that fa fb This implies a2 b2 by the de nition of f Thus a b or a 7b Since the domain of f is the set of natural numbers7 both a and b must be nonnegative Thus a b This shows VaVbfa fb a a b7 which shows f is injective D Discussion In Example 231 we prove a function is injective7 or one to one Notice that to prove a function7 f A a B is one to one we must show the following V96 E AWy E Al96 7 y n Wt 7 fyl This is equivalent to showing V96 E AWy E Alf96 fy 96 10l To prove this statement which actually uses the contrapositive of the de nition we begin by choosing two arbitrary elements of the domain and assume the hypothesis 2 PROPERTIES OF FUNCTIONS 107 of the implication ie we begin with Let Ly E A and assume fd y77 We then use the rules of algebra to show that the conclusion must follow 24 Example 241 EXAMPLE 241 Prove that the function g N a N de ned by gn 713 is smjeetz39oe PROOF Let n E N Notice that g3n n Since 3n 6 N this shows n is in the range of 9 Hence 9 is surjective D Discussion To prove a function f A a B is surjective or onto we must show fA B In other words we must show the two sets fA and B are equal We already know that fA Q B if f is a well de ned function While most functions encountered in a course using algebraic functions are well de ned this should not be an automatic assumption in general With that said though we will usually assume the functions given to us are well de ned so all that must be shown is that B Q fA To do this we may use the de nition of a subset show every element of B is also an element of fA Thus we begin the proof by xing an arbitrary element of B We then use the tools at our disposal de nition of the function algebra any other known information to show that this arbitrary element must in fact be the image of some element of A 25 Example 251 EXAMPLE 251 Prove that the function g N a N de ned by gn 713 is not injectioe PROOF The numbers 1 and 2 are in the domain of g and are not equal but 91 92 0 Thus 9 is not injective Discussion To show a function is not injective we must show nlV96 E AWy E Al96 7e 1 Wt 7e fyll This is equivalent to 396 6 Amy 6 Al96 7e 1 Wt fyl 2 PROPERTIES OF FUNCTIONS 108 Thus when we show a function is not injective it is enough to nd an example of two different elements in the domain that have the same image 26 Example 261 EXAMPLE 261 Prove that the function f N a N be de ned by fn n2 is not surjeetz39ue PROOF The number 3 is an element of the codomain7 N However7 3 is not the square of any integer Therefore7 there is no element of the domain that maps to the number 37 so f is not surjective Discussion To show a function is not surjective we must show fA 31 B Since a well de ned function must have fA Q B7 we should show B Z fA Thus to show a function is not surjective it is enough to nd an element in the codomain that is not the image of any element of the domain You may assume the familiar properties of numbers in this module as done in the previous examples 2 7 Inverse Functions DEFINITION 271 Suppose f A a B is 1 Injection Then the inverse of f denoted fil B a A is the function de ned by the rule f 1y x if and only if fx y Discussion If a function f is a bijection7 then it makes sense to de ne a new function that reverses the roles ofthe domain and the codomain7 but uses the same rule that de nes f This function is called the inverse of the f If the function is not a bijection7 it does not have an inverse You have seen many functions in algebra and calculus that are de ned as inverses of other functions For example7 the square root function V is de ned by the rule y if and only if y 2 0 and y2 x That is7 the square root function is the inverse of the square function Before we can invert the square function7 however7 its usual domain7 the set of all real numbers7 must be restricted to the set of nonnegative real numbers in order to have a bijection That is7 if A B x E R z 2 07 2 PROPERTIES OF FUNCTIONS 109 then the function f A a B de ned by fx x2 is a bijection and its inverse f l B a A is the square root function f 1 p Another important example from algebra is the logarithm function If a is a positive real number different from 1 and RJV x E R z gt 0 the function f R a RJV de ned by fp am is a bijection lts inverse f l Rf a R is the logarithm function with base a f 1p loga x In other words y logaz if and only if ay x EXAMPLE 271 Let f A a B where A abcd and B vwpy be de ned as follows a 1 b w C i day Then the inverse function is f l B a A de ned as follows v a w b x c 9d L 72 1 is the inverse off This is a good example of an EXAMPLE 272 Suppose f R743 a Rig is de ned by fp 2 Then the function f 1x z algebraically de nedfunction whose inverse has a nice formula specifying its rule You p may recall that the formula de ning f 1 can be obtained by setting y fp p interchanging z and y and solving algebraically for y 72 EXERCISE 271 Find the inverse of the function f R7 72 a Rig de ned byfltz2 2 PROPERTIES OF FUNCTIONS 110 EXERCISE 272 Find the inverse of the function f R a 7001 de ned by u 1 7 e m THEOREM 271 If dfunetion is d bijeetion then its inverse is also a bijeetion PROOF Let f A a B be a bijection and let f l B a A be its inverse To show f 1 is a bijection we must show it is an injection and a surjection Let 172 E B be such that f 1x1 f 1d2 Then by the de nition of the inverse we have 1 ff 1z2 2 This shows f 1 is injective We leave the proof that f 1 is surjective as an exercise for the reader D EXERCISE 273 Finish the proof of Theorem 27 28 Inverse Image DEFINITION 281 Let f A a B and let S be a subset of B Then the inverse image ofS under f is the set f 1S 96 E ADM E 5 There is no requirement for f to be injectiue or surjeetiue for this de nition to hold EXAMPLE 281 Let f A a B where A abed and B Luz be de ned as follows 1 bay 0amp2 d 0 f 12 07d 0 f 17y 075 Discussion We revisit the de nition of the inverse image of a set to emphasis the difference between the inverse image of a subset of the eodomdin and the inverse of a function The inverse image of a set is the set of all elements that map into that set The function does not have to be injective or surjective to nd the inverse image of a set For example7 the function fn 1 with domain and codomain all natural numbers 2 PROPERTIES OF FUNCTIONS 111 would have the following inverse images f 11 N and fquotl56787 9 0 This function does not have an inverse7 however The context of the use of the notation f l usually indicates if the inverse image or the inverse function is intended If A is a subset of the codomain we would always assume f 1A is the inverse image of A When discussing a bijection the distinction between the inverse image and inverse function is often blurred 29 Composition DEFINITION 291 Let f A a B and g B a C The composition ofg with f denotedg o f is the function from A to 0 de ned by g o EXAMPLE 291 Let A abcd B owzy and C 735 and let f A a B andg B a C by de ned as follows a i o r b w 10 c z dt d y 9 a 7 Discussion The composition of two functions is de ned by following one function by another To de ne the composition 9 of we must have the range of f contained in the domain of g 2 PROPERTIES OF FUNCTIONS 112 210 Example 2101 EXAMPLE 2101 Prove that the composition of two injectiue functions is injectiue PROOF Let AB and C be sets and let f A a B and g B a C be two injections Suppose z and y are elements of A such that g o g o This means gfz Since the codomain of f is B7 u E B and fy E B Thus we have two elements of B7 u and y such that gfx Since 9 is injective7 we must have fp But now we may use the fact that f is injective to conclude z y This shows that g o f is an injection D Discussion Sometimes we have to prove properties about functions without any speci c for mula for the functions In Example 2101 we prove that the composition of two injections is again an injection We cannot use speci c examples of function be cause that would not prove this more general statement We have to use the tools given by the assumptions namely7 that we know the two functions that make up the composition are known to be injections EXERCISE 2101 Prove the composition of two supjections is a surjection THEOREM 2101 Corollary to Example 2101 and Exercise 2101 The compo sition of two bijections is a bijection EXERCISE 2102 Prove 07quot disprove if the composition of two functions is an injection then the two original functions must be injections too EXERCISE 2103 Prove 07quot disprove if the composition of two functions is an suijection then the two original functions must be supjections too 3 RECURRENCE 113 3 Recurrence 31 Recursive De nitions To construct a recursively de ned function 1 Initial Conditions or basis Prescribe initial values of the function 2 Recursion Use a xed procedure rule to compute the value of the function at the integer n 1 using one or more values of the function for integers S n To construct a recursively de ned set 1 Initial Conditions or basis Prescribe one or more elements of the set 2 Recursion Give a rule for generating elements of the set in terms of previously prescribed elernents Discussion In computer programming evaluating a function or executing a procedure is often accomplished by using a recursion A recursive process is one in which one or more initial stages of the process are speci ed7 and the nth stage of the process is de ned in terms of previous stages7 using some xed procedure In a computer program this is usually accomplished by using a subroutine7 such as a For loop7 in which the same procedure is repeated a speci ed number of times that is7 the procedure calls itself EXAMPLE 311 The function fn 2 where n is a natural number can be de ned recursively as follows 1 Initial Condition f0 1 2 Recursion fn 1 2 fn for n 2 0 For any particular n this procedure could be programmed by rst initializing F 1 and then epecuting a loop quotFori 1 to n 2 gtk F F Here is how the de nition gives us the rst few powers of 2 2120112022 222111212224 23221222428 3 RECURRENCE 114 32 Recursive de nition of the function fn nl EXAMPLE 321 The factorial function fn n is de ned recursively as follows 1 Initial Condition f0 1 2 Recursion fn 1 n 1fn Discussion Starting with the initial condition f0 1 the recurrence relation fn 1 n 1fn tells us how to build new values of f from old values For example 1 f1 1f0 1 2x f2 2f1 2 3 f3 3f2 6 etc When a function fn such as the ones in the previous examples is de ned recursively the equation giving fn 1 in terms of previous values of f is called a recurrence relation 33 Recursive de nition of the natural numbers DEFINITION 331 The set of natural numbers may be de ned recursively as fol laws 1 Initial Condition 0 E N 2 Recursion Ifn E N then n 1 6 N Discussion There are a number of ways of de ning the set N of natural numbers recursively The simplest de nition is given above Here is another recursive de nition for N EXAMPLE 331 Suppose the set S is de ned recursively as follows 1 Initial Condition 01 6 S 2 Recursion If Ly E S then x y E S 3 RECURRENCE 115 Then S N Notice that in the recursive step z and y don t have to represent dz erent num bers Thus haulngxy 1 E S we get11 2 E S Then we get12 3 E S And so on It should be noted that there is an ecstremal clause in recursively de ned sets If you cannot build a given element in a nite number of applications of the recursion then it is not in the set built from the recursive de nition To prove an element is in a recursively de ned set you must show that element can be built in a nite number of steps EXAMPLE 332 Prove that the set S recursively in Example 331 is equal to the set N of natural numbers PROOF We will show that S N by showing separately that S Q N and N Q S H First we show N Q S Prove by induction that n E S for every natural number n 2 0 a Basis Step 01 6 S by de nition b lnduction Step Suppose n E S for some n 2 1 Then by the recursion step nESand1 Simplyn1 S Thus by the rst principle of mathematical induction n E S for every natural number n 2 0 Now we show S Q N This time we apply the second principle of mathematical induction on n to show that if s E S is produced by applying n steps 1 initial condition and n 7 1 recursive steps then s E N a Basis Step After one step the only elements produced are 0 and 1 each of which is in N b lnduction Step Suppose n 2 1 and assume any element in S produced by applying n or fewer steps is also an element of N Suppose s E S is produced by applying n 1 steps Since n 1 2 2 there must be two elements z and y in S such that s xy Both z and y must have been produced by applying fewer than n1 steps since 5 is produced by applying n1 steps and we use one step to obtain 5 from x and y By the induction hypothesis both z and y are element of N Since the sum of two natural numbers is again a natural number we have s E N E0 D 34 Proving assertions about recursively de ned objects Assertions about recursively de ned objects are usually proved by mathematical induction Here are three useful versions of induction In particular note the third version which we introduce here 3 RECURRENCE 116 Version 1 Second Principle of Induction a Basis Step Prove the assertion for the initial conditions The assertion Version 2 a b F7 may have to be veri ed for more than one particular value lnduction Step Assume the assertion is true for integers S n and use the recurrence relation to prove the assertion for the integer n 1 Basis Step Prove the assertion for the initial conditions The assertion may have to be veri ed for more than one particular value lnduction Step Assume the assertion is true when the recursive de nition has been applied less than or equal to n times for some integer n 2 0 and use the recurrence relation to prove the assertion when the recursive de nition is applied n 1 times Version 3 Generalized 0r Structural Principle of Induction Use to prove an assertion about a set S de ned recursively by using a set X given in the basis and a set of rules using 5152 5k 6 S for producing new members in the recursive set a Basis Step Prove the assertion for every 5 E X b lnduction Step Let 5152sk E S be arbitrary and assume the assertion for these elements this is the induction hypothesis Prove all elements of S produced using the recursive de nition and 51 52 satis es the assertion Discussion EXAMPLE 341 Let S a subset ofN gtlt N be de ned recursively by 1 Initial Condition 00 6 S 2 Recursion If mn E S then m 2n 3 E S Prove that if mn E S then m n is a multiple of 5 PROOF We use the Generalized Principle of lnduction 8k 1 Basis Step Show the statement for 00 0 0 is a multiple of 5 Since 0 0 5 this is clear E0 lnductive Step Let mn E S and assume in n is a multiple of 5 Show the statement is true for m 2n 3 In other words show in 2 n 3 is a multiple of 5 m2n3mn5 We know in n is a multiple of 5 and clearly 5 is a multiple of 5 so the sum must also be a multiple of 5 This proves the induction step 3 RECURRENCE 117 Therefore7 by the rst principle of mathematical induction if in7 n 6 S7 then m n is a multiple of 5 D EXERCISE 341 Suppose a S is de ned recursively as follows 11ES 2prSthen2zES Prove that S 2 ln 2 0 EXERCISE 342 Suppose a S is de ned recursively as follows 1 01ES 2 Ifxy S thenpy S What are the elements ofS Prove that your answer is correct EXAMPLE 342 Suppose fn is de ned by 1 Initial Condition f0 0 2 Recursion fn 1 fn n 1 for n 2 0 Then fn w for all n 2 0 PROOF 1 Basis Step n 0 f0 07 by de nition On the other hand 0 0 l 0 0 1 0 Thus f0 l 2 2 7101 1 2 lnductive Step Suppose fn 7 for some n 2 0 We must prove n 1 n 1 1 fltn1 gtltlt2 gt gt39 fn 1 fn n 1 recurrence relation W n 1 by the induction hypothesis n 1 E 1 2 n 1 2 W 2 3 RECURRENCE 118 1 Therefore7 by the rst principle of mathematical induction fn m for all n 2 0 D EXERCISE 343 Suppose fn n 2 0 is de ned recursively as follows 1 f 0 2 fn 1 fn 2n 1 for n 2 0 Prove that fn n2 for all n 2 0 35 De nition of f DEFINITION 351 Let f A a A be function Then we de ne f recursively as follows 1 Initial Condition f1 f 2 Recursion f 1 f o f for n 2 1 Discussion EXAMPLE 351 Prove that iff is injective then f is injective for n 2 1 PROOF Assume f is injective 1 Basis Step f1 f is injective by our assumption 2 Inductive Step Let n 2 1 and assume f is injective Prove fl is injective Recall that to prove fl is injective we must show Vab E Af 1a f 1b n a bl Assume ab E A and fn1a fwd fwd recurrence relation 0 f 115 f o f a f o f b recurrence relation ff a ff b by the de nition of composition f a f b since f is injective a b by the induction hypothesis7 f is injective Therefore7 by the rst principle of mathematical induction f is injective for all positive integers D 3 RECURRENCE 119 EXERCISE 351 Prove that iff is surjeetiue that f is surjeetiue 36 Example 361 EXAMPLE 361 Given a real number a 31 0 de ne a for all natural numbers n inductively by 1 Initial Condition a0 1 2 Recursion am ana THEOREM 361 VmVnama am where m7 n are natural numbers PROOF Proofthat Vin Vii aman am 7 where m7 n are natural numbers We accomplish this by assuming m is an arbitrary natural number and proving Vnama amm by induction on n 1 Basis Step n 0 Show ama0 am This follows directly from the initial condition of the de nition a0 17 there fore ama0 am1 am aer0 2 Induction Step lnduction hypothesis Let n be a natural number and assume ama an Prove aman am n l aman amana by the recursive part of the de nition an a a amma by the induction hypothesis am 1 am 1 by the recursive part of the de nition By induction7 Vnama amm Since in was an arbitrary natural number the statement is true for all natural numbers in Discussion Here we see a recursive de nition for the function fn aquot7 where n is a natural number and a is an arbitrary nonzero real number followed by a proof of one of the laws of exponents7 am ama This proof uses both mathematical induction and Universal Generalization We x in as some arbitrary natural number and then proceed to use induction on n We do not need to use induction on both in and it simultaneously When there are two different variables7 this is a standard strategy to try There are circumstances7 however7 when this strategy doesnt work so that you 3 RECURRENCE 120 would need to use induction on both of the variables double induction We will not encounter these kinds of problems in this course7 however 3 7 Fibonacci Sequence DEFINITION 371 The Fibonacci sequence may be de ned recursively as follows 1 Initial Conditions F0 0F1 1 2 Recursion Fn 1 Fn 7 1 for n 2 1 Discussion The famous Fibonacci sequence is de ned here using a recursively de ned function The de nition of the Fibonacci sequence requires two initial conditions There are no limits on the number of initial conditions on a recursively de ned object 7 only that there be a xed nite number in each instance EXAMPLE 371 Suppose Fn n 2 0 denotes the Fibonacci sequence Prove F n 1 that1lt lt2foralln23 F n PROOF Let Rn for n 2 1 We will prove by induction that 1 lt Rn lt 2 for all n 2 3 3 1 Basis Step n 3 R3 7 E and 1 lt 3 lt 2 3 RECURRENCE 121 2 Induction Step Suppose 1 lt Rn lt 2 for some n 2 3 We need to prove 1 lt Rn 1 lt 2 Fn 2 Pt 1 1 Fn1 W by the recursive de nition of Fn 1 1 or Rn1 1 By the inductive hypothesis 1 lt Rn lt 2 and so 1gt 1 gt1 Rn 239 Thus 1 3 2gt1 agtagt1 1201 2 7 01 1 1lt1 7lt2 Rltngt Substituting from above we have 1 lt Rn 1 lt 2 F 1 By the rst principle of mathematical induction 1 lt lt 2 for all n 2 3 n D F 1 1 5 EXAMPLE 372 calculus required Prove that lim if the limit artists Fn 1 FM 1 in Example 371 we see that Rn 1 1 7 Assume lim PM W lim Notice that lim Rn lim Rn 1 n taco taco taco l as in Example 371 Then from the induction step Fn 1 PROOF Let Rn exists and let L lim taco 1 Therefore L 1 3 RECURRENCE 122 Since L is a real number7 the equation 1 L 1 i L is equivalent to L2 i L i 1 By the quadratic formula L 71 i 2 Since L gt 0 and since xB gt17 1 5 L 7 D EXERCISE 371 Prove that gt 37 1 for n gt 6 Hintx Show that the statement is true for n 6 and 7 basis step and then show the induction step works for n 2 7 Here is another Fibonacci like sequence EXAMPLE 373 Suppose Fn n 2 0 is de ned recursively as follows 1 F0 1 and F1 2 2 Fn 1 2Fn 71forn 21 Prove that 2 for all n 2 0 PROOF Using the second principle of mathematical induction 1 Basis Step n 0 and n 1 F0 1 20 and F1 2 21 2 Induction Step Let n 2 1 Suppose 2k for 0 S h S n Then Fn1 Fn2Fn71 2 22 1 2 2 22n 2n1 Thus7 by the second principle of mathematical induction7 2 for all n 2 0 D 3 RECURRENCE 123 REMARKS 371 I Here and in the previous eccercise we see the slight vari ation in the basis step from the ones encountered in Module 33 Induction there may be more than one initial condition to verify before proceeding to the induction step 2 Notice that in this eccample as well as in some of the other emamples and edercises we have been asked to prove that a function de ned recursively is also given by a relatively simple formula The problem of solving recurrence relations for these nice formulas so called closed form is an interesting subject in its own right but it will not be discussed in this course EXERCISE 372 Let f N a Z be the function de ned recursively by N f0 1 and f1 74 3f71 14fn 7 2 forn 2 2 IS Prove fn 74 EXERCISE 373 Let f N a Z be the function de ned recursively by 2 7 2 fn fn71 2fn 7 2 forn 2 2 Prove fn 32 771 38 Strings DEFINITION 381 Given a nite set of symbols 2 the set of strings denoted 2 over 2 is de ned recursively as follows 1 Initial Condition The empty string A is in 2 2 Recursion Ifw is a string in 2 and a is a symbol in 2 then wa is in 2 Discussion The set E is usually called an alphabet and strings in 2 are called words in the alphabet 2 Strings words on a nite alphabet E are de ned recursively using right concatenation In other words every string of symbols from E can be built from a smaller string by applying new letters to the right REMARK 381 When a is a symbol from an alphabet we use the notation a where n E N to represent a concatenated with itselfn times In particular a0 is understood to represent the empty string A 3 RECURRENCE 124 EXERCISE 381 Suppose the alphabet E is the set abcd Then 2 is the set of all words on Z Use right concatenation to build the bit string daabc starting with the empty string A use Aa a for any element a in E EXERCISE 382 Now take the same bit string daabc and build it using left con catenation Notice that your steps are not the same that is concatenation is not commutatiue Regardless we arrive at the same set of strings 2 39 Bit Strings EXAMPLE 391 The set S of all bit strings with no more than a single 1 can be de ned recursiuely as follows 1 Initial Condition A1 E S 2 Recursion Ifw is a string in S then so are 0w and w0 Discussion In this de nition we must start with two objects in the set Then we can build all the bit strings that have at most one 1 We can de ne various subsets of bit strings using recursively de ned sets EXAMPLE 392 This eccample is an eactension of eccample 391 Let the set S be de ned recursiuely by Basis A1 E S Recursion Ifw E S then 0w 6 S and w0 E S In creating a set recursiuely it can help to use a tree diagram to develop more of an intuitive understanding of how this set is built The following diagram shows how the applying the above de nition 4 times gives the elements in the diagram Some key ideas to keep in mind is that all strings in the tree and all strings that would be in the tree if you kept going are in the set When a string is repeated that means there is more than one way to get that element but there is no need to see what is produced from it more than one time 3 RECURRENCE 125 Initial Condition Apply recursive step Prove S is the set of all bit strings with no more than one 1 PROOF Let A denote the set of all bit strings with no more than one 1 in the string Then we need to show A S First we will show A Q S Let a E A Then a is a bit string with either no 17s or it is a bit string with exactly one 1 Case 1 Suppose a has no 17s Then a 0 where n is some natural number We can build 1 using the recursive de nition by starting with A and applying the recursive step n times If we apply the recursive step 0 tirnes7 we get A Case 2 Suppose a has exactly on 1 Then a 0 10m for some ii7 m E N We can build a by starting with 17 which is given by the initial condition7 and applying the recursive step it E S a 0w 6 S ntirnes and applying it E S a wO E S in times This shows we can apply the recursive de nition given for S nitely many times to obtain any element of A Therefore A Q S Now we show S Q A by general induction 3 RECURRENCE 126 basis The elements given by the basis initial condition of the de ntion of S are both in A since A has no is and 1 has one 1 induction step Let x E S and assume z E A We need to show any elements obtained by appling the recursive step one time will also be in A Notice we obtain 0x and x0 when we apply the recursive step one time to x Since z is in A we know the string x has either no ones or a single one 0x and 0 do not add any more is to the bit string7 so they are also in A Thus by the principle of mathematical induction Vd E Sz E A This completes the proof that S A D EXAMPLE 393 Here s an example of proving a recursively de ned set of bit strings is the same as set of bit strings de ned in a non recursive manner Let A be the set of all bit strings of the form Uni where n can be any natural num ber Note that this is the same as A Onlnln E N A7 017 00117 0001117 000011117 and is slightly di erent from the set described in ELECTClSC 393 Now de ne B by the following recursive de nition Basis A E B Recursive Step Ifw E B then Owl E B Prove that A B PROOF First we prove A Q B Let a E A Then a FLO for some n E N If we use the recursive de nition of B we see A 0010 by the basis step and if we apply the recursive step n times to A we will build to the element Uni This demonstrates that we can apply the recursive de nition to nd 1 using a nite number of steps Thus a E B Now we need to prove B Q A We will do this using generalized induction7 which gives us a formal proof of this statement Basis Notice the element7 A7 created by the initial step or basis step in the de nition of B is also an element of A A 0010 Induction Step Let x E B be such that z E A as well Show that any element of B obtained from x by applying the recursive step one time is also an element of A If we apply the recursive step to w one time the only element we get Owl Since z is an element of A we know z Uni for some n E N So then 0x1 00 1 1 0n1ln1 which we see is also an element of A 3 RECURRENCE 127 Thus by the principle of generalized induction Va 6 Bz E A This completes that proof that A B D EXERCISE 391 What kinds of bit strings would we have if the initial condition in Example 391 is changed to 1 E S only So the de nition would be 1 Initial Condition 1 E S 2 Recursion Ifw is a string in S then so are 0w and w0 EXERCISE 392 What kinds of strings do we get from the following recursive de nition 1 Initial Conditions A1 E S 2 Recursion Ifw is a string in S then so is 0w EXERCISE 393 Find a recursive de nitionfor the set of bit strings T 0719M s E N EXERCISE 394 Prove your answer for ELECTClSC 393 is correct EXERCISE 395 Find a recursive de nition for the set of all bit strings containing no adjacent 1 s For edarnple 1001010 is allowed but 0011010 is not 4 GROWTH OF FUNCTIONS 128 4 Growth of Functions 41 Growth of Functions Given functions f and 9 we wish to show how to quantify the statement 9 grows as fast as f The growth of functions is directly related to the complexity of algorithms We are guided by the following principles 0 We only care about the behavior for large77 problems 0 We may ignore implementation details such as loop counter incrementation Discussion When studying the complexity of an algorithm we are concerned with the growth in the number of operations required by the algorithm as the size of the problem increases In order to get a handle on its complexity we rst look for a function that gives the number of operations in terms of the size of the problem usually measured by a positive integer n to which the algorithm is applied We then try to compare values of this function for large n to the values of some known function such as a power function exponential function or logarithm function Thus the growth of functions refers to the relative size of the values of two functions for large values of the independent variable This is one of the main areas in this course in which experience with the concept of a limit from calculus will be of great help Before we begin one comment concerning notation for logarithm functions is in order Most algebra and calculus texts use logz to denote loglOz or perhaps loge x but in computer science base 2 is used more prevalently So we shall use logz to denote logzz As we shall see in the context of this module it actually doesn7t 1 matter wh1ch base you use s1nce loga z log for any acceptable bases a and b ogba 10gb m 10gb a EXERCISE 411 Prove that logaz for arbitrary positive real numbers a and b di erent from 1 42 The BigO Notation DEFINITION 421 Let f and g be functions from the natural numbers to the real numbers Then 9 asymptotically dominates f or f is bigO ofg if there are positive constants C and k such that lf96l S OWN for x 2 k 4 GROWTH OF FUNCTIONS 129 If f is big O of 9 then we write NC is 0996 f E 09 THEOREM 421 If lim l f m L where L 2 0 then f 6 09 4100 9 z f96 1 1996 VV THEOREM 422 If lim 00 then f is not 09 f Z 09 Discussion The most basic concept concerning the growth of functions is big 0 The statement that f is big O of g expresses the fact that for large enough L f will be bounded above by some constant multiple of 9 Theorem 421 gives a necessary condition for f to be big O of g in terms of limits The two notions aren7t equivalent since there are examples where the de nition holds7 but the limit fails to exist For the functions we will be dealing with7 however7 this will not happen When working the problems in the module you may nd it helpful to use a graph ing calculator or other graphing tool to graph the functions involved For example7 if you graph the functions x2 10 and 3 then you will see that 2 10 3 3x2 when x 2 3 Actually7 when x 2 This seems to imply that f x2 10 is big O of g 2 This is NOT a proof7 but it can give you some ideas as to what to look for In particular7 you wouldnt try to show that f S 39z for z 2 2 It isn7t necessary that you nd the best bound7 k for L however7 as long as you nd one that works Also7 there is nothing unique about the choice of 0 EXAMPLE 421 Show that 2 10 is 0x2 Proof 1 using De nition of BigO Let C 3 and k 3 Then7 if z 2 37 3x2z22z22x22322210 D Proof 2 using De nition of BigO Let C 2 and k 4 Then7 if z 2 47 2x2x2z222422210 D 2 10 10 Proof 3 using Theorem 421 lim z 2 lim 1 7 1 0 1 14100 mace So7 by Theorem 17 2 10 E 0z2 D 4 GROWTH OF FUNCTIONS 130 EXERCISE 421 Let ab E RJV 7 Prove logaz is Ologbx Hint recall emerez39se 41 43 Proofs of Theorems 421 and 422 Proof of Theorem 421 Suppose lim L where L is a nonnegative 4100 9 z lf96 19901 wish by choosing z large enough In particular we can ensure that as close to L as we lf96l real number Then by the de nition of limit we can make is within a distance 1 of L by choosing z 2 k for some positive number k That is there is a number k 2 0 such that if z 2 k then In particular WM S L1lg9 l So we can choose 0 L 1 Thus f 6 09 D lf96l p p p p 19001 positive number 0 there is a positive number N such that lfxl gt C 19001 if z 2 N Thus for all positive numbers 0 and k there is an x 2 k take z greater than the larger of k and N such that Proof of Theorem 422 Suppose lim 00 This means that for every 01 Thus f Z 09 D 4 GROWTH OF FUNCTIONS 131 Discussion How do you interpret the statement f Z 09 That is7 how do you negate the de nition Let7s apply principles of logic from Module 23 The de nition says f 6 09 if and only if there exist constants C and k such that7 for all x if z 2 k then S The negation would then read f Z 09 if and only if for all constants C and k there exist x such that z 2 k and gt EXAMPLE 431 Show that 2 is not Proof 1 using the De nition of bigO As we have just seen7 the de nition requires us to show that no matter how we choose positive constants C and k there will be a number x 2 k such that x2 gt Cm So7 suppose C and k are arbitrary positive constants Choose z so that z 2 k and z gt G Then 2 z z gt C z We dont have to use the absolute value symbol7 since z gt 0 D 2 Proof2 using Theorem 422 lim 1 lim z oo So7 by Theorem mace 00 4227 2 Z D While it is true that most of the functions f and 9 that measure complexity have domain N they are often de ned on the set of all positive real numbers7 and7 as we see7 this is where the calculus can come in handy 44 Example 441 EXAMPLE 441 Show that 2x3 2 7 3x 2 is 0x3 Proof 1 using the De nition of bigO By the triangle inequality7 l2x3 x2 7 3x 2 S l2x3l 1le l3l 2 2lz3l le 3ll 2 Now7 if z 2 27 then 2 3 3 x 3 3 and 2 3 3 Thus Will l czl l3l 2 S 2W l cgl 3l3l l cgl 7W 4 GROWTH OF FUNCTIONS 132 Using these inequalities C 7 and h 2 we see that f is 0x3 D Proof 2 using Theorem 422 2x3 x2 7 3x 2 122 is hm 21w71gt223 By Theorem 421 2x3 2 7 3x 2 is 0z3 Discussion In the rst proof in Example 441 we used the triangle inequality which is proved in the Appendix at the end of this module We also need to use the fact labl lal Notice the strategy employed here We did not try to decide what 0 and h were until after using the triangle inequality The rst constant we dealt with was h After separating the function into the sum of absolute values we thought about what part of this function would be the biggest for large values of z and then thought about how large z needed to be in order for all the terms to be bounded by that largest term This led to the choice of k In general the constant 0 depends on the choice of h and the two functions you are working with EXERCISE 441 Use the de nition to show that 5x3 7 3x2 2x 7 8 E 0x3 EXERCISE 442 Use Theorem 421 to show that 103 7 7x2 5 E 0z3 EXERCISE 443 Use Theorem 422 to show that x5 Z 0100x4 45 Calculus De nition DEFINITION 451 ff andg are such that 1rn Ln 0 Hoe 971 then we say f is littleo of 9 written f E 09 As a corollary to Theorem 421 we have THEOREM 451 ff is 09 then f is 09 4 GROWTH OF FUNCTIONS 133 Discussion As Theorem 451 indicates7 the little 0 relation is stronger than big O Two of the most important examples of this relation are 1 logaz E 0a7 where a is a positive number different from 17 and 2 x E 0aw ifa gt1 These are most easily seen using a version of l7Hopital7s rule from calculus 17H6pital7s Rule lf lim f lim 9a 007 and if f 96 gz 7 L7 then f x if m L39 f and 9 denote the derivatives of f and g respectively EXAMPLE 451 Show that logaz E 0z where a is a positive number di ereht from Z d PROOF First observe that lim logaz lim z oo Recall that dalogax zaco zaco z 1 a where lnx loge x By l7Hopital7s rule7 zlna 1 hm 0g hm I 0 EH00 EH00 D EXERCISE 451 Show that loga z2 E 0a EXAMPLE 452 Show that ifa gt1 then x E 0aw PROOF First observe that lim z lim am 00 By l7Hopital7s rule7 1 hm 3 hm 70 zaco am mace am ln a since a gt 1 D EXERCISE 452 Show that ifa gt 1 then x2 E 0aw 4 GROWTH OF FUNCTIONS 134 EXERCISE 453 Use mathematical induction to show that ifa gt 1 then x E 0am for every positive integer n 46 Basic Properties of Big0 The following theorems and facts will be helpful in determining big 0 THEOREM 461 A polynomial of degree n is Fact Theorem 461 can be extended to functions with non integral exponents like THEOREM 462 ffL is 091 and f2 is 092 then f1f2 is 0maxl91l COROLLARY 4621 If f1 and f2 are both 09 then f1 f2 is 09 THEOREM 463 If fl is 091 and f2 is 092 then flfg is 09192 THEOREM 464 ffL is 0f2 and f2 is 0f3 then fl is 0f3 THEOREM 465 ff is 09 then af is 09 for any constant a Discussion Use these theorems when working the homework problems for this module EXAMPLE 461 Find the least inte9ern such that x45 log 1 is 0x Solution First we consider mil If you think back to calculus and consider which part of this function quottakes over when x 9ets large that provides the clue that this function should be To see this we take the following limit hm ltz4gtltz31gt m e 1 szz31 mace Since that limit is Z we have veri ed 4 show that m is not 0x0 01 m31 4 3 hm w hm L woo 1 woo 1 1953 is Theorem 422 can be used to 4 m31 Slogm Slogm m3 Since logx is 0x m3 is 0 as above 5 is 0z hence 51 Now consider is and by taking a limit Since the original function is the sum of the two functions each of which is 0x the sum d4 5 log 1 is 0x by Corollary 462 4 GROWTH OF FUNCTIONS 135 47 Proof of Theorem 463 PROOF OF THEOREM 463 Suppose f17f27g1g2 are all functions with domain and codomain R such that fl is 0g1 and f2 is 0g2 Then by de nition of big O7 there are positive constants 017h1702k2 such that V95 2 k1llfllt gtl S 01l9195ll and V95 2 kzllf295l S 02l92ll Let h maph1h2 and C 0102 Then if z 2 h we have lf1f295l lf195l 39 lf295l S 01l9195 39 02l9295l 0102l919295l Cllt919296l This shows f1f2 is 0g1g2 D 48 Example 481 EXAMPLE 481 Suppose there are two computer algorithms such that 0 Algorithm 1 has complepity n2 7 71 1 arid 0 Algorithm 2 has complepity 7122 3n 2 Theri both are 00 but to indicate Algorithm 2 has a smaller leadirig eoe eieht arid heriee would be faster we write 0 Algorithm 1 has complepity n2 0a arid 0 Algorithm 2 has complepity 7122 Discussion Example 481 illustrates the way in which the big O notation may be used to discuss complexity of algorithms 4 GROWTH OF FUNCTIONS 136 49 BigOmega DEFINITION 491 f is bigOmega of 9 written f 6 99 if there are positive constants C and k such that WW 2 019W forx gt k Big Omega is very similar to big O Big Q notation is used to indicate a lower bound on functions for large values of the independent variable Notice that f is 99 if and only if g is 0f Using this fact we see the properties for big O give similar properties for big Q EXAMPLE 491 95 is 9log z EXAMPLE 492 2953 2 7 3x 2 is 9953 PROOF USING THE DEFINITION OF BIG Q Let x 2 3 Then 2 7 3x 2 0 and so 2 7 3x 2 2 0 as well Thus l2z3x2732l 2z3x273z2 2 23 By choosing C 2 and h 3 in the de nition of big Q the above work shows 23x2 732 is D EXERCISE 491 Let ab 6 RT 7 Prove logaz is 9logb 410 BigTheta DEFINITION 4101 f is bigTheta ofg written f 6 99 iff is both 09 and 99 Discussion The de nition given for big 9 is equivalent to the following THEOREM 4101 f is g if and only iff is 09 and g is 0f EXERCISE 4101 Prove Theorem 410 4 GROWTH OF FUNCTIONS 137 EXAMPLE 4101 2x2 7 33z4 3 7 2x2 71 is x z 2x2 7 33z4 953 7 2x2 71 7 2x2 7 3 962 4 73x4372z271 2x4 7 3x2 3x4372z271 i 273x2 31z72z2 71954 lim 7 1700 x 3 2x2 7 33z4 3 7 2x2 71 2 72 7 You now will show through the following exercise that any two logarithm functions have the same growth rate hence7 it doesnt matter what acceptable base is used EXERCISE 4102 fa and b are positive real numbers dz erent from 1 show that loga z E logb 411 Summary Suppose f and 9 are functions such that lim f L7 700 9 where 0 S L 3 oo 1 If L 07 then f is 09 hence7 097 and 9 is 9f hence7 not Of D 2 If L 007 then f is 99 hence7 not 097 and 9 is 0f hence7 Of 3 If 0 lt L lt 007 then f is 99 hence7 097 and 9 is f hence7 Of 4 GROWTH OF FUNCTIONS 138 412 Appendix Proof of the Triangle Inequality Recall the triangle in equality for all real numbers a and b7 1051 S 101 W PROOF Recall from Module 12 that the absolute value function f is de ned by L if207 we m 7x ifs lt 0 We rst observe that for any real numbers z and y if y 2 07 then S y if and only if 7y S x S y To see this7 look at two cases Case 1 z 2 0 Then x and so 3 y if and only if 7y S 0 S x S y or 7y S x S 1 Case 2 z lt 0 Then 7x and so S y if and only if 7y S 0 S is S y Multiplying through by 71 and reversing the inequalities we get y 2 z 2 7y or 7y S x S y We now prove the triangle inequality For arbitrary real numbers a and b7 apply the above to z a and y al and then to z b and y b to get inequalities 101 S a S 101 7w b M Then W b Sab ab or 101 151 S 05 S 101 151 Now apply the assertion above to z a b and y a b to get la bl S al CHAPTER 5 Number Theory 1 Integers and Division 11 Divisibility DEFINITION 111 Given two integers a and b with a 31 0 we say a divides b if there is an integer e such that b ac fa divides b we write alb fa does not divide b we write aXb Discussion EXAMPLE 111 The number 6 is divisible by 3 3 6 since 6 3 2 EXERCISE 111 Let a b and e be integers with a 31 0 Prove that ifablae then ble Using this de nition7 we may de ne an integer to be even if it is divisible by 2 and add if it is not divisible by 2 This concept is one of the simplest of properties of numbers to de ne7 yet it is among the most complicated of all mathematical ideas Keep in mind that we are talking about a very restricted notion of what it means for one number to divide77 another we can certainly divide 7 by 3 and get the rational number 23333 but7 since the result is not an integer7 we say that 3 does not divide 77 or 3X7 For this reason7 you should avoid using fractions in any discussion of integers and integer arithmetic 12 Basic Properties of Divisibility THEOREM 121 For all integers a b and e Z Ifalb and ale then alb e 2 Ifalb then albe 3 Ifalb and ble then ale Discussion 139 1 INTEGERS AND DIVISION 140 Theorem 121 states the most basic properties of division Here is the proof of part 3 Proof of part 3 Assume a b and c are integers such that IV and MC Then by de nition there must be integers in and n such that b am and c bn Thus 0 bn amn amn Since the product of two integers is again an integer we have 1 0 D EXERCISE 121 Prove part 1 of Theorem 12 EXERCISE 122 Prove part 2 of Theorem 12 13 Theorem 131 The Division Algorithm THEOREM 131 Division Algorithm Given iritegers a arid d with d gt 0 there eists unique iritegers q arid r with 0 S r lt d such that a qd r NOTATION 131 We call a the dividend d the divisor q the quotient arid r the remainder Discussion The division algorithm is probably one of the rst concepts you learned relative to the operation of division It is not actually an algorithm but this is this theorem7s traditional name For example if we divide 26 by 3 then we get a quotient of 8 and remainder or 2 This can be expressed 26 38 2 It is a little trickier to see what q and r should be if a lt 0 For example if we divide 726 is by 3 then the remainder is riot 72 We can however use the equation 26 3 8 2 to our advantage 726378i2378737233791 So dividing 726 by 3 gives a quotient of 79 and remainder 1 The condition 0 S r lt d makes r and q unique for any given a and d 14 Proof of Division Algorithm Proof Suppose a and d are integers and d gt 0 We will use the well ordering principle to obtain the quotient q and remainder r Since we can take q a if d 1 we shall assume that d gt 1 Let S be the set of all natural numbers of the form a7 hd where h is an integer In symbols Sa7kdk Zandaikd20 If we can show that S is nonempty then the well ordering principle will give us a least element of S and this will be the remainder r we are looking for There are two cases 1 INTEGERS AND DIVISION 141 Case 1 a 2 0 ln this case we can set Is 0 and get the element a 7 0 h a 2 0 of S Case 2 a lt 0 ln this case we can set Is a Then a 7 kd a 7 ad a17 d Since a lt 0 and d gt 1 a17 d gt 0 hence is an element of S Thus S 31 0 and so S has a least element r a 7 qd for some integer q Thus a qd r and r 2 0 We are left to show r lt d and ii q and r are unique i Suppose r 2 d Then r dr where 0 S r lt r Then a qdr qddr q1dr so that r a 7 q 1d is an element of S smaller than r This contradicts the fact that r is the least element of S Thus r lt d ii Suppose integers q and r satsify a q d r and 0 S r lt d Without loss of generality we may assume r 2 r so that 0 S r 7 r lt d Since a q d r qd r r 7r dq 7g This means that d divides r 7 r which implies either r 7 r 2 d or r 7 r 0 But but we know 0 S r 7 r lt d Thus r r which in turn implies q q That is q and r are unique 15 Prime Numbers Composites DEFINITION 151 pr is an integer greater than 1 then p is a prime number if the only divisors ofp are 1 and p DEFINITION 152 A positive integer greater than 1 that is not a prime number is called composite Discussion Prime numbers are the building blocks of arithmetic At the moment there are no ef cient methods algorithms known that will determine whether a given integer is prime or nd its prime factors This fact is the basis behind many of the cryp tosystems currently in use One problem is that there is no known procedure that will generate prime numbers even recursively ln fact there are many things about prime numbers that we dont know For example there is a conjecture known as Goldbach7s Conjecture that there are in nitely many prime pairs that is consecu tive odd prime numbers such as 5 and 7 or 41 and 43 which no one so far has been able to prove or disprove As the next theorem illustrates it is possible however to prove that there are in nitely many prime numbers lts proof attributed to Euclid is one of the most elegant in all of mathematics THEOREM 151 There are in nitely many prime numbers 1 INTEGERS AND DIVISION 142 PROOF We prove the theorem by contradiction Suppose there are only nitely many prime numbers say 101102 pn Let Ni 01102quot3910n1 Then N is an integer greater than each of 101102 pn so N cannot be prime ln Example 9 Module 33 we showed that N can be written as a product of prime numbers hence some prime p divides N We may assume by reordering 101102 pn if necessary that p p1 Thus N pla for some integer a Substituting we get p10 p1p2pn1 plaip1p2pn 1 p1ap2pn 1 Thus a 7102 10 is a positive integer Since p1 is a prime number p1 gt 1 and so p1ap2pn gt1 But this contradicts the equality above D 16 Fundamental Theorem of Arithmetic THEOREM 161 Fundamental Theorem of Arithmetic Every positive integer greater than one can be written uniquely as a product of primes where the prime factors are written in nondecreasinq order Discussion We have already given part of the proof Theorem 161 in an example of Module 33 Induction There we showed that every positive integer greater than 1 can be written as a product of prime numbers The uniqueness of the factors is important and the proof that they are unique which requires a few additional ideas will be postponed until the next module The prime factorization of 140 is 2 2 5 7 You can see one reason why we do not want 1 to be prime There is no limit to the number of times 1 may be repeated as a factor and that would give us non unique prime factorizations 17 Factoring THEOREM 171 Ifn is a composite integer then n has afactor less that or equal to 1 INTEGERS AND DIVISION 143 Discussion Theorem 171 can be helpful in narrowing down the list of possible prime factors of a number lt was proved in an example of Module 32 Methods of Proof and exploited in another example of that module lf the number 253 is composite for example it must have a factor less than or equal to 15 Thus we need only check the primes 2 3 5 7 11 and 13 lt turns out 253 11 23 18 Mersenne Primes DEFINITION 181 A prime number of the form 21771 wherep is a prime number is called a Mersenne prime Discussion Mersenne primes are a special class of primes which lend themselves to a nice theoretical development Not all primes are Mersenne though and not all numbers of the form 2 7 1 are prime For example 2 71 is prime for p 2 3 5 and 7 but 211 71 2047 23 89 which is not prime On the other hand the primes 5 and 11 cannot be written in this form 19 Greatest Common Divisor and Least Common Multiple DEFINITIONS 191 Given integers a and b I The greatest common divisor ofa and b denoted GCD ab is the largest positive integer d such that dla and dlb 2 The least common multiple ofa and b denoted LCM a b is the smallest positive integer in such that alm and blm 3 a and b are called relatively prime if GCD ab 1 4 The integers a1 a2 a3 an are called pairwise relatively prime ifGCDaaj 1for1 iltj n 5 The Euler b function is the function b Z4r a N de ned by n the number of positive integers less than n that are relatively prime to n LEMMA 191 Suppose a and b are integers and m LCMab Ifc is a positive integer such that ale and blc then mlc PROOF Suppose ale and blc but mXc By the division algorithm there are unique positive integers q and r such that c mg r and 0 S r lt m Since mXc r 31 0 that is r gt 0 Write r c 7 mg Since a and b both divide c and m a and b both divide r But this contradicts the fact that m is supposed to be the least positive integer with this property Thus mlc D 1 INTEGERS AND DIVISION 144 THEOREM 191 ab GCDab LCMab Discussion The proof of Theorem 191 will be discussed in the next module EXAMPLE 191 Here are some epamples to illustrate the de nitions above I GCD4560 15 since 45 153 and 60 15 4 and Z5 is the largest number that divides both 45 and 60 2 LCM457 60 180 since 180 454 603 and 180 is the smallest number that both 45 and 60 divide 3 45 and 60 are not relatively prime 4 45 and 16 are relatively prime since GCD4516 1 5 4 7 13 and 55 are pairwise relatively prime 6 lt15gt 7 8 lf we are given the prime factorizations of two integers7 then it is easy to nd their GOD and LCM For example7 600 23 3 52 and 220 22 5 11 has greatest common divisor 22 5 20 and least common multiple 23 3 52 11 6600 Since prime factorizations can be dif cult to nd7 however7 this idea does not lead to an ef cient way to compute GCD7s We will introduce an ef cient algorithm in the next module that does not involve knowledge about prime factorizations EXERCISE 191 Let denote the n th term of the Fibonacci Sequence Prove using induction that GCDFn7 Fn 7 1 1 for all integers n 2 2 110 Modular Arithmetic DEFINITION 1101 Given integers a and m with m gt 0 a mod m is de ned to be the remainder when a is divided by m DEFINITION 1102 a E bmod in read quota is congruent to b modulo or mod mn Zf mla 7 b that is a 7 b mod m 0 THEOREM 1101 Given integers a b and m 1 a E b mod m if and only ifa mod m b mod m 2 a E b mod m if and only ifa b km for some integer k 3 fa E b mod m and c E d mod m then a ac2bdmodm b aCEbdmodm 1 INTEGERS AND DIVISION 145 Discussion The mod operation is derived from the Division Algorithm If we divide the integer a by the positive integer in we get a unique quotient q and remainder r satisfying a mg r and 0 S r lt m The remainder r is de ned to be the value of a mod in One of the notational aspects that may seem a little unusual is that we write a bmod m for a b mod Also the symbol mod in may occasionally be omitted when it is understood EXAMPLE 1101 Here are some examples a 12 mod 5 2 b 139 mod 5 4 c 1142 mod 5 2 d 1142 E 1222mod 5 e1142139224E621mod5 1711424392242 23mod5 One ofthe differences to note between the concept of congruence modulo m verses the mod operator is that an integer k may be congruent to in nitely many other integers modulo in however k mod m is equal to one single integer For example 139 mod 5 4 but 139 is congruent to all the elements of 76 714 9 14 19 EXERCISE 1101 Given a positive integer in prove that the assignment a gt gt a mod m de nes a function f Z a Z Is f one to one onto What is its range a gt gt a mod m is another way to write fa a mod in Here is a proof of part 3b of Theorem 1101 Proof of 3b Since a E bmod m and c E dmod in there must be integers s and t such that b a 5m and d c tm part 2 Thus bd a smc tm ac atm smc stm2 ac at 5c stmm Since a c t and s are all integers at 5c st is as well Thus by part 2 ac E bdmod EXERCISE 1102 Prove part 3a of Theorem 1101 1 INTEGERS AND DIVISION 146 111 Applications of Modular Arithmetic 1 Hashing Functions 2 Pseudorandom Number Generators 3 Cryptology Discussion There are many applications of modular arithmetic in computer science One such application is in the construction of pseudorandom number generators Numbers that seem to be somewhat random may be produced using the linear congruential method As you will see it does not produce truly random numbers but rather a sequence of numbers that will eventually repeat To generate a sequence we choose a modulus in multiplier a and an increment c Then we start with a seed number 0 and then construct a sequence of numbers recursively using the formula xn azn c mod in EXAMPLE 1111 Suppose we choose in 11 a 7 c 3 and x0 1 Then we get 713mod 1110 7103mod117 773mod 118 743mod 119 z47108mod114 793mod 110 703mod 113 The sequence will be 1 10 7 8 4 9 U 3 etc If we wanted a random sequence of bits 0 and Z we could then reduce each xn mod 2 In practice large Mersenne primes are often chosen for the modulus and the repetition period for such sequences can be made to be quite large 1 INTEGERS AND DIVISION 147 EXERCISE 1111 Prove that for a given modulus in and arbitrary multiplier a increment e and seed 0 the sequence 0317 2 must eventually repeat 2 INTEGERS AND ALGORITHMS 148 2 Integers and Algorithms 21 Euclidean Algorithm Euclidean Algorithm Suppose a and b are in tegers with a 2 b gt 0 1 Apply the division algorithm a bq r 0 S r lt b 2 Rename b as a and r as b and repeat until 7 0 The last nonzero remainder is the greatest common divisor of a and b The Euclidean Algorithm depends upon the following lemma LEMMA 211 fa bq r then GCDab GCDbr PROOF We will show that if a bq r then an integer d is a common divisor of a and b if and only if d is a common divisor of b and 7 Let d be a common divisor of a and b Then dla and dlb Thus da 7 bq which means dlr since 7 a 7 bq Thus d is a common divisor of b and 7 Now suppose d is a common divisor of b and 7 Then dlb and dlr Thus dbqr so dla Therefore d must be a common divisor of a and b Thus the set of common divisors of a and b are the same as the set of common divisors of b and 7 It follows that d is the greatest common divisor of a and b if and only if d is the greatest common divisor of b and 7 D Discussion The fact that the Euclidean algorithm actually gives the greatest common divi sor of two integers follows from the division algorithm and the equality in Lemma 211 Applying the division algorithm repeatedly as indicated yields a sequence of remainders 71 gt r2 gt gt Tn gt 0 n1 where 71 lt b Lemma 211 says that GCDab GCDbr1 GCDltT1T2 GCDrn1rn But since n1 0 Tn divides 1 so that GCDTL1 Tn 7quot Thus the last nonzero remainder is the greatest common divisor of a and b EXAMPLE 211 Fmd GCD 1317 56 2 INTEGERS AND ALGORITHMS 149 1317 5623 29 56 291 27 29 271 2 27 2131 2 120 GCD 1317561 Example 211 shows how to apply the Euclidean algorithm Notice that when you proceed from one step to the next you make the new dividend the old divisor replace a with b and the new divisor becomes the old remainder replace b with r Recall that you can nd the quotient q by dividing b into a on your calculator and rounding down to the nearest integer That is q labj You can then solve for r Alternatively if your calculator has a mod operation then r modab and q a 7 rb Since you only need to know the remainders to nd the greatest common divisor you can proceed to nd them recursively as follows Basis r1 amod b r2 bmod r1 Recursion rk1 rk1 mod rk for h 2 2 Continue until 7311 0 for some n 22 GCD7s and Linear Combinations THEOREM 221 Ifd GCDab theri there are iritegers s aridt such that d as bt Moreover d is the smallest positive iriteger that earl be eapressed this way Discussion Theorem 221 gives one of the most useful characterizations of the greatest com mon divisor of two integers Given integers a and b the expression as bt where s and t are also integers is called a linear combination of a and b EXERCISE 221 Prove that if abst arid d are iritegers such that dla arid dlb theri dlas bt The Euclidean Algorithm can in fact be used to provide the representation of the greatest common divisor of a and b as a linear combination of a and b Here is how it would work for the example in Example 211 2 INTEGERS AND ALGORITHMS 150 EXAMPLE 221 Eccpress 1 GCD131756 as a linear combination of 1317 and 56 Solution We work backwards using the equations derived by applying the Euclidean algorithm in eccample 21 eccpressing each remainder as a linear combination of the associated diuisor and diuidend 1 7 13 2 linear combination of 2 and 27 1 7137 1 substitute27 1 1 14 713 linear combination of 27 and 29 1 1471713 substitute 71 1 14 7 27 linear combination of 29 and 56 1 14 727m723 substitute m723 1 635 7 21m linear combination of 56 and 1317 The dividends diuisors and remainders have been underlined So GCD131756 1 1317727 56635 Theorem 221 can be proved by mathematical induction following the idea in the preceding example Proof of Theorem 221 Suppose a and b are integers We may assume a and b are positive7 since GCDab GCDiaib The Euclidean algorithm uses the division algorithm to produce a sequence of quotients and remainders as follows a 5 11 T1 5 T1Q2 T2 T1 T2Q3 T3 Tn72 Tn71Qn i Tn Tn71 TTLQTL i l i 0 where rn is the last nonzero remainder We will use the second principle of mathe matical induction to prove that rk is a linear combination of a and b for 1 S k S n 1 Basis Step h 1 r1 a 7 bqL a1 b7q1 2 Induction Step Suppose rl is a linear combination of a and b for 1 S i S h For 1 S h S n we have Tk1 W71 Tka1 2 INTEGERS AND ALGORITHMS 151 where r0 b when k 1 By the inductive hypothesis rk1 and rk are linear combinations of a and b This works for h 1 since r0 b is trivially a linear combination of a and b Write rm a81 btl and rk asz bbg for integers 51t1 52 t2 and substitute into the equation above Tk1 051 btl 052 bt2Jk1 051 52Qk1gt bt1 tZQk1 Thus n1 is a linear combination of a and b By the second principle of math ematical induction rn is a linear combination of a and b But rn is the greatest common divisor of a and b This proves the rst part of the theorem Next we show that d is the smallest positive integer expressible as a linear combi nation of a and b Suppose a positive integer c can be expressed as a linear combination of a and b c ax by for integers z and y Since dla and dlb then dlc which implies d S c D Here is an alternative proof of Theorem 221 that does not use the Euclidean algorithm Second proof of Theorem 221 Let S be the set of all positive integers that can be expressed as a linear combination of the positive integers a and b Clearly S 31 0 since a b E S By the well ordering principle S has a least element d We will prove by contradiction that dla and dlb lf an then use the division algorithm to get integers q and r such that a dq r where 0 lt r lt d Since both a and d are linear combinations of a and b then r a 7 dq is also But this means that r E S contradicting the fact that d is the smallest member of S Similarly one shows that dlb If e is a divisor of a and b then c divides any linear combination of a and b hence cld Thus d GCDab D EXERCISE 222 Prove that ifp is a prime number and n is an integer that is not divisible by p then there are integers s andt such that p5 nt 1 First show that GCDpn 1 2 INTEGERS AND ALGORITHMS 152 EXERCISE 223 Prove that if is a linear combination ofa and b then GCDab 23 Uniqueness of Prime Factorization LEMMA 231 If GCDab 1 and albc then alc PROOF Write 1 as bt for integers s and t Multiply both sides by c c acs bct Since albc7 a divides this linear combination acs bct c of a and be D THEOREM 231 Suppose a and b are integers andp is a prime number prlab then either pla or plb PROOF We will prove the equivalent statement if plab and pla then plb You should convince yourself that the two propositional forms P a Q V R and P Q a R are equivalent Suppose plab and an Then GCDp7 a 1 By the Lemma 17 plb D Discussion Theorem 231 is very useful in deciding how prime factors are distributed in a product of two integers For example7 we gave an indirect proof in Module 32 that if the product of two integers z and y is even7 then either p is even or y is even As we hinted there7 a direct proof is possible7 and Theorem 231 provides just the right information to make it work EXERCISE 231 Use Theorem 231 to give a direct proof that if the product of two integers z and y is even then either z is even ory is even EXERCISE 232 Use mathematical induction to prove the following generalization of Theorem 23 Suppose a17a2an are integers andp is a prime number If plalaZuan then plai for somei 127n Hintx The induction step has two cases EXERCISE 233 Use Lemma 231 to prove that ifk Z andm are positive integers such that hlm llm and h and Z are relatively prime then the product hllm 2 INTEGERS AND ALGORITHMS 153 EXERCISE 234 Suppose a and b are positive integers d GCDab a dk and b di Prove that k and i are relatively prime Hintx Show that 1 can be edpressed as a linear combination of k and i We can now give a proof of Theorem 6 of Module 5 Integers and Division If a and b are positive integers then ab GCDa b LCMa b Proof of Theorem 6 Module 51 Let d GCDab Write a dk b di where k and i are positive integers which by Exercise 234 are relatively prime Then ab dkdi d kid GCDa b kid We will succeed once we show that kid LCMab We will prove this by contra diction Suppose m LCMab and m lt kid Observe that kid dki ai and kid dik bk That is both a and b divide kid hence their least common multiple in does also Since kia and ill k and i both divide in hence by Exercise 233 the product kiim Aside We also know that d divides in so it is tempting to assert that kid also divides in But we cant use Exercise 233 to conclude this since d may not be relatively prime to either k or i Can you give an example where d divides both k and i7 Thus in kiz for some positive integer x and z lt d by hypothesis Since mikid zid Write d zy where y is an integer gt 1 Now a dk xykim kix so yii b di xyiim kix so This implies that k and i are not relatively prime since y gt 1 Thus the assump tion in lt kid is false and so in kid This generalization of Theorem 231 can be used to prove the uniqueness of prime factorizations asserted in the Fundamental Theorem of Arithmetic Module 51 If n is a positive integer greater than 1 then it can be written uniquely as a product of prime numbers where the factors appear in nondecreasing order 2 INTEGERS AND ALGORITHMS 154 Proof of uniqueness of prime factorization We have already shown that we can write any integer n gt 1 as a product 7110110239 10k7 where each p is prime By reordering the factors if necessary we can always assume th at P1 P2Squot39Spk We will prove by induction on k that if an integer n gt 1 has a factorization into k primes k 2 1 then the factorization is unique 1 E0 Basis Step k 1 In this case n p1 is prime and so it has no other factorization into primes lnduction Step Assume that every integer that can be factored into k primes has a unique factorization Suppose 71 101102 39 39 39Pkpmh where each p is prime and 101 1023 Spk Smu Suppose n has another prime factorization 71 119 le where each q is prime possibly Z 31 k 1 and ASQZS39HSQI By the generalization of Theorem 231 in Exercise 232 since plln q1q2 ql then pllqj for some j But qj is also prime so 101 Qj 2 Q1 On the other hand since qllp1p2pkpk1 then qllpi for some 239 and since p is prime Q1 10139 Z 101 But if pl 2 Q1 and Q1 2 p1 then p1 ql Thus we can cancel the rst factor from both sides of the equation 10110239 10k10k1 1112 39 39 Ql to get 102 39 39 39Pkpk1 1239 39 91 The integer on the left hand side of this equation has a prime factorization using k primes By the induction hypothesis this factorization is unique This means thatZk1 and 102 127103 137 Thus p q for 1 S 239 S k 1 and the factorization of n is unique 7 10k1 Qk1 2 INTEGERS AND ALGORITHMS 155 By the rst principle of mathematical induction7 every integer greater than one has a unique prirne factorization 3 APPLICATIONS OF NUMBER THEORY 156 3 Applications of Number Theory 31 Representation of Integers THEOREM 311 Given an integer b gt 1 every positive integer n can be ecspresses uniquely as n akbk ak1bk 1L alb a07 where h 2 0 0 S a0a1a27 ak lt b and are all integers DEFINITION 311 Base b expansion of n is akak1a1a0b if the al are as described in Theorem 311 EXAMPLE 311 Here are epamples of common expansions other than the more familiar decimal eppansion o Binary expansion is the base 2 eppansion o Octal expansion is the base 8 eppansion o Hexadecimal expansion is base 16 eppansion The symbols A through F are used to represent 10 through 15 in the eppansion Discussion Theorem 311 asserts that each positive integer n can be expressed uniquely as a linear combination of powers of a xed integer b gt 1 The coef cients in the linear combination must be less than b and must be greater than or equal to zero These coef cients are7 by de nition7 the digits of the base b expansion of n7 n akak1a1a0b 32 Constructing Base b Expansion of n Use the division algorithm to get the base b expansion of n 1 nbq1a00 a0ltbandq1ltn 2 q1bq2a10 a1ltbandq2ltq1 3 q2bqsa20 a2ltbandQ3ltq2 4 etc until 11 0 Then n akak1a1a0b EXAMPLE 321 Find the binary ecopansion of 42 Solution We can use the division algorithm to get the al s 3 APPLICATIONS OF NUMBER THEORY 157 42 2210 21 2101 10 250 5 221 2 210 1 201 This gives us 42 125 024 123 022 121 0 Thus the binary eppansion of 42 is 1010102 EXAMPLE 322 Find the hepadecirnal eccpansion of 42 Solution This time we use 16 for b 42 162 10 2 160 2 So the heccadecirnal eccpansion of42 is 2A16 recall we use A 10 in hepadecirnal notation EXAMPLE 323 Find the decimal notation of the octal representation 102408 10248 183 082 281 4 532 33 Cancellation in Congruences THEOREM 331 Suppose GCDcm 1 and ac E bcrnod Then a E brnod PROOF Suppose GCDcm 1 and ac E bcrnod We may assume in gt 1 so that c 31 0 Then acibccaib km for some integer k This implies cUsm Since GCDcm 17 Lemma 2 from Module 52 asserts that if cUsm7 then c1h Write h cd for some integer d7 and substitute for h in the equation above Ca 7 b hm cdm cdm 3 APPLICATIONS OF NUMBER THEORY 158 Since the cancellation law holds for integers and c 74 0 we can cancel c to get a 7 b dm Thus a E bmod D Discussion Theorem 331 provides a criterion for being able to cancel when you have a congruence Notice that in order to perform the cancellation the modulus in and the factor to be cancelled must be relatively prime Here is an example to illustrate why EXAMPLE 331 36 E 16mod 12 but3 i 1mod 12 The reason cancellation fails is that 6 and 12 are not relatively prime EXAMPLE 332 3 6 E 8 6mod 5 Here 6 and 5 are relatively prime and we can easily check that 3 E 8mod 5 34 lnverses mod m DEFINITION 341 An integer a is a multiplicative inverse to a modulo m 239f aa E1mod EXAMPLE 341 The inverse of 14 modulo 9 is 2 since 14 2 E 28 E 1mod 9 There is no inverse to 6 modulo 9 however In general an inverse refers to something that undoes77 another thing leaving something that is an identity 0 With regular multiplication of real numbers the inverse of z is since 1 lnverses do not necessarily exist if we look only at integers 0 With regular addition of real numbers the inverse of z is 7x since x7x 0 With matrices and matrix multiplication the inverse of a matrix A is a matrix A l such that AA l A lA I where I is the identity matrix Not all matrices have inverses 0 With functions and composition the inverse of a function f is a function f l such that f o f 1z f 1 o z identityw Not all functions have inverses 0 Not all integers even nonzero integers have inverses modulo m Moreover if an inverse does exist it is not unique This last part is different from all the other ones mentioned before We shall see below however that if an integer a has an inverse modulo m then it has a unique inverse lying between 0 and m 3 APPLICATIONS OF NUMBER THEORY 159 35 Linear Congruence DEFINITION 351 A linear congruence is d congruence of the form ax E bmod m where a b and m are cced integers and m gt 0 One may solve for x by nding an inverse ofa modulo m if an inverse eccists EXAMPLE 351 Solve the linear congruence 2x E 7mod 15 for d Solution An inverse of2 modulo Z5 is 8 Thus 8 2d E 87mod 15 z E 56mod 15 1 z 1mod 15 Discussion Solving a linear congruence an E b mod m is very similar to solving an ordi nary linear equation ax b We can solve for z in the linear equation by multiplying through by the multiplicative inverse 1a of 1 provided a 31 0 In a similar manner we can solve a linear congruence ax E bmod m provided a has a multiplicative inverse a modulo in Then z E a az E a bmod To get a canonical choice for d we would reduce a b modulo m Caution DO NOT express the solution to a linear congruence ax E bmod m as x g as you would the solution to the linear equation ax b We have previously cautioned against using fractional notation when doing integer arithmetic but in the world of integers modulo in they are expressly forbidden 36 Criterion for Invertibility mod m THEOREM 361 Suppose a dndm are integers dndm gt 1 Then a has an inverse modulo m if and only if GCDam 1 Moreover if GCDam 1 then a has a unique inverse a with 0 lt a lt m PROOF GCDam 1 if and only if there are integers s and t such that 1 as int This is true if and only if there is an integer s such that 1 E asmod By de nition this is true if and only if a has an inverse namely 5 modulo m D Discussion proof of the moreover77 part is complete once you solve the following exercise 3 APPLICATIONS OF NUMBER THEORY 160 Theorem 361 provides us with the conditions required for inverses modulo m to exist For a to have an inverse modulo m7 a and m must be relatively prime The EXERCISE 361 Prove that if ab E 1mod m and b E cmod m then ac 1mod 37 Example 371 We can use the Euclidean Algorithm and the division gorithm to nd the unique77 inverse of a modulo m N 16 Fe 9 EXAMPLE 371 Find the inverse of8 modulo 35 Apply the Euclidean Algorithm 35 483 8 232 3 121 2 210 Find the linear combination of8 and 35 that equals 1 the COD 1 3 7 12 135 48l 118 23l 35 7 48 718 7 235 7 48 335 7138 This gives 7138 E 1mod 357 so an inverse of8 modulo 35 is 713 To nd the inverse between 0 and 35 use the division algorithm 713 7135 22 The unique inverse of8 modulo 35 between 0 and 35 is 22 Check 8 22 176 5351E1 mod 35 38 Fermatls Little Theorem THEOREM 381 Up is a prime that does not divide the integer a then ap l E 1mod p a E amod p a 3 APPLICATIONS OF NUMBER THEORY 161 EXAMPLE 381 Find 5158 mod 11 Solution Since 158 1510 8 we have 5158 5151058 E 58mod 117 by Fermat s little theorem applied to a 515 andp 11 Now 58 524 254 E 34mod 11 81 E 4mod 11 Thus 5158 mod 11 4 Discussion The problem of determining whether a given integer is a prime may be very dif cult This fact is both interesting mathematically and useful in coding theory Fermat7s little theorem provides some help in working with prime numbers and pro vides the basis for many probabilistic piimality tests We will not give a proof of Fermat7s theorem7 since it involves concepts from the theory of groups that would take us too far a eld An elementary proof can be found in Introduction to Modern Algebra7 Fourth Edition7 by McCoy and Janusz Allyn and Bacon7 1987 The converse of Fermat7s little theorem is not true In particular7 there are com posite numbers n such that 2W1 E 1mod These are called pseudopiimes They are very rare7 but 341 is a pseudoprime Fermat7s little theorem can be used to reduce the problem of nding the remainder of a large power modulo a prime ln Example 3817 we use the fact that 515 and 11 are relatively prime and Fermat7s little theorem to get 51510 E mod 117 thereby reducing 5158 to a smaller power of 5 modulo 11 One clearly has to be comfortable with the laws of exponents to carry out an exercise such as this 3 APPLICATIONS OF NUMBER THEORY 162 39 RSA System The RSA system is a public key cryptosystem based on modular exponentiation modulo the product of two large primes This system named after the researchers who introduced it Rivest Shamir and Adleman is a public key cryptosystem QPONQFH FFQFW RSA Code 1 Find p and q large primes 2 Choose e so that e lt pq and GCDep71q71 1 e must be odd but not necessarily prime 3 Find d such that de E 1mod p 71q 7 4 Encryption function ft t5mod pg 5 Decryption function f 1c cdmod pq The public keys are pqe and the private key is d EXAMPLE 391 Here is the routine usingp 61 q 53 e 17 andd 2753 The rst prime number destroy after computing e and d p 61 The second prime number destroy after computing e and d q 53 Modulus give this to others pq 3233 Public eccponent give this to others e 17 Private eccponent keep this secret d 2753 Your public key is pq e 323317 Your private key is d 2753 The encryption function is ft The decryption function is 39 f t17mod 3233 1c c2753mod 3233 To encrypt the plaintext value 123 do this f123 12317mod 3233 337587917446653715596592958817679803mod 3233 855 To decrypt the ciphertext value 855 do this f 1855 8552753mod 3233 an incredibly huge number goes here mod 3233 123 The large exponential expressions can be reduced modulo 3233 in a piecemeal fashion however so that you dont actually have to calculate these large numbers 4 MATRICES 163 4 Matrices 41 De nitions DEFINITION 411 A matrix is a rectangular array of numbers A matria with in rows and n columns is said to have dimension in gtlt n and may be represented as follows an 012 39 39 39 aln 021 022 39 39 39 am A laijl aml amZ 39 39 39 amn DEFINITION 412 Matrices A and B are equal A B ifA and B have the same dimensions and each entry ofA is equal to the corresponding entry ofB Discussion Matrices have many applications in discrete mathematics You have probably encountered them in a precalculus course We present the basic de nitions associated with matrices and matrix operations here as well as a few additional operations with which you might not be familiar We often use capital letters to represent matrices and enclose the array of numbers a b a with brackets or parenthesis eg A or A We do not use simply c d a straight lines in place of brackets when writing matrices because the notation has a special meaning in linear algebra A aw is a shorthand notation often used when one wishes to specify how the elements are to be represented where the rst subscipt i denotes the row number and the subscript j denotes the column number of the entry aij Thus if one writes a34 one is referring to the element in the 3rd row and 4th column This notation however does not indicate the dimensions of the matrix Using this notation we can say that two in gtlt n matrices A aw and B bigl are equal if and only if aij bij for all i and j EXAMPLE 411 The following matria is a 1 gtlt 3 matria with an 2 an 3 and 113 72 2 3 72 4 MATRICES 164 EXAMPLE 412 The following matricv is a 2 gtlt 3 matrix 0 7T 72 2 5 0 42 Matrix Arithmetic Let oz be a scalar A aw and B bigl be m gtlt n matrices and C 07 a n gtlt p matrix Subtraction A 7 B aij 7 bigl 3 Scalar Multiplication 04A amj TL E aikaj k1 Discussion Matrices may be added subtracted and multiplied provided their dimensions satisfy certain restrictions To add or subtract two matrices the matrices must have the same dimensions Notice there are two types of multiplication Scalar multiplication refers to the product of a matrix times a scalar real number A scalar may be multiplied by a matrix of any size On the other hand matrix multiplication refers to taking the product of two matrices The de nition of matrix multiplication may not seem very natural at rst It has a great many applications however some of which we shall see Notice that in order for the product AC to be de ned the number of columns in A must equal the number of rows of 0 Thus it is possible for the product AC may be de ned while CA is not When multiplying two matrices the order is important In general AC is not necessarily the same as CA even if both products AC and CA are de ned In other words matrix multiplication is not commutative 43 Example 431 EXAMPLE 431 Suppose 3 4 76 0 172 3 0 1 A B me 0 71 2 2 034 3745 172 34 4 MATRICES 165 Then 1 71 1 A B 3 71 9 1 73 5 A 7 B i 73 7 71 3 i6 9 3A 0 9 12 6 0718 4 71118 22 Let us break down the multiplication of A and C in Example 431 down to smaller pieces 3 172 3 0 3036 111 3 4 172 3 0 i1 303 42766 0 172 3 4 76 0 172 3 0 i1 2 2 303 4276 76749 07412 172 34 6 0 718 Now compute the second row to get 4 711 18 D D 4 MATRICES 166 44 Special Matrices H A square matrix is a matrix with the same number of rows as columns E0 A diagonal matrix is a square matrix whose entries off the main diagonal are zero 9 An upper triangular matrix is a matrix having all the entries below the main diagonal equal to zero 7 A lower triangular matrix is a matrix having the entries above the main diagonal equal to zero 9 The n gtlt 71 identity matrix7 I7 is the n gtlt 71 matrix with ones down the diagonal and zeros elsewhere 6 The inverse of a square matrix7 A is the matrix A l7 if it exists7 such that AA 1 A lA I The transpose of a matrix A calj is At 174 005 A symmetric matrix is one that is equal to its transpose Discussion Many matrices have special forms and special properties Notice that7 although a diagonal matrix must be square7 no such condition is put on upper and lower triangular matrices The following matrix is a diagonal matrix it is also upper and lower triangular 200 0720 L0 06 The following matrix is upper triangular 710372 0125 0073 3 The next matrix is the transpose of the previous matrix Notice that it is lower triangular 4 MATRICES 167 71 0 0 0 1 0 2 73 72 5 3 The identity matrix is a special matrix that is the multiplicative identity for any matrix multiplication Another way to de ne the identity matrix is the square matrix I calj where aij 0 ifz39 31 j and an 1 The n gtlt 71 identity I has the property that IA A and AI A7 whenever either is de ned For example7 10 37472 37472 0 1 2 7 0 2 7 0 The inverse of a matrix A is a special matrix A 1 such that AAA AAA I A matrix must be square to de ne the inverse Moreover7 the inverse of a matrix does not always exist EXAMPLE 441 21 171 710 11 71 2 701 sothat 21717 171 11 T 71 2 The transpose of a matrix is the matrix obtained by interchanging the rows for the columns For example7 the transpose of 2 72 2 3 71 A is At 3 5 72 5 6 1 6 lf the transpose is the same as the original matrix7 then the matrix is called symmetric Notice a matrix must be square in order to be symmetric We will show here that matrix multiplication is distributive over matrix addition 4 MATRICES 168 Let A calj and B blj be m gtlt n matrices and let G clj be an n gtlt p matrix We use the de nitions of addition and matrix multiplication and the dis tributive properties of the real numbers to show the distributive property of matrix multiplication Let 2 and j be integers with 1 S 2 S m and 1 S j S p Then the element in the 2 th row and the j th column in A BC would be given by aikckj bikckj M 02k bik0kj M w H H w H H TL aikaj E bikckj k1 H M w H H TL aikaj E bikckj 1 k1 H M w H This last part corresponds to the form the element in the 2 th row and j th column of A0 BC Thus the element in the 2 th row and j th column of A BC is the same as the corresponding element of A0 BC Since 2 and j were arbitrary this shows A BC A0 BC The proof that CA B CA GB is similar Notice that we must be careful7 though7 of the order of the multiplication Matrix multiplication is hot commutative 45 Boolean Arithmetic If a and b are binary digits 0 or 17 then 17 if a b 1 a b otherw1se 7 07 if a b 0 a V b 1 otherw1se 7 DEFINITIONS 451 Let A and B be 72 gtlt m matrices Z The meet ofA and B A B aij Abij 2 The join ofA and B A V B aij V bigl DEFINITION 451 Let A aij be m gtlt h and B blj be h gtlt n The Boolean product ofA and B A C B is the m gtlt n matm39at C clj de ned by CH an A blj V am A 32739 V dig A bgj V 39 39 39 V 1 A 4 MATRICES 169 Discussion Boolean operations on zero one matrices is completely analogous to the standard operations7 except we use the Boolean operators and V on the binary digits instead of ordinary multiplication and addition7 respectively 46 Example 461 1 1 0 1 1 0 1 0 1 0 0 0 1 0 EXAMPLE 461 LetA B me 0 1 1 0 1 0 1 0 0 1 1 1 0 0 Then 0 0 Z A B 1 0 0 1 2 A V B 1 0 1 1 0 3 A G O 0 1 1 Here are more details of the Boolean product in Example 461 A O i 1A1V1AOVOAOV1A1 1A1V1A1V0A1V1A0 1AOV1AOVOA1V1AO Q 0A1V1AOV1AOVOA1 0A1V1A1V1A1VOAO OAOV1AOV1A1VOAO 1VOVOV11V1VOV0 OVOVOVO OVOVOVO 0V1V1V0 0VOV1V0 EXERCISE 461 110 0 1010 A 0 011 B 010 0 0101 1110 4 MATRICES 170 Find 1AB 2AB EXERCISE 462 1 1 0 A 0 0 1 0 1 0 Find 1A A 2A A A 3A A A A EXERCISE 463 1 1 0 A 0 0 1 0 1 0 Find GLIA the Boolean product ofA with itselfn times Hint D0 exercise 462 rst CHAPTER 6 Introduction to Graph Theory 1 Introduction to Graphs 11 Simple Graphs DEFINITION 111 A simple graph V E consists ofa set representing uertiees V and a set of unordered pairs of elements of V representing edges E A simple graph has 0 no arrows o no loops and 0 cannot have multiple edges joining uertiees Discussion Graphs offer a convenient way to represent various kinds of mathematical objects Essentially any graph is made up of two sets a set of vertices and a set of edges Depending on the particular situation we are trying to represent however we may wish to impose restrictions on the type of edges we allow For some problems we will want the edges to be directed from one vertex to another whereas in others the edges are undirected We begin our discussion with undirected graphs The most basic graph is the simple graph as de ned above Since the edges of a simple graph are undirected they are represented by unordered pairs of vertices rather than ordered pairs For example if V a b c then a b b a would represent the same edge EXERCISE 111 If a simple graph G has 5 vertices what is the maximum number of edges that G can have 12 Examples EXAMPLE V U1121314 E Ul gU11312131214 171 1 INTRODUCTION TO GRAPHS 172 V1 V2 V3 V4 EXAMPLE 122 V abc E abbcac a 13 Multigraphs De nition A multigraph is a set of vertices7 V7 a set of edges7 E7 and a function fE uvuv Vandu7 v If 61 62 E E are such that f61 f627 then we say 61 and 62 are multiple or parallel edges EXAMPLE 131 V abcd E 616266 f E a uw u1 E V and u 31 1 is de ned as follows 6 61 62 63 64 65 66 f6 a70 070 075 C75 57d 57d 1 INTRODUCTION TO GRAPHS 173 a 63 b Discussion In Example 131 el and e2 are parallel edges7 but the edges e2 and e5 are not called parallel edges EXERCISE 131 Fmd all the parallel edges Example 3 Notice that a rnultigraph allows for multiple edges between a pair of vertices7 but does not allow for loops In some applications it may be desirable to illustrate all the connections between the vertices Say for exarnple7 in a network there may be multiple wires connecting the same units 14 Pseudograph DEFINITION 141 A pseudograph is a set of vertlees V a set of edges E and afahetlzm f E a uv u1 E V Ife E E is such that fe mu u then we say e is a loop EXAMPLE 141 V abcd E 5152 58 f E a uw uw E V is de ned as follows 6 61 62 63 64 65 66 67 68 f6la70 070 075 C75 57d 57d 0 d 1 INTRODUCTION TO GRAPHS 174 Discussion The psuedograph adds the possibility of loops For example7 a diagnostic line may be used in a network7 which is a line connecting a computer to itself 15 Directed Graph DEFINITION 151 A directed graph V7 E consists of a set of vertiees V and a set of directed edges E The elements ofE are ordered pairs of vertiees EXAMPLE 151 V abcd E 07 07607 075 075 57d dd 07607 61761 1 INTRODUCTION TO GRAPHS 175 Discussion A directed graph or digraph allows loops and allows two edges joining the same vertex but going in the opposite direction More than one edge going in the same direction between vertices however is not allowed A directed edge is de ned by an ordered pair rather than an unordered pair That is the ordered pair ab is different from the ordered pair ba while the unordered pair ab b a Be careful of the notation you use when writing an edge EXERCISE 151 If a directed graph G has 5 vertices what is the maximum number of directed edges of G 16 Directed Multigraph DEFINITION 161 A directed multigraph V E consists of vertices V and edges E and a function f E a V gtlt V uoluo E V The edges el and e2 are multiple edges if fe1 fe2 EXAMPLE 161 V abcd E 162610 f E a uo uo E V is de ned as follows 5 l 51 52 53 54 55 56 57 58 59 510 f6la70 C70 075 C75 57d CM CM CM 075 57d 1 INTRODUCTION TO GRAPHS 176 Discussion Notice the difference between a directed graph and a directed multigraph a di rected graph allows more than one edged to connect the same two vertices as long as they have opposite directions whereas7 no such restriction is placed on the edges of a directed multigraph EXERCISE 161 Give all the multiple edges in Example 16 17 Graph Isomorphism DEFINITION 171 Let G1 V7 E and G2 U7 F be simple graphs The graphs G1 and G2 are isomorphic if there epists a bijection v U such that for all 11112 E V pl and 112 are adjacent in G1 if and only if fi1 and fi2 are adjacent in G2 DEFINITION 172 ff is a bijection as described above then f is called an iso morphism between G1 and G2 and we often write f G1 a G2 Discussion There are several notations that are used to represent an isomorphism We will use a common notation G1 2 G2 to mean that G1 is isomorphic to G2 Trying to construct an isomorphism between graphs can be a very dif cult problem in general If simple graphs G1 and G2 are isornorphic7 then7 clearly7 they must have 1 INTRODUCTION TO GRAPHS 177 the same number of vertices As the next exercise shows G1 and G2 must also have the same number of edges Having the same number of vertices and edges however is in no way su icient for graphs G1 and G2 to be isomorphic Often to prove existence of an isomorphism between two graphs one must actually construct the isomorphism EXERCISE 171 Prove that if simple graphs G1 arid G2 are isomorphic theri G1 arid G2 have the same number of edges EXAMPLE 171 The graphs G1 arid G2 below are isomorphic The bijeetiori is de ried by fo ui V1 V2 U1 U V 4 v G1 GZ Example 171 illustrates a situation in which it is very easy to construct an isomorphism The graph G2 is merely an alteration of G1 obtained by moving one of the edges so it goes around rather than crossing over another edge and relabeling its vertices One way to visualize when two graphs are isomorphic is to imagine that all the vertices are beads and each edge is represented by a sting with each end tied to the beads that represents its endpoints If you pick one or more beads up and place it in another location without untying the strings you obtain a graph that is isomorphic to the original In fact if you can move the vertices to different positions keeping the edges attached to go from one graph to another the two graphs are isomorphic Edges are allowed to pass through77 each other so a straight edge and a knotted edge would be considered the same edge When two graphs are isomorphic they share many of the important properties of graphs In many instances we do not differentiate between two graphs that are 1 INTRODUCTION TO GRAPHS 178 isomorphic Until we study isomorphism in detail7 we will not differentiate between two isomorphic graphs We will discuss graph isomorphisms further in Module 63 EXERCISE 172 Construct a de nition for isomorphism between a two multigrdphs b two pseudogrdphs c two directed graphs d two directed multigrdphs 2 GRAPH TERMINOLOGY 179 2 Graph Terminology 21 Undirected Graphs DEFINITIONS 211 Suppose G V7 E is an undirected graph 1 Two uertices um E V are adjacent or neighbors if there is an edge e between it and i o The edge e connects u undo o The uertices u dndi are endpoints of e 2 The degree of d uertep i denoted dego is the number of edges for which it is an endpoint A loop contributes twice in an undirected graph 0 If dego 0 then i is called isolated o If dego 1 then i is called pendant EXAMPLE 211 V o1o2o3o4 and E e1L7 e27 e37 e4 I 112 and 113 are adjacent 2 dew1 2 Discussion Notice that in computing the degree of a vertex in an undirected graph a loop contributes two to the degree In this example7 none of the vertices is isolated7 but 114 is pendant In particular the vertex U1 is not isolated since its degree is 2 2 GRAPH TERMINOLOGY 180 22 The Handshaking Theorem THEOREM 221 The Handshaking Theorem Let G V7 E be art uridi reeted graph Theri 21m Edam 116V PROOF Each edge contributes twice to the sum of the degrees of all vertices D Discussion Theorem 221 is one of the most basic and useful combinatorial formulas associ ated to a graph It lets us conclude some facts about the numbers of vertices and the possible degrees of the vertices Notice the immediate corollary COROLLARY 2211 The sum of the degrees of the uertiees iri arty graph must be art euert riumber In other words7 it is impossible to create a graph so that the sum of the degrees of its vertices is odd try itl 23 Example 231 EXAMPLE 231 Suppose a graph has 5 uertiees Cari each uertem have degree 3 degree 4 I The sum of the degrees of the uertiees would be 35 if the graph has 5 uertiees of degree 3 This is art odd riumber though so this is riot possible by the hartdshahirtg Theorem 2 The sum of the degrees of the uertiees if there are 5 uertiees with degree 4 is 20 Siriee this is euert it is possible for this to equal Discussion If the sum of the degrees of the vertices is an even number then the handshaking theorem is not contradicted ln fact7 you can create a graph with any even degree you want if multiple edges are permitted However7 if you add more restrictions it may not be possible Here are two typical questions the handshaking theorem may help you answer EXERCISE 231 Is it possible to have a graph S with 5 uertiees each with degree 4 arid 8 edges 2 GRAPH TERMINOLOGY 181 EXERCISE 232 A graph with 21 edges has 7 vertices of degree 1 three of degree 2 seven of degree 3 and the rest of degree 4 How many vertices does it have THEOREM 231 Every graph has an even number of vertices of odd degree PROOF Let V2 be the set of vertices of odd degree and let V5 be the set of vertices of even degree Since V V2 U V5 and V2 V5 Q the handshaking theorem gives us 2lEl Zdegv Z degv Z degv 116V UEVO ierE Z degv 2lEl 7 Z degv veVo veVg Since the sum of any number of even integers is again an even integer the right hand side of this equations is an even integer So the left hand side which is the sum of a collection of odd integers must also be even The only way this can happen however is for there to be an even number of odd integers in the collection That is the number of vertices in V2 must be even D Theorem 231 goes a bit further than our initial corollary of the handshaking theorem If you have dif culty with the last sentence of the proof consider the following facts 0 odd odd even 0 odd even odd 0 even even even If we add up an odd number of odd numbers the previous facts will imply we get an odd number Thus to get an even number out of End0 degv there must be an even number of vertices in V2 the set of vertices of odd degree While there must be an even number of vertices of odd degree there is no restric tions on the parity even or odd of the number of vertices of even degree This theorem makes it easy to see for example that it is not possible to have a graph with 3 vertices each of degree 1 and no other vertices of odd degree 24 Directed Graphs DEFINITIONS 241 Let G V E be a directed graph 1 Let uv be an edge in G Then it is an initial vertex and is adjacent to v The vertem v is a terminal vertex and is adjacent from u 2 The in degree of a vertem v denoted deg v is the number of edges which terminate at v 2 GRAPH TERMINOLOGY 182 3 Similarly the outdegree of i denoted degi is the number of edges which initiate at i 25 The Handshaking Theorem for Directed Graphs THEOREM 251 For any directed graph G V7 E El Edam Edema 116V 116V Discussion When considering directed graphs we differentiate between the number of edges going into a vertex verses the number of edges coming out from the vertex These numbers are given by the in degree and the out degree Notice that each edge contributes one to the in degree of some vertex and one to the out degree of some vertex This is essentially the proof of Theorem 251 EXERCISE 251 Prove Theorem 251 26 Underlying Undirected Graph DEFINITION 261 If we take a directed graph and remove the arrows indicating the direction we get the underlying undirected graph Discussion There are applications in which you may start with a directed graph7 but then later nd it useful to consider the corresponding undirected graph obtained by removing the direction of the edges Notice that if you take a vertex7 i in a directed graph and add its in degree and out degree7 you get the degree of this vertex in the underlying undirected graph 27 New Graphs from Old DEFINITIONS 271 1 W F is a subgraph ofG V E if W Q V and F Q E 2 Given graphs G1 and G2 their union G1UG2V1UV2E1UE2 2 GRAPH TERMINOLOGY 183 3 Given graphs G1 and G2 theirjoin denoted by G1 gtk G2 is the graph consisting of the union G1 U G2 together with all possible edges connecting a oertem of G1 that is not in G2 to a vertep of G2 that is not in G1 EXAMPLE 271 Suppose G has vertep set V ab and one edge e ab connecting a and b and H has a single oertem e and no edges Then Ggtk H has vertep set abe and edges ab ae be EXERCISE 271 Find the union and join of the graphs G1 and G2 below a b a b 0 0 0 5 0 e C d c g Id G1 G2 EXERCISE 272 Prove that the union of two simple graphs is a simple graph EXERCISE 273 Prove that the join of two simple graphs is a simple graph 28 Complete Graphs DEFINITION 281 The complete graph with n oertiees denoted K is the simple graph with emaetly one edge between each pair of distinct oertiees Discussion There are a certain types of simple graphs that are important enough that they are given special names The rst of these are the complete graphs These are the simple graphs that have the maximal number of edges for the given set of vertices For example if we were using graphs to represent a local area network a complete graph would represent the maximum redundancy possible In other words each pair of computers would be directly connected It is easy to see that any two complete graphs with n vertices are isomorphic so that the symbol Kn is ambiguously used to denote any such graph Complete graphs also arise when considering the question as to whether a graph G is planar that is whether G can be drawn in a plane without having any two edges intersect The complete graphs K1 K2 K3 and K4 are planar graphs but Kn is not planar if n 2 5 Draw K4 without making the edges intersect then try to draw K5 without creating an unwanted intersection between edges Notice that Kn can be created from Kn by adding one new vertex and an edge from the new vertex to each vertex of 2 GRAPH TERMINOLOGY 184 EXERCISE 281 Prove that the complete graph Kn n 2 1 is the join KW gtk G where G is a graph with one vertem and no edges 29 Cycles DEFINITION 291 A cycle with n vertiees U1121n denoted by On is a simple graph with edges 0f the jam 711712 02113 713 m new 71 v1 Discussion Notice that a cycle must have at least 3 vertices Here are examples of the rst three possibilities c3 C4 C5 Local area networks that are con gured this way are often called ring networks Notice that the following two graphs are isomorphic Pay close attention to the labels V1 91 V2 V1 91 V2 e2 e 92 4 e4 V4 V3 V3 V4 The point of the last illustration is that sometimes you have to redraw the graph to see the ring shape It also demonstrates that a graph may be planar even though this fact may not be evident from a given representation 210 Wheels DEFINITION 2101 A Wheel is d join 0 gtk G where 0 is a cycle and G is a graph with one oertem and no edges The wheel with n 1 oertiees is denoted W 2 GRAPH TERMINOLOGY 185 Discussion Notice that a wheel is obtained by starting with a cycle and then adding one new vertex and an edge from that vertex to each vertex of the cycle Be careful The index on the notation Wn is actually one less that the number of vertices The n stands for the number of vertices in the cycle that we used to get the wheel 211 n Cubes DEFINITION 2111 The n cube denoted Qm is the graph with 2 vertices rep resented by the vertices and edges of an n dimensional cube These graphs can be constructed recursively as follows 1 Initial Condition A 0 cube is a graph with one vertex and no edges 2 Recursion Let Q and Q be two disjoint n cubes7 n 2 07 and let f Q a Q be an isomorphism Qn1 is the graph consisting of the union Q U Q together with all edges pfi joining a vertex i in Q with its corresponding vertex fi in 2 Qn can also be represented as the graph whose vertices are the bit strings of length n7 having an edge between each pair of vertices that differ by one bit Discussion The n Cube is a common way to connect processors in parallel machines Here are the cubes Q3 and Q4 011 111 010 110 000 1 0 3cube 4cube EXERCISE 2111 Find all the subgraphs of Q1 and Q2 EXERCISE 2112 Label the vertices 0fQ4 appropriately using bit strings of length four 2 GRAPH TERMINOLOGY 186 EXERCISE 2113 Use your labeling of the vertices of Q4 from Epercise 2112 to identify two disjoint Q3 s and an isomorphism between them from which Q4 would be obtained in the recursive description above EXERCISE 2114 Prove that Qn1 Q Q gtk Qi where Q and Qi are disjoint n cubes n 2 0 EXERCISE 2115 Prove that the 2 cube is not isomorphic to the join of two Z cubes EXERCISE 2116 Draw the graph Q5 Hintx Abandon trying to use a cube shape Put 00000 on the top of the page and 11111 on the bottom and look for an organized manner to put the rest in between 212 Bipartite Graphs DEFINITION 2121 A simple graph G is bipartite ifV can be partitioned into two nonempty disjoint subsets V1 and V2 such that every edge connects a vertem in V1 and a vertem in V2 DEFINITION 2122 A bipartite graph is complete ifV can be partitioned into two disjoint subsets V1 and V2 such that there is an edge from every vertem V1 to every vertem in V2 Km denotes the complete bipartite graph when m W11 and n Discussion The de nition of a bipartite graph is not always consistent about the necessary size of W11 and We will assume V1 and V2 must have at least one element each7 so we will not consider the graph consisting of a single vertex bipartite Note There are no edges connecting vertices in V1 in a bipartite graph Neither are there edges connecting vertices in V2 EXERCISE 2121 How many edges are there in the graph Km EXERCISE 2122 Prove that a complete bipartite graph Km is the join Gm gtk Gn of graphs Gm and Gm where Gm has in vertices and no edges and Gn has n vertices and no edges 213 Examples EXAMPLE 2131 A star network is a K1 bipartite graph 2 GRAPH TERMINOLOGY 187 K18 EXAMPLE 2132 Ck fork eueri is a bipartite graph Label the U6Ttl06811121k cyclicly arourid Ck arid put the uertices with odd subscripts iri V1 arid the uertices with eueri subscripts iri V2 1 Suppose V1 is a set of airlines and V2 is a set of airports Then the graph with vertex set V V1 U V2 where there is an edge between a vertex of V1 and a vertex of V2 if the given airline serves the given airport is bipartite If every airline in V1 serves every airport in V2 then the graph would be a complete bipartite graph 2 Supplier warehouse transportation models where an edge represents that a given supplier sends inventory to a given warehouse are bipartite EXERCISE 2131 Is the following graph bipartite b c e EXERCISE 2132 Prove that Qn is bipartite Hiritx You dori t rieed mathematical iriductiori use the bit stririg model for the uertem set Bipartite graphs also arise when considering the question as to whether a graph is planar It is easy to see that the graphs K1 and K2 are planar for every n 2 1 The graphs Km however are not planar if both in and n are greater than 2 In particular K33 is not planar Try it A theorem which we shall not prove states that every nonplanar graph contains in some sense a subgraph see Slide 15 isomorphic to K5 or a subgraph isomorphic to K33 REMARK 2131 The importarit properties of a graph do riot deperid ori how it is drawri To see that two graphs whose uertices have the same labels are isomorphic check that uertices are coririected by art edge iri orie graph if arid orily if they are also coririected by art edge iri the other graph 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 188 3 Representing Graphs and Graph Isomorphism 31 Adjacency Matrix DEFINITION 311 The adjacency matrix A aw for a simple graph G V7 E where V 111112 Zn is de ned by a 7 1 if vi71 is an edge of G W 7 0 otherwise Discussion We introduce some alternate representations7 which are extensions of connection matrices we have seen before7 and learn to use them to help identify isomorphic graphs Remarks Here are some properties of the adjacency matrix of an undirected graph 1 The adjacency matrix is always symmetric 2 The vertices must be ordered and the adjacency matrix depends on the order chosen 3 An adjacency matrix can be de ned for multigraphs by de ning aij to be the number of edges between vertices i and j 4 If there is a natural order on the set of vertices we will use that order unless otherwise indicated 32 Example 321 EXAMPLE 321 An adjacency matiid for the graph V1 V2 V3 V5 V4 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 189 is the matmw 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 Discussion To nd this matrix we may use a table as follows First we set up a table labeling the rows and columns with the vertices 1 1 112 113x 114 115 Since there are edges from 01 to 112 114 and 115 but no edge between 01 and itself or 113 we ll in the rst row and column as follows 1 1 112 113x 114 115 We continue in this manner to ll the table with Us and 17s The matrix may then be read straight from the table EXAMPLE 322 The adjacency matricv for the graph 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 190 1 U2 is the indth E l l H H H C O H C H O O H H O H H H O H O H O H H H H 33 Incidence Matrices DEFINITION 331 The incidence matrix A Lilj for the undirected graph G V7 E is de ned by 1 if edge j is incident with vertecci ai39 7 0 otherwise Discussion Remarks 1 This method requires the edges and vertices to be labeled and depends on the order in which they are written 2 Every column will have exactly two is 3 As with adjacency matrices7 if there is a natural order for the vertices and edges that order will be used unless otherwise speci ed EXAMPLE 331 The incidence matricc for the graph 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 191 V1 61 V2 e5 62 es 66 V3 67 33 V5 64 V4 is the matrip 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 l0 0 0 1 1 0 1 OJ Again you can use a table to get the matrix List all the vertices as the labels for the rows and all the edges for the labels of the columns 3 4 Degree Sequence DEFINITION 341 The degree sequence a graph G with n yertiees is the se queriee d1d2dn where d17d2dn are the degrees of the yertiees of G arid d12d22quot392dn Note that a graph could conceivably have in nitely many vertices If the vertices are countable then the degree sequence would be an in nite sequence If the vertices are not countable7 then this degree sequence would not be de ned 3 5 Graph Invariants DEFINITION 351 We say a property of graphs is a graph invariant or just invariant if whenever a graph G has the property arty graph isomorphic to G also has the property THEOREM 351 The following are iriyariarits of a graph G 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 192 I G has r uertices 2 G has 5 edges 3 G has degree sequence d1d2dn 4 G is a bipartite graph 5 G contains r complete graphs Kn as a subgraphs 6 G contains r complete bipartite graphs Km 7 G contains r n cycles 8 G contains r n wheels 9 G contains r n cubes Discussion Recall from Module 6 Introduction to Graphs that two simple graphs G1 V1E1 and G2 V27E2 are isomorphic if there is a bijection fili lz such that vertices u and i in V1 are adjacent in G1 if and only if u and fi are adjacent in G2 If there is such a function7 we say f is an isomorphism and we write G1 2 G2 It is often easier to determine when two graphs are not isomorphic This is some times made possible by comparing invariants of the two graphs to see if they are different The invariants in Theorem 351 may help us determine fairly quickly in some examples that two graphs are not isomorphic 36 Example 361 EXAMPLE 361 Show that the following two graphs are not isomorphic 1 2 a b G1 G2 The two graphs have the same number of uertices the same number of edges and same degree sequences 33332222 Perhaps the easiest way to see that they 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 193 are not isomorphic is to observe that G2 has only two 4 cycles whereas G1 has three 4 cycles In fact the four yertices of G1 of degree 3 lie in a 4 cycle in G1 but the four yertices of G2 of degree 3 do not Either of these two discrepancies is enough to show that the graphs are not isomorphic Another way we could recognize the graphs above are not isomorphic is to consider the adjacency relationships Notice in G1 all the yertices of degree 3 are adjacent to 2 yertices of degree 3 and Z of degree 2 However in graph G2 all of the yertices of degree 3 are adjacent to Z yertem of degree 3 and 2 yertices of degree 3 This discrepancy indicates the two graphs cannot be isomorphic EXERCISE 361 Show that the following two graphs are not isomorphic 1 2 a b 5 e 7 g h 3 4 c d G1 G2 37 Example EXAMPLE 371 Determine whether the graphs G1 and G2 are isomorphic V5 V4 Solution We go through the following checklist that might tell us immediately if the two are not isomorphic 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 194 0 They have the same number of uertices 5 0 They have the same number of edges 8 0 They have the same degree sequence 4433 2 Since there is no obvious reason to think they are not isomorphic we try to con struct an isomorphism f Note that the above does not tell us there is an isomor phism only that there might be one The only uertem on each that have degree 2 are 113 and u2 so we must have fi3 u2 Now since degi1 degy5 degu1 degu4 we must have either 0 fi1 ul and fi5 U4 or o fi1 U4 and fi5 ul It is possible only one choice would work or both choices may work or neither choice may work which would tell us there is no isomorphism We try fi1 u1 and fi5 u4 Similarly we have two choices with the remaining uertices and try fi2 us and fi4 U5 This de nes a bijection from the uertices of G1 to the uertices of G2 We still need to check that adjacent uertices in G1 are mapped to adjacent uertices in G2 To check this we will look at the adjacency matrices The adjacency matrip for G1 when we list the uetices ofG1 by plygygy4y5 is 01011 10111 A01010 11101 11010 We create an adjacency matrip for G2 using the bijection f as follows since 01 U1 02 Us f 3 112 04 U5 171d 05 U4 we Teammge the order of the uertices of G2 to U1U3u2U5U4 With this ordering the adjacency 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 195 matricc for G2 is 01011 10111 301010 11101 11010 Since A B adjacency is preserved under this bijection Hence the graphs are isomorphic Discussion Notice that trying to establish that the two graphs are isomorphic it is notenough to show that they have the same number of vertices edges and degree sequence In fact if we knew they were isomorphic and we were asked to prove it we would proceed to trying to nd a bijection that preserves adjacency That is the check list is not necessary if you already know they are isomorphic On the other hand having found a bijection between two graphs that doesnt preserve adjacency doesn7t tell us the graphs are not isomorphic because some other bijection that would work If we go down this path we would have to show that every bijection fails to preserve adjacency The advantage of the checklist is that it will give you a quick and easy way to show two graphs are not isomorphic if some invariant of the graphs turn out to be different If you examine the logic however you will see that if two graphs have all of the same invariants we have listed so far we still wouldnt have a proof that they are isomorphic Indeed there is no known list of invariants that can be ef ciently checked to determine when two graphs are isomorphic The best algorithms known to date for determining graph isomorphism have exponential complexity in the number n of vertices EXERCISE 371 Determine whether the following two graphs are isomorphic 3 REPRESENTING GRAPHS AND GRAPH ISOMORPHISM 196 1 2 a b G1 G2 EXERCISE 372 How mariy di ererit isomorphism that is bijectioris that pre serve adjaeerieies are possible between the graphs iri Example 3 71 EXERCISE 373 There are 14 rioriisomorphie pseudographs with 3 vertiees arid 3 edges Draw all of them EXERCISE 374 How mariy rioriisomorphie simple graphs with 6 vertiees 5 edges arid rio cycles are there rt other words how mariy di ererit simple graphs satisfying the criteria that it have 6 vertiees 5 edges arid rio eyeles earl be drawn so that ho two of the graphs are isomorphic 38 Proof of Theorem 351 Part 3 for nite simple graphs PROOF Let G1 and G2 be isomorphic nite simple graphs having degree se quences By part 1 of Theorem 351 the degree sequences of G1 and G2 have the same number of elements Let f VG1 a VG2 be an isomorphism and let i E VG1 We claim d69011 degG2fi If we show this7 then f de nes a bijection between the vertices of G1 and G2 that maps vertices to vertices of the same degree This will imply the degree sequences are the same Proof of claim Suppose d69011 h Then there are k vertices in G1 adjacent to i say u17u2 uk The isomorphism maps each of the vertices to h distinct vertices adjacent to u in G2 since the isomorphism is a bijection and preserves adjacency Thus degG2fu 2 h Suppose degG2fu gt h Then there would be a vertex7 wk L E VG27 not equal to any of the vertices fu1fuk7 and adjacent to Since f is a bijection there is a vertex uk1 in G1 that is not equal to any of U1 uk such that fuk1 wk Since f preserves adjacency we would have uk1 and i are adjacent But this contradicts that d69011 h Thus d6902fu k degaxu a EXERCISE 381 Prove the rst 2 properties listed iri Theorem 351 for riite simple graphs usirig orily the properties listed before each arid the de riitiori of iso morphism CHAPTER 7 Introduction to Relations 1 Relations and Their Properties 11 De nition of a Relation De nition A binary relation from a set A to a set E is a subset R Q A gtlt B If Lab 6 R we say a is related to b by R A is the domain of R7 and B is the codomain of R If A B7 R is called a binary relation on the set A Notation o If 17 b E R7 then we write 11 o If a7b Z R7 then we write a b Discussion Notice that a relation is simply a subset of A gtlt B If Lab 6 R7 where R is some relation from A to B7 we think of a as being assigned to b In these senses students often associate relations with functions In fact7 a function is a special case of a relation as you will see in Example 124 Be warned7 however7 that a relation may differ from a function in two possible ways If R is an arbitrary relation from A to B7 then 0 it is possible to have both Lab 6 R and a7b E R7 where b 31 b that is7 an element in A could be related to any number of elements of B or o it is possible to have some element a in A that is not related to any element in B at all 197 1 RELATIONS AND THEIR PROPERTIES 198 Often the relations in our examples do have special properties but be careful not to assume that a given relation must have any of these properties 12 Examples EXAMPLE 121 LetA abc andB 1 234 and let R1 a 1 a 2 04 EXAMPLE 122 Let R2 C N gtlt N be de ned by 77171 E R2 if and only if EXAMPLE 123 Let A be the set of all FSU students and B the set of all courses o ered at FSU De ne R3 as a relation from A to B by 50 E R3 if and only ifs is enrolled in c this term Discussion There are many different types of examples of relations The previous examples give three very different types of examples Let7s look a little more closely at these examples Example 12 This is a completely abstract relation There is no obvious reason for a to be related to 1 and 2 It just is This kind of relation while not having any obvious application is often useful to demonstrate properties of relations Example 122 This relation is one you will see more frequently The set R2 is an in nite set so it is impossible to list all the elements of R2 but here are some elements of R2 27674787575757076707671872718 Equivalently we could also write 2R26 4R28 5R25 5R20 6R20 6R218 2R218 Here are some elements of N gtlt N that are not elements of R2 672 874 275 075 076 1876 678 876 Epample 123 Here is an element of R3 you MAD2104 EXAMPLE 124 Let A and B be sets and let f A a B be afunetion The graph off de ned by graphf 2 E A is a relation from A to B Notice the previous example illustrates that any function has a relation that is associated with it However not all relations have functions associated with them EXERCISE 121 Suppose f R a R is de ned by fp I Find 5 elements of the relation graphf 1 RELATIONS AND THEIR PROPERTIES 199 2 Find 5 elements ofR gtlt R that are not in graphf EXERCISE 122 Find a relation from R to R that cannot be represented as the graph of a functions EXERCISE 123 Let n be a positive integer How many binary relations are there on a set A if A n Hintx How many elements are there in IA gtlt AI 13 Directed Graphs DEFINITIONS 131 o A directed graph or a digraph D from A to B is a collection ofvertices V Q A U B and a collection ofedges R Q A gtlt B o If there is an ordered pair e Ly in R then there is an arc or edge from x to y in D o The elements z and y are called the initial and terminal vertices of the edge e Ly respectively Discussion A digraph can be a useful device for representing a relation7 especially if the relation isnt too large77 or complicated The digraph that represents R1 in Example 121 is a 1 2 b0 03 co b O4 Discussion If R is a relation on a set A7 we simplify the digraph D representing R by having only one vertex for each a E A This results7 however7 in the possibility of having loops7 that is7 edges from a vertex to itself7 and having more than one edge joining distinct vertices but with opposite orientations 1 RELATIONS AND THEIR PROPERTIES 200 A digraph for R2 in Example 122 would be dif cult to illustrate and impossible to draw completely since it would require in nitely many vertices and edges We could draw a digraph for some nite subset of R2 It is possible to indicate what the graph of some in nite relations might look like but this one would be particularly dif cult EXAMPLE 131 Let R5 be the relation from 0 1 23456 de ned by mR5n if and only ifm E nmod 3 The digraph that represents R5 is w m Jgt U1 14 Inverse Relation DEFINITION 141 Let R be a relation from A to B Then R l balab E R is a relation from B to A R 1 is called the inverse of the relation R Discussion The inverse of a relation R is simply the relation obtained by reversing the ordered pairs of R The inverse relation is also called the converse relation EXAMPLE 141 Recall Example 12 A abc and B 1234 and R1 a 1 a2 c4 Then R l 1a 2a4a EXERCISE 141 Recall Example 124 A and B are sets and f A a B is a function The graph off graphf p E A is a relation from A to B I What is the inverse of this relation 2 Does f have to be invertible for the inverse of this relation to exist 3 If f is invertible nd the inverse of the relation graphf in terms of the inverse function f l 1 RELATIONS AND THEIR PROPERTIES 201 15 Special Properties of Binary Relations DEFINITIONS 151 Let A be a set and let R be a binary relation on A I R is re exive if Vxz E A a E 2 R is irre exive if Vxz E A a Z 3 R is symmetric if WViW y E R c 21796 E 3 4 R is antisymmetric if V cViKKLy 6 RI 21795 6 RI 96 5 R is asymmetric if WViW y E R c 11795 if 3 6 R is transitive if ViviWWW 6 RI 172 6 RI 9672 E 3 21 Discussion Study the de nitions of the de nitions of the properties given above You must know these properties7 be able to recognize whether or not a relation has a particu lar property7 and be able to prove that a relation has or does not have a particular property Notice that the de nitions of re exive and irre exive relations are not com plementary That is7 a relation on a set may be both re exive and irre exive or it may be neither The same is true for the symmetric and antisymmetric properties7 as well as the symmetric and asymmetric properties Some texts use the term antire exive for irre exive EXERCISE 151 Before reading further nd a relation on the set a7b7c that is neither a reflecciye nor irreflecciye b symmetric nor antisymmetric c symmetric nor asymmetric 16 Examples of Relations and their Properties EXAMPLE 161 Suppose A is the set of FSU students and R is the relation given by aRb if students a and b have the same last name This relation is o reflecciye 0 not lTTC CCElUC o symmetric 0 not antisymmetric 1 RELATIONS AND THEIR PROPERTIES 202 0 not asymmetric o transitive EXAMPLE 162 Suppose T is the relation on the set of integers given by pTy if 2x 7 y 1 This relation is not refleccive not irreflepive not symmetric antisymmetric not asymmetric not transitive EXAMPLE 163 Suppose A a7b7c7d and R is the relation aa This relation is not refleccive not irreflepive symmetric antisymmetric not asymmetric transitive Discussion The examples above illustrate three rather different relations Some of the rela tions have many of the properties de ned on Section 157 whereas one has only one of the property It is entirely possible to create a relation with none of the properties given in Section 15 EXERCISE 161 Give an eccample of a relation that does not satisfy any property given in Section 15 17 Proving or disproving relations have a property EXAMPLE 171 Suppose T is the relation on the set of integers given by pTy if 2x 7 y 1 This relation is 0 not refleccive PROOF 2 is an integer and 2 2 7 2 2 31 1 This shows that Vplx E Z 7 oz 6 T is not true D 0 not irreflepive PROOF 1 is an integer and 2 1 71 1 This shows that Vplx E Z 7 ex Z T is not true D 1 RELATIONS AND THEIR PROPERTIES 203 0 not symmetric PROOF Both 2 and 3 are integers 22 7 3 1 and 23 7 2 4 7amp1 This shows 2R3 but 332 that is VsVyxy E Z 7 yz E T is not true D o antisymmetric PROOF Let mn E Z be such that mn E T and nm E T By the de nition of T this implies both equations 2m 7 n 1 and 2n 7 m 1 must hold We may use the rst equation to solve for n n 2m 7 1 and substitute this in for n in the second equation to get 22m 7 1 7 m 1 We may use this equation to solve for m and we nd in 1 Now solve for n and we get n 1 This shows that the only integers in and n such that both equations 2m7n 1 and 2n 7m 1 hold are m n 1 This shows that VmVnmn E T 71771 E T 7 m 0 not asymmetric PROOF 1 is an integer such that 11 6 T Thus Vszxy E T 7 ba Z T is not true counterexample is a b 1 D 0 not transitive PROOF 2 3 and 5 are integers such that 23 6 T 35 6 T but 25 Z T This shows VxVszKLy E T yz E T 7 L2 6 T is not true D EXAMPLE 172 Recall Example 122 R2 C N gtlt N was de ned by mn E R2 if and only if 0 reflecciye PROOF Since nln for all integers n we have nRgn for every integer This shows R2 is re exive 0 not irrefleaiye PROOF 1 is an integer and clearly IRZI This shows R2 is not irre exive you could use any natural number to show R2 is not irre exive 0 not symmetric PROOF 2 and 4 are natural numbers with 2 4 but 4 2 so 2R24 but 4322 This shows R2 is not re exive D o antisymmetric PROOF Let nm E N be such that nRgm and ngn By the de nition of R2 this implies nlm and Hence we must have m n This shows R2 is antisyrnrnetric D 1 RELATIONS AND THEIR PROPERTIES 204 0 not asymmetric PROOF Let in n be any natural number Then nRgm and ngn which shows R2 is not asymetric You may use a particular number to show R2 is not asymmetric o transitive PROOF Let p q r E N and assume goqu and ngr By the de nition of R2 this means plq and qlr We have proven in Integers and Division that this implies plr thus pRgr This shows R2 is transitive Discussion When proving a relation R on a set A has a particular property the property must be shown to hold for all possible members ofthe set For example if you wish to prove that a given relation R on A is re exive you must take an arbitrary element x from A and show that sz Some properties such as the symmetric property are de ned using implications For example if you are asked to show that a relation R on A is symmetric you would suppose that z and y are arbitrary elements of A such that zRy and then try to prove that ny It is possible that a property de ned by an implication holds vacuously or trivially EXERCISE 171 Let R be the relation on the set of real numbers given by pRy if and only ifp lt y Prove R is antisymmetric When proving B does not have a property it is enough to give a counterexample Recall VszPzy gt Hx y Ppy EXERCISE 172 Prove whether or not each of the properties in Section 15 holds for the relation in Example 161 EXERCISE 173 Prove whether or not each of the properties in Section 15 holds for the relation in Example 163 18 Combining Relations lmportant Question Suppose property P is one of the properties listed in Section 15 and suppose R and S are relations on a set A each having property P Then the following questions naturally arise 1 RELATIONS AND THEIR PROPERTIES 205 19 Example of Combining Relations EXAMPLE 191 Let R1 and R2 be transitive relations on a set A Does it follow that R1 U R2 is transitive Solution No Here is a countereccarnple A 1727 R1 17 27 R2 27 Therefore R1 U R2 1727271 Notice that R1 and R2 are both transitive vacuously since there are no two ele ments satisfying the conditions of the property However R1 U R2 is not transitive If it were it would have to have 11 and 22 in R1 U R2 Discussion Example 191 gives a counterexample to show that the union of two transitive relations is not necessarily transitive Note that you could nd an example of two transitive relations whose union is transitive However7 the question asks if the given property holds for two relations must it hold for the binary operation of the two relations This is a general question and to give the answer yes we must know it is true for every possible pair of relations satisfying the property Here is another example EXAMPLE 192 Suppose R and S are transitive relations on the set A Is R S transitive Solution Yes PROOF Assume R and S are both transitive and let ab7 be 6 R S Then abbc E R and abbc E S It is given that both R and S are transitive so ac E R and ac E S Therefore a7c E R S This shows that for arbitrary ab7 be 6 R S we have a7c E R S Thus R S is transitive D 110 Composition DEFINITIONS 1101 I Let 0 R1 be a relation from A to B and 0 R2 be a relation from B to C 1 RELATIONS AND THEIR PROPERTIES 206 Then the composition of R1 with R2 denoted R2 0 R1 is the relation from A to 0 de ned by the following property 72 6 R2 0 R1 if and only if there is a y E B such that Ly E R1 and 972 E R2 2 Let R be a binary relation on A Then Pi is de ned recursively as follows Basis R1 R Recurrence Rn1 R o R ifn 2 1 Discussion The composition of two relations can be thought of as a generalization of the composition of two functions7 as the following exercise shows EXERCISE 1101 Prove If f A a B and g B a C are functions then ampKg 0 f amp19 0 ampW EXERCISE 1102 Prove the composition of relations is an associative operation EXERCISE 1103 Let R be a relation on A Prove R o R R o B using the previous eccercise and induction EXERCISE 1104 Prove an ordered pair Ly E R if and only if in the digraph D of B there is a directed path of length n from x to y Notice that if there is no element of B such that a7b E R1 and be 6 R2 for some a E A and c E C then the composition is empty 111 Example of Composition EXAMPLE 1111 Let A doc B 1234 and OIIIIIIIV R1 a747b71 0 R2 1II1IV2I Then RzoRl bllbIV Discussion It can help to consider the following type of diagram when discussing composition of relations7 such as the ones in Example 1111 as shown here 1 RELATIONS AND THEIR PROPERTIES 207 a 1 I 2 II b 3 III c 4 IV EXAMPLE 1112 IfR and S are transitive binary relations on A is R0 S tran sitive Solution No Here is a countereccample Let R 12 347 and S 237 47 Then both R and S are transitive vacuously However R0 S 247 47 2 is not transitive EXAMPLE 1113 Suppose R is the relation on Z de ned by aRb if and only if aIb Then R2 R EXERCISE 1111 Let R be the relation on the set of real numbers given by thy if and only if i 2 y 1 Describe the relation R2 2 Describe the relation Pt EXERCISE 1112 Let P be a property given below and let R and S be relations on A satisfying property P When does the relation obtained by combining R and S using the operation given satisfy property P I P is the refleccive property a RU S b R S c REDS d R 7 S e R0 S f 3 1 9 R 2 P is the symmetric property 1 RELATIONS AND THEIR PROPERTIES 208 3 P is the transitive property a R U S b R m S 112 Characterization of Transitive Relations THEOREM 1121 Let R be a binary relation on a set A R is transitive if and only ifR Q R fern 21 PROOF To prove R transitive a Rn Q R we assume R is transitive and prove R Q R for n 2 1 by induction Basis Step n 1 R1 R7 so this is obviously true Induction Step Prove R Q R a R 1 Q R Assume R Q R for some n 2 1 Suppose Ly E Rn By de nition Rn R 0 R7 so there must be some a E A such that x a E R and my 6 R However7 by the induction hypothesis R Q R7 so my 6 R R is transitive though7 so ma7 my 6 R implies Ly E R Since my was an arbitrary element of Rn this shows Rn Q R Now we must show the other direction R Q R7 for n 2 17 implies R is transitive We prove this directly Assume zyyz E R But by the de nition of composition7 this implies zz E R2 But R2 Q R7 so zz E B This shows R is transitive D Discussion
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'