¶ Predicates
A proposition whose truth depeonds on the value of one or more variables (called a free variable). "n is a perfect square" is a predicate, since you don't know its true or false until a value for n is provided.
Like other propositions, a predicate is often named with a letter. Furthermore, a function-like notation is used to denote a predicate supplied with specific variable vlaues. For example...
would be true and is false.
¶ Predicates and Quantifiers
We can assert that a predicate is sometimes true(existential qualification) or always true (universal quantificiation).
The following asserts that there is a number less than 0.
The following asserts that every number is greater than or equal to 0.
The following asserts that a predicate is true for all values of in some set
The whole thing is read as, "for all in , is true".
To say that a predicate is true for at least one value of in one writes:
This expression would be read as, "There exists an in such that is true.
¶ Binding Variables
When a quantifier is used on the variable , we say this occurence of the variable is bound. An occurence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free.
In the statement , is bound and is free.
¶ Note differences between order
- True iff there is a that makes true for every .
- is a constant independent of .
- True iff for every value of there is a value of for which is true.
- It is possible that can depend on
¶ Mixing Quantifiers
Many mathematical statements involve several quantifiers. Goldbach's Conjecture states:
Rewritten to make the use of quantification clearer:
Let Ev be the set of even integers greater than 2, and let Primes be the set of primes. Then we can write Goldbach’s Conjecture in logic notation as follows:
¶ Reordering Quantifiers
Swapping quantifiers in Goldbach's Conjecture creates a false statement that every even number is the sum of the same two primes:
¶ Variables Over One Domain
When all the variables in a formula are understood to take values from the same nonempty set it's conventional to omit mention of .
For example instead of we would write . The unnamed empty set that x and y range over is called the domain.
Goldbach's Conjecture could be expressed with all variables ranging over the domain as
¶ Negating Quantifiers
Quantified predicates are themselves propositions and can be combined with logical connectives just like any other proposition.
is equivalent to
is equivalent to
(Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type).
These two sentences mean the same thing:
We can express the equivalence in logic notation in this way:
¶ Negating Nested Quantifiers
Nested quantifiers are negated by successively applying the rules for negating statements involving a single quantifier.
For example to negate and to move the negation inside all of the quantifiers we repeatedly apply De Morgan's law for quantifiers.
- (De Morgan's Law)
- (De Morgan's Law)
- (Simplify)
¶ Validity for Predicate Formulas
For a predicate formula to be valid, a formula must evaluate to true no matter what the domain of discourse may be, no matter what values its variables may take over the domain, and no matter what interpretations its predicate variables may be given.
¶ Example and Proof
A useful example of a valid assertion:
Lefthand side reads: There is an for which is true for every
Righthand side reads For every , there is a for which is true.
There is an for which is true for every IMPLIES For every , there is a for which is true.
Proof: Let be the domain for the variables and be some binary predicate on . We need to show that if holds under this interpretation, then so does .
Suppose . Some element has the property that is true for all . So for every , there is some , namely , such that is true. That is, holds under this interpretation.
¶ Nested Quantifiers
Note that everything within the scope of a quantifier can be thought of as a propositional function. For example,
is the same thing as where is , where is .
¶ Understanding Statements Involving Nested Quantifiers
says that for all real numbers and . This is the commutative law of addition for real numbers.
says that for every real number there is a real number such that . This states that every real number has an additive inverse.
is the associative law for addition of real numbers.
The statement “The sum of two positive integers is always positive” can be turned into the following logical expression
where the domain for both variables consists of all integers.
¶ Thinking of Quantification as Loops
This is a helpful way of thinking about nested quantifiers. For example, to see whether is true, we loop through the values for , and for each we loop through the values for . If we find that is true for all values for and , we have determined that is true. If we ever hit a value for which we hit a value which makes false, we have shown is false.
A similar procedure is done for , although this time we don't have to loop through all ... just until we find one that satisfies the proposition.