What is an $\in$-isomorphim?

Question

Context of the question:

Robert Gandy (Principles for mechanism, The Kleene Symposium (1978) p. 128) and Wilfried Sieg (Calculations by man and machine, p. 3; Church without dogma, New computational paradgims (2005) p. 147) use the notion of $\in$-isomorphism.

Here is an example of a passage in which this notion occurs: "We consider pairs $(D,F)$ where $D$ is a class of states and $F$ is an operation from $D$ to $D$ (...). States are finite objects and are represented by non-empty hereditarily finite sets over an infinite set of atoms. (...) Any $\in$-isomorphic set can replace a given one in this (...) role, and so we consider structural classes of $D$, i.e., classes of states that are closed under $\in$-isomorphisms." (Sieg, Church without dogma, p. 147)

The question:

What is an $\in$-isomorphism in this context? Is it an isomorphism $f$ that respects set-theoretic inclusion in the sense that if $x\in X$, then $f(x)\in X$?

Many thanks for your help. I really appreciate.

Answer 1

Let $A,B$ be sets (or classes). An $\in$-isomorphism from $A$ to $B$ is a bijective map $$ f \colon A \to B $$ such that for all $x,y \in A$ $$ x \in y \iff f(x) \in f(y). $$

The question now is, why one would bother about this notion. More precisely, what does the author mean with the following:

Any $\in$-isomorphic set can replace a given one in this (...) role, and so we consider structural classes of $D$, i.e., classes of states that are closed under $\in$-isomorphisms.

It may sound confusing, but his intention is really simple. (Even though I think that $\in$-isomorphisms might not be an ideal choice. But I'd need more context to be certain about that.) He doesn't want to distinguish structures that are 'essentially the same'. Take for example $A = \{* \}$ and $B = \{ \dagger \}$ for $* \neq \dagger*$. Both structures are defined by the fact that they have a unique element and there is not much else to them. In fact, $$ f \colon \{ * \} \to \{ \dagger \}, * \mapsto \dagger $$ is an $\in$-isomorphism. So they should be treated as equal (in this context).

Another example: Let $\mathcal A = \{a_n \mid n \in \mathbb N \}$ be a set of axioms, let $A = \mathcal P(\{a_1, \ldots, a_{100} \})$ and let $B = \mathcal P(\{a_{101}, \ldots, a_{200} \})$. There is an $\in$-isomorphism between $A$ and $B$ induced by $$ f^* \colon \{a_{1}, \ldots, a_{100} \} \to \{ a_{101}, \ldots, a_{200} \}, a_n \mapsto a_{n + 100}. $$ So, again, $A$ and $B$ are essentially the same and thus should be treated as equals.

---

edit: Btw. the author says that $D$ is a class of states if

1. $D$ is a set,
2. $D$ contains only hereditarily finite sets, i.e. any set $x \in D$ is finite and any $y \in x$ is finite and any $z \in y$ is finite...
3. $D$ is closed under $\in$-isomorphism: If $A \in D$, $B$ is hereditarily finite and there is an $\in$-isomorphism $f \colon A \to B$, then $B \in D$.