A. B. Clemons

2May/120

Late April/Early May Update

With the Troy University Chancellor's Fellowship Symposium at the end of April and finals around the corner for the beginning of May, I have been quite busy. I have a draft of the proof by contrapositive section. I also have a rough idea of a proof by induction section. These two posts will round off all that I want to do with the mathematical logic and proof techniques notes.

I'll look over the old notes over the next few weeks to expand them out by adding extra examples. I personally hate definition-theorem-proof style exposition and don't think that you ought to suffer through it either.

Filed under: Uncategorized No Comments

10Apr/120

Direct Proof

Clearly, trivial and vacuous proofs can only be used for a very small subset of propositions. We must therefore consider a more general approach to prove a larger body of propositions. In this installment, we discuss one these approaches and give a few examples of how it might be implemented.

Suppose that we are given an implication. We employ a direct proof to show that the conclusion must be true when we assume the hypothesis to be given. That is: given $P\Rightarrow Q$ , assume $P=True$ , and show $Q=True$ .

The direct proof is one of the most widely used proof techniques. Its popularity does not necessarily stem from the ease with which one can prove a proposition directly. To the contrary, the direct proof of a proposition can be counter-intuitive at first attempt. Nonetheless, most mathematicians prefer the approach when reading mathematical literature. Reasons for preference vary from technical concerns to pure aesthetics. Regardless of the reason, the rule of thumb is that if a direct proof can be employed, then it ought to be. Lest the stodgy old mathematicians rip apart our theses in our sleep, we ought employ it too !

Before we begin an example, we ought to establish the algebraic properties of the integers. We will take these properties axiomatically (without further proof).

Axiom: The Algebraic Properties of the Integers

Let $a$ , $b$ , and $c$ be integers. We then have the following

Closure Properties of Addition, Subtraction, and Multiplication

The sum of integers, i.e. $a+b$ , is an integer.
The difference of integers, i.e. $a-b$ , is an integer. (Note: There is no loss of generality to consider the difference of two integers as a sum. I.e. $a-b = a + (-b)$ .)
The multiplicative product of integers, i.e. $a\cdot b$ , is an integer.

Associative Properties of Addition and Multiplication

$(a+b)+c=a+(b+c)$
$(a\cdot b)\cdot c = a\cdot (b\cdot c)$

Commutative Properties of Addition and Multiplication

$a+b=b+a$
$a\cdot b = b \cdot a$

Multiplicative Distribution Property

$a \cdot (b+c) = a \cdot b + a \cdot c$

Additive Identity

$a + (-a) = 0$

Define: An integer $z$ is even if there exists an integer $x$ such that $z=2x$ . Else, $z$ is odd. That is, $z=2x+1$ for some integer $x$ .

We can now explore an example of a proposition with which we may employ a direct proof. Let us consider the following proposition

If $m$ and $n$ are even integers, then $m+n$ is an even integer.

Proof: Suppose that $m$ and $n$ are even integers. Since $m$ and $n$ , there exist integers $x$ and $y$ such that $m=2x$ and $n=2y$ . We then observe

$m+n=2x+2y=2(x+y)$

Since the sum of integers is an integer, the term $x+y$ is an integer, and $2(x+y)$ is by definition even. Hence, $m+n$ is an even integer.

Thus, if $m$ and $n$ are even integers, then $m+n$ is an even integer. QED

Proof Analysis: We have employed a direct proof of the proposition. We first assumed that $m$ and $n$ are even integers. Using the definition of even, we then rewrote $m$ and $n$ . At this point, we took the equation in the conclusion, $m+n$ , and plugged in the new values of $m$ and $n$ . This yields 2 times the sum of two integers. By the definitions of even, this new term must be even.

We have axiomatically assumed that right multiplication of integers is distributive. We can employ a direct proof to show that left multiplication of integers is likewise distributive. That is

$\forall a,b,c \in \mathbb{Z}, (b+c) \cdot a = b \cdot a + c \cdot a$

Proof Strategy: We have to be a little more cautious for this proof. We recall that to employ a direct proof we must first assume the hypothesis. However, what is the hypothesis of the above proposition? In short, the hypothesis is the universal quantifier. When dealing with a universal quantifier, we will often choose arbitrary elements to represent the entire set we wish to discuss. Thus, we can rewrite our proposition as

If $a$ , $b$ , and $c$ are integers, then $(b+c) \cdot a = b \cdot a + c \cdot a$

We now have a standard implication with which we can employ a direct proof. However, how will the mere property of " $a$ , $b$ , and $c$ are integers" give the conclusion? In the previous example. it was obvious - we rewrite using the definition of even. We then plug-and-chug. In this example, we will use the axiomatic algebraic properties of integers. The application will be a little more elegant, but it is tangible nonetheless.

Proof: Suppose that $a$ , $b$ , and $c$ are integers. The multiplicative commutative property and additive closure property gives $a \cdot (b+c) = (b+c) \cdot a$ . We then have $(b+c) \cdot a = a \cdot b + a \cdot c$ .

The multiplicative commutative property then gives $a \cdot b + a \cdot c = b \cdot a + c \cdot a$ .

Hence, $(b+c) \cdot a = b \cdot a + c \cdot a$ .

Thus, $\forall a,b,c \in \mathbb{Z}, (b+c) \cdot a = b \cdot a + c \cdot a$ . QED

Proof Analysis: As mentioned in the proof strategy, the connection between " $a$ , $b$ , and $c$ are integers" and left multiplicative distribution of integers is not as obvious as the first example. This is okay. The connection may not always be obvious, and even if it is obvious, we will rarely achieve a logical connection in a single step (as was seen in the first example).

