Thursday, May 27, 2010

how to prove it - ch4, sec4.1(Ordered Pairs and Cartisian Product)

As the title suggests, this section is about orderderd pairs(pairs where ordering is important) and cartisian product of sets.

Cartisian product of two sets A and B is defined as
A X B = {(a,b) | a A and b B}
where (a,b) is the ordered pair. Often a is called the first and b is called the second coordinate of the ordered pair.

One important property we might want to notice is that
A X = X A =

Now, for any statement P(x,y), where x and y are free variables and x ranges over a set A and y ranges over a set B. Then
Truth set(T) of P(x,y) would be defined as {(a,b) | P(a,b)}

clearly if some (a,b) T, then P(a,b)

=================================================================================

Ex-1(a) {(x,y) | x is a parent of y}

Ex-1(b) {(x,y) | someone lives in x and attends y}

Ex-2(a) {(x,y) | x lives in y} for example {(himanshu,bangalore), ...}

Ex-2(b) {(x,y) | population of x is y} for example
{(bangalore, 1 mn), ...}

Ex-3(a) {(x,y) | y = x2-x-2} for example {(0,-2), (1,-2),...}

Ex-3(b) {(x,y) | y < x} for example {(1,0), (2,1), (2,0), ...}

Ex-3(c) {(x,y) | either y = x2-x-2 or y = 3x-2 } for example {(0,-2), (1,1), ...}

Ex-3(d) {(x,y) | y < x and either y = x2-x-2 or y = 3x-2 }


Ex-4
1. AX(BC)
= {1,2,3} X {4}
= {(1,4), (2,4), (3,4)}

(A X B) (A X C)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} {(1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}
= {(1,4), (2,4), (3,4)}

2. AX(BC)
= {1,2,3} X {1,3,4}
= {(1,1), (2,1), (3,1), (1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}

(A X B) (A X C)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} {(1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}
= {(1,1), (2,1), (3,1), (1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}

3. (A X B) (C X D)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} {(3,5), (4,5)}
=

(AC)X(BD)
= {3} X
=

4. (A X B) (C X D)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} {(3,5), (4,5)}
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4), (3,5), (4,5)}

(AC)X(BD)
= {1,2,3,4} X {1,4,5}
= {(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4), (1,5), (2,5), (3,5), (4,5)}

5. A X = X A =


Ex-5
-- Prove AX(BC) = (A X B) (A X C). --

Let p be arbitrary element of AX(BC). It follows that there exist x and y s.t. p = (x,y) and xA and yBC. Since yBC, so either yB or yC. Let us consider both the cases.

Case#1: yB
Then (x,y)AXB. Thus (x,y)(AXB)(AXC)

Case#2: yC
Then (x,y)AXC. Thus (x,y)(AXB)(AXC)

Since p is arbitrary, we can conclude that AX(BC)(AXB)(AXC)

Now, Let p be arbitrary element of (AXB)(AXC). Then either p(AXB) or p(AXC). Let us consider both the cases

Case#1: p(AXB)
There exist xA and yB s.t. p = (x,y). clearly y(BC) also, so (x,y)AX(BC)

Case#2: p(AXC)
By similar argument as above, (x,y)AX(BC)

Since p is arbitrary, we can conclude that (AXB)(AXC)AX(BC)

Thus AX(BC) = (A X B) (A X C)

-- Prove that (AXB)(CXD)=(AC)X(BD) --

Let p be an arbitrary element of (AXB)(CXD). Then p(AXB) and p(CXD). So there exists x and y s.t. p = (x,y) and xA and yB and xC and yD. So x(AC) and y(BD). Hence p(AC)X(BD). Since p is arbitrary, so (AXB)(CXD)(AC)X(BD)

Let p be an arbitrary element of (AC)X(BD). It follows there exist x and y s.t. p = (x,y) and x(AC) and y(BD). So xA and xC and yB and yD. So (x,y)(AXB) and (x,y)(CXD). Thus p(AXB)(CXD). Since p is arbitrary, so (AC)X(BD)(AXB)(CXD)

