Mathematics for Computer Science

Chapter 4 Mathematical Data Types96

Problems for Section 4.1

Practice Problems

Problem 4.1.
For any setA, let pow.A/be itspower set, the set of all its subsets; note thatAis
itself a member of pow.A/. Let;denote the empty set.

(a)The elements of pow.f1;2g/are:

(b)The elements of pow.f;;f;gg/are:

(c)How many elements are there in pow.f1;2;:::;8g/?

Problem 4.2.
Express each of the following assertions about sets by a formula of set theory.^7

(a)xD;.

(b)xDfy;zg.

(c)xy. (xis a subset ofythat might equaly.)
Now we can explain how to express “xis a proper subset ofy” as a set theory
formula using things we already know how to express. Namely, letting “x¤y”
abbreviateNOT.xDy/, the expression

.xy AND x¤y/;

describes a formula of set theory that meansxy.
From here on, feel free to use any previously expressed property in describing
formulas for the following:

(d)xDy[z.

(e)xDyz.

(f)xDpow.y/.

(g)xD

S

z 2 yz.
This means thatyis supposed to be a collection of sets, andxis the union of all of
them. A more concise notation for “

S

z 2 yz’ is simply “

S

y.”

(^7) See Section 7.3.2.