Problem 2 (13 pts.)

Consider the following claim.

Claim. For any sets S and T,

(SxT)n (Tx S)-(Sx S) = 0.

(a) (11 pts.) Use a proof by contradiction to prove the claim.

To get full points you must use a mixture of formal notation and word explanations (e.g. the

"column" format). Each step of your proof should have an explanation as to how/why you

could make that logical step. When in doubt, more detail is better than less.

Grading Notes. While a detailed rubric cannot be provided in advance as it gives away

solution details, the following is a general idea of how points are distributed for this problem.

We give partial credit where we can.

(9) Correctness. If your proof is not correct, this is where you'll get docked.

(5) Regardless of how you formulate your proof, somewhere you'll need certain facts

without which the proof wouldn't work. E.g. if it weren't true that the sum of two

integers is integer, would your proof fail? If so, then that is a fact I need to see

stated somewhere.

(1) The order of these facts must make sense, so that you're not inferring something

before you have all the facts to infer it. E.g. you cannot use the fact that the sum

of two integers is integer if you don't already know that you have two integers to

begin with.

(3) You also must use a proof by contradiction, which clearly states it is a proof by

contradiction, states what the contradictory assumption is, finds a contradiction,

and clearly states what and where that contradiction is.

(2) Communication. We need to see a mix of notation and intuition, preferably in the

"column" format with the notation on the left, and the reasons on the right. If you

skip too many steps at once, or we cannot follow your proof, or if your solution is overly

wordy or confusing, this is where you'll get docked.

(b) (2 pts.) Is it possible to prove this claim by contrapositive? If so, what would the statement of

the claim be (that you could then apply the contrapositive to)? If not, give a brief explanation

why it cannot be done.

Grading Notes. This problem is meant for you to think about whether you can modify

your proof to be of a different form, and explaining your answer.