Determining validity in predicate logic

403 Views Asked by At

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

There are 1 best solutions below

0
On BEST 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.