NOTES ON PROOFS

Preamble on Mathematical Reasoning:

The following definitions constitute a basis for mathematical reasoning:

Definition: Undefined Terms

An entity that escapes formal definition by leading to circular reasoning (i.e., point, line, set, number, element, etc).

Definition: Defined Terms

An entity that can be formally defined. A reasonable definition should be i) sufficient, ii) precise, iii) concise, and iv) non-redundant.

Definition: Postulate or Axiom

A statement whose truth is accepted without proof (a "special fact" which constitutes a starting point for derivation of theorems via deductive logic).

Definition: Conjecture

A statement whose truth value is unknown.

Definition: Theorem

A declarative statement in mathematics whose truth value is established by formal proof (i.e., there exists a proof).

A proof is an argument based on both deductive and inductive reasoning, which are two fundamental techniques of the modern scientific method.

Preamble on Arguments:

Definition: Argument

A collection of propositions, one of which, referred to as the conclusion, is justified by the others, referred to as premises (or propositions presented in an argument as reasons for accepting the conclusion).

Definition: Fallacy

An incorrect way of reasoning (for example, an argument that tries to persuade psychologically but not logically).

Definition: Deductive Argument

An argument whose conclusion is wholly justified by the premises (i.e., the premises are intended to show that the conclusion must necessarily be true - arguing from the general to the specific).

Definition: Inductive Argument

An argument that reasons about more general new knowledge from a small number of given facts or observations (i.e., the premises are intended to show that the conclusion is probably true - arguing from the specific to the general).

Remarks:

Deductive arguments reason about knowledge that is implicit in an already known body of knowledge and is the logic of formal science. It employs declarative statements, the logical connections between them, and the logical sequence (or lack thereof) from one statement to anonther.
Inductive arguments rely on evidence (or experience) and whether or not statements conform to facts. It is concerned with empirical investigation upon which conclusions are reached or hypotheses tested (i.e., on the basis of some limited experience a generalization is made in terms of some probability concept).
Progress in the modern scientific method is an inductive process.
All of our proofs will be deductive.

Examples:

A deductive argument is as follows:

An inductive argument is as follows:

Definition: Validity

A deductive argument whose conclusion is always true whenever all its premises are true.

Example:

1. If a person has a pulse, then that person's heart is pumping.
2. I have a pulse.
3. Therefore, my heart is pumping.
More formally, let p mean "I have a pulse," and q mean "My heart is pumping." Then,
1. p -> q
2. p
3. Therefore q

You should construct the truth table for this example and verify that the definition of validity holds in this case.

Definition: Invalid Argument

A deductive argument is invalid iff there exists at least one assignment of truth values in which the premises are true, but the conclusion is false.

Preamble on Theorems:

The word "theorem" suggests a powerful statements with far-reaching consequences. Thus, we can regard words such as fact, result, or proposition as "lesser theorems" (i.e., 1+1=2 is a fact which can indeed be proved according to the axioms of real number theory whereas, say, the Theorem of Pythagoras has much more general utility). Between the extremes from facts to full-fledged theorems are three common and very important notions that must be mentioned:

Lemma: A "pre-theorem" (a theorem that is used to prove a more complex one).

Corollary: A "post-theorem" (a result that naturally follows from a theorem).

Claim: An intermediate result generally utilized during the proof of a theorem.

It is important to note that theorems come in various logical forms. The simplest and most common form is the "Implication Theorem," (or "if-then theorem"). For example, the proposition "The sum of two even integers is even" can be restated as "If x and y are even integers, then x + y is an even integer." Clearly, this notion can be extended to the "Equivalence Theorem" (or "iff theorem"), which is an example of another class of theorems, and so on.

Deductive Proofs:

Definition: Deductive Proof

An approach to establishing the validity of an argument by using a series of "simpler arguments," known as rules of inference, that are known to be valid.

Definition: Rules of Inference

A primitive valid argument form.

Remark: Each inference rule enables the elimination or the introduction of a logical connective. Common rules of inference are listed in your textbook.

Definition: Direct Proof

This is the most basic type of proof pertaining to implication theorems. We assume that the hypotheses are true and use the rules of inference, axioms, definitions and theorems, to establish the truth of the conclusion.

Remark: We are proving p -> q directly from the truth assumption of p.

