Mathematical Proof/Logic

(Redirected from Mathematical Proof/Introduction/Logical Reasoning)

As discussed in the introduction, logical statements are different from common English. We will discuss concepts like "or," "and," "if," "only if." (Here I would like to point out that in most mathematical papers it is acceptable to use the term "we" when referring to oneself. This is considered polite by not commanding the audience to do something nor excluding them from the discussion.)

Truth and statement

edit

We encounter statements frequently in mathematics.

Definition. (Statement) A statement is a declarative sentence that is either true or false (but not both), and its truth value is true (denoted by  ) or false (denoted by  ).

Example. Consider the following sentences:

  1. The number 9 is even.
  2.  .
  3. Mathematics is easy.
  4. How to solve  ?
  5. Please read this book.
  • The sentence 1 and 2 above are statements (even if the sentence 1 is false).
  • The sentences 3, 4 and 5 are not statements, since they are not declarative sentences, and we cannot say whether each of them is true or false.
  • In particular, the sentence 3 is an opinion, the sentence 4 is a question, and the sentence 5 is a command. Thus, none of them are declarative.
 

Exercise.

Is the sentence "The 123th digit in the decimal expansion of   is 3." a statement?

Yes.
No.


For the sentences that are not statements, there is a special type of sentences among them, namely open statement.

Definition. (Open statement) An open statement is a sentence whose truth value depends on the input of certain variable.

Remark.

  • Since the truth value may change upon input change, we cannot determine the truth value of an open statement (we cannot say it is (always) true or it is (always) false).

Example. Consider the sentence   (  is read "such that").

  • This sentence is true when  , and false otherwise.
  • This sentence is an open statement.

To express all possible combinations of truth values of some statements, we usually list them in a table, called a truth table.

Example. (Truth table for two statements) For two statements   and  , the truth table for them is as follows:   and there are four possible combinations of truth values of   and  .

Example. (Truth table for three statements) For three statements  ,   and  , the truth table for them is as follows:   and there are eight possible combinations of truth values of  ,   and  .

Remark.

  • In general, there are   possible combinations of truth values of   statements, since each statement has two possible truth values.
  • The truth table for three statement may seem to be complicated, and you may miss (or duplicate) some combinations in the truth table if you are not careful enough. Because of this, here is an advice for constructing such truth table:
  • for  , write four  's and then four  's, from top to bottom;
  • for  , write in this pattern from top to bottom:  ;
  • for  , write in this pattern from top to bottom:  .


Conjunction, disjunction and negation

edit

In this section, we will discuss some ways (conjunction and disjunction) to combine two statements into one statement, which is analogous to Mathematical Proof/Introduction to Set Theory#Set operations, in which two sets are combined into one set. Also, we will discuss a way (negation) to change a statement to another one.

Conjunctions

edit

Definition. (Conjunction) The conjunction of statements   and  , denoted by  , is a statement that is true when both   and   are true, and false otherwise.

Remark.

  •   is read "P and Q", and the conjunction of the statements   and   can also be expressed by "  and  " directly.

Example. (Truth table for  ) The truth table for   (in terms of possible combinations of truth values of   and   [1]) is  

  • We can see that   is true only when both   and   are true, and false otherwise.

Disjunctions

edit

Definition. (Disjunction) The disjunction of statements   and  , denoted by  , is a statement that is false when both   and   are false, and true otherwise.

Remark.

  • That is,   is true when at least one of   and   is true, and false otherwise.
  •   is read "P or Q", and the disjunction of the statements   and   can also be expressed by "  or  " directly.
  • The meaning of "or" in mathematics may be different from the meaning of "or" as an English word. For "or" in mathematics, it is used inclusively, i.e.   or   means   or   or both. However, as an English word, "or" may be used exclusively, i.e.   or   means   or   but not both. For example, when someone say "I will go to library or go to park this afternoon.", we interpret this as "I will either go to library, or go to park, but not both.".

Example. (Truth table for  ) The truth table for   is  

  • We can see that   is false only when both   and   are false, and true otherwise.

Negations

edit

Definition. The negation of a statement  , denoted by  , is a statement with truth value that is opposite to that of  .

