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