Open Problems in Mathematical Logic — Problem 49

Definitions and mathematical statement

Let $\omega=\{0,1,2,\ldots\}$, and equip $X=2^{\omega\times\omega}$ with the product topology, where $2=\{0,1\}$ is discrete. An element of $X$ codes a binary relation on $\omega$ by its characteristic function. The source does not explicitly specify its graph conventions. Under the usual convention of simple undirected graphs, put \[ \mathcal G=\{G\in X:(\forall m\in\omega)\ G(m,m)=0\text{ and }(\forall m,n\in\omega)\ G(m,n)=G(n,m)\}. \] For $G\in\mathcal G$, its complement $G^c$ has the same vertex set and is defined by \[ G^c(m,n)= \begin{cases} 1-G(m,n),&m\ne n,\\ 0,&m=n. \end{cases} \] Graphs $G,H\in\mathcal G$ are isomorphic, written $G\cong H$, if there is a bijection $p:\omega\to\omega$ such that $G(m,n)=H(p(m),p(n))$ for every $m,n\in\omega$. Thus define \[ S=\{G\in\mathcal G:G\cong G^c\} =\left\{G\in\mathcal G:\exists p:\omega\to\omega\text{ bijective }\ \forall m\ne n,\ G(m,n)=1-G(p(m),p(n))\right\}. \] The question attributed by the supplied source to Matt Foreman in 2021 is: Is $S$ a Borel subset of $X$? Here Borel means belonging to the $\sigma$-algebra generated by the product-open subsets of $X$. Since $\mathcal G$ is closed in $X$, asking for Borelness in $\mathcal G$ gives the equivalent question under these conventions. The simple undirected graph convention and the corresponding off-diagonal complement are explicit interpretations requiring confirmation against the source; the supplied wording does not resolve them.

Short English statement

The supplied question asks whether the countable graphs that are isomorphic to their own complements form a Borel set in the space of graph codes. It attributes the question to Matt Foreman in 2021. The displayed formulation uses an explicitly stated simple undirected graph convention, which requires source confirmation.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $801037$, exact source problem code catalogue entry, title Open Problems in Mathematical Logic --- Problem 49; collection: AMR Open Problem Lists. The registry labels the problem open; this is a supplied status, not an independently verified mathematical assessment.
• Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 49. Supplied source URL: https://arxiv.org/abs/2608.26628. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent access or verification.
• The supplied statement attributes the question to Matt Foreman in 2021. The registry's proposed_by and proposed_year fields instead identify Barmpalias, Gao et al. and 2026, respectively; these collection-level fields are retained separately from the statement's attribution. No direct reference to Foreman's original question is supplied.