Proof writing
First is a list of things one must do for proofs written for our
course. The second set of items are not absolute requirements,
but following them will lead to better written proofs. Even though
these are intended for students in my upper-level classes, there is
a large overlap with proof-writing rules put together by others
such as these,
although they are for a slightly different purpose.
Things you must do
-
Quantifiers
-
When introducing a variable, always give its quantifier.
-
Quantifiers can occur before or immediately after the use
of the variable (in my classes; for other professors, your
milage may vary), such as
\[ \text{for all } x\in A\]
which puts the quantifier before, or
\[ n=2k \text{ for some } k\in\Z\]
which puts it after.
-
"for" by itself is not a quantifier. It might mean "for
all" or "for some", which does not distinguish the two basic
quantifiers
-
The introduced variable should almost always come with a
set: "for some \( x\in A\)" instead of just "for some \(x\)".
The main exception is in some set theory proofs (in MAT 300)
where one really wants "for all sets \(x\)", but there is not
set of all sets.
-
Reasons
-
If something does not follow from the preceding statement,
it deserves a reason. For example, it may pull in a hypothesis
from the statement of the proposition (or problem), use a fact
asserted several lines before, or be invoking a theorem.
-
If you invoking a named theorem, always cite it.
-
On homework, you can cite theorems by number in the book.
On exams, you can just say "from a theorem from the course" for
an unnamed theorem.
-
When invoking a theorem, be sure you have noted each of the
hypotheses in your situation. In a book or journal paper, some
may be left as obvious to the reader. But, in a homework or
exam, you are both applying the theorem and showing that you
know what it says.
-
Flow of logic
-
Individual assertions need to be connected in a way which
shows how they are related logically. If there are two
statements \(P\) followed by \(Q\), are you saying \(P\) implies
\(Q\), that the preceeding implies both are true (so \(P\) and
\(Q\), that only one
of them may be true (\(P\) or \(Q\))?
-
The implications can be indicated by words in a sentence,
or sometimes by symbols. A common error is to forget to connect
a series of equations or inequalities. For example, one would
be marked off for:
\[ 0_1+0_2=0_1\]
\[ 0_1+0_2=0_2\]
\[ 0_1=0_2\]
It should be
\[ 0_1+0_2=0_1 \text{ and }
0_1+0_2=0_2\]
which implies that
\[ 0_1=0_2\]
-
A long running equation (or inequality) is a different
story. The parts of
\[
\begin{align}
0_1 &= 0_1+0_2 \\
&= 0_2
\end{align}
\]
are already connected.
-
When concatenating assertions, the reader still reads
left to right, so that is how the logic should work. Suppose
we want to show that \(n\) is an integer, we know \(k\) is an
integer, and \(n=2k\) (and the product of integers is an
integer). The sequence
\[ 2k = n \in \Z\]
has parts \(2k=n\) (ok) and \(n\in\Z\). The second part is
what you are trying to prove; how can it be asserted. The
right way to order the parts is
\[ n = 2k \in \Z\]
Now the reader can see \(n=2k\) (given above), and
\(2k\in\Z\) (product of integers is an integer), so they can
understand each step. Then we can simplify this to deduce
\(n\in\Z\).
-
Assuming the conclusion.
-
Of course, you can never assume the conclusion in a
proof, and deduce things from there. It is a fatal flaw.
-
It is good to tell the reader what you are doing, so
be explicit when saying you will show something,
so that it isn't confused with something you claim has
already been proven.
Things you should do
-
Avoid logic symbols for "and" (\(\wedge\)), "or"
(\(\vee\)), and "not" (a variety of symbols). These are ok if
the subject matter is formal logic (e.g., the beginning of MAT
300), but nowhere else.
-
You can use logic symbols for "implies" (\(\implies\)) and
"if and only if" (\(\iff\)). (Other professors may feel
differently in their courses.)
-
Do not start a sentence with a symbol. This is standard
math style. In some cases, you can avoid it by reminding the
reader what the symbol stands for. So, instead of
\[ f \text{ is irreducible} \]
use
\[ \text{The polynomial } f \text{ is irreducible}\]
|