------------------------------------------------------------------------
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")
------------------------------------------------------------------------