Set theory: If A-intersect-B^C = A-intersect-C, then A is subset of B^C-union-C^C

[pisrationalhahaha]

Show that
\(\displaystyle A\cap B^{c} =A\cap C\Rightarrow A\subseteq B^{c}\cup C^{c}\)
A, B, and C are subsets of S
Can someone give me a hint ?

 

[stapel]

Given that A, B, and C are subsets of another set S, show that

. . . . .\(\displaystyle A\cap B^{c}\, =\, A\cap C\, \Rightarrow\, A\, \subseteq \,B^{c}\cup C^{c}\)

Can someone give me a hint ?

Try using the standard process of element-chasing. Pick a generic member of the "if" statement, and show that it is also a member of the "then" statement.

For instance, if I pick "a" to be the element which is in each of A-intersect-B-complement and A-intersect-C, then I know that "a" is in A, B-complement (so not in B), and C. In other words, "a" is in A and C, but not in B. Where does this lead?

 

[pisrationalhahaha]

Try using the standard process of element-chasing. Pick a generic member of the "if" statement, and show that it is also a member of the "then" statement.

For instance, if I pick "a" to be the element which is in each of A-intersect-B-complement and A-intersect-C, then I know that "a" is in A, B-complement (so not in B), and C. In other words, "a" is in A and C, but not in B. Where does this lead?

Let
\(\displaystyle a\in A\cap C\)
Since \(\displaystyle A\cap C=A\cap B^c\)
then
\(\displaystyle a\in A\cap C\cap B^c\)
\(\displaystyle \Rightarrow a\in C\cap B^c\)
\(\displaystyle \Rightarrow [a\notin C\cap B\) \(\displaystyle \Leftrightarrow a\in (C\cap B)^c\)\(\displaystyle \Leftrightarrow a\in C^c\cup B^c]\)
Is what I wrote correct ?

 

[stapel]

Let \(\displaystyle a\, \in\, A\,\cap\, C\)

Since \(\displaystyle A\, \cap\, C\,=\,A\,\cap\, B^c\)

No, we can't say that this equality holds for any element in A-intersect-B^C. We haven't "proved" this. Instead, we have to figure out the implications for if the element fulfills the "if" part of the statement. (Re-read my reply, where I explained this and did the work for you.)

For instance, let A = {1, 2, 6, 7}, B = {2, 3, 4, 7}, C = {4, 5, 6, 7}, and S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Then A-intersect-C = {6, 7} and A-intersect-B-complement = {1, 6}. These subsets are not the same; they are not equal. But there is an element which is shared between the two subsets; namely, the 6.

Then \(\displaystyle a\, \in\, A\, \cap\, C\,\cap B^c \, \Longrightarrow\, a\,\in\, C\, \cap\, B^c\)

\(\displaystyle \Longrightarrow\, [a\, \notin \, C\, \cap\, B\, \Longleftrightarrow\, a\, \in\, (C\, \cap\, B)^c\, \Longleftrightarrow\, a\, \in\, C^c\, \cup\, B^c]\)

Is what I wrote correct ?

I think the rest of the steps may be okay, but explaining your logic as you go along would probably be a good idea. Also, you haven't taken the proof all the way to the end; that is, you haven't said anything about subset-hood.

You can also use the standard technique of element-chasing. Let "a" be an element in each of A-intersect-C and A-intersect-B-complement. So "a" is in A and in C, but is not in B. Since "a" is in each of these sets, then it is in their intersection:

. . . . .\(\displaystyle \left(A\, \cap\, C\right)\, \cap\, \left(A\, \cap\, B^C\right)\)

By the Associative and Commutative Laws of sets, we have:

. . . . .\(\displaystyle \left(A\, \cap\, C\right)\, \cap\, \left(A\, \cap\, B^C\right)\, =\, \left(C\, \cap\, A\right)\, \cap\, \left(A\, \cap\, B^C\right)\)

. . . . .\(\displaystyle =\, C\, \cap\, (A\, \cap\, A)\, \cap\, B^C\, =\, C\, \cap\, (A)\, \cap\, B^C\, =\, C\, \cap\, A\, \cap\, B^C\)

If we remove one of these sets from the intersection expression above, we'll get something bigger (or the same size, but certainly not smaller). So, since "a" is in the last set displayed above, then certainly it is in:

. . . . .\(\displaystyle a\, \in\, C\, \cap\, B^C\)

Since "a" is in C and in B-complement, then (as we've shown before) "a" cannot be in B. Therefore, it must be in B-complement. Part of B-complement is C. Since "a" is in C but not in B, then "a" cannot be in C-intersect-B. Since "a" is not in C-intersect-B, then "a" must be in the complement of C-intersect-B.

Apply one of DeMorgan's Laws, and you have proved the result.

Then, because any "a" in A that complied with the equation in the "if" statement ended up being in the set in the "then" statement, we have shown that every element of A must be an element in the "then" statement. Since very element of A is in this other set, then A must be a subset of this other set.

Study the above, and try to come up with your own proof, using the above methodology, using the correct "if" relationships, and completing the proof to the conclusion of the "then" statement.