How to code a model by a real number (an infinite sequence of bits)?

Question

The proof of Lemma $2.10$ in the paper “Feedback computability on Cantor space” mentions “any fixed standard way of coding a model by a real.”

What does it mean? What can be an example of how to code a model by a real?

Answer 1

For simplicity, consider the case of countably infinite directed graphs, where "directed graph" just means "$\{E\}$-structure" for a binary relation symbol $E$.

To each $X\subseteq\mathbb{N}^2$ we can associate a countably infinite directed graph $\mathcal{A}_X$ as follows: the vertices of $\mathcal{A}_X$ are the natural numbers, and $\mathcal{A}_X$ has an edge between $m$ and $n$ iff $(m,n)\in X$. Every countably infinite directed graph is isomorphic to some $\mathcal{A}_X$. Now if we fix a bijection $b: \mathbb{N}\rightarrow\mathbb{N}^2$ we get a map from sets of naturals to countably infinite directed graphs which is surjective up to isomorphism. It's in this sense that we can code countably infinite directed graphs by reals: each real determines a countably infinite directed graph, and no countably infinite directed graph is unrepresented.

More generally, this same idea works for representing countable(-or-finite) structures in arbitrary countable languages: to each countable language $\Sigma$ we can whip up a construction assigning to each real $r$ a countable $\Sigma$-structure $Struc(r)$ such that every countable $\Sigma$-structure is isomorphic to some $Struc(r)$.