29
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ 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$. $\endgroup$
    – Tunococ
    Jul 10, 2013 at 8:00
  • $\begingroup$ @Tunococ: Boolean algebra already has a symbol for addition. Exclusive or is usually denoted by $\oplus$ in that case. $\endgroup$
    – Asaf Karagila
    Jul 10, 2013 at 8:12
  • $\begingroup$ @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. $\endgroup$ Jul 10, 2013 at 8:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – J Marcos
    Jul 10, 2013 at 11:01
  • 1
    $\begingroup$ @JMarcos: if you can elaborate on that, I think that will make a good answer! $\endgroup$ Jul 10, 2013 at 11:36

4 Answers 4

20
$\begingroup$

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) \cup (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]\!]) \\ & = (-1, 0) \cup (0, 1) = A - \{0\}\\ [\![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]\!]) \\ & = \mathbb R - \{0\} \ne \mathbb R \end{align*} where int is the interior and $^c$ is the complement.)

$\endgroup$
4
  • 3
    $\begingroup$ Ah thanks. This post is very educational for me. $\endgroup$ Jul 11, 2013 at 9:26
  • $\begingroup$ 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? $\endgroup$ Jul 12, 2013 at 16:50
  • 3
    $\begingroup$ @DougSpoonwood I would rather say that the classical logic is not the only way to interpret a propositional sentence. $\endgroup$
    – Tunococ
    Jul 12, 2013 at 21:00
  • 2
    $\begingroup$ Shorter version: By definition of ¬, (a ↔ 0) ↔ ¬a. If ↔ is associative, this means a ↔ (0 ↔ ¬a). By definition of ¬, this means a ↔ ¬¬a. But double negation elimination does not hold for intuitionistic logic. $\endgroup$
    – user76284
    Jul 19, 2022 at 2:01
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ But that's just passing the buck, no? Why is it intuitive that iterated $\iff$ amounts to a parity connective? Cf. my comment above. $\endgroup$ Jul 16, 2013 at 7:32
3
$\begingroup$

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).

$\endgroup$
2
  • 1
    $\begingroup$ Hi Doug: thanks for your answer. Is $\equiv$ the symbol you are thinking of? In that case in mathmode enter \equiv. $\endgroup$ Jul 15, 2013 at 8:29
  • $\begingroup$ @WillieWong Thanks! $\endgroup$ Jul 15, 2013 at 13:42
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ This is not really different from the "truth table" proof I alluded to in the question statement. $\endgroup$ Jul 16, 2013 at 7:29
  • $\begingroup$ @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. $\endgroup$
    – msh210
    Jul 16, 2013 at 19:37
  • 3
    $\begingroup$ "all of logic boils down ZF" that's a rather narrow view of the word logic. $\endgroup$ Jul 17, 2013 at 7:59
  • $\begingroup$ @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. $\endgroup$
    – msh210
    Jul 17, 2013 at 15:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .