1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.