Mathematical Proofing & reasoning

Link to any subpages this page might have

Set

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:  tex2html_wrap_inline81 .
   Proof: By the definition of  tex2html_wrap_inline83 ,  we need to show that  tex2html_wrap_inline85 .
   For that, what we need is to show that for an arbitrary x,  tex2html_wrap_inline89   holds according to the inference rule "universal generalization".
   Since x is an object of the universe of discourse,   tex2html_wrap_inline93 is true for any arbitrary object by the Universal Instantiation. Hence   tex2html_wrap_inline89 is true for any arbitrary object x ( tex2html_wrap_inline97 is always true if q is true regardless of what p is). Thus by the Universal Generalization  tex2html_wrap_inline85, that is,  tex2html_wrap_inline81 by the definition of subset.

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

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

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

   We say tex2html_wrap_inline97 is  vacuously true  if p is false, and this kind of proof (i.e. showing p is false for tex2html_wrap_inline97 ) 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 tex2html_wrap_inline97   we prove its contrapositive, tex2html_wrap_inline147 ,   instead.
   So to prove   tex2html_wrap_inline121   for an arbitrary x,   try to prove   tex2html_wrap_inline153 .
   In this case since tex2html_wrap_inline155   is true for any arbitrary x,   tex2html_wrap_inline153   is trivially true. Hence its contraposiive   tex2html_wrap_inline121   is also true.

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

   More Proofs
   Theorem 3: A = B iff tex2html_wrap_inline185 and tex2html_wrap_inline187 .
   Proof: By the definition of A = B,
   tex2html_wrap_inline191
                  tex2html_wrap_inline193
                  tex2html_wrap_inline195
   Since tex2html_wrap_inline197 , this means that tex2html_wrap_inline185 and tex2html_wrap_inline187 .
   Hence, A = B iff tex2html_wrap_inline185 and tex2html_wrap_inline187 .

   Theorem 4: tex2html_wrap_inline209
   Proof: tex2html_wrap_inline211
   tex2html_wrap_inline213
   tex2html_wrap_inline215
   Thus for an arbitrary x in the universe,
   tex2html_wrap_inline219 , and
   tex2html_wrap_inline221 hold.
   Hence, by hypothetical syllogism tex2html_wrap_inline223
   Hence, tex2html_wrap_inline225 .