Search for question
Question

Problem 1 (23 pts.)

Consider the following claim:

Claim. {21n: n € Z} U {14n: n € Z} c{7n:n €Z}.

(a) (3 pts.) Write the claim as an (equivalent) if-then statement.

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.

(3) Correctness. Regardless of how you formulate your proof, you will need to have an

if-then statement that is equivalent to the original.

(b) (11 pts.) Give a direct proof by cases that the claim is true. As a hint, you might want

to prove the if-then statement you constructed in (a).

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.

If you can at least get part-way, we give partial credit where we can.

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

(2) Regardless of how you formulate your proof, you will need clearly labeled exhaustive

cases.

(6) 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 makes 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.

The order of how you use these does not have to exactly match those in the sample

solutions, but there are orders that will not work and you will lose points if, for example,

you use "the difference of ints is int" before you use "the product of ints is int". If you

combine some steps (such as "the difference and product of ints is int" or "the product

of two non-zero ints is a non-zero int") that is fine. Just don't combine all (see below).

(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.

(c) (3 pts.) State (but do not prove) the contrapositive of your statement from part (a).

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.

(3) Correctness. You have to have the contrapositive statement of whatever if-then state-

ment you wrote in part (a).

(d) (3 pts.) State (but do not prove) the converse of your statement from part (a).

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.

(3) Correctness. Regardless of how you formulate your proof, you will need to have an

if-then statement that is the contrapositive of the original.

(e) (3 pts.) Give a disproof by counter-example of the converse from part (d). (That is, show

that the converse is not true by providing an example that demonstrates it is not true.)

Remember that any disproof by counter-example not only provides the counter-example, but

also an explanation as to why it is a counter-example.

Grading Notes. Note that this problem gives you practice disproving a statement by

counter-example, which requires clearly stating a counter-example, and then showing why it

is a counter-example.