Mathematical reasoning and nature of proof

1. Nature of Truth

In mathematics we deal with statements that are “True” or “False”. This is known as the “Law of Excluded Middle”. Despite the fact that multi valued logics are used in computer science, they have no place in mathematical reasoning.

2. Nature of Mathematical Proof

A very common question that comes to our mind is “What is the definition of a good mathematical proof?” And the answer seems to be best given by “It convinces you!” Unfortunately this is not very true. Personal certitude has nothing to do with mathematical proof. The human mind is a very fragile thing, and human beings can be convinced of the most preposterous things. A good proof is one that starts with a set of axioms, and proceeds using correct $$mathbf {rules ~of~ inference}$$ to the conclusion.

3. Rules of Inference

The common rule of inference that are frequently used are listed below.

1) Given the statement: $$All ~A ~ is ~ B$$ ~ and the statement $$All~B ~is ~ C$$ , we conclude that  $$All~ A ~ is ~ C. $$

For example:

If I do not wake up, then I cannot go to work.

If cannot go to work then I will not be paid.

Therefore, if I do not wake up, then I will not get paid.

2) Given $$All ~ A ~ is ~B$$ . We conclude that $$Some~ B~ is ~A $$ .

For example:

All cows are Animals, therefore some animals are cows.

An incorrect inference is to conclude that $$All ~ B ~ is ~ A,$$ given $$All~ A ~ is ~ B$$ . After all, not all animals are cows!

3) Given $$Some ~ A ~ is B ~ and Some~ B~ is ~C$$ , we can conclude nothing.

For example:

Some cows are Jerseys,

Some Jerseys are human.

Here we interpret the word “Jersey” as “Things that come from Jersey, an island in the English Channel.”

4) Given $$Some ~ A ~ is ~ B$$ , we conclude that $$Some~ B~ is ~ A$$ .

For example:

Some cows are Jerseys, therefore some Jerseys are cows.

5) Given $$Some ~ A ~is B~ and ~ All ~ B ~ is ~C$$ we conclude that $$Some ~ A ~ is ~C$$ .

For example:

Some cows give milk, All things that give milk are female.

Therefore , Some cows are female.

6) Given $$All ~ A ~ is ~ B, $$ and $$Some ~ B ~ is ~ C$$ . In this case we can conclude nothing.

For example:

All cows are animals. Some animals are birds.

No conclusion is possible.

Now such logical inferences can be formulated in rigorous mathematical format by the proper use of $$mathbf{quantifiers}.$$

⦁ A statement such as $$All ~ A ~ is B~$$ is said to be $$”mathbf{Universally ~quantified}”$$ . In other words, it is a universal statement that applies to all $$A.$$

⦁ A statement such as $$Some ~ A ~ is ~ B ~$$ is said to be $$”mathbf{Existentially ~quantified} “$$ . In other words , there exists at least one $$A$$ to which the statement applies.

⦁ The only permissible form for the universal negative is $$No~ A ~ is ~ B$$ . The existential negative has several forms like –

Not all A is B

Some A is not B, and many others.

Mathematical statements require somewhat greater precision than general statements.

4. Negation of a statement

A proposition is a statement that can be assigned the value $$mathbf{True}$$ or $$mathbf{False}$$ . Negation of a statement is the one that produces a value of $$mathbf{true}$$ when the original statement is $$mathbf{false}$$ and vice versa. In ordinary logic

* An existential negates a universal and a universal negates an existential.

* The negation of $$”All~ A~ is~ B”$$ is $$”Some ~A~ is ~ not~B”$$ .

* The negative of $$”Some ~ A ~ is~ B”$$ is  $$”No ~ A~is ~B”$$.

* The statements $$”Some ~A~is~B”$$ and $$”Some~A~is~not~B”$$ can both be true.

5. Logical Connectives

1) If $$P$$ is a proposition, $$neg P$$ is its negation. $$neg P$$ is read as $$”not~ P”$$ .

Note: Do not confuse this mathematical connective with the general statement $$”Not~ all~ A ~is~ B”$$ . They are not the same thing.

2) If $$P$$ and $$Q$$ are propositions,

* $$Pwedge Q$$ is called the conjunction of $$P$$ and $$Q$$ , and is read as $$P~and ~Q$$ .

* $$Pvee Q$$ is called the disjunction of $$P$$ and $$Q$$ , and is read as $$P~ or ~ Q$$ .

