# Proof regarding the algebra of sets.

1. Jun 5, 2010

I am currently trying to prove the following:
An equation in X with righthand member $$\oslash$$ can be reduced to one of the form (A $$\cap$$ X) $$\cup$$ (B $$\cap$$ ~X) = $$\oslash$$.
(Where A, B, and X are sets of some universal set U, and ~X is the complement of the set X).

The only problem is that I'm not sure how to formulate or symbolize every possible equation in X. After asking a few friends and doing a bit of research online I came across ideas like structural induction and normal forms, but I'm still not sure how to apply it to prove this statement.

I know that once I can formulate this I can apply the deMorgan laws until complements of individual sets appear, and then expand the resulting lefthand side by the distributive laws and then play around with the X's and ~X's until I get what I need. But again, this all depends on the initial problem I have.

Any help would be appreciated.

2. Jun 5, 2010

### CompuChip

Indeed, the two usual arguments I have seen are the following:

1) Bring the expression into some normal form, for example
$$(X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k)$$
using $\neg X$ for the complement (there are theorems that say that this can always be done) and prove your statement for a normal form.

2) Use, what you so nicely call structural induction. First you identify which operations make a new valid ("well-formed" equation). For example:
* a = X is well-formed (i.e. X = 0 with 0 the empty set)
* If a is well-formed, then so is ~a (e.g. $\neg X = 0$)
* If a and b are well-formed, then so are $a \cup b$ and $a \cap b$)
etc.

Then use this to prove your statement. For example,
* X = 0 is in the given form (let A = B = X).
* Suppose that $a = (A \cap X) \cup (B \cap \neg X)$. Then
$$\neg a = \neg( (A \cap X) \cup (B \cap \neg X) ) = \neg(A \cap X) \cap \neg(B \cap \neg X) = \cdots$$​
and reason until you again have something of the form $\neg a = (A' \cap X) \cup (B' \cap \neg X)$ (using deMorgan's laws, etc).​

3. Jun 5, 2010

Forgive me, but which expression are you referring to? Are you saying that I need to break the proof up by cases and prove that each separate expression in X can be reduced to the formula in the first post? In that case, is there another proof that shows that there is only a finite number of expressions that I need to test out? (This seems rather tedious...)

I'm not sure what you're doing here. Aren't you assuming what we're trying to prove? What do you mean by proving my statement for a normal form? I'm not sure why this is significant, but maybe I just need to read more about normal forms.

I guess this relates to my first question -- how do I know when to stop making these combinations of well-formed formulas? Until I get $(A \cap X) \cup (B \cap \neg X) = \oslash$ ?

Again, isn't this assuming what I'm trying to prove, since a = $\oslash$ ?

I can follow the logical steps here, but I'm not quite sure why you are doing this. How does showing that $\neg a$ is well-formed prove the original statement?

I'm sorry if all my questions have obvious answers, I just can't see the bigger picture at the moment.

4. Jun 7, 2010

### CompuChip

What you want to prove is that any expression in X (which you set equal to the empty set) can be written as $(X \cap A) \cup (\neg X \cap B)$, right? The idea of this method of proof is the following:
(1) Take such a formula (the left hand of an equation in X of which the right hand is the empty set)
(2) Write it in a normal form
(3) Prove that any expression in the normal form can be written in the way you want

For the normal form, there are several possibilities, such as Disjunctive normal form (DNF) or Conjunctive normal form (CNF).
On that link you will also find the claim that
Basically what it says is, that every formula like the one you started with in step (1) has a logically equivalent form that looks like (for example, using DNF)
$$(X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k)$$

Then you can use logical steps to rewrite this to the form you want, i.e. show that this in turn can be rewritten as
$$(X \cap A) \cup (\neg X \cap B)$$
where of course A and B will be expressed in all of the Yi and Zj.
That proves the statement at once for all possible formulas.

For the second method, I think you haven't quite got the idea yet of what we are trying to do. Maybe you should read my post again very slowly. The idea is as follows: if we have any equation in X which we can set equal to the empty set, then we can build this equation from scratch. For this we can use building rules, like:
if you have two of these equations, say
A = 0 and B = 0
(where 0 stands for the empty set, and A and B can be any equation in X), then you can build new equations like
$A \cup B = 0$ and $A \cap B = 0$.
For example, since
$$(X \cap S) \cap (\neg X \cup T) = 0$$ and $$(X \cup U) \cap (\neg X \cup (X \cap V)) \cup W = 0$$
are valid equations (as opossed to, for example $$X \cup = 0$$ or $$X \cap \cap Y = 0$$) you know that also
$$\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cup \left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0$$
is a valid equation, and so is
$$\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cap\left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0$$
and
$$\neg \left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cup \left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0$$
and
$$\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cap \neg\left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0$$
and so on.

So this is sort of like a proof by induction. In a proof by induction, you assume that some statement (S) is true for the number n and then show that it also holds for n + 1. Then if you show that for n = 0 it is true, you have proved it for all possible values of n (because from n = 0 it follows for n = 1, and from that for n = 2, etc).

Now, you assume some statement (in your case, that an equation be written in the form $(X \cup A) \cap (\neg X \cup B)$) is true for two particular equations. Then you show that it also holds for the conjunction, disjunction and negation of those statements. Now if you show that it is true for the simplest equation you can think of (for example, X) you have proved it for all possible formulas (because from a = X, it also follows for a = (not X), a = X union X, a = X intersection X; and from that for a = not (X union X), A = X intersection (not X), and so on).

Sorry I don't have time to explain in even more detail, I hope this makes it more clear.
Perhaps a book on first order logic would be helpful to you?