Namespaces
Variants
Actions

Coordinatization

From Encyclopedia of Mathematics
Jump to: navigation, search

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
How to Cite This Entry:
Coordinatization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Coordinatization&oldid=29686

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners in accordance with our Privacy Policy. You can manage your preferences in 'Manage Cookies'.