0

Let say I have a signature $\{ P_1^1 ,P_2 ^2 , F^2 \}$ with the interpretation $$U= \{ 0,1 \}$$ $$R_1= \{ 0 \}$$ $$R_2= \{ (0,1),(1,0) \}$$ $$F={(0,0,1),(1,0,0),(0,1,0),(1,1,1)}$$

I have been given a sentence $$\exists x.P_1 (x)$$

Why is this sentence true?

1 Answers1

1

Assuming that the interpretation of $P_1$ is $R_1$ and of $P_2$ is $R_2$, we have that in the domain $U$ there is an element, $0$, such that it satisfy the interpretation of the predicate symbol $P_1$, that is $R_1$, due to the fact that : $0 \in R_1$.

The inductive definition of the satisfaction relation : $\mathcal M \vDash \varphi$ (read : the structure $\mathcal M$ satisfy the formula $\varphi$) gives us :

let $\varphi$ a formula with a free variable $x$ and let $D$ the domain of the structure $\mathcal M$.

We define :

if $\varphi$ is $P_1(x)$, then $\mathcal M \vDash \varphi(a)$ iff $a \in P_1^M$, where $P_1^M$ is the interpretation of $P_1$ in $\mathcal M$ [in our case $R_1$]

And :

$\mathcal M \vDash ∃x \varphi$ iff there is some $a \in D$ such that : $\mathcal M \vDash \varphi(a)$.

Mauro ALLEGRANZA
  • 94,169
  • In the question I forgot to put what F was, I have added it in. How did you get those curly brackets? –  Jan 18 '15 at 14:44
  • By my understanding, F contains a mapping from (0,1) to 0 so it is true? –  Jan 18 '15 at 14:45
  • what about for all x and some y p2(x,y) how do the quantifiers change things? –  Jan 18 '15 at 15:00
  • that is correct –  Jan 18 '15 at 15:05
  • @user204450 - also $\forall x \exists y P_2(x,y)$ is true in $U$, because $(0,1) \in R_2$ and $(1,0) \in R_2$ and $0,1$ are the only elements of $U$. – Mauro ALLEGRANZA Jan 18 '15 at 15:12
  • what is the quantification symbols were swapped for x and y? Also what is |=? –  Jan 18 '15 at 15:32
  • @user204450 - if you mean $\exists x \forall y P_2(x,y)$, this is not true in $U$, because neither $(0,0) \in R_2$ nor $(1,1) \in R_2$. – Mauro ALLEGRANZA Jan 18 '15 at 18:03
  • where did you get (0,0) and (1,1) from? –  Jan 19 '15 at 14:47
  • @user204450 - I've found them through the definition of $R_2$; they are the couples not in $R_2$ and this means that in the interpretation we are discussing $P_2(0,0)$ and $P_2(1,1)$ do not hold. This is enough to show that in the said interpretation the formula $∃x∀yP_2(x,y)$ is not true. – Mauro ALLEGRANZA Jan 19 '15 at 14:57
  • What is x and y though? (sorry, I am really bad at logic) –  Jan 19 '15 at 15:43