Module 1: Basic Set Theory
Module 2: Modular Arithmetic, Divisibility, and the Fundamental Theorem of Arithmetic
Module 3: Functions and Relations
Module 4: Truth Tables and Symbolic Logic
Module 5: Basic Direct Proofs
Module 6: Proof Techniques Part 1: Contrapositive and Contradiction
Module 7: Sequences, Sums, and Products
Module 8: Proof Techniques Part 2: (Weak) Induction
Module 9: Recurrence Relations and Recursion
Module 10: Counting Systems (Binary, Hex, Octal, etc.)
Module 11: Combinatorics
Module 12: Graph Theory
Module 13: Review

Universal and Existential Quantifiers

For example, the predicate “\(x+1=0\)” (as in the sentence above) could be assumed to have domain \(\mathbb{R}\); i.e. one could substitute any real number in for \(x\) into that predicate. The statement you get after plugging in a number may be true or it may be false. In a sense, predicates are functions that have a domain (same as the domain of their predicate variables) that map to either “True” or “False.” In fact, we often write predicates using function notation. This is seen in the following definition.

To illustrate the definition a bit, let \(P(x)\) be the predicate “x+1=0.” As we mentioned above, the domain of \(P(x)\) can be assumed to be \(\mathbb{R}\), the set of all real numbers. The statement \(\forall x\in D, P(x)\), that is,

\(\forall x\in \mathbb{R}, x+1=0\)

evaluates to “False,” because what we are claiming (in English) is that “for every possible real number \(x\), it is the case that \(x+1=0\).” To see that this is false, a counterexample for the statement is \(x=1\). Just plug in \(x=1\) to see that the equation \(x+1=0\) is false.

Quick Example

Let \(P(x)\) be the predicate \(x+5>0\) and let the domain of \(P(x)\) be \(D=\{-1,-2,-3,-4\}\). Is the statement “\(\forall x\in D, x+5>0\)” true? How would you verify that, intuitively?

In this case, one could show the whole universal statement to be true simply by substituting each element of \(D\) into the predicate \(x+5>0\) and verify that it is true; i.e. \(-1+5=4>0\) so \(P(x)\) is true for \(x=-1\); \(-2+5=3>0\) so \(P(x)\) is true for \(x=-2\); \(-3+5=2>0\) so \(P(x)\) is true for \(x=-3\); \(-4+5=1>0\) so \(P(x)\) is true for \(x=-4\).

This technique for proving universal statements to be true is called either brute force or, more formally, method of (or proof by) exhaustion. This method works well when the predicate of your domain is finite, because you can practically check the truth of your predicate for each element of \(D\) that you plug in.

However, when \(D\) is infinite, it is impossible to confirm by brute force that your predicate holds. Take, for example, the predicate \(P(x)\) defined as \(x+5>0\) (as above) and let the domain of variable \(x\) to be \(D=\{-4,-3,-2,-1,0,1,…\}\). Then, to prove that the statement \(\forall x\in D, x+5>0\) by brute force, we would need to plug in \(x=-4,-3,-2,-1,0,1,…\) to see if \(x+5>0\) holds. Not a good use of time. We will develop methods for proving universally quantified statements in future lessons.

Quick Example

Let \(Q(x)\) be the predicate “\(x\leq 3\)” and let the domain of \(x\) in this predicate be the set of all natural numbers \(\mathbb{N}\). Is the statement “\(\exists x\in \mathbb{N}\) such that \(x\leq 3\)” true? How would you verify this?

One way to prove an existential statement is to find an example of an element in the domain for which the statement holds. Such an example is called a witness. In our case, one witness for the statement “\(\exists x\in \mathbb{N}\) such that \(x\leq 3\)” is \(x=2\). Another is \(x=1\).

If you can find a witness for an existential statement, then the statement is true. However, NOT being able to find a witness does NOT mean the statement is false! There are objects in math that can be proven to exist (using deduction via a set of axioms), yet have no example for you to find!

Translating Quantified Statements into English

More often than not, mathematical statements don’t look like “\(\exists x\in \mathbb{N}\) such that \(x\leq 3\)” or “\(\forall x\in \mathbb{N}\),\(x>0\),” i.e. they don’t usually have the quantifiers \(\exists\) or \(\forall\). However, every mathematical statement (of interest and that we typically care about) can be expressed using these quantifiers. In fact, even that last sentence can be expressed using quantifiers and be made mathematically precise!

Being able to convert an informally presented mathematical statement (without quantifiers) to a more formal presentation (with quantifiers) will help with trying to prove such a statement precisely (see future lessons). It is also beneficial at times to translate formal statements with quantifiers to informal statements without quantifiers because it helps one understand what the quantified statement is trying to communicate. Both translations will be demonstrated below.