Remark.

  •   is read "not P", and the negation of the statement   can also be expressed by "not  ", or "It is not the case that  " directly.
  • Another common notation for the negation of a statement   is  .
  • We refer to process of expressing a negation of a statement as negating a statement.

Example. (Truth table for  ) The truth table for   is  

  • We can see that   always has the opposite truth value to that of  .

To negate a statement, we usually add the word "not" into a statement, or delete it from a statement. For example, the negation of the statement "The number 4 is even." is "The number 4 is not even.", and the negation of the statement "The number 1 is not prime." is "The number 1 is not prime."

 

Exercise. Complete the following truth table:  

Answer

 

  • We can observe that in some combinations of truth values of   and  , the truth values of   and   are different.
 

Exercise. Let   be the statement "The number 3 is even.", and   be the statement "The number   is irrational."

Write down (in words) the negation of each of   and   without using the word "not".

Answer
  • The negation of   can be "The number 3 is odd.".
  • The negation of   can be "The number   is rational."
 

Exercise. Let   be the statement   and   be the statement  .

(a) Is the statement   true or false?

(b) Is the statement   true or false?

(c) Is the statement   true or false?

(d) Is the statement   true or false?


Answer
  • First, we can see that both   and   are false.

(a) Since   is false, the answer is true.

(b) Since   is false, the answer is true.

(c),(d) Since   and   are both true, the answer for (c) and (d) are both true.



Conditionals

edit

Apart from the above ways to form a new statement, we also have another very common way, namely the "if-then combination". The statement formed using the "if-then combination" is called a conditional.

Definition. (Conditionals) The conditional of two statements   and   is the statement "If   then  .", denoted by  .   and   are called the hypothesis and consequent of the conditional respectively. The conditional   is false when   is true and   is false, and true otherwise.

Example. (Truth table for  ) The truth table for   is  

  • We can observe that, in particular, even if the hypothesis   is false, the conditional   is true, by definition [2].
  • Another observation is that when the consequent is true, then no matter the hypothesis is true or false, the conditional must be true (see 1st and 3rd row).

To understand more intuitively why the conditional is always true when the hypothesis is false, consider the following example.

Example. Suppose Bob is taking a mathematics course, called MATH1001. The course instructor of MATH1001 warns Bob that if he fails the final examination of this course, then he will fail this course. Let   be the statement "Bob fails the final examination of MATH1001.", and   be the statement "Bob fails MATH1001". Then, the statement made by the course instructor is " ".

For the statement made by the course instructor to be true, either Bob actually fails the final examination of MATH1001, and he actually fails the course, or Bob passes the final examination of MATH1001. In the latter case, whether Bob fails MATH1001 or not does not matter, since the course instructor does not promise anything if Bob passes the final examination of MATH1001 [3].

For the statement made by the course instructor to be false, the only situation is that Bob fails the final examination of MATH1001, but he still passes MATH1001 (  is true and   is false) (this shows that the instructor is lying!).

Converse and biconditionals

edit

After discussing conditional of   and  , we will discuss biconditional of   and  . As suggested by its name, there are two conditionals involved. The conditional involved, in addition to  , is  , which is called the converse of the conditional  .

In mathematics, given that the conditional   is true, we are often interested in knowing whether its converse   is true as well [4].

Example. The converse of the statement made by the course instructor in the previous example is "If Bob fails MATH1001, then he fails the final examination of MATH1001.".

Definition. (Biconditionals) The biconditional of two statements   and  , denoted by  , is  , that is, "If   then  ." and "If   then  .".

Remark.

  • We also write   if and only if   in this case.
  • To understand the phrase "if and only if" more clearly, consider the following:
  •   if and only if   can be interpreted as "  if   and   only if  ".
  • For "  if  ", it should be easy to accept that it means "If   then  ".
  • For "  only if  , it means   can only be true when   is true. That is,   is a necessary condition for  . Thus, we can deduce that when   is true,   must be true (or else   cannot possibly be true). Hence, "  only if  " means "If   then  .".

