3

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

S.C.
  • 4,984
  • @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? – S.C. Feb 06 '20 at 00:26
  • 1
    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? – mrtaurho Feb 06 '20 at 00:27
  • @mrtaurho the skinny arrow simply denotes a biconditional connective. The thick arrow denotes logical equivalency. – S.C. Feb 06 '20 at 00:28
  • 1
    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? – mrtaurho Feb 06 '20 at 00:30
  • @mrtaurho my understanding of logical equivalence is that I need to make sure these statements have the exact same truth table for all possible models...whereas the portion in the parentheses seems to suggest I only need to demonstrate the one model (specifically when the statements are assigned values of true). – S.C. Feb 06 '20 at 00:32
  • 1
    Ah, I see. Then Ben Blum-Smith's answer should clear it up. – mrtaurho Feb 06 '20 at 00:34
  • When in doubt, read the definitions... :-) Tao's Index page 342: if: see implication, page 312. At page 312, implication is defined as the logical connective formalizing the "if..., then.." natural language syntactical construct. – Mauro ALLEGRANZA Feb 06 '20 at 14:54
  • Unfortunately, Tao's book does not define logical equivalence; it seems to me that the first occurrence is in Ex.3.1.5, "three statements are logically equivalent [when] any one of them implies the other two)." Thus, the Ex asks to prove: "if $A ⊆ B$, then $A ∪ B = B$" and "if $A ∪ B = B$, then $A ⊆ B$". – Mauro ALLEGRANZA Feb 06 '20 at 14:59

3 Answers3

4

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

Ben Blum-Smith
  • 20,766
  • Thank you for the response. The one question I have is in response to your phrasing, "...$P(x) \leftrightarrow Q(x)$ IN ALL SITUATIONS." All situations, to me, means all possible models. i.e. I also need to demonstrate that the biconditonal is behaving like a biconditional from all possible truth values of the propositions (so, for example, I need to show that when one proposition is false, the others are false...etc) – S.C. Feb 06 '20 at 00:41
  • 2
    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. – Ben Blum-Smith Feb 06 '20 at 00:56
  • 1
    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. – Ben Blum-Smith Feb 06 '20 at 00:57
  • 1
    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). – S.C. Feb 06 '20 at 01:02
  • 1
    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? – Ben Blum-Smith Feb 07 '20 at 03:13
  • Close enough! Thank you for the help. – S.C. Feb 07 '20 at 12:53
  • I think in your previous comment I've lost track of what you mean by "the biconditional". In my mind this is the statement "P implies Q AND Q implies P". This evaluates to false if P and Q do not have the same truth value because, for example, if P is true and Q is false, then "P implies Q" is false, therefore "P implies Q AND Q implies P" is false. – Ben Blum-Smith Feb 07 '20 at 22:42
  • Yes, I was under the impression that if I wanted to claim that a statement was a biconditional, I would have to also show that it is false when P and Q do not have the same truth values. But after understanding a little more about entailment, I see that we really only care about demonstrating when statements are true. So, for example, when someone says "Prove the biconditional statement"...what they really mean is "Show that this biconditional statement can result in truth". At least I think that is correct. – S.C. Feb 08 '20 at 14:48
  • No. I think that either you are not fully appreciating the strength of the statement "P implies Q", or else you are using a different meaning of "to prove" than the rest of us. (I am at this point quite engaged by the challenge of achieving full communication here, so I hope you'll stick with it! I won't be satisfied with "close enough" and I hope you won't be either!) A biconditional (i.e., the statement "P implies Q AND Q implies P") is false when P and Q have different truth values! And we do care about this! – Ben Blum-Smith Feb 08 '20 at 16:00
  • My second-to-last comment is a proof that the biconditional is false when P and Q have different truth values!

    It is a completely universal proof of this. I did not require any information about P and Q.

    In other words, any biconditional is false when P and Q have different truth values.

    You do not have to prove this for a given biconditional, not because it doesn't matter or people don't care, but because it's already been proven!

     – Ben Blum-Smith Feb 08 '20 at 16:03
  • Ohhhhh, interesting. So we don't "prove" false statements. We only "prove" true statements. Is there a reason for this? Why is it that "truths" necessitate formal proofs but falsehoods do not necessitate formal proofs? (I feel like we may be running into issues regarding what is meant by "proof" haha) – S.C. Feb 08 '20 at 16:17
  • What would it mean to prove a false statement? (If it's false, how would you prove it?) – Ben Blum-Smith Feb 08 '20 at 16:18
  • The easiest thing I could think of would be the act of demonstrating a counter example. – S.C. Feb 08 '20 at 16:20
  • (Yes I think the issue may be coming down to what is meant by "proof".) – Ben Blum-Smith Feb 08 '20 at 16:20
  • Giving a counterexample is proving that a given statement (say P) is false. (Of course we need to do this!) But then P is not the statement you're proving with the counterexample. The statement you are proving with the counterexample is "not-P". So you are still proving something true. – Ben Blum-Smith Feb 08 '20 at 16:22
  • 1
    Let us continue this discussion in chat. – Ben Blum-Smith Feb 08 '20 at 16:26
2

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • 1
    could you please differentiate logical equivalence in the context of sets versus logical equivalence in the context of propositional logic? – S.C. Feb 06 '20 at 02:06
  • 2
    @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. – Bram28 Feb 06 '20 at 14:07
  • 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)? – S.C. Feb 06 '20 at 14:10
  • 2
    @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. – Bram28 Feb 06 '20 at 14:24
  • @S.Cramer Yes, the phrase "logically equivalent" (analogous: "logically implies") in the given exercise may distractingly lead some of us to think about tautologies and logical validities. The weaker "equivalent in the context of some theory/ axiom system" (or simply "equivalent" without any modifier) is more technically accurate. – ryang Jan 31 '22 at 05:02
2

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.

Community
  • 1
Graham Kemp
  • 129,094
  • 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). – S.C. Feb 06 '20 at 12:35
  • 1
    It seems like logical equivalence in the context of predicate logic is really the idea of "reciprocal logical entailment". Is that correct? – S.C. Feb 06 '20 at 13:43