# Symmetric set difference is equivalent to proper set difference and what?

I would like to see if some set operations can be represented by some other set operations.

proper set difference + finite union $\implies$ symmetric set difference $\implies$ proper set difference + finite disjoint union

The first $\implies$: $A$ symminus $B$ = [($A$ $\cup$ $B$) properminus $A$] $\cup$ [($A$ $\cup$ $B$) properminus $B$]

The second $\implies$ is trivial.

So I was wondering "symmetric set difference $\iff$ proper set difference + what set operation"?

Note $A$ properminus $B$ is defined as $A \setminus B$ for $B \subseteq A$.

Thanks and regards!

-
What do you mean by $+$, $\Rightarrow$ and $\Leftrightarrow$ here? –  Rahul Jan 6 '13 at 19:51
@RahulNarain: I would like to see if some set operations can be represented by some other set operations. –  Tim Jan 6 '13 at 19:56
To make sure that I understand: when you write $\oplus+\otimes\implies\circ$ you mean that $\circ$ can be defined in terms of $\oplus$ and $\otimes$? –  Brian M. Scott Jan 6 '13 at 20:08
@BrianM.Scott: yes! –  Tim Jan 6 '13 at 20:09
Ah, and by $\ominus \Rightarrow \setminus + \sqcup$ you mean both $\ominus \Rightarrow \setminus$ and $\ominus \Rightarrow \sqcup$ independently. –  Rahul Jan 6 '13 at 20:25

I think there is no non-trivial way to do what the question is asking.

Let's say that a set of partial (possibly total) binary operations $S$ is complete for the symmetric difference operation $\triangle$ if

• every operation in $S$ is a (possibly trivial) restriction of some composition of copies of $\triangle$, and

• for every pair of sets $(A,B)$ there is a partial operation $\cdot$ that is a composition of partial operations in $S$ and has the property that $A \cdot B$ is defined and is equal to $A \mathbin{\triangle} B$. (Note that is weaker than saying that $S$ itself is a composition of partial operations in $S$, which is impossible if none of the operations in $S$ is total.)

Even with this weak version of the definition, the only sets $S$ that are complete for $\triangle$ are trivial, in a sense that we will make precise below. Note that by the first clause of the definition, and the fact that $\triangle$ is commutative, associative, and satisfies $A \mathbin{\triangle} A = \emptyset$, every partial operation $\cdot$ in $S$ is the restriction of one of the four following total operations:

• The constant binary operation given by $A \cdot B = \emptyset$,

• The projection given by $A \cdot B = A$,

• The projection given by $A \cdot B = B$, and

• The symmetric difference operation $\triangle$ itself.

The first three operations do not help us form any additional binary operations under composition, so we consider them to be trivial, and we assume that $S$ consists only of restrictions of $\triangle$.

A trivial way to get a complete set $S$ is for the union of the domains of the partial operations in $S$ to consist of all pairs $(A,B)$: for example, the proper set difference operation "$\setminus$" as defined in the question is simply the restriction of $\triangle$ to the domain $\{(A,B) : B \subseteq A\}$, so we could let $S = \{\setminus, \cdot\}$ where $\cdot$ is the restriction of $\triangle$ to the complementary domain $\{(A,B) : B \not \subseteq A\}$. More generally, we could weaken the triviality requirement to consider the domains of the partial operations in $S$ and their reverses; for example, this requirement would be satisfied by the set $S = \{\setminus, \cdot\}$ where $\cdot$ now denotes the restriction of $\triangle$ to the domain $\{(A,B) : A \not \subseteq B\}$.

However, every complete set is trivial in this way. Suppose that some pair $(A,B)$ is not in the domain of any partial operation $\cdot$ in $S$, and neither is the reversed pair $(B,A)$. Because the partial operations in $S$ are all binary, it is not hard to show that the pairs $(A,B)$ and $(B,A)$ cannot be in the domain of any composition of elements of $S$ either, so there is no way to get the symmetric difference $A \mathbin{\triangle} B$.

-