Hence (AXB)(CXD)=(AC)X(BD)


Ex-6 Flaw is that all the cases are not considered. Here is the list of cases that is left out in the proof.

xA and yD
xC and yB


Ex-7 m * n


Ex-8 It is true. Here is the proof.

Let p be an arbitrary element of (A X B\C). It follows there exist x and y s.t. p = (x,y) and xA and yB\C. So yB and yC. Since xA and yB, so p(AXB). Since yC, so p(AXC). Hence p(AXB)\(AXC). Since p is arbitrary, so (AXB\C)(AXB)\(AXC)

Now let p be an arbitrary element of (AXB)\(AXC). Then p(AXB) and p(AXC). It follows that there exist x and y s.t. p = (x,y). Since p(AXB), so xA and yB. Since p(AXC), so either xA or yC.. but we already saw that xA, so yC. Since xA, yB and yC. So pAX(B\C). Since p is arbitrary, so (AXB)\(AXC)(AXB\C)

Thus (AXB\C)=(AXB)\(AXC)


Ex-9 Let p be an arbitrary element of (AXB)\(CXD). Then p(AXB) and p(CXD). Thus there exist x and y s.t. p = (x,y). Since p(AXB), so xA and yB. Since p(CXD), so either xC or yD. Let us consider both the cases.

Case#1: xC
Since xA and yB and xC, so p(A\C)XB. Thus p[AX(B\D)][(A\C)XB]

Case#2: yD
Since xA and yB and yD, so pAX(B\D). Thus p[AX(B\D)][(A\C)XB]

Since p is arbitrary, (AXB)\(CXD)[AX(B\D)][(A\C)XB]

Again, Let p be an arbitrary element of [AX(B\D)][(A\C)XB]. Then either pAX(B\D) or p(A\C)XB. Let us consider both the cases.

Case#1: pAX(B\D)
Then there exist x and y s.t. p = (x,y) and xA and yB and yD. Since xA and yB, so p(AXB). Also since yD, so p(CXD). Thus p(AXB)\(CXD)

Case#2: p(A\C)XB
we can use similar argument as above case to prove that p(AXB)\(CXD)

Now since p is arbitrary, so [AX(B\D)][(A\C)XB](AXB)\(CXD)

Thus (AXB)\(CXD) = [AX(B\D)][(A\C)XB]


Ex-10 Suppose (A X B) and (C X D) are disjoint. Let (x,y) be an arbitrary ordered pair of (A X B), it follows that (x,y)(CXD). So either xC or yD. Since x,y are arbitrary, Thus either A and C are disjoint or B and D are disjoint.


Ex-11
(a) Let (x,y) be an ordered pair in iI(AiXBi). Then there exists a particular kI s.t. (x,y)AkXBk. It follows that xAk and yBk. Since xAk, so xiIAi. Also since yBk, so yiIBi. So (x,y)iIAiXiIBi. Since x,y is arbitrary, so iI(AiXBi)iIAiXiIBi

(b) Let (x,y) be an arbitrary ordered pair in pPCp. Then there exists a particular ordered pair (l,m) in P s.t. (x,y)C(l,m). Since C(l,m)=AlXBm, So (x,y)AlXBm. Then xAl and yBm. Since xAl, so xiIAi. Also since yBm, so yiIBi. Thus (x,y)iIAiXiIBi. Since (x,y) is arbitrary, so pPCpiIAiXiIBi

Again, Let (x,y) be and arbitrary ordered pair in iIAiXiIBi. Then xiIAi and yiIBi. Since xiIAi, so there exists a particular lI s.t. xAl and similarly there exists a particular mI s.t. yBm. So (x,y)AlXBm. Then (x,y)C(l,m). So (x,y)pPCp. Since (x,y) is arbitrary, so iIAiXiIBipPCp.

Thus pPCp = iIAiXiIBi


Ex-12 The proof and the theorem, both are incorrect. It starts with assuming elements in A and B. It is nowhere given that A and B, both are non-empty set.

No comments:

Post a Comment