5. 𝖦𝗋𝖺𝗉𝗁𝖨𝗌𝗈 is analytic

problem

Show that the set

$$\mathsf{GraphIso} ≔ \{(G,H)∈\mathsf{Graphs}×\mathsf{Graphs} : \text{\(G\) and \(H\) are isomorphic}\}$$

is analytic.

proof

Let

$$B = \{(G,H,ϕ)∈\mathsf{Graphs}×\mathsf{Graphs}×ℕ^ℕ : \text{\(ϕ\) is an isomorphism from \(G\) to \(H\)}\}.$$

Expanding the condition for a triple $(G,H,ϕ)$ to be in $B$:

• $ϕ$ is a bijection:
  • $ϕ$ is injective: for all $i≠j∈ℕ$, we have $ϕ(i)≠ϕ(j)$.
  • $ϕ$ is surjective: for all $i∈ℕ$, there exists $j∈ℕ$ so that $ϕ(j)=i$.
• $ϕ$ is a graph homomorphism from $G$ to $H$: for all $i≠j∈ℕ$, $\{ϕ(i),ϕ(j)\}$ is an edge in $H$ if and only if $\{i,j\}$ is an edge in $G$.

Observe that the quantifiers for each condition range over countable sets. So $B$ is Borel, and $\mathsf{GraphIso}$ is the projection of $B$ on to the first two components and therefore analytic.