After learning open statements and universe of discourse, we now ask how to turn an open statement into a complete statement without substituting a particular value. Existential and universal quantifiers do this by saying that a predicate is true for at least one element or for every element of the universe. These quantifiers are central to definitions, theorems, programming specifications, and mathematical proofs. In this lesson, existential and universal quantifiers will be read, interpreted, and tested through examples. :::definition[Existential Quantifier] The symbol $\exists$ is called the existential quantifier. The statement $$\begin{equation*} \exists x\,p(x) \end{equation*}$$ is read as “there exists an $x$ such that $p(x)$.” It also means “for some $x$,” “for at least one $x$,” or “there is an $x$ such that $p(x)$.” ::: :::definition[Universal Quantifier] The symbol $\forall$ is called the universal quantifier. The statement $$\begin{equation*} \forall x\,p(x) \end{equation*}$$ is read as “for every $x$, $p(x)$.” It also means “for all $x$,” “for each $x$,” or “for every $x$, $p(x)$.” ::: :::definition[Existential Quantification] Let $p(x)$ be an open statement over a universe $U$. The statement $\exists x\,p(x)$ is true if there is at least one element $a\in U$ such that $p(a)$ is true. ::: :::definition[Universal Quantification] Let $p(x)$ be an open statement over a universe $U$. The statement $\forall x\,p(x)$ is true if $p(a)$ is true for every element $a\in U$. ::: :::definition[Free Variable] A variable is called a free variable if it is not controlled by a quantifier. For example, in $$\begin{equation*} \forall x\,p(x,y), \end{equation*}$$ the variable $x$ is bound, but $y$ is free. ::: :::definition[Bound Variable] A variable is called a bound variable if it is controlled by a quantifier. For example, in $$\begin{equation*} \forall x\exists y\,p(x,y), \end{equation*}$$ both $x$ and $y$ are bound variables. ::: :::theorem[Universal Quantification Implies Existential Quantification] Let the universe of discourse be nonempty. If $\forall x\,p(x)$ is true, then $\exists x\,p(x)$ is true: $$\begin{equation*} \forall x\,p(x)\to\exists x\,p(x). \end{equation*}$$ ::: :::proof Given that the universe of discourse is nonempty. To prove that $\forall x\,p(x)\to\exists x\,p(x)$. Suppose $\forall x\,p(x)$ is true. Since the universe is nonempty, there exists at least one element $a$ in the universe. Since $p(x)$ is true for every $x$, it follows that $p(a)$ is true. Therefore, there exists an element $a$ such that $p(a)$ is true. Hence $\exists x\,p(x)$ is true. $\square$ ::: :::solved-problem Let the universe be the set of all real numbers. Let $p(x):x\geq 0$, $q(x):x^2\geq 0$, $r(x):x^2-3x-4=0$, and $s(x):x^2-3>0$. Determine the truth value of $\exists x[p(x)\land r(x)]$. ::: :::solution Given that the universe is the set of all real numbers. The statement says that there exists a real number $x$ such that $x\geq 0$ and $x^2-3x-4=0$. Solve $$\begin{align*} x^2-3x-4&=0\\ (x-4)(x+1)&=0. \end{align*}$$ Thus $x=4$ or $x=-1$. Since $x=4$ satisfies $x\geq 0$, there exists a real number satisfying both conditions. Hence $\exists x[p(x)\land r(x)]$ is true. ::: :::solved-problem Let the universe be the set of all real numbers. Let $p(x):x\geq 0$ and $q(x):x^2\geq 0$. Determine the truth value of $\forall x[p(x)\to q(x)]$. ::: :::solution Given that the universe is the set of all real numbers. The statement says that every real number satisfying $x\geq 0$ also satisfies $x^2\geq 0$. If $x\geq 0$, then the square of $x$ is nonnegative. Therefore $x^2\geq 0$. Hence $\forall x[p(x)\to q(x)]$ is true. ::: :::example[Class Roster Translation] Let the universe be all students at a university. Let $c(x):x$ is in the class, $j(x):x$ is a junior, and $m(x):x$ is a mathematics major. The sentence “There is a mathematics major in the class who is a junior” is written as $$\begin{equation*} \exists x[c(x)\land m(x)\land j(x)]. \end{equation*}$$ The existential quantifier is used because the sentence asks for at least one student with all three properties. ::: :::exercise Let the universe be the set of all real numbers. With $p(x):x\geq 0$, $q(x):x^2\geq 0$, $r(x):x^2-3x-4=0$, and $s(x):x^2-3>0$, determine the truth values of $\exists x[p(x)\land r(x)]$, $\forall x[p(x)\to q(x)]$, $\forall x[q(x)\to s(x)]$, $\forall x[r(x)\lor s(x)]$, and $\forall x[r(x)\to p(x)]$. ::: :::answer The truth values are true, true, false, false, and false respectively. The witnesses or counterexamples are $x=4$, any nonnegative real, $x=0$, $x=0$, and $x=-1$ respectively. ::: :::faq[Frequently Asked Questions] Q: Does $\exists x\,p(x)$ mean every $x$ works? A: No. It means at least one element in the universe works. Q: Does $\forall x\,p(x)$ allow exceptions? A: No. One counterexample makes the universal statement false. Q: Why must the universe be stated? A: The truth of a quantified statement depends on which values are allowed. ::: :::call-to-action[Practise Quantifier Meaning] subtitle: Translate quantified statements before studying how context can hide the intended quantifier. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/implicit-quantification-and-universe-dependence button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/open-statements-and-universe-of-discourse :::