Prenex normal form and empty set

55 Views Asked by At

Wikipedia states the following regarding conjunction and disjunction rules for turning a formula into its prenex form:

Conjunction:
$(\forall x \phi) \land \psi $ is equivalent to $\forall x (\phi \land \psi)$ under the (mild) additional condition that at least one individual exists.

If I understand universal quantification over an empty set, the sentences are not equivalent if no $x$ exists because $(\forall x \phi) \land \psi $ will be false due to the second conjunct, while $\forall x (\phi \land \psi)$ is true, since $\forall x (\phi \land \psi) \Leftrightarrow \forall x(x \in \{\} \rightarrow \phi \land \psi)$, and the antecedent is always false.

Disjunction:
$ (\exists x \phi) \lor \psi $ is equivalent to $\exists x (\phi \lor \psi)$ under the (mild) additional condition that at least one individual exists.

Here I get lost, as the same logic applied to the conjunction rule breaks down. Both formulas should be false for the empty set, so I do not understand in what case they would have different truth values.

Help?

1

There are 1 best solutions below

3
On BEST ANSWER

In your first paragraph, you write "$(\forall x\phi)\land \psi$ will be false due to the second conjunct". This only works if $\psi$ is a sentence which is false in the empty structure. For example, taking $\psi$ to be $\top$ (the sentence "true"), we have that $(\forall x \phi)\land \top$ and $\forall x\, (\phi\land \top)$ are both true in the empty structure. On the other hand, taking $\psi$ to be $\bot$ (the sentence "false"), we have that $(\forall x \phi)\land \bot$ is false in the empty structure, while $\forall x\, (\phi\land \bot)$ is true.

This observation suggests how to fix the reasoning in your second paragraph. Taking $\psi$ to be $\top$, $(\exists x \,\phi) \lor \top$ is true in the empty structure, while $\exists x\, (\phi\lor \top)$ is false.

If you don't include $\top$ and $\bot$ in your syntax for first-order logic, feel free to replace $\top$ by $\forall x\, (x=x)$ and replace $\bot$ by $\exists x\, \lnot (x= x)$.