Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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