## Mathematical Reasoning

### Subjects to be Learned

• axiom
• theorem
• proof --- mathematical reasoning -- inferencing
• trivial proof
• vacuous proof
• proof by contrapositive
• proof by contradiction

### Contents

Mathematical theories are constructed starting with some fundamental assumptions, called axioms, such as "sets exist" and "objects belong to a set" in the case of naive set theory, then proceeding to defining concepts(definitions) such as "equality of sets", and "subset", and establishing their properties and relationships between them in the form of theorems such as "Two sets are equal if and only if each is a subset of the other", which in turn causes introduction of new concepts and establishment of their properties and relationships. Proofs are the arguments for establishing those properties and relationships. At the bottom level these arguments follow the inference rules of propositional and predicate logic, that is the conclusion of the theorem being proved must be derived from its hypotheses, axioms, definitions, and proven theorems using inference rules. However, at the bottom level they become tedious and inefficient as one can easily imagine. Thus in actual proofs short-cuts are taken using already proven theorems, using multiple inference rules in one step without explicitly mentioning them individually, omitting "obvious" proofs, and so on.

Finding a proof is in general an art. There is no single method that works for all cases. However, at this level the most important thing to remember is to know and understand definitions of concepts involved. The next important thing to keep in mind is to look up relevant facts and try to use them. Even if you don't see the entire path to the goal, if you  move one step forward from where you are, you get a new perspective and it often gives you some good ideas to pursue. Needless to say that you must not forget the inference rules. It is not a bad idea to review "Problem Solving" we studied earlier here.

There are also some well used and often very useful proof techniques such as trivial proof, vacuous proof, direct proof, proof by contradiction, proving the contrapositive, and proof by induction. These are explained below with proofs of the theorems on subset relation as examples. If you wish to review identities, implications and inference rules click here.

Theorem 1: .
Proof: By the definition of ,  we need to show that .
For that, what we need is to show that for an arbitrary x, holds according to the inference rule "universal generalization".
Since x is an object of the universe of discourse, is true for any arbitrary object by the Universal Instantiation. Hence is true for any arbitrary object x ( is always true if q is true regardless of what p is). Thus by the Universal Generalization , that is, by the definition of subset.

We say is trivially true if q is true, and this kind of proof (i.e. showing q is true for without referring to p ) is called a trivial proof.

Theorem 2: .
Proof: By the definition of ,  we need to show that . For that, what we need is to show that for an arbitrary x, holds. Then apply the Universal Generalization.

Since ,   for any arbitrary x, is false by the Universal Instantiation. Hence is true for any arbitrary x ( is always true if p is false regardless of what q is). Hence by the Universal Generalization . Thus by the definition of subset.

We say is  vacuously true  if p is false, and this kind of proof (i.e. showing p is false for ) is called a vacuous proof.

Proof Variations for Theorem 2
Theorem 2, like most others, can be proven in a number of other ways. Here we try to prove it in two other ways.

(1) Proof by Contrapositive:
In this method, to prove we prove its contrapositive, ,   instead.
So to prove for an arbitrary x,   try to prove .
In this case since is true for any arbitrary x, is trivially true. Hence its contraposiive is also true.

(2) Proof by Contradiction:
In this method, to prove p we assume and derive a contradiction from that. Then since implies a contradiction, it can not hold true. Hence p must be true.
So to prove we assume that . is equivalent to .
This in turn is equivalent to .
However, implies by formula 4 of the relationships between the connectives and quantifiers from predicate logic and "simplification" from the implications of propositional logic.  But for any x, which contradicts .
Hence, can not be true.
Hence, .

### More Proofs

Theorem 3: A = B iff and .
Proof: By the definition of A = B,   Since , this means that and .
Hence, A = B iff and .

Theorem 4: Proof:   Thus for an arbitrary x in the universe, , and hold.
Hence, by hypothetical syllogism Hence, .

Next -- Set Operations

Back to Schedule