Example. (Truth table for  ) The truth table for   is  

  • We can see that   is true when both   and   have the same truth values (i.e. either both   and   are true, or both   and   are false), and false otherwise.


Implication and logical equivalence

edit

When the conditional   is true, we can say "  implies  ", denoted by  . On the other hand, when   does not imply  , i.e.   is false, we denote this by  .

We have some other equivalently ways to say "  implies  ", namely

  •   is a sufficient condition for   (or   is sufficient for   in short)
  • We call   to be sufficient for   since when   implies  , then "  is true" is sufficient to deduce "  is true".
  •   is a necessary condition for   (or   is necessary for   in short)
  • We call   to be necessary for   since when   implies  , the hypothesis cannot be possibly true when the consequent   is false (or else the conditional   will be false). This explains the necessity of "  is true".

When  , we are often interested knowing whether the converse of   is true or not, i.e. whether we have   or not [5].

In the case where   but  , we have multiple equivalent ways to express this:

  •   is sufficient but not necessary for  .
  • From the previous interpretation, when we say   is necessary for  , we mean  . Hence, when   is sufficient but not necessary for  , we mean   and  .
  •   is a stronger condition than   (or   is stronger than   in short).

In the case where   and   as well, the biconditional   is also true, and we denote this by  . There are also multiple equivalent ways to express this:

  •   is logically equivalent to  .
  • We say they are logically equivalent since they always have the same truth values (because   is true), which is related to logic.
  • "  if and only if  " (is true).
  • Recall that we also use "  if and only if  " to express the biconditional  . Thus, technically, we should write "  if and only if  " is true in the case where  . However, we rarely write this in practice, and usually omit the phrase "is true" since it makes the expression more complicated. So, when we write "  if and only if  " in this context, we mean that the biconditional is true without saying it explicitly.
  • Usually, when we just write "  if and only if  ", we have the meaning of the logical equivalence  , rather than the statement  . If we really want to have the latter meaning, we should specify that "  if and only if  " refers to a statement.
  •   is necessary and sufficient for  .
  • Following the previous interpretation,   is necessary and sufficient for   means   and  .

