What an effect the location of quantifier has in such predicate logics

46 Views Asked by At

Let's say we have a logical expression such that;

$\forall $y( $\theta$(x,y) $\implies$ $\forall$x$\beta$(x) ) )

Can we safely say that it is "logically equivalent" to

$\forall$y$\forall$x( $\theta$(x,y) $\implies$ $\beta$(x) )

2

There are 2 best solutions below

0
On BEST ANSWER

Suppose that $\theta(x, y)$ means $y$ is an aardvark and $x$ is the daughter of $y$ and that $\beta(x)$ means that $x$ is an aardvark. Then:

$$\forall y(\theta(x, y) \implies \forall x \beta(x)) \tag{*}$$

is equivalent to:

$$\forall y(\theta(x, y) \implies \forall z \beta(z))$$

(because the names of bound variables don't matter) and is the (rather remarkable) statement about an individual $x$ that says that if $x$ is the daughter of an aardvark then every individual is an aardvark.

On the other hand:

$$\forall y\forall x(\theta(x, y) \implies \beta(x)) \tag{**}$$

is the unexceptionable statement that the daughter of any aardvark is an aardvark.

So (*) and (**) are certainly not logically equivalent.

2
On

The first statement has a free variable, but the second has not, so we can't say they are equivalent as pointed out by some of the comments.

But we can extend the notion of equivalence to expressions with free variables, e.g. $\neg \neg P(x)$ is equivalent to $P(x)$, since the exact same objects that satisfy the first statement satisfy the second statement. I am thinking that that is maybe what you were really asking.

Also, you may have been wondering about the move of the quantifier. Again, when we make sure we don't have any differences in free variables, you get the equivalence you are suspecting, e.g. $\forall y \: (P(y) \rightarrow \forall x \: R(x,y))$ is indeed equivalent to $\forall y \forall x \: (P(y) \rightarrow R(x,y))$.

You have to be careful in moving quantifiers though, e.g. $\forall y \: ( \forall x \: R(x,y) \rightarrow P(y))$ is not equivalent to $\forall y \forall x \: ( R(x,y) \rightarrow P(y))$, but to $\forall y \exists x \: ( R(x,y) \rightarrow P(y))$.