2
$\begingroup$

In the math book that I am studying, the reader is asked to show that several statements are "logically equivalent"...and then in parentheses, the author says "[i.e.] any one of them implies the other".

After scouring this website (and others) for the differences between biconditionals and logical equivalencies, I must say that this question has me quite confused. I understand that when the biconditional $P(x) \leftrightarrow Q(x)$ yields a tautology, we claim that the propositions $P(x)$ and $Q(x)$ are logically equivalent...$P(x) \iff Q(x)$.

This is where my confusion arises. At first it seems like I need to demonstrate that the truth tables are identical...but then the advice in the parentheses seems to suggest that I only need to prove that the biconditional is true when the propositions are true.

Or does proving that the biconditional is true when the propositions are true necessarily imply that the propositions are logically equivalent?

Here is the exact question in the book (Tao's Analysis I):

Exercise 3.1.5. Let $A,B$ be sets. Show that the three statements $A\subseteq B$, $A\cup B=B$, $A\cap B=A$ are logically equivalent (any one of them implies the other two).

$\endgroup$
  • $\begingroup$ @mrtaurho I am not sure I understand your response. Also, I think our notation may be different. You are using your "thick" double arrow to denote a biconditional? $\endgroup$ – S.Cramer Feb 6 at 0:26
  • 1
    $\begingroup$ It might be the case that I either misread your question or your notation. What exactly defines the difference between $\leftrightarrow$ and $\iff$ for you? $\endgroup$ – mrtaurho Feb 6 at 0:27
  • $\begingroup$ @mrtaurho the skinny arrow simply denotes a biconditional connective. The thick arrow denotes logical equivalency. $\endgroup$ – S.Cramer Feb 6 at 0:28
  • 1
    $\begingroup$ When working with them in a setting like the exercise you gave; where's the difference? From what I understand that's your question, isn't it? Could you give an example for both (i.e. a biconditional connective and logically equivalence) which differ in a meaningful way? $\endgroup$ – mrtaurho Feb 6 at 0:30
  • 1
    $\begingroup$ Ah, I see. Then Ben Blum-Smith's answer should clear it up. $\endgroup$ – mrtaurho Feb 6 at 0:34
4
$\begingroup$

I do not have a background in formal logic, but from the point of view of mathematics outside formal logic (which is the point of view from which Tao's book is written, for example), "Prove $P(x)$ and $Q(x)$ are equivalent" means the same thing as "Prove $P(x)$ and $Q(x)$ imply each other." There is no difference between the equivalence and the biconditional.

However, in all cases, you have to show more than that the biconditional holds when the statements hold. That's vacuous. If $P(x)$ and $Q(x)$ both hold, then $P(x)\leftrightarrow Q(x)$ holds too, just by truth-table reasoning. What you have to prove is that $P(x)\leftrightarrow Q(x)$ in all situations. Another way to say this is that you need to prove that whenever $P(x)$ holds, $Q(x)$ also holds, and whenever $Q(x)$ holds, $P(x)$ also holds.

In practice, this is not usually done by considering truth tables, but instead just by reasoning directly with the statements. For example:

Suppose $A\subseteq B$. Then, unioning both sides with $B$ and observing that this operation preserves the relation of containment, we can conclude that $A\cup B\subseteq B\cup B$. But $B\cup B=B$, and we can conclude $A\cup B\subseteq B$. Meanwhile, Also $A\cup B\supseteq B$ since $A\cup B$ is a union of $B$ and something else. Since $A\cup B\subseteq B$ and $A\cup B\supseteq B$, we can conclude $A\cup B=B$. We have thus proven that $A\subseteq B\Rightarrow A\cup B = B$.

You do a similar thing to show that $A\cup B = B \Rightarrow A\subseteq B$, etc.

Addendum: Per the discussion below in comments, I think the heart of the matter is that while it might at first appear that proving the two implications "P implies Q" and "Q implies P" is strictly weaker than proving equivalence, it is actually no weaker!

"P implies Q" is the same thing as "It is impossible for $P(x)$ to hold without $Q(x)$ also holding." Meanwhile, "Q implies P" is the same thing as "It is impossible for $Q(x)$ to hold without $P(x)$ holding." Thus, if you prove both implications, you have established that it is impossible for $P$ and $Q$ to have different truth values in any model. In other words, they have the same truth value in every model. This reasoning is not contingent on assuming they have the same truth value: the claim that they always have the same truth value follows as a consequence of the pair of statements "P implies Q" and "Q implies P".

$\endgroup$
  • 2
    $\begingroup$ After reflecting on this for a few minutes, I think I figured out something about what is bothering you. (??) The thing is, if you prove that "if P holds, then Q holds", then you have also simultaneously [with no additional work] proven that "if Q is false, then P is false." To put it another way, if you can show that in all models in which P holds, Q also holds, then you have also shown that in any model in which Q fails to hold, then P fails to hold. Both these statements are (equivalent) variants of the statement that it is impossible for a model to satisfy P without satisfying Q. $\endgroup$ – Ben Blum-Smith Feb 6 at 0:56
  • 1
    $\begingroup$ As a consequence, if you can show that "P implies Q" and also "Q implies P", then you have simultaneously [with no added work] shown that "not P implies not Q" [this follows from "Q implies P"] and "not Q implies not P" [this follows from "P implies Q"]. Let me know if this clears it up; if so, I'll add a version of these ideas to the answer itself. $\endgroup$ – Ben Blum-Smith Feb 6 at 0:57
  • 1
    $\begingroup$ Yes! This is most definitely part of the confusion. Thank you for touching on this part; however, this only establishes that the biconditional is true in the "appropriate" conditions. (i.e. a biconditional is true when both P and Q have the same logical value...TT=T and FF=T). To fully satisfy a biconditional, though, don't we have to demonstrate that the biconditional evaluates to false when P and Q do NOT have the same truth value? (I think this is the crux of my issue, namely that we are only demonstrating when the biconditional evaluates to "True"...hopefully I didn't lose you). $\endgroup$ – S.Cramer Feb 6 at 1:02
  • 1
    $\begingroup$ My point above is that "P implies Q" is the same as the statement "P and not-Q is impossible". "Q implies P" is the same as "Q and not-P is impossible". Taken together, these two statements mean that P and Q always have the same truth value; in other words, they have the same truth value in every model. So if you prove both "P implies Q" and "Q implies P", then you actually have a proof that the biconditional holds in all models. Does that answer? $\endgroup$ – Ben Blum-Smith Feb 7 at 3:13
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Ben Blum-Smith Feb 8 at 16:26
2
$\begingroup$

In the math book that I am studying, the reader is asked to show that several statements are "logically equivalent"...and then in parentheses, the author says "[i.e.] any one of them implies the other".

This is where my confusion arises. At first it seems like I need to demonstrate that the truth tables are identical...but then the advice in the parentheses seems to suggest that I only need to prove that the biconditional is true when the propositions are true.

The claim being made by the text is that a set of propositional statements will be logical equivalents when any one of them will logically entail another.   That "any" indicates a universal claim: all.

That is that when $P\Rightarrow Q$, $P\Rightarrow R$, $Q\Rightarrow R$, $Q\Rightarrow P$, $R\Rightarrow P$, and $R\Rightarrow Q$ all hold, then and only then do $P\Leftrightarrow Q$, $Q\Leftrightarrow R$, and $R\Leftrightarrow P$ all hold. (And so forth for more than three statements.)

However, it is sufficient to prove a cyclic chain such as: $P\Rightarrow Q$, $Q\Rightarrow R$, and $R\Rightarrow P$ and let Hypothetical Syllogism take care of the rest.

$\endgroup$
  • $\begingroup$ so "logical equivalency", in this context, takes on a different meaning from the one that I described? (For example, based on my definition, i.e. when two propositions have the same truth values across all models, the implication and the contrapositive connectives are logically equivalent). $\endgroup$ – S.Cramer Feb 6 at 12:35
  • 1
    $\begingroup$ It seems like logical equivalence in the context of predicate logic is really the idea of "reciprocal logical entailment". Is that correct? $\endgroup$ – S.Cramer Feb 6 at 13:43
1
$\begingroup$

This is where my confusion arises. At first it seems like I need to demonstrate that the truth tables are identical...but then the advice in the parentheses seems to suggest that I only to prove that the biconditional is true when the propositions are true.

False on both accounts!

First: A truth-table wil do you no good for this problem. Truth-tables work nicely for problems in propositional logic, and if this would be a propositional logic problem, then indeed showing that their truth-tables are identical would indeed show logical equivalence ... but this is not a propositional logic problem; these statements are about sets.

Indeed, I would get it out of your head that the way to solve this problem is to show that the truth-functional biconditional between any pair of the statements is true. Again, this is not a propositional logic problem. Instead, you should just directly show that all three statements are logically equivalent.

Second: I have no idea where and how or why you get the idea that you have to show that the biconditional is true "when the propositions are true". Instead, you show that if one of the propositions is true, then the other two are true as well. To be precise: you have to show that if the first is true, then the second and third are true, but you also have to show that if the second is true, then the first and the second are true, and that if the third is true, then the first and the second are true. If you do all that, then you will have shown that the biconditional between any two of them is a logical truth ... but more to the point: that they are all logically equivalent.

Now, this makes it sounds like you have to show six logical implications ... but in fact just three of them will suffice: if you can show that the first implies the second, that the second implies the third, and that the third implies the first, then it is easy to see that they all imply each other.

$\endgroup$
  • 1
    $\begingroup$ could you please differentiate logical equivalence in the context of sets versus logical equivalence in the context of propositional logic? $\endgroup$ – S.Cramer Feb 6 at 2:06
  • 1
    $\begingroup$ @S.Cramer Well, to be exact, the three statements given in the exercise are not logically equivalent, but rather what you might call set-theoretically equivalent. That is: you cannot derive the statements from each other purely on the basis of logical principles, be they from propositional or first-order logic, but you can derive them once you add the standard axioms for set-theory. $\endgroup$ – Bram28 Feb 6 at 14:07
  • $\begingroup$ hmmmm. Would you agree that "reciprocal logical entailment" is an okay way of describing logical equivalence in the context of set theory (or any theory founded on axioms)? $\endgroup$ – S.Cramer Feb 6 at 14:10
  • 1
    $\begingroup$ @S.Cramer "reciprocal logical entailment" is really the same thing as logical equivalence, and does still not refer to the fact that set-theoretic axioms are assumed. So, it should be "set-theoretic reciprocal logical entailment" or "set-theoretic logical equivalence" ... but even that is a mouthful. I think "set-theoretic equivalence" captures what we want quite nicely; logic is always presumed in any field of mathematics, so no need to refer to that. $\endgroup$ – Bram28 Feb 6 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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