Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have recently encountered this equality as I am learning set theory and there are a couple of points I am not sure about: $$ (A\cap B \cap (A' \cup C')) \cup ((A' \cup B') \cap A \cap C) = (A\cap B\cap C') \cup (A\cap B'\cap C) .$$

1) how does $((A' \cup B') \cap A \cap C) $ become $ (A\cap B'\cap C) $ would it not be $ (A\cup B'\cap C) $ ?

2) For the above to be true it means that the parentheses () have no effect and the expression can be evaluated in any order. Is this the case or is this achieved some other way?

NOTE: $A'$ means complementy of $A$.

share|improve this question
    
There are many notations for the complement set, the two common ones are $\bar A$ and $A^c$, I prefer the latter, as the bar one is way overused throughout mathematics. –  Asaf Karagila May 25 '11 at 21:11

3 Answers 3

up vote 7 down vote accepted

Added. It seems to me that you need to back up and start slower, develop some feel for these operations and their meanings; right now, it seems like you are just trying to shuffle symbols...

You should become familiar with some of the basic properties of the union, intersection and complement: for all sets $X$, $Y$, and $Z$:

  • Commutativity of union: $X\cup Y = Y\cup X$.
  • Commutativity of intersection: $X\cap Y=Y\cap X$.
  • Associativity of union: $(X\cup Y)\cup Z = X\cup(Y\cup Z)$.
  • Associativity of intersection: $(X\cap Y)\cap Z = X\cap (Y\cap Z)$.
  • Distributivity of intersection over union: $X\cap(Y\cup Z) = (X\cap Y)\cup(X\cap Z)$.
  • Distributivity of union over intersection: $X\cup(Y\cap Z)=(X\cup Y)\cap (X\cup Z)$.
  • Idempotency of union: $X\cup X = X$.
  • Idempotency of intersection: $X\cap X = X$.
  • Empty set is the neutral element for union: $X\cup\emptyset = X$.
  • Empty set is a zero element for intersection: $X\cap \emptyset=\emptyset$.
  • Double complementation: $(X')' = X$.
  • Complements and unions: $X\cup X' = \text{everything}$.
  • Complements and intersections: $X\cap X' = \emptyset$.
  • De Morgan's Laws: $(X\cap Y)' = X'\cup Y'$ and $(X\cup Y)' = X'\cap Y'$.

Try proving the following:

  • $X\subseteq Y$ if and only if $X\cap Y'=\emptyset$.
  • $X\subseteq Y$ if and only if $X'\cup Y =\text{everything}$.
  • $X\subseteq Y$ if and only if $(X\cap Y')\subseteq X'$.
  • $X\subseteq Y$ if and only if $(X\cap Y')\subseteq Y$.
  • $X\subseteq Y$ if and only if $(X\cap Y')\subseteq (Z\cap Z')$.

You have to be careful. Just because two expressions are equal does not necessarily mean that there is some standard rewriting method that transforms the first into the second. Just because $2\times 3 = 1+5$, that does not mean that you have some standard way of taking $2\times 3$ and having it "become" $1+5$; it's just that the two expressions yield the same final answer.

Here, though, you do have some basic rules, specifically distributivity. For any sets $X$, $Y$, and $Z$, we have that $\cup$ distributes over $\cap$, and $\cap$ distributes over $\cup$ (just like, with numbers, $\times$ distributes over $+$). Explicitly, $$X\cap (Y\cup Z) = (X\cap Y)\cup(X\cap Z)\qquad\text{and}\qquad X\cup(Y\cap Z) = (X\cup Y)\cap(X\cup Z).$$ This just says: the things that are both in $X$ and (either in $Y$ or $Z$) are the same as the things that are either in both $X$ and $Y$, or in both $X$ and $Z$; and the things that are either in $X$ or in both $Y$ and $Z$ are the same as the things that are both in either $X$ or $Y$, or in either $X$ or $Z$.

So, take $(A'\cup B')\cap A\cap C$. This is the same (since $(X\cap Y)\cap Z = X\cap (Y\cap Z)$; intersection is associative) as $$\Bigl( (A'\cup B')\cap A\Bigr)\cap C.$$ Distributing the first $\cap$ over the $\cup$, we have that this is the same as $$\Bigl( (A'\cap A)\cup (B'\cap A)\Bigr)\cap C.$$ Distributing the last $\cap$ over the $\cup$, we get that this is the same as $$\Bigl((A'\cap A)\cap C\Bigr) \cup \Bigl( (B'\cap A)\cap C\Bigr).$$ Now, look at $A'\cap A\cap C$: since $A'$ is the complement of $A$, then $A'\cap A = \emptyset$, so $A'\cap A\cap C=\emptyset$. And since for any set $X$, $\emptyset\cup X = X$, then the entire thing is just the same as the second set, namely $$(B'\cap A)\cap C.$$ And since $X\cap Y = Y\cap X$, then this is the same as $A\cap B'\cap C$.

So, no it should not be $A\cup B'\cap C$.

No, it is not true that the parentheses have no effect in general. Both $\cup$ and $\cap$ are associative, so that $(X\cup Y)\cup Z$ is the same as $X\cup(Y\cup Z)$, and so we may write it as $X\cup Y\cup Z$ (exactly like $(2+3)+4 = 2+(3+4) = 2+3+4$). But when you have both unions and intersections, parenthesis start to matter because $(X\cup Y)\cap Z$ is not necessarily the same thing as $X\cup(Y\cap Z)$, exactly like $(2+3)\times 4$ is not the same as $2+(3\times 4)$.


share|improve this answer
    
Great answer thanks.also the extra information you added is great for me. Thanks to joriki aswell –  Jason May 25 '11 at 19:16
    
Nice job, Arturo: +1 for answer and +1 for effort (if I had two votes to give)! This could almost make a "big-list"...in terms of serving as a reference to which to direct similar questions! Any way to flag it so it stands out as such...? –  amWhy May 25 '11 at 19:54

1) Both terms on the left are simplified in the same way. When you intersect $A$ and $B$ with something, it doesn't matter whether you throw in $A'$ or not, since $A'$ is disjoint from $A$. Thus $A\cap B \cap (A' \cup C')=A\cap B \cap C'$. More formally, you can deduce this using the distributive law: $A\cap B \cap (A' \cup C')=(A\cap B \cap A') \cup (A\cap B \cap C') = \emptyset \cup (A\cap B \cap C')= A\cap B \cap C'$. Likewise, $(A' \cup B') \cap A \cap C=B' \cap A \cap C$.

2) I don't understand the second part of the question. The parentheses are important and are being applied correctly; you'd have to point out why you think they have no effect.

share|improve this answer

Even though the equality can be established reasonably simply by "Boolean Algebra" manipulations, there is no a priori reason to do it in that way. (Of course, an exercise may demand that you use such manipulations, to test your mastery of these.)

So let us proceed more concretely. A standard approach to showing that two sets $S$ and $T$ are equal is to show that if $x \in S$ then $x \in T$, and vice-versa. I will do this in a semi-mechanical way, in order to illustrate the process. Then I will look back and note that everything was obvious all along.

Let $S$ be the set on the left, and $T$ the set on the right. Then $x \in S$ if $$x\in A\cap B \cap (A' \cup C')\qquad\text{OR} \qquad x\in (A' \cup B') \cap A \cap C$$

Suppose for example that $x\in A\cap B \cap (A' \cup C')$. Then $x$ is in $A$, and $x$ is in $B$. But also $x \in A' \cup C'$. Since $x$ is in $A$, it cannot be in $A'$, meaning that $x$ is in $A$, in $B$, and in $C'$.

Thus $x \in A\cap B\cap C'$, and therefore $x \in T$.

The other possibility $ x\in (A' \cup B') \cap A \cap C$ is taken care of in exactly the same way. The symmetry would be even more obvious if instead of $(A' \cup B') \cap A \cap C$ we write $A \cap C \cap (A' \cup B')$.

It is equally straightforward to show that if $x \in T$ then $x \in S$. Suppose that $x \in T$. If $x \in T$ then $$x \in A\cap B\cap C' \qquad\text{OR}\qquad x\in A\cap B'\cap C$$ Suppose first that $x \in A\cap B\cap C'$. Then $x$ is in $A$, in $B$, and not in $C$. It is then obvious that $x\in A\cap B \cap (A' \cup C')$, and therefore $x\in S$. The possibility $x\in A\cap B'\cap C$ is dealt with in the same way.

Looking back: Let $D= A\cap B \cap (A' \cup C')$, $E=(A' \cup B') \cap A \cap C$, $F=A\cap B\cap C'$, $G=A\cap B' \cap C$. We were asked to show that $$D \cup E =F \cup G$$ Note that $D=F$ and $E=G$! This is clear almost by inspection. But if you want to do the details, they are written down in the analysis that was done above.

share|improve this answer
    
Great view aswell in my case the question was not to prove equality the equality was just a step along the way and I did not understand it and how it was derived –  Jason May 25 '11 at 22:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.