Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that

  • $(A\iff B)\iff C$
  • $A\iff (B\iff C)$

are equivalent statements.

One can brute-force a proof fairly easily (just write down the truth table). But is there a more intuitive reason why this associativity must hold?

share|improve this question
    
I don't know if looking at this as a Boolean algebra (with $+$ being the exclusive or) is more intuitive, but at least we know the two statements are equal to $A + B + C$. –  Tunococ Jul 10 '13 at 8:00
    
@Tunococ: Boolean algebra already has a symbol for addition. Exclusive or is usually denoted by $\oplus$ in that case. –  Asaf Karagila Jul 10 '13 at 8:12
    
@Tunococ: I haven't thought of that. Mapping truth values to $0,1$ and doing arithmetic mod two we have $A \iff B$ is the same as $1 + A + B$. That addition in mod two arithmetic is associative is certainly intuitive, but I don't know if this help say anything about the intuition behind the original question. –  Willie Wong Jul 10 '13 at 8:41
    
I wonder how "intuitive" such associativity may be claimed to be, as the property fails, for instance, for the canonical bi-conditional of well-known non-classical logics such as intuitionistic logic, or the main fuzzy logics. –  J Marcos Jul 10 '13 at 11:01
1  
@JMarcos: if you can elaborate on that, I think that will make a good answer! –  Willie Wong Jul 10 '13 at 11:36
show 2 more comments

4 Answers 4

up vote 9 down vote accepted

I would say that I personally don't feel that this equivalence is that intuitive. (Maybe it is because I have been thinking too constructively these days.) In classical logic, we have the isomorphism with the Boolean algebra, and that makes it possible to think of $A \leftrightarrow B$ as $A \oplus B \oplus 1$ where $\oplus$ is the exclusive OR. This makes quite a short proof of the associativity of the biconditional. To me, this is the most intuitive way I can think of to justify the associativity.

But as J Marcos mentioned, the equivalence is no longer true in intuitionistic logic. This may serve as an explanation why the equivalence is not supposed to be as intuitive.

(It is straightforward to find a counterexample using the topological model. I will just work out the tedious details for you. Assume $\mathbb R$ is the topological space of interest with the usual topology. Define the valuation $[\![\cdot]\!]$ by $[\![A]\!] = (-1, 1)$, $[\![B]\!] = (0, \infty)$ and $[\![C]\!] = (-\infty, -1) \cup (0, 1)$. It follows that \begin{align*} [\![A \leftrightarrow B]\!] & = [\![A \rightarrow B]\!] \cap [\![B \rightarrow A]\!] = \text{int}([\![A]\!]^c \cup [\![B]\!]) \cap \text{int}([\![B]\!]^c \cup [\![A]\!]) \\ & = (-\infty, -1) \cap (0, 1) = [\![C]\!] \\ [\![(A \leftrightarrow B) \leftrightarrow C]\!] & = [\![(A \leftrightarrow B) \to C]\!] \cap [\![C \to (A \leftrightarrow B)]\!]\\ & = \text{int}([\![A \leftrightarrow B]\!]^c \cup [\![C]\!]) \cap \text{int}([\![C]\!]^c \cup [\![A \leftrightarrow B]\!]) = \mathbb R \\ [\![B \leftrightarrow C]\!] & = [\![B \rightarrow C]\!] \cap [\![C \rightarrow B]\!] = \text{int}([\![B]\!]^c \cup [\![C]\!]) \cap \text{int}([\![C]\!]^c \cup [\![B]\!]) \\ & = (-\infty, 1) \cap (-1, \infty) = \mathbb R\\ [\![A \leftrightarrow (B \leftrightarrow C)]\!] & = [\![(B \leftrightarrow C) \to A]\!] \cap [\![A \to (B \leftrightarrow C)]\!] \\ & = \text{int}([\![B \leftrightarrow C]\!]^c \cup [\![A]\!]) \cap \text{int}([\![A]\!]^c \cup [\![B \leftrightarrow C]\!]) \\ & = [\![A]\!] \cap \mathbb R = (-1, 1) \ne \mathbb R \end{align*} where int is the interior and $^c$ is the complement.)

share|improve this answer
3  
Ah thanks. This post is very educational for me. –  Willie Wong Jul 11 '13 at 9:26
    
From this answer I infer that Tunococ feels the associativity of addition modulo 2 not intuitive or that negation doesn't intuitively seem like an isomorhpism between concrete algebras of 2 elements. Only one of these? Which one? Or both? –  Doug Spoonwood Jul 12 '13 at 16:50
2  
@DougSpoonwood I would rather say that the classical logic is not the only way to interpret a propositional sentence. –  Tunococ Jul 12 '13 at 21:00
add comment

Do you find it intuitive that addition modulo 2 qualifies as associative? Do you find it intuitive that two-valued negation N can qualify as an isomorphism between concrete algebras ({0, 1}, X) and ({0, 1}, Y) where X and Y indicate binary operations? Well, if you answer yes to both questions, then if you let E-2 indicate logical equivalence, from the associativity of addition modulo 2 the negation isomorphism gives you that E-2 associates also.

