Prove `A nn(B uu C) = (A nn B) uu (A nn C)` for sets A, B, C.

2 Answers | Add Yours

txmedteach's profile pic

txmedteach | High School Teacher | (Level 3) Associate Educator

Posted on

I apologize, in order for (1) and (2) to make a contradiction in the proof that `x in Ann(BuuC) => x in (AnnB)uu(AnnC)`, we need to consider somthing extra.

Just to make sure we have it down, our original description of `x` was the following:

`x in Ann(BuuC)`

We then assumed `x !in (AnnB)uu(AnnC)`

This fact told us that both of the following must also be true:

1) `x !in AnnB`

2)`x !in AnnC`

In order for (1) to be true, `x !in A` or `x!inB`. If `x !in A`, we arrive immediately at a contradiction, because we supposed that `x` was in a set derived from an intersection with `A`.  If `x !in B` and `x in A` we must proceed to show that (2) leads to a contradiction. In order for (2) to be true, `x !in A` or `x !in C`. We already showed that `x in A`; therefore, `x !in C`. Therefore, `x !in B` and `x !in C` in order for both (1) and (2) to hold. However, if `x !in B` and `x !in C`, then `x !in BuuC`, leading us to a contradiction because we supposed that `x` was in a set derived from an intersection with `BuuC`.

Therefore, we have proven the following (for sure this time!):

`x in Ann(BuuC) => x in (AnnB)uu(AnnC)`

Again, I apologize for overlooking that in my original answer!

txmedteach's profile pic

txmedteach | High School Teacher | (Level 3) Associate Educator

Posted on

To prove this statement, you have to show the two sets are equivalent. In other words, there must be no elements from the first set that are not contained within the second set and vice versa.

To start, let's prove the forward direction, that all elements from the set on the left are in the set on the right. Suppose the following:

`x in Ann(BuuC)`

With a view towards contradiction, assume the following:

`x !in (AnnB)uu(AnnC)`

If this is the case, both of the following must be true:

1) `x !in AnnB`

2) `x !in AnnC`

In order for (1) to be true, `x !in B` or `x !in A`; however, in either case, `x !in Ann(BuuC)`, a contradiction to our first supposition. Therefore, because both (1) and (2) must have been true to avoid a contradiction, we do not have to show that (2) leads to a contradiction, which it does. Therefore, we have proven that:

`x in Ann(BuuC) => x in (AnnB)uu(AnnC)`.

Now to prove the opposite direction. Suppose the following:

`y in (AnnB)uu(AnnC)`

Again, with an aim towards contradiction, let's assume the following:

`y !in Ann(BuuC)`

In order for this to be true, one of the following conditions must be met:

3) `y !in A`

4) `y !in BuuC`

In order for (3) to be true, `y !in A`. However, if this were true, then `y !in (AnnB)uu(AnnC)` because an element of `(AnnB)uu(AnnC)` would be derived from the union of two sets derived from intersections with `A`. Therefore, each element in the set must be in `A`. Therefore, the conclusion that `y !in A` is a contradiction.

Similarly, in order for (4) to be true, `y !in B` and `y !in C`.  However, this also would imply that `y !in (AnnB)uu(AnnC)` because in order for an element to be contained within `(AnnB)uu(AnnC)`, it must be contained within the intersection of a set with `B` or contained within the intersection of a set with `C`.  If (4) is true, `y` meets neither criterion, creating another contradiction.

Because both cases create a contradiction in this second larger scenario, we have proven the following:

`y in (AnnB)uu(AnnC) => y in Ann(BuuC)`

Because we have proven it both ways, we have shown that both sets contain exactly the same elements. Therefore, the two are equivalent, proving the desired statement:

`Ann(BuuC) = (AnnB)uu(AnnC)`

I hope that helps!

Sources:

We’ve answered 318,934 questions. We can answer yours, too.

Ask a question