# Proof Help: Membership Table

I am new to proofs with membership tables and this is the last question I am posting.

I am trying to teach myself discrete math and am stuck on this:

Let $A, B$ and $C$ be sets in the universal set U. By making a membership table, prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

-
Ah, I had to look up what a membership table was somewhere else. I see. What have you tried? – mixedmath Mar 26 '13 at 0:18

I'm going to do an example with a smaller thing in two ways, hopefully inspiring you to the answer.

Let's show that $A = (B^C\cap A) \cup (A \cap B)$, where by $B^C$ I mean the 'complement' of $B$ in $U$, consisting of all elements in $U$ that are not in $B$.

Let's first do this by using a 'membership table.'

$$\begin{array}{cccccc} A & B & B^C & B^C\cap A & A\cap B & (B^c\cap A)\cup (A\cap B) \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{array}$$

What this does is chooses all possible membership options for elements. Here, an element can be in $A$, not be in $A$, be in $B$, or not be in $B$. This is where my first two columns come from. The third column is simply the opposite of the second. Then you determine the rest of the relationships. For example, an element in $A$ that is also in $B$ is in $A\cap B$, giving the rest of the first row.

Now you notice that anytime you have an element in $A$, that element is also in $(B^c \cap A)\cup (A \cap B)$, and vice-versa. Thus they are the same set.

A much more intuitive way (I think) of viewing this proof is to see that $(B^c \cap A)\cup (A \cap B)$ is exactly the set of things in $A$ that are in $B$ plus the set of things in $A$ that are not in $B$. As everything is either in $B$ or not in $B$, we get all of $A$.

Does this help?

-
I hope it helps - it was a pain to TeX up. – mixedmath Mar 26 '13 at 0:35
Thank you!! By B^c, do you mean B U C? – JustaBreitGuy Mar 26 '13 at 1:22
@Justa: There are many ways of denoting the 'complement' of something, but by $B^C$ I mean everything not in $B$. – mixedmath Mar 26 '13 at 1:24
OK- But where does the C come into play in that situation? Sorry :) – JustaBreitGuy Mar 26 '13 at 1:26
+1 mixedmath and +1 for the time and effort! – amWhy Mar 26 '13 at 14:28

Usually, when we are trying to prove that two sets $A, B$ are equal, we start with an arbitrary element $x$ from one side, say from $A$, and we try to show that this element must be in $B$. If we succeed, since $x$ was any old element of $A$, with no special assumptions attached, we may conclude that every element of $A$ must also be contained in $B$. This will show that $A$ is contained in $B$---if you think of this in a Venn diagram, the circle representing the set $A$ will be inside that of $B$.

We repeat the process for elements of $B$, and if we succeed, then by the same reason as above, we conclude that $B$ is contained in $A$. But the only way two sets can contain one another is if they are equal, so the sets we started out with must be equal! This last step can been seen clearly if you think back to the Venn diagram circles.

The proof process described above is sometimes called element chasing.

Now, when we're dealing with more complicated sets, such as those built up with unions and intersections as in the example in your problem, the main challenge is figuring out where that arbitrary element $x$ is when we start out. One method you may approach this, as suggested by the problem, is to tabulate the membership relation. That is, make a table with the constituent sets as headers, and then fill out whether or not some element $x$ that is contained in one side is contained in the smaller sets.

So, for example, if $x \in A\cap(B\cup C)$, then you might have a table with $A, B, C$ with headers. Looking at the definition of $\cap$, it must be the case that $x \in A$ and $x \in B\cup C$, so you might write something down in the table indicating that $x$ is certainly in $A$, and $x$ is in $B\cup C$. Then you continue from here.

This method is an approach to element chasing, but definitely not the only one. I would say not necessarily get too hung up on the whole idea of membership tables, but try to write in a way that is clear and logical.

-