Translating from Formal Statements to Informal Statements

The following examples demonstrate how one could translate from a formally presented statement to an informal, “plain English” statement. All this entails (more or less) is “spelling out, verbally” what the symbols are saying.

Note that the statements given may not be true. We are merely expressing symbolic statements verbally without consideration of truth. Note also that there are many different ways of informally expressing the same formally presented statement. Below also lists an implicitly quantified informal statement, which is nothing more than an almost colloquial way of saying the same thing as the formal or informal statement given.

Formal StatementInformal StatementImplicitly Quantified Statement
“\(\forall x\in \mathbb{Z}, x\) is prime”“For each integer \(x\), \(x\) is prime”“Every integer is prime”
“\(\exists y\in \mathbb{N}\) such that \(31\leq y\leq 33\)”“There exists a natural number \(y\) that is greater than \(31\) and less than \(33\).”“There is a natural number between \(31\) and \(33\).”
“\(\forall x,y\in \mathbb{Z},\) if \(x\vert y\), then \(x\leq y\)”“For every pair of integers \(x\) and \(y\), if \(x\) divides \(y\) then \(x\) is no greater (or “less than or equal to” if you prefer) than \(y\).”“If \(x\) divides \(y\), then \(x\) is less than or equal to \(y\).”
“\(\exists n\in \mathbb{N}\) such that \(n\vert 1000\)”“There exists a natural number \(n\) that divides \(1000\).”“There is a natural number that divides \(1000\).”
“\(\forall n\in \mathbb{N}, \exists m\in \mathbb{N}\) such that \(m>n\)”“For every natural number \(n\) there exists a natural number \(m\) that is greater than \(n\).”“Every natural number has another natural number greater than itself.”

Pro-tip: When converting from a formal statement to an informal statement, make sure that your informal statement says essentially the same thing as the formal statement without any loss of (or extra) meaning. Always ask yourself “are these two statements saying exactly the same thing?”

Translating from Informal statements to Formal Statements

More often than not, quantified mathematical statements are given implicitly or informally and need to be translated (at least somewhat) into fully quantified formal statements before one sets out to prove them. This process is usually done subconsciously once you’ve had enough practice translating into and out of formal quantified statements.

Tips for Translating to Formal Quantified Statements

  • Words like “all,” “every,” “each,” indicate the need for a universal quantifier
  • Words/phrases like “there is a,” “some,” “exists,” indicate the need for an existential quantifier.
Implicitly Quantified StatementInformal StatementFormal Quantified Statement
“There is a prime less than 3”“There exists a natural number \(p\) such that \(p\) is prime and \(p<3\)”“\(\exists p\in \mathbb{N}\) such that \(p\) is prime \(\wedge p<3\)”
“Every prime number is divisible by itself”“For every natural number \(p\) that is prime, \(p\) divides \(p\)”“\(\forall p\in \mathbb{N},\) if \(p\) is prime, then \(p\vert p\).”
“If \(0<x<1\), then \(x^2<x\)”“For every real number \(x\) (or so we assume), if \(0<x<1\) then \(x^2<x\).”“\(\forall x\in \mathbb{R},\) if \(0<x<1\) then \(x^2<x\).”
“There is a natural number greater than or equal to every other natural number” (obviously false statement)“There exists a natural number \(n\) such that for every natural number \(m\), \(n\geq m\).”“\(\exists n\in \mathbb{N}, \forall m\in \mathbb{N}, n\geq m\)”

Protip: Again, it is absolutely critical to make sure that your conversions express exactly the same idea. DO NOT blindly rely on examples you have seen to help you with these conversions! The easiest and best way to get good at these conversions (and understanding math as a whole) is to try to understand the underlying idea that is being communicated in each statement given.

Note: Converting definitions and relations to their formally quantified form is usually NOT trivial! This is especially true when you are trying to reduce the number of quantifiers being used to bare minimum (stuff logicians and computability theorists care about).

Before You Start!

Note that the answers given below will be different from the ones you get. This is okay as there are many different ways of expressing the same ideas. I highly encourage you to think understand the meaning of statements and express your thoughts based on that meaning. DO NOT try to model the phrasing of your work on what you see in the solutions below! There is no “standard” way of doing most of these problems!

The statement is true. Note that \(1,…,5\), i.e. all the elements of \(D\), are less than \(6\). So, it is the case that “\(\forall x\in D, x<6\).”

The statement is true. Note that \(p=2\) is prime and \(2\ \text{mod}\ 2=0\). Therefore, \(\exists p\in P\) such that \(p\ \text{mod}\ 2=0\) is true.

This statement is false. Let \(n=4\), then \(4\ \text{mod}\ 2=0\) instead of \(4\ \text{mod}\ 2=1\). Therefore, we have found a counterexample to the statement “\(\forall n\in E,\ n\ \text{mod}\ 2=1\),” proving it false.

