2
$\begingroup$

Determine whether the follwing formula is universally valid: $$ \forall v_0(P(v_0)\lor Q(v_0))\rightarrow\forall v_0P(v_0)\lor\exists v_0Q(v_0) $$

I was confused about this question, because my professor has said that this is false in the structure $<\mathbb{N},P_\mathbb{N},Q_\mathbb{N}>$, where $P_\mathbb{N}=\{\text{primes}\}$, $Q_\mathbb{N}=\{\text{non-primes}\}$. However, I do not see how this is false, since to me it seems like $\exists v_0$ such that $v_0$ is non-prime, so this would make the statement true. Am I missing something here?

I also believe that we can show that a formula is universally valid by showing that the negation of the statement is unsatisfiable. Is this correct? So then I tried to show that the negation was unsatisfiable. I think that the negation is $$ [\forall(P(v_0)\lor Q(v_0))\land\exists v_0\neg P(v_0)]\land\forall v_0\neg Q(v_0) $$

  • The $\forall v_0\neg Q(v_0)$ is saying that $Q$ is not the whole universe
  • The $\forall(P(v_0)\lor Q(v_0))$ is saying that $P$ and $Q$ partition the universe, and so with the previous bullet, we have that $P$ is the whole universe
  • The $\exists v_0\neg P(v_0)$ is saying that there is an element of the universe that is not in $P$, which contradicts the previous bullet

So I then concluded that this negation is not satisfiable. I then said that this means that the formula is universally valid. However, the fact that my answer is different to the answer my professor has given me makes me think that I must be misunderstanding something. Could anybody spot where my misunderstandings are? Help is much appreciated!

$\endgroup$
2
  • 2
    $\begingroup$ Yes, this is a valid sentence. Is it possible your professor misread and thought that all three of the quantifiers were $\forall$? $\endgroup$ Aug 22, 2021 at 19:00
  • $\begingroup$ umsu.de/trees/… $\endgroup$
    – Shaun
    Aug 22, 2021 at 19:06

2 Answers 2

3
$\begingroup$

Yes, it is.

I'm going to split the proof into cases where the domain is empty and where it isn't because I think that makes it slightly easier to follow.

Suppose the domain is empty, then $\forall x \mathop. P(x) \lor Q(x)$ holds and $\forall x \mathop. P(x)$ holds. Thus the LHS and RHS both hold.

Suppose the domain is non-empty.

Let's do a proof by contradiction.

Background assumption.

$$ \forall x \mathop. P(x) \lor Q(x) $$

Negate the goal.

$$ (\exists x \mathop. \lnot P(x)) \land (\forall x \mathop. \lnot Q(x)) $$

Conjunction elimination.

$$ \exists x \mathop. \lnot P(x) $$

Existential instantiation.

$$ \lnot P(c) $$

Conjunction elimination.

$$ \forall x \mathop. \lnot Q(x) $$

Universal instantiation.

$$ \lnot Q(c) $$

Thus, $(\forall x \mathop. P(x) \lor Q(x))$ is false because it fails at $c$.

$\endgroup$
1
$\begingroup$

Yes. Here's a Gentzen-style proof:

$\cfrac{P(a)\rightarrow P(a),Q(a);\qquad Q(a)\rightarrow P(a),Q(a)}{\cfrac{\cfrac{\cfrac{\cfrac{P(a)\lor Q(a)\rightarrow P(a),Q(a)}{\forall v_0(P(v_0)\lor Q(v_0))\rightarrow P(a),Q(a)}}{\forall v_0(P(v_0)\lor Q(v_0))\rightarrow P(a),\exists v_0Q(v_0)}}{\forall v_0(P(v_0)\lor Q(v_0))\rightarrow\forall v_0P(v_0),\exists v_0Q(v_0)}}{\forall v_0(P(v_0)\lor Q(v_0))\rightarrow\forall v_0P(v_0)\lor\exists v_0Q(v_0)}.}$

$\endgroup$

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.