After translating quantifiers in mathematics and programming, we now study their exact truth conditions. Truth conditions for quantified statements tell us how to prove or disprove existential and universal statements. An existential statement needs one witness, while a universal statement must survive every element of the universe. In this lesson, truth conditions for quantified statements will be used to translate, evaluate, and find counterexamples. :::definition[Truth Condition for Existential Quantification] Let $p(x)$ be an open statement over a universe $U$. The statement $\exists x\,p(x)$ is true if $p(a)$ is true for at least one $a\in U$. It is false if $p(a)$ is false for every $a\in U$. ::: :::definition[Truth Condition for 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 $a\in U$. It is false if $p(a)$ is false for at least one $a\in U$. ::: :::definition[Truth Condition for Negated Existential Quantification] The statement $\exists x\,\neg p(x)$ is true if $p(a)$ is false for at least one $a\in U$. It is false if $p(a)$ is true for every $a\in U$. ::: :::definition[Truth Condition for Negated Universal Quantification] The statement $\forall x\,\neg p(x)$ is true if $p(a)$ is false for every $a\in U$. It is false if $p(a)$ is true for at least one $a\in U$. ::: :::definition[Counterexample] A counterexample to a universal statement is an element of the universe for which the open statement is false. To disprove $\forall x\,p(x)$, it is enough to find one element $a$ such that $p(a)$ is false. ::: :::solved-problem Let the universe be the set of all integers. Let $q(x):x$ is even. Write symbolically and determine the truth value of “at least one integer is even.” ::: :::solution Given that $q(x)$ means $x$ is even. The statement says that there exists an integer $x$ such that $x$ is even. Therefore, the symbolic form is $$\begin{equation*} \exists x\,q(x). \end{equation*}$$ Since $2$ is an even integer, $q(2)$ is true. Hence $\exists x\,q(x)$ is true. ::: :::solved-problem Let the universe be the set of all integers. Let $q(x):x$ is even and $t(x):x$ is divisible by $5$. Write symbolically and determine the truth value of “No even integer is divisible by $5$.” ::: :::solution Given that $q(x)$ means $x$ is even and $t(x)$ means $x$ is divisible by $5$. The sentence says that for every integer $x$, if $x$ is even, then $x$ is not divisible by $5$. Therefore, the symbolic form is $$\begin{equation*} \forall x[q(x)\to\neg t(x)]. \end{equation*}$$ This statement is false. The integer $10$ is even and divisible by $5$. Thus $10$ is a counterexample. ::: :::solved-problem Let the universe be the set of all integers. Let $q(x):x$ is even, $r(x):x$ is a perfect square, and $s(x):x$ is divisible by $4$. Write symbolically and determine the truth value of “If $x$ is even and $x$ is a perfect square, then $x$ is divisible by $4$.” ::: :::solution Given that $q(x)$ means $x$ is even, $r(x)$ means $x$ is a perfect square, and $s(x)$ means $x$ is divisible by $4$. The symbolic form is $$\begin{equation*} \forall x[(q(x)\land r(x))\to s(x)]. \end{equation*}$$ Suppose $x$ is even and $x$ is a perfect square. Since $x$ is even, there exists an integer $k$ such that $x=2k$. Since $x$ is a perfect square and even, the prime $2$ must occur with even positive exponent in the prime factorization of $x$. Therefore the exponent of $2$ is at least $2$, so $4$ divides $x$. Hence the quantified statement is true. ::: To prove an existential statement, give a witness: one element that satisfies the predicate. To disprove an existential statement, show that every element fails. To prove a universal statement, argue for an arbitrary element of the universe. To disprove a universal statement, give one counterexample. These four patterns should be memorised because they reappear in all later proof work. A witness is a value that makes an existential statement true, while a counterexample is a value that makes a universal statement false. Choose a finite integer range and one quantified statement from the lesson. The calculator checks every integer in the selected range and reports the first useful witness or counterexample when one appears. This is a finite model, so it is best used to understand the proof pattern before writing a full argument over all integers. :::calculator[Witness and Counterexample Tester] ::: :::exercise Let the universe be the set of all integers. Let $p(x):x>0$, $q(x):x$ is even, $r(x):x$ is a perfect square, $s(x):x$ is divisible by $4$, and $t(x):x$ is divisible by $5$. Write each statement symbolically and determine its truth value: at least one integer is even; there exists a positive integer that is even; if $x$ is even, then $x$ is not divisible by $5$; there exists an even integer divisible by $5$; if $x$ is even and a perfect square, then $x$ is divisible by $4$. ::: :::answer The answers are $\exists x\,q(x)$ true, $\exists x[p(x)\land q(x)]$ true, $\forall x[q(x)\to\neg t(x)]$ false with counterexample $10$, $\exists x[q(x)\land t(x)]$ true with witness $10$, and $\forall x[(q(x)\land r(x))\to s(x)]$ true. ::: :::faq[Frequently Asked Questions] Q: What proves an existential statement? A: One valid example from the universe proves it. Q: What disproves a universal statement? A: One counterexample from the universe disproves it. Q: Is a counterexample the same as a random example? A: No. It must satisfy the hypothesis and make the claimed conclusion false. ::: :::call-to-action[Use Witnesses and Counterexamples] subtitle: Practise truth conditions before studying implication and equivalence between predicates. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/logical-equivalence-and-implication-of-predicates button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/quantifiers-in-programming-statements :::