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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s