I'm trying to prove whether "all loves all" (everyone loves everyone) is a tautology or not using the tree method. While this statement shouldn't be a logical truth, my tree closes (tree setup is $\forall x \forall y Lxy$ , $\neg \forall x \forall y Lxy$ ). Where did I go wrong?

1) ∀x∀y Lxy (premise)
2) ¬∀x∀y Lxy (negation)

∃x ¬∀y Lxy    from 2)
¬∀y Lay       from 3)
∃y ¬Lay       from 4)
¬Lab          from 5)

∀y Lay        from 1)
Lab           from 7)
(Tree closes)


1) ¬∀x∀y Lxy (negation)

∃x ¬∀y Lxy    from 1)
¬∀y Lay       from 2)
∃y ¬Lay       from 3)
¬Lab          from 4)
  • $\begingroup$ If you want to prove that a formula $\phi$ is a tautology, you have to set up a truth tree fro $\lnot \phi$, fullstop. You tree shows that $∀x∀y Lxy \vdash ∀x∀y Lxy$, which is (obviously) correct. $\endgroup$ – Mauro ALLEGRANZA Oct 23 '16 at 15:59
  • $\begingroup$ I see. So ¬ϕ would prove that if the tree is open, then there is a case where ϕ is not true (therefore not every single case is true - the definition of a tautology) so it is not a tautology? How would the tree close if there are no other premises to "close it off" with? $\endgroup$ – JC1 Oct 23 '16 at 16:01
  • $\begingroup$ What Mauro says: you need to get rid of step 1 in the setup of your tree. It should just be what you now have as step 1. $\endgroup$ – Bram28 Oct 23 '16 at 16:03
  • $\begingroup$ If there are no other premises to close it off with, well, then I suppose you can't close it. So if you ever get open but finished branches, you know that what you put in the setup of the tree (the negation of the original statement) can be true ... which means that your original statement can be false ,... which means the original statement is not a tautology. $\endgroup$ – Bram28 Oct 23 '16 at 16:05
  • $\begingroup$ Thanks. So would the edited version of the tree be correct? $\endgroup$ – JC1 Oct 23 '16 at 16:10

The edited version is correct ... And since you obtained a finished and open branch the original statement that 'all loves all' is not a tautology. And of course it isn't: a simple counterexample is a scenario where a does not love b .. Which is a counterexample provided by the tree.


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.