Mathematical Proof/Logic

Template:Nav 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

We encounter Template:Colored em frequently in mathematics. Template:Colored definition Template:Colored example Template:Colored exercise For the sentences that are not statements, there is a special type of sentences among them, namely Template:Colored em. Template:Colored definition Template:Colored remark Template:Colored example To express all possible combinations of Template:Colored em of some statements, we usually list them in a table, called a Template:Colored em. Template:Colored example Template:Colored example Template:Colored remark

Conjunction, disjunction and negation

In this section, we will discuss some ways (conjunction and disjunction) to combine two statements into one statement, which is analogous to [[../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.

Negations

Template:Colored definition Template:Colored remark Template:Colored example 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 Template:Colored em even.", and the negation of the statement "The number 1 is not prime." is "The number 1 is not prime." Template:Colored exercise Template:Colored exercise Template:Colored exercise

Conditionals

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 Template:Colored em. Template:Colored definition Template:Colored example To understand more intuitively why the conditional is always true when the hypothesis is false, consider the following example. Template:Colored example

Converse and biconditionals

After discussing Template:Colored em of $P$ and $Q$, we will discuss Template:Colored em of $P$ and $Q$. As suggested by its name, there are Template:Colored em conditionals involved. The conditional involved, in addition to $P\to Q$, is $Q\to P$, which is called the Template:Colored em of the conditional $P\to Q$.

In mathematics, given that the conditional $P\to Q$ is true, we are often interested in knowing whether its Template:Colored em $Q\to P$ is true as well .

Implication and logical equivalence

When the conditional $P\to Q$ is Template:Colored em, we can say "$P$ Template:Colored em $Q$", denoted by $P\Rightarrow Q$. On the other hand, when $P$ does Template:Colored em imply $Q$, i.e. $P\to Q$ is Template:Colored em, we denote this by $P\nRightarrow Q$.

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

• $P$ is a Template:Colored em for $Q$ (or $P$ is sufficient for $Q$ in short)

• We call $P$ to be Template:Colored em for $Q$ since when $P$ implies $Q$, then "$P$ is true" is Template:Colored em to deduce "$Q$ is true".

• $Q$ is a Template:Colored em for $P$ (or $Q$ is necessary for $P$ in short)

• We call $Q$ to be Template:Colored em for $P$ since when $P$ implies $Q$, the hypothesis cannot be possibly true when the consequent $Q$ is false (or else the conditional $P\to Q$ will be false). This explains the Template:Colored em of "$Q$ is true".

When $P\Rightarrow Q$, we are often interested knowing whether the Template:Colored em of $P\to Q$ is true or not, i.e. whether we have $Q\Rightarrow P$ or not .

In the case where $P\Rightarrow Q$ but $Q\nRightarrow P$, we have multiple equivalent ways to express this:

• $P$ is Template:Colored em for $Q$.

• From the previous interpretation, when we say $P$ is necessary for $Q$, we mean $Q\Rightarrow P$. Hence, when $P$ is Template:Color but Template:Color for $Q$, we mean $P\Rightarrow Q$ and $Q\nRightarrow P$.

• $P$ is a Template:Colored em than $Q$ (or $P$ is Template:Colored em than $Q$ in short).

In the case where $P\Rightarrow Q$ and $Q\Rightarrow P$ as well, the biconditional $P\leftrightarrow Q$ is also true, and we denote this by $P\iff Q$. There are also multiple equivalent ways to express this:

• $P$ is Template:Colored em $Q$.

• We say they are Template:Colored em equivalent since they always have the same truth values (because $P\leftrightarrow Q$ is true), which is related to Template:Colored em.

• "$P$ Template:Colored em $Q$" (is true).

• Recall that we also use "$P$ if and only if $Q$" to express the Template:Colored em $P\leftrightarrow Q$. Thus, technically, we should write "$P$ if and only if $Q$" is true in the case where $P\iff Q$. 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 "$P$ if and only if $Q$" in this context, we mean that the biconditional is true without saying it explicitly.
• Usually, when we just write "$P$ if and only if $Q$", we have the meaning of the logical equivalence $P\iff Q$, rather than the statement $P\leftrightarrow Q$. If we really want to have the latter meaning, we should specify that "$P$ if and only if $Q$" refers to a Template:Colored em.

• $P$ is Template:Colored em for $Q$.

• Following the previous interpretation, $P$ is Template:Color and Template:Color for $Q$ means $Q\Rightarrow P$ and $P\Rightarrow Q$.

Proof. They can be shown using truth tables.

$◻$

Proof. It can be shown using the following truth table: $$\begin{array}{ccccc}P& Q& \sim P& P\to Q& (\sim P)\vee Q\\ T& T& F& T& T\\ T& F& F& F& F\\ F& T& T& T& T\\ F& F& T& T& T\end{array}$$

$◻$

Proof. Using the bridge between conditional and disjunction and some other laws, it can be shown as follows: $$P\to Q\iff (\sim P)\vee Q\iff Q\vee (\sim P)\iff (\sim (\sim Q))\vee (\sim P)\iff (\sim Q)\to (\sim P).$$

$◻$

Tautologies and contradictions

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 $\sim ,\vee ,\wedge ,\to$ and $\leftrightarrow$. These symbols are sometimes called Template:Colored em, and we can use Template:Colored em to make some complicated statements. Such statements, which are composed of at least one given (or component) statements (usually denoted by $P,Q,R$ etc.) and at least one logical connective, are called Template:Colored em.

Proof. They can be shown using truth tables.

$◻$

Quantifiers

Recall that an Template:Colored em 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 $x$, $x^2\ge 0$." We can let $P(x)$ be the Template:Colored em "$x^2\ge 0$". Then, it can be further rephrased as "For each real number $x$, $P(x)$." In this case, we can observe how an open statement ($P(x)$) is converted to a statement (For each real number $x$, $P(x)$), and the phrase "for each" is a type of the Template:Colored em. Other phrases that are also universal quantifiers include "for every", "for all" and "whenever". The universal quantifier is usually denoted by $\mathrm{\forall }$ (an inverted "A"). After introducing this notation, the statement we mention can be further rephrased as "$\mathrm{\forall }x\in ℝ,x^2\ge 0$" (we also use some set notations here).

In general, we can use the universal quantifier to change an open statement $P(x)$ to a statement, which is "$\mathrm{\forall }x\in S,P(x)$" in which $S$ is a (universal) set (or domain) which restricts the input $x$.

Apart from the universal quantifier, another way to convert an open statement into a statement is using an Template:Colored em. Each of the phrases "there exists", "there is", "there is at least one", "for some" , "for at least one" is referred to as an Template:Colored em, and is denoted by $\mathrm{\exists }$ (an inverted "E"). For example, we can rewrite the statement "The square of some real number is negative." as "$\mathrm{\exists }x\in ℝ,x^2<0.$" (which is false).

In general, we can use the existential quantifier to change an open statement $P(x)$ to a statement, which is "$\mathrm{\exists }x\in S,P(x)$" in which $S$ is a (universal) set (or domain) which restricts the input $x$.

Another quantifier that is related to Template:Colored em quantifier is the Template:Colored em. Each of the phrases "there exists a unique", "there is exactly one", "for a unique", "for exactly one" is referred to as Template:Colored em, which is denoted by $\mathrm{\exists }!$. For example, we can rewrite the statement "There exists a unique real number $x$ such that $2x=0$." as "$\mathrm{\exists }!x\in ℝ,2x=0$." We can express the unique existential quantifier in terms of existential and universal quantifiers, by Template:Colored em "$\mathrm{\exists }!x\in S,P(x)$" as $$(\mathrm{\exists }x\in S,P(x))\wedge (\mathrm{\forall }{x}_1,x_2\in S,P(x_1)\wedge P(x_2)\to x_1=x_2)$$ where the left bracket is the existence part, and the right bracket is the uniqueness part. In words, the expression means

There exists $x\in S$ such that $P(x)$, AND for every $x_1,x_2\in S$, if $P(x_1)$ and $P(x_2)$, then $x_1=x_2$ (i.e., $x_1$ and $x_2$ are actually referring to the same thing, so there is Template:Colored em $x$ such that $P(x)$).

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

Negation of quantified statements

Template:Colored example From this example, we can see that the negation of the statement "$\mathrm{\exists }x\in S,P(x)$" is logically equivalent to "$\mathrm{\forall }x\in S,\sim P(x)$". Now, it is natural for us to want to know also the negation of the statement "$\mathrm{\forall }x\in S,P(x)$. Consider this: when it is not the case that $P(x)$ is true for each $x\in S$, it means that $P(x)$ is false for Template:Colored em $x\in S$. In other words, $\mathrm{\exists }x\in S,\sim P(x)$. Hence, we know that the negation of the statement "$\mathrm{\forall }x\in S,P(x)$" is logically equivalent to $\mathrm{\exists }x\in S,\sim P(x)$.

Quantified statements with more than one quantifier

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 $x$ and for each real number $y$, $xy$ is a real number." It can be written as "$\mathrm{\forall }x\in ℝ,\mathrm{\forall }y\in ℝ,xy\in ℝ$". When we interchange "$\mathrm{\forall }x\in ℝ$" and "$\mathrm{\forall }y\in ℝ$", 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 "$\mathrm{\forall }x,y\in ℝ,xy\in ℝ$" without any ambiguity.

For an example that involve two existential quantifiers, consider the statement "There exists an real number $x$ and an real number $y$ such that $xy$ is a real number." It can be written as "$\mathrm{\exists }x\in ℝ,\mathrm{\exists }y\in ℝ,xy\in ℝ$." Similarly, interchanging "$\mathrm{\exists }x\in ℝ$" and "$\mathrm{\exists }y\in ℝ$" does not affect the meaning of the statement (the statement still means "For at least one pair of real numbers $x$ and $y$, $xy$ is a real number.") Because of this, we can simply write the statement as "$\mathrm{\exists }x,y\in ℝ,xy\in ℝ$" 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 $x$, there exists an integer $y$ such that $y<x$." This can also be written as "$\mathrm{\forall }x\in \mathbb{Z},\mathrm{\exists }y\in \mathbb{Z},y<x$". 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 $x=13$, I can choose $y=-99,0$ or $12$. Indeed, for the integer $x$ chosen by you, I can always choose my $y$ as $x-1$ so that $y<x$.

Let's see what happen if we interchange "$\mathrm{\forall }x\in \mathbb{Z}$" and "$\mathrm{\exists }y\in \mathbb{Z}$". The statement becomes $\mathrm{\exists }y\in \mathbb{Z},\mathrm{\forall }x\in \mathbb{Z},y<x$, meaning that there exists an integer $y$ such that it is (strictly) smaller than Template:Colored em integer $x$! 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 $\mathrm{\exists }$, it Template:Colored em depend on the variable(s) introduced earlier in the statement, but Template:Colored em be independent from the variable(s) introduced later in the statement.

What does it mean? For example, consider the above example. Template:Colored em, we have $\mathrm{\forall }x\in \mathbb{Z},\mathrm{\exists }y\in \mathbb{Z},y<x.$. Then, since the variable $x$ appears Template:Colored em than the variable $y$ which associated to $\mathrm{\exists }$, $y$ Template:Colored em on $x$ (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 $x=13$, and I choose $y=12$. Then, $y<x$. However, if you change your choice to $x=9$, then my $y=12$ does not work, and I need to change my $y$ to, say, 8 so that $y<x$. Then, we can see that $y$ depends on $x$ in this case. Template:Colored em, we have $\mathrm{\exists }y\in \mathbb{Z},\mathrm{\forall }x\in Z,y<x$. In this case, the variable $x$ appears Template:Colored em than the variable $y$. Hence, the variable $y$ must be independent from $x$. That is, when such $y$ is determined, it needs to satisfy $y<x$ for each $x$ chosen, and the $y$ cannot change depend on what $x$ is. Indeed, $y$ cannot Template:Colored em depend on $x$, since $y$ is supposed to be determined when $x$ is not even introduced!

Exercises

In the following questions, $P,Q,R,S$ are statements.

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

1. $\sim P\to Q$
2. $P\to (\sim Q)$
3. $(P\vee Q)\to R$
4. $(P\wedge Q)\to (R\vee S)$
5. $(R\to S)\to (P\to Q)$

B. Negate the following statements:

1. $P\wedge Q$
2. $(P\vee Q)\wedge (R\wedge S)$
3. $(P\wedge \sim Q)\vee (\sim R\vee S)$