What persistent data structure for a set of partially ordered elements? I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.

One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.

Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so).
More precisely, the operations I will need to perform are as follows:


Remove an element from the antichain;
Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.


I can also bound every element by two integers, so that if I know that $i_1 &lt; a &lt; i_2$ and $i_3 &lt; b &lt; i_4$, then knowing $i_2 &lt; i_3$ instantly gives me $a &lt; b$. Of course, $i_2 \not&lt; i_3$ does not mean $a \not &lt; b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.
The paper "Sorting and Selection in PoSets" by Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 which describes a dynamic representation of PoSets based on antichains.

You might also be interested in the paper "Succinct Posets" by Munro, Nicholson, 2012 recently released on Arxiv and in the bibliography therein. Their data-structure is static but I assume that the next step is to have a dynamical data-structure.