From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Wed Feb 27 10:14:10 2008 Date: Wed, 27 Feb 2008 10:13:50 -0500 From: "William J. Rapaport" Subject: 191: More theorems to try to prove To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: More theorems to try to prove ------------------------------------------------------------------------ Here are some more theorems to practice your proving strategies on. I will discuss some of them on Friday, and post answers to the others afterwards, to help you study. For each of these, first try to represent the proposition in FOPL. Then try to prove it. 1. If n+1 is an odd integer, then n+3 is an odd integer. 2. If x and y are odd integers, then 3x+2y is an odd integer. 3. n is odd iff 5n+3 is even 4. For all real numbers x and y, max(x,y) = (x + y + |x-y|)/2 5. The square of every odd integer is of the form 8k+1, where k is an integer. 6. Any 3 reals such that each is less than the sum of the other two are all positive. From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Wed Feb 27 11:38:04 2008 Date: Wed, 27 Feb 2008 11:35:35 -0500 From: "William J. Rapaport" Subject: Re: 191: More theorems to try to prove To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU A student writes: | Some of these odd/even questions could be trivialized by using different | definitions of odd and even - for instance, #1 could be solved easily by | saying that n is odd iff n = 1 (mod 2). Similarly, 2 could be trivialized | by saying that n is even iff 2 is one of its (prime) factors, then using the | lemma that an odd number plus an even number yields an odd number. Are | these options against the rules - do definitions need to be the same | throughout multiple problems? After all, the definition we have been using | has been that an even n is a multiple of 2, even though generally speaking, | the definition is that n is divisible by 2. Can I substitute definitions | like that when they are clearly equivalent? The answer in general is "yes", but keep in mind that the notions of "trivial" and "clearly" are often in the eye of the beholder. One person's trivial or clear truth is another's difficult theorem requiring proof. If you define "odd" as congruence to 1 mod 2, then you have to prove that odd numbers are successors of multiples of 2. Conversely, if you define "odd" as being 1 more than a multiple of 2, then you have to prove that odd numbers are congruent to 1 mod 2. You even note that you have to invoke a lemma, which, of course, would need to be proved. Logicians start with the absolute basics and build up from there (and you could that in several different ways). Mathematicians don't care where you start, as long as you don't argue in circles. For our purposes, I'm less concerned with which facts you use to prove other facts (unless you try arguing in a circle, of course) than I am with making sure that you understand the strategies needed to do the proof. So, as long as you make all of your assumptions crystal clear to the reader (so that the reader will be confident that you're not arguing in circles), then you can use whatever facts you want to prove things. From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Fri Feb 29 08:27:12 2008 Date: Fri, 29 Feb 2008 08:26:47 -0500 From: "William J. Rapaport" Subject: 191: More theorems to try to prove To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: More theorems to try to prove ------------------------------------------------------------------------ Here are the proofs of the theorems that I posted for practice on Wednesday. For each of these, first try to represent the proposition in FOPL. Then try to prove it. ------------------------------------------------------------------------ 1. If n+1 is an odd integer, then n+3 is an odd integer. Representation: Let the domain be Z = {x | x is an integer} Let Odd(x) = x is odd An[Odd(n+1) -> Odd(n+3)] Proof: Choose an arbitrary n in Z and show Odd(n+1) -> Odd(n+3). This is of the form P -> Q. Let's try direct proof: Suppose Odd(n+1) & show Odd(n+3). Replace "Odd" with (one of) its definition(s): Odd(n) =def Ek[n = 2k+1]. We are assuming Odd(n+1), so Ek[n+1 = 2k+1]. Existentially instantiate this to "k". Therefore, n+1 = 2k+1; so n=2k (call this equation 1). We need to show Odd(n+3), i.e., we need to show Ej[n+3= 2j+1]. I.e., we need to try to find some j such that n+3 = 2j+1: But n+3 = 2k + 3, substituting from equation 1. And 2k+3 = 2k + 2 + 1 = 2(k+1) + 1. Take j = k+1. QED. The above proof is a long-winded, verbose proof that a logician or computer might give. Here's a shorter, swifter version such as a mathematician might give: Choose an arbitrary n in Z and show Odd(n+1) -> Odd(n+3). Odd(n+1), so n+1 = 2k+1 for some k. Therefore, n = 2k. Therefore, n+3 = 2k + 3 = 2(k+1) +1, which shows that n+3 is odd. QED ------------------------------------------------------------------------ 2. If x and y are odd integers, then 3x+2y is an odd integer. Representation: Domain and predicate as above. AxAy[Odd(x) ^ Odd(y) -> Odd(3x+2y)] Proof (this one will be somewhere between a wordy logical proof and a sloppy mathematical proof): Suppose Odd(x). Suppose Odd(y). Show Odd(3x+2y): x = 2k+1, for some k y = 2j+1, for some j 3x+2y = 3(2k+1) + 2(2j+1) = 6k + 3 + 4j + 2 = 6k + 4j + 4 + 1 = 2(3k+2j+2) + 1, which is of the form 2x+1, hence odd. QED ------------------------------------------------------------------------ 3. n is odd iff 5n+3 is even Representation: As above, plus: Even(x) = x is even An[Odd(n) <-> Even(5n+3)] Proof: This is a biconditional; hence, we must show two things: (a) Odd(n) -> Even(5n+3) (b) Even(5n+3) -> Odd(n) proof of (a): Suppose Odd(n) & show Even(5n+3). n = 2k+1 for some k Show 5n+3 = 2j for some j (because Even(x) =def Ey[x=2y]) 5n+3 = 5(2k+1) + 3 = 10k + 5 + 3 = 2(5k+4), which is even. QED proof of (b): Let's start by trying a direct proof: Suppose Even(5n+3) & show Odd(n): 5n+3 = 2k for some k. so, n = (2k-3)/5. Whoa! (that's NOT a mathematical term :-) fractions are too hard to think about! So let's try an **indirect** proof! In fact, let's try a proof by contraposition: Suppose -Odd(n) & show -Even(5n+3). I.e., suppose Even(n) & show Odd(5n+3) (because Even(n) equiv -Odd(n)--I hope you know that!) n = 2k for some k So, 5n+3 = 5(2k)+3 = 10k + 2 + 1 = 2(5k+1) + 1, which is odd. QED QED. ------------------------------------------------------------------------ 4. For all real numbers x and y, max(x,y) = (x + y + |x-y|)/2 Representation: Domain = R AxAy[max(x,y) = (x + y + |x-y|)/2] Proof: Well, that representation didn't really help very much, did it? What to do? Well, whenever you talk about "max" (the maximum function), you're talking about < (or >). And when you do that, there are 3 possibilities for any 2 numbers x,y: x=y x>y xy. We know ahead of time that the answer should be x. max(x,y) = (x + y + |x-y|)/2 = (x + y + (x-y))/2 = (x + y + x - y)/2 = 2x/2 = x. Checks out again! Case (c): x Ek[x^2 = 8k+1]] Proof: Suppose Odd(x) & show Ek[x^2 = 8k+1]. i.e., try to find k such that x^2 = 8k+1: x = 2y+1, for some y so, x^2 = (2y+1)^2 = 4y^2 + 4y + 1. We have to show that this polynomial can be written in the form "8k+1" for some k. But that means that we only have to show that 4y^2 + 4y is of the form 8k! Now 4y^2 + 4y = 4y(y+1). Here's an interesting fact: y and y+1 are consecutive integers! (in fact, using our terminology from Peano's axioms, y+1 is y's successor). But that means that one of them (we don't know or care which) is odd and the other one is even. And **that** means that their product is even (you proved that for an earlier HW, remember? :-) i.e., y(y+1) = 2m, for some m. So: 4y^2 + 4y = 4y(y+1) = 4*2m, for some m But 4*2m = 8m. QED ------------------------------------------------------------------------ 6. Any 3 reals such that each is less than the sum of the other two are all positive. Representation: AxAyAz[((x < y+z) ^ (y < x+z) ^ (z < x+y)) -> ((x>0) ^ (y>0) ^ (z>0))] Proof: Let a,b,c be 3 reals that satisfy the antecedent. Show that they are all > 0. Because a < b+c and b < a+c, it follows that a < (a+c) + c = a + 2c I.e., a < a + 2c Subtracting a from both sides, we get 0 < 2c, which implies c>0. We can repeat this proof, changing whatever needs to be changed, two more times in order to derive a>0 and then to derive b>0. The formal mathematical way to say this is: "without loss of generality, it follows mutatis mutandis, that a,b>0". ------------------------------------------------------------------------