# Determining validity in predicate logic

Not sure if I've done this correctly.

Check the following formulae for validity. If valid, justify why. If they are not valid, give a countermodel.

i) ∃xP(x)→∀xP(x)

ii) ∀xP(x)→∃xP(x)

iii) ∃x(P(x)→∀yP(y))

For part i) It is false, let $D=\mathbb{N}$ and let $P(x)$ mean "x is odd", then it is not the case that if some natural numbers are odd, that all natural numbers are odd.

For part ii) It is true, let $D=\mathbb{N}$ and let $P(x)$ mean "x is divisible by 1", then it is the case that if all natural numbers are divisible by one, that some natural numbers (which would make up a subset) are divsible by 1.

For part iii) I'm not sure. Looking at the scope of the quantifiers, I think that it is the same as part i, but I truly am unsure. Would appreciate some guidance with this.

## 1 Answer

(i): correct, it's false, and you've given a good counterexample.

(ii): partial credit. You've given an example confirming that the statement is valid, but you haven't indicated why it's true in general. The statement is valid (in any nonempty domain — the usual assumption of first-order logic). Suppose $\forall x P(x)$. Something exists $y$ (there's that assumption at work). Then $P(y)$, so $\exists y P(y)$ — or, by change of variable, $\exists x P(x)$.

(iii) is valid. Note that if $x$ is not free in $B$, then $\forall x(A\lor B) \iff \forall x A \lor B$. Also recall that $A\to B \iff \neg A\lor B$, and that $\exists \neg \equiv \neg\forall$. Hence \begin{align} \exists x(P(x)\to \forall y P(y)) &\iff \exists x(\neg P(x)\lor \forall y P(y)) \\ &\iff \exists x\neg P(x)\lor \forall y P(y) \\ &\iff \neg\forall x P(x)\lor \forall y P(y) \\ &\iff \forall x P(x)\to \forall y P(y), \\ \end{align} which of course is valid.