Universal specification moves from every object to one object. Universal generalization moves in the reverse direction: if a statement is proved for an arbitrary element, then it is true for every element. This rule is essential in theorem proofs, because most universal theorems cannot be proved by checking all cases. In this lesson, universal generalization in theorem proofs is developed through quantified arguments and symbolic proof patterns. :::definition[Universal Generalization] The Rule of Universal Generalization states that if an open statement $p(x)$ is proved for an arbitrarily chosen element of the universe, then the statement is true for every element of the universe. If $c$ is chosen arbitrarily from the universe and $p(c)$ is proved, then $\forall x\,p(x)$ is true. ::: :::definition[Rule of Universal Generalization] The rule is written as $$\begin{equation*} p(c)\ \text{for arbitrary }c\quad\Longrightarrow\quad \forall x\,p(x). \end{equation*}$$ The word “arbitrary” is essential; $c$ must not be chosen because it has a special property. ::: :::definition[Universal Generalization for Two Variables] If $c$ and $d$ are chosen arbitrarily from the universe and $q(c,d)$ is proved, then $$\begin{equation*} \forall x\forall y\,q(x,y) \end{equation*}$$ is true. ::: :::remark[Arbitrary Choice] An arbitrary element is not a special element. It represents any element of the universe. If a proof uses a property that is special to one chosen element, then universal generalization cannot be applied. Thus, one may not prove a universal statement by checking only one convenient element. ::: :::theorem[Universal Generalization] Let $p(x)$ be an open statement over a universe $U$. If $p(c)$ is proved for an arbitrarily chosen element $c\in U$, then $\forall x\in U,\ p(x)$ is true. ::: :::proof Given that $c$ is an arbitrarily chosen element of $U$. Given that $p(c)$ has been proved. To prove that $\forall x\in U,\ p(x)$. Since $c$ was arbitrary, the proof did not depend on any special property of $c$. Therefore the same argument applies to every element of $U$. Hence $\forall x\in U,\ p(x)$ is true. $\square$ ::: :::definition[Associative Form inside a Universal Quantifier] For predicates $p(x)$, $q(x)$, and $r(x)$, $$\begin{equation*} \forall x[p(x)\land(q(x)\land r(x))]\leftrightarrow\forall x[(p(x)\land q(x))\land r(x)]. \end{equation*}$$ This is the associative law for conjunction applied uniformly inside a universal quantifier. ::: :::solved-problem Let $p(x)$, $q(x)$, and $r(x)$ be open statements for a given universe. Prove the validity of $\frac{\forall x[p(x)\to q(x)]\qquad \forall x[q(x)\to r(x)]}{\therefore \forall x[p(x)\to r(x)]}$. ::: :::solution Given that $\forall x[p(x)\to q(x)]$ and $\forall x[q(x)\to r(x)]$. To prove that $\forall x[p(x)\to r(x)]$. Let $c$ be an arbitrary element of the universe. By universal specification, $p(c)\to q(c)$. Again, by universal specification, $q(c)\to r(c)$. By Hypothetical Syllogism, $p(c)\to r(c)$. Since $c$ was chosen arbitrarily, universal generalization gives $\forall x[p(x)\to r(x)]$. Hence the argument is valid. ::: :::example[Algebraic Equation as Universal Syllogism] For the universe of all real numbers, define $p(x):3x-7=20$, $q(x):3x=27$, and $r(x):x=9$. The argument has the form $$\begin{equation*} \frac{\forall x[p(x)\to q(x)]\qquad \forall x[q(x)\to r(x)]}{\therefore \forall x[p(x)\to r(x)]}. \end{equation*}$$ It corresponds to the statement: if $3x-7=20$, then $3x=27$; if $3x=27$, then $x=9$; therefore, if $3x-7=20$, then $x=9$. ::: :::example[Squares, Rectangles, and Parallelograms] For the universe of all quadrilaterals in the plane, define $p(x):x$ is a square, $q(x):x$ is a rectangle, and $r(x):x$ is a parallelogram. The mathematical statement is: every square is a rectangle; every rectangle is a parallelogram; therefore every square is a parallelogram. Its symbolic form is $$\begin{equation*} \frac{\forall x[p(x)\to q(x)]\qquad \forall x[q(x)\to r(x)]}{\therefore \forall x[p(x)\to r(x)]}. \end{equation*}$$ ::: :::solved-problem Prove the validity of $\frac{\forall x[p(x)\lor q(x)]\qquad \forall x[(\neg p(x)\land q(x))\to r(x)]}{\therefore \forall x[\neg r(x)\to p(x)]}$. ::: :::solution Given that $\forall x[p(x)\lor q(x)]$ and $\forall x[(\neg p(x)\land q(x))\to r(x)]$. To prove that $\forall x[\neg r(x)\to p(x)]$. Let $c$ be an arbitrary element of the universe. By universal specification, $p(c)\lor q(c)$. Again, by universal specification, $(\neg p(c)\land q(c))\to r(c)$. Assume $\neg r(c)$. By Modus Tollens, $\neg(\neg p(c)\land q(c))$. By De Morgan’s law, $p(c)\lor\neg q(c)$. Since $p(c)\lor q(c)$ and $p(c)\lor\neg q(c)$, we obtain $p(c)$. Therefore $\neg r(c)\to p(c)$. Since $c$ was arbitrary, universal generalization gives $\forall x[\neg r(x)\to p(x)]$. Hence the argument is valid. ::: :::example[Failed Universal Generalization] Consider the statement over the universe of integers: $\forall n[n^2=n]$. For $n=0$, we have $0^2=0$. For $n=1$, we have $1^2=1$. However, for $n=2$, we have $2^2=4\neq 2$. Therefore $\forall n[n^2=n]$ is false. But $\exists n[n^2=n]$ is true, because $n=0$ and $n=1$ both satisfy the equation. ::: :::remark[One Example Does Not Prove a Universal Statement] Checking a single element may prove an existential statement, but it does not prove a universal statement. Thus $p(a)$ may show $\exists x\,p(x)$, but it does not show $\forall x\,p(x)$. ::: :::solved-problem Provide reasons for the steps verifying $\frac{\forall x[p(x)\to(q(x)\land r(x))]\qquad \forall x[p(x)\land s(x)]}{\therefore \forall x[r(x)\land s(x)]}$. ::: :::solution Given that $\forall x[p(x)\to(q(x)\land r(x))]$ and $\forall x[p(x)\land s(x)]$. To prove that $\forall x[r(x)\land s(x)]$. Let $a$ be an arbitrary element of the universe. $$\begin{equation*} \begin{array}{lll} 1. & \forall x[p(x)\to(q(x)\land r(x))] & \text{Premise}\\ 2. & \forall x[p(x)\land s(x)] & \text{Premise}\\ 3. & p(a)\to(q(a)\land r(a)) & \text{Universal Specification from 1}\\ 4. & p(a)\land s(a) & \text{Universal Specification from 2}\\ 5. & p(a) & \text{Simplification from 4}\\ 6. & q(a)\land r(a) & \text{Modus Ponens from 3 and 5}\\ 7. & r(a) & \text{Simplification from 6}\\ 8. & s(a) & \text{Simplification from 4}\\ 9. & r(a)\land s(a) & \text{Conjunction from 7 and 8}\\ 10. & \forall x[r(x)\land s(x)] & \text{Universal Generalization from 9} \end{array} \end{equation*}$$ Therefore the conclusion follows. Hence the argument is valid. ::: :::solved-problem Write the following argument in symbolic form and determine whether it is valid. All credit union employees must know COBOL. All credit union employees who write loan applications must know Quattro. Roxe works for the credit union, but she does not know Quattro. Imogene knows Quattro but does not know COBOL. Therefore Roxe does not write loan applications and Imogene does not work for the credit union. ::: :::solution Given the universe of all adults presently residing in Las Cruces. Let $C(x):x$ works for the credit union, $B(x):x$ knows COBOL, $W(x):x$ writes loan applications, and $Q(x):x$ knows Quattro. Let Roxe be $r$ and Imogene be $i$. The premises are $\forall x[C(x)\to B(x)]$, $\forall x[(C(x)\land W(x))\to Q(x)]$, $C(r)\land\neg Q(r)$, and $Q(i)\land\neg B(i)$. The conclusion is $\neg W(r)\land\neg C(i)$. From $C(r)\land\neg Q(r)$, we get $C(r)$ and $\neg Q(r)$. By universal specification, $(C(r)\land W(r))\to Q(r)$. Using Modus Tollens with $\neg Q(r)$, we get $\neg(C(r)\land W(r))$. By De Morgan’s law, $\neg C(r)\lor\neg W(r)$. Since $C(r)$ is true, $\neg W(r)$ follows. From $Q(i)\land\neg B(i)$, we get $\neg B(i)$. By universal specification, $C(i)\to B(i)$. Using Modus Tollens, $\neg C(i)$ follows. Therefore $\neg W(r)\land\neg C(i)$. Hence the argument is valid. ::: :::exercise Answer the following. (1) State the rule of universal generalization. (2) Explain why $p(0)$ alone cannot prove $\forall x\,p(x)$. (3) Prove symbolically that $\forall x[p(x)\to q(x)]$ and $\forall x[q(x)\to r(x)]$ imply $\forall x[p(x)\to r(x)]$. ::: :::answer (1) If $p(c)$ is proved for an arbitrary element $c$, then $\forall x\,p(x)$ follows. (2) The element $0$ may have a special property, so it does not represent every element unless it was chosen arbitrarily and the proof used no special feature. (3) Choose arbitrary $c$. From the premises get $p(c)\to q(c)$ and $q(c)\to r(c)$ by universal specification. Then $p(c)\to r(c)$ by Hypothetical Syllogism. Since $c$ was arbitrary, $\forall x[p(x)\to r(x)]$. ::: :::faq[Frequently Asked Questions] Q: What is the difference between universal specification and universal generalization? A: Specification moves from all elements to one element; generalization moves from an arbitrary element to all elements. Q: Why must the chosen element be arbitrary? A: Otherwise the proof may depend on a special property not shared by the whole universe. Q: Can one example prove an existential statement? A: Yes. One valid witness proves an existential statement, but not a universal statement. ::: :::call-to-action[Generalize Only from Arbitrary Elements] subtitle: Practise proving statements for arbitrary elements before using existential rules and quantifier laws. button: Next Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/quantifier-laws-and-existential-rules button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/universal-specification-in-quantified-arguments :::