4.1. Sets 69
For example, when the domain we’re working with is the real numbers, the com-
plement of the positive real numbers is the set of negative real numbers together
with zero. That is,
RCDR [f 0 g:
It can be helpful to rephrase properties of sets using complements. For example,
two sets,AandB, are said to bedisjointiff they have no elements in common, that
is,A\BD;. This is the same as saying thatAis a subset of the complement of
B, that is,AB.
4.1.4 Power Set
The set of all the subsets of a set,A, is called thepower set,P.A/, ofA. So
B 2 P.A/iffBA. For example, the elements ofP.f1;2g/are;;f 1 g;f 2 gand
f1;2g.
More generally, ifAhasnelements, then there are 2 nsets inP.A/. For this
reason, some authors use the notation 2 Ainstead ofP.A/.
4.1.5 Set Builder Notation
An important use of predicates is inset builder notation. We’ll often want to talk
about sets that cannot be described very well by listing the elements explicitly or
by taking unions, intersections, etc., of easily-described sets. Set builder notation
often comes to the rescue. The idea is to define asetusing apredicate; in particular,
the set consists of all values that make the predicate true. Here are some examples
of set builder notation:
AWWDfn 2 Njnis a prime andnD4kC 1 for some integerkg
BWWDfx 2 Rjx^3 3xC1 > 0g
CWWDfaCbi 2 Cja^2 C2b^2 1 g
The setAconsists of all nonnegative integersnfor which the predicate
“nis a prime andnD4kC 1 for some integerk”is true. Thus, the smallest elements ofAare:
5;13;17;29;37;41;53;57;61;73;::::Trying to indicate the setAby listing these first few elements wouldn’t work very
well; even after ten terms, the pattern is not obvious! Similarly, the setBconsists
of all real numbersxfor which the predicate
x^3 3xC1 > 0