1

In other words, how do you prove $A\rightarrow(B\rightarrow C)$ and $(A \rightarrow B) \rightarrow C$ are not equivalent?

I've tried material implications, indirect proofs, modus ponens, and modus tollens galore. I can't seem to figure it out.

I know that the interpretation where all A, B, and C are false makes the former true and the latter false, but how do I prove it Fitch style?

(Please let me know if there's anything I can do to improve the quality of the question.)

Update: In case I didn't make it clear, I need ¬{[A→(B→C)]↔[(A→B)→C]} only, and only from rules of inference.

Update: So, I should have caught way sooner (when I very first started spinning my tires very late at night) that by the points @danielschepler and @MauroALLEGRANZA made, I cannot show that they are not equivalent Fitch style (as the equivalence is not a contradiction and thus the negation is not a tautology, but rather they are each contingent). If someone wants to write something about this as an answer for future people with the same problem, please do and I'll mark it as the answer. (That's the right move in this situation, right?)

user3146
  • 685
  • Fitch style arguments allow us to prove that certain things are equivalent. As far as I know, there is no way to show that two formulas are inequivalent using these techniques. After all, you would need to show that there is no derivation ending with the equivalence of two formulas. There's a surprising amount to say here, for instance about the duality between syntax and semantics, but the crux of the issue is that you're using the wrong tool for the job. Looking for an interpretation that gives two formulas different truth values, however, is the correct tool ^_^ – HallaSurvivor Mar 26 '22 at 07:47
  • 3
    Use truth table – Mauro ALLEGRANZA Mar 26 '22 at 13:49
  • @MauroALLEGRANZA Like I said, "I know that the interpretation where all A, B, and C are false makes the former true and the latter false, but how do I prove it Fitch style?" – user3146 Mar 26 '22 at 14:58
  • @HallaSurvivor Are you saying I cannot prove this Fitch style? Are you saying I cannot assume [A→(B→C)]↔[A→B)→C], which isn't true, and find a contradiction? – user3146 Mar 26 '22 at 15:02
  • You could presumably use some complete system of cut-free sequent calculus and argue there can be no proof of the equivalence in that system, at least in theory. – Daniel Schepler Mar 26 '22 at 17:09
  • 1
    You could also use a Fitch-style proof to show that if $((A\to B)\to C) \leftrightarrow (A \to (B \to C))$, then $A\lor B\lor C$. Then the meta-argument following on from that would be: therefore, if $((A\to B)\to C) \leftrightarrow (A \to (B \to C))$ were a tautology, then $A\lor B\lor C$ would also have to be a tautology, which it clearly isn't. (The term $A\lor B\lor C$ arising as the negation of $\lnot A \land \lnot B \land \lnot C$.) – Daniel Schepler Mar 26 '22 at 17:15
  • If a formula is not a contradiction you cannot prove its negation. – Mauro ALLEGRANZA Mar 26 '22 at 19:18
  • 2
    Due to soundness of the calculus (only tautologies are provable) you show unprovability showing that the formula is not a tautology. – Mauro ALLEGRANZA Mar 26 '22 at 19:22
  • @MauroALLEGRANZA yeah, that's right. My brain is fried right now. I'll start upvoting people trying to get at that. – user3146 Mar 26 '22 at 19:25
  • I meant people who were trying to get at that – user3146 Mar 26 '22 at 20:00

3 Answers3

2

Hint: Prove $\neg A \land \neg B \land \neg C \implies \neg(((A\implies B)\implies C)\iff (A\implies (B\implies C)))$

Edit 1: Easier might be $\neg A \land \neg C \implies \neg(((A\implies B)\implies C)\iff (A\implies (B\implies C)))$

Edit 2: Did it in 24 lines in my system. Assumed $\neg A \land \neg C$. Proved by contradiction that $\neg(((A\implies B)\implies C)\iff (A\implies (B\implies C))))$. Twice made use of both vacuous truth and $P\implies Q ~\equiv~ \neg(P \land \neg Q)$.

Edit 3: You could do it by brute force by cases. You have 2 cases $A\lor \neg A$, 2 subcases $B \lor \neg B$, and 2 sub-subcase $C \lor \neg C$. In other words, prove each line of the truth table. Or.....

