F for Freedom said:
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...)
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
Every propositional formula can be converted into an equivalent formula that is in CNF. This transformation is based on rules about logical equivalences: the double negative law, De Morgan's laws, and the distributive law.
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)
<br />
(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) <br />
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 Y
i and Z
j.
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?
