Showing a first-order predicate formula is not valid.

Question

There is first-order predicate formula

$$A = \forall a (\neg P(a,a))$$

$$B = \forall a \forall b \forall c (P(a,b)\wedge P(b,c)\Rightarrow P(a,c))$$

$$B'= \forall a \forall b \forall c (P(a,b)\wedge P(b,c)\Rightarrow \neg P(a,c))$$

$$C = \forall a \forall b (P(a,b)\Rightarrow \neg P(b,a))$$

Question: Show that $A \vee B \vee B' \vee C$ is not valid.

Valid means there is no truth assignment makes it false.

What I got understood are truth assignment and resolving $A\Rightarrow B$ to $\neg A \vee B$. But I can't understand how to implement '$\forall $' Universal notation into formula. And what happened when we use $P(a,b)$ instead of just $a$ or $b$.

So, can anyone solve above question with explaination step by step .

Many thanks. You're all legends!

Answer 1

To say $A\vee B\vee B'\vee C$ is invalid, is to claim that we are able to evaluate it as false for some interpretation. Thus you need to construct a counterexample where $\neg A\wedge\neg B\wedge\neg B'\wedge\neg C$ holds.

But I can't understand how to implement '∀' Universal notation into formula.

The negation of a universal is an existential. So $\neg A\equiv \exists a~P(a,a)$. Thus your counterexample needs a witness to this (and likewise to the other statements' negations).

And what happened when we use $P(a,b)$ instead of just $a$ or $b$.

So, rather than evaluating propositions, we are evaluating predicates.

The bivalent predicate $P$ is a relation between terms in the domain . Your interpretation then must consist of some set of values and some relation over them which makes $\neg A\wedge\neg B\wedge\neg B'\wedge\neg C$ true.

Can you build it?

The natural numbers, or a subset, often may serve as a domain. Now, to have $\neg A$ hold true, we need a witness to $\exists a~P(a,a)$. So we declare $P(0,0)$ to be a fact.

• If we evaluate $P(0,0)$ to be true, then $\neg A$ holds in this interpretation of $(\Bbb N,P)$.

And so forth...

Answer 2

Hint

To show that the formula is not valid, you have to find an interpretation such that the complex formula is False.

Being a disjunction, this means that the sought interpretation must falsifies every disjunct.

We can try with a simple interpretation $\mathcal I$ with domain $I = \{ 0,1,2,3 \}$.

Try with $P^{\mathcal I} = \{ (0,0), (0,1), (0,2), (1,0), (1,2), (1,3) \}$ as interpretation of the predicate symbol $P$.

(A) We have that $(0,0) \in P^{\mathcal I}$ and thus it is not true that $\lnot P(a,a)$ for every $a$.

(C) We have that $(0,1) \in P^{\mathcal I}$ and also $(1,0) \in P^{\mathcal I}$; thus it is not true that $P(a,b) \to \lnot P(b,a)$ for every $a,b$.

(B') We have that $(0,1) \in P^{\mathcal I}$ and $(1,2) \in P^{\mathcal I}$ and also $(0,2) \in P^{\mathcal I}$. Thus, it is not true that $(P(a,b) ∧ P(b,c)) \to ¬P(a,c)$, for every $a,b,c$.

In the same way, you can check (B).