Universal rules handle statements about every element. Existential rules handle statements about at least one element. Quantifier laws and existential rules must be used carefully, because an existentially chosen element is a particular witness, not an arbitrary object. In this lesson, existential specification, existential generalization, and important quantifier laws are proved and applied to quantified arguments. :::definition[Existential Specification] The Rule of Existential Specification states that if $\exists x\,p(x)$ is true, then there is at least one element of the universe for which $p(x)$ is true. We may name such an element $a$ and write $p(a)$, provided that $a$ is treated as a particular element whose existence is guaranteed, not as an arbitrary element. ::: :::definition[Rule of Existential Specification] The rule is written as $$\begin{equation*} \frac{\exists x\,p(x)}{\therefore p(a)\ \text{for some }a}. \end{equation*}$$ The symbol $a$ names a witness supplied by the existential premise. ::: :::definition[Existential Generalization] The Rule of Existential Generalization states that if a statement is true for a particular element of the universe, then there exists an element of the universe for which the statement is true. ::: :::definition[Rule of Existential Generalization] The rule is written as $$\begin{equation*} \frac{p(a)}{\therefore \exists x\,p(x)}. \end{equation*}$$ This rule moves from a known instance to an existential statement. ::: An existential statement gives at least one witness, but the witness is not arbitrary. We observe a finite universe and decide which elements satisfy $p(x)$. Select the boxes for the elements that satisfy the predicate, then let the explorer name one valid witness when it exists. Compare the existential claim with the universal claim to see why one witness can prove existence but cannot prove every case. This distinction protects proofs from using existential specification as if it were universal generalization. :::scientific-preview[Existential Witness Explorer] ::: :::theorem[Existential Distribution over Disjunction] Let $p(x)$ and $q(x)$ be open statements over a universe. Then $$\begin{equation*} \exists x[p(x)\lor q(x)]\leftrightarrow(\exists x\,p(x)\lor\exists x\,q(x)). \end{equation*}$$ ::: :::proof Given that $p(x)$ and $q(x)$ are open statements. To prove that $\exists x[p(x)\lor q(x)]\leftrightarrow(\exists x\,p(x)\lor\exists x\,q(x))$. First assume $\exists x[p(x)\lor q(x)]$. Then for some element $a$, $p(a)\lor q(a)$ is true. If $p(a)$ is true, then $\exists x\,p(x)$ is true. If $q(a)$ is true, then $\exists x\,q(x)$ is true. Therefore $\exists x\,p(x)\lor\exists x\,q(x)$. Conversely, assume $\exists x\,p(x)\lor\exists x\,q(x)$. If $\exists x\,p(x)$ is true, then for some element $a$, $p(a)$ is true, and therefore $p(a)\lor q(a)$ is true. Thus $\exists x[p(x)\lor q(x)]$ is true. If $\exists x\,q(x)$ is true, the same reasoning gives $\exists x[p(x)\lor q(x)]$. Hence the equivalence holds. $\square$ ::: :::theorem[Universal Distribution over Conjunction] Let $p(x)$ and $q(x)$ be open statements over a universe. Then $$\begin{equation*} \forall x[p(x)\land q(x)]\leftrightarrow(\forall x\,p(x)\land\forall x\,q(x)). \end{equation*}$$ ::: :::proof Given that $p(x)$ and $q(x)$ are open statements. To prove that $\forall x[p(x)\land q(x)]\leftrightarrow(\forall x\,p(x)\land\forall x\,q(x))$. First assume $\forall x[p(x)\land q(x)]$. Let $a$ be an arbitrary element of the universe. By universal specification, $p(a)\land q(a)$. By simplification, $p(a)$ and $q(a)$. Since $a$ was arbitrary, $\forall x\,p(x)$ and $\forall x\,q(x)$. Therefore $\forall x\,p(x)\land\forall x\,q(x)$. Conversely, assume $\forall x\,p(x)\land\forall x\,q(x)$. Then $\forall x\,p(x)$ and $\forall x\,q(x)$. Let $a$ be an arbitrary element of the universe. By universal specification, $p(a)$ and $q(a)$. By conjunction, $p(a)\land q(a)$. Since $a$ was arbitrary, $\forall x[p(x)\land q(x)]$. Hence the equivalence holds. $\square$ ::: :::theorem[Universal Disjunction Implication] Let $p(x)$ and $q(x)$ be open statements over a universe. Then $$\begin{equation*} (\forall x\,p(x)\lor\forall x\,q(x))\to\forall x[p(x)\lor q(x)]. \end{equation*}$$ ::: :::proof Given that $\forall x\,p(x)\lor\forall x\,q(x)$. To prove that $\forall x[p(x)\lor q(x)]$. Let $a$ be an arbitrary element of the universe. If $\forall x\,p(x)$ is true, then by universal specification, $p(a)$ is true. Therefore $p(a)\lor q(a)$ is true. If $\forall x\,q(x)$ is true, then by universal specification, $q(a)$ is true. Therefore $p(a)\lor q(a)$ is true. Thus in either case, $p(a)\lor q(a)$ is true. Since $a$ was arbitrary, $\forall x[p(x)\lor q(x)]$. Hence the implication is proved. $\square$ ::: :::solved-problem Find open statements $p(x)$, $q(x)$, and a universe such that $\forall x[p(x)\lor q(x)]$ is true, but $\forall x\,p(x)\lor\forall x\,q(x)$ is false. ::: :::solution Given the universe $U=\{1,2\}$. Define $p(x):x=1$ and $q(x):x=2$. For $x=1$, $p(1)\lor q(1)$ is true. For $x=2$, $p(2)\lor q(2)$ is true. Therefore $\forall x[p(x)\lor q(x)]$ is true. However, $\forall x\,p(x)$ is false because $p(2)$ is false. Also, $\forall x\,q(x)$ is false because $q(1)$ is false. Therefore $\forall x\,p(x)\lor\forall x\,q(x)$ is false. Hence the converse is not valid. ::: :::solved-problem Provide reasons for the steps verifying $\frac{\forall x[p(x)\lor q(x)]\qquad \exists x\,\neg p(x)\qquad \forall x[\neg q(x)\lor r(x)]\qquad \forall x[s(x)\to\neg r(x)]}{\therefore \exists x[\neg s(x)]}$. ::: :::solution Given that the four displayed premises are true. To prove that $\exists x[\neg s(x)]$. By existential specification, choose an element $a$ such that $\neg p(a)$. Then: $$\begin{equation*} \begin{array}{lll} 1. & \forall x[p(x)\lor q(x)] & \text{Premise}\\ 2. & \exists x\,\neg p(x) & \text{Premise}\\ 3. & \neg p(a) & \text{Existential Specification from 2}\\ 4. & p(a)\lor q(a) & \text{Universal Specification from 1}\\ 5. & q(a) & \text{Disjunctive Syllogism from 3 and 4}\\ 6. & \forall x[\neg q(x)\lor r(x)] & \text{Premise}\\ 7. & \neg q(a)\lor r(a) & \text{Universal Specification from 6}\\ 8. & q(a)\to r(a) & \text{Conditional equivalence from 7}\\ 9. & r(a) & \text{Modus Ponens from 5 and 8}\\ 10. & \forall x[s(x)\to\neg r(x)] & \text{Premise}\\ 11. & s(a)\to\neg r(a) & \text{Universal Specification from 10}\\ 12. & r(a) & \text{Restatement of 9}\\ 13. & \neg s(a) & \text{Modus Tollens from 11 and 12}\\ 14. & \exists x[\neg s(x)] & \text{Existential Generalization from 13} \end{array} \end{equation*}$$ Therefore $\exists x[\neg s(x)]$. Hence the argument is valid. ::: The main danger in existential specification is treating the witness as arbitrary. From $\exists x\,p(x)$ we may say “there is some $a$ such that $p(a)$,” but we may not conclude $\forall x\,p(x)$. The element $a$ is chosen because it satisfies the existential statement. It is not chosen freely from the whole universe. :::exercise Answer the following. (1) State existential specification. (2) State existential generalization. (3) Determine whether $\forall x[p(x)\lor q(x)]\to(\forall x\,p(x)\lor\forall x\,q(x))$ is valid. (4) Explain why $\exists x[p(x)\lor q(x)]$ is equivalent to $\exists x\,p(x)\lor\exists x\,q(x)$. ::: :::answer (1) From $\exists x\,p(x)$, infer $p(a)$ for some witness $a$. (2) From $p(a)$, infer $\exists x\,p(x)$. (3) It is not valid in general; use $U=\{1,2\}$, $p(x):x=1$, and $q(x):x=2$. (4) A witness satisfying a disjunction satisfies at least one disjunct, and a witness for either disjunct satisfies the disjunction. ::: :::faq[Frequently Asked Questions] Q: What is an existential witness? A: It is a particular element guaranteed by an existential statement. Q: Can an existential witness be used for universal generalization? A: No. It is not arbitrary. Q: Does $\forall$ distribute over disjunction? A: Only one implication holds in general, not a full equivalence. ::: :::call-to-action[Use Witnesses Carefully] subtitle: Practise separating arbitrary elements from existential witnesses before applying definitions in direct proofs. button: Next Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/integer-parity-definitions-and-direct-proofs button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/universal-generalization-in-theorem-proofs :::