The statement is false. To show this, notice that none of \(2,5,7,13\) or \(17\) divide \(33\), so there can’t exist a number \(a\in S\) such that \(a\vert 33\). Put another way, for every number \(a\) in \(S\), \(a\not|\ 33\).

  1. “\(\forall n\in \mathbb{N},\ n\vert 20\)”
  2. “\(\forall x\in \mathbb{Z}, x\in \mathbb{R}\)”
  3. “\(\forall y\in \mathbb{N},\) if \(y\geq 5\) then \(y\geq 4\).”
  4. “\(\exists n\in \mathbb{Z}\) such that \(n>5\) or \(n\leq 6\)”
  5. “\(\exists m\in \mathbb{Z}\) such that \(m\ \text{mod}\ 5=3\)”
  6. “\(\exists x\in \mathbb{R}\) such that \(\forall y\in \mathbb{R}, x<y\)”
  7. “\(\forall x\in \mathbb{R}, \exists y\in \mathbb{R}\) such that \(x-y=0\).”
Original StatementInformal StatementImplicitly Quantified Statement (not required)
“\(\forall n\in \mathbb{N},\ n\vert 20\)”“For every natural number \(n\), \(n\) divides \(20\)”“Every natural number divides \(20\).”
“\(\forall x\in \mathbb{Z}, x\in \mathbb{R}\)”“For every integer \(x\), \(x\) is (also) a real number.”“Every integer is a real number”
“\(\forall y\in \mathbb{N},\) if \(y\geq 5\) then \(y\geq 4\).”“For every natural number \(y\), if \(y\) is no less than (or “greater than or equal to” if you’d prefer) 5, then \(y\) is no less than \(4\)”“Every natural number that is greater than or equal to \(5\) is also greater than or equal to \(4\).”
“\(\exists n\in \mathbb{N}\) such that \(n>5\) or \(n\leq 6\)”“There exists a natural number \(n\) such that \(n\) is greater than \(5\) or \(n\) is less than or equal to \(6\)”“There is a natural number greater than \(5\) or less than or equal to \(6\)”
“\(\exists m\in \mathbb{Z}\) such that \(m\ \text{mod}\ 5=3\)”“There exists an integer \(m\) such that \(m\ \text{mod}\ 5=3\)”“There is an integer that has a remainder of \(3\) when divided by \(5\).”
“\(\exists x\in \mathbb{R}\) such that \(\forall y\in \mathbb{R}, x<y\)”“There exists a real number \(x\) such that, for every real number \(y)\), \(x\) is strictly less than \(y\)”“There is a real number that every real number is greater than”
“\(\forall x\in \mathbb{R}, \exists y\in \mathbb{R}\) such that \(x-y=0\).”“For every real number \(x\) there is a real number \(y\) such that \(x-y=0\)”can’t really simplify the implicit statement any more.
  1. “\(\forall x\in \mathbb{R},\ (x+1)(x-1)=x^2-1\)”
  2. “\(\exists n\in \mathbb{N}\) such that \(n^2\equiv 1\ (\text{mod}\ 2)\)”
  3. “\(\exists x\in \mathbb{R}\) such that \(x^2=x\)”
  4. “\(\forall m\in \mathbb{Z},\) if \(m\) is even, then \(m\ \text{mod}\ 2 =0\)”
  5. “\(\exists y\in \mathbb{N}\) such that if \(y\) is odd, then \(y\vert 100\).”
  6. “\(\forall n\in \mathbb{N}, \exists m\in \mathbb{N}\) such that \(n\vert m\)”
  7. “\(\exists n\in \mathbb{N}\) such that \(\forall m\in \mathbb{N},\ n=m\cdot 2\)”
