Can you please help me understand why implication was used instead of conjunction in the answer to this practice question? I have been struggling with nested quantifiers and when to use implication versus conjunction. I thought for sure this would be a case for conjunction. Thank you.
Use predicates, quantifiers, logical connectives, and
mathematical operators to express the statement that every positive integer is the sum of the squares of four integers.
my answer:
$$ \forall x \exists a \exists b \exists c \exists d ((x > 0) \land (x = a^2 + b^2 + c^2 + d^2)) $$
correct solution from book:
$$ \forall x \exists a \exists b \exists c \exists d ((x > 0) \implies x = a^2 + b^2 + c^2 + d^2) $$
Best Answer
I don’t think either phrasing is natural, but your phrasing is incorrect. I will take all quantifiers to range over the integers.
Let’s start with the statement “$x$ is the sum of four squares”. This is naturally translated as $\exists a \exists b \exists c \exists d (x = a^2 + b^2 + c^2 + d^2)$.
Now we proceed to the slightly more complicated statement, “If $x$ is positive, then $x$ is the sum of four squares”. We know how to say “$x$ is positive”, and we know how to say “$x$ is the sum of four squares”. To make an “if” statement in logic, we use the implication operator. So this translates to $x > 0 \implies \exists a \exists b \exists c \exists d (x = a^2 + b^2 + c^2 + d^2)$. It turns out that this is logically equivalent to saying $\exists a \exists b \exists c \exists d (x > 0 \implies x = a^2 + b^2 + c^2 + d^2)$, at least in classical logic. It is not a particularly natural way of phrasing the underlying claim, however.
Finally, we want to say “For all $x$, if $x$ is positive, then $x$ is the sum of four squares”. To do this, we add the $\forall x$, and we’re done.