Axiomatics
Mathematical facts are abstract, even fairly simple ones. You can't know that
x² is non-negative for all real x by trying all real numbers x; there are too many of them. If you have tried a lot of them, you may have a strong conjecture (guess) that it's true, but that doesn't amount to knowing it's true.
Mathematical facts are known by having a proof for them, in a deductive system. A deductive system consists of a set of assumptions, usually called axioms or postulates, and a series of conclusions drawn from the axioms by proofs. A proof is a series of statements (mostly in English; or some other natural language) with reasons. A valid reason for a statement must be one of the axioms of the system, or a statement that has already been proved, or a rule of formal logic, or a combination of them, having the given statement as conclusion.
Because of the pairing of statements and reasons, the "two-column" style is preferred by some, as it makes it less likely that a reason will be omitted, leaving a gap in the right-hand column. In writing for a journal, the reader is expected to recognize gaps and know how to fill them in, so some reasons will be omitted anyway, and a paragraph style may be preferable.

Language
Notice that the principal language of our proofs is English, our native tongue, not mathematical formulas. We can sometimes use a mathematical formula as a convenient abbreviation for an English statement. It is shorter and sometimes clearer to say "x² is non-negative for all x" than "any number when multiplied by itself once gives a result greater than or equal to zero." But the proof as a whole must make sense in English, with those abbreviations taken into account. A teacher may present a proof in class, with just a few lines of formulas written on the board; but those formulas by themselves aren't the proof; the proof often includes much of the English language explanation given while the formulas were being written down. When we write a proof, we must be sure to include whatever English is required to make it complete.
The English we use in mathematical discussions differs somewhat from colloquial or even literary English, because it is necessary in mathematics to be very precise, while for other uses vagueness and ambiguity may be acceptable or even desirable. Ambiguous language in mathematics can easily lead one to totally false conclusions; so we have to learn precise meanings even for some of our English, and must be careful to use it accurately, in the technical sense, when we are doing mathematics. Besides the question of accuracy, there are some words whose meaning in mathematics or logic is not the same as in colloquial English.
Similarly, the logic used in mathematics is somewhat stricter than what the "person on the street" refers to when s/he says "it's just logical." Logic is based on certain principles of common sense, but developed very strictly; while everyday common sense includes kinds of reasoning by analogy and perceived probability that are not included in formal logic. These non-logical parts of common sense can be very helpful in deciding what things to try to prove, or what direction we think a proof should take, but they are sometimes misleading, because we don't, and can't, have enough experience with the abstract quantities of mathematics to make analogy and intuitive probability reliable. Therefore, in our final version of a proof, we must make sure all our reasoning is logical in the strict sense.

Why Proofs? Proofs are written for any of several reasons, basically to convince someone that a theorem is true in a particular deductive system, and to show why it is true. A mathematician may write a proof to find out whether a statement is true, to convince him/herself that a statement is true, or to communicate to others that it is true. A new proof may written to be clearer, or shorter, or cleverer, or do a better job of showing why the statement is true, or to show an unsuspected connection with other facts, even if one proof is already known. A mathematician will often omit reasons s/he feels the audience will have no trouble supplying.

A proof written by a student for a course has a special job. It doesn't have to convince the instructor that the theorem is true; s/he knows that very well. Instead, the proof is to show the student that the theorem is true, and why; and to show the instructor that the student understands all the reasons involved. Therefore, students must supply reasons that a textbook or article might leave for the reader to figure out.
Your job as a student writing a proof is to convince both you and the instructor beyond any reasonable doubt that you understand the structure of that proof and know all the reasons for the statements you make. If the instructor has to guess whether you understood or knew the right reason, you haven't done your job.
 

Formality & Understanding

Some basics of formal logic

