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)?
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)?
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?
$\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:
Consider now the semantical clause for existential quantifier:
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: