1
$\begingroup$

$\exists x \exists z \forall y(2y-z=4x)$

Where $x$, $y$ and $z$ are integers.

Rearranging, I got

$z=2y-4x$

Since $y$ and $x$ are integers, $2y-4x$ would also be an integer for any given value of $y$.

Since $z$ is also an integer, shouldn't the predicate logic statement be true as there would always exist an integer $z$ which equals the integer $2y-4x$?

The explanation on why it was false is here:

False. For every x and z, there is an integer y = 4|x| + |z| + 1, and thus 2y = 8|x| + 2|z| + 2 > 4x + z.

However I don't understand how that shows that it must be false.

$\endgroup$
3
  • 2
    $\begingroup$ What do you think the difference is between $\exists x,$ $\exists z,$ and $\forall y?$ Do you think the order matters? $\endgroup$ Oct 28, 2021 at 4:22
  • $\begingroup$ The way that I understood the question was that you either had to prove or disprove that you could alter the numbers x and z so that the expression is true for any value of y. In that case, I don't think that the order matters. $\endgroup$
    – FarmerZee
    Oct 28, 2021 at 4:36
  • 1
    $\begingroup$ Then you are wrong. It means “there exists x,z such that (for all y, …).” Order matters. If it started $\forall y\exists x\exists z\dots,$” then you could pick $x,z$ given a specific $y.$ $\endgroup$ Oct 28, 2021 at 4:52

1 Answer 1

2
$\begingroup$

As user @Thomas Andrews hinted in the comment, order of mixed type quantifiers matters, see a previous post discussing similar subtle FOL issue. Had your $\forall y$ moved to any previous position then your reasoning is fine. But now you're clearly given a concrete counterexample construction you cannot avoid. Hope you can see that now...

$\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.