Back to resources,html#proof
Things to avoid in proofs
- Assuming what you want to prove.
- "Begging the question". See circular reasoning as well.
- This can be done by mistake: you might use a "well known" property B to prove property A, but the proof of B actually relies on knowing A is true.
- Note that it is sometimes ok to assume something similar but weaker than what you're trying to prove, for instance with proof by induction.
- Claiming that certain steps are obvious or simple facts, when they are actually just as difficult to prove as the main result.
- Technically in a proof one can rely on extremely complicated results, as long as they are properly described and cited. In an introductory course (like one where you learn about proof techniques) you should avoid doing this, unless you're relying on something that has already been proved during the course, or is basic enough to be considered prerequisite material.
- Making unjustified assumptions.
- Example: assuming that a set of numbers are integers, when the statement to be proved made no such restriction.
- In general, don't interpret problems in a way that is convenient to get a simple solution. For example, if I say "you have a deck of n cards", don't assume n=52 just because that's what a standard deck has.
- Using convenient interpretations that are too good to be true.
- Using results that are not applicable in the given situation.
- This is like "making assumptions" without knowing about it. It typically arises when one hasn't really understood what they're relying on, specifically when one hasn't understood what assumptions were made to obtain the result they're relying on. One such example is that students often state as a fact that hashing always takes constant time.
- Proof by example
- Also, "proof by picture". For instance, I ask you to prove a property about planar graphs. You draw a planar graph, assume it is general enough, show the property is true, and incorrectly conclude that the property holds in general.
- Make sure that your claims hold in general, not for specific situations.
- Not defining things.
- Not quite as bad, but still something to avoid: defining things and then not using them.
- Not labeling things.
- I often see sentences in proofs that refer to unlabeled things. For example, "therefore it is equal to 3", where "it" was actually last referred to about 10 lines and 5 sentences ago. This could be avoided by giving "it" a name, e.g., "therefore X is equal to 3" (where X was defined earlier).
It doesn't help to be more specific about "it" by saying "that object that I was talking about ten lines above".
- Not simplifying (see course notes on logic as well).
- For example, you have a case analysis proof with several cases, but many of them could have been eliminated. For example: "Case 1: If A is true and B is true, do X. Case 2: if A is true and B is not true, do X." (B was not needed).
- Obfuscation
- Basically, writing a whole lot without getting to the point, or purposely fitting in lengthy complicated math to hide the fact that a crucial step is missing somewhere.
- Proof by intimidation:
wiki,
Chewbacca defense, (xkcd 982)
- Here is another list
- See Rosen, chapter 1.7, p.89-90.
