Showing that a formula is inconsistent.

Question

Let $L$ be a first-order language with the predicate symbol $P$, and let $x,y$ be variables in $L$.

I want to show that

$$\forall x\neg\big(P(x) \rightarrow \forall yP(y)\big)$$

is inconsistent (I mean that the set of that sentence is inconsistent.

I am using Enderton's A Mathematical Introduction to Logic. I am not allowed to use the completeness theorem. If a set of sentences $\Gamma$ is inconsistent it means that there exists a sentence $\sigma$ such that $\Gamma\vdash\sigma$ and $\Gamma\vdash\neg\sigma$.

Should I try to find such a $\sigma$ ?

I am not allowed to use the completeness theorem.

Answer 1

We have that the formula :

$∀x¬(P(x) → ∀yP(y))$

is inconsistent iff it is unsatisfiable (by the Completeness Th) iff its negation is valid.

In order to show the validity of :

$¬∀x¬(P(x) → ∀yP(y))$ we have to consider the equivalent formula : $\exists x (¬P(x) \lor ∀yP(y))$.

According to the semantical specifications of :

• Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), page 88 :

[A formula] $\varphi$ is valid iff for every $\mathfrak A$ and every $s : Var \to |\mathfrak A|$, $\mathfrak A$ satisfies $\varphi$ with $s$.

In turn, $\mathfrak A$ satisfies $\exists x \alpha$ with $s$ iff for some $d \in |\mathfrak A|, \vDash_\mathfrak A \alpha[s(x|d)]$.

Now, for $\exists x (¬P(x) \lor ∀yP(y))$, we have that it is valid if for any $|\mathfrak A|$ and any $s$ :

$\vDash_\mathfrak A (¬P(x) \lor ∀yP(y))[s(x|d)]$, for some $d \in |\mathfrak A|$.

Now the conlcusion is straightforward; for any structure $\mathfrak A$, we have two psoobilities :

(i) there is some object in the domain such that the interpretation of $P$ does not hold of it, i.e. for some $d \in |\mathfrak A|$, $d \notin P^\mathfrak A$, in which case this object is the needed $d$ for $s(x|d)$ satisfying the formula;

otehrwise :

(ii) $P$ holds of all objects in the domain, i.e. for no $e \in |\mathfrak A|$, $e \notin P^\mathfrak A$, that means : for all $e \in |\mathfrak A|$, $e \in P^\mathfrak A$; in this case we have that for every $e \in |\mathfrak A|$, we have $\vDash_\mathfrak A P(y)[s(x|e)]$, and this means that $\vDash_\mathfrak A \forall y P(y)[s]$.

In both cases, the formula is satisfied for any structure $\mathfrak A$ and for any $s$, i.e. it is valid.

---

Alternatively, we can easily prove :

$\vdash \exists x (P(x) \to ∀yP(y))$

using formula Q3a of Exercise 8, page 130 : $\vdash (∀xβ → α) ↔ ∃x(β → α)$, provided that $x$ does not occur free in $\alpha$.

But then, in order to conlcude with the validity of the formula, we need the Soundness Theorem [page 131].

---

---

A more "formal" proof of the inconsistency of the above formula can be produced with Enderton's proof system :

1) $∀x¬(P(x) → ∀yP(y))$ --- premise

2) $¬(P(x) → ∀yP(y))$ --- from 1) and Ax.2 by modus ponens

3) $P(x) \land \lnot ∀yP(y)$ --- from 2) by tautological equivalence : $\lnot (p \to q) \leftrightarrow (p \land \lnot q)$

4) $\lnot ∀yP(y)$ --- from 3) by tautological implication : $p \land q \to p$

5) $P(x)$ --- from 3) as above

6) $\forall y P(y)$ --- from 5) by Generalization Th : $x$ is not free in 1); 4) and 6) are the desired contradiction.