I was wondering about the relation between complement of a subset, different between two subsets, union and intersection of subsets. Can we reduce the set of the above operations in a minimal way so that other operations can be represented by these "independent" operations? And how many ways to do this?

For example, the intersection (or union) can be represented by complement and union (or intersection) in the same way as in De Morgan law.

But can we represent complement or difference in terms of union and intersection?



Well, set difference is defined in terms of intersection and complement: $A\setminus B = A\cap B^C$. (Personally, I prefer the notation $A-B$ to $A\setminus B$, but the latter is relatively standard in my experience.)

As you note, De Morgan's laws allow us to translate between union and intersection via complements. Beyond this, we must have at least union and complement (or, equivalently, intersection and complement). That is, we cannot define complement solely in terms union and intersection.

  • $\begingroup$ Can difference be defined in terms of union and intersection? $\endgroup$ – Tim Oct 11 '10 at 21:54
  • $\begingroup$ Because set difference is defined in terms of intersection and complement, and complement cannot be defined in terms of only union/intersection, the answer is no. $\endgroup$ – Bey Oct 11 '10 at 22:03
  • $\begingroup$ Although we could do something like write A^C as the union (taken over all of X) of all elements x not in A, where X is our universal set. But I assumed you were thinking solely in terms of operations on the sets themselves, rather than appealing to elemental definitions. $\endgroup$ – Bey Oct 11 '10 at 22:05
  • 1
    $\begingroup$ No, because you need a negative for difference and union and intersection are positive operators. See the Wikipedia article Functional completeness, where and and or are truth-preserving. And corresponds to intersection and or to union. $\endgroup$ – Ross Millikan Oct 11 '10 at 22:07

There is a "minimal" definition of set operations, though it's not really a restriction of the classical ones, and is more a fun trick than a clever insight. It was discovered by Charles Sanders Peirce, for general Boolean algebras.

Let $A\uparrow B=(A\cap B)^c$. Then $A\uparrow A=A^c$. So $(A\uparrow A)\uparrow(B\uparrow B)=(A^c\cap B^c)^c=A\cup B$. Similarly, $(A\uparrow B)\uparrow(A\uparrow B)=((A\cap B)^c)^c=A\cap B$. And then you can get difference or whatever else, as expected. You can do the same thing with $(A\cup B)^c$.

  • $\begingroup$ You could mention that $(A \cup B)^C$ works as well. $\endgroup$ – Seamus Oct 12 '10 at 15:12
  • $\begingroup$ I did (my last sentence). $\endgroup$ – Paul VanKoughnett Oct 12 '10 at 16:52
  • 2
    $\begingroup$ How would you define the difference between a fun trick and a clever insight? $\endgroup$ – Leo Jun 19 '11 at 22:41

We could also write set difference in terms of intersection and complement as : $A \cap B = A - (A - B)$. (I do also prefer $A - B$ to $A \setminus B$)

This expression comes handy when you are dealing with cardinality.


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.