Problem 1

Work the following problem, write it up carefully (on a separate sheet of paper from the homework), and turn it in on Monday, January 30:

Problem: Let x and y be integers. Prove that x + y is even iff both x and y are even or both x and y are odd.

Proof: We will use a two-part iff.

 

(=>)

We need to show P => Q or R, where P is "x + y is even," 
Q is "both x and y are even," and R is "both x and y are odd."
The contrapositive is ~(Q or R) => ~P.
This is equivalent to ~Q and ~R => ~P.

Then, ~Q is one of x or y is odd, or they are both even.
Also, ~R is one of x or y is even, or they are both odd.
Thus, ~Q and ~R is one of x or y is even. 
Thus, if x is even and y is odd, let x = 2j and y = 2k + 1, for
 some integers j and k.
 Then, x + y = 2j + 2k + 1 = 2(j+k) + 1 = 2n + 1, where n = j+k.
 Thus, x + y is odd, or ~P.

Similarly, if x is odd and y is even, x + y is odd, or ~P. 

Since the contrapositive of P => Q or R is true, this conditional is
true. 1/2 QED


(<=) 

Here, need to show Q or R => P, with Q, R, and P as above in (=>).
Q or R => P
  <=> ~(Q or R) or P
 <=> (~Q and ~R) or P
 <=> (~Q or P) and (~R or P)
 <=> (Q => P) and (R => P).

To show Q => P, assume x and y are even.
 Then x = 2j, and y = 2k, for some integers j and k.
 Thus, x + y = 2j + 2k = 2(j+k) = 2m.
 Thus, x + y is even.

To show R => P, assume x and y are odd.
 Then x = 2j +1, and y = 2k + 1, for some integers j and k.
 Thus, x + y = 2j + 1 + 2k + 1 = 2j + 2k + 2 = 2(j+k+1) = 2m.
 Thus, x + y is even.

This proves Q or R => P, and thus by a two-part proof, Q or R <=> P, 
or x + y is even iff both x and y are even or both x and y are odd. QED

Notes:

Some variations are possible, and it is possible to prove this statement with cases, but we need to be very careful with the different cases.

Some common mathematical errors:

• Assuming facts that are essentially what was asked to be proved. For example, assuming that x + y is even and thus = 2j + 2k, so x = 2j and y = 2k, both even. As I indicated on some papers, 2+3 = 4+1, but this does not mean that 2=4 and 3=1.
• Choice of less appropriate method. For example, the second part is a straightforward direct proof, which is complicated by using contraposition.
• Assuming that x is odd means that x = 2k + 1, or that x is even means that x = 2j, for *any* integers k and j, instead of for *some* integers k and j. These statements are very different.
• Saying x even implies x=2k (or similarly y odd implies y=2k+1) without saying that k is an integer.
• Saying that x and y are even so they equal 2k and 2m, respectively, for some k and m but then saying that x+y=2(k+m) implies that x+y is even without noting that k+m is an integer.
  
• There were considerable problems with cases. Sometimes it was not explained what all of the cases are. Sometimes too many special cases were considered, instead of just considering a few general cases. Sometimes cases were considered that could have been ruled out.
• Assuming the very special case that x = y.
• Making logical claims without support.
• Claiming that x = 2j and y = 2k means that xy = 4jk.
• Concluding that if a number is divisible by 2 it is even. This is actually a small theorem, and without it we should just say that x=2k, some k, and conclude that x is even by definition.
• Concluding that ~(x odd and y odd) is equivalent to x even and y even.
• Proving only => or <= and then concluding <=>.
• Concluding that x/2 is an integer, when it is not clear that x is even.
• Beginning with an unspecified collection of integers (including x and j perhaps) and later saying that x = 2j. Actually, j should not appear until we produce "some j" because we know x is odd.
• Spotty use of quantifiers. Sometimes their use was unnecessary, and other times it was very important and not done.
• Trying to use division or making blanket statements about 1/2 when our properties are in terms of addition and multipilcation.  Subtraction and division are addition and multiplication by inverses.
• Using "similarly" or "wihtout loss of generality" without justifying why the case is similar.
• Forgetting to use "similarly" or "without loss of generality" and just assuming x is odd and y is even or vice versa, forgetting the other case.
  
• Drawing a conclusion that is not closely related to the previous step -- taking a flying leap in logic.

Some common expositional errors:

• Failing to state the problem up front, or failing to state what is to be proved.
• The proof method not stated up front. This made interpretation of the steps more difficult. It sometimes made the interpretation so difficult that I stopped trying.
• The argument not clearly laid out and thus hard to follow, even if correct.
• Stating that the proof directions are cases within one large proof and getting a multitude of confusing cases.
  
• Complete and correct sentences not always used.
• Lack of conciseness, with some of the arguments way too long.
• Using contraposition without saying so.
• Saying that since the statement is a biconditional, we *need* to use a two-part proof. This is an option and not a necessity.
• Letters such as Q, R, and S used but not identified in the statement.
• Not using "similarly" in situations that are essentially the same as a previous one.
• Using truth tables instead of deriving equivalences using our tools.
• Trying to make what might be called a table layout of a proof instead of a readable and flowing step-by-step solution.
  
• Using "=" for "is" in a sentence.