Proving Sets Intersections/Unions


by roam
Tags: proving, sets
roam
roam is offline
#1
Jul23-09, 12:17 AM
P: 884
1. The problem statement, all variables and given/known data

Let A,B,C be sets.

(a) Show that:

[tex]A \cup B = (A\B)\cup(B\A)\cup(A \cap B)[/tex]

(b) Show that:

[tex]A \times (B\C) = (A \times B) \ (A \times C)[/tex]

2. Relevant equations



3. The attempt at a solution

For part (a) I need to prove the definition of a union. I think in order to prove that both sides of [tex]A \cup B = (A\B)\cup(B\A)\cup(A \cap B)[/tex] are equal each other I must show that:

[tex]A \cup B \subseteq (A\B)\cup(B\A)\cup(A \cap B)[/tex] and

[tex]A \cup B \supseteq (A\B)\cup(B\A)\cup(A \cap B)[/tex]

I'm stuck here and don't know how to prove that the two are subsets of one another. Can anyone help me please?
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
Office_Shredder
Office_Shredder is offline
#2
Jul23-09, 12:32 AM
Mentor
P: 4,499
I checked your latex and it looks like some of it didn't come out (you had some A\B's that only came out as A's that probably were intended to be set subtraction).

The basic idea is to show that if x is an element of one side, x is an element of the other side. For example, if the question is show [itex] A = (A-B)\cup B[/itex] if B is a subset of A, then I would do:

Suppose x is contained in A. Then either x is an element of B, or x is not. If x is an element of B, x is contained in [itex](A-B)\cup B[/itex] by definition of union. If x is not an element of B, then x is in A-B and hence in [itex](A-B)\cup B[/itex]. In either case, x is an element of [itex](A-B)\cup B[/itex]

Now, suppose x is in [itex](A-B)\cup B[/itex]. Then either x is in A-B or x is in B. If x is in A-B, then x is in A necessarily. If x is contained in B, then as B is a subset of A, x is contained in A. In either case, x is an element of A

Hence x is contained in A if and only if x is contained in [itex](A-B)\cup B[/itex] assuming B is a subset of A

Try using logic like that for your problem
roam
roam is offline
#3
Jul23-09, 03:50 AM
P: 884
I'm sorry, I don't know why the latex code didn't work, I will use the "-" sign instead of the "\" in my posts. Anyway here's the question:



So for the first one:

Suppose [tex]x \in A \cup B[/tex], then [tex]x \in A[/tex] or [tex]x \in B[/tex] or [tex]x \in A[/tex] and [tex]x \in B[/tex], thus [tex]x \in (A-B) \cup (B-A) \cup (A \cap B)[/tex] and hence:

[tex]A \cup B \subseteq (A-B) \cup (B-A) \cup (A \cap B)[/tex]

Conversely, suppose [tex]x \in (A-B) \cup (B-A) \cup (A \cap B)[/tex], then [tex]x \in A[/tex] or [tex]x \in B[/tex] or [tex]x \in A[/tex] and [tex]x \in B[/tex], so by the definition of union [tex]x \in A\cup B[/tex].

[tex](A-B) \cup (B-A) \cup (A \cap B) \subseteq A \cup B[/tex]

Is this proof correct?

HallsofIvy
HallsofIvy is offline
#4
Jul23-09, 06:26 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,881

Proving Sets Intersections/Unions


You shouldn't just jump form "if [itex]x\in A\cup B[/itex]" to "hence". Show more detail.
If x is in [itex]A\cup B[/itex], the x is in A or in B (or both). If x is in A and NOT B then x is in [itex]A- B[/itex]. If x is B but NOT A, then [itex]B- A[/itex]. If x is in both A and B, then x is in [itex]A\cap B[/itex]. In any case x is in [itex](A-B)\cup(B-A)\cup(A\cap B)[/itex].
roam
roam is offline
#5
Jul26-09, 12:57 AM
P: 884
OK here's what I've done for the second one:

[tex]A \times (B-C) = (A \times B) - (A \times C)[/tex]

Suppose [tex]x \in A \times (B-C)[/tex], it means that x belongs to [tex]A \times B[/tex] but not [tex]A \times C[/tex] (is this the explanation that is required?)

So [tex]x \in (A \times B) - (A \times C)[/tex] [tex]\Rightarrow A \times (B-C) \subseteq (A \times B) - (A \times C)[/tex]

Now suppose that x is in [tex](A \times B) - (A \times C)[/tex], that means [tex]x \in (A \times B)[/tex], [tex]x \notin (A \times C)[/tex] (is this sufficient?) therefore:

[tex]x \in A \times (B-C)[/tex]

[tex](A \times B) - (A \times C) \subseteq A \times (B-C) [/tex]

So is it correct?
Office_Shredder
Office_Shredder is offline
#6
Jul26-09, 01:53 AM
Mentor
P: 4,499
I would demonstrate that if x is in Ax(B-C) then x is in AxB but not in AxC, since that basically is what the question is asking
roam
roam is offline
#7
Jul26-09, 04:09 AM
P: 884
And if [tex]x \in (A \times B) - (A \times C)[/tex] then [tex]x \in (A \times B)[/tex] but [tex]x \notin A \times C[/tex] which means [tex]x \in A \times (B-C)[/tex].
n!kofeyn
n!kofeyn is offline
#8
Jul26-09, 04:51 AM
P: 538
Quote Quote by roam View Post
OK here's what I've done for the second one:

[tex]A \times (B-C) = (A \times B) - (A \times C)[/tex]

Suppose [tex]x \in A \times (B-C)[/tex], it means that x belongs to [tex]A \times B[/tex] but not [tex]A \times C[/tex] (is this the explanation that is required?)

