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
Β¬βπ₯π(π₯) β‘ βπ₯Β¬π(π₯)
Β¬βπ₯π(π₯) β‘βπ₯Β¬π(π₯)
βπ₯(π (π₯) β§π(π₯)) β‘
βπ₯π(π₯) β§βπ₯π(π₯)
βπ₯(π(π₯) β§π(π₯)) β‘ΜΈ
βπ₯π(π₯) β§βπ₯π(π₯)
βπ₯ππ₯ β¨ππ₯ β‘
βπ₯π(π₯) β¨βπ₯π(π₯)
βπ₯ππ₯ β¨ππ₯ β‘ΜΈ
βπ₯π(π₯) β¨βπ₯π(π₯)
Determining the truth value of nested quantified mathematical statements
βπ₯βπ¦ ( π₯π¦ = 1 )
This statement is false. To see that, it is helpful to think of the statement as achallenge-response game: someone else gives you the number x. You have no control over x. Your job is to respond to the x by finding a y that makes the equation π₯π¦ = 1 true. If you can always win this game by doing that, then the statement above is true. If not, then the statement is false.
βπ₯βπ¦ ( π₯ + π¦ = 1 )
This statement is true. For any π₯ that the challenger gives us, we can select a π¦ to make the equation π₯ + π¦ = 1 true, namely π¦ = 1 β π₯.
βπ¦βπ₯ ( π₯+π¦=1 )
This statement is false. This challenge-response game may seem like the same game as that in the previous example, but there is a crucial difference. Rather than being allowed to pick the π¦ in response to your opponentβs π₯, now you have to pick your π¦ first, and commit to it. Then, your opponent is free to choose any π₯ she wants, and for all π₯ except one, the equation π₯ + π¦ = 1 is false.
βπ₯βπ¦ ((π₯π¦=1)β(π₯π¦=2))
This statement is true. This may seem absurd- surely, if π₯π¦ is 1, it canβt also be 2?
To understand why the statement is true, we must go beyond a merely intuitive understanding of the conditional and apply the exact formal definition of the conditional. Recall that if the premise of a conditional is false, the conditional is true by default. The question we should be askingourselves therefore is, can we always respond to the challenge βxβ with a βyβthat makes the premise of the conditional false?
βπ₯βπ¦βπ§βπ€ ( π₯π¦ β₯ π§π€ )
This is like a challenge-response game in 4 rounds. First, your opponent gives you the π₯. Then, you select the π¦.Then, your opponent gives you the π§, and finally, you get to pick the π€. Can you always prevail in this game and force the inequality π₯π¦ β₯ π§π€ to be true?
The answer is yes. The following is a winning strategy: Given π₯, select π¦ = 0. Then, for the given π§, select π€ = 0. This makes π₯π¦ β₯ π§π€ true because both sides are zero.