Take a model $\mathfrak M$ for NBG set theory, and interpret your new symbols as:
- $a
- $a\mathrel R b$ iff $a\in b$ or $b\in a$.
Then $(|\mathfrak M|,{<},R)$ is automatically a model for your theory, and $a\in b$ exactly when $(a
Therefore you can express any sentence in the language of set theory in your language by representing each $a\in b$ as $(a
Edit: As mjqxxxx points out, simply having $<$ is enough to establish undecidability. One can see this by a slightly more involved translation from the language of set theory to the language of partial orders:
In the other direction, if we start from a model of set theory, every set/class becomes an element of the partial order, and every pair $(a\in b)$ in the membership relation becomes a link element. (An element that represents a set is not a "link" because every set is a member of more than one other set, so the element has more than one immediate successor, and an element that represents a proper class is not a "link" because it will have no successors at all).
Edit even more: The above constructions depend on the fact that the axioms of set theory guarantee that $\in$ is acyclic (and thus its transitive closure is a strict partial order). However, using more of the same techniques one can also represent an arbitrary predicate calculus as statements about a partial order. Then we don't need to depend on specific knowledge of axiomatic set theory, only that predicate calculus in general is undecidable.