Predicates, Quantifiers and Nested Quantifiers

Question 1

proposition-valued function

Answer 1

a function that assigns to each real number 𝑥 a proposition 𝑃 (𝑥)

Question 2

Proposition-valued functions are also known as predicates

Answer 2

just like predicates in grammar, they convey an idea about, or express the action of, a subject

Question 3

The domain (set of input values) of a predicate is also known as

Answer 3

the domain of discourse or universe of discourse

Question 4

quantification

Answer 4

A quantification of a predicate is the proposition that 𝑃(𝑥) is true for some or all input values

Question 5

∀𝑥∃𝑦𝑃 (𝑥,𝑦)

(translation)

Answer 5

Question 6

∃𝑥∀𝑦𝑃 (𝑥,𝑦)

Answer 6

There exists x such that for all y, x loves y.

There is someone who loves everyone.

Question 7

∃𝑥∃𝑦𝑃 (𝑥,𝑦)

Answer 7

There exist x and y such that x loves y.

Love between people exists.

Question 8

∀𝑥∀𝑦𝑃 (𝑥,𝑦)

Answer 8

For all x and y, x loves y.

Everyone loves everyone.

Question 9

∀𝑥∃𝑦𝑃 (𝑥,𝑦)

Answer 9

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.

Question 10

Love is always reciprocal:

Answer 10

∀𝑥∀𝑦(𝑃 (𝑥,𝑦) →𝑃 (𝑦,𝑥) )

Question 11

Joe loves only one person:

Answer 11

∃𝑥 (𝑃 (Joe,𝑥) ∧∀𝑦 (𝑃 (Joe,𝑦) →𝑦=𝑥))

Question 12

Ishaan loves exactly two people:

Answer 12

∃𝑥∃𝑦 (𝑃 (Ishaan,𝑥) ∧𝑃 (Ishaan,𝑦) ∧∀𝑧(𝑃 (Ishaan,𝑧) →𝑧=𝑥∨𝑧=𝑦))

Question 13

People who don’t love themselves don’t love anyone else either:

Answer 13

∀𝑥(¬𝑃 (𝑥,𝑥) → ∀𝑦¬𝑃 (𝑥,𝑦) )

Question 14

The unique existential quantifier

Answer 14

signifies the existence of exactly one object of a type. This quantifier is written as∃! or ∃1.

∃1𝑥𝑃 (𝑥) =∃𝑥(𝑃 (𝑥) ∧∀𝑦 (𝑃 (𝑦) →𝑦=𝑥))

Question 15

Universal quantification with a domain restriction

Answer 15

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.

Question 16

Existential quantification with a domain restriction

Answer 16

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.

Question 17

Domain Restricted Quantification in the Notation of Sets

Answer 17

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 𝐷.)

Question 18

Bound vs. Free Variables

Answer 18

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.

Question 19

Precedence of Quantifiers and Scope

Answer 19

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 ∀𝑥𝑃( 𝑥 ).

Question 20

Logical Equivalence of Statements involving Predicates

Answer 20

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.

Question 21

De Morgan’s laws for quantifiers

Answer 21

¬∀𝑥𝑃(𝑥) ≡ ∃𝑥¬𝑃(𝑥)

¬∃𝑥𝑃(𝑥) ≡∀𝑥¬𝑃(𝑥)

Question 22

∀𝑥(𝑃 (𝑥) ∧𝑄(𝑥)) ≡

Answer 22

∀𝑥𝑃(𝑥) ∧∀𝑥𝑄(𝑥)

Question 23

∃𝑥(𝑃(𝑥) ∧𝑄(𝑥)) ≢

Answer 23

∃𝑥𝑃(𝑥) ∧∃𝑥𝑄(𝑥)

Question 24

∃𝑥𝑃𝑥 ∨𝑄𝑥 ≡

Answer 24

∃𝑥𝑃(𝑥) ∨∃𝑥𝑄(𝑥)

Question 25

∀𝑥𝑃𝑥 ∨𝑄𝑥 ≢

Answer 25

∀𝑥𝑃(𝑥) ∨∀𝑥𝑄(𝑥)

Question 26

Determining the truth value of nested quantified mathematical statements

∀𝑥∃𝑦 ( 𝑥𝑦 = 1 )

Answer 26

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.

Question 27

∀𝑥∃𝑦 ( 𝑥 + 𝑦 = 1 )

Answer 27

This statement is true. For any 𝑥 that the challenger gives us, we can select a 𝑦 to make the equation 𝑥 + 𝑦 = 1 true, namely 𝑦 = 1 − 𝑥.

Question 28

∃𝑦∀𝑥 ( 𝑥+𝑦=1 )

Answer 28

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.

Question 29

∀𝑥∃𝑦 ((𝑥𝑦=1)→(𝑥𝑦=2))

Answer 29

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?

Question 30

∀𝑥∃𝑦∀𝑧∃𝑤 ( 𝑥𝑦 ≥ 𝑧𝑤 )

Answer 30

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.