Definition: Proof by Contrapositive (indirect)

A direct proof of the contrapositive form of an implication theorem.

Remark: We are proving ~q -> ~p directly (where ~ refers to negation).

Definition: Proof by Contradiction (Reductio ad Absurdum, and another indirect proof form)

A proof of an implication theorem wherein the direct and contrapositive techniques are combined. Specifically, the conclusion is assumed false and a contradiction is derived using the direct proof technique.

Remarks: An indirect proof (proof by contradiction) is often regarded as a special case of proof by contrapositive. Here, we want to show that it is impossible for p to be true while q is false (i.e., we want to show that "p and ~q" is impossible). To do this, we suppose the impossible thing is true and prove that this supposition leads to an absurd conclusion (if a statement implies something wrong, then the statement itself must be wrong). More rigorously, we assume p and ~q and use all necessary axioms, definitions, and previously derived theorems to derive a contradiction (recall that this is a proposition of the form r AND ~r). For an exercise, show that the propositions [p -> q] and [p AND q -> r AND ~r] are logically equivalent. Note that in order to prove p -> q we must arrive at the contradiction r AND ~r, which is an indirect route.

Definition: Proof by Counterexample

A simple technique used to prove fallacy in an implication by demonstrating an instance where the hypothesis is true, but the conclusion is false (recall the implication truth table).

Definition: Vacuous Proof

A simple technique used to prove truth in an implication wherein the hypothesis is impossible (again recall the implication truth table).

Let us summarize the assumptions of our basic deductive proof techniques of theorems of the form p -> q:

                                          Assumption            Result Derived
Direct                                 p is true                        q is true
Contrapositive              ~q is true                      ~p is true
Contradiction                  p and ~q are true       =><= (i.e., Contradiction)

Example:

Theorem: If m is an even integer, then m + 7 is odd.

Proof #1 (direct):

    Since m is even, we have m=2a for some integer a.
    Then m + 7 = 2a + 7 = 2a + 6 + 1 = 2(a + 3) + 1.
    Since a + 3 is an integer, we know that m + 7 is odd.
    q.e.d.

Proof #2 (proof by contrapositive):

    Suppose that m + 7 is not odd.
    Then m + 7 = 2b for some integer b and m = 2b - 7 = 2b - 8 + 1 = 2(b - 4) + 1, where b - 4 is an integer. Hence m is odd
    (due to the logical equivalence of contrapositive and implication).
    q.e.d.

Proof #3 (proof by contradiction):

    Assume that m is even and that m + 7 is also even (i.e., assume the negation of what we want to prove).
    If m + 7 is even, then m + 7 = 2c for some integer c.
    Conseqently, m = 2c - 7 = 2c - 8 + 1 = 2(c - 4) + 1 with c - 4 an integer, so m is odd.
    =><=
    q.e.d.

NB: The proof began by assuming that m is even and then deduced that it was odd, which is an impossible situation (no integer can be both even and odd). The dilemma is a result of the false assumption that m + 7 is even, and accordingly its negation is true (that m + 7 is odd). Also, although it seems obvious that no integer can be both even and odd, a necessary lemma for this proof, can you prove it?

In all cases, the skeleton of a proof for an if-then theorem is as follows:

The first sentence of the proof is a restatement of either

    i) the hypothesis (direct),
    ii) the negation of the conclusion (contrapositive), or
    iii) the hypothesis and the negation of the conclusion (indirect)
    of the result.

The last sentence of the proof is a restatement of the conclusion of the result. Unravelling all appropriate definitions and working forward from the beginning of the proof and backward from the end of the proof until logical links are established (on rare occasions a previously derived theorem can be used which makes things even simpler).

Quantifiers (beyond proving if-then theorems)

Proving existential statements is similar to finding a counterexample (we need only find one object with the required properties). For example,

Theorem: There exists an integer x such that x is even and x is prime.
Proof:

Consider the integer 2, which is both even and prime.
q.e.d.

Proving universal statements requires us to show that every element of the set satisfies the required assertions. For example,

Theorem: Every integer that is divisible by 6 is even.
Proof:

    Let x be an integer that is divisible by 6.
    This means that there is an integer y such that x = 6y, which can be rewritten as x = 2(3y).
    Therefore, x is divisible by 2 and therefore even.
    q.e.d.