My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
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 double-inclusion
_ _
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 non-empty sets. If f : A ? B and g : C ? D are two functions, we de?ne a new function h : AC ? BD as follows: ?(a, c) ? AC, 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.
zaff9 is offline  
 
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.
zaff9 is offline  
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 non-empty)

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.
Deveno is offline  
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.
zaff9 is offline  
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 = (B-A)?(A?B) <--B-A, 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, non-overlapping 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 set-membership, and this exercise is trying to make this clear to you.
Deveno is offline  
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)
zaff9 is offline  
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 round-about 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.
Deveno is offline  
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.
skipjack is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

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





Copyright © 2019 My Math Forum. All rights reserved.