Page 146 - Discrete Mathematics and Its Applications

2.1 Sets 125

Truth Sets and Quantifiers

We will now tie together concepts from set theory and from predicate logic. Given a predicate
P , and a domain D, we define the truth set of P to be the set of elements x in D for which
P(x) is true. The truth set of P(x) is denoted by {x ∈ D | P(x)}.
EXAMPLE 23 What are the truth sets of the predicates P(x), Q(x), and R(x), where the domain is the set of
2
integers and P(x) is “|x|= 1,” Q(x) is “x = 2,” and R(x) is “|x|= x.”
Solution: The truth set of P , {x ∈ Z ||x|= 1}, is the set of integers for which |x|= 1. Because
|x|= 1 when x = 1or x =−1, and for no other integers x, we see that the truth set of P is the
set {−1, 1}.
2
2
The truth set of Q, {x ∈ Z | x = 2}, is the set of integers for which x = 2. This is the
2
empty set because there are no integers x for which x = 2.
The truth set of R, {x ∈ Z ||x|= x}, is the set of integers for which |x|= x. Because
|x|= x if and only if x ≥ 0, it follows that the truth set of R is N, the set of nonnegative
integers. ▲
Note that ∀xP (x) is true over the domain U if and only if the truth set of P is the set U.
Likewise, ∃xP (x) is true over the domain U if and only if the truth set of P is nonempty.

Exercises

1. List the members of these sets. a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1}
2
a) {x | x is a real number such that x = 1} b) {{1}}, {1, {1}} c) ∅, {∅}
6. Suppose that A ={2, 4, 6}, B ={2, 6}, C ={4, 6}, and
b) {x | x is a positive integer less than 12}
D ={4, 6, 8}. Determine which of these sets are subsets
c) {x | x is the square of an integer and x< 100}
of which other of these sets.
2
d) {x | x is an integer such that x = 2}
7. For each of the following sets, determine whether 2 is an
2. Use set builder notation to give a description of each of element of that set.
these sets.
a) {x ∈ R | x is an integer greater than 1}
a) {0, 3, 6, 9, 12}
b) {x ∈ R | x is the square of an integer}
b) {−3, −2, −1, 0, 1, 2, 3}
c) {2,{2}} d) {{2},{{2}}}
c) {m, n, o, p} e) {{2},{2,{2}}} f) {{{2}}}
3. For each of these pairs of sets, determine whether the first 8. For each of the sets in Exercise 7, determine whether {2}
is a subset of the second, the second is a subset of the first, is an element of that set.
or neither is a subset of the other. 9. Determine whether each of these statements is true or
a) the set of airline flights from NewYork to New Delhi, false.
the set of nonstop airline flights from New York to
a) 0 ∈∅ b) ∅∈{0}
New Delhi
c) {0}⊂⊆ d) ∅⊂{0}
b) the set of people who speak English, the set of people e) {0}∈{0} f) {0}⊂{0}
who speak Chinese g) {∅} ⊆ {∅}
c) the set of flying squirrels, the set of living creatures 10. Determine whether these statements are true or false.
that can fly
a) ∅ ∈ {∅} b) ∅∈{∅, {∅}}
4. For each of these pairs of sets, determine whether the first c) {∅} ∈ {∅} d) {∅} ∈ {{∅}}
is a subset of the second, the second is a subset of the first, e) {∅}⊂{∅, {∅}} f) {{∅}} ⊂ {∅, {∅}}
or neither is a subset of the other. g) {{∅}} ⊂ {{∅}, {∅}}
a) the set of people who speak English, the set of people 11. Determine whether each of these statements is true or
who speak English with an Australian accent false.
b) the set of fruits, the set of citrus fruits a) x ∈{x} b) {x}⊆{x} c) {x}∈{x}
c) the set of students studying discrete mathematics, the d) {x}∈{{x}} e) ∅⊆{x} f) ∅∈{x}
set of students studying data structures 12. Use aVenn diagram to illustrate the subset of odd integers
5. Determine whether each of these pairs of sets are equal. in the set of all positive integers not exceeding 10.