Whats the difference between ∃ x P(x) and P(x)

108 Views Asked by At

First Order Logic:

Let M= be a structure for L, v be an assignment in M, P be an unary predicate symbol.

Prove / Refute: if (i) then (ii)

(i) M,v |= ∃ x P(x)

(ii) M,v |= P(x)

What's the difference between (i) and (ii)?

2

There are 2 best solutions below

1
On BEST ANSWER

$\mathcal M,v \vDash Px$ means that the variable assignment fucntion $v$ maps the variable $x$ to an element $d$ of domain $M$ of the interpretation $\mathcal M$ such that $d \in P^{\mathcal M}$.

Consider the following example: the interpretation is $\mathbb N$, $Px$ is interpreted with "$x$ is Even" and $v(x)=3$. Clearly:

$\mathbb N, v \nvDash Px$.

Consider now the semantical clause for existential quantifier:

A formula $\exists x\phi (x)$ is true according to $\mathcal M$ and $v$ if there exists a variable assignment $v'$' of the variables that only differs from $v$ regarding the evaluation of $x$ and such that $\phi$ true according to the interpretation $\mathcal M$ and the variable assignment $v'$.

Thus, considering the interpretation above and the assignment $v'$ defined as $v$ except that $v'(x)=2$, we have that $Px$ is true in $\mathbb N$ with $v'$.

Thus:

$\mathbb N, v \vDash \exists x Px$.

0
On

$\exists x P(x)$ means: There is something which has property $P$.
$P(x)$ means: This (pointing at a specific object) has property $P$.

To find out what the two statements mean and how they differ, just unpack the definitions.

Remember: $v$ is a variable assignnment, i.e. a function that maps variables $x, y, ...$ to objects of the domain. A statement is true in a structure $M$ under assignment $v$ -- write $M, v \vDash \phi$ -- iff $\phi$ is true of that object $a$ that $v$ assigns to $x$.
Quantifiers $\exists, \forall$ "overrwrite" the initial assignment $v$ and range over alternative ways of assigning objects to variables. $\exists x \phi$ means that there is a way of mapping $x$ to some object $a$ such that $\phi$ is true of $a$; $\forall x \phi$ means that every object that $x$ could possibly be assigned to will lead to success.

$M, v \vDash \exists x P(x)$ is true iff there exists an object $a$ that can be assigned to $x$ (this may be the original assignment $v$ or an alternative mapping) such that $P$ is true of $a$.
$M, v \vDash P(x)$ is true iff $P$ is true of that object that the particular variable assignment $v$ assigns to $x$.

Now if there is an alternative of $v$ that makes $P(x)$ true, can we conclude that $v$ itself makes $P(x)$ true? Why or why not?