1
$\begingroup$

If $\psi$ and $\phi$ are formulas and x is a variable that is not free in $\phi$, then the formuals $(\exists x)(\psi \rightarrow \phi)$ is logically equivalent to $[(\forall x) \psi \rightarrow \phi]$ in the predicate calculus. A proof of this can be found on page 215 in Jean Rubin's Mathematical Logic, where it is called Theorem 10.6.h.

By soundness and completeness of the predicate calculus, every universe in which $(\exists x)(\psi \rightarrow \phi)$ is true, $[(\forall x) \psi \rightarrow \phi]$ must also be true. However, consider a universe in which $\psi = \text{student $x$ does well}$, $\phi = \text{the class gets ice cream}$, and the class only gets ice cream if the entire class does well.

In this universe, $[(\forall x) \psi \rightarrow \phi]$ is true, but $(\exists x)(\psi \rightarrow \phi)$ = 'there exists a particular student such that if that student does well then the class gets ice cream' is false.

What is wrong with my reasoning?

$\endgroup$
  • $\begingroup$ You say: "the class gets ice cream, and the class only gets ice cream if the entire class does well". If this is true, this implies that the entire class does well. Thus, if $\phi$ is true, then the conditional $\psi \to \phi$ is true. $\endgroup$ – Mauro ALLEGRANZA Apr 8 at 17:14
  • $\begingroup$ On the contrary, if the class do net get ice cream, this mean that not all students get well. So $(\forall x) \psi$ is false, and thus the LH formula is true. $\endgroup$ – Mauro ALLEGRANZA Apr 8 at 17:52
  • $\begingroup$ Of course there is a particular student x such that if x does well then the class gets ice cream. Namely, let x be the student who does the worst. E.g., if "does well" means "does well on the next exam", then surely some student is going to get the lowest score on the exam, no? $\endgroup$ – bof Apr 8 at 20:09
1
$\begingroup$

I think perhaps the misunderstanding is that to have a "universe" or a "model" in which to evaluate the truth value of either statement $(\exists x) (\psi \rightarrow \phi)$ or $[(\forall x) \psi] \rightarrow \phi$, you need to have a set of students along with a fixed truth assignment of $\psi$ for each value of $x$ in the set of students, and a fixed truth assignment of $\phi$. Thus, it might be more helpful to think of the statements as being in the past tense about a certain fixed "instance of the experiment": the one statement is "if everybody in the class did well on yesterday's test, then the class got ice cream today", and the other statement is "there is a student such that if that student did well on the yesterday's test, then the class got ice cream today". From there, you can apply the logic from Bram28's answer which I won't repeat here.

On the other hand, implicitly in the supposed paradox, you're considering a collection of $2^n$ universes where $n$ is the number of students -- one universe for each possible set of students who do well. In this situation, it is indeed true for $n \ge 2$ that there is no one fixed student who works as a witness for the existence statement across all these universes.

This does give an indication of how you could construct a counterexample to equivalence of $(\exists x) (\forall y) (\psi \rightarrow \phi)$ and $(\forall y) [[(\forall x) \psi] \rightarrow \phi]$ where $y$ is possibly free in both $\psi$ and $\phi$ whereas $x$ is possibly free in $\psi$ but $x$ is not free in $\phi$. Just let $y$ represent something along the lines of an "experiment number". (And incidentally, it also gives an indication of how to construct a Kripke frame model which shows the two original statements are not equivalent in intuitionistic first-order logic. If the previous sentence means nothing to you, though, don't worry about it.)

For further reading, you might find it helpful to look up the drinker paradox which is closely related.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

... consider a universe in which $\psi = \text{student $x$ does well}$, $\phi = \text{the class gets ice cream}$, and the class only gets ice cream if the entire class does well.

In this universe, $[(\forall x) \psi \rightarrow \phi]$ is true, but $(\exists x)(\psi \rightarrow \phi)$ = 'there exists a particular student such that if that student does well then the class gets ice cream' is false.

What is wrong with my reasoning?

First, to say that "the class only gets ice cream if the entire class does well" [emphasis of 'only' is mine] is to say that the entire class doing well is a necessary condition for the class getting ice cream. Hence, that statement should be translated as:

$\phi \rightarrow (\forall x) \psi $

If you want to work with the formula $(\forall x) \psi \rightarrow \phi$, then you should read that as "the class gets ice cream if the entire class does well"

OK, but still, you ask: how does the truth of "the class gets ice cream if the entire class does well" imply that "there exists a particular student such that if that student does well then the class gets ice cream"?

Well, consider the fact that in logic, any conditional is true as soon as the antecedent is false. So, if there are some students who did not do well in the class, then the statement $(\exists x)(\psi \rightarrow \phi)$ is true, since you can simply point to any student that does not do well, and say: "There! There is a stduent for which the conditional is true, exactly because for this student, the antecedent is false!". The only other option is that there are no student who did not do well .. but that means that they all did do well, in which case (give the truth of $(\forall x) \psi \rightarrow \phi$) we know that $\phi$ is true, and hence you can point to any stduent and say: "There! There is a student for which the conditional is true, exactly because the consequent is true".

| cite | improve this answer | |
$\endgroup$

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.