After studying negation of quantified statements, we now allow more than one quantified variable. Multiple and nested quantifiers appear whenever a relation connects two or more objects, such as divisibility, order, equations, or array entries. The order of quantifiers matters when universal and existential quantifiers are mixed. In this lesson, multiple and nested quantifiers will be read, expanded over finite universes, and tested through examples. :::definition[Nested Quantifiers] A statement has nested quantifiers if one quantifier occurs within the scope of another quantifier. Examples include $$\begin{equation*} \forall x\exists y\,p(x,y) \end{equation*}$$ and $$\begin{equation*} \exists y\forall x\,p(x,y). \end{equation*}$$ The order of quantifiers is important when universal and existential quantifiers are mixed. ::: :::theorem[Order of Universal Quantifiers] For an open statement $p(x,y)$, $$\begin{equation*} \forall x\forall y\,p(x,y)\leftrightarrow\forall y\forall x\,p(x,y). \end{equation*}$$ Thus, the order of two universal quantifiers may be interchanged. ::: :::proof Given that $p(x,y)$ is an open statement. To prove that $\forall x\forall y\,p(x,y)\leftrightarrow\forall y\forall x\,p(x,y)$. Suppose $\forall x\forall y\,p(x,y)$ is true. Then for every value of $x$ and for every value of $y$, $p(x,y)$ is true. Therefore, for every value of $y$ and for every value of $x$, $p(x,y)$ is true. Hence $\forall y\forall x\,p(x,y)$ is true. The converse follows by the same reasoning with $x$ and $y$ interchanged. Hence the equivalence holds. $\square$ ::: :::theorem[Order of Existential Quantifiers] For an open statement $p(x,y)$, $$\begin{equation*} \exists x\exists y\,p(x,y)\leftrightarrow\exists y\exists x\,p(x,y). \end{equation*}$$ Thus, the order of two existential quantifiers may be interchanged. ::: :::theorem[Mixed Quantifiers Need Not Commute] For an open statement $p(x,y)$, $$\begin{equation*} \forall x\exists y\,p(x,y) \end{equation*}$$ is not necessarily equivalent to $$\begin{equation*} \exists y\forall x\,p(x,y). \end{equation*}$$ The order matters when universal and existential quantifiers are mixed. ::: Mixed quantifiers are easiest to read as a grid of choices. Each row fixes one value of $x$, and each column fixes one value of $y$. For $\forall x\exists y$, every row must contain at least one true cell; for $\exists y\forall x$, one column must contain true cells in every row. This visual difference explains why switching mixed quantifiers can change the meaning of a statement. :::scientific-preview[Nested Quantifier Grid Explorer] ::: :::example[Mixed Quantifiers over Integers] Let the universe be the set of all integers and let $p(x,y):x+y=17$. The statement $\forall x\exists y\,p(x,y)$ means that for every integer $x$, there exists an integer $y$ such that $x+y=17$. This is true, because for any integer $x$, choose $y=17-x$. The statement $\exists y\forall x\,p(x,y)$ means that there exists one integer $y$ such that $x+y=17$ for every integer $x$. This is false, because one fixed $y$ cannot satisfy the equation for every $x$. ::: :::solved-problem Identify the bound and free variables in $\forall y\exists z[\cos(x+y)=\sin(z-x)]$. ::: :::solution Given that the statement is $\forall y\exists z[\cos(x+y)=\sin(z-x)]$. The variable $y$ is bound by the universal quantifier $\forall y$. The variable $z$ is bound by the existential quantifier $\exists z$. The variable $x$ is not controlled by any quantifier. Therefore, $x$ is a free variable. Hence the bound variables are $y,z$, and the free variable is $x$. ::: :::solved-problem Let the universe be the set of all integers. Let $p(x,y):x$ divides $y$. Determine the truth value of $\forall y\exists x\,p(x,y)$. ::: :::solution Given that $p(x,y):x$ divides $y$. The statement means that for every integer $y$, there exists an integer $x$ such that $x$ divides $y$. For any integer $y$, choose $x=1$. Since $1$ divides every integer $y$, $p(1,y)$ is true. Therefore, for every integer $y$, there exists an integer $x$ such that $x$ divides $y$. Hence $\forall y\exists x\,p(x,y)$ is true. ::: :::solved-problem Let the universe for each variable be $\{2,3,5\}$. Express $\exists x\,p(x,5)$ and $\forall x\,p(x,3)$ without quantifiers. ::: :::solution Given that the possible values of $x$ are $2,3,5$. The statement $\exists x\,p(x,5)$ means that $p(x,5)$ is true for at least one value of $x$. Therefore, $$\begin{equation*} \exists x\,p(x,5)\leftrightarrow p(2,5)\lor p(3,5)\lor p(5,5). \end{equation*}$$ The statement $\forall x\,p(x,3)$ means that $p(x,3)$ is true for every value of $x$. Therefore, $$\begin{equation*} \forall x\,p(x,3)\leftrightarrow p(2,3)\land p(3,3)\land p(5,3). \end{equation*}$$ ::: :::definition[Identity and Inverse Statements] For the universe of all real numbers, the existence of an additive identity is written as $\exists z\forall a(a+z=z+a=a)$, and $z=0$ satisfies it. The statement “every real number has an additive inverse” is written as $\forall a\exists b(a+b=b+a=0)$. The existence of a multiplicative identity is written as $\exists z\forall a(az=za=a)$, and $z=1$ satisfies it. For nonzero real numbers, multiplicative inverse is written as $\forall a[a\neq 0\to\exists b(ab=ba=1)]$. ::: :::exercise Answer the following: over the integers, determine the truth value of $\forall x\exists y[x+y=17]$ and $\exists y\forall x[x+y=17]$; over $\{2,3,5\}$, expand $\forall x\,p(x,5)$ and $\exists x\,p(x,3)$. ::: :::answer The statement $\forall x\exists y[x+y=17]$ is true by choosing $y=17-x$. The statement $\exists y\forall x[x+y=17]$ is false. The expansions are $p(2,5)\land p(3,5)\land p(5,5)$ and $p(2,3)\lor p(3,3)\lor p(5,3)$. ::: :::faq[Frequently Asked Questions] Q: Can two universal quantifiers be interchanged? A: Yes, $\forall x\forall y$ may be interchanged with $\forall y\forall x$. Q: Can two existential quantifiers be interchanged? A: Yes, $\exists x\exists y$ may be interchanged with $\exists y\exists x$. Q: Can mixed quantifiers be interchanged? A: Not in general. $\forall x\exists y$ and $\exists y\forall x$ often have different meanings. ::: :::call-to-action[Read Quantifier Order Carefully] subtitle: Practise nested quantifiers before learning how to negate statements with several quantifier layers. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/negation-of-nested-quantified-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/negation-of-quantified-statements :::