Predicates, Quantifiers and Nested Quantifiers Flashcards
proposition-valued function
a function that assigns to each real number π₯ a proposition π (π₯)
Proposition-valued functions are also known as predicates
just like predicates in grammar, they convey an idea about, or express the action of, a subject
The domain (set of input values) of a predicate is also known as
the domain of discourse or universe of discourse
quantification
A quantification of a predicate is the proposition that π(π₯) is true for some or all input values

βπ₯βπ¦π (π₯,π¦)
(translation)

βπ₯βπ¦π (π₯,π¦)
There exists x such that for all y, x loves y.
There is someone who loves everyone.
βπ₯βπ¦π (π₯,π¦)
There exist x and y such that x loves y.
Love between people exists.
βπ₯βπ¦π (π₯,π¦)
For all x and y, x loves y.
Everyone loves everyone.
βπ₯βπ¦π (π₯,π¦)
For all x, there is y such that x loves y.
There is always someone who loves you*.
*βyouβ is used in the generic sense here, to express a general rule that holds for every person.
Love is always reciprocal:
βπ₯βπ¦(π (π₯,π¦) βπ (π¦,π₯) )
Joe loves only one person:
βπ₯ (π (Joe,π₯) β§βπ¦ (π (Joe,π¦) βπ¦=π₯))
Ishaan loves exactly two people:
βπ₯βπ¦ (π (Ishaan,π₯) β§π (Ishaan,π¦) β§βπ§(π (Ishaan,π§) βπ§=π₯β¨π§=π¦))
People who donβt love themselves donβt love anyone else either:
βπ₯(Β¬π (π₯,π₯) β βπ¦Β¬π (π₯,π¦) )
The unique existential quantifier
signifies the existence of exactly one object of a type. This quantifier is written asβ! or β1.
β1π₯π (π₯) =βπ₯(π (π₯) β§βπ¦ (π (π¦) βπ¦=π₯))
Universal quantification with a domain restriction
The proposition Every positive real number has a real square root can be expressed as
βπ₯ > 0βπ¦ (π¦^2 = π₯)
but also as
βπ₯βπ¦( π₯ > 0 β π¦^2 = π₯)
a domain-restricted universal quantification of a predicate is logically equivalent to the unrestricted universal quantification of aconditional in which the domain restriction is the premise, and the predicate is the conclusion.
All Swedish people are tall is logically equivalent to saying It is true for all people that if they are Swedish, then they are tall.
Existential quantification with a domain restriction
The proposition There is a positive real number whose square is 2 can be expressed as
βπ₯ > 0 (π₯^2 = 2)
but also as
βπ₯ (π₯ > 0 β§ π₯^2 = 2)
a domain-restricted existential quantification of a predicate is logically equivalent to the unrestricted existential quantification of the conjunction of the domain restriction and the predicate.
There is a Chinese dog that is blue is logically equivalent to saying There is a dog that is Chinese and blue.
Domain Restricted Quantification in the Notation of Sets
Let us assume that π is a subdomain of a given domain of discourse π·, and that π is a predicate defined on π·. Then the following equivalences hold:
βπ₯βπ ( π (π₯)) β‘βπ₯ (π₯βπβπ (π₯))
βπ₯βπ ( π(π₯)) β‘βπ₯ ( π₯βπβ§π(π₯))
(We could write βπ₯ β π· or βπ₯ β π· on the right side, but that is unnecessary since the default domain is the full domain of discourse π·.)
Bound vs. Free Variables
A bound variable is a variable that is subject to a quantifier. A variable that is not bound is called free.
In the expression βπ₯π(π₯, π¦), π₯ is bound, π¦ is free. Due to the free variable, βπ₯π ( π₯, π¦ ) is not a proposition, but a propositional function of π¦. A proposition can only contain bound variables, no free variables.
Precedence of Quantifiers and Scope
The quantifiers enjoy a higher precedence than all logical operators. Therefore, if we wish to say that for all π₯, both π(π₯) and π(π₯) are true, we must use parentheses:
βπ₯ ( π (π₯) β§ π (π₯))
The expression without parentheses, βπ₯π (π₯) β§ π (π₯)
means (βπ₯π (π₯) ) β§ π (π₯) , which is not even a proposition, but a propositional function of π₯, because the π₯ in π π₯ is free, and not the same π₯ as the one in βπ₯π( π₯ ).
Logical Equivalence of Statements involving Predicates
When we state the logical equivalence of two statements involving predicates, we mean that the two sides are logically equivalent regardless of the predicates and their domain.
This means that in order to show logical non- equivalence, it is sufficient to come up with (a) specific predicate(s) for which the two statements in question do not share the same truth value.
De Morganβs laws for quantifiers
Β¬βπ₯π(π₯) β‘ βπ₯Β¬π(π₯)
Β¬βπ₯π(π₯) β‘βπ₯Β¬π(π₯)
βπ₯(π (π₯) β§π(π₯)) β‘
βπ₯π(π₯) β§βπ₯π(π₯)
βπ₯(π(π₯) β§π(π₯)) β‘ΜΈ
βπ₯π(π₯) β§βπ₯π(π₯)
βπ₯ππ₯ β¨ππ₯ β‘
βπ₯π(π₯) β¨βπ₯π(π₯)