Prenex form of uniqueness quantifier

68 Views Asked by At

$\exists !xP(x)$ is generally defined as $$\exists x(P(x)\land\forall y(P(y)\rightarrow y=x)).$$

What is the prenex normal form of this? I think it should be $\exists x\forall y(P(x)\land (P(y)\rightarrow y=x)).$ If so, how to prove this (using only the prenex conversion rules)?

1

There are 1 best solutions below

0
On

Correct.

See in general Prenex Normal Form for the equivalences requested for prenex operations, that hold in general provided that $x$ is not free in $ψ$.

More specifically : $(∀xϕ) ∧ ψ$ is equivalent to $∀x(ϕ ∧ ψ)$.

The proof relies on the proof system used; it is quite straightforward with Natural Deduction

A semantic argument may help : let $D$ a non-empty domain. Several cases :

(i) let $a \in D$ such that $Pa$ is False. Thus, $Pa \land \forall y Qy$ is False.

But also $Pa \land Qb$ is False, for every $b \in D$. Thus $\forall y(Pa \land Qy)$ is False.

(ii) let $a \in D$ such that $Pa$ is True. Two sub-cases :

(ii-a) $Qb$ is True for every element $b \in D$. Thus $\forall y Qy$ holds in $D$ and thus $Pa \land \forall y Qy$ is True.

But also $Pa \land Qb$ holds, for every $b \in D$. Thus : $\forall y(Pa \land Qy)$ is True.

(ii-b) $Qb$ is False for some element $b \in D$. Thus $\forall y Qy$ is False and also $Pa \land \forall y Qy$ is False.

But then $Pa \land Qb$ is False, and thus $\forall y(Pa \land Qy)$ is False.