Theorem. (Some laws about conjunction, disjunction and negation) In the following,  ,   and   are arbitrary statements.

  •   (double negation)
  •   (commutative law of conjunction)
  •   (commutative law of disjunction)
  •   (associative law of conjunction)
  •   (associative law of conjunction)
  •   (distributive law)
  •   (distributive law)
  •   (De Morgan's law)
  •   (De Morgan's law)

Proof. They can be shown using truth tables.

 

Remark.

  • You may observe that there are also some analogous results in set theory (some even have the same name!), discussed in the chapter about set theory. This is because the results discussed in the chapter about set theory are actually proven from the corresponding results above almost directly.

Theorem. (Bridge between conditional and disjunction) The statements   and   are logically equivalent.

Proof. It can be shown using the following truth table:  

 

Theorem. (Logical equivalence of a conditional and its contrapositive) The contrapositive of a conditional   is defined to be another conditional  , and they are logically equivalent.

Proof. Using the bridge between conditional and disjunction and some other laws, it can be shown as follows:  

 

Remark.

  • It may seem "surprising" when we "suddenly" negate   twice. Indeed, when we are thinking about how to prove the logical equivalence, we do not directly do this from nowhere. Instead, we are "motivated" to do so after observing that   and  . So, we sort of finish the above series of equivalence "like a sandwich" (from left to right and from right to left simultaneously). This may be useful for other similar proofs.
  • This result is very important for Proof by Contrapositive, which will be discussed later.


Tautologies and contradictions

edit

Before defining what tautologies and contradictions are, we need to introduce some terms first. In the previous sections, we have discussed the meaning of the symbols   and  . These symbols are sometimes called logical connectives, and we can use logically connectives to make some complicated statements. Such statements, which are composed of at least one given (or component) statements (usually denoted by   etc.) and at least one logical connective, are called compound statements.

Definition. (Tautologies and contradictions) A compound statement   is called a tautology (contradiction) if it is true (false) for each possible combination of truth values of the component statement(s) that comprise  .

Remark.

  • We use   to denote a tautology and   to denote a contradiction.
  • When a statement   is a tautology, we can also write  , since it means   and   always have the same truth value, and because the truth value of   is always true, the truth value of   is also always true, i.e.   is a tautology.
  • Because of this, when we want to prove that a statement   is always true, one way is to show that  . For example, if we want to prove that   and   are logically equivalent, we may show that  .

Example. Let   be an arbitrary statement. Then,

  •   is a tautology.
  •   is a contradiction.

This is because the truth table for   is   and the truth table for   is  

Example. Let   and   be arbitrary statements. Then,   is a tautology, since its truth table is  

 

Exercise. The following are some further questions on this example.

1 Is the converse of the statement in the example,  , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

2 Is the negation of the statement in the example,  , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

3 Is the contrapositive of the statement in the example,  , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

Prove that   is a tautology without using truth tables.

Answer

Since   the given conditional is a tautology.

A student claims that   is a contradiction with the following argument:

Since  , the conditional is a contradiction.

Comment on his claim.

Answer
  • The claim is wrong.
  • The step   is incorrect, since we should use distributive law here instead, and we cannot apply associative law with two types of logical connector here.
  • Indeed, it is shown in an above question that the conditional   is neither tautology nor contradiction.


Theorem. (Laws about tautologies and contradictions) Let   be an arbitrary statement. Then,

  •  .
  •  .
  •  .
  •  .
  •  .
  •  .

Proof. They can be shown using truth tables.

 

Quantifiers

edit

Recall that an open statement is a sentence whose truth values depends on the input of certain variable. In this section, we will discuss a way to change an open statement into a statement, by "restricting the input" using quantifiers, and such statement made is called an quantified statement. For example, consider the statement "The square of each real number is nonnegative.". It can be rephrased as "For each real number  ,  ." We can let   be the open statement " ". Then, it can be further rephrased as "For each real number  ,  ." In this case, we can observe how an open statement ( ) is converted to a statement (For each real number  ,  ), and the phrase "for each" is a type of the universal quantifier. Other phrases that are also universal quantifiers include "for every", "for all" and "whenever". The universal quantifier is usually denoted by   (an inverted "A"). After introducing this notation, the statement we mention can be further rephrased as " " (we also use some set notations here).

In general, we can use the universal quantifier to change an open statement   to a statement, which is " " in which   is a (universal) set (or domain) which restricts the input  .

Apart from the universal quantifier, another way to convert an open statement into a statement is using an existential quantifier. Each of the phrases "there exists", "there is", "there is at least one", "for some" [6], "for at least one" is referred to as an existential quantifier, and is denoted by   (an inverted "E"). For example, we can rewrite the statement "The square of some real number is negative." as " " (which is false).

In general, we can use the existential quantifier to change an open statement   to a statement, which is " " in which   is a (universal) set (or domain) which restricts the input  .

Another quantifier that is related to existential quantifier is the unique existential quantifier. Each of the phrases "there exists a unique", "there is exactly one", "for a unique", "for exactly one" is referred to as unique existential quantifier, which is denoted by  . For example, we can rewrite the statement "There exists a unique real number   such that  ." as " ." We can express the unique existential quantifier in terms of existential and universal quantifiers, by defining " " as   where the left bracket is the existence part, and the right bracket is the uniqueness part. In words, the expression means

There exists   such that  , AND for every  , if   and  , then   (i.e.,   and   are actually referring to the same thing, so there is exactly one   such that  ).

In general, we need to separate the existence and uniqueness part as above to prove statements involving unique existential quantifier.

Negation of quantified statements

edit

Example. The statement " " [7] can be expressed in words (partially) as "There exists a set   such that  ."

 

Exercise. Write down the negation of this statement in words (partially). (Hint: What is the negation of "  (  is a nonnegative integer)."? Hence, what is the negation of "There is at least one   such that  ."?)

Answer
  • For the hint, the negation of "  (  is a nonnegative integer)." is " ", and the negation of "There is at least one   such that  ." is hence "There is no   such that  ". It can also be expressed equivalently as "For each  ,   is not satisfied.", or  .
  • Inspired from the hint, the negation of this statement can be written as "For each set  ,  ."


From this example, we can see that the negation of the statement " " is logically equivalent to " ". Now, it is natural for us to want to know also the negation of the statement " . Consider this: when it is not the case that   is true for each  , it means that   is false for at least one  . In other words,  . Hence, we know that the negation of the statement " " is logically equivalent to  .

Quantified statements with more than one quantifier

edit

A quantified statement may contain more than one quantifier. When only one type of quantifier is used in such quantified statement, the situation is simpler. For example, consider the statement "For each real number   and for each real number  ,   is a real number." It can be written as " ". When we interchange " " and " ", the meaning of the statement is not affected (the statement still means "The product of two arbitrary real numbers is a real number.") Because of this, we can simply write the statement as " " without any ambiguity.

For an example that involve two existential quantifiers, consider the statement "There exists an real number   and an real number   such that   is a real number." It can be written as " ." Similarly, interchanging " " and " " does not affect the meaning of the statement (the statement still means "For at least one pair of real numbers   and  ,   is a real number.") Because of this, we can simply write the statement as " " without any ambiguity.

However, when both types of quantifier are used in such quantified statement, things get more complicated. For example, consider the statement "For each integer  , there exists an integer   such that  ." This can also be written as " ". It means that for each integer, we can find a (strictly) smaller one, and we can see that this is a true statement. For instance, if you choose  , I can choose   or  . Indeed, for the integer   chosen by you, I can always choose my   as   so that  .

Let's see what happen if we interchange " " and " ". The statement becomes  , meaning that there exists an integer   such that it is (strictly) smaller than every integer  ! This is false, since, for example, there is no integer that is (strictly) smaller than itself (which is an integer). In this example, we can see that interchanging the positions of universal quantifier and existential quantifier can change the meaning of the statement. Hence, it is very important to understand clearly the meaning of a quantified statement with both universal and existential quantifiers. To ease the understanding, here is a tips for reading such statement:

For the variable associated to the quantifier  , it may depend on the variable(s) introduced earlier in the statement, but must be independent from the variable(s) introduced later in the statement.

What does it mean? For example, consider the above example. In the first case, we have  . Then, since the variable   appears earlier than the variable   which associated to  ,   may depend on   (This is similar to the case in English. In a sentence, a thing may depend on other things mentioned earlier.). For instance, when you choose  , and I choose  . Then,  . However, if you change your choice to  , then my   does not work, and I need to change my   to, say, 8 so that  . Then, we can see that   depends on   in this case. In the second case, we have  . In this case, the variable   appears later than the variable  . Hence, the variable   must be independent from  . That is, when such   is determined, it needs to satisfy   for each   chosen, and the   cannot change depend on what   is. Indeed,   cannot possibly depend on  , since   is supposed to be determined when   is not even introduced!

Exercises

edit

In the following questions,   are statements.

A. Construct the truth tables for each the following statements, and also give its converse and contrapositive:

  1.  
  2.  
  3.  
  4.  
  5.  

B. Negate the following statements:

  1.  
  2.  
  3.  
  1. When we construct a truth table for a statement that involves some statements, we need to also list all possible combinations of truth values of the statements involved, so that we can observe the truth value for that statement under all situations.
  2. In this case, we may call this conditional to be vacuously true, since the conditional is meaningless (when the hypothesis is false, no matter the consequent is true or false, the conditional is true. Thus, "the conditional is true" is "useless" when the hypothesis is false).
  3. For example, it may be the case that Bob does not hand in any assignment, and thus even if he passes the final examination, he still fails the course (  is false and   is true). It may also be the case that Bob passes the final examination, and perform consistently well in all assignments, and thus he passes the course (  is false and   is false).
  4. It is not necessary for   to be true when   is true. For example, when   is false and   is true,   is (vacuously) true, but   is false.
  5. It is not necessary for   when  . See, for example, the third row of the above truth table for  , in which   is true while   is false. Indeed, it is a common mistake to think that we must also have   when  .
  6. "Some" in mathematics always means "at least one".
  7. In the form of " ", this statement can also be written as " ."