View source for Gödelization

{{MSC|68P05}} 

{{TEX|done}}

A <i>Gödelization</i> or <i>Gödel numbering</i> of a [[Sigma-algebra (Computer Science)|$\Sigma$-algebra]] $A$ is a pair $(C,\beta)$ with $C$ as a recursive $\Sigma$-number-algebra and $\beta\colon A \longrightarrow C$ as a $\Sigma$-algebra-morphism from $A$ onto $C$. As usual, $\Sigma$ designates a [[Signature (Computer Science)|signature]]. A Gödelization could be understood as encoding of the elements of $A$ by natural numbers {{Cite|W90}}.


Gödelizations with bijective mapping $\beta$ are of special interest.  They are the counterpart of a certain bijective [[coordinatisation|coordinatisation]] mapping $\nu\colon C \longrightarrow A$.  More precisely, $\beta=\nu^{-1}$ is the inverse of $\nu$ in this case.  For a sensible signature $\Sigma$ and a term-generated $\Sigma$-algebra $A$, such a coordinatization with bijective mapping $\nu$ always exists. Taking together, every Gödelization induces canonically a corresponding coordinatization and vice versa.

The correspondence between Gödelization and coordinatization can be extended to [[Sigma-Congruence|congruences]] defined on $A$ and $C$.  A congruence $\sim^\beta \subseteq A \times A$ induces a congruence $\sim^\nu \subseteq C \times C$ and vice versa via $\beta$ resp. $\nu$ {{Cite|W90}}.

As one can easily see, a Gödelization with bijective mapping $\beta$ does not always exist. As a simple counterexample take a $\Sigma$-algebra $A$ with an uncountable number of elements.

==References==

* {{Ref|W90}} M. Wirsing, "Algebraic Specification", in J. van Leeuwen, "Handbook of Theoretical Computer Science", Elsevier 1990 {{ZBL|0900.68309}}