# Different logical outcomes based on two similar statements with different bracketing

In trying to understand some predicate calculus notes, let the domain for $$x,y$$ be buildings, and the domain for $$z$$ be cities.

Let $$H(x,y)$$ signify that $$x$$ is higher than $$y$$

Let $$O(x,y)$$ stand for $$x$$ and $$y$$ are not the same building

Let $$L(x,z)$$ stand for $$x$$ is in $$z$$,

Then my prof states:

"A building is higher than every other building only if this building is in Toronto"

He writes: this can be formulated as:

$$1) \forall x (\forall y(O(x,y) \implies H(x,y)) \implies L(x, "Toronto"))$$,

But it cannot be formulated as:

$$2) \forall x \forall y ((O(x,y) \implies H(x,y)) \implies L(x, "Toronto"))$$

In trying to understand this, I am trying to come up with an example where $$1$$, $$2$$ have different truth values for the same $$x,y$$ values since I believe this is the strategy to show that they are not logically equivalent, but I am stumped and need a hint to continue.

In the second formulation, we are considering all of the pairs of buildings. What it says, is that for any two buildings in which one ($$x$$) is higher than the other ($$y$$), then the former building must be in Toronto.

In ($$1$$) however, we are restricting to the case where $$x$$ is a particular building that is higher than every other building.

• OK! That makes perfect sense so the second could be true for a building x larger than a building y, but which isn't larger than ALL buildings y? – IntegrateThis Jan 22 at 8:30
• Exactly. All that's left to show is that there exist buildings outside of Toronto ;) – GossipM Jan 22 at 8:36

See Prenex Normal Form: $$(\forall x\phi )\rightarrow \psi$$ is equivalent to $$\exists x(\phi \rightarrow \psi )$$ under the assumption that $$x$$ is not free in $$\psi$$.

In your example, $$y$$ is not free in $$L(x , \text {Toronto})$$.

Why the above equivalence (in classical logic)?

Transform $$(\forall x\phi )\rightarrow \psi$$ into $$\lnot (\forall x\phi )\lor \psi$$ and then in $$(\exists x \lnot \phi )\lor \psi$$.

If $$x$$ is not free in $$\psi$$ we have $$\exists x (\lnot \phi \lor \psi)$$ and this in turn is $$\exists x (\phi \to \psi)$$.

• Interesting. Why is $y$ not free in $L(x, Toronto)$ since it seems $L$ only depends on $x$ here? – IntegrateThis Jan 22 at 8:40