Tagged as: direct proof No Comments

18Mar/12Off

Collecting the Notes

In the next few days, I am going to set up a page which collects the Mathematical Logic and Proof Techniques Notes in a more coherent manner. Until then, please excuse the mess that the category link gives.

Filed under: News Comments Off

18Mar/12Off

Trivial and Vacuous Proofs

A mathematical proposition which is taken a true without proof is called an axiom. A proof is a deduced form of reasoning in which truth of one proposition is derived from the assumed validity of a set of axioms. That is a proof is a method of determining if when given a set of axioms assumed to be true, then some mathematical proposition is shown to be true.

Note: The proofs which we will write in the next few sections will not be "slick" or terse. When we read mathematical literature, it is often the case that proofs can be terse or vague, and it has been told to us by our professors and colleagues that we ought to emulate this style. However, clarity should never be sacrificed for brevity. We do, after all, want others to understand our proofs! Upon first proving a mathematical proposition, it is good practice to write every detail of a proof in what I call Sesame-Street-style prose. We can then revisit our proof an remove the excessive details.

Trivial Proofs

Consider two propositions $P$ and $Q$ on a set $S$ . Consider the implication $P\Rightarrow Q$ . If $Q$ is a tautology, then $P\Rightarrow Q$ is true. By showing that $Q$ is a tautology, we employ what is called a trivial proof of the implication $P\Rightarrow Q$ .

Consider the following proposition:

Let $n,k\in \mathbb{Z}$ . If $n^{2k+1}<0$ , then $2n$ is even.

Proof: We recall that the definition of an even integer is given by the following: an integer $x$ is even if it can be written in the form of $x=2y$ for some integer $y$ . We note that $2n$ must then be even. Thus, the implication, if $n^{2k+1}<0$ , then $2n$ is even, is trivially true. QED

We observe that in order to employ the trivial proof of our proposition we relied on the axiomatic definition of even integer. Once we had recalled this axiomatic definition, it was only necessary to note that the conclusion was always true. The hypothesis never even enters our considerations!

We note that we use the phrase "... is trivially true" to alert the reader that we employed a trivial proof.

We finally note that we used the italicized term "Proof" to alert the reader that the proof had begun, and we used the emboldened term "QED" which is the acronym for the Latin statement "Quod Erat Demonstrandum" ("That which has been shown."). Modern literature usually make use of the tombstone,□, to end a proof. Unfortunately, our technological medium is not yet optimized to use the tombstone, and we will employ the term "QED" to end our proofs.

Vacuous Proofs

Consider two propositions $P$ and $Q$ on a set $S$ . Consider the implication $P\Rightarrow Q$ . For the implication given $P\Rightarrow Q$ in which $Q$ is a tautology, we have that the contrapositive of $P\Rightarrow Q$ gives $\neg Q\Rightarrow \neg P$ . We define a vacuous proof as the contrapositve of a trivial proof.That is, if $P$ is a contradiction, then $P\Rightarrow Q$ is true.

Consider the contrapositve of our previous example:

Let $n,k\in \mathbb{Z}$ . If $2n$ is odd, then $n^{2k+1}\geq 0$ .

Proof: We recall that the definition of an odd integer is given by the following: an integer $x$ is even if it can be written in the form of $x=2y+1$ for some integer $y$ . We note that $2n$ can never be odd. Thus, the implication, if $2n$ is odd, then $n^{2k+1}\geq 0$ , is vacuously true. QED

As with the trivial proof, we used the term "Proof" to tip off the reader that the proof had begun, and we used the term "QED" to signal the proof's end. We also used the phrase "is vacuously true" to signal that we had employed a vacuous proof. Finally, we note that we used the axiomatic definition of odd integer to show that the hypothesis was a contradiction.

A Final Word

In the introduction, we said that we would use Sesame-Street-style prose in the first work through of a proof. I would like to revisit our trivial proof of the implication: Let $n,k\in \mathbb{Z}$ . If $n^{2k+1}<0$ , then $2n$ is even. We had written:

A terse way of writing the above is as follows:

Proof: Since $2n$ must be even, the implication is trivially true. QED

Tagged as: axiom, implication, QED, trivial proof, vacuous proof Comments Off

18Mar/12Off

Addendum to Propositional Logic

Before we begin discussing proof techniques, we need to expand a few of the concepts from the previous post.

Suppose that $P$ and $Q$ are propositions on a set $S$ . Consider the implication $P\Rightarrow Q$ .

The converse of $P\Rightarrow Q$ is the proposition $Q\Rightarrow P$ .

The inverse of $P\Rightarrow Q$ is $\neg P\Rightarrow \neg Q$ .

The contrapositve of $P\Rightarrow Q$ is $\neg Q\Rightarrow \neg P$ . Note that the contrapositive of a proposition is the inverse of the converse of that proposition. Also, note that the contrapositive of a statement has precisely the same truth values as the original statement.

We leave it to the reader to draw truth tables to verify the above observations/assertions.

Tagged as: contrapositve, converse, implication, inverse Comments Off

Older Entries »

A. B. Clemons Mathematics, Physics, and Philosphy

Late April/Early May Update

Direct Proof

Collecting the Notes

Trivial and Vacuous Proofs

Trivial Proofs

Vacuous Proofs

A Final Word

Addendum to Propositional Logic

Subscribe to Blog via Email

Pages

Links

Archives

Meta