Confusion about there exist and forall

205 Views Asked by At

Which of the following is a correct predicate logic statement for "every natural number has [at least] one successor?" \begin{align*} A: \quad & \forall x\exists y\left(\operatorname{succ}(x,y)\wedge\left(\exists z\operatorname{succ}(x,z)\implies\operatorname{equal}(y,z)\right)\right)\\ B: \quad &\forall x\exists y\left(\operatorname{succ}(x,y)\vee\left(\exists z\operatorname{succ}(x,z)\implies\operatorname{equal}(y,z)\right)\right)\\ C: \quad &\exists y\forall x\left(\operatorname{succ}(x,y)\wedge\left(\exists z\operatorname{succ}(x,z)\implies\operatorname{equal}(y,z)\right)\right)\\ D: \quad &\forall x\exists y\operatorname{succ}(x,y) \end{align*}

I feel that both $A$ and $D$ are true. Is this right?

1

There are 1 best solutions below

4
On BEST ANSWER

Statement $A$: for every natural number $x$, there exists a natural number $y$ such that $y$ is the successor of $x$ and there exists a natural number $z$ such that whenever $z$ is the successor of $x$, $y$ and $z$ are equal (note that this last part is vacuously true by taking $z=y$, so the whole statement becomes $\forall x\exists y\operatorname{succ}(x,y)$).

In that sense, $A= D$, but I would say that $D$ captures the spirit of the question as intended.