## The following are equivalent

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:

1. $m$ is even.
2. $m+2$ is even.
3. $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
This entry was posted in Uncategorized. Bookmark the permalink.

### 4 Responses to The following are equivalent

1. Is this related to the problem of expressions like “-3 < -2 < -1" resulting in false in most programming languages? I've had more than one mentee make this error.

• Yes and no :). No, in the sense that your example is a problem in most languages (like C++) because of Boolean promotion, but in this case the values being compared are already Boolean.

Yes, in the sense that the corresponding C++ expression (p[1] == p[2] == p[3] == … == p[n]), where the p[k] are of type bool, has the same problem as Rosen’s notation; this “looks” like it might evaluate to true iff all of the p[k] are equal and false otherwise, but it doesn’t.

The *intended* meaning of this expression is essentially how Python treats chained comparisons, with an implicit AND stuck in between each consecutive binary comparison.

2. Alex Nelson says:

I thought $p_1 \leftrightarrow p_2 \leftrightarrow \ldots \leftrightarrow p_n$ was short hand for $(p_1 \leftrightarrow p_2) \land (p_{2} \leftrightarrow p_{3}) \land \ldots \land (p_{n-1} \leftrightarrow p_n)$

• Right! The problem, IMO, is that this is never mentioned anywhere in the text, and to a student, it isn’t clear that this is “special” notation, since it’s well-formed as is. Rosen even follows up with the tautology justifying the usual “chain-of-implications” approach to proving equivalences like this, formatted as:

$p_1 \leftrightarrow p_2 \leftrightarrow \ldots \leftrightarrow p_n \leftrightarrow (p_1 \to p_2) \land (p_2 \to p_3) \land \ldots \land (p_n \to p_1)$

This site uses Akismet to reduce spam. Learn how your comment data is processed.