### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Discrete and Foundational Mathematics I MATH 187

BSU

GPA 3.72

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Mathematics (M)

This 27 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 187 at Boise State University taught by Melvin Holmes in Fall. Since its upload, it has received 10 views. For similar materials see /class/217990/math-187-boise-state-university in Mathematics (M) at Boise State University.

## Reviews for Discrete and Foundational Mathematics I

### 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: 10/03/15

Additional Notes for February 3 Dr Holmes February 3 2004 These notes discuss additional content in the February 3 lecture which is not found in the book Additional rules for summation basic properties El f l f1 2E2 2 2311 0 f n 1 summing units n 2i 1 1 n distributing a constant multiplier 0311 i 2710 2 adding summations with the same range 2311 i 3198 2310 i 90 telescoping sums 231fi 1 N ff 1 f1 Development of the formula nn 1 29 2 By telescoping sums 21 2 12 i2 n 12 12 n 271 1 1 n 27 By algebra and by applying rules for summations given above 27 12 2 23 22 1 2 2312i1 22 211 221 n Things equal to the same thing are equal to each other so 2Ey1i n n 2n and so 2Eydi n 2n n n2 n and so 2 1 n n n n 2311 T 7 Here we have proved the formula but not by induction Note that we have not only proved the formula but we have developed it This won t be true with the induction proof Prove the previous formula by induction Theorem n n n 1 2511 Proof The proof is subdivided into the basis step and induction step Basis step The goal is to prove 212 2110 1 is true Induction step The goal is to prove that for any natural number k if 2511 mg then 21331 lt 1 2gt Let k be an arbitrary natural number the proof of a universal sentence about natural numbers will usually start this Assume 2512 This is the inductive hypathcsis ou should always clearly indicate the inductive hypothesis in your induction proofs and indicate clearly where it is used Our goal is now to prove 2532 213110 2121i k 1 by a basic property of summations k 1 LC l k 1 2 by inductive hypothesis and substitution of equals for equals k2k 2k2 k23k2 k1k2 T 2 f f by algebra which completes the proof If you look at this file again later you may find the derivation of the formula for 231L129 from the rules for summations inserted here Additional notes for Feb 20 and 23 Dr Holmes February 23 2004 These notes contain additional ideas about finite and infinite sets and about sizes of sets found in my lectures on Feb 20 and Feb 23 De nition We that two finite sets are the same size if A B Theorem Two nite sets A and B are the same size if and only if there is a bijection f A gt B Proof A and B are nite if and only if for some m n E N there are bijec tions f Nm gt A and g M gt B by our definition of nite There are two things to show if A and B are the same size there is a bijection f A gt B and if there is a bijection from A to B A and B will be the same size Suppose that A and B are the same size This means that there are bijections f Nm gt A and g Nquot gt B noted above but with m A B 72 This implies that f and 9 have the same range so gf 1 will be a bijection from A to B the inverse of a bijection is a bijection so f 1 is a bijection from A to Nquot and the composition of two bijections is a bijection so gf 1 is a bijection from A to B Suppose that there is a bijection h from A to B For some m n E N there are bijections f 21 gt A and g Nquot gt B because A and B are supposed to be finite sets Now observe that the composition g lh f is a bijection and so an injection from Nm to Nquot By the pigeonhole principle we have m g 71 and 71 g m so m 71 by Axiom 10 This result suggests a more general de nition of what it means for two sets to be the same size De nition We that two sets A and B nite or in nite are the same size just in case there is a bijection f A gt B We abbreviate this A N B We know that this de nition the right thing if A and B are nite Suppose A to be nite and B to be any set with A N B By the de nition of nite there is f Nquot gt A for some natural number 71 and by the de nition of being the same size there is a bijection 9 between A and B Now observe that the composition gf is a bijection from Nquot to A establishing that B is nite and in fact the same size A in the sense de ned above Further we need the relation to be re exive symmetric and transitive re exive A A is true for any set A the identity function on A is a bijection from A to A symmetric If A N B there is a bijection from A to B whose inverse is a bijection from B to A so B N A transitive If A N B and B N C then there is a bijection f A gt B and a bijection g B gt C and we see that the composition gf is a bijection from A to C so A N C is true Clearly if N failed to have any of these properties it would not make sense to translate it as is the same size as Notice also that a set A is nite i 39 there is 72 such that M N A by the de nitions of nite and N Now we prove another common sense Theorem Any subset of a nite set is nite Proof Suppose that A g B and B is nite Thus there is a natural number 71 B such that B N Nquot Fix a bijection g from B to The set C 9m m E A is a subset of Nquot with the additional property that C N A To show that A is nite it is suf cient to show that C is nite and to show that C is nite it is suf cient to show that any subset of Nquot is nite for any 71 E N We prove this by induction on 71 The basis step is to show that any subset of is nite it has only two subsets and 1 both of which are obviously nite 2 Suppose ind hyp that any subset of is nite we need to show that any subset of M is nite Let D be a subset of 1 Either k 1 E D or not If not D g Nk is nite by inductive hypothesis If 61 E D then D k1 is a subset ofAk and so nite Let g be a bijection from some Nm to D k 1 we de ne a bijection 9 from Nm1 to D by de ning 9 gi for ig m and gm 1 16 1 This completes the proof by induction that any subset of any Nquot is nite which we have already seen implies that any subset of a nite set is nite I gave my own proof of the theorem that N is in nite Theorem N is an in nite set Proof We suppose that N is nite and deduce a contradiction IfN is nite this means that there is 72 E N such that Nquot N N Let f be a bijection from Nquot to N Consider the set A i ENquot fa ENn1 Clearly A g Nquot so A is nite by a previously proved theorem Thus there is a bijection g from Nm to A for some natural number m There is an injection part of 1quot from A into Nquot so m g 71 by the pigeonhole principle But there is also a bijection from Nm to M because there is the bijection g from Nm to A and a bijection part of f from A to Nu which requires m 71 1 and implies the impossible 71 1 lt 71 by substitution of equals for equals There certainly more in my lectures these notes capture ideas which are not in the book or not in exactly this form Please do not hesitate to ask me questions if you think something here is wrong I m very sleepy I write this and you might earn a special homework point A Step by Step Proof Dr Holmes January 28 2004 Theorem nb2 a22abb2 Comments Before this theorem can even be understood in the context of sections 41 2a it is necessary to notice that some de nitions are needed It s harder to notice this because the material is so familiar Usually we will keep things somewhat more informal De nition 2 11 De nition For any natural number 7 de ne n2 as 7m Definition 1 b c will be de ned as a b 0 abc will be de ned as 1bc Proof 11 b2 11 ba b by de nition of 72 abaabb by distributivity of multiplication over addition aabbab by commutativity of multiplication twice an ab ba bb 1 by distributivity of multiplication over addition twice 111 ab ba bb by associativity of addition 111 111 ba bb by associativity of addition 111 111 ab bb by commutativity of multiplication 111 1ab 1ab bb by the identity property of multiplication 1a 11ab bb by distributivity of multiplication over addition 111 2ab bb by de nition of 2 a2 2ab b2 by de nition of 712 a2 2111 b2 by de nitions of a b c and abc Notice that we are being extremely careful here also notice that being extremely careful takes up time and space We will not normally nit pick to this extent l0 Additional notes for Feb 17th Dr Holmes February 17 2004 The additional remarks for today concern the proof of the pigeonhole principle My version of this proof is very similar to the author s version in section 62 but there s a difference in the we construct the bijection used in the induction step De nition We define M for each natural number 71 the set m E N m g 71 For example 1 is the set 1 2 De nition We that the set A has 71 elements if and only if there is a bijection from Nquot to A Notice that if f is a bijection from Nquot to A then f 1 is a bijection from A to Nquot and if g is a bijection from A to Nquot then f 1 is a bijection from Nquot to A it doesn t really matter which we suppose that the bijection goes Notice that this definition actually corresponds exactly to the that we count small finite sets using numbers We digressed to discuss the usual formal set theoretical definition of the natural numbers This is motivated by an alternative method of counting which is possible if we have 0 a natural number A has 71 members if and only if there is a bijection between A and the set 0 71 1 the set of all nonnegative integers less than 71 We can take this farther we can de ne the natural number 71 the set of all natural numbers less than 71 This might seem to be circular but it isn t it is merely recursive 0 is de ned the set of all nonnegative integers less than 0 which is the empty set 1 is defined 0 or equivalently W the set whose only element is the empty set for some reason students frequently confuse and m these sets are quite different the first one has no elements and the second has one element for example 2 is de ned 01 which is m by the rst two de nitions In this way each natural number can successfully be identi ed a set You are not responsible for this de nition I mention it an example of a process you will see in mathematical foundations which is the effort to code all mathematical objects sets Another example of this process is the de nition of the ordered pair 16 the set One should not believe that this de nition of the natural numbers explains what the natural numbers really are in fact there are other codings of the natural numbers sets which have been used We now return to stuff you are responsible for Theorem Pigeonhole Principle For any natural numbers 71 and m if there is an injection from the set Nquot to the set 1 then 72 g m Proof of Pigeonhole Principle This statement is obviously true on a common sense understanding of what it Proving it is a little tricky It is proved by induction The statement we prove by induction is V71Pn where 137 abbreviates for all m if there is an injection from the set Nquot to the set 1 then 72 g m Notice how I took a statement with two quanti ers over the natural numbers and de ned 137 by peeling off one of the quanti ers The role of the two variables m and 72 in the theorem is not symmetrical and the other approach to setting up the induction would give a rather different proof if it were practical at all I haven t tried it Basis step for all m if there is an injection from the set M to the set 1 then 1 g m This is valid because 1 g m is true no matter what injections there may be Induction step for all natural numbers k if it is true that for all m if there is an injection from the set M to the set 1 then k g m then it is true that for all m if there is an injection from the set MM to the set 1 then k 1 3 m Admittedly the induction step is rather hard to read It is probably easier to read in logical notation We assume for all m if there is an injection from the set M to the set Nm then 16 3 7m this is the inductive hypothesis Our goal is to prove using ind hyp that for all m if there is an injection from the set MM to the set 1 then k 1 g m Let m be an arbitrary natural number Suppose that there is an injection from the set MM to the set Nm call it f Now our goal is to prove that k 1 g m Our strategy is follows we prove that if there is a bijection f from the set MM to the set 1 there must be a bijection J from the set M to the set Nm1 If we show this it will follow by the inductive hypothesis that k g m 1 from which it will follow by standard properties of inequalities that k 1 g m which is our goal First we need to show that m gt 1 so that m 1 will make sense If there is an injection h from M which has at least the elements 1 and k 1 to Nm then there must be distinct elements h1 and hk 1 of Nm distinct because h is an injection so m 1 because there are not two distinct elements of M We know that a natural number not equal to 1 must be greater than 1 There are two different you have been shown to define a bijection f from the set Nk to the set Nm1 given a bijection f from the set MM to the set 1 If f doesn t map any value i 3 k to m then it is to get J from f just omit the value of f at k 1 and you are done you now have a map with domain 1 instead of M whose range is restricted to Nm1 it is to see that it is still an injection If f maps some element i g k to m then we appear to have a problem But it isn t a bad problem Notice that fk 1 lt m because f is an injection we can t map two different numbers to m This means that we can define fj as fj for allj i and define fi fk 1 This will still be an injection the values of fj certainly can t cause any trouble and the value fk 1 assigned to fi has to be different from all values fj fj forj i because f is an injection and so would not map k 1 to the same value any j This shows that there is a bijection from the set M to the set Nm1 if there is a bijection from the set MM to the set 1 and we have already seen that this is enough to prove the theorem Thus far the proof given is the same in the book My alternative de nition of f went follows the idea is to remove the arrow from k 1 to fk 1 then reduce each of the range values greater than fk 1 by one this will produce a map from the set Nk to the set Nm1 desired The formal de nition is fa if r lt fk 1 fi fa 1 if r gt fk 1 for each i g k The case fi fk 1 can t happen because f is an injection It is also fairly to see that this must be an injection This de nition of f can be used in exactly the same the other to complete the proof The Pigeonhole Principle is remarkably powerful for such an obvious statement We will use it initially to show that the number of elements in a nite set is a wellde ned notion Counting Theorem Let A be a set If A has m elements and A has 72 elements then m 72 Proof Suppose A has m elements and A has 72 elements By de nition of having a number of elements we are given a bijection f NW gt A and a bijection g M gt A We have proved that compositions of injections are injections and com positions of surjections are surjections and from this it follows directly that compositions of bijections are bijections Notice that f 1 is a bijection from A to Nm and 9 1 is a bijection from A to Nquot The composition g lf will be a bijection from Nm to Nquot By the Pigeonhole Principle the existence of this bijection implies m g 71 The composition f 1 g the inverse of 9 1 will be a bijection from Nquot to Nm By the Pigeonhole Principle the existence of this bijection implies 71 g m If m g 71 and 71 g m then m 71 which is what we wanted to show This Theorem allows us to make the following De nition For any set A we de ne A the cardinality or size of A the unique natural number 71 if there is one such that A has 71 elements The theorem allows us to exclude the nasty possibility that there might be more than one number 71 which could be taken to be A 0 In this document there are two outlines of to prove that multiplica tion of our de ned integers is independent of choice of representatives The problem de nitely too hard without an extensive hint First proof De ne m n R q m q 72 p for all natural numbers m mp 1 Assume m 71 m n and pq p q Show that 7npnqmq up R m p n q m q n p m n n m and p q p 1 by our hypotheses mp nq m q up mq up m p n q is what we want to show mp nq m q n p n p m q m p n q mq up m p n q n p m q m p n q is equivalent cancellation property of addition I added n pm qm p n q to both sides mp nq m q n p n p m q m p n q by algebra m n p 71 m q m q p n p q by hypotheses if you look at this step you will see why I added the weird thing I added to both sides it makes it possible to apply the assumptions 71 m p n mq p qm q pn by algebra mq up m p n q m p n q m q n p which is what we want Second proof This is more natural there is less sense of having pulled a rabbit out of a hat but it requires more work It also has the unfortunate feature of breaking into cases Lemma If m 71 m n then either m m and 71 71 or there is a k such that either m mHc and n 71 k or m m k and 72 n k Proof If m m then m n 71 m so 72 m 71 m so 72 72 If m gt m then m mk and mn m k 71 so 71 k m n m so 71 k n The proof that if m gt m that m m k and 72 n k goes in exactly the same We can assume that either m 72 m n or m k 72 k m 71 because we can stipulate that the primed letters are larger without loss of generality and similarly either q p q or p q p 7quot q 7quot Really there are just three cases to consider 1 both of m m and p p there is nothing to show in this case m 71 m n and pq p q It is to see that if we drop all primes the two products are the same 2 one of m m and p p is true without loss of generality we can assume m m 72 n and p p k 1 q k and show mp nq m q n p mq up m p n q by showing mpnqm q n p mpnqmqk npk mp nqmqmknpnk mqnpmpknqk mqnpm p n q 3 both of m m and p p are false so we can assume m mHc n nkp prq qr and show mp nq m q n p mq up m p n q mp nq m q n p by facts about primed letters mp nq m kq 7quot 71 kp r by algebra mpnqmqmrkqkrnpnrkpkr by algebra regroup to swap terms with p and q mqnpmpmrkpkrnqnrkqkr by algebra reversing the distribution step above mq up m 7quot 71 kq r by facts about primed letters mq up m p n q This proof is somewhat more natural This not a good homework problem without some kind of major hint about how to proceed Tips for Writing Proofs Dr Holmes February 13 2004 Always be careful to distinguish between statements you want to prove goals and statements you know are true or can assume are true in the current part of your proof hypotheses v premises or assumptions 7 these words all mean the same thing but I might use any of them so I m listing all of them The logical form of a sentence whether it is a goal or an assumptiom can give you guidance as to what to do next So it39s a good idea to work on recognizing the logical forms of statements Sometimes it is necessary to paraphrase an English sentence to make its logical form more obvious before you can apply these guidelines 1 Conjunction Sentences in and whether hypotheses or goals are refreshingly simple to deal with To prove P and Q prove P then prove Q just break it apart If you can assume P and Q you can assume P and you can assume Q 2 Implication Always carefully distinguish between If P then Q or equivalently P implies Q Q if P and other variants and P and Q these are totally different but students seem to confuse them Also don t confuse If P then Q with either If Q then P its con verse or If P then Q its inverse The converse and the inverse are equivalent to each other but not to the original implication Of course the contrapositive If Q then P is equivalent to the original implication To prove a sentence of the form If P then Q the strategy is to add P as a new assumptiom and show that Q can be proved with this new assumption if your goal is If P then Q add P as an assumption and your new goal is If you don t like the assumption of P think of it this way our goal is to prove If P then Q Either P is false or it is true If P is false If P then Q is true look at the truth table for gt so we have nothing to do If P is true we need Q to be true so we need to show that we can prove Q if we assume P and we don t need to worry about the easy case where P is false An assumption of the form If P then Q can be used as follows suppose that we have assumed or proved P and P gt Q we can conclude Q This is called the rule of modus ponens in traditional logic Remember that P gt Q is equivalent to Q gt P an implication is equivalent to its contrapositive This means that we can also prove If P then Q by assuming Q and using this assumption to deduce P It also means that if we have proved or assumed P gt Q and Q we can conclude P this is the classical logical rule called modus 130119715 3 Disj unction To prove a statement of the form P or Q show that if P is false Q must be true or show that if Q is false P must be true Of course it is also suf cient to show just that P is true or just that Q is true To use a hypothesis of the form P or Q use the method of proof by cases if we know P or Q and we can show that assuming P leads to a conclusion R and we can show that assuming Q leads to the same conclusion R we can draw the conclusion R It is useful to remember that for any statement P we have P or not P the law of excluded middle Statements of this kind are often useful as the basis for a proof by cases 4 Negation To prove P assume P and show that a contradiction follows Since any statement P is equivalent to P the law of double negation this means that we can prove any statement by the method of proof by contradiction to prove P assume P and show that a contradiction follows Assumptions or theorems of the form P can be used in two ways if you have proved or assumed both P and P you have arrived at a contradiction In additiom if you have a premise PV Q and you show P you can conclude Q this has already been mentioned above under disjunction 5 Biconditional To prove P if and only if Q prove If P then Q then prove If Q then P Since either or both of these can be replaced by its contrapositive there are four different ways to prove a biconditional 7 but notice that in any case the proof of a biconditional has two parts one for each direction of implication 6 Universal Quanti er To prove any statement of the form for any x E A Par start out by saying Let x be an arbitary element of A then prove Pay If you have a theorem or assumption for any 10 E A Pay and i is any element of A at all you can conclude Pt Pi is the result of replacing all references to w in the possibly quite complicated sentence Pay with references to t 7 Existential Quanti er To prove any statement of the form there is an x E A such that Pro v prove Pi for some particular object i E A Pi is again the result of replacing all references to w in the possibly quite complicated sentence Pay with references to i If you have a theorem or assumption Pt with t E A you can draw the conclusion there is L39 E A such that Pay 8 De nitions If a de ned concept appears in a goal you are trying to prove or a theorem or assumption you are trying to use and the statements logical form doesn t give you any help you can use the de nition to expand the statement You can see all these ideas in full symbolic form in the section on natural deduction in my current M387 notes This is not to say I recommend trying to look them up there Updated versions of this document Will contain sample proofs with dis cussion of the application of these rules the proof that a function with an inverse is a bijection would be a good example and perhaps also the proofs that the compositions of injections are injections and the compositions of bijections are bijections Additional Math 187 Notes for Jan 26 Dr Holmes January 27 2004 These additional notes include some discussion of de nitions and proofs discussed in the 42 lecture especially those which do not actually occur in the book De nition For natural numbers m 71 we define m lt 71 for some natural number 7quot m r 72 It is an immediate consequence of the com mutative law of addition that it is also equivalent to for some natural number 7quot 7quot m 71 De nition For natural numbers m 71 we define m gt 71 71 lt m de ne m g 71 m lt TLVTR 71 and define m 2 71 m gt 71 Vm 71 Axiom 10 Let m and 72 be natural numbers Then exactly one of the following statements is true m lt 71m 7171 lt m or equivalently m lt 71 m 71 m gt 71 We use Axiom 10 to prove the cancellation property of addition Theorem For any natural numbers m 71 7quot if m 7quot 71 7quot then m 71 Proof We prove the contrapositive if m 35 71 then m 7quot 71 7quot Assume m 71 By Axiom 10 either m lt 71 or 71 lt m since the third case m 71 is ruled out We argue by cases In Case 1 we assume m lt 71 There is a natural number a such that m a 72 by the de nition of lt Thus we have n7quot 7R3 7quot by substitution of equals for equals n7quotmatr by the associative property of addition n7quotmrat by the commutative property of addition n7quotmrat by the associative property of addition m 7quot lt 71 7quot by the de nition of lt and nally m 7quot 71 7quot by axiom 10 we cannot have both m 7quot lt 71 7quot and m 7quot 71 7quot true The proof of Case 2 looks exactly the same except that m and n are swapped In Case 2 we assume 7 lt m There is a natural number y such that 71 3 m by the de nition of lt Thus we have mHquot nyr by substitution of equals for equals mrnyr by the associative property of addition mrnry by the commutative property of addition mrnry by the associative property of addition 71 7quot lt m 7quot by the de nition of lt and nally 7 7quot m 7quot by axiom 10 we cannot have both 71 7quot lt m 7quot and 71 7quot m 7quot true Since we are able to show that the desired conclusion follows in both cases the proof is complete We now de ne subtraction Since we are working with positive natural numbers we cannot expect subtraction always to be de ned Nonetheless we can de ne this operation and prove theorems about it De nition Let m and 71 be natural numbers We de ne m n the unique natural number a such that a n m if there is such a number So we have m n 71 m if m 71 is de ned Observation m 71 is de ned exactly when m gt 71 If m gt 71 there is an a such that CCTL m de nitions of lt and gt To show that a m n we need to show that there is only one such Suppose at 72 m and yn m Then we have citHI yHI things equal to the same thing are equal to each other and so a y by the cancellation property of addition just proved above So we have the following if a 72 m then a m 72 so m n 72 72 As an example of reasoning with subtraction we prove the distributive property of multiplication over subtraction Theorem Let 160 be natural numbers If i c is de ned then ac be is de ned and 16 c ab ac Proof Assume that b c is de ned b ccb by the de nition of subtraction ab cc ab by properties of equality ab cac ab by distributiVity of multiplication over addition and nally ab cab ac by the de nition of subtraction really by the observation that follows it Additional Math 187 Notes for Jan 26 Dr Holmes January 27 2004 These additional notes include some discussion of de nitions and proofs discussed in the 42 lecture especially those which do not actually occur in the book De nition For natural numbers m 71 we define m lt 71 for some natural number 7quot m r 72 It is an immediate consequence of the com mutative law of addition that it is also equivalent to for some natural number 7quot 7quot m 71 De nition For natural numbers m 71 we define m gt 71 71 lt m de ne m g 71 m lt TLVTR 71 and define m 2 71 m gt 71 Vm 71 Axiom 10 Let m and 72 be natural numbers Then exactly one of the following statements is true m lt 71m 7171 lt m or equivalently m lt 71 m 71 m gt 71 We use Axiom 10 to prove the cancellation property of addition Theorem For any natural numbers m 71 7quot if m 7quot 71 7quot then m 71 Proof We prove the contrapositive if m 35 71 then m 7quot 71 7quot Assume m 71 By Axiom 10 either m lt 71 or 71 lt m since the third case m 71 is ruled out We argue by cases In Case 1 we assume m lt 71 There is a natural number a such that m a 72 by the de nition of lt Thus we have n7quot 7R3 7quot by substitution of equals for equals n7quotmatr by the associative property of addition n7quotmrat by the commutative property of addition n7quotmrat by the associative property of addition m 7quot lt 71 7quot by the de nition of lt and nally m 7quot 71 7quot by axiom 10 we cannot have both m 7quot lt 71 7quot and m 7quot 71 7quot true The proof of Case 2 looks exactly the same except that m and n are swapped In Case 2 we assume 7 lt m There is a natural number y such that 71 3 m by the de nition of lt Thus we have mHquot nyr by substitution of equals for equals mrnyr by the associative property of addition mrnry by the commutative property of addition mrnry by the associative property of addition 71 7quot lt m 7quot by the de nition of lt and nally 7 7quot m 7quot by axiom 10 we cannot have both 71 7quot lt m 7quot and 71 7quot m 7quot true Since we are able to show that the desired conclusion follows in both cases the proof is complete We now de ne subtraction Since we are working with positive natural numbers we cannot expect subtraction always to be de ned Nonetheless we can de ne this operation and prove theorems about it De nition Let m and 71 be natural numbers We de ne m n the unique natural number a such that a n m if there is such a number So we have m n 71 m if m 71 is de ned Observation m 71 is de ned exactly when m gt 71 If m gt 71 there is an a such that CCTL m de nitions of lt and gt To show that a m n we need to show that there is only one such Suppose at 72 m and yn m Then we have citHI yHI things equal to the same thing are equal to each other and so a y by the cancellation property of addition just proved above So we have the following if a 72 m then a m 72 so m n 72 72 As an example of reasoning with subtraction we prove the distributive property of multiplication over subtraction Theorem Let 160 be natural numbers If i c is de ned then ac be is de ned and 16 c ab ac Proof Assume that b c is de ned b ccb by the de nition of subtraction ab cc ab by properties of equality ab cac ab by distributiVity of multiplication over addition and nally ab cab ac by the de nition of subtraction really by the observation that follows it

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.