Dan Christensen
  • 14,529
  • I was trying to do something like that – user3146 Mar 26 '22 at 15:41
  • I was trying to suppose not C BWOC, and then not A, and then possibly not B, in my indirect proof of your consequent – user3146 Mar 26 '22 at 15:43
  • Any idea why that went wrong, I'm a bit sleep deprived. Also, doing a conditional proof of what you have doesn't fully give me a proof that the consequent of your conditional statement is true, right? – user3146 Mar 26 '22 at 15:45
  • I meant to say, "I was trying to suppose A BWOC, then C, then possibly B, and then not C, and then not A, and then possibly not B, in my indirect proof of your consequent". It's not letting me edit it now – user3146 Mar 26 '22 at 15:49
  • I mean, proving what you have only shows that the conditional statement isn't true if the three (or two) base statements are false. Is that kind of a cheat or something as to a Fitch style proof (because it's mixing the technique of truth table with Fitch style)? – user3146 Mar 26 '22 at 16:05
  • Who's to say it wasn't a lucky guess? ;^) – Dan Christensen Mar 26 '22 at 16:08
  • I guess I'll make more clear in my post that I want to know how to prove this purely Fitch style, as in not using Fitch style to prove what a truth table would, that there is an interpretation (ordered triple of truth values of base statements) that makes the equivalence false. Though if I can use something like that to prove ¬{[A→(B→C)]↔[A→B)→C]}, then that would be appreciated (as in can we get ¬{[A→(B→C)]↔[A→B)→C]} from (¬A∧¬B∧¬C)→¬{[A→(B→C)]↔[A→B)→C]} by rules of inference?). – user3146 Mar 26 '22 at 16:22
  • @user3146 See edits. – Dan Christensen Mar 26 '22 at 16:42
  • If you assume ¬A∧¬C, and prove by contradiction that ¬(((A⟹B)⟹C)⟺(A⟹(B⟹C)))), then you are only proving (¬A∧¬C)→¬{[A→(B→C)]↔[A→B)→C]}, not ¬{[A→(B→C)]↔[A→B)→C]}, right? After you assume ¬A∧¬C, you assume ((A⟹B)⟹C)⟺(A⟹(B⟹C))) BWOC, find a contradiction, which gives ¬(((A⟹B)⟹C)⟺(A⟹(B⟹C)))), which because you started with the the assumption ¬A∧¬C, gives (¬A∧¬C)→¬{[A→(B→C)]↔[A→B)→C]}, not ¬{[A→(B→C)]↔[A→B)→C]}, right? – user3146 Mar 26 '22 at 17:14
  • Regarding the edit 2: on proofs.openlogicproject.org, it only took me 15 lines to show the implication, and I didn't do anything at all tricky there. (Though I proved $\lnot A, \lnot C \therefore \cdots$; proving $\therefore \lnot A \land \lnot C \to (\cdots)$ would take it up to 17 lines, I guess.) – Daniel Schepler Mar 26 '22 at 17:20
  • Thanks, but like I said, need ¬{[A→(B→C)]↔[A→B)→C]}, not (¬A∧¬C)→¬{[A→(B→C)]↔[A→B)→C]} (only from rules of inference). – user3146 Mar 26 '22 at 17:22
  • @user3146 It won't be possible to give a Fitch proof of $\lnot((A\to (B\to C)) \leftrightarrow ((A\to B) \to C))$ since that's not a tautology either -- for example, if $A, B, C$ are all true, then that negation evaluates to false. – Daniel Schepler Mar 26 '22 at 17:26
  • @DanielSchepler whoa, how did I overlook that? But isn't ¬{[A→(B→C)]↔[(A→B)→C]} equivalent to saying A→(B→C) and (A→B)→C are not equivalent? – user3146 Mar 26 '22 at 17:42
  • 1
    @user3146 I think maybe you're getting confused between logical equivalence of two propositions, and truth value of a $\cdots \leftrightarrow \cdots$ proposition. What's true is that $A\to (B\to C)$ and $(A\to B) \to C$ are not logically equivalent; what's not true is that the proposition $(A\to (B\to C)) \leftrightarrow ((A\to B) \to C)$ is always false. – Daniel Schepler Mar 26 '22 at 17:53
  • yeah, I know it looks that way (I do know the interpretation differences between tautology, contingency, consistency, contradiction), but (A→(B→C))↔((A→B)→C) is equivalent to saying A→(B→C) and (A→B)→C are logically equivalent, and then saying (A→(B→C))↔((A→B)→C) is not true is ¬((A→(B→C))↔((A→B)→C)), right? Or am I overlooking something up there? – user3146 Mar 26 '22 at 18:02
  • No, by definition $A\to(B\to C)$ being logically equivalent to $(A\to B)\to C$ means the same thing as $(A\to(B\to C))\leftrightarrow((A\to B)\to C)$ being a tautology. So, the negation of logical equivalence is that $(A\to(B\to C))\leftrightarrow((A\to B)\to C)$ is either contingent or a contradiction. In this case, the $\leftrightarrow$ proposition is contingent. – Daniel Schepler Mar 26 '22 at 19:02
  • @DanielSchepler Right.. I'm pretty sure I agree with everything you said. Maybe this is the point of confusion: isn't saying (A→(B→C))↔((A→B)→C) is either contingent or a contradiction saying that this equivalence is not true (that they are not equivalent)? – user3146 Mar 26 '22 at 19:09
  • Is this a confusion of truth value of statement involving reference versus truth value of the statement being referenced? – user3146 Mar 26 '22 at 19:20
  • I'm seeing a confusion of what I consider different levels which shouldn't be mixed (though there is obviously relation between them): one is the level of logical equivalence, tautology, contingency, contradiction, etc. which is independent of any particular assignment of truth values to the atomic variables; and the other is the truth value of a proposition, which does require a particular assignment of truth values to the atomic variables. – Daniel Schepler Mar 26 '22 at 19:35
