3

The way I did was to simply construct a truth table about $\rightarrow$, and treat the 2,3 line as ordered pairs in vertical direction. (Given $A: T T FF$ $B:TFTF$.)

I got $(T,F)$ from $A$ and $(F,T)$ from $B$. Thus all the possible in the 2,3 line were $(T,F),(F,T),(T,T)$ by operation $\rightarrow$. Thus the pair $(F,F)$ in $(A\leftrightarrow B)$ was not possible by $\rightarrow$.

However, is there any other way to prove it without listing all the posibilities?

  • 1
    You're only using one implication symbol. Clearly, using only one implication symbol you can't emulate $\iff$, simply because the two are different, as you've demonstrated. You also have to rule out anything like $(A\implies B)\implies(B\implies A)$, and monsters with thousands or millions of arrows, and anything both between and beyond. And that cannot be done with a truth table. – Arthur Sep 15 '17 at 05:44
  • You can't even make $\bot$ from $\implies$ – Kenny Lau Sep 15 '17 at 05:46
  • @KennyLau That doesn't prove anything, as you can't make a tautologically false statement with $\iff$ either. – Arthur Sep 15 '17 at 05:49
  • @Arthur did I say that proves anything? – Kenny Lau Sep 15 '17 at 06:04
  • @KennyLau You did when you used the word "even". That hints that your statement is stronger. – Arthur Sep 15 '17 at 06:26
  • Thanks. But I didn't think there need any more cases on the truth table as ${(T,F),(F,T),(T,T)}$ was the only sets generated by ${(T,F),(F,T)}$.no matter how many finite many cases you constructed. –  Sep 16 '17 at 06:20

2 Answers2

4

Consider any expression using only the implication $\to$. Possibly it is very long, such as $(((A\to B)\to ((A\to A)\to(B\to A)))\to (A\to B))$ or what have you. Perhaps it has millions of symbols, or just a few.

In any case, consider the very last propositional variable that appears in the statement, such as the variable $B$ in the example above, which appears at the extreme right. Let's imagine a case where that variable is true. It follows that the implication it appears in is also true, and so the next level implication that appears in is true, and so on all the way out to the top-level implication. So the whole expression will be true, provided that we specify merely that that variable at the end is true. But $A\leftrightarrow B$ cannot be guaranteed true by knowing only that one of the variables is true. Therefore, we cannot express $A\leftrightarrow B$ in terms of the conditional $\to$.

JDH
  • 44,236
  • Thanks! (Also little notes for myself: the case can also be disproved through induction by "properties".(Just learned it today.)) However, I was studying abstract algebra these days, and the boolean operation gave me an awkward feeling of similarity. Can we steal something from group theory to prove this statement? –  Sep 16 '17 at 06:30
1

One way of doing it: Prove by (strong) induction on the number of $\implies$ in your expression that if either of $(A,B)=(T,F)$ or $(A,B)=(F,T)$ in a statement that uses only $\implies$ gives false (which it should if we're trying to make $\iff$), then the other one gives true.

Arthur
  • 199,419