In a paper called The Equivalential Calculus (you can read the paper in either of the volumes Polish Logic 1920-1939 or Jan Lukasiewicz: Selected Works) J. Lukasiewicz writes "Now, I long ago noted that equivalence is also associative, and accordingly I established the following thesis in the symbolism of Principia p≡.q≡r:≡:p≡q.≡r This thesis, which in my symbolism can be expressed by EEpEqrEEpqr, is cited by Tarski in his doctoral thesis of 1923...

A2. p≡.q≡r:≡:p≡q.≡r

The second axiom [A2] is the law of associativity for equivalence, discovered by myself."

Unfortunately though Lukasiewicz does not give any reference to any sort of paper where he first discovered this. So, I have no idea as to how he figured it out.

From a natural deduction framework, I do not think the associativity of logical equivalence intuitive at all, even if you know one particular natural deduction system fairly well. I tried to prove it once without any derived rules of inference, and then found a shorter proof. The shorter proof took up 141 lines. Someone else tried proving it with derived rules of inference, and proved one of the required conditionals in 47 lines.

In what gets called Lukasiewicz 3-valued logic logical equivalence takes on the value of truth along the diagonal, the value of falsity at the other corners not covered so far, and the third truth value elsewhere. In other words, where 0 indicates falsity, .5 the third truth value, and 1 truth we have the following matrix for logical equivalence E:

  E   0  .5  1
  0   1  .5  0
  .5  .5  1  .5 
  1   0  .5  1

In reverse Polish notation logical equivalence goes pqrEEpqErEE. So, let p=.5, q=.5, and r=0. Then we obtain:

.5 .5 0 E E .5 .5 E 0 E E= .5 .5 E 1 0 E E=1 0 E=0.

So, in Lukasiewicz 3-valued logic, the associativity of logical equivalence can take on the falsity value "0" and thus doesn't even qualify as a quasi-tautology (a quasi-tautology never takes on the value of falsity, the law of Clavius CCNppp comes as a quasi-tautology in Lukasiewicz 3-valued logic).

share|improve this answer
1  
Hi Doug: thanks for your answer. Is $\equiv$ the symbol you are thinking of? In that case in mathmode enter \equiv. –  Willie Wong Jul 15 '13 at 8:29
    
@WillieWong Thanks! –  Doug Spoonwood Jul 15 '13 at 13:42
add comment

This might be one of the situations where a more general (and therefore stronger) result is more intuitive (depending on how your intuition works). The result I have in mind is that, if you combine any list $\mathcal L$ of formulas (not just three like the $A,B,C$ in the question) by $\iff$, then no matter how you put the parentheses to make it unambiguous, the resulting formula is true if and only if an even number of the formulas in the list $\mathcal L$ are false. In other words, iterated $\iff$ amounts to a parity connective, regardless of the placement of parentheses.

share|improve this answer
    
But that's just passing the buck, no? Why is it intuitive that iterated $\iff$ amounts to a parity connective? Cf. my comment above. –  Willie Wong Jul 16 '13 at 7:32
add comment

The reason it's hard to intuit this is that we're used to thinking of "$(A\Leftrightarrow B)\Leftrightarrow C$" as stating something about the sentences "$A\Leftrightarrow B$" and "$C$", but nothing about "$A$" (or "$B$") directly: converting it to a sentence, "$A\Leftrightarrow(B\Leftrightarrow C)$", that speaks about "$A$" directly, is counterintuitive.

So to understand the equivalence between "$(A\Leftrightarrow B)\Leftrightarrow C$" and "$A\Leftrightarrow(B\Leftrightarrow C)$", we need to think of them not as sentences about "$A\Leftrightarrow B$" and "$C$", respectively "$A$" and "$B\Leftrightarrow C$", but as sentences about "$A$", "$B$", and "$C$" directly.

What does "$(A\Leftrightarrow B)\Leftrightarrow C$" say about "$A$", "$B$", and "$C$"?

  1. If "$C$" and "$A$" hold, so does "$B$".
  2. If "$B$" and "$C$" hold, so does "$A$".
  3. If "$A$" and "$B$" hold, so does "$C$".
  4. If "$A$" and "$B$" both are false, "$C$" holds.

So the crucial point in understanding the equivalence between "$(A\Leftrightarrow B)\Leftrightarrow C$" and "$A\Leftrightarrow(B\Leftrightarrow C)$" is understanding the equivalence between

4. If "$A$" and "$B$" both are false, "$C$" holds.

and

4$'$. If "$B$" and "$C$" both are false, "$A$" holds.

(which is clear).

The trick here was looking only at the direct statements (e.g. if "$C$" and "$A$" hold, so does "$B$"): their contrapositives (e.g. if "$C$" holds but "$B$" does not, then "$A$" is false) are less intuitive.

share|improve this answer
    
This is not really different from the "truth table" proof I alluded to in the question statement. –  Willie Wong Jul 16 '13 at 7:29
    
@WillieWong, all of logic boils down ZF: nothing is "really different". This write-up is more intuitive than a real truth-table proof, at least to me. –  msh210 Jul 16 '13 at 19:37
    
"all of logic boils down ZF" that's a rather narrow view of the word logic‌​. –  Willie Wong Jul 17 '13 at 7:59
    
@WillieWong, I meant "boils down to ZF", and I was referring to all of the logic assumed by the question, not all of logic altogether. –  msh210 Jul 17 '13 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.