Solutions for HW3

1) Let X,Y be two sets and P(X), P(Y) be their power sets respectively.

a) I will show that ÈP(X) = X.

Since elements of P(X) are subsets of X, ÈP(X) is a subset of X. Conversely, since X is an element of P(X), X is a subset of ÈP(X).

b) I will show that P(XÇY) = P(X)ÇP(Y).

Let AÎ P(XÇY). Then AÍ X and XÍY. Thus AÎP(X)ÇP(Y).

Let AÎP(X)ÇP(Y). Then AÍ X and XÍY. Thus AÍ XÇY. Hence AÎ P(X)ÇP(Y).

c) I will show that P(X)ÈP(Y)Í P(XÈY).

Let AÎ P(X)ÈP(Y). If AÎP(X), then AÍXÈY. Thus AÎP(XÈY). The other case follows similarly.

The equality does not hold in general (try find conditions for equality). Take X={1} and Y={2}. Then {1,2}ÎP(XÈY) but {1,2}ÏP(X)ÈP(Y).

d) In general (try find conditions for equality) we cannot compare them. Just check some examples.

2)

a) For any xÎX, (x,x)ÎS iff (x,x)ÎR. Since R is reflexive, S is reflexive too. Assume (x,y)ÎS for some x,yÎX. Then (x,y)ÎR and (y,x)ÎR. This also means that (y,x)ÎS. Thus S is symmetric. Transitivity follows easily.

b) For any xÎX, (x,x)ÎT iff (x,x)ÎR. Thus T is reflexive. T is symmetric too. But T is not necessarily transitive. Take R reflexive and transitive and such that there are x,y,z ÎX such that (x,y)ÎR, (z,y)ÎR and (x,z)ÏR, (z,x)ÏR. Then by definition, (x,y)ÎT, (y,z)ÎT but (x,z)ÏT. (Check it!)

3)

a) R is not reflexive because ÆÎP(X) and ÆÇÆ = Æ.

b) Assume aRb for some a,b ÎP(X). Then we have aÇb ¹Æ. This also means bRa since aÇb=bÇa.

c) R is not transitive. Take X={1,2}. Then {1}R{1,2} and {1,2}R{2} but it is not true that {1}R{2}.