* $$Prightarrow Q$$ is called the implication of $$P$$ and $$Q$$ and is read as $$If ~ P ~ then ~ Q$$ .

6. Implications

◦ The most interesting connective is the implication $$Prightarrow Q$$ . It can also be written as $$neg Pvee Q$$ .

◦ If $$P$$ is false then the entire statement is true. That is $$”mathbf{ A ~False~ statement~ Implies ~Anything }”$$ .

◦ An implication is proven by assuming that $$P$$ is true and in that case, $$Q$$ must also be true.

◦ Given a statement $$S$$ of the form $$P rightarrow Q$$ , the statement $$Qrightarrow P$$ is called the $$mathbf{Converse}$$ of $$S$$ .

◦ The Converse of $$S$$ is an independent statement and must be proven independently of $$S$$ .

◦ A statement and its contrapositive are logically equivalent. Either both are true or both are false.

◦ Given a statement $$S$$ of the form $$P rightarrow Q$$ , the statement $$neg Qrightarrow neg P$$ is called the $$mathbf{Contrapositive}$$ of $$S$$ .

◦ The statement $$neg P rightarrow neg Q$$ is called the $$mathbf {Inverse}$$ if $$S$$ . The Inverse of $$S$$ is logically equivalent to the Converse of $$S$$ .

◦ The statement of the form $$P~ iff~ Q$$ is the shorthand for $$(If ~ P ~then ~Q)$$ and $$(If ~ Q~ then ~ P)$$ . In symbols we express this as $$Pleftrightarrow Q$$ .To prove $$Pleftrightarrow Q$$ , we must prove both $$P rightarrow Q$$ and $$Q rightarrow P$$ .

7. Negating Compound Statements

$$neg(Pwedge Q) = neg P vee neg Q $$

⦁ X is less than three and X is odd

⦁ X is greater than or equal to 3 or X is even

$$neg(Pvee Q) = neg P wedge neg Q $$

⦁ The car was either red or green

⦁ The car was not red AND it was not green

$$neg(Prightarrow Q) = P wedge neg Q $$

⦁ If a person has a Ph.D. then they must be rich

⦁ Prof. Maurer has a PhD and Prof. Maurer is poor.

⦁ Note change in quantifiers.

8. Rules of inferences

✓ If $$P$$ is known to be true , $$neg P$$ is false, and vice versa.

✓ If $$Pwedge Q$$ is true, then $$Qwedge P$$ is true.

✓ If $$Pwedge Q$$ is true, then both $$P$$ and $$Q$$ are true.

✓ If $$Pwedge Q$$ is false and $$P$$ is known to be true, then $$Q$$ is false.

✓ If $$Pvee Q$$ is true, then $$Qvee P$$ is true.

✓ If $$Pvee Q$$ is false, then both $$P$$ and $$Q$$ are false.

✓ If $$Pvee Q$$ is known to be true, and $$P$$ is known to be false then $$Q$$ is true.

✓ If $$Prightarrow Q$$ is known to be true, and $$P$$ is true then $$Q$$ is true.

✓ If $$Prightarrow Q$$ is known to be true, and $$Q$$ is false then $$P$$ is false.

✓ If $$Pleftrightarrow Q$$ is known to be true and $$P$$ is true then $$Q$$ is true, and vice versa.

✓ If $$Pleftrightarrow Q$$ is known to be true and $$P$$ is false then $$Q$$ is false, and vice versa.

✓ If $$Pleftrightarrow Q$$ is known to be false and $$P$$ is true then $$Q$$ is true, and vice versa.

✓ If $$Pleftrightarrow Q$$ is known to be false and $$P$$ is false then $Q$ is true, and vice versa.

9. Logical Fallacies

Most students have a hard understanding this. It is not the calculations that are incorrect, it is the $$mathbf{Inference}$$ that is wrong. If an inference technique can be used to prove a silly nonsense then it cannot be used to prove anything true. A mathematical proof is actually supposed to demonstrate what is true and apply the rules of inference correctly. So, the next time you write a proof, use proper tools i.e., $$mathbf{Rules ~of~ Inference}$$ and do avoid $$mathbf{HASTY~ GENERALIZATION}$$ !

Tarun Kumari, Research Scholar,

Dept of Mathematical Sciences,

Tezpur University.