How to prove these two sets are identical?

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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).