# How to prove these two sets are identical?

This is more a question of the methadology one should use to solve these type of questions:

Say there is a set $V \subseteq X \subseteq Y$ and $U \subseteq Y$ such that $$X \setminus V = U \cap X$$ Prove that $$V = X\cap (Y \setminus U)$$

The easiest approach I found to prove these solutions is to simply draw a venn diagram that fits all the properties and then the equivalence becomes obvious but I don't think that is rigorous enough.

The other approach I know of is to do something like this:

$$x\in V \implies (x\in X) \wedge (x\notin U\cap X ) \implies (x\notin U\cap V) \implies x\notin U\implies x\in Y\setminus U\implies V\subseteq X\cap (Y\setminus U)$$

$$x\in X\cap (Y\setminus U)\implies (x\in X)\wedge(x\notin U)\implies x\notin X\setminus V \implies x\in V\implies X\cap (Y\setminus U)\subseteq V$$

However I don't like this approach because it looks so messy. Long ago I took a class on Digital Logic and we had all sorts of rules in which we could open up statements in a systematic way. De Morgan's Laws in that case did not depend on whether or not one set was a subset of another. Is there some kind of similiar methadology that one could use in this case to solve such problems in a systematic way?

Let $S$ be the reference set. One can indeed consider $X$, $Y$, $U$ and $V$ as elements of the Boolean ring $\mathcal{P}(S)$ of subsets of $S$, where the addition is the symmetric difference and the product is intersection. Then the union of two subsets $A$ and $B$ is $A + B + AB$, the complement of $A$ is $1 + A$, the set difference $A \ B$ is $A(1+B) = A + AB$ and one has $A + A = 0$ (thus $-A = A$) for all $A$.

Now the conditions $V \subseteq X \subseteq Y$, $U \subseteq Y$ and $X \setminus V = U \cap X$ can be written as $V = XV$, $X = XY$, $U = UY$ and $X + XV = XU$. The equality to prove, $V = X\cap (Y \setminus U)$ becomes $V = XY + XYU$ and is now easy to prove since $$XY + XYU = X + XU = X + (X + XV) = (X + X) + XV = XV = V$$ Note that the fact that $U = UY$ was not used.

The standard methodology for proving two sets are the same is to prove that each is a subset of the other. So, to prove $A=B$ your first case is to prove $A\subseteq B$. To do this, you pick an element of $A$ and argue that it must be contained in $B$. Then for your other case, you wish to prove $B\subseteq A$. To do this, you pick an element of $B$ and argue that it must be contained in $A$.

• I know that. I was asking if there is also some set of rules that always apply so that you could manipulate set descriptions algebraically. Basically is there an set algebra in the same way that there is a boolean algebra? – MathIsCrazy Feb 3 '16 at 23:00

Once you know some standard manipulations, you can skip formal steps pretty easily - just depends on how rigorous your teacher expects you to be. For example, a rapid solution to this is:

$$X\cap(Y\setminus U)=(X\cap Y)\setminus(X\cap U)=X\setminus(X\cap U)=X\setminus(X\setminus V)$$

I've used a distributive law, the fact that $X\subseteq Y$, and a substitution. The conclusion is then trivial: $$X\setminus(X\setminus V)=V$$ This is equivalent to the algebraic statement $-(-x)=x$.

As J.-E Pin explains, there is a formal way to turn set logic into a Boolean Algebra, a ring with nice manipulation properties (in some ways, that's 'why' I can do the manipulation I've given above). However, this is a level of formality that typically ends up being more hassle than its worth if you're working by hand - you have to learn how to follow precisely its rules, and then for larger problems, the working will get longer and longer to write e.g. unions.

EDIT: However, I can see it could be a really valuable technique if you wanted to programme a computer to solve similar problems on a larger scale. Thanks for pointing this out J.-E Pin

At a certain level, your argument just has to be plausible to someone at a similar or higher level than you, so use some intuition, some technical details, and skip any steps that are 'obvious' (whatever that means at your level).

• Well, one advantage of the formal approach is that it can converted to a computer programme able to solve larger examples, contrary to an intuitive approach. – J.-E. Pin Feb 4 '16 at 0:38
• Ah, that's a totally valid point I hadn't considered. My apologies, I'll edit my post. – Alexander Heyes Feb 4 '16 at 20:21