I am interested in the following decision problem:

Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic.

The question is: is this problem decidable at all?

(A graph $G$ is represented by a triple of formulas $(\phi_{\text{dom}},\phi_{\sim},\phi_E)$ describing the interpretation in the usual way (namely, $\phi_{\text{dom}}$ is a formula with $d$ free variables for some $d\in\mathbb N$, defining a set $V\subset \mathbb N^d$, $\phi_{E}$ has $2d$ free variables and defines a symmetric binary relation $E\subset V\times V\subset \mathbb N^{2d}$, and $\phi_\sim$ is a formula with $2d$ free variables defining a binary relation $\sim\subset V\times V$ which is a congruence of the graph $(V,E)$ (i.e. the edge relation is invariant under $\sim$). The graph $G$ is defined as the quotient graph $(V,E)/\sim$ with vertices $V/\sim$ and edges $\{[v],[w]\}$ such that $(v,w)\in E$.)

The graphs $G,H$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence $\phi$ which distinguishes $G$ from $H$. Since it can be effectively tested whether $\phi$ holds in $G$ and in $H$, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these graphs.

These graphs are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to graphs which interpret in other structures with decidable first order theory, e.g., the dense linear order.

Edit 1: I modified the question so that it talks about graphs rather than arbitrary structures. Those two questions are easily seen to be equivalent.

Edit 2: I wrote down some preliminary observations concerning this problem here: http://atoms.mimuw.edu.pl/?p=1063

I am interested in the following decision problem:

Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic.

The question is: is this problem decidable at all?

(A graph $G$ is represented by a triple of formulas $(\phi_{\text{dom}},\phi_{\sim},\phi_E)$ describing the interpretation in the usual way (namely, $\phi_{\text{dom}}$ is a formula with $d$ free variables for some $d\in\mathbb N$, defining a set $V\subset \mathbb N^d$, $\phi_{E}$ has $2d$ free variables and defines a symmetric binary relation $E\subset V\times V\subset \mathbb N^{2d}$, and $\phi_\sim$ is a formula with $2d$ free variables defining a binary relation $\sim\subset V\times V$ which is a congruence of the graph $(V,E)$ (i.e. the edge relation is invariant under $\sim$). The graph $G$ is defined as the quotient graph $(V,E)/\sim$ with vertices $V/\sim$ and edges $\{[v],[w]\}$ such that $(v,w)\in E$.)

The graphs $G,H$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence $\phi$ which distinguishes $G$ from $H$. Since it can be effectively tested whether $\phi$ holds in $G$ and in $H$, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these graphs.

These graphs are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to graphs which interpret in other structures with decidable first order theory, e.g., the dense linear order.

Edit 1: I modified the question so that it talks about graphs rather than arbitrary structures. Those two questions are easily seen to be equivalent.

Edit 2: I wrote down some preliminary observations concerning this problem here: http://atoms.mimuw.edu.pl/?p=1063

I am interested in the following decision problem:

Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$ are isomorphic.

The question is: is this problem decidable at all?

(A structure $A=(Dom(A),R_1,...,R_k)$ is represented by a tuple of formulas $(φ_{\sim},φ_1,...,φ_k)$ describing the interpretation in the expected way (namely, $φ_{\sim}$ defines an equivalence relation $\sim$ on a subset $V⊆\mathbb N^d$ for some $d\ge 0$, $Dom(A)=V/{\sim}$ is the set of its equivalence classes, and $φ_i$ is a formula describing the pullback of $R_i$ under the quotient mapping $V\rightarrow Dom(A)$; $φ_i$ has $n\cdot d$ free variables if $R_i$ has arity $n$.)

The structures $A,B$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence φ which distinguishes A from B. Since it can be effectively tested whether φ holds in A and in B, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these structures.

These structures are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to structures which interpret in other structures with decidable first order theory, e.g., the dense linear order.

I am interested in the following decision problem:

Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic.

The question is: is this problem decidable at all?

(A graph $G$ is represented by a triple of formulas $(\phi_{\text{dom}},\phi_{\sim},\phi_E)$ describing the interpretation in the usual way (namely, $\phi_{\text{dom}}$ is a formula with $d$ free variables for some $d\in\mathbb N$, defining a set $V\subset \mathbb N^d$, $\phi_{E}$ has $2d$ free variables and defines a symmetric binary relation $E\subset V\times V\subset \mathbb N^{2d}$, and $\phi_\sim$ is a formula with $2d$ free variables defining a binary relation $\sim\subset V\times V$ which is a congruence of the graph $(V,E)$ (i.e. the edge relation is invariant under $\sim$). The graph $G$ is defined as the quotient graph $(V,E)/\sim$ with vertices $V/\sim$ and edges $\{[v],[w]\}$ such that $(v,w)\in E$.)

The graphs $G,H$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence $\phi$ which distinguishes $G$ from $H$. Since it can be effectively tested whether $\phi$ holds in $G$ and in $H$, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these graphs.

These graphs are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to graphs which interpret in other structures with decidable first order theory, e.g., the dense linear order.

Edit 1: I modified the question so that it talks about graphs rather than arbitrary structures. Those two questions are easily seen to be equivalent.

Edit 2: I wrote down some preliminary observations concerning this problem here: http://atoms.mimuw.edu.pl/?p=1063

I am interested in the following decision problem:

Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$ are isomorphic.

(A structure $A=(Dom(A),R_1,...,R_k)$ is represented by a tuple of formulas $(φ_{\sim},φ_1,...,φ_k)$ describing the interpretation in the expected way (namely, $φ_{\sim}$ defines an equivalence relation $\sim$ on a subset $V⊆\mathbb N^d$ for some $d\ge 0$, $Dom(A)=V/{\sim}$ is the set of its equivalence classes, and $φ_i$ is a formula describing the pullback of $R_i$ under the quotient mapping $V\rightarrow Dom(A)$; $φ_i$ has $n\cdot d$ free variables if $R_i$ has arity $n$.)

The structures $A,B$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence φ which distinguishes A from B. Since it can be effectively tested whether φ holds in A and in B, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these structures.

These structures are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to structures which interpret in other structures with decidable first order theory, e.g., the dense linear order.

I am interested in the following decision problem:

Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$ are isomorphic.

The question is: is this problem decidable at all?

(A structure $A=(Dom(A),R_1,...,R_k)$ is represented by a tuple of formulas $(φ_{\sim},φ_1,...,φ_k)$ describing the interpretation in the expected way (namely, $φ_{\sim}$ defines an equivalence relation $\sim$ on a subset $V⊆\mathbb N^d$ for some $d\ge 0$, $Dom(A)=V/{\sim}$ is the set of its equivalence classes, and $φ_i$ is a formula describing the pullback of $R_i$ under the quotient mapping $V\rightarrow Dom(A)$; $φ_i$ has $n\cdot d$ free variables if $R_i$ has arity $n$.)

The structures $A,B$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence φ which distinguishes A from B. Since it can be effectively tested whether φ holds in A and in B, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these structures.

These structures are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to structures which interpret in other structures with decidable first order theory, e.g., the dense linear order.