
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 25th, 2013, 06:17 AM  #1 
Newbie Joined: Jan 2013 Posts: 26 Thanks: 0  Two questions  Approach?
Let U be a universal set, A and B two subsets of U. (1) Show that B ? A ? (B ? A). _ _ (2) A = B if and only if there exists a subset X of U such that A ? X = B ? X and X\A = X\B. For (1), I did this: B ? A ? (B ? A). _ B ? (A?B)?(A?A) B ? (A?B)?(u) Therefore since A and B are both in the universe, B ? A ? (B ? A) For (2), I did this: Property of doubleinclusion _ _ A ? X = B ? X and X\A = X\B, Show A=B Let X ? A Case 1: X?X X?X > X?AUX > X?BUX >X?B Case 2 X?X > X?X\A > X?X\B > X?X or X?B, but X?X so X?B This one, I don't really know how to approach... If someone could prove it or even just point me in the direction, I'd appreciate it. Let A, B, C and D four nonempty sets. If f : A ? B and g : C ? D are two functions, we de?ne a new function h : A×C ? B×D as follows: ?(a, c) ? A×C, h(a, c) = (f(a), g(c)). Show that h is bijective if and only if f and g are bijective. This is really my first EVER exposure to abstract math, so at this point I'm kind of fumbling in the dark; any pointers would be great. 
January 25th, 2013, 06:19 AM  #2 
Newbie Joined: Jan 2013 Posts: 26 Thanks: 0  Re: Two questions  Approach?
The format I used didn't properly show that for question 1, it's B ? A ? (B ? A). where A with the intersection of B is a COMPLEMENT A A ? X = B ? X and X\A = X\B. Here the A and B in the XA XB difference is also complements. 
January 25th, 2013, 07:22 AM  #3 
Senior Member Joined: Mar 2012 Posts: 294 Thanks: 88  Re: Two questions  Approach?
if you want to show that: B ? A?(B?A^c) you know to show that every element of B is in the set on the right. now B = B?U = B ? (AUA^c) = (B?A) U (B?A^c). if b in B is in B ? A, then it lies in A, so certainly lies in A?(B?A^c). otherwise, b is in B?A^c, so lies in A?(B?A^c). with number 2, you cannot conclude that just because x lies in B?X, it lies in B. this is false. however, since x is assumed to lie in A, it is NOT in X\A. therefore it is NOT in X\B, therefore it IS in B (why? because B?X = X\B U B). this shows that A is a subset of B. now what you need to do is show if y is in B, y must also lie in A. it might help to draw some pictures. even that is only "half" of 2: showing that the existence of X with A?X = B?X, and A\X = B\X implies A = B. now you have a different proof: showing that if A = B, there is some X with that property. will X = U work? ***************************** for your last problem, you need a definition of injective and surjective. the one i will use is: f is injective if f(x) = f(y) implies x = y, and f is surjective if for ANY b in B there is some a in A with f(a) = b. bijective functions are both. one part (as is often the case) of this "iff (if an only if)" proof is fairly simple: suppose f,g are injective, and that h(a,c) = h(a',c'). this means that (f(a),g(c)) = (f(a'),g(c')). by the definition of equality on BxD, this means f(a) = f(a'), and g(c) = g(c'). since BOTH f,g are injective, a = a', and c = c'. therefore (a,c) = (a',c') and we have proved h is injective. now suppose f,g are surjective. then for any (b,d) in BxD, we have b = f(a), d = g(c), for some a in A, and c in C. hence h(a,c) = (f(a),g(c)) = (b,d), so h is surjective. now...the "other direction". suppose all we know is that h is bijective. well this means h is injective and surjective. now suppose f(a) = f(a'). then h(a,c) = (f(a),g(c)) = (f(a'),g(c)) = h(a',c), and since h is injective, (a,c) = (a',c), which means a = a' and c = c. we don't care about c right now, but a = a' shows f is injective. a similar proof works for g. so both f,g are injective if h is. now let b be any element of B. we need to find an a such that f(a) = b to show f is surjective. since h is surjective, for any element of BxD, we have (a,c) in AxC with h(a,c) = (b,d). so pick some random element d of D (we can do this, D is nonempty) and consider (b,d). there exists SOME (a,c) in AxC with h(a,c) = (b,d). so let's use the a of that particular (a,c). since h(a,c) = (f(a),g(c)) = (b,d), we have f(a) = b. again, a similar proof works for g. 
January 25th, 2013, 10:44 AM  #4 
Newbie Joined: Jan 2013 Posts: 26 Thanks: 0  Re: Two questions  Approach?
OK I'm a little confused... for the first question: B ? A?(B?A^c) to B = B?U = B ? (AUA^c) = (B?A) U (B?A^c). Where is the B?U from? Am I just looking at it backwards? AUA^c is just the universe, can't I switch it using that property? Is my method of using associative properties, followed by the AUA^c property to show the universe not sufficient when it shows B and A are both in the universe? Man this stuff is stressing me out lol. 
January 25th, 2013, 10:00 PM  #5 
Senior Member Joined: Mar 2012 Posts: 294 Thanks: 88  Re: Two questions  Approach?
I'm not sure I even understand what you wrote (part of this could be because however you are denoting "complement" isn't showing up). We want to show B is contained in a certain set, which is a union of two other sets. Since A,B are arbitrary, we can easily imagine situations where B is not contained in A, nor in the intersection of B with the complement of A. For example, suppose U = {1,2,3,4,5,6}, A = {1,2,3}, and B = {2,3,4}. then B clearly isn't contained in A. Now A^c = {4,5,6}, and B?A^c = {4}, so B clearly isn't contained in this set, either. So, we want to split up U somehow so that when we take the part of B that is in the first part of U, we have A?B, and when we take the part of B that is in the second part of U, we have A^c?B. this way we split up U should be "clean", exactly 2 pieces with no overlap. U = A?A^c does this for us. this isn't just a union, but a very special kind of union called a DISJOINT union, which is much easier to talk about (x is either in A, or A^c, never both). If you understand this, then I could have just written: B = (A?B)?(A^c?B) without mentioning U <the same disjoint union of U, induces a disjoint union of B. This is just the same as saying: B = (BA)?(A?B) <BA, or B\A is another way of writing (B?A^c). This is important for describing the "interaction" of A and B, A partitions B into two, nonoverlapping sets: B\A and A?B. This is implicitly appealing to the logical: Law of the Excluded Middle  either x in B is in A as well, or it's not, there are no other choices. This is a basic principle of setmembership, and this exercise is trying to make this clear to you. 
January 26th, 2013, 01:16 PM  #6 
Newbie Joined: Jan 2013 Posts: 26 Thanks: 0  Re: Two questions  Approach?
OK. I took what you said, and this is what I've developed: So B?A?(B?A^c) To show this, we can say that when x?B, implies there exists an x?A?(B?A^c) We will let x?B, Case 1: x? A x? A>x? A and x?(B?A^c). So clearly, x?A. Case 2: x?A x?A or x?(B?A^c). We have declared x?A, so x?B and x?A^c. Now we note that X?A^c is = to X?A. Thus proving that B?A?(B?A^c) 
January 26th, 2013, 09:55 PM  #7 
Senior Member Joined: Mar 2012 Posts: 294 Thanks: 88  Re: Two questions  Approach?
So very close. When you say: "....that when x is in B, there exists an x in x?A?(B?A^c)...." it should not be: "there exists", that is too general. it must be the very same x we are supposing we have in B. That is: to say X?Y is equivalent to saying: (x is in X) implies (x is in Y). Case 1) is wrong. If x is in A, x is NOT in A^c, and it is certainly not in B?A^c. you need to change the "and" to "or", that is the meaning of "union". Like this: suppose x is in B. If x is in A, then x is in A?(B?A^c). That's all you need to write. Case 2) is much better, but I would START with: Case 2: x?A we note that X?A^c is = to X?A. Hence x is in B?A^c, and thus in A?(B?A^c). ********************************** In general, for any two sets A and B: A?B ? A ? A?B A?B ? B ? A?B If you want to show something (say an element x) is in A?B, you can do this one of two ways: 1) show it is in A, or it is in B (but at least one; doesn't have to be both). 2) assume it is not in A, and show it must lie in B (this is really the same thing....if it's in A, then it surely lies in A?B by dint of the inclusions listed above. So if it's not in A, it had better be in B  this is a roundabout way of saying: A?B = [(A^c)?(B^c)]^c). If you want to show something is in A?B, there is really only one way: 1) show it is in A, and it lies in B. Both must be true. 
September 20th, 2013, 11:50 PM  #8 
Global Moderator Joined: Dec 2006 Posts: 20,820 Thanks: 2159 
1. A?(B?A^c) = (A?B)?(A?A^c) (distributive law) = (A?B)?(U) = A?B (as A and B are subsets of U) ? B. 

Tags 
approach, questions 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Hessian approach  matthius  Calculus  0  February 20th, 2012 07:26 AM 
How to approach this problem  JohnA  Algebra  2  February 19th, 2012 09:29 AM 
Different Geometry Approach  tiba  Math Books  0  February 19th, 2012 07:03 AM 
approach to integration  akle  Calculus  1  July 9th, 2010 10:11 AM 
How do I approach this?  cmmcnamara  Advanced Statistics  4  February 10th, 2010 05:49 AM 