Prove that formula is not logically valid and is not contradiction

183 Views Asked by At

Consider $\alpha= \forall x \forall y (P(x,y) \rightarrow P(y,x))$

First, i need to find an interpretation $I_1$ in which $\alpha$ is false. Second, i need to find an interpretation $I_1$ in which $\alpha$ is true.

Im a little confused about the first. Find an interpretation $I_1$ in which $\alpha$ is false, means that it does not exists a valuation on $I_1$ for which $\alpha$ is true, so no valuation satisfies $\alpha$.

Consider the domain of $I_1$ as $N$ and $P(x,y)$ as $x>y$. If $x=2, y=1$ then $\alpha$ is false as i pretend, but if $x=1, y=2$ then $\alpha$ is true, which i think is not what i need, (i think i need every valuation to be false).

Following this results, $\alpha$ is false for $I_1$ ?.

2

There are 2 best solutions below

1
On BEST ANSWER

I think that you are having a little trouble with what it means for $\alpha$ to be false in a particular interpretation. Let’s take your example: $I_1=\Bbb N$, and $P(x,y)$ as $x>y$. In this interpretation $\alpha$ becomes $\forall m,n\in\Bbb N(m>n\to n>m)$. Suppose that this is true; then every instance of $m>n\to n>m$ with $m$ and $n$ both natural numbers must be true. In particular, $2>1\to 1>2$ must be true. But $2>1\to 1>2$ clearly isn’t true, so $\forall m,n\in\Bbb N(m>n\to n>m)$ can’t be true either. This is an instance of a simple but very useful observation: it takes only one counterexample to falsify a universal statement.

So all you need now is an interpretation in which $\alpha$ is true. Asaf’s hint should help there. Alternatively, you could look for an interpretation in which $P(x,y)$ and $P(y,x)$ say the same thing about $x$ and $y$: in such an interpretation it will certainly be true that if $P(x,y)$ holds, then so does $P(y,x)$.

0
On

Think what does it mean that $\alpha$ is true and what does it mean that it is false. If $I$ is an interpretation then $P^I$ (the interpretation of $P$ in $I$) is a binary relation.

Do you recognize that $\alpha$ states that $P$ is a symmetric relation?

What does it mean, if so, that $\alpha$ is true or false?