July | 2017 | Possibly Wrong

I have been reviewing Rosen’s Discrete Mathematics and Its Applications textbook for a course this fall, and I noticed an interesting potential pitfall for students in the first chapter on logic and proofs.

Many theorems in mathematics are of the form, “ $p$ if and only if $q$ ,” where $p$ and $q$ are logical propositions that may be true or false. For example:

Theorem 1: An integer $m$ is even if and only if $m+2$ is even.

where in this case $p$ is “ $m$ is even” and $q$ is “ $m+2$ is even.” The statement of the theorem may itself be viewed as a proposition $p \leftrightarrow q$ , where the logical connective $\leftrightarrow$ is read “if and only if,” and behaves like Boolean equality. Intuitively, $p \leftrightarrow q$ states that “ $p$ and $q$ are (materially) equivalent; they have the same truth value, either both true or both false.”

(Think Boolean expressions in your favorite programming language; for example, the proposition $p \land q$ , read “ $p$ and $q$ ,” looks like p && q in C++, assuming that p and q are of type bool. Similarly, the proposition $p \leftrightarrow q$ looks like p == q in C++.)

Now consider extending this idea to the equivalence of more than just two propositions. For example:

Theorem 2: Let $m$ be an integer. Then the following are equivalent:

$m$ is even.
$m+2$ is even.
$m-2$ is even.

The idea is that the three propositions above (let’s call them $p_1, p_2, p_3$ ) always have the same truth value; either all three are true, or all three are false.

So far, so good. The problem arises when Rosen expresses this general idea of equivalence of multiple propositions $p_1, p_2, \ldots, p_n$ as

$p_1 \leftrightarrow p_2 \leftrightarrow \ldots \leftrightarrow p_n$

Puzzle: What does this expression mean? A first concern might be that we need parentheses to eliminate any ambiguity. But almost unfortunately, it can be shown that the $\leftrightarrow$ connective is associative, meaning that this is a perfectly well-formed propositional formula even without parentheses. The problem is that it doesn’t mean what it looks like it means.

Reference:

Rosen, K. H. (2011). Discrete Mathematics and Its Applications (7th ed.). New York, NY: McGraw-Hill. ISBN-13: 978-0073383095

Possibly Wrong

On science, mathematics, and computing

Monthly Archives: July 2017

The following are equivalent