Key takeaways
- A predicate such as P(x): x > 3 is not true or false until x is given a value or the statement is quantified.
- ∀x P(x) says P(x) holds for every x in the domain; ∃x P(x) says it holds for at least one.
- The domain matters: ∃x (x² = 2) is true over the real numbers and false over the integers.
- Universal statements usually pair with an implication, ∀x (S(x) → P(x)), and existential statements with a conjunction, ∃x (S(x) ∧ P(x)).
- Quantifiers of the same kind can be swapped, but ∀x ∃y and ∃y ∀x usually mean different things.
Propositional logic deals with whole statements: "it is raining", "the program halts". It cannot say "every integer has a successor" or "some prime is even", because those sentences are about the members of a collection. Predicates and quantifiers add that ability, and definitions such as "n is even if n = 2k for some integer k" are written with them.
Predicates: statements with a blank
A predicate is a statement with one or more variables, such as
P(x): x is greater than 3.
P(x) is neither true nor false yet. P(5) is true and P(2) is false. Levin's Discrete Mathematics: An Open Introduction draws the line the same way: a sentence that contains variables is called a predicate, and while a variable is left free it is not yet a statement. Predicates can have several variables too: L(x, y): "x is less than y" makes L(2, 7) true and L(7, 2) false.
There are two ways to turn a predicate into a statement with a truth value: give each variable a value, or quantify it.
The two quantifiers
| Symbol | Name | Read as | ∀x P(x) / ∃x P(x) is true when |
|---|---|---|---|
| ∀ | Universal quantifier | "for all", "for every" | P(x) holds for every x in the domain |
| ∃ | Existential quantifier | "there exists", "for some" | P(x) holds for at least one x in the domain |
"At least one" is the important phrase. ∃x P(x) is true if one element works and also if all of them do. It does not mean "exactly one"; that needs extra notation, usually written ∃!.
The domain changes the answer
Every quantified statement is about some domain (also called the universe or domain of discourse). Applied Discrete Structures writes it as a subscript on the quantifier, which keeps it in view, and it needs to be: the same formula can be true over one domain and false over another.
- ∃x (x² = 2) is true over the real numbers (x = √2) and false over the integers.
- ∀x (x² ≥ x) is true over the integers, since 0 and 1 give equality and every other integer gives a larger square, but false over the real numbers: x = 0.5 gives 0.25, which is less than 0.5.
- ∀x (x + 1 > x) is true over any of the usual number systems.
When a question does not state the domain, assume the one the course has been using, and when you write a statement yourself, say what the domain is.
Translating English into quantifiers
Take the domain to be all people, with S(x): "x is a student" and P(x): "x passed".
| English | Symbols |
|---|---|
| Every student passed. | ∀x (S(x) → P(x)) |
| Some student passed. | ∃x (S(x) ∧ P(x)) |
| No student passed. | ∀x (S(x) → ¬P(x)), or ¬∃x (S(x) ∧ P(x)) |
| Not every student passed. | ¬∀x (S(x) → P(x)), or ∃x (S(x) ∧ ¬P(x)) |
The pairing in the first two rows is a rule worth memorising: ∀ goes with →, ∃ goes with ∧.
Here is why. ∀x (S(x) ∧ P(x)) says everyone is a student and everyone passed, a much stronger claim than intended. And ∃x (S(x) → P(x)) is true as soon as there is anyone who is not a student, because a conditional with a false hypothesis is true; that is far too weak. The truth table guide shows why a false hypothesis makes a conditional true.
The same structures underlie classical syllogisms such as "all A are B, some C are A, so some C are B", which the syllogisms guide treats in everyday language.
Nested quantifiers and the order problem
Statements with two variables often need two quantifiers, and then order matters. Quantifiers of the same kind can be rearranged freely, but Applied Discrete Structures warns that when existential and universal quantifiers are mixed, the order cannot be exchanged without possibly changing the meaning.
Its example, over the positive real numbers:
- ∀a ∃b (ab = 1): for every a there is some b with ab = 1. True: take b = 1/a.
- ∃b ∀a (ab = 1): there is one b that works for every a. False: if b works for a = 1, then b = 1, and then a = 2 gives ab = 2.
In ∀a ∃b, the b may depend on a. In ∃b ∀a, the same b must work for everything. A familiar pair:
- ∀x ∃y (y > x): every number has a larger number. True over the integers.
- ∃y ∀x (y > x): some number is larger than every number. False over the integers.
Reading nested quantifiers left to right, as a game, helps. For ∀x ∃y, an opponent picks x first and you then choose y in response; the statement is true if you can always respond. For ∃y ∀x, you must commit to y first, and the opponent then picks x to defeat it.
Bound and free variables
In ∀x P(x, y), the x is bound by the quantifier and y is free. A formula with a free variable is still a predicate, not a statement: its truth depends on y. Before claiming a quantified formula is true or false, check that every variable is bound or has been given a value.
How quantifiers are used in proofs
The two quantifiers call for different proof strategies.
- To prove ∀x P(x), take an arbitrary x from the domain and show P(x) using only what is true of every element. A direct proof usually starts "Let n be any integer."
- To prove ∃x P(x), exhibit one x that works and check it.
- To disprove ∀x P(x), one counterexample is enough.
- To disprove ∃x P(x), you must show every x fails, which is a universal claim.
The last two points come from how quantified statements are negated, which is the subject of negating quantified statements. The quantifier rules of inference, such as universal instantiation, are in the rules of inference guide.
True or false over the integers?
Over the integers, decide which are true: ∀x ∃y (x + y = 0); ∃y ∀x (x + y = x); ∃x ∀y (xy = y); ∀x ∃y (y = x²); ∃x ∀y (y = x²). (Answers: true, take y = −x; true, y = 0; true, x = 1; true; false.)
Discrete Math: Study & Quiz has a unit on quantifiers and rules of inference, with lessons and knowledge checks, and a quantifier-negation tool. Our education apps include it alongside reasoning games, and the discrete math topic page collects the rest of the logic guides.
Good to know
Frequently asked questions
What is a predicate in discrete math?
What is the difference between ∀ and ∃?
Does the order of quantifiers matter?
Why does 'all students passed' use an arrow but 'some student passed' use 'and'?
Sources
- Quantifiers (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Mathematical Statements: Predicates and Quantifiers (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- 2.1 Statements and Quantifiers (Contemporary Mathematics) (opens in a new tab)OpenStax — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.