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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's let $\def\OP#1#2{\left\langle#1,#2\right\rangle}\OP xy$ represent the set $\{\{x\},\{x,y\}\}$ as is usual, per Kuratowski. Then:

$$ \begin{eqnarray} \OP{\OP ab}c & = & \{\{\{\{a\}, \{a,b\}\}\}, \{\{\{a\}, \{a, b\}\}, c\}\} \\ \OP x{\OP yz} & = & \{\{x\}, \{x, \{\{y\}, \{y,z\}\}\}\} \end{eqnarray} $$

I would like to unify these two equations to produce a set of relations on $a,b,c,x,y,z$ that give the most general conditions for which $ \OP{\OP ab}c = \OP x{\OP yz}$.

The unification algorithm I know works on expressions. Applying it to $ \OP{\OP ab}c = \OP x{\OP yz}$ directly gives $x=\OP ab, c=\OP yz$. This is correct, but may not be the most general possible set of conditions.

I can also abbreviate $\{x\}$ as $Sx$ and $\{y,z\}$ as $Dxy$, so that $\OP xy = \{\{x\}, \{x, y\}\} = DSxDxy$. Then the two set expressions I want to unify become $DSDSaDabDDSaDabc$ and $DSxDxDSyDyz$. I can unify these; the result is the same as in the previous paragraph.

But this may not be fully general, because it fails to capture the fact that for sets, $\{a, a\} = \{a\}$. Abbreviating $\{x\}$ as $Sx$ and $\{y,z\}$ as $Dxy$, and attempting to unify $\{x\}$ and $\{y, z\}$ with this method fails outright. But I want it to succeed and to yield the equations $x=y, x=z$.

How can I fix either the unification algorithm or my representation of the expressions to allow $\{x\}$ to unify with $\{y, z\}$?

I can make some progress on this particular problem by representing $\{x\}$ as $Dxx$. Then $\{x\}$ unifies with $\{y,z\}$ because $Dxx$ unifies with $Dyz$ giving $x=y, x=z$ as I wanted.

But this is not quite enough either, because it doesn't understand that $\{x, y\} = \{y, x\}$. I want the unification of $\{x, y\}$ with $\{a, b\}$ to give me not simply $x=a, y=b$ but $[x=a, y=b] \lor [x=b, y=a]$.

The problem grows worse if any of the sets have more than two elements. There are several possible ways in which $\{x, y\}$ could unify with $\{a,b,c\}$. For example, we might have $x=a=c, y=b$, or $x=c, y=a=b$.

Is there a modified version of the unification algorithm that can handle unification of sets in this way?

share|cite|improve this question

When the ordered pair $\langle x, y \rangle$ is defined as the set $\{\{x\}, \{x, y\}\}$, your original unification algorithm is correct and gives the most general conditions for equality; the fact that $\{ x ,x \}=\{x\}$ is already accounted for.

In particular, $\langle x, y \rangle$ always contains exactly one singleton element, $\{ x \}$, containing the first half of the ordered pair. If it contains a second element, that element is $\{x, y\}$ (with $x\neq y$), from which the second half of the pair can be read off (since we already know the first half). If it does not contain a second element, then the second half of the ordered pair is the same as the first. Since the first and second halves of each ordered pair can be deduced from its corresponding set, $\langle a, b \rangle = \langle c, d \rangle$ if and only if $a=b$ and $c=d$.

share|cite|improve this answer
I don't understand how this addresses my questions, which are highlighted in gray. – MJD Jul 6 '12 at 0:37
@MarkDominus: It doesn't; it addresses what I read as the motivation for your questions, which was your assertion that the unification of ordered pairs you described "may not be the most general possible set of conditions." – mjqxxxx Jul 6 '12 at 2:14
I understand. Thanks. ${}{}$ – MJD Jul 8 '12 at 1:38

Your Answer


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.