7
$\begingroup$

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?

Thanks!

3 Answers 3

1

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.

6

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

  • 0
    You could mention that $(A \cup B)^C$ works as well.2010-10-12
  • 0
    I did (my last sentence).2010-10-12
  • 2
    How would you define the difference between a fun trick and a clever insight?2011-06-19
5

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.

  • 0
    Can difference be defined in terms of union and intersection?2010-10-11
  • 0
    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.2010-10-11
  • 0
    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.2010-10-11
  • 1
    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.2010-10-11