Original StatementInformal StatementImplicitly Quantified Statement (not required)
“\(\forall x\in \mathbb{R},\ (x+1)(x-1)=x^2-1\)”“For every real number \(x\), \((x+1)(x-1)=x^2-1\)”“\((x+1)(x-1)=x^2-1\) for every real number \(x\).”
“\(\exists n\in \mathbb{N}\) such that \(n^2\equiv 1\ (\text{mod}\ 2)\)”“There is a natural number \(n\) so that \(n^2\) is conguent to \(1\) modulo \(2\).”“There is a natural number whose square is congruent to \(1\) modulo \(2\).”
“\(\exists x\in \mathbb{R}\) such that \(x^2=x\)”“There is a real number \(x\) such that \(x^2=x\)”“There is a real number equal to its own square.”
“\(\forall m\in \mathbb{Z},\) if \(m\) is even, then \(m\ \text{mod}\ 2 =0\)”“For every integer \(m\), if \(m\) is even, then \(m\ \text{mod}\ 2=0\)”“If \(m\) is even, then \(m\ \text{mod}\ 2=0\)”
“\(\exists y\in \mathbb{N}\) such that if \(y\) is odd, then \(y\vert 100\).”“There is a natural number \(y\) such that if \(y\) is odd, then \(y\) divides \(100\)”“There is some natural number that, if it is odd, then it divides 100”
“\(\forall n\in \mathbb{N}, \exists m\in \mathbb{N}\) such that \(m\vert n \)”“For every natural number \(n\), there is a natural number \(m\) so that \(m\) divides \(n\)”“Every natural number is divisible by some (other) natural number”
“\(\exists n\in \mathbb{N}\) such that \(\forall m\in \mathbb{N},\ n=n\cdot m\)”“There exists a natural number \(n\) so that for every natural number \(m\), we have \(n=n\cdot m\).”“There is a natural number that is the product of any other natural number with itself.”
  1. “Every natural number is prime or composite” (Don’t need symbols for “prime” and “composite”)
  2. “\(x^2+2x+1=(x+1)^2\)” (Hint: what sort of number is \(x\) in these sorts of statements?)
  3. “There is a natural number that is divisible by \(7\)”
  4. “There is a natural number that is less than or equal to all other natural numbers”
  5. “There is no natural number less than 1”
  6. “There is no real number greater than all other real numbers.”
  7. “Every even number can be written as the product of 2 times some integer”
Original Implicitly Quantified StatementInformal Statement (not required for this problem)Formally Quantified Statement
“Every natural number is prime or composite”“For every natural number \(n\), \(n\) is prime or composite”“\(\forall n\in \mathbb{N}\), \(n\) is prime, or \(n\) is composite”
“\(x^2+2x+1=(x+1)^2\)”“For every real number \(x\), \(x^2+2x+1=(x+1)^2\)”“\(\forall x\in \mathbb{R}, x^2+2x+1=(x+1)^2\).”
“There is a natural number that is divisible by \(7\)”“There exists a natural number \(n\) such that \(7\vert n\)”“\(\exists n\in \mathbb{N}\) such that \(7\vert n\).”
“There is a natural number that is less than or equal to all other natural numbers”“There exists a natural number \(n\) such that, for any natural number \(m\), \(n\leq m\)”“\(\exists n\in \mathbb{N}\) such that \(\forall m\in \mathbb{N}, n\leq m\)”
“There is no natural number less than 1”“For every natural number \(n\), \(n\) is not less than \(1\).”
OR
“There does not exist a natural number \(n\) that is less than \(1\)”
“\(\forall n\in \mathbb{N}, n\not< 1\)”
OR
“\(\not\exists n\in \mathbb{N}\) such that \(n<1\)”
“There is no real number greater than all other real numbers.”“For every real number \(x\), there exists a real number \(y\) so that \(x\leq y\)”
OR
“There does not exist a real number \(x\) such that for every real number \(y\), \(y<x\).”
“\(\forall x\in \mathbb{R},\exists y\in \mathbb{R}\) such that \(x\leq y\)”
OR
“\(\not\exists x\in \mathbb{R}\) such that \(\forall y\in \mathbb{R}, (y<x)\)”
“Every even integer can be written as the product of 2 times some integer”“For every integer \(n\), if \(n\) is even, then there exists some integer \(m\) such that \(n=2\cdot m\)”“\(\forall n\in \mathbb{Z},\) if \(n\) is even, then \(\exists m\in \mathbb{Z}\) such that \(n=2\cdot m\).”
  1. “For every real number \(x\), \(0<x\) or \(x\leq 0\)”
  2. “There exists a natural number \(n\) such that \(3\vert n\).”
  3. “For every pair of real numbers \(x,y\), there is a real number \(z\) such that \(x\leq z\leq y\).”
  4. “There is an integer \(m\) such that for all natural numbers \(n\), \(m<n\)”
Original Informal StatementFormally Quantified Statement
“For every real number \(x\), \(0<x\) or \(x\leq 0\)”“\(\forall x\in \mathbb{R}, 0<x\ or\ x\leq 0\)”
“There exists a natural number \(n\) such that \(3\vert n\).”“\(\exists n\in \mathbb{N}\) such that \(3\vert n\)”
“For every pair of real numbers \(x,y\), there is a real number \(z\) such that \(x\leq z\leq y\).”“\(\forall x,y\in \mathbb{R},\exists z\in \mathbb{R}\) such that \(x\leq z\leq y\)”
“There is an integer \(m\) such that for all natural numbers \(n\), \(m<n\)”“\(\exists m\in \mathbb{Z}\) such that \(\forall n\in \mathbb{N}, (m<n)\)”
Scroll to Top