Logic quantifier position nuances

Question

I've been learning about translating English to logic and vice versa and I have to say that I find this quite difficult.

On a paper that I'm examining , I've across the following logic formula:

$ \forall x (circle(x) \Rightarrow \exists y (circle(y) \land above(x,y)))$

Each circle has a circle somewhere below it

With predicates

$ circle(x) $ - $x$ is a circle.

$ above(x, y)$ - $x$ is above $y$.

I started to wonder what the nuance is if the exists quantifier was moved outside of the entire bracket like this:

$ \forall x \exists y (circle(x) \Rightarrow circle(y) \land above(x,y))$

But my feeling is that this formula I says the same thing as the former sentence but I also think it doesn't as I'm unsure of the meaning in natural English.

Former formula: For all $x$ , if $x$ is a circle then there exists a $y$ such that $y$ is a circle and it is above $x$.

Latter formula: For all $x$ , there exists a $y$ such that if $x$ is a circle then $y$ is a circle and is above $x$.

My question is , what the difference between these two formulas in logic and natural English?

Translating from logic to English is quite hard I think and even harder from English to logic.

Are there any tips for translating from logic to English and vice versa? How do you work out the nuance if two formulas seem alike when you read them?

Answer 1

Any formula in logic is equivalent to a formula in Pre-Nex normal form, which begins with a string of quantifiers, followed by a quantifier-free expression. The two formulas you give are equivalent. I think there must be a published algorithm .Even professional mathematicians can find parsing a formula to be less than easy.

Answer 2

Consider the first formula.

$\forall X (circle(X) \implies \exists Y(circle(Y) \land above(X, Y))$

Let $x$ be an instantiation of $X$.

$circle(x) \implies \exists Y(circle(Y) \land above(x, Y))$

Let $y$ be an instantiation of $Y$.

$circle(x) \implies (circle(y) \land above(x,y))$

So clearly we have a $y$ such that

$circle(x) \implies (circle(y) \land above(x,y))$

So we may existentially generalize this so that

$\exists Y (circle(x) \implies circle(Y) \land above(x, Y))$

And since no conditions were placed on $x$, we may universally generalize so that

$\forall X \exists Y (circle(X) \implies circle(Y) \land above(X, Y))$

To answer your question, in general yes $\forall x \exists y(A(x) \implies B(x,y)) \equiv \forall x (A(x) \implies \exists y B(x, y))$ so long as A does not depend on y; however, it is also VERY important that you do not changer the order in which the quantifiers occur.

Answer 3

I've been learning about translating English to logic and vice versa and I have to say that I find this quite difficult.

Indeed.   It is difficult.   Logical expressions in native languages are often very imprecise, and formal mathematics is all about precision.   When converting to and from mathematical expressions you will encounter many trips and traps.

Every student has trouble with this.   Don't be discouraged; just be careful.   It takes practice to master, that's all.

In this case your intuition is quite correct.   The two expressions are correct.   Generally speaking, as long as $y$ does not occur free in $P(x)$, then we have the following equivalence: $$\forall x\Big( P(x) \to \exists y \big(Q(x,y)\big)\big) \iff \forall x\exists y \Big(P(x)\to Q(x,y)\Big)$$

It is important that you don't change the order of nesting the quantifiers when shifting to and from PreNex form of the expression.   Be careful about this.

---

Note also, however, the following equivalence.

$$\forall x \Big(\exists y\big(Q(x,y)\big) \to P(x)\Big) \iff \forall x \color{red}{\forall} y\Big( Q(x,y) \to P(x)\Big) \\ \Updownarrow \\ \forall x \Big(\neg \exists y\big(Q(x,y)\big) \vee P(x)\Big) \iff \forall x \color{red}{\forall} y\Big( \neg Q(x,y) \vee P(x)\Big)$$

As you see, the placement of the quantifier in the implication matters.   Be careful.