Proofs and Plagiarism

Notes on the homework

Plagiarism

If you go to the library and find a theorem and copy it, it is research. If you do not cite your source, it is plagiarism. Reread your student handbooks. Plagiarism can get you expelled.

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.

Proofs

If you are not sure how to prove something, try the following:
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 [fill in your negated hypothesis]. Therefore,....'' Then fill in the blank space.

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.