------------------------------------------------------------------------ Subject: More theorems to try to prove ------------------------------------------------------------------------ Here are the proofs of the theorems that I posted for practice earlier this week. 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 sup 2 = 8k+1]] Proof: Suppose Odd(x) & show Ek[x sup 2 = 8k+1]. i.e., try to find k such that x sup 2 = 8k+1: x = 2y+1, for some y so, x sup 2 = (2y+1) sup 2 = 4(y sup 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 4(y sup 2) + 4y is of the form 8k! Now 4(y sup 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 (I think you proved that for an earlier HW; if not, you should try to prove it now!) i.e., y(y+1) = 2m, for some m. So: 4(y sup 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". ("mutatis mutandis" is Latin for "changing whatever needs to be changed") ------------------------------------------------------------------------