(This idea is an abstraction from ordinary language: what's called a statement in English has many aspects, including its truth value; but many very useful English statements may be partially true and partially false, or neither true nor false. In doing mathematics, we have to try to make only statements that have a unique truth value. In particular, we have to try to avoid ambiguity; statements with more than one possible meaning.)

Compound statements
Logical statements can be combined to form new statements, by means of what are called "logical connectives" or "logical operators." The principal ones are ..AND.. (conjunction), ..OR.. (disjunction), IF..THEN.. (implication), and NOT.. (negation). That is, if p and q are statements, then so are
"p and q," "p or q," "if p then q," and "not p."
These are called compound statements, and p and q are their components or operands. The logical connectives are abstractions from the ordinary daily use of the same words.

In ordinary English, we sometimes use the word "or" to mean one or the other is true, but not both (exclusive or), while other times we allow it to include the possibility that both are true (inclusive or). In mathematics and logic, we don't want a word that has two possible meanings, so we always use the word "or" inclusively. If we want to express the exclusive meaning, we say "..or..and not both." So "or" in mathematics has the truth table
 

p	q	p or q
T	T	T
T	F	T
F	T	T
F	F	F

That is, a disjunction is true unless both of its components are false.

In ordinary English, we often give "if..then.." a lot of things to do besides its job as a logical connective for statements. Therefore, its logical use may seem incomplete or surprising. Study its truth table for surprises.
 

p	q	if p then q
T	T	T
T	F	F
F	T	T
F	F	T

That is, an implication is true unless its hypothesis is true and its conclusion false.
The ordinary English use often includes such ideas as "because" or "first...and later..." or "whenever", which are not part of the formal logical operator.

The compound "not p" has the opposite truth value from that of p.
 

p	not p
T	F
F	T

Ambiguity
Notice the parentheses. Without them, there's no way to tell whether "p and q or r", means the above "(p and q) or r", or "p and (q or r)," which has a different truth table, and therefore a different meaning. In "p and q or r," you can't tell whether the first operand of "or" is q or is "p and q".
In writing a compound, you have to be sure to include enough grouping that it is perfectly clear exactly what the operands of each connective are. Parentheses can be used, or underlines, or sometimes punctuation or wording.
For instance, the comma in "p and q, or r" would make it clear that the first operand of the "or" is "p and q", not q.
Truth tables can be used to show that expressions that use only "and" and expressions that use only "or" don't need grouping: that is, for instance "p and q and r" and "p and q and r" have the same truth table, and therefore they mean the same, so you don't have to say which one of them you mean. In just about all other cases of using multiple connectives, some kind of grouping is necessary to avoid ambiguity (to "disambiguate" the expression).

Despite our best efforts, we all (including authors of texts) write ambiguous statements sometimes. You must be prepared to notice when that happens, so that you can consider which of the possible meanings was probably intended. If you can't tell, ask.

For each of the following, tell if it is ambiguous. If it is, write all of its possible unambiguous versions, by adding grouping. For example,
"p or q and r" is ambiguous with meanings "(p or q) and r" and "p or (q and r)".
"p and not q" is unambiguous.
1. not p or q
2. p or not q
3. if p and q then r
4. if p then if q then r
5. if p then q and r
6. q and if p then r
 

Equivalent forms
There are some compounds that can always be substituted for each other. Some of those substitutions are extremely helpful in doing proofs, as one form may be much easier to work with than another. The ones you should be familiar with are the equivalents of "if..then.." and of "not..." If some of these equivalents don't seem natural to you, be sure to take the time to learn them, so you have them available when you need them.

A compound using if..then.. is called an implication. In the implication "if p then q," p is called the antecedent or hypothesis, and q is called the conclusion.
The contrapositive of the implication "if p then q" is the implication "if (not q) then (not p)." The contrapositive interchanges the hypothesis and conclusion and negates them both. An implication and its contrapositive always have the same truth value, and therefore they can be used interchangeably in a proof.

p	q	if p then q	not q	not p	if (not q) then (not p)
T	T	T	F	F	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	F	F	T

The last column is constructed from the two columns before it using the rule for "if..then..", but it turns out to have the same value on every line as "if p then q," so the two forms are logically equivalent.

Interchanging the hypothesis and conclusion of an implication without negating them gives the converse. The converse of the implication "if p then q" is the implication "if q then p." An implication and its converse do not have the same truth table. It can be a serious error to use one of them in place of the other. When you see an implication, be careful to note its direction: which is the hypothesis and which the conclusion.

Another equivalent form for the implication "if p then q" is the disjunction
"(not p) or q."

You can also rephrase the disjunction "p or q" as the implication
"if not p, then q," or its contrapositive, "if not q, then p." "Or" means at least one of them must be true, so if it isn't one, it must be the other.

"Untying Nots"
The other class of especially useful equivalents is the equivalents of negations. The most useful form is often the one with the "not" operator taken as far "inside" as possible, so that it is no longer being applied to compounds. For instance,
not (p and q) applies "not" to the compound "p and q". But it is equivalent to
(not p) or (not q), in which "not" is applied only to p and to q separately.
Here are the fundamental equivalents of negation applied to each logical connective:

not (not p) <=> p
not (p and q) <=> (not p) or (not q)
not (p or q) <=> (not p) and (not q)
not (if p then q) <=> p and not q

This last one often surprises people. It may seem that the negation of "if p then q" should be "if p then not q," but if you look at their truth tables, you see that isn't right. It's easy to slip, and it will spoil a proof, so be sure to remember, "the negation of an implication is not an implication." If p implies q, then it's impossible for p to be true without q also being true, and that's what the negation says. Or you can think of it as the negation of the equivalent disjunction "(not p) or q".

To "untie the not" on a multiply compound expression, just use the above rules as many times as needed. It's a little like differentiation in that respect: ask yourself whether the expression is a conjunction, disjunction, implication or negation, and apply the appropriate rule. For instance,
not( p and (q or r)) <=> (not p) or not (q or r) (applying the not to the and first)
<=> (not p) or ( (not q) and (not r) ) (applied to the or.)

not ( if p then not q) <=> p and not (not q) <=> p and q

Summary. The truth tables are presented for whatever help they may be to you in remembering and understanding the relationships and rules. What you need to retain is the ability to
1. find the truth value of a compound from the values of the components.
2. write and interpret logical compounds accurately.
3. rewrite an implication as its contrapositive. (Not its converse.)
4. rewrite a disjunction ("or") as an implication ("if..then.."). (Two ways.)
5. simplify the negation of any compound statement correctly.
These are fundamental skills in doing the logic necessary to proofs. Memorizing the rules is useful. You must also keep working at understanding the sense of them, as a doublecheck.

Exercises. Simplify by applying the rules for negation until "not" is no longer applied to any compound. Do each of them formally, AND check with your common sense. If they don't agree, ask about it.
7. not (if p and q, then r).
8. not (p, and if q then r).
9. not (if p, then q or r).
10. not (if not p, then q).
11. not (p or (q and not r)).
Rewrite as an implication, and simplify if possible. (These can have several answers.)
12. p or not q.
13. (p and q) or r.
14. p or q or r.
Write the contrapositive, and simplify if possible.
15. If p then not q.
16. If not p, then q or not r.

Quantifiers
Besides the logical connectives, most mathematical statements involve the quantifiers "for all.." or "there exists..". Sometimes other phrases are used that mean "for all.." or "there exists..". "Every," "each," "all" and sometimes "any" are words that often can be rephrased as "for all.." "For some.." is an equivalent to "there exists..".
"Any" is a problem word, as it is sometimes used to mean "for all.." and sometimes "there exists. Avoid using "any", and if you find it in a sentence, don't unconsciously assume what it means: think about it and decide.
"The sum of two integers is always an integer" means "for all integers a and b,
a + b is an integer." "Every real number has a non-negative square" means "For all real numbers x, x² 3 0." "The number 2 has a real square root" means "There exists a real number x with x² = 2."
(A "for all.." statement is an extended conjunction ("and"), while a "there exists.." is an extended disjunction ("or").)

Ambiguity
An expression with a "for all" on one end and a "for some" on the other is often ambiguous. "For all n in Z n + m = 0 for some m in Z" can mean either "(For all n in Z n + m = 0) for some m in Z" or "For all n in Z (n + m = 0 for some m in Z)", The first one is false and the second is true. Probably the safest thing is to put all your quantifiers at the beginning. If you see such an ambiguous statement, try to figure out which is meant, and if you aren't sure, ask.

Negations
We often need to write the negation of a "for all.." or a "there exists..". They are the negations of each other, in the following sense. (Underlines for emphasis.)

"not (for all x, p)" <=> "there exists an x such that not p."
"not (there exists an x such that p)" <=> "for all x, not p."

That is, to carry out the not,
1. replace "for all" with "there exists" (or vice versa) and
2. negate the predicate (the p).

The reason they are each others' negations is that "for all" is an extended "and", while "there exists" is an extended "or."

For the time being, we won't be concerned with whether the following sample statements are true, but just in being able to write them and their negations correctly.

Thus, the negation of "Every real number has a square root" is
not (for all real numbers x, x has a square root)
which is equivalent to
there exists a real number x such that x has no square root.

The negation of "There is an integer n such that n² = m" is
"For all integers n, n² ­ m."

Study and discuss these rules and examples until it becomes clear exactly why they are correct. Otherwise you may misuse them in proofs.

"For all.." and "there exists.." can also be combined with each other and with the other logical connectives. Their compounds can become very complicated, but following the negation rules carefully (and later the rules for proof openings) allows us to deal reliably with them.

Negate "For all x there exists a y with x + y > 100." Do it step by step:
not (for all x there exists a y with x + y > 100)
<=> there exists an x such that not (there exists a y with x + y > 100)
<=> there exists an x such that for all y, not (x + y > 100)
<=> there exists an x such that for all y, x + y 2 100.

"For all x there exists a y..." and "There exists a y such that for all x..." have very different meanings. The first means every x has its own y, possibly different from the y for some other x; while the second asserts that there is one y that works for all x's. "For all x in Z there exists a y in Z such that x + y = 0" is true, while "There exists a y in Z such that for all x in Z, x + y = 0" is false.

Exercises: Negate the following. Check with your common sense, and if they don't agree, ask about it.
17. Every real number is either a prime or even.
18. For every x there is an n such that nx is an integer.
19. For all nonzero x, if xy = 0, then y = 0.
20. There is an x such that for every y, xy = 0.

THEOREMS
"A valid reason for a statement must be one of the axioms of the system, or a statement that has already been proved, or a rule of formal logic, or a combination of them, having the given statement as conclusion." Once a statement has been proved, it is a theorem. Other words sometimes used for theorem include lemma (which often means a theorem proved to use as a tool in proving some other theorem), corollary (a theorem which follows fairly easily from the one before), and proposition.
Once a theorem has been proved, it becomes available to be used as a reason in other proofs. We build a scaffold of facts, starting with the axioms, using them to prove some theorems, then using those theorems to prove others, building higher and higher in an effort to find out the facts about our subject, in a way that leaves as little as possible room for error. It is theoretically possible to prove any theorem from the axioms alone, but once we have proved Theorem A, there are many theorems that can be proved much more easily using Theorem A than from the axioms alone. Therefore you must learn and be ready to use any theorem that has been proved. When you start working on a new proof, it's a good idea to quickly make a list of the theorems that have anything to do with the concepts in the new proof, so that you have them in front of you to choose from when you need a reason.

USING THEOREMS
When you use a theorem as a reason,
1. make it clear to the reader exactly what theorem you're quoting.
2. be sure you have checked all the theorem's hypotheses, and show the reader where you did it, unless it was just the previous step. Don't make the reader hunt.
3. be sure your conclusion is exactly that of the theorem. Any further reasoning should go in the next step.

THEOREM & DEFINITION LIST
To help you in remembering the theorems, you should always keep a list of the definitions and statements of all the theorems that have been proved so far so that you can glance through the list easily to remind yourself of what's already known and available to use. After you have studied a theorem and used it a few times, you should know it by heart anyway, but the list is a good idea to help you organize your thoughts.
How should you learn a theorem? Word for word memorization? You certainly have to know exactly what it says, and memorizing is one way. The words don't have to be the same, but the meaning must be exactly the same, so if you change any words, you have to be very sure you haven't changed the exact meaning. You want to understand the meaning, of course, but memorization can be a big help with that. In some cases, understanding the proof will help you to understand the meaning, and seeing how it is applied in examples, exercises, and later proofs is important also. But don't think you can just "absorb" the meaning by seeing those examples: you have to specifically learn exactly what the theorem says. Examples help, but they won't do the whole job.

FORMS OF THEOREMS
There are usually three ways in which you should know a theorem.
1. As it appears in the course or text, probably involving several variables.
This is probably the most compact exact form.
2. With no variables at all, or as few as possible.
For example, a theorem which usually appears as "If p is a prime and p divides ab, then p divides a or p divides b," can be stated as "If a prime divides a product of two integers then it must divide one of the factors." This form must still be exactly right. There are several advantages to such a restatement.
a. Rephrasing it helps you to think about the meaning.
b. The variable-less form sometimes makes it easier to recognize when the theorem can be applied, because it helps you to realize that you can apply it to any prime and any factors, not just ones named p, a and b. Sometimes people concentrate too much on the names of the variables used in the theorem and miss applications just because the names in the application are different.
There are limits to this form: some theorems are so complicated that a statement without variables would be too long and incomprehensible. Usually the version with variables is more compact, and often easier to use in proofs.
3. Informal memory handle.
Both of the first two forms of a theorem must be exactly correct. Sometimes it helps to have a third form, a really quick word or two to remind you of what a theorem says, just as kind of a memory handle. "Primes dividing products." To be short, it may not be complete, so be sure you don't try to use it in a proof; it's just there to help you think of which theorem to use. When you use a theorem, you have to use the exact form.

COMMON ERRORS
1. Leaving out part of the theorem. There usually aren't any unnecessary parts in a theorem statement, so you can't just learn the parts you like or think are important. Often a theorem has an introduction or preamble, then some numbered points. Learn the numbered points, but what's in the preamble is just as important.
2. Failing to notice which direction the implication goes. If the theorem says every A is a B, then if you have a B you can't conclude that it's an A. Always notice which way it goes. (See "converse" below.)
3. Failing to check that all the hypotheses are satisfied before making the conclusion. If you're not sure you remember all the hypotheses, look them up.
4. Misunderstanding the quantification of the variables. (See "Variables.")
5. Operating from a vague or imprecise statement of the theorem.

STANDARD PROOF METHODS OR OPENINGS
These are what you do to prove the given kind of statement. (What you do if you are given them is quite different.) In many cases, this answers the problem: "I don't know how to start."

There are three common methods to start proving "IF a THEN b."
Direct: "Assume a is true. Prove b is true."

Or, since the contrapositive has the same meaning, we can prove it instead.
Contrapositive: "Assume b is false. Prove a is false."

A third method is contradiction, or the indirect method. (See below.)
Indirect: "Assume a is true and b is false. Find a contradiction."
When you find a contradiction, be sure you have proved it true and false.

When proving an implication, state the method you are using and write out the opening statement for the specific case. For instance, to prove
If x > y, then x 3 y + 1, the three possible proof openings are

Direct: Assume x > y . Prove that x 3 y + 1.

Contrapositive: Assume x < y + 1. Prove x 2 y.

Indirect: Assume x > y and x < y + 1. Find a contradiction.

AND
This is easy. To prove "a and b," you must prove a and you must prove b. The two parts of the proof are called that, parts. ("Cases" are something different.)
Part 1. Prove a.
Part 2. Prove b.

CASES If you are given an "or" statement as part of your assumptions, as in "If a or b, then c", then you have two cases to prove, and both must be proved:
Case 1. Assume a. Prove c.
Case 2. Assume b. Prove c.
You have to do both because you don't know which is true, a or b, and you have to prove c is true no matter which.
Instead of "Prove c," it is legal for a case to end in a contradiction (see next).

CONTRADICTION
A method that can be tried for any theorem is contradiction, or an indirect proof. It consists in assuming the theorem is false and deducing a contradiction. "Contradiction" means a statement that is proved both true and false, not just something that seems strange or unlikely. If the theorem being false would lead to a contradiction, then the theorem must be true. (Some mathematicians don't believe in this kind of reasoning, but most do.)

FOR ALL
Another form of statement that often must be proved is an "every" or "for all" statement.
"For all integers a and b, a + b is an integer."
"For all real numbers x, x² 3 0."
These can also be rephrased as "The sum of two integers is always an integer," and "Every real number has a non-negative square."

To prove a "for all" statement, the automatic way to start is with a "Let" (or "suppose" or "assume"). If you have to prove "For every complex number z, there is a complex square root," start with "Let z be a complex number. Prove z has a complex square root." Once you have introduced your variable z this way, don't assume anything more about z that isn't true of every complex number. Then whatever conclusions you draw must be true of every complex number.
How does that work? You aren't really proving something about an object "z", you are using z as a convenient name for a general (or arbitrary) complex number. (Having a convenient name can help a lot to reduce complications.) If you don't assume anything about z that isn't true of every complex number, then your proof can be considered as a pattern. You could put any specific complex number at all into the pattern in place of your z, and all the statements would still be true, including the conclusion; so the conclusion must be true for "any complex number at all." If you assume any properties for z that are not true of all complex numbers, then you don't get that generality, and your conclusion might be false for some complex numbers.

THERE EXISTS or FOR SOME
"There exists" can be equivalently expressed by "there is" or "for some".
To prove a statement that asserts existence, you must find an example of the object that is claimed to exist, and then prove that it has the desired properties. In a formal sense, whatever steps you take to find the example are not part of the proof, although sometimes it is nice to share with the reader where the example came from. You only need one example, and it should be as concrete as possible. It is better to answer "37" than to say "just take x large enough."
Prove there is a pair of integers x and y such that x > y and 2y > x.
Proof: 3 and 2 are integers and 3 > 2, but 2 times 2 is greater than 3.
The phrases "for all" and "there exist(s)" and their equivalents are called "quantifiers," and are legitimate ways of introducing variables into your discussion.

"SOLVING"
Often, to prove that "there exists" something satisfying a certain property, you assume you have one, state the property, and "solve for the variable." This is often a good discovery process, but it's often not what the proof needs, only a way to discover what the answer may be. In general, "solving" only finds possible solutions; they then have to be verified. For the proof, you have to produce the solution, THEN prove that it has the desired properties. In "solving," you assume the properties and deduce the solution, which is just backward of what the proof needs. The "solving" process isn't even needed in the proof. You might want to include it to show how you arrived at the solution, but all the proof cares about is that you have told what the solution is, and proved that it works, no matter how you found it.
Example: Is there a real number x such that 1/x² = 2/(x² + x)? If I don't know, I can try to solve, like this
INVESTIGATION ("solving")
1/x² = 2/(x² + x Assume I've found one.
(x² + x)1 = 2x² Multiply both sides by x²(x² + x)
-x² + x = 0 Add -2x² to both sides.
x(-x + 1) = 0 factor
x = 0 or x = 1 If a product of reals is zero, one factor must be zero.
Does this prove that 0 and 1 are solutions? Not at all. What it proves is that IF there is a solution (I started with that assumption), THEN it must be 0 or 1. That is, they are the only numbers that have a chance of being solutions. To find out if they really are solutions, I have to plug them into the original equation. When I do, I find that 1 is a solution, but 0 isn't, since neither side of the equation exists if x = 0, and it doesn't make sense to talk of things being equal that don't exist; so not every candidate is a solution. But now I can answer the question and give a proof:
END INVESTIGATION
Yes, there is a real number x such that 1/x² = 2/(x² + x).
Proof: One such number is 1, because 1 is a real number; and 1/1² = 1 and 2/(1² + 1) = 2/2 = 1, so 1/1² = 2/(1² + 1) .
Now if I wanted to prove that 1 is the only solution, then I could include my solving process to show that 1 and 0 are the only possible ones, and show 0 isn't. But just to prove there exists such a real number, all I need is this two-line proof.
Notice that the investigation is NOT part of the proof. Sometimes it is good to include it, to show the reader how you came up with your solution, but it isn't logically necessary. The proof is just as correct if you came up with the number 1 as the result of a big fat guess, with no investigation at all.

MIXTURES
Many statements are mixtures of these kinds. For instance, with Z representing the set of integers, "for every x in Z there is an element y in Z such that x + y = 0" is a combination of there exists and for all. If we reverse the order of the quantifiers we get the statement "there is an element y in Z such that for every x in Z, x + y = 0." These are two very different statements. The first asserts that every integer has (its own) additive inverse (and different x's may have different y's), and is true; the second claims there is a single integer that acts as the additive inverse for all integers, and there certainly is no such thing. When there are multiple quantifiers in a statement, you must look closely to be sure you get the right meaning.
To prove a mixture, just deal with each part as you come to it. Suppose we are trying to prove "For every integer x, there is an integer y such that either xy is nice or x + y is nice." This is a nesting of three types. The first is the "for every", so we start with
Let x be an integer. Prove there is an integer y such that either xy is nice or x + y is nice.
Notice that we don't at this point need to know what "nice" means.
So our job now is an existence proof. To carry it out, we would need to know what "nice" means. We would have to find such a y, and once we had found it, verify that it is an integer, and prove that "xy is nice or x + y is nice." This last we might do by proving either "if xy is not nice, then x + y is nice," or its contrapositive.

PROVING THINGS EQUAL
To prove that a = b, you need to know what kinds of objects a and b are.
If they are real numbers, high school algebra may do it. If not, you have to look at the definition of the kind of objects they are, which often includes a criterion for their equality.
If a and b are sets, for instance, the definition of set equality is that a is contained in b and b is contained in a.
If they are ordered pairs, you have to look at their components and prove that corresponding components are equal.
If they are functions, you have to prove that they have the same domain, the same codomain, and that a(x) = b(x) for all x in their domain.
Besides the definition of equality for the particular kind of object, you may have theorems available that say that under certain circumstances (the hypotheses of the theorem), a = b. In that case, you may be able to prove a = b by proving that they satisfy the hypotheses of the theorem.
Therefore, when faced with an "a = b" to prove, you should review your tools: the definition of equality for their kind of object and any theorems you have learned that imply that objects of their kind are equal. Then choose one of those tools that looks like it might work. If you can't get the first one you try to work, try another. Often it's not obvious until you try which one is going to work, or be easiest.
 

NEGATIONS, or DISPROVING
To disprove something means to prove its opposite, or negation. Finding the correct negation is necessary for carrying out contrapositive proofs, indirect proofs, and many "or" proofs, and it can be complicated, so we need to know the rules for negation. Some of these may not seem natural to you. so it is important to learn them, as not knowing them may lead you to very wrong conclusions.
 

TYPE	STATEMENT	ITS NEGATION
Implication	If a then b	a is true, and b is false
for all	for all x, a	there exists an x such that a is false
There exists	there exists a y such that a	for all y, a is false
Conjunction (and)	a and b	a is false or b is false
Disjunction (and)	a or b	a is false and b is false

Notice that "and" and "or" are negations of each other, as are "for all..." and "there exists...such that," and that the negation of an implication is not an implication.
 

Another way of saying it is to say that these statements are equivalent:

STATEMENT	EQUIVALENT EXPANDED FORM
It is false that if a then b	a is true, and b is false
It is false that for all x, a	there exists an x such that a is false
It is false that there exists a y such that a	for all y, a is false
It is false that (a and b)	a is false or b is false
It is false that (a or b)	a is false and b is false

As with proving mixtures, finding their negations is a matter of applying the negation rules from the beginning. Taking the above statement to negate,
"For every integer x, there is an integer y such that either xy is nice or x + y is nice,"
we see it is a "for all," so its negation is a "there exists." Applying only that rule, we get the negation
"There is an integer x such that it is false that [there exists an integer y such that either xy or x + y is nice.]"
Now apply negation to the statement in the brackets. That statement is a "there exists," so we get
"There is an integer x such that for every integer y it is false that [either xy or x + y is nice.]"
Finally, we can apply negation to the "or" to get
"There is an integer x such that for every integer y, xy is not nice and x + y is not nice."

IMPLICIT (DISGUISED) FOR ALLS
The negation of our previous implication "If T is an equilateral triangle, then T is isosceles" by the above rules is
"T is an equilateral triangle and T is not isosceles."
This is the correct negation if T is a fixed object, previously defined. But in fact what one often means by such an implication is not a statement about a single object, but a statement about all such triangles, namely "For all T, if T is an equilateral triangle, then T is isosceles." Then we get a more reasonable negation, "There exists a T such that T is an equilateral triangle and T is not isosceles," or more compactly, "there is an equilateral triangle that is not isosceles." Leaving off the "for all" doesn't cause any problems until you try to negate the implication; then you have to supply the "for all" to get the appropriate negation.
Therefore, whenever you see an if statement, consider whether it is really an implied "for all," especially if you are to negate the statement.

PROVING THINGS UNEQUAL
It is tempting to take things that don't look alike and say they are unequal: a² ­ a. But a² ­ a isn't necessarily true. If a = 0 or 1, then a² = a, so a² ­ a is false in those cases.
The point is, a claim of inequality needs proof just as much as a claim of equality. After all, whole subjects like high school algebra are devoted to finding out when things that don't look alike really are equal after all; so not looking alike isn't enough to prove things are unequal.
"But I meant a² = a is not always true." Oh, okay, then be sure you say it that way, and prove it. In this case, you are negating "a² = a for all a in R," for instance (assuming you meant the domain to be R), so you want to prove its negative "a² ­ a for some a in R." You have to produce a real number a for which a² ­ a, and one is enough. The proof could be "3 is an element of R, and 3² = 9 while 3 ­ 9, so 3² ­ 3." Make it an explicit, concrete number.

21. If x > y, then x² > y².

22. If x > 0, then x has a square root.

23. Every real number has a real cube root.

24. If every number less than x is negative, then x is negative.
 

TO PROVE USE ONE OF THESE OPENINGS

TO PROVE	OPENING
If a then b. (direct)	Assume a. Prove b.
If a then b. (contrapositive)	Assume b is false. Prove a is false.
If a then b. (Indirect)	Assume a is true and b is false. Deduce a contradiction.
For all so-and-sos q, a.	Let q be a so-and-so. Prove a.
There exists an a such that b.  Or, For some a, b	Find as concrete an a as you can, and prove b is true of it.
Anything (indirect)	Assume it false, deduce a contradiction.
Anything	Apply a theorem that has it as its conclusion.

• Don't memorize proofs. Develop them afresh each time.

(Definitions and theorems are good to memorize, but not proofs.)
• State what has to be proved.
• Select a method. If it's not a simple proof opening, then what theorem or definition will be used? Tell the reader.
• Use proof openings.
• Keep "to proves" separate from known and assumed facts.
• There's always a latest "to prove": that's your goal. You aren't finished until your latest proved statement matches it.
• Give a reason for every assertion.
• In quoting a theorem as reason, check that all its hypotheses are satisfied.

The assertion should be exactly the conclusion of the theorem.
Any further reasoning goes into a separate step.
• When part of your reason is a statement you proved earlier in the proof, give some kind of reference to where it is; line number or star, for instance.
• Let the reader know what you are about to do and why, and summarize when you have done it.

Using variables that haven't been introduced is always a formal error, and can lead to substantive errors: "proving" things that are false, or writing a "proof" that can't be fixed up.

The sentence introducing the variable should include all the properties you are assuming about that variable. It is usually an error to try to give a variable additional properties later in the proof, unless you are redefining it altogether.

Don't requantify (reintroduce) a variable unless you are throwing away the old one. The phrase "Let x...", "for all x" or "for some x" usually makes unavailable any previous x you may have been using.

What is it? Whenever a variable is introduced, make yourself aware of what is known about what kind of object it represents, and remember that. Does it represent an integer, a real number, a set, a function, or what? Many errors come from losing track of what kind of object x is, and treating it as a number when it's something else instead 

Axioms

ARITHMETIC: Know how to do addition, subtraction, multiplication and division of actual real or complex numbers (no letters), and tell when one real number is bigger than another.

HIGH SCHOOL ALGEBRA: Any two real or complex numbers have a sum and a product, and the operations of addition and multiplication are subject to these rules.

For all real or complex numbers a,b,c, the following are true. (If you state one of these as a separate rule, you must include "for all real or complex numbers a,b,c.")

Addition
(a + b) + c = a + (b + c) associativity of +
a + b = b + a commutativity of +
a + 0 = a 0 is additive identity
For every number a, there's a number ­a such that their sum is 0.

Multiplication
(ab)c = a(bc) associativity
ab = ba commutativity
1a = a 1 is mult. identity
For all numbers a,b, IF ab = 0, THEN a = 0 or b = 0.

Distributivity connects addition and multiplication
a(b + c) = ab + ac and (a + b)c = ac + bc

Real numbers have an ordering; non-real complex numbers do not.
< and <=. For all real numbers a,b,c,d,
a < b or b < a or a = b, and only one of them is true.
if a < b and b < c then a < c. if a <= b and b <= c, then a <= c.
if c > 0 and a < b, then ac < bc. if c > 0 and a <= b, then ac <= bc.
if c < 0 and a < b, then ac > bc. if c < 0 and a <= b, then ac >= bc.
if a < b and c < d, if a <= b and c <= d,
then a + c < b + d. then a + c <= b + d.
("For all real numbers a,b,c,d" is stated once at the top, but it is a part of each of these rules.)

High School Algebra (HSA) includes these facts and various ones deduced from them, such as the rules for division and identities like (a ­ b) (a + b) =  a² ­ b2 .
High School Algebra is true for all real numbers, not just integers. What allows us to prove things about integers that are not true of real numbers in general are the remaining axioms. These first two should already be familiar to you.

REALS:
Nonnegative real numbers have square roots.
(Before you can take the square root of x, you must explain why x >= 0.)
All real numbers have real cube roots, fifth roots; all odd-numbered roots.
| x | =  x if x >= 0,
    = -x if x < 0.

• The sum and difference of two integers are integers.

("The integers are closed under addition and subtraction.")
• The product of two integers is an integer. (The quotient often is not.)

("The integers are closed under multiplication.")

The following are also axioms for integers, but it is not assumed that you are already familiar with them. They will be explained when they are used.
THE WELL-ORDERING PRINCIPLE (three versions):

1. A non-empty set of integers which is bounded from above contains a largest element.
2. A non-empty set of integers which is bounded from below contains a smallest element.
3. A non-empty set of positive integers contains a smallest element.

1. S contains only integers
2. S contains at least one integer, AND
3. there is an integer which is geater than or equal to every integer in S

(The integer described in c. is called an upper bound for S, and need not be in S.)

THE FIRST PRINCIPLE OF MATHEMATICAL INDUCTION:
SUPPOSE THAT for every positive integer n, S(n) is defined to be some statement, and that the following can be proved:
1) S(1) is true (Anchor)
2) For all positive integers k, IF S(k) is true, THEN S(k + 1) is true. (Step)
THEN S(n) is true for all positive integers n.

Note that there are two implications: the Principle itself is an implication, and the step contains an implication.

THE SECOND (COURSE-OF-VALUES) PRINCIPLE OF MATHEMATICAL INDUCTION:
SUPPOSE THAT for every positive integer n, S(n) is defined to be some statement, and that the following can be proved:
1) S(1) is true (Anchor)
2) For all integers k > 1, IF S(1),...,S(k - 1) are all true, THEN S(k) is true. (Step)
THEN S(n) is true for all positive integers n.

In these versions, 1 is used as the anchor value; that it usually the most useful one, but they can be stated in more generality, with any integer a as anchor. Then the step says "For all integers k greater than or equal to a" (First Principle) or "For all integers k greater than or equal to a, if S(a),...,S(k-1) are all true,..." Then the conclusion is that "S(n) is true for all integers n greater than or equal to a."

This is not as small as possible a set of axioms for the integers, because any of the last three can be used to prove the other two; so it would only be necessary to assume any one of them. For our purposes, it is more convenient to assume all three.

[ Proof.9906 07/21/2000 18:47 ] Proof.9906