I encourage you to work together. However, if I find problem sets that are identical, and that do not cite the other student's help, that is also plagiarism. If you hand in one assignment for several students, I will divide the grade equally among those students.

Therefore, once you have discussed the problems, write the solutions up separately. If someone copies your assignment, you are equally responsible.

Write down what you are assuming (the hypothesis), then leave some blank space, then write down what you are trying to prove (the conclusion). Then try to connect the two, logically.

If that doesn't work, try writing, ``Suppose not." Then write down what that means (i.e., the negation of the conclusion). Leave some blank space, and write down the negation of the hypothesis. (It should be the same conclusion as in the previous attempt!) On the line above the conclusion, write down, ``This contradicts the assumption that

Think about what proof method you want to use. Can you simply write down the definitions of everything in the hypothesis, and everything in the conclusion, and get from one to the other in a straight line? Can you prove it by contradiction? Can you use induction? If you use induction, figure out what you are inducting on --- is it a number, or a definition (induction by cases)?

Write down the relevant definitions, and any related results that
might be relevant, on a piece of scrap paper. If you want to use
one of those results or definitions, be prepared to write something
like this: *``We know, by Thm 18.2 of the text, that if a set and
its compliment are r.e., then the set is recursive.''* (In other
words, state both the source of the result -- ``class notes'' is a valid
source -- and the result itself. If the result is a numbered theorem
from the text, it is not necessary to state the result, though it may
be helpful to you to write it down.)

When you have what you think might be a proof, do the following:

See whether you have used everything in the hypothesis. If not,
ask yourself whether you should have, or whether the result would
still hold without that piece of the hypothesis.

See whether you have introduced something (a variable, or additional
hypothesis) that isn't used in the proof. If so, remove it.

See whether you can justify each step. If not, you may need to write
more down.

See whether you have used *``Clearly,...''* or *``Obviously,...''*
or any similar words. If so, check whether they indicate a mistake,
or laziness. Fix the mistakes, and decide not to be lazy. Those words
should never appear in the final form of a proof.