Hello! In our last lesson, we built our first formal proofs, often starting with a phrase like "for any integer n...". This was our informal way of making a general claim. Now, it's time to make this language precise.
So far, we've worked in propositional logic, which deals with simple true/false statements. But to handle variables and concepts like "for all" or "for some," we need to step up to predicate logic. This lesson introduces the two core building blocks of predicate logic that allow us to do this. You will learn to distinguish between the universal quantifier (∀), which corresponds to "for all," and the existential quantifier (∃), which corresponds to "there exists." This distinction is the foundation for expressing complex mathematical ideas with clarity and precision.
From Propositions to Predicates
Our logic so far can't handle a simple sentence like "$x > 5$". It isn't a proposition because its truth depends on the value of the variable . This is where predicates come in.
A predicate is a statement containing variables, which becomes a proposition once the variables are assigned specific values. We can write our example as .
- If , then is the true proposition "7 > 5".
- If , then is the false proposition "2 > 5".
The set of possible values a variable can take is called the universe of discourse or domain. This is a crucial concept that gives context to our statements. For instance, the truth of a statement can change dramatically if the domain is all integers versus just positive integers.
3.3Quantifiers and Predicate Logic¶ permalink
This text from "Discrete Mathematics: An Open Introduction" introduces the need for predicate logic and defines what a predicate is.
Read the introductory part of the section to see why propositional logic is not enough. Then, read the subsection on Predicates to formalize this idea. Note the distinction between a formula like E(x) and a statement like E(2).
Quantifiers: Binding Variables into Statements
Substituting a value isn't the only way to turn a predicate into a proposition. We can also use quantifiers to make a claim about how many elements in the domain make the predicate true. There are two fundamental quantifiers.
The Universal Quantifier: ∀ ("For All")
The universal quantifier, denoted by the symbol , expresses the idea that a predicate is true for every single element in the domain. It is often read as "for all," "for every," or "for any."
A statement like is true if and only if is true for every possible value of from the universe of discourse. If you find even one value of (a counterexample) for which is false, then the entire statement is false.
From your computer science background, you can think of the universal quantifier as a massive AND operation across the entire domain.
The Existential Quantifier: ∃ ("There Exists")
The existential quantifier, denoted by the symbol , expresses the idea that a predicate is true for at least one element in the domain. It is often read as "there exists," "there is," or "for some."
A statement like is true if you can find at least one value of in the domain that makes true. It is false only if is false for every single element in the domain.
Analogously, you can think of the existential quantifier as a massive OR operation.
The following image provides a simple, intuitive illustration of this core difference.
The following video from Dr. Trefor Bazett gives a great verbal walkthrough of these two concepts and how they turn a predicate into a full-fledged logical statement.
Universal and Existential Quantifiers, ∀ "For All" and ∃ "There Exists"
This video clearly explains the meaning and notation of both universal and existential quantifiers.
Please watch the first two segments. The first part introduces the universal quantifier (∀). The second part introduces the existential quantifier (∃). Finally, pay close attention to the explanation of how quantifiers turn a predicate into a statement that can be true or false.
To solidify this, let's consider the predicate over the domain of all integers.
- Is true? No. For , . We found a counterexample.
- Is true? Yes. For , . We found an example that makes it true.
Conclusion
In this lesson, we moved beyond simple propositions and into the more expressive world of predicate logic. You learned to distinguish the two fundamental quantifiers that allow us to make precise claims about variables.
Key Takeaways:
- A predicate is a statement with variables, like . It becomes a true/false proposition when the variables are specified or quantified.
- The universal quantifier (∀) means "for all." The statement is true only if holds for every single element in the domain. It's like a giant AND.
- The existential quantifier (∃) means "there exists." The statement is true if holds for at least one element in the domain. It's like a giant OR.
- Applying a quantifier to a predicate's variable(s) "binds" them and transforms the predicate into a complete logical statement with a definite truth value.
In our next lesson, we will build on this foundation and learn how to translate more complex English sentences into predicate logic. This involves combining quantifiers with the logical connectives (AND, OR, NOT, IMPLIES) we've already learned. For instance, we'll see why a statement like "Every fox is faster than some snail" requires a specific combination of quantifiers and connectives to be expressed correctly.