So [tex]x \in (A \times B) - (A \times C)[/tex] [tex]\Rightarrow A \times (B-C) \subseteq (A \times B) - (A \times C)[/tex]

Now suppose that x is in [tex](A \times B) - (A \times C)[/tex], that means [tex]x \in (A \times B)[/tex], [tex]x \notin (A \times C)[/tex] (is this sufficient?) therefore:

[tex]x \in A \times (B-C)[/tex]

[tex](A \times B) - (A \times C) \subseteq A \times (B-C) [/tex]

So is it correct?
Instead of letting the point x be in a cross product of two sets, I might suggest the following.
Let [itex](x,y)\in A\times (B-C)[/itex]
[itex]x\in A[/itex], and [itex]y\in B[/itex] and [itex]y\not\in C[/itex]
[itex]x\in A[/itex] and [itex]y\in B[/itex], and [itex]x\in A[/itex] and [itex]y\not\in C[/itex]
[itex](x,y)\in A\times B[/itex] and [itex](x,y)\not\in A\times C[/itex]
[itex](x,y)\in (A\times B) - (A\times C)[/itex]
Therefore, [itex] A\times(B-C)\subseteq (A\times B) - (A\times C)[/itex]

Here I'm letting (x,y) be in the cross product, as a point in a cross product of two sets is an ordered pair of two points. For me, that clears things up a bit, as you are directly using the definition of each set function: the cross product and set minus. Now can you do the same for the other direction? For these set theory proofs, I think it is good to overkill them by including every single step so as to not make any leaps, which can often lead to mistakes. Although, it looks like you are doing okay, just include more steps.
roam
roam is offline
#9
Jul26-09, 10:30 PM
P: 884
Quote Quote by n!kofeyn View Post
Instead of letting the point x be in a cross product of two sets, I might suggest the following.
Let [itex](x,y)\in A\times (B-C)[/itex]
[itex]x\in A[/itex], and [itex]y\in B[/itex] and [itex]y\not\in C[/itex]
[itex]x\in A[/itex] and [itex]y\in B[/itex], and [itex]x\in A[/itex] and [itex]y\not\in C[/itex]
[itex](x,y)\in A\times B[/itex] and [itex](x,y)\not\in A\times C[/itex]
[itex](x,y)\in (A\times B) - (A\times C)[/itex]
Therefore, [itex] A\times(B-C)\subseteq (A\times B) - (A\times C)[/itex]

Here I'm letting (x,y) be in the cross product, as a point in a cross product of two sets is an ordered pair of two points. For me, that clears things up a bit, as you are directly using the definition of each set function: the cross product and set minus. Now can you do the same for the other direction? For these set theory proofs, I think it is good to overkill them by including every single step so as to not make any leaps, which can often lead to mistakes. Although, it looks like you are doing okay, just include more steps.
So here's the converse (please correct me if I'm wrong):

Suppose [tex](x,y) \in (A \times B) - (A \times C)[/tex]

[tex]x \in A[/tex], and [tex]y \in B[/tex], [tex]x \notin A[/tex] [tex]y \notin C[/tex]

So, [tex]x \in A[/tex], and [tex]y \in B[/tex], & [tex]y \notin C[/tex]

[tex](x,y) \in A \times (B-C)[/tex]

Hence: [tex](A\times B) - (A\times C) \subseteq A\times(B-C)[/tex]

Does this show enough detail/steps?
n!kofeyn
n!kofeyn is offline
#10
Jul26-09, 11:54 PM
P: 538
Quote Quote by roam View Post
So here's the converse (please correct me if I'm wrong):

Suppose [tex](x,y) \in (A \times B) - (A \times C)[/tex]

[tex]x \in A[/tex], and [tex]y \in B[/tex], [tex]x \notin A[/tex] [tex]y \notin C[/tex]
I would be careful right here. Recall that the definition of a Cartesian product is [itex]A\times C = \{(a,c) \mid a\in A \text{ and } c\in C\}.[/itex]
For a point [itex](a,c)\not\in A\times C[/itex], then [itex]a\not\in A[/itex] or [itex]c\not\in C[/itex].

So if [itex](x,y)\in(A\times B)-(A\times C)[/itex],
then [itex](x,y)\in A\times B[/itex] and [itex](x,y)\not\in A\times C[/itex].
Then [itex]x\in A[/itex] and [itex]y\in B[/itex], and [itex]x\not\in A[/itex] or [itex]y\not\in C[/itex].
But we know that x is in A from the first part, so y must not be in C.
So then [itex]x\in A[/itex] and [itex]y\in B[/itex], and [itex]x\in A[/itex] and [itex]y\not\in C[/itex].
Then [itex]x\in A[/itex], and [itex]y\in B[/itex] and [itex]y\not\in C[/itex].
Then [itex]x\in A[/itex], and [itex]y\in B-C[/itex].
Thus [itex](x,y)\in A \times (B-C)[/itex].
Therefore, [itex](A\times B)-(A\times C)\subseteq A\times (B-C)[/itex].

By the way, I said cross product in my previous post, but I meant Cartesian product. Make sure you go through all my steps in both posts so that you understand. For these proofs, you have to very explicit with your "ands" and "ors", as well as with where your points are at. Hope this helps.
roam
roam is offline
#11
Jul27-09, 02:38 AM
P: 884
Thanks very much your post was very helpful.


Register to reply

Related Discussions
What am I doing wrong on this simple cardinality of unions/intersections problem? General Math 5
preserves inclusions, unions intersections... Differential Geometry 0
probability of unions/intersections Set Theory, Logic, Probability, Statistics 4
Unions and Intersections Set Theory, Logic, Probability, Statistics 15
Functions, intersections, and unions Introductory Physics Homework 3