0

Propositional logic is complete. You can either prove it semantically by truth table (that the truth tables of both propositions are different) or syntactically by showing that these propositions are not equivalent (by using the axioms and modus ponens). The first method is simpler.

Wuestenfux
  • 20,964
  • How do you show semantically that two formulas are inequivalent? I'm about to go to bed, so I'm likely missing something easy, but I can't think of a method – HallaSurvivor Mar 26 '22 at 08:00
  • Not so easy. It's much easier to show that they are equivalent. Therefore, I'd choose the way using semantics. – Wuestenfux Mar 26 '22 at 13:47
  • Regarding truth tables, I know it's simpler and I know what interpretation in the truth table gives me the solution. Like I said, "I know that the interpretation where all A, B, and C are false makes the former true and the latter false, but how do I prove it Fitch style?" I know propositional logic is complete. That's why I didn't ask if it is possible, but how. Regarding the axioms and modus ponens, "I've tried material implications, indirect proofs, modus ponens, and modus tollens galore. I can't seem to figure it out" (obviously among the other rules of inference, but these galore). – user3146 Mar 26 '22 at 15:08
  • So, with all of that said, what I'm getting at is I'm not sure what your answer is answering. – user3146 Mar 26 '22 at 15:09
  • Also, doing a truth tree validity test with the trunk as the conjunction of your two premises (which if you get all branches closed, means that the negation of the conjunction is valid and thus the conjunction is a contradiction, right?) gives an open branch, which means the conjunction is consistent, and thus I won't be able to find a contradiction in either of the two sub indirect proofs above, right? – user3146 Mar 26 '22 at 15:57
  • Sorry, I wrote that one in the wrong place – user3146 Mar 26 '22 at 16:06
0

If the formulas $A\rightarrow(B\rightarrow C)$ and $(A \rightarrow B) \rightarrow C$ were equivalent, then $(A\rightarrow(B\rightarrow C))\leftrightarrow (A \rightarrow B) \rightarrow C)$ would be a tautology.

Therefore, show that, using $A\rightarrow(B\rightarrow C)$ and $(A \rightarrow B) \rightarrow C$ and the condition Dan Christensen gives as premisses to account for the rows with T in the box below:

$$\neg((A\rightarrow(B\rightarrow C))\leftrightarrow (A \rightarrow B) \rightarrow C))$$

Yet, it may be a tiresome exercise —see the question to get an idea about how much work it may demand.

enter image description here

Tankut Beygu
  • 2,331
  • I'm confused as to why you posted a link to that question. Did I make it seem like I don't know how to do Fitch style proofs? I said in my question that I did Fitch style proofs on this in a bunch of different ways that got me nowhere. One of which was indirect proof, which is the setup you gave. – user3146 Mar 26 '22 at 15:15
  • OK. So, if you find out some other way one day, please post it so that we learn, too. – Tankut Beygu Mar 26 '22 at 15:18
  • That's what I'm asking for on here. – user3146 Mar 26 '22 at 15:35
  • Also, you're setup appears to be wrong. If I'm showing there not equivalent, then I assume they are, which means the premises are "[A→(B→C)]→[A→B)→C] and [A→B)→C]→[A→(B→C)]" or "[A→(B→C)]↔[A→B)→C]", but not "A→(B→C) and (A→B)→C", right? But, what seems naturally the first thing to go for is assuming one of your premises to false or true BWOC, gives either your two premises or the conjunction of negation of each. Then once you reach contradiction, which it doesn't seem you can, leads to the other, which again seems you can't reach contradiction for the main indirect proof. – user3146 Mar 26 '22 at 15:35
  • I only say that, in propositional calculus, the only syntactic expression that any two propositions P and Q are not equivalent (i.e., the first sentence of the question) is the negation of material equivalence and in some Fitch implementations it may demand too much work. The strategy one would pursue to show that is one's personal choice. – Tankut Beygu Mar 26 '22 at 16:01
  • Sorry, I wrote this in the wrong answer before, "Also, doing a truth tree validity test with the trunk as the conjunction of your two premises (which if you get all branches closed, means that the negation of the conjunction is valid and thus the conjunction is a contradiction, right?) gives an open branch, which means the conjunction is consistent, and thus I won't be able to find a contradiction in either of the two sub indirect proofs above, right?" – user3146 Mar 26 '22 at 16:07
  • Sorry, I'm sleep-deprived. I'm still unclear as to why you gave your two premises. You're not saying they are a negation of material equivalence, right? And, if not, why are you taking them as premises to show negation of material equivalence? – user3146 Mar 26 '22 at 16:12
  • 1
    It won't be possible to find a Fitch proof of $A\to (B\to C), (A\to B) \to C \therefore \lnot((A\to (B\to C)) \leftrightarrow ((A\to B) \to C))$: it's not a valid sequent since for example if $A,B,C$ are all true, then the premises are true but the conclusion is false; contradicting the soundness of the Fitch proof system. – Daniel Schepler Mar 26 '22 at 17:29
  • @DanielSchepler right – user3146 Mar 26 '22 at 17:31
  • @DanielSchepler My purpose was actually is not show how to prove, but to say it is possible. Anyway, I'll re-examine it. – Tankut Beygu Mar 26 '22 at 17:38
  • @DanielSchepler you're right. Thanks. – Tankut Beygu Mar 26 '22 at 17:42
  • @TankutBeygu It's looking like it, but isn't ¬{[A→(B→C)]↔[(A→B)→C]} equivalent to saying A→(B→C) and (A→B)→C are not equivalent, and we know they're not, right? – user3146 Mar 26 '22 at 17:50
  • Right. More precisely to say, this is not an unconditional non-equivalence. I've added the condition citing Dan Christensen. – Tankut Beygu Mar 26 '22 at 18:08
  • So if it's true that A→(B→C) and (A→B)→C are not equivalent, then isn't that equivalent to saying ¬{[A→(B→C)]↔[(A→B)→C]} is true? – user3146 Mar 26 '22 at 18:44
  • As Schepler has pointed out, if we do not assume ¬A ∧ ¬B ∧ ¬C, the conclusion violates the soundness of Fitch proof system —I'll go over the question and the responses again. – Tankut Beygu Mar 26 '22 at 19:05