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.

  • $\begingroup$ 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? $\endgroup$ – IntegrateThis Jan 22 at 8:30
  • $\begingroup$ Exactly. All that's left to show is that there exist buildings outside of Toronto ;) $\endgroup$ – 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)$.

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

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.