If the language has only one predicate, can we simplify the quantifiers?

63 Views Asked by At

Assume that our language has only one predicate symbol. Then $(\forall x_1 \forall x_2 )(\phi)$ is equivalent to $(\forall x)(\phi')$ where $\phi'$ is a formula obtained by replacing all occurrences of $x_1$ and $x_2$ to $x$.

I wonder if this proposition is correct. .

2

There are 2 best solutions below

0
On BEST ANSWER

Even with arity $1$ this breaks down.

Consider the sentence $$(*)\quad\forall x_1\forall x_2(P(x_1)\vee\neg P(x_2)).$$ This is equivalent to $$(**)\quad(\forall x(P(x)))\vee (\forall x(\neg P(x))).$$

(Why? Clearly the latter implies the former, so suppose that the latter failed. Then we have $a,b$ with $\neg P(a)$ and $P(b)$. Now in $(*)$ set $x_1=a$ and $x_2=b$.)

On the other hand, the one-variable version $$(\dagger)\quad\forall x(P(x)\vee\neg P(x))$$ is a tautology. So they're not in general equivalent.


Replacing my original second example which used both equality and a predicate symbol:

In fact, we don't need non-logical symbols at all - consider the sentence $$\forall x_1\forall x_2(x_1=x_2),$$ which is not a tautology but transforms into one under the operation you describe.

Of course $=$ basically is a binary relation, it's just that it's a "logical" as opposed to "non-logical" one; for that reason, the first example above is really the best one. However, it's still worth noting how equality alone brings enough complexity into the picture.

0
On

Work in the language of graphs, which has a single binary predicate symbol $R(x,y)$ whose interpretation is "$x$ is connected to $y$".

Consider the following formula $\varphi$:$$\forall x_1\forall x_2(x_1\neq x_2\rightarrow R(x_1,x_2))$$

Then $\varphi'$ holds in every structure, while $\varphi$ doesn't