Question

Let U be the set of real numbers. Determine the truth value of the following propositions.
(a) (∀x)(∀y)(x2 + y ≥ 0).
(b) (∃x)(∀y)(x2 + y ≥ 0)
(c) (∃x)(∀y)(x2 + y2 = 1)
(d) (∃x)(∀y)(x ≤ y2)
(e) (∀x)(∃y)(x · y = 1)
(f) (∃x)(x2) = 2
(g) (∀x)(∃y)(x2 = y)
(h) (∃x)(∀y)(xy = 0)
(i) (∃x)(∃y)(x + y 6= y + x)
(j) (∃x)(∃y)[(x + 2y = 2) ∨ (4y + 2x = 5)]
(k) (∃x)(∃y)[(x + y = 2) ∧ (−y + 2x = 1)]

Answer 1

Answer:

Problem 1.5.28. Determine the truth value of each of these statements if the domain of each variable consists

of all real numbers:

(1) ∀x∃y(x

2 = y): This is true; the rule y = x

2 determines a function, and hence the quantity y exists for any

x.

(2) ∀x∃y(x = y

2

): This is not true; when x = −1, there is no y with y

2 = x = −1.

(3) ∃x∀y(xy = 0): This is true; x = 0 is a witness, as it has the absorptive property xy = 0 · y = 0.

(4) ∃x∃y(x + y 6= y + x): This is false; addition of real numbers is commutative.

(5) ∀x(x 6= 0 → ∃y(xy = 1)): This is true; for any nonzero x, the assignment y = 1/x has the property

xy = x ·(1/x) = 1.

(6) ∃x∀y(y 6= 0 → xy = 1): This is false. If it were true, then there would be an x for which the proposition is

true for y = 2 and 3 simultaneously, i.e., 2x = 1 and 3x = 1. Taking the difference of these two equations,

we find

x = 3x − 2x = 1 − 1 = 0,

but x · y = 0 · y = 0 for any y, making our premise absurd.

(7) ∀x∃y(x + y = 1): This is true; set y = 1 − x.

(8) ∃x∃y(x +2y = 2∧2x +4y = 5): This is false. Divide the second equation by 2 to get the equivalent equation

x + 2y = 5/2. The line it determines is of the same slope as the first equation, but they have distinct y-

intercepts, which means that they are parallel and hence never intersect. So, they cannot have a common

solution (x, y).

(9) ∀x∃y(x + y = 2∧2x − y = 1): This is true. Solving the linear system yields the witness (x, y) = (1, 1).

(10) ∀x∀y∃z(z = (x + y)/2): This is true; the rule z = (x + y)/2 determines a function, and hence the quantity

z exists for any x and y.

1.2. Problem 1.5.30. Rewrite each of these statements so that negations appear only within predicates.

(1) ¬∃y∃xP(x, y):

¬∃y∃xP(x, y) ≡ ∀y¬∃xP(x, y)

≡ ∀y∃y¬P(x, y).

(2) ¬∀x∃yP(x, y):

¬∀x∃yP(x, y) ≡ ∃x¬∃yP(x, y)

≡ ∃x∀y¬P(x, y).

(3) ¬∃y(Q(y)∧ ∀x¬R(x, y)):