3
$\begingroup$

I was just wondering if it is possible to derive the set $A-B$ using just union and intersection. I've tried all different ways and even tried adding a new set C and tried with that but didn't work out. I am questioning is it even possible?

$\endgroup$
7
$\begingroup$

$A-B$ cannot be realised by unions and intersections alone, even if an ambient set is brought in.

The union and intersection operations correspond to the $\lor$ and $\land$ operators of Boolean logic. These operators are monotone – changing any of their arguments from $0$ to $1$ never changes the result from $1$ to $0$. But $A-B$ corresponds to $A\land\neg B$, which is not monotone.

$\endgroup$
  • 2
    $\begingroup$ Your result on monotone operators is more difficult to prove than the question, which only requires an elementary argument, see my answer. $\endgroup$ – J.-E. Pin May 26 at 5:17
  • 1
    $\begingroup$ Your question is a better servant of the present @J.-E.Pin , but this answer is a better servant of the future. $\endgroup$ – Dannie May 26 at 12:31
  • $\begingroup$ @Dannie: You may be interested in my answer for how one can naturally and intuitively derive the key idea used in Parcly's answer. $\endgroup$ – user21820 May 26 at 12:53
3
$\begingroup$

Here is a minimal counterexample.

Let $X = \{0,1\}$. Then the subset $S = \{ \emptyset, \{1\}, \{0,1\}\}$ of $\mathcal{P}(X)$ is closed under intersection and union, as you can easily verify. However, $\{0,1\} - \{1\} = \{0\}$ is not in $S$. Therefore $\{0\}$ cannot be obtained from $\{0,1\}$ and $\{1\}$ just by using union and intersection.

$\endgroup$
1
$\begingroup$

Here's an abstract way to approach it, which - while more complicated than necessary (just look at J.-E. Pin's counterexample) - may be useful for such arguments more generally:

Remember that forming $A-B$ from $A$ consists of throwing out the whole set of things $A$ and $B$ have in common. Now this is a problem: "$\cup$" doesn't throw anything out at all, and "$\cap$" throws out everything except the things $A$ and $B$ have in common. Intuitively, repeatedly applying $\cup$ and $\cap$ to $A$ and $B$ - however complicatedly we do so - will never manage to get rid of anything in both $A$ and $B$, so will never be able to yield $A-B$ (unless $A\cap B=\emptyset$ of course).


Now let's formalize that intuition.

First we'll need a precise definition of "built from $A$ and $B$ using $\cup$ and $\cap$." This is the following:

  • Let $\mathcal{C}_0=\{A,B\}$.

  • For $i\in\mathbb{N}$, let $$\mathcal{C}_{i+1}=\mathcal{C}_i\cup\{X\cup Y:X,Y\in\mathcal{C}_i\}\cup\{X\cap Y: X,Y\in\mathcal{C}_i\}.$$

  • Let $\mathcal{C}=\bigcup_{i\in\mathbb{N}}\mathcal{C}_i$.

This $\mathcal{C}$ is the set-of-sets we want.

Exercise: Show that $\mathcal{C}$ can also be defined as the smallest set-of-sets containing both $A$ and $B$ as elements and closed under $\cup$ and $\cap$. (This "top-down" definition is perhaps less constructive, but is also extremely useful.)

Now suppose $A\cap B\not=\emptyset$; we will prove the following:

Claim: For each $Z\in\mathcal{C}$, we have $A\cap B\subseteq Z$ (and hence $Z\not=A-B$).

Proof: Everything in $\mathcal{C}$ lives in some $\mathcal{C}_i$, so we can use induction.

  • Clearly every element of $\mathcal{C}_0$ contains $A\cap B$ as a subset.

  • Suppose every element of $\mathcal{C}_i$ contains $A\cap B$ as a subset; we want to show the same for $\mathcal{C}_{i+1}$. So let $Z\in\mathcal{C}_{i+1}$. There are three cases:

    • $Z\in\mathcal{C}$: then we're done.

    • $Z=X\cup Y$ for some $X,Y\in\mathcal{C}_i$: by the induction hypothesis we have $A\cap B\subseteq X$, so since $X\subseteq X\cup Y$ we have $A\cap B\subseteq Z$.

    • $Z=X\cap Y$ for some $X,Y\in\mathcal{C}_i$: again by the induction hypothesis we have $A\cap B\subseteq X$ and $A\cap B\subseteq Y$, so $A\cap B\subseteq X\cap Y$.

And we're done!

$\endgroup$
1
$\begingroup$

Here is an elementary solution that should serve as an intuitive stepping stone to the very useful technique in Parcly Taxel's answer.

Consider the effects of adding elements to a set involved in a union or intersection. What happens? The union or intersection can either gain new elements or perhaps not change at all. It cannot lose elements. This is a simple way of grasping the concept called "monotone". But then it is very clear intuitively that you cannot obtain set difference by a formula that uses only union and intersection, because adding elements to $B$ cannot possibly remove elements from the original result. Thus if we start with $A$ non-empty and $B$ empty, the formula must produce $A$, but if we then add elements to $B$ to make it equal to $A$, the formula must produce $∅$, which is impossible by the above observation.

More concretely this should suggest the following simple counter-example (simpler than JEP's): If $A = B$ and are non-empty, then obviously any sequence of union/intersection operations will not produce any new set besides $A$, so obviously $A∖B = ∅$ cannot be produced.

$\endgroup$
0
$\begingroup$

If you see the definition of $A - B$, which is usually written as $A \setminus B$, it means the collection of all those elements of $A$ which are not in $B$. Therefore, the elements in $A \setminus B$ have the property that they are IN $A$ AND NOT IN $B$. We can write this as $A \cap B^c$, where $B^c$ is the complement of $B$ in the universal set being considered. In fact, this is a reason that $A \setminus B$ is called the "relative complement" of $B$ with respect to $A$.

$\endgroup$
  • $\begingroup$ Unions and intersections ONLY. No complements are allowed. See my answer. $\endgroup$ – Parcly Taxel May 26 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.