Is it decidable if two structures are isomorphic? Suppose that $S$ is a nested set and let $S_E$ be the set of "pure" elements (that is, elements of $S$ that are not sets). For example, if $S=\{a,\{a,b,c\}\}$ the "pure" elements of $S$ are $S_E=\{a,b,c\}$.
Two nested sets $S$ and $T$ are "hierarchically isomorphic" if there is a structure preserving bijection $f: S\rightarrow T$ between the "pure" elements. That is, the pure elements in $S$ distinguish the pure elements in $T$. For example, consider the sets
$S=\{x,\{y,\{z\}\}\}$ and $T=\{a,\{a,b\},\{c\}\}$
We can construct a structure preserving bijection $f: x\rightarrow a, y\rightarrow b, z\rightarrow c$. In fact, there are many structure preserving bijections. Another example is $f: x\rightarrow c, y\rightarrow a, z\rightarrow b$. Therefore $S$ and $T$ are isomorphic. Note that the structure of $S$ is equivalent to uniquely ordering $x,y$ and $z$.
Now, if we had
$T=\{a,\{a,b\},\{a,c\}\}$ instead of $\{a,\{a,b\},\{c\}\}$ we have no way of distinguishing between $b$ and $c$, but we must be able to distinguish between $b$ and $c$ for $T$ to be isomorphic to $S$, so in this case, $S$ and $T$ are non-isomorphic.
A more complicated example:
$S = \{a, \{b,c\}, \{b,\{a,d\}\}, \{c,\{a,e\}\}\}$
$T = \{v, \{x,y\}, \{w,z\}\}$
In the example above, we can uniquely identify $a \in S_E$ with $v \in T_E$. But $S$ contains two distinguishable pairs of elements (namely $\{b,c\}$ and $\{d,e\}$), while $T$ contains two indistinguishable pairs of elements, so the sets are non-isomorphic. However, if we replace $T$ as
$T = \{v, \{x,y\}, \{v,w,z\}\}$
we can now distinguish between the pairs $\{x,y\}$ and $\{w,z\}$, yielding a set isomorphic to $S$.

If we are given arbitrary sets $S$ and $T$, can we easily tell if $S$ and $T$ are isomorphic? Or is this generally undecidable?
Clearly we can check that $S_E$ and $T_E$ have the same cardinality. That much is known. The problem is that there are infinitely many types of nesting structures, so there is the possibility that the only way is to check all of them? Would some sort of tree-traversal algorithm work here?
 A: If we are dealing with hereditarily finite sets, and if the set of atoms (or, as you call them, “pure elements”) is decidable, then equality and membership are both decidable.
To show this, we use mutual recursion. To decide whether $a \in b$, we check to see whether $\exists c \in b (c = a)$. There are only finitely many $c \in b$, and all of them are structurally smaller than $b$. To decide whether $a = b$, we check whether $a$ and $b$ are both atoms and, if so, are the same atom. If $a$ and $b$ are both sets, we check whether $\forall c \in b (c \in a)$, which we can do since $b$ is finite and $c \in b$ is structurally smaller than $b$. And we also check whether $\forall c \in a (c \in b)$, which we can do by the same logic.
Once we start dealing with sets whose transitive closures are not finite, there is no reason to think anything should be decidable (or even that we can represent the relevant objects computationally).
If you want to do things efficiently, I would recommend starting by constructing the transitive closure of a set and sorting it in some canonical way, probably first sorting by rank. Sorting each rank one at a time seems like a decent strategy for coming up with a canonical representation.
