# Showing a first-order predicate formula is not valid.

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!

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).

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...

• Could you use predicate formula such as ∀a(¬P(a,a)) instead of A.
– Hume
Sep 13, 2019 at 12:04
• That is what A is. Sep 13, 2019 at 23:57
• To make the "¬A ∧ ¬B ∧ ¬B ′ ∧ ¬C" true, we should prove ¬B, ¬B' and ¬C true. Right?
– Hume
Sep 15, 2019 at 5:45
• Yes, indeed. Do the "And so forth..." Sep 15, 2019 at 6:16
• But we don't know what the P is. It can be smaller than or square and so on. How to prove A and other things are true?
– Hume
Sep 15, 2019 at 6:27