Coordinatization

2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

A coordinatization is some kind of a representation of a $\Sigma$-algebra $A$ by a $\Sigma$-algebra consisting of natural numbers, i.e. by a $\Sigma$-number-algebra. Contrary to a usual representation, however, not the elements of $A$ are encoded by elements of $C$ — this would be a Gödelization — but vice versa. Such kind of a representation is useful in situations, where preferably natural numbers are processed.

Formally, a coordinatization of a $\Sigma$-algebra $A$ is a pair $(C,\alpha)$ with $C$ as a $\Sigma$-number-algebra and $\alpha\colon C \longrightarrow A$ as a surjective $\Sigma$-algebra-morphism from $C$ onto $A$. Usually, $\alpha$ is chosen to be injective as well making $C$ and $A$ isomorphic. If $\alpha$ is not injective, $C/\equiv_\alpha$ can be considered instead. In such a case it holds $A\cong C/\equiv_\alpha$ whereby $n\equiv_\alpha m :\Longleftrightarrow \alpha(n)=\alpha(m)$ for $n,m\in C_s$, $s\in S$ [W90].

Using a coordinatization $(C,\alpha)$, the notions of computability (and other areas of theoretical computer science) can be transferred to $\Sigma$-algebras. Accordingly, a coordinatization is called computable resp. semicomputable resp. co-semicomputable, if $C$ (and $\equiv_s$ for all $s\in S$) is recursive resp. recursively enumerable resp. co-recursively enumerable. A $\Sigma$-algebra is computable resp. semicomputable resp. co-semicomputable, if it exists a computable resp. semicomputable resp. co-semicomputable coordinatization of $A$. An algebraic specification is called computable resp. semicomputable resp. co-semicomputable, if it exists a computable resp. semicomputable resp. co-semicomputable $\Sigma$-algebra [W90].

The properties of a computable $\Sigma$-algebra are summarized in the following theorem: A computable $\Sigma$-algebra is isomorphic to a recursive $\Sigma$-number-algebra $C$ with carrier sets $C_s$, $s\in S$, equal to $\mathbb{N}$ or $\{1,\ldots,n_s\}\subseteq \mathbb{N}$ [W90].

Sometimes, one has to compare two coordinatizations $(C_1,\alpha_1)$, $(C_2,\alpha_2)$ of a $\Sigma$-algebra $A$. Then the following notion may be useful. $\alpha_1$ is said to recursively reduce to $\alpha_2$, if it exists a recursive mapping $f\colon C_1\longrightarrow C_2$ such that $\alpha_1 =\alpha_2 \circ f$ [W90].

References

[W90]

M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990