Coordinatization
2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]
A coordinatization is some kind of a representation of a -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 |
Coordinatization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Coordinatization&oldid=29686