COMPUTABLE PRESENTATIONS OF C*-ALGEBRAS

Abstract

We initiate the study of computable presentations of real and complex C*-algebras under the program of effective metric structure theory. With the group situation as a model, we develop corresponding notions of recursive presentations and word problems for C*-algebras, and show some analogous results hold in this setting. Famously, every finitely generated group with a computable presentation is computably categorical, but we provide a counterexample in the case of C*-algebras. On the other hand, we show every finite-dimensional C*-algebra is computably categorical.

1 Introduction

With his 1882 paper [11], Dyck began the study of presentations of groups in terms of generators and relations, and in doing so laid the foundation for what would become the field of combinatorial group theory. By the mid-twentieth century, mathematical logic had been incorporated into the field to incredible success. A success that was, perhaps, most exemplified by the independently proven result of Boone [3] and Novikov [39] of the existence of finitely presented groups with unsolvable word problem. In that same era, defining work by Fröhlich and Shepherdson in effective field theory [17] and by Mal’tsev in effective algebra [27, 28] established what would later be known as computable structure theory, i.e., the study of the relationship between computability theoretic complexity and mathematical structures. Although implicit in the 1989 text [40] by Pour-El and Richards, it is only within the last decade that a program has emerged to extend computable structure theory to the uncountable structures one might encounter in analysis. Now known as effective metric structure theory, the program truly began with the work of Melkinov and Nies [36] on the classification of compact metric spaces and the work of Melnikov [34] on the categoricity of various metric spaces. Our goal is to apply perspectives and techniques from both combinatorial group theory and effective metric structure theory to C*-algebras.

Complex C*-algebras have become a fixture of modern mathematics, and while real C*-algebras have not received the same attention, they represent a natural class of objects for consideration from the viewpoint of computability theory. Importantly, the classes of real and complex C*-algebras share similarities with the class of groups. In particular, C*-algebras can be studied by their presentations in terms of generators and relations, C*-algebras are principally determined by their algebraic structure, and the universal contraction C*-algebras, while not truly free objects, can fulfill some of the same roles as free groups. Furthermore, any discrete group has corresponding universal and reduced group C*-algebras, so theorems for groups can often serve as a bound on theorems for C*-algebras.

Over the last decade, effective metric structure theory has been developed in the context of metric spaces [15, 18], Polish spaces [1, 19, 20], $\ell ^p$ spaces [30–32], and $L^p$ spaces [5]. This paper fills a remaining hole by initiating the study of real and complex C*-algebras under the program of effective metric structure theory.

As combinatorial group theory and computable structure theory introduce conflicting terminology, we follow [33] in referring to presentations of groups in terms of c.e. generators and c.e. relations as c.e. presentations instead of recursive presentations. In Section 3, we adapt c.e. presentations and word problems from groups to C*-algebras and develop the basic theory. Specifically, we give characterizations for when c.e. presentations are actually computable in the sense of computable structure theory, and show that the computability theoretic properties of a presentation can be defined in terms of the word problem. We also investigate the connection between computable presentations of groups and properties of the word problems of the corresponding universal and reduced group C*-algebras. In Section 4, we describe the relationship between real C*-algebras and their complexifications. Consequently, we are able to transfer some already established results about ${C({X};{\mathbb {R}})}$ as a real Banach space or algebra to ${C({X};{\mathbb {C}})}$ as a complex C*-algebra. Of particular importance, using a result of Melnikov and Ng [35], we find that, as a complex C*-algebra, ${C({[0,1]};{\mathbb {C}})}$ is finitely generated and admits a computable presentation but is not computably categorical. In Section 5, we show, on the other hand, that every finite-dimensional C*-algebra is computably categorical.

2 Preliminaries

2.1 C*-algebras

Although, historically, real C*-algebras were rarely studied in their own right, interest in real C*-algebras has grown as it has become clear that the theory of real C*-algebras can not be subsumed under the theory of complex C*-algebras (see [37] for an overview of some differences) and as new applications of real C*-algebras have been found (see [42] for an overview of some applications). For our purposes, the framework of real C*-algebras also provides a crucial link between complex C*-algebras and previously established results for real Banach algebras. In this section, we provide an introduction to real and complex C*-algebras. More information can be found on real C*-algebras in [24] or [43], and on complex C*-algebras in [10] or [38].

Throughout the paper, we let $\mathbb {K}$ denote the real numbers $\mathbb {R}$ or the complex numbers $\mathbb {C}$ .

Definition 2.1. A C*-algebra over $\mathbb {K}$ is a Banach *-algebra over $\mathbb {K}$ which is isometrically *-isomorphic to a norm-closed *-subalgebra of the set of bounded operators ${B({\mathcal {H}};{\mathbb {K}})} $ on a Hilbert space $\mathcal {H}$ over $\mathbb {K}$ .

We have the following abstract characterizations. A complex Banach *-algebra A is a complex C*-algebra if and only if it satisfies the C*-axiom $\left \lVert x\right \rVert ^{2} = \left \lVert x^{*}x\right \rVert $ for all $x \in A$ . In the case of real C*-algebras, however, this is no longer enough. A real Banach *-algebra A is a real C*-algebra if and only if $\left \lVert x\right \rVert ^{2} \leq \left \lVert x^{*}x + y^{*}y\right \rVert $ for all $x,y \in A$ .

If A is a unital complex C*-algebra and $x \in A$ , then the spectrum $\sigma _A(x)$ of x in A is defined to be the set $\{\lambda \in {\mathbb {C}} {\colon \,} \lambda 1 - x \text { is not invertible}\}$ , where $1$ is the unit in A. For any complex C*-algebra A, there is a unique unital complex C*-algebra $\tilde {A}$ , called the unitization of A, such that A is an ideal of $\tilde {A}$ and $\tilde {A} / A \cong \mathbb {C}$ . If A is a nonunital complex C*-algebra and $x \in A$ , then the spectrum $\sigma _A(x)$ of x in A is defined to be $\sigma _{\tilde {A}}(x)$ where $\tilde {A}$ is the unitization of A.

The primary tool connecting real and complex C*-algebras is that of complexification.

Definition 2.2. Given a real C*-algebra A, its complexification $A_{c}$ is the complex C*-algebra $A \otimes _{\mathbb {R}} \mathbb {C} = A + iA$ equipped with the natural complex *-algebra operations and the induced C*-norm.

Note $A_{c}$ truly is a complexification of A. Namely, the norm on $A_{c}$ extends the norm on A, and $\left \lVert x + iy\right \rVert = \left \lVert x - iy\right \rVert $ for all $x,y \in A$ . We also have the useful consequence that $\max (\left \lVert x\right \rVert , \left \lVert y\right \rVert ) \leq \left \lVert x + iy\right \rVert $ for all $x,y \in A$ .

Through the complexification, we can define the spectrum of elements in a real C*-algebra. If A is a real C*-algebra and $x \in A$ , then the spectrum $\sigma _{A}(x)$ of x in A is defined to be the spectrum $\sigma _{A_{c}}(x)$ of x in $A_{c}$ . When A is unital, we can further characterize the spectrum by noting that $a + ib \in \sigma _{A}(x)$ if and only if $(x - a)^{2} + b^{2}$ is not invertible in A, for $a,b \in \mathbb {R}$ .

Definition 2.3. Given a complex C*-algebra A, a conjugation on A is a conjugate-linear map $\tau : A \to A$ such that $\tau (\tau (x)) = x$ , $\tau (xy) = \tau (x)\tau (y)$ , and $\tau (x^{*}) = \tau (x)^{*}$ for $x,y \in A$ .

If A is a real C*-algebra, then there is a natural conjugation $\tau $ on $A_{c}$ given by $\tau (x + iy) = x - iy$ for $x,y \in A$ . We can recover A from $\tau $ as the set of fixed points of $\tau $ , $\{z \in A_c {\colon \,} \tau (z) = z\}$ , with the induced operations and norm. In the same way, every conjugation $\tau $ on a complex C*-algebra A determines a real C*-algebra.

The natural maps between C*-algebras are those that preserve the *-algebraic structure, namely *-homomorphisms. If $\psi : A \to B$ is a real *-homomorphism between real C*-algebras, then $\psi $ extends to a conjugation-preserving complex *-homomorphism $\psi _{c} : A_{c} \to B_{c}$ given by $\psi _{c}(x + iy) = \psi (x) + i\psi (y)$ for $x,y \in A$ . Furthermore, the kernel of $\psi _{c}$ is the complexification of the kernel of $\psi $ . Note any *-homomorphism between C*-algebras is necessarily norm-decreasing. In particular, any *-isomorphism preserves the norm.

Let A be a C*-algebra over $\mathbb {K}$ . We say an element $x \in A$ is self-adjoint if $x^{*} = x$ , and skew-adjoint if $x^{*} = -x$ . Every $z \in A$ can be uniquely expressed as $x + y$ where x is self-adjoint and y is skew-adjoint, just let $x = \frac {1}{2}(z + z^{*})$ and $y = \frac {1}{2}(z - z^{*})$ . If A is a complex C*-algebra, then z can also be uniquely expressed as $a + ib$ where a and b are both self-adjoint, just let $a = \frac {1}{2}(z + z^{*})$ and $b = \frac {1}{2i}(z - z^{*})$ .

In both the real and complex cases, we have a complete classification of the finite-dimensional C*-algebras.

Fact 2.4. Every finite-dimensional complex C*-algebra is isomorphic to a direct sum of matrix algebras $\bigoplus _{i=1}^k M_{n_i}(\mathbb {C})$ for some $n_1,\ldots ,n_k \in \mathbb {N}$ .

We denote the ring of quaternions by $\mathbb {H}$ .

Fact 2.5. Every finite-dimensional real C*-algebra is isomorphic to a direct sum of matrix algebras $\bigoplus _{i=1}^k M_{n_i}(\mathbb {D}_i)$ for some $n_1,\ldots ,n_k \in \mathbb {N}$ , where each $\mathbb {D}_i$ is $\mathbb {R}$ , $\mathbb {C}$ , or $\mathbb {H}$ .

We also have a complete classification of the abelian C*-algebras.

Fact 2.6. Every abelian complex C*-algebra A is isomorphic to ${C_0(X;{\mathbb {C}})}$ , the space of continuous complex-valued functions on X vanishing at infinity, where X is the set of nonzero complex *-homomorphisms from A to $\mathbb {C}$ .

If X is a locally compact Hausdorff space and $\theta : X \to X$ is a homeomorphism such that $\theta (\theta (x)) = x$ for $x \in X$ , then we let

$$\begin{align*}C_0 (X,\theta) = \{f \in {C_0(X;{\mathbb{C}})} {\colon\,} \overline{f(\theta(x))} = f(x) \text{ for } x \in X\}. \end{align*}$$

Fact 2.7. Every abelian real C*-algebra A is isomorphic to ${C_0(X, \theta )}$ , where X is the set of nonzero real *-homomorphisms from A to $\mathbb {C}$ , and $\theta : X \to X$ is defined by $\theta (x) = \overline {x}$ .

Universal C*-algebras are often difficult to realize concretely, but as we will see further on, their definition in terms of generators and relations grants access to an effective perspective.

Let $\mathcal {G}$ be a set of noncommuting indeterminates, which we call generators. Let $\mathcal {R}$ be a set of relations in $\mathcal {G}$ ; specifically, relations of the form $\left \lVert p(x_{1},\ldots ,x_{n})\right \rVert \leq a$ where p is a *-polynomial over $\mathbb {K}$ in n noncommuting variables with no constant term, $x_{1},\ldots ,x_{n}$ belong to $\mathcal {G}$ , and a is a nonnegative real number. We also require that for every generator $x \in \mathcal {G}$ there is a relation of the form $\left \lVert x\right \rVert \leq M$ in $\mathcal {R}$ . We will often follow the convention of writing $p = q$ for the relation $\left \lVert p - q\right \rVert \leq 0$ . A representation of $(\mathcal {G}, \mathcal {R})$ is an assignment of generators $j : \mathcal {G} \to A$ , where A is a C*-algebra over $\mathbb {K}$ , such that $\left \lVert p(j(x_{1}),\ldots ,j(x_{n}))\right \rVert _{A} \leq a$ for every relation $\left \lVert p(x_{1},\ldots ,x_{n})\right \rVert \leq a$ in $\mathcal {R}$ .

Definition 2.8. The universal C*-algebra of $(\mathcal {G},\mathcal {R})$ over $\mathbb {K}$ is a C*-algebra ${\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}} {\mathcal {R}};{\mathbb {K}}\rangle }$ over $\mathbb {K}$ , along with a representation $\iota : \mathcal {G} \to {\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}} {\mathcal {R}};{\mathbb {K}}\rangle }$ of $(\mathcal {G},\mathcal {R})$ , such that for all representations $j : \mathcal {G} \to A$ of $(\mathcal {G},\mathcal {R})$ there is a unique *-homomorphism $\varphi : {\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}} {\mathcal {R}};{\mathbb {K}}\rangle } \to A$ for which $\varphi (\iota (x)) = j(x)$ for all $x \in \mathcal {G}$ .

If ${\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}} {\mathcal {R}};{\mathbb {K}}\rangle }$ exists, then it is unique up to isomorphism, and it is generated by $\iota (\mathcal {G})$ as a C*-algebra over $\mathbb {K}$ . The existence of universal complex C*-algebras is well-established (see [2] or [26]), and the existence of universal real C*-algebras follows by the same argument. It may be of interest to model theorists that, in both cases, existence of universal C*-algebras is just an application of the continuous form of the classical fact that strict universal Horn theories admit all initial term models.

Note that if $\mathcal {G}$ is a set of generators and $\mathcal {R}$ is a set of relations over $\mathbb {R}$ , then ${\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {C}}\rangle }$ is the complexification of ${\mathrm {C}^{*} \langle {\mathcal {G}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {R}}\rangle }$ .

We have not required that the C*-algebras be unital. If we want to speak of universal C*-algebras among unital C*-algebras, we often need to explicitly require a generator for the identity and relations describing that it is indeed the identity. To that end, we define here

$$\begin{align*}\operatorname{\mathrm{Iden}}(e;X) = \{e^{2} = e^{*} = e\} \cup \{ex = xe = x {\colon\,} x \in X\} \end{align*}$$

for all indeterminates e and sets of indeterminates X.

Let G be a countable discrete group with identity e.

Definition 2.9. If we let $\mathcal {G} = G$ and let

$$\begin{align*}\mathcal{R} = \{x^{*}x = xx^{*} = e {\colon\,} x \in \mathcal{G}\} \cup \{xy = z {\colon\,} x,y,z \in \mathcal{G} \text{ and } xy = z \text{ in } G\}, \end{align*}$$

then the universal C*-algebra of $(\mathcal {G},\mathcal {R})$ over $\mathbb {K}$ is called the universal group C*-algebra of G over $\mathbb {K}$ and denoted ${\mathrm {C}_{\mathrm {uni}}^{*} ({G};{\mathbb {K}})}$ .

There is another important way to form group C*-algebras. Let $\ell ^{2}G$ be the Hilbert space of all square summable functions from G to $\mathbb {C}$ . Then G acts on $\ell ^{2}G$ by left multiplication on the standard orthonormal basis, and in this way can be embedded as a set of operators in ${B({\ell ^{2}G};{\mathbb {K}})}$ .

Definition 2.10. The C*-algebra over $\mathbb {K}$ generated by G in ${B({\ell ^{2}G};{\mathbb {K}})}$ is called the reduced group C*-algebra of G over $\mathbb {K}$ and denoted ${\mathrm {C}^{*}_{\mathrm {red}} ({G};{\mathbb {K}})}$ .

The following lifting property will come in handy. A proof for the complex case can be found in [41] (2.2.10), and the real case follows from complexification.

Fact 2.11. Let A and B be C*-algebras over $\mathbb {K}$ . If $\pi : A \to B$ is a surjective $*$ -homomorphism, then for all $b \in B$ there exist $a \in A$ such that $\left \lVert a\right \rVert _{A} = \left \lVert b\right \rVert _{B}$ and $\pi (a) = b$ .

When dealing with finite-dimensional C*-algebras, it will be useful to remember they are von Neumann algebras.

Definition 2.12. Let $\mathcal {H}$ be a Hilbert space over $\mathbb {K}$ . For $S \subseteq {B({\mathcal {H}};{\mathbb {K}})} $ , we define the commutant $S'$ of S in ${B({\mathcal {H}};{\mathbb {K}})} $ by

$$\begin{align*}S' = \{x \in {B({\mathcal{H}};{\mathbb{K}})} {\colon\,} xs= sx \text{ for } s \in S\}.\end{align*}$$

Definition 2.13 (Von Neumann double commutant theorem).

Let $\mathcal {H}$ be a Hilbert space over $\mathbb {K}$ . If $A \subseteq {B({\mathcal {H}};{\mathbb {K}})} $ is a C*-algebra over $\mathbb {K}$ which contains the identity, then A is a von Neumann algebra if and only if $A" = A$ in ${B({\mathcal {H}};{\mathbb {K}})} $ .

2.2 Computability

We present the basics of effective metric structure theory in the context of C*-algebras. Our presentation is an instance of the general framework for arbitrary metric structures developed by Franklin and McNicholl in [15]. See also [7] for a treatment of Banach spaces.

Definition 2.14. Given a separable C*-algebra A over $\mathbb {K}$ , a presentation of A is a pair $(A, \overline {a})$ , where $\overline {a}$ is a countable sequence of elements of A such that $\overline {a}$ generates A as a C*-algebra over $\mathbb {K}$ .

Every separable C*-algebra admits a presentation, just consider any countable dense subset. The presentation is finitely generated if the length of $\overline {a}$ is finite. We refer to the elements of $\overline {a}$ as the special points of the presentation.

We restrict our attention to the class of rational polynomials, where a real polynomial is rational if its coefficients belong to $\mathbb {Q}$ , and a complex polynomial is rational if its coefficients belong to $\mathbb {Q}(i)$ . If p is a rational *-polynomial in n noncommuting variables with no constant term, and $(A,\overline {a})$ is a presentation of A, then we say $p(a_{i_{1}},\ldots ,a_{i_{n}})$ is a rational point of $(A,\overline {a})$ for $i_{1},\ldots ,i_{n} \in \mathbb {N}$ .

Definition 2.15. A presentation $A^{\dagger }$ of a C*-algebra A over $\mathbb {K}$ is computable if there is an effective procedure which, when given a rational point r of $A^{\dagger }$ and $k \in \mathbb {N}$ , returns a rational $q \in \mathbb {Q}$ such that $|\left \lVert r\right \rVert - q| < 2^{-k}$ .

Here are some standard computable presentations.

Examples 2.16.

1. (i) $({C({[0,1]};{\mathbb {K}})}, (1,x))$ , where $x : [0,1] \to \mathbb {K}$ is the identity function. The rational points are the rational *-polynomials in x, which are dense by Stone–Weierstrass.

2. (ii) $(M_n(\mathbb {K}), (e_{ij})_{1 \leq i,j \leq n})$ , where each $e_{ij}$ is $1$ in the $(i,j)$ entry and $0$ in all others. The rational points are the rational *-polynomials in $(e_{ij})_{1 \leq i,j \leq n}$ , which are clearly dense.

Let A be a C*-algebra over $\mathbb {K}$ with computable presentation $A^{\dagger }$ . We say $x \in A$ is a computable point of $A^{\dagger }$ if there is an effective procedure which, when given $k \in \mathbb {N}$ , returns a rational point r of $A^{\dagger }$ such that $\left \lVert x - r\right \rVert < 2^{-k}$ . Trivially, every rational point of $A^{\dagger }$ is a computable point of $A^{\dagger }$ . A sequence $(x_{n})_{n\in \mathbb {N}}$ of computable points of $A^{\dagger }$ is uniformly computable from $A^{\dagger }$ if there is an effective procedure which, when given $n \in \mathbb {N}$ and $k \in \mathbb {N}$ , returns a rational point r of $A^{\dagger }$ such that $\left \lVert x_{n} - r\right \rVert < 2^{-k}$ .

Let A and B be C*-algebras over $\mathbb {K}$ with computable presentations $A^{\dagger }$ and $B^{\dagger }$ , respectively. Let $\varphi : A \to B$ be a *-homomorphism. Then $\varphi $ is a computable *-homomorphism from $A^{\dagger }$ to $B^{\dagger }$ if the images of rational points of $A^{\dagger }$ are uniformly computable with respect to $B^{\dagger }$ . Note this notion of computable map agrees with the usual one, as in [15], since *-homomorphisms are Lipschitz. If $\varphi $ is bijective and $\varphi $ is computable, then $\varphi ^{-1}$ is computable, and we say $\varphi $ is a computable isomorphism from $A^{\dagger }$ to $B^{\dagger }$ . A C*-algebra A over $\mathbb {K}$ is computably categorical if for all computable presentations $A^{\dagger }$ and $A^{+}$ of A, there exists a computable isomorphism from $A^{\dagger }$ to $A^{+}$ .

We also consider computability properties of closed subsets of C*-algebras as in [4].

Let A be a C*-algebra over $\mathbb {K}$ with computable presentation $A^{\dagger }$ . An open (resp. closed) rational ball of $A^{\dagger }$ is an open (resp. closed) ball in A whose center is a rational point of $A^{\dagger }$ and whose radius is a positive dyadic rational. We require the radius to be dyadic to better integrate with the framework of continuous first-order logic established in [45].

Let S be a closed subset of A. If the set of all open rational balls of $A^{\dagger }$ that intersect S is c.e., then S is c.e. closed. If there is a c.e. set of open rational balls of $A^{\dagger }$ whose union is the complement of S, then S is co-c.e. closed. Together, if S is c.e. closed and co-c.e. closed, then S is computable closed. If the set of all closed rational balls of $A^{\dagger }$ that do not intersect S is c.e., then S is strongly co-c.e. closed. Similarly, if S is c.e. closed and strongly co-c.e. closed, then S is strongly computable closed.

Here are some fundamental propositions in the computable structure theory for C*-algebras. The straightforward proofs are left to the reader.

Proposition 2.17. There is an effective procedure which, when given a rational noncommutative *-polynomial over $\mathbb {K}$ with no constant term $q(z_1,\ldots ,z_n)$ , a rational bound M, and $k \in \mathbb {N}$ , returns $j \in \mathbb {N}$ such that, for all Banach *-algebras B and all $v_1,\ldots ,v_n,w_1,\ldots ,w_n \in B$ , if $\max _i\left \lVert v_i\right \rVert \leq M$ , $\max _i\left \lVert w_i\right \rVert \leq M$ , and $\max _i\left \lVert v_i - w_i\right \rVert \leq 2^{-j}$ , then

$$\begin{align*}\left\lVert q(v_1,\ldots,v_n) - q(w_1,\ldots,w_n)\right\rVert < 2^{-k}.\end{align*}$$

Proposition 2.18. Let A be a C*-algebra over $\mathbb {K}$ and let $A^{\dagger }$ be a computable presentation of A. Let $\overline {x}$ be a sequence of uniformly computable points of $A^{\dagger }$ . Let $B = {\mathrm {C}_{\mathrm {gen}}^{*} ({\overline {x}};{\mathbb {K}})} \subseteq A$ , the C*-algebra over $\mathbb {K}$ generated by $\overline {x}$ . Then $(B, \overline {x})$ is a computable presentation of B and the inclusion map from $(B, \overline {x})$ to $A^{\dagger }$ is computable.

Corollary 2.19. Let A be a C*-algebra over $\mathbb {K}$ and let $A^{\dagger }$ be a computable presentation of A. Let $\overline {x}$ be a uniformly computable sequence of points of $A^{\dagger }$ such that ${\mathrm {C}_{\mathrm {gen}}^{*} ({\overline {x}};{\mathbb {K}})} = A$ . Then $(A, \overline {x})$ is a computable presentation of A which is computably isomorphic to $A^{\dagger }$ via the identity map.

2.3 Linear algebra

When working with real C*-algebras, we will need to do linear algebra over $\mathbb {H}$ . Let $\mathbb {D}$ be one of $\mathbb {R}$ , $\mathbb {H}$ , or $\mathbb {C}$ , viewed as a C*-algebra over corresponding $\mathbb {K}$ . We develop basic linear algebra facts over $\mathbb {D}$ for that purpose. See [8] or [25] for the fundamentals of linear algebra, and [14] for an exploration of linear algebra for quaternions.

A vector space V over $\mathbb {D}$ is a right $\mathbb {D}$ -module. Any vector space over $\mathbb {D}$ can be viewed as a vector space over $\mathbb {K}$ by restricting scalars to $\mathbb {K}1$ inside $\mathbb {D}$ . An inner product space over $\mathbb {D}$ is a vector space V over $\mathbb {D}$ equipped with an inner product $\langle \;,\;\rangle : V \times V \to \mathbb {D}$ that has the following properties for $x,y,z \in V$ and $a \in \mathbb {D}$ :

1. (i) $\langle x + y, z \rangle = \langle x, z \rangle + \langle y,z \rangle $ ,

2. (ii) $\langle x, y + z \rangle = \langle x,y \rangle + \langle x,z \rangle $ ,

3. (iii) $\langle xa,y \rangle = a^{*}\langle x,y \rangle $ ,

4. (iv) $\langle x, ya \rangle = \langle x,y \rangle a$ ,

5. (v) $\langle x,y \rangle ^{*} = \langle y, x \rangle $ ,

6. (vi) $\langle x,x \rangle \geq 0$ and if $\langle x,x \rangle = 0$ , then $x = 0$ .

The inner product determines a norm on V given by $x \mapsto \sqrt {\langle x,x \rangle }$ , where we identify the self-adjoint elements of $\mathbb {D}$ with $\mathbb {R}$ . A Hilbert space $\mathcal {H}$ over $\mathbb {D}$ is an inner product space over $\mathbb {D}$ which is complete with respect to the induced norm. Note $\mathcal {H}$ can also be viewed as a Hilbert space over $\mathbb {R}$ when equipped with the inner product $(x,y) \mapsto \frac {1}{2}(\langle x,y \rangle + \langle x,y\rangle ^{*})$ .

We view $\mathbb {D}$ as a vector space over itself. The set of n by n matrices $M_{n}(\mathbb {D})$ with entries in $\mathbb {D}$ can be identified with the set of $\mathbb {D}$ -linear operators ${B({\mathbb {D}^{n}};{\mathbb {D}})}$ on $\mathbb {D}^{n}$ . Rank is well-defined since $\mathbb {D}$ is a division ring so has the invariant basis number property. Any $\mathbb {D}$ -linear operator on a Hilbert space $\mathcal {H}$ over $\mathbb {D}$ is also $\mathbb {K}$ -linear, so we can view ${B({\mathcal {H}};{\mathbb {D}})} $ as a subspace of ${B({\mathcal {H}};{\mathbb {K}})} $ . For all $a \in \mathbb {D}$ , define $R_a : \mathcal {H} \to \mathcal {H}$ to be multiplication on the right by a. Then the commutant ${B({\mathcal {H}};{\mathbb {D}})} '$ of ${B({\mathcal {H}};{\mathbb {D}})} $ in ${B({\mathcal {H}};{\mathbb {K}})} $ is $\{R_{a} {\colon \,} a \in \mathbb {D}\}$ . In particular, the center of ${B({\mathcal {H}};{\mathbb {D}})} $ can be identified with the center of $\mathbb {D}$ .

Of course, $\mathbb {D}$ itself is a Hilbert space over $\mathbb {K}$ when equipped with the natural inner product. We identify a standard orthonormal basis Z of $\mathbb {D}$ over $\mathbb {K}$ as follows. We let:

• • $Z = \{1\}$ if $\mathbb {D} = \mathbb {K} = \mathbb {R}$ or $\mathbb {D} = \mathbb {K} = \mathbb {C}$ ,

• • $Z = \{1, i\}$ if $\mathbb {D} = \mathbb {C}$ and $\mathbb {K} = \mathbb {R}$ ,

• • $Z = \{1, i, j, k\}$ if $\mathbb {D} = \mathbb {H}$ and $\mathbb {K} = \mathbb {R}$ .

We also define a system of matrix units which characterize $M_{n}(\mathbb {D})$ as a C*-algebra over $\mathbb {K}$ up to isomorphism. For any element t in $Z \cup \{-z {\colon \,} z \in Z\}$ , we define $\epsilon (t) \in \{1,-1\}$ and $b(t) \in Z$ such that $t = \epsilon (t)b(t)$ . We say $(f_{rs}^{z} {\colon \,} 1 \leq r,s \leq n, z \in Z)$ is a system of matrix units for $M_{n}(\mathbb {D})$ over $\mathbb {K}$ if $(f_{rs}^{z})^{*} = \epsilon (z^{*})f_{sr}^{z}$ and $f_{rs}^{z}f_{uv}^{w} = \epsilon ({zw})\delta _{su}f^{b(zw)}_{rv}$ for $1 \leq r,s,u,v \leq n$ and $z,w \in Z$ . The standard system of matrix units is then just $(e_{rs}^{z} {\colon \,} 1 \leq r,s \leq n, z \in Z)$ where $e_{rs}^{z}$ is the matrix with z in the $(r,s)$ entry and $0$ in all other entries for $1 \leq r,s \leq n$ and $z \in Z$ . When the superscript of a matrix unit is $1$ , we will often suppress it.

We will use Skolem–Noether to characterize the $*$ -automorphisms of $M_{n}(\mathbb {D})$ .

Fact 2.20 (Skolem–Noether).

Let k be a field. Let A be a finite-dimensional k-algebra which is simple and has center k. Then every automorphism of A is of the form $x \mapsto v^{-1}xv$ for some unit $v \in A$ .

Corollary 2.21. If the center of $\mathbb {D}$ is exactly $\mathbb {K}$ , then every $*$ -automorphism of $M_{n}(\mathbb {D})$ is of the form $x \mapsto u^{*}xu$ for some unitary $u \in M_{n}(\mathbb {D})$ .

Proof Let $\varphi $ be a $*$ -automorphism of $M_{n}(\mathbb {D})$ . It can be observed that $M_{n}(\mathbb {D})$ is a simple finite-dimensional $\mathbb {K}$ -algebra with center $\mathbb {K}$ , so, by the previous fact, there exists an invertible $v \in M_{n}(\mathbb {D})$ such that $\varphi (x) = v^{-1}xv$ for $x \in M_{n}(\mathbb {D})$ . For $x \in M_{n}(\mathbb {D})$ ,

$$\begin{align*}xvv^{*} = v(v^{-1}xv)v^{*} = v\varphi(x)v^{*} = v\varphi(x^{*})^{*}v^{*} = v(v^{*}x(v^{-1})^{*})v^{*} = vv^{*}x.\end{align*}$$

Hence $vv^{*}$ belongs to the center of $M_{n}(\mathbb {D})$ , so is of the form $R_{a}$ for some $a \in \mathbb {K}$ . In fact, since $vv^{*}$ is self-adjoint and nonzero, it must be that $a> 0$ . Let $b = a^{-1/2}$ and let $u = R_{b} v$ . Then $uu^{*} = R_{b}vv^{*}R_{b} = R_{b}R_{a}R_{b} = I$ . By uniqueness of the inverse, u is unitary. Furthermore, for $x \in M_{n}(\mathbb {D})$ , $u^*xu = v^{-1}R_{1/b}xR_{b}v = v^{-1}xv = \varphi (x)$ .

3 C.e. presentations and word problems

Here we introduce c.e. presentations for C*-algebras, borrowing the terminology from [33], and explore their similarity to the group situation.

We consider universal C*-algebras where the set of generators forms a sequence. Let ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ be a universal C*-algebra over $\mathbb {K}$ , where we identify the elements of $\overline {x}$ with their image under the associated representation. The standard presentation of ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ is then $({\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }, \overline {x})$ , which we simply denote by ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ .

On a set of generators, a relation $\left \lVert p(x_{1},\ldots ,x_{n})\right \rVert \leq a$ is rational if p is rational and a is a positive dyadic rational.

Definition 3.1. A presentation $A^{\dagger }$ of a C*-algebra A over $\mathbb {K}$ is c.e. if $A^{\dagger }$ is the standard presentation ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ for some c.e. set of rational relations $\mathcal {R}$ .

If $\overline {x}$ and $\mathcal {R}$ are finite, we say $A^{\dagger }$ is finitely c.e.

There is another c.e. notion for presentations that one might consider in any presented metric structure. We give the definition for C*-algebras (see [1] for the definition for Polish metric spaces).

Definition 3.2. A presentation $A^{\dagger }$ of a C*-algebra A over $\mathbb {K}$ is right-c.e. if there is an effective procedure which, when given a rational point r of $A^{\dagger }$ , enumerates a decreasing sequence $(q_{n})_{n \in \mathbb {N}}$ of rationals such that $\lim _{n \to \infty } q_{n} = \left \lVert r\right \rVert $ .

In the following theorem, we show the two notions agree. We use the framework of continuous first-order logic (see [45] for an overview of the underlying logic and [13] for a reference on its applications to complex C*-algebras).

Theorem 3.3. Let A be a C*-algebra over $\mathbb {K}$ with presentation $A^{\dagger }$ . Then $A^{\dagger }$ is c.e. if and only if it is right-c.e. Furthermore, if $A^{\dagger } = {\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ for some c.e. set of rational relations $\mathcal {R}$ in $\overline {x}$ , we can effectively determine a procedure which witnesses that $A^{\dagger }$ is right-c.e. from a computable enumeration of $\mathcal {R}$ .

Proof Suppose $A^{\dagger }$ is c.e., so $A^{\dagger }$ is the standard presentation ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ for some c.e. set of rational relations $\mathcal {R}$ in $\overline {x}$ .

Let T be the continuous first-order theory of C*-algebras over $\mathbb {K}$ . We expand our language to include additional constants for the generators $\overline {x}$ . Note if $x_{i}$ is a member of $\overline {x}$ , then there is a relation of the form $\left \lVert x_{i}\right \rVert \leq M$ in $\mathcal {R}$ , so we can put $x_{i}$ in an appropriate sort. Given a rational point $r(\overline {x})$ of $A^{\dagger }$ , we enumerate through all formal deductions from $T \cup \mathcal {R}$ . For each formal deduction, we output a positive dyadic rational $q_{n}$ if $q_{n} \leq q_{i}$ for all $i < n$ and the formal deduction witnesses that $T \cup \mathcal {R} \vdash \left \lVert r(\overline {x})\right \rVert \leq q_{n}$ . Note this procedure is defined uniformly in the computable enumeration of $\mathcal {R}$ . By Pavelka-style completeness, $\left \lVert r(\overline {x})\right \rVert $ is the infimum of all positive dyadic rationals d such that $T \cup \mathcal {R} \vdash \left \lVert r(\overline {x})\right \rVert \leq d$ . Thus, we have enumerated a decreasing sequence of rationals $(q_{n})_{n \in \mathbb {N}}$ such that $\lim _{n \to \infty } q_{n} = \left \lVert r(\overline {x})\right \rVert $ .

Conversely, suppose $A^{\dagger }$ is right-c.e. Then there is an effective procedure which, when given a rational point r of $A^{\dagger }$ , enumerates a decreasing sequence $(q_{n})_{n \in \mathbb {N}}$ of dyadic rationals such that $\lim _{n \to \infty } q_{n} = \left \lVert r\right \rVert $ . Let $\overline {a}$ be such that $A^{\dagger } = (A,\overline {a})$ , and let $\overline {x}$ be a sequence of generators of the same length. Let $\mathcal {R}$ be the set of relations $\left \lVert r(\overline {x})\right \rVert \leq d$ where $r(\overline {a})$ is a rational point of $A^{\dagger }$ and d is one of the positive dyadic rationals enumerated by the procedure given $r(\overline {a})$ . Then $\mathcal {R}$ is c.e., and $A^{\dagger } = {\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ .

It may interest some that the statement and proof directly generalize from C*-algebras to metric models of a c.e. strict universal Horn theory.

Essentially, with Theorem 3.3, we have rephrased c.e. in terms of the norm so that it mirrors the definition of computable. From this, it becomes clear that if $A^{\dagger }$ is a computable presentation of a C*-algebra A over $\mathbb {K}$ , then $A^{\dagger }$ is also c.e.

If a finitely presented group is residually finite, then it has solvable word problem, as shown by Dyson in [12]. We want to establish an analogous result for C*-algebras.

Definition 3.4. A C*-algebra over $\mathbb {K}$ is called RFD if its finite-dimensional representations form a separating family.

In [16], the authors showed that the standard presentation for a universal group C*-algebra of a finitely presented RFD group is computable, and noted that their result generalizes to arbitrary finitely-presented *-algebras. Their proof works for finitely c.e. presentations of C*-algebras over $\mathbb {K}$ with only a small modification. We include the proof here to emphasize that their use of semidefinite programming is not required, and that the argument is uniform in the sense we describe.

Theorem 3.5. If A is an RFD C*-algebra over $\mathbb {K}$ , then any finitely c.e. presentation $A^{\dagger } = {\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ of A is computable. Furthermore, from $\mathcal {R}$ one can effectively determine a procedure which witnesses that the presentation is computable.

Proof We write $\left \lVert \cdot \right \rVert _f$ for the norm on the direct sum of all finite-dimensional representations of A. Since A is RFD, we have $\left \lVert \cdot \right \rVert _{A} = \left \lVert \cdot \right \rVert _f$ .

For any $n \in \mathbb {N}$ , consider the set $X_n = \{\overline {m} \in M_n(\mathbb {K})^{|\overline {x}|} {\colon \,} \mathcal {R}[\overline {m}] \text { holds in } M_{n}(\mathbb {K})\}$ as a subset of $\mathbb {R}^{k|\overline {x}|n^2}$ , where k is the dimension of $\mathbb {K}$ over $\mathbb {R}$ . Note $X_n$ is compact since every relation in $\mathcal {R}$ is a closed condition and we require for every generator $x_i$ that there is a relation of the form $\left \lVert x_i\right \rVert \leq M_i$ in $\mathcal {R}$ . Furthermore, $X_n$ is definable in the language of real closed fields since $\mathcal {R}$ is finite and if $\left \lVert p(\overline {x})\right \rVert \leq d$ is a relation in $\mathcal {R}$ , then $\left \lVert p(\overline {m})\right \rVert \leq d$ holds in $M_{n}(\mathbb {K})$ if and only if

$$\begin{align*}(\forall \lambda \in \mathbb{R}) [\textstyle\det_n\big(p(\overline{m})^*p(\overline{m}) - \lambda I\big) = 0 \to \lambda \leq d^2].\end{align*}$$

Let $D_n = \{\xi \in \mathbb {K}^n : \left \lVert \xi \right \rVert \leq 1\}$ . Fix a rational point $q(\overline {x}) \in A^{\dagger }$ . Define $F_{n,q} : X_n \times D_n \to \mathbb {R}$ by $F_{n,q}(\overline {m},\xi ) = \left \lVert q(\overline {m})\xi \right \rVert ^2$ , and let $\alpha _{n,q}$ be the maximum value of $F_{n,q}$ . Following closely, we see there is actually an effective procedure which, when given inputs n and q, returns a formula that defines $\alpha _{n,q}$ in the language of real closed fields. Applying the effective quantifier elimination given by Tarski–Seidenberg, we see this formula can even be made quantifier-free, so $\alpha _{n,q}$ is computable uniformly in n and q.

Observe $\left \lVert q(\overline {x})\right \rVert _A = \left \lVert q(\overline {x})\right \rVert _f \leq \sup \{\alpha _{n,q}^{1/2} {\colon \,} n \in \mathbb {N}\}$ since every finite-dimensional representation of A can be embedded in $M_n(\mathbb {K})$ for sufficiently large n. By the universality of ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ , we also have $\left \lVert q(\overline {x})\right \rVert _A \geq \sup \{\alpha _{n,q}^{1/2} {\colon \,} n \in \mathbb {N}\}$ . Hence $\left \lVert q(\overline {x})\right \rVert _A = \sup \{\alpha _{n,q}^{1/2} : n \in \mathbb {N}\}$ , so along with Theorem 3.3 we can conclude that $\left \lVert q(\overline {x})\right \rVert $ is computable uniformly in q. Thus $A^{\dagger }$ is computable. This procedure is uniform in $\mathcal {R}$ since the formula which defines $\alpha _{n,q}$ can be effectively determined uniformly in $\mathcal {R}$ , and the procedure from Theorem 3.3 is uniform in $\mathcal {R}$ .

We would like to study word problems associated with presentations of C*-algebras. Although the category of C*-algebras over $\mathbb {K}$ does not admit-free objects, we can recover a lot of their utility for word problems by considering universal contraction algebras.

Definition 3.6. For $n \in \mathbb {N}$ , we let $\mathcal {F}(n;\mathbb {K})$ denote ${\mathrm {C}^{*} \langle {c_1,\ldots ,c_n}\operatorname {\mathrm {|}}{\left \lVert c_j\right \rVert \leq 1};{\mathbb {K}}\rangle }$ , the universal contraction C*-algebra over $\mathbb {K}$ on n generators. Similarly, we let $\mathcal {F}(\omega ;\mathbb {K})$ denote ${\mathrm {C}^{*} \langle {\{c_{j} {\colon \,} j \in \mathbb {N}\}}\operatorname {\mathrm {|}}{\left \lVert c_{j}\right \rVert \leq 1};{\mathbb {K}}\rangle }$ , the universal contraction C*-algebra over $\mathbb {K}$ on infinitely many generators.

To avoid confusion, we will always use $\overline {c}$ to refer to the generators of a universal contraction C*-algebra.

In order to study the computability properties of subsets of the standard presentation $\mathcal {F}(n;\mathbb {K})$ , we first need to establish that the presentation is computable. The following is a standard fact (see [26] for details).

Fact 3.7. $\mathcal {F}(n;\mathbb {K})$ is RFD for every $n \in \mathbb {N} \cup \{\omega \}$ .

Together with the previous theorem, we have the following.

Corollary 3.8. The standard presentation $\mathcal {F}(n;\mathbb {K})$ is computable for every $n \in \mathbb {N}$ .

Not only that, but the effective procedure which witnesses that $\mathcal {F}(n;\mathbb {K})$ is computable is uniform in n. If $p(c_{1},\ldots ,c_{k})$ is a rational point of $\mathcal {F}(\omega ;\mathbb {K})$ , then $\left \lVert p(c_{1},\ldots ,c_{k})\right \rVert _{\mathcal {F}(\omega ;\mathbb {K})} = \left \lVert p(c_{1},\ldots ,c_{k})\right \rVert _{\mathcal {F}(k;\mathbb {K})}$ , so we have the following.

Corollary 3.9. The standard presentation $\mathcal {F}(\omega ;\mathbb {K})$ is computable.

Now we are in a position to define the word problem. When considering the word problem, it is convenient if we assume every presentation $(A,\overline {a})$ satisfies $\left \lVert a_j\right \rVert \leq 1$ for all j.

Definition 3.10. Let A be a C*-algebra over $\mathbb {K}$ with presentation $(A,\overline {a})$ . The word problem of $(A,\overline {a})$ is the kernel of the natural quotient map from $\mathcal {F}(|\overline {a}|;\mathbb {K})$ onto A.

As with groups, there are relationships between the word problem and the presentation.

Theorem 3.11. Let A be a C*-algebra over $\mathbb {K}$ with presentation $A^{\dagger }$ . The following are equivalent:

1. (a) $A^{\dagger }$ is the standard presentation ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {S}};{\mathbb {K}}\rangle }$ where $\mathcal {S}$ is a computable set of relations.

2. (b) the word problem of $A^{\dagger }$ is c.e. closed.

3. (c) $A^{\dagger }$ is a c.e. presentation.

Proof (a) $\implies $ (c) clearly holds.

(c) $\implies $ (a). This follows by the standard argument known as Craig’s trick. Since $A^{\dagger }$ is c.e., $A^{\dagger }$ is the standard presentation ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ for some c.e. set of rational relations $\mathcal {R}$ . For every relation $\left \lVert p(\overline {x})\right \rVert \leq d$ in $\mathcal {R}$ , include the relation $\left \lVert p(\overline {x}) + k0\right \rVert \leq d$ in $\mathcal {S}$ , where k encodes a Turing computation which witnesses that $\left \lVert p(\overline {x})\right \rVert \leq d$ belongs to $\mathcal {R}$ . Then $\mathcal {S}$ is computable and $A^{\dagger }$ is the standard presentation ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {S}};{\mathbb {K}}\rangle }$ .

Let $\overline {a}$ be such that $A^{\dagger } = (A,\overline {a})$ , and let $\overline {c}$ be the corresponding sequence of generators for $\mathcal {F}(|\overline {a}|;\mathbb {K})$ . Let N be the word problem of $A^{\dagger }$ .

(b) $\implies $ (c). Given a rational point $r(\overline {a})$ of $A^{\dagger }$ , we enumerate the set of all open rational balls of $\mathcal {F}(|\overline {a}|;\mathbb {K})$ that intersect N. For each rational ball, we output a positive dyadic rational $q_{n}$ if $q_{n} \leq q_{i}$ for all $i < n$ , and the open rational ball is of the form $B(r(\overline {c}), q_{n})$ . Note $B(r(\overline {c}),q_{n})$ intersects N if and only if $\left \lVert r(\overline {a})\right \rVert < q_{n}$ . Then $(q_{n})_{n \in \mathbb {N}}$ is a decreasing sequence of rationals such that $\lim _{n \to \infty } q_{n} = \left \lVert r(\overline {a})\right \rVert $ . By Theorem 3.3, we conclude the presentation $A^{\dagger }$ is c.e.

(c) $\implies $ (b). We enumerate through all rational points of $\mathcal {F}(|\overline {a}|;\mathbb {K})$ and all positive dyadic rationals. For each rational point $r(\overline {c})$ and positive dyadic rational d, we begin an enumeration of the decreasing sequence $(q_{n})_{n \in \mathbb {N}}$ of rationals determined by Theorem 3.3 on input $r(\overline {a})$ , and output $B(r(\overline {c}),d)$ if ever $q_{n} < d$ for some $n \in \mathbb {N}$ . Since $B(r(\overline {c}),d)$ intersects N if and only if $\left \lVert r(\overline {a})\right \rVert < d$ , we have shown N is c.e. closed.

We can even define when a presentation is computable in terms of the word problem.

Theorem 3.12. Let A be a C*-algebra over $\mathbb {K}$ with presentation $A^{\dagger }$ . Then $A^{\dagger }$ is computable if and only if the word problem of $A^{\dagger }$ is strongly computable closed.

Proof Let $\overline {a}$ be such that $A^{\dagger } = (A,\overline {a})$ , and let $\overline {c}$ be the corresponding sequence of generators for $\mathcal {F}(|\overline {a}|;\mathbb {K})$ . Let N be the word problem of $A^{\dagger }$ .

Suppose $A^{\dagger }$ is a computable presentation. Then $A^{\dagger }$ is a c.e. presentation, so N is c.e. closed by Theorem 3.11. We show N is strongly co-c.e. closed. We enumerate through all rational points $r(\overline {a})$ of $A^{\dagger }$ , positive dyadic rationals d, and $k \in \mathbb {N}$ . The computable presentation $A^{\dagger }$ determines a rational q such that $|\left \lVert r(\overline {a})\right \rVert - q| < 2^{-k}$ . If $d \leq q - 2^{-k}$ , then we output the closed rational ball $\widehat {B}(r(\overline {c}), d)$ . If d is a positive dyadic rational such that $\widehat {B}(r(\overline {c}), d) \cap N = \emptyset $ , then $\left \lVert r(\overline {a})\right \rVert> d$ by Fact 2.11. So, if $k \in \mathbb {N}$ is such that $2^{-k+1} < \left \lVert r(\overline {a})\right \rVert - d$ , then $d \leq q - 2^{-k}$ for any rational q such that $|\left \lVert r(\overline {a})\right \rVert - q| < 2^{-k}$ . Hence $\widehat {B}(r(\overline {c}), d)$ is eventually output.

Conversely, suppose N is strongly computable closed. If $B(r(\overline {c}),d)$ is an open rational ball, then it intersects N if and only if $\left \lVert r(\overline {a})\right \rVert < d$ . Similarly, if $\widehat {B}(r(\overline {c}),e)$ is a closed rational ball, then $\widehat {B}(r(\overline {c}),e) \cap N = \emptyset $ if and only if $\left \lVert r(\overline {a})\right \rVert> e$ by Fact 2.11. We define an effective procedure which witnesses that $A^{\dagger }$ is computable. Given a rational point $r(\overline {a}) \in A^{\dagger }$ and $k \in \mathbb {N}$ , we begin enumerating all open rational balls $B(r(\overline {c}), d_{i})$ , centered at $r(\overline {c})$ , that intersect N. We also begin enumerating all closed rational balls $\widehat {B}(r(\overline {c}),e_{j})$ , centered at $r(\overline {c})$ , such that $\widehat {B}(r(\overline {c}),e_{j}) \cap N = \emptyset $ . If ever $d_{i} - e_{j} < 2^{-k+1}$ for some $i,j \in \mathbb {N}$ , we return $\frac {1}{2}(d_{i} - e_{j})$ .

Consequently, if $A^{\dagger }$ is a computable presentation of a C*-algebra A over $\mathbb {K}$ , then the word problem of $A^{\dagger }$ is computable closed. In the group situation, we know the converse holds.

Question 3.13. Is there a presentation $A^{\dagger }$ of a C*-algebra A over $\mathbb {K}$ such that $A^{\dagger }$ is not computable but has computable closed word problem?

In [23], Kuzntsov proved that a recursively presented simple group has solvable word problem. Analogously, we have the following theorem.

Theorem 3.14. If A is a simple C*-algebra over $\mathbb {K}$ , then any c.e. presentation $A^{\dagger }$ of A is computable.

Proof Let $\mathcal {R}$ be a c.e. set of rational relations such that $A^{\dagger }$ is ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R}};{\mathbb {K}}\rangle }$ .

Let T be the continuous first-order theory of C*-algebras over $\mathbb {K}$ . We expand our language to include additional constants for the generators $\overline {x}$ . Fix a rational point $q(\overline {x})$ of $A^{\dagger }$ and a positive dyadic rational $\ell $ such that $\left \lVert q(\overline {x})\right \rVert> \ell $ . Since A is simple, if $r(\overline {x})$ is a rational point of $A^{\dagger }$ and d is a positive dyadic rational, then ${\mathrm {C}^{*} \langle {\overline {x}}\operatorname {\mathrm {|}}{\mathcal {R} \cup \{\left \lVert r(\overline {x})\right \rVert \leq d\}};{\mathbb {K}}\rangle }$ is just A if $\left \lVert r(\overline {x})\right \rVert \leq d$ and $\{0\}$ if $\left \lVert r(\overline {x})\right \rVert> d$ . Hence by Pavelka-style completeness, $\left \lVert r(\overline {x})\right \rVert> d$ if and only if $T \cup \mathcal {R} \cup \{\left \lVert r(\overline {x})\right \rVert \leq d\} \vdash \left \lVert q(\overline {x})\right \rVert \leq \ell $ .

We define an effective procedure which witnesses that $A^{\dagger }$ is computable. Given a rational point $r(\overline {x}) \in A^{\dagger }$ and $k \in \mathbb {N}$ , we apply Theorem 3.3 and enumerate a decreasing sequence $(q_n)_{n \in \mathbb {N}}$ of positive dyadic rationals such that $\lim _{n \to \infty } q_n = \left \lVert r(\overline {x})\right \rVert $ . Let be $a - b$ if $a \geq b$ and $0$ otherwise for $a,b \in \mathbb {R}$ . For each $q_{n}$ , we begin enumerating through all formal deductions from , and we return $q_{n}$ if the formal deduction witnesses that .

The computability of several standard presentations follows as a direct consequence.

Definition 3.15. For $2 \leq n < \infty $ , the Cuntz algebra $\mathcal {O}(n;\mathbb {K})$ over $\mathbb {K}$ is the universal C*-algebra given by

$$\begin{align*}{\mathrm{C}^{*} \langle{s_{1},\ldots,s_{n},1}\operatorname{\mathrm{|}}{\operatorname{\mathrm{Iden}}(1;s_{1},\ldots,s_{n}) \cup \mathcal{R}};{\mathbb{K}}\rangle} , \end{align*}$$

where

$$\begin{align*}\mathcal{R} = \{s_i^*s_j = \delta_{ij}1 {\colon\,} i,j \leq n\}\cup\{s_{1}s_{1}^* + \cdots + s_{n}s_{n}^{*}= 1\}.\end{align*}$$

We also consider $n = \infty $ and define $\mathcal {O}(\infty ;\mathbb {K})$ to be the universal C*-algebra given by

$$\begin{align*}{\mathrm{C}^{*} \langle{\{s_{i} {\colon\,} i \in \mathbb{N}\}, 1}\operatorname{\mathrm{|}}{\operatorname{\mathrm{Iden}}(1;\{s_{i} {\colon\,} i \in \mathbb{N}\}), s_{i}^{*}s_{j} = \delta_{ij}1 \;(i,j \in \mathbb{N})};{\mathbb{K}}\rangle}. \end{align*}$$

It is known that $\mathcal {O}(n;\mathbb {C})$ is simple (see [9] for details). Note then $\mathcal {O}(n;\mathbb {R})$ is simple by complexification.

Corollary 3.16. The standard presentation of $\mathcal {O}(n;\mathbb {K})$ is computable for $2 \leq n \leq \infty $ .

Definition 3.17. For irrational $\theta \in (0,1)$ , the irrational rotation algebra $A_{\theta }$ is the complex universal C*-algebra given by

$$\begin{align*}{\mathrm{C}^{*} \langle{u,v,1}\operatorname{\mathrm{|}}{\operatorname{\mathrm{Iden}}(1;u,v) \cup \mathcal{R}};{\mathbb{C}}\rangle}, \end{align*}$$

where

$$\begin{align*}\mathcal{R} = \{u^*u = uu^* = v^*v = vv^* = 1\} \cup \{uv = e^{2i\pi \theta}vu\}.\end{align*}$$

It is known that $A_{\theta }$ is simple (see [10] for details).

Corollary 3.18. Let $\theta \in (0,1)$ be irrational. The following are equivalent:

1. (a) $\theta $ is computable.

2. (b) The standard presentation $A_{\theta }$ is c.e.

3. (c) The standard presentation $A_{\theta }$ is computable.

Proof (a) $\implies $ (b). Since $\theta $ is computable, $\cos (2\pi \theta )$ and $\sin (2\pi \theta )$ are also computable. Let $(a_k)_{k \in \mathbb {N}}$ be a computable enumeration of rationals such that $|\cos (2\pi \theta ) - a_k| \leq 2^{-k}$ for $k \in \mathbb {N}$ , and let $(b_k)_{k \in \mathbb {N}}$ be a computable enumeration of rationals such that $|\sin (2\pi \theta ) - b_k| \leq 2^{-k}$ for $k \in \mathbb {N}$ . Let

$$ \begin{align*} \mathcal{S} = \operatorname{\mathrm{Iden}}(1;u,v) &\cup \{u^*u = uu^* = v^*v = vv^* = 1\} \\ &\cup \{\left\lVert uv - (a_k +ib_k)vu\right\rVert \leq 2^{-k+1} : k \in \mathbb{N}\}. \end{align*} $$

Then $\mathcal {S}$ is c.e. and $A_{\theta }$ is the standard presentation ${\mathrm {C}^{*} \langle {u,v,1}\operatorname {\mathrm {|}} {\mathcal {S}};{\mathbb {K}}\rangle }$ .

(b) $\implies $ (c). Since $A_{\theta }$ is simple, by Theorem 3.14, $A_{\theta }$ is computable.

(c) $\implies $ (a). Note that $uvu^*v^* - vuv^*u^* = 2i\sin (2\pi \theta )1$ is a rational point of $A_{\theta }$ , so $\sin (2\pi \theta )$ is computable. Similarly, $uvu^*v^* + vuv^*u^* = 2i\cos (2\pi \theta )1$ is a rational point of $A_{\theta }$ , so $\cos (2\pi \theta )$ is computable. The angle $\theta $ can be calculated from $\sin (2\pi \theta )$ and $\cos (2\pi \theta )$ with use of the arctangent function. Thus $\theta $ is computable.

We now investigate the connections between a group and its group C*-algebras. We cover some of the same ground as in [16], but our perspective has the advantage of avoiding the use of semidefinite programming.

When working with arbitrary countable groups, we adopt the same language of presentations that we have used for C*-algebras. We can again use the framework for arbitrary metric structures developed in [15] if we view discrete groups as metric structures equipped with the discrete metric.

Definition 3.19. Given a countable discrete group G with identity e, we say $(G,\overline {g})$ is a presentation of G if $\overline {g}$ is a countable sequence of elements from G that generates G as a group. The presentation $(G,\overline {g})$ is computable if the set of all words w, on generators $\overline {g}$ , for which $w = e$ in G is computable.

We say a presentation of G is c.e. if the presentation witnesses that G is recursively presented, and is finitely c.e. if the presentation witnesses that G is finitely presented.

Let G be a countable discrete group with presentation $G^{\dagger }$ . We denote by ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ the induced presentation of ${\mathrm {C}_{\mathrm {uni}}^{*} ({G};{\mathbb {K}})}$ , and by ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ the induced presentation of ${\mathrm {C}^{*}_{\mathrm {red}} ({G};{\mathbb {K}})}$ . From the definition of ${\mathrm {C}_{\mathrm {uni}}^{*} ({G};{\mathbb {K}})}$ , it is clear that if $G^{\dagger }$ is c.e., then ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ is c.e. Furthermore, if $G^{\dagger }$ is finitely c.e., then ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ is finitely c.e.

Theorem 3.20. Let G be a countable discrete group with presentation $G^{\dagger }$ . Let $N_{\mathrm {uni}}$ and $N_{\mathrm {red}}$ be the word problems of ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ and ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ , respectively. The following are equivalent:

1. (a) $G^{\dagger }$ is a computable presentation.

2. (b) $N_{\mathrm {uni}}$ is c.e. closed and $N_{\mathrm {red}}$ is strongly co-c.e. closed.

3. (c) $N_{\mathrm {uni}}$ is c.e. closed and the set of rational points which belong to the complement $N_{\mathrm {uni}}^{c}$ is c.e.

4. (d) $N_{\mathrm {red}}$ is co-c.e. closed and there is a c.e. set of open rational balls, each which intersects $N_{\mathrm {red}}$ , such that the set contains all balls centered at rational points belonging to $N_{\mathrm {red}}$ .

Proof Let $\overline {g}$ be such that $G^{\dagger } = (G,\overline {g})$ . Let $\overline {c}$ be the corresponding sequence of generators for $\mathcal {F}(|\overline {g}|;\mathbb {K})$ . Let e be the identity in G.

(a) $\implies $ (b). Since $G^{\dagger }$ is c.e., ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ is c.e. By Theorem 3.11, $N_{\mathrm {uni}}$ is c.e. closed.

We show $N_{\mathrm {red}}$ is strongly co-c.e. closed. We enumerate through all rational points $r(\overline {g})$ of ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ and all positive dyadic rationals d. Since $G^{\dagger }$ is computable, for each pair $r(\overline {g})$ and d, we can begin an enumeration of all finite sums $\sum _{i=1}^{n} a_{i}h_{i}$ where $a_{1},\ldots ,a_{n}$ are nonzero rationals of $\mathbb {K}$ , $h_{1},\ldots ,h_{n}$ are words on $\overline {g}$ such that $h_{i} \neq h_{j}$ in G for $1 \leq i < j < n$ , and

$$\begin{align*}\left\lVert\sum_{i=1}^{n} a_{i}h_{i}\right\rVert_{\ell^{2}(G)}^{2} = \sum_{i=1}^{n} a_{i}^{2} \leq 1.\end{align*}$$

Again using that $G^{\dagger }$ is computable, we can effectively rewrite the action of $r(\overline {g})$ on $\sum _{i=1}^{n} a_{i}h_{i}$ into the form $\sum _{i=1}^{m} b_{i}f_{i}$ where $b_{1},\ldots ,b_{m}$ are nonzero rationals of $\mathbb {K}$ , and $f_{1},\ldots ,f_{m}$ are words on $\overline {g}$ such that $f_{i} \neq f_{j}$ in G for $1 \leq i < j \leq m$ . Note

$$\begin{align*}\left\lVert r(\overline{g})\right\rVert_{\mathrm{red}} \geq \left\lVert\sum_{i=1}^{m} b_{i}f_{i}\right\rVert_{\ell^{2}(G)} = \bigg(\sum_{i=1}^{m} b_{i}^{2}\bigg)^{1/2}.\end{align*}$$

If $d < (\sum _{i=1}^{m} b_{i}^{2})^{1/2}$ , we output $\widehat {B}(r(\overline {c}),d)$ . Since $\left \lVert r(\overline {g})\right \rVert _{\mathrm {red}}$ is the supremum of all such $\left \lVert \sum _{i=1}^{m} b_{i}f_{i}\right \rVert _{\ell ^{2}(G)}$ , by Fact 2.11, we have shown $N_{\mathrm {red}}$ is strongly co-c.e. closed.

(b) $\implies $ (c). Since $N_{\mathrm {red}}$ is strongly co-c.e. closed, we can enumerate all rational points r such that $\left \lVert r\right \rVert _{\mathrm {red}}> 0$ . Now, we just observe that $\left \lVert r\right \rVert _{\mathrm {uni}}> 0$ if and only if $\left \lVert r\right \rVert _{\mathrm {red}}> 0$ for rational points r.

(c) $\implies $ (a). Let w be a word on generators $\overline {g}$ . Then $\left \lVert w - e\right \rVert _{\mathrm {uni}} = 0$ or $\left \lVert w - e\right \rVert _{\mathrm {uni}} \geq \sqrt {2}$ . Since $N_{\mathrm {uni}}$ is c.e. closed, we can enumerate all open rational balls $B(r(\overline {c}),d)$ that intersect $N_{\mathrm {uni}}$ . If ever $r(\overline {g}) = w - e$ and $d < \sqrt {2}$ , we have determined that $w = e$ in G. Simultaneously, we enumerate all rational points $q(\overline {c})$ which belong $N_{\mathrm {uni}}^{c}$ . If ever $q(\overline {g}) = w - e$ , then $\left \lVert w - e\right \rVert _{\mathrm {uni}}> 0$ , so $w \neq e$ in G.

(b) $\implies $ (d). Since $N_{\mathrm {uni}}$ is c.e. closed, we can enumerate all open rational balls $B(r(\overline {c}),d)$ such that $\left \lVert r(\overline {g})\right \rVert _{\mathrm {uni}} < d$ . Any such open rational ball intersects $N_{\mathrm {red}}$ since $\left \lVert \cdot \right \rVert _{\mathrm {red}} \leq \left \lVert \cdot \right \rVert _{\mathrm {uni}}$ . If $r(\overline {c})$ belongs to $N_{\mathrm {red}}$ , then $\left \lVert r(\overline {g})\right \rVert _{\mathrm {red}} = 0$ , so $\left \lVert r(\overline {g})\right \rVert _{\mathrm {uni}} = 0$ . Hence $B(r(\overline {c}),d)$ will be enumerated for all positive dyadic rationals d.

(d) $\implies $ (a). Let w be a word on generators $\overline {g}$ . Then $\left \lVert w - e\right \rVert _{\mathrm {red}} = 0$ or $\left \lVert w - e\right \rVert _{\mathrm {red}} \geq \sqrt {2}$ . We express $w - e$ as a rational point $q(\overline {g})$ . Since $N_{\mathrm {red}}$ is co-c.e. closed, we can enumerate a sequence of open rational balls $B(r(\overline {c}), d)$ whose union is $N_{\mathrm {red}}^{c}$ . If ever $\left \lVert q(\overline {c}) - r(\overline {c})\right \rVert < d$ , then $q(\overline {c})$ belongs to $N_{\mathrm {red}}^{c}$ , so we have determined $w \neq e$ in G. Simultaneously, we enumerate a sequence of open rational balls $B(s(\overline {c}),e)$ , each which intersects $N_{\mathrm {red}}$ , such that the sequence contains all balls centered at rational points belonging to $N_{\mathrm {red}}$ . If ever $s(\overline {g}) = w - e$ and $d < \sqrt {2}$ , we have determined that $w = e$ in G.

The properties (c) and (d) may fail to be computably robust for an arbitrary C*-algebra. However, in theorem above, the properties are robust in the sense that they are preserved between computably isomorphic presentations of G.

Observe if ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ has computable closed word problem, then (c) is satisfied, so $G^{\dagger }$ is computable. Similarly, if ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ has computable closed word problem, then (d) is satisfied, so $G^{\dagger }$ is computable.

Question 3.21. Is there a computable presentation $G^{\dagger }$ of a countable discrete group G such that ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ or ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ does not have computable closed word problem?

If G is amenable, then ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})} = {\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ (see [10]), so we have the following stronger characterization.

Corollary 3.22. Let G be an amenable discrete group with presentation $G^{\dagger }$ . Then $G^{\dagger }$ is computable if and only if ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})} = {\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ is computable.

For finitely generated groups, we can thus restate the theorem as follows.

Corollary 3.23. Let G be a finitely generated discrete group. Then G has solvable word problem if and only if the word problem of ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ is c.e. closed and the word problem of ${\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ is strongly co-c.e. closed for all (for some) presentations $G^{\dagger }$ of G. If in addition G is amenable, then G has solvable word problem if and only if ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})} = {\mathrm {C}^{*}_{\mathrm {red}} ({G^{\dagger }};{\mathbb {K}})}$ is computable for all (for some) presentations $G^{\dagger }$ of G.

By Boone [3] and Novikov [39], there are finitely presented groups with unsolvable word problem. If G is such a group with corresponding presentation $G^{\dagger }$ , then ${\mathrm {C}_{\mathrm {uni}}^{*} ({G^{\dagger }};{\mathbb {K}})}$ is finitely c.e. but not computable, in fact, the word problem is not even computable closed.

4 The relationship between real and complex C*-algebras

In this section, we investigate the relationship between presentations of real C*-algebras and their complexifications. The main benefit is the ability to extend results already established for real Banach algebras to real and complex C*-algebras. In particular, using a result of Melnikov and Ng [35], we show ${C({[0,1]};{\mathbb {K}})}$ is not computably categorical as a C*-algebra over $\mathbb {K}$ .

First, we include a result about presentations of abelian C*-algebras ${C_0(X;\mathbb {K})}$ induced from presentations of X. By Fact 2.6, every abelian complex C*-algebra is of this form. However, by Fact 2.7, only those abelian real C*-algebras with trivial $*$ -operation are of this form.

Definition 4.1. Given a separable metric space X, a presentation of X is a pair $(X,\overline {x})$ where $\overline {x}$ is a countable sequence of elements from X which is dense in X. The presentation $(X,\overline {x})$ is computable if $d(x_{i}, x_{j})$ is computable uniformly in i and j.

We will only really be concerned with proper metric spaces, i.e., metric spaces in which every closed ball is compact. Note proper metric spaces are both locally compact and complete.

Definition 4.2. A computable presentation $X^{\dagger }$ of a proper metric space X is computably proper if there is an effective procedure which, when given a closed rational ball K and $i \in \mathbb {N}$ , returns a finite sequence of open rational balls of radius at most $2^{-i}$ that covers K.

For those in computable analysis, this is simply a reformulation of the effective covering property for metric spaces with compact closed balls (see [21]). Furthermore, if X is compact then a computable presentation of X is computably proper if and only if it is effectively compact as defined in [22].

We extend an observation made by Tim McNicholl in [1] and include a proof.

Theorem 4.3. Let X be a separable proper metric space which admits a computably proper presentation. Then ${C_0(X;\mathbb {K})}$ admits a computable presentation as a C*-algebra over $\mathbb {K}$ . In particular, ${C_0({X};{\mathbb {R}})}$ admits a computable presentation as a real Banach space.

Proof Let $X^{\dagger } = (X,{(x_n)}_{n \in \mathbb {N}})$ be a computably proper presentation of X. For each $n \in \mathbb {N}$ , let $f_n : X \to \mathbb {K}$ be defined by $f_n(z) = \frac {1}{1 + d(x_n,z)}$ , and observe $f_n$ belongs to ${C_0(X;\mathbb {K})}$ . Since ${(f_n)}_{n \in \mathbb {N}}$ separates points and vanishes nowhere, ${\mathrm {C}_{\mathrm {gen}}^{*} ({{(f_n)}_{n \in \mathbb {N}}};{\mathbb {K}})} = C_0(X; \mathbb {K})$ by Stone–Weierstrass. Let ${C_0(X;\mathbb {K})}^{\dagger } = ({C_0(X;\mathbb {K})}, {(f_{n})}_{n \in \mathbb {N}})$ .

We show ${C_0(X;\mathbb {K})}^{\dagger }$ is computable. We are given a rational point $q(f_{\ell _1},\ldots ,f_{\ell _n})$ of ${C_0(X;\mathbb {K})}^{\dagger }$ and a positive integer $k \in \mathbb {N}$ . We must compute a rational r such that $|\left \lVert q(f_{\ell _1},\ldots ,f_{\ell _n})\right \rVert - r| < 2^{-k}$ . By Proposition 2.17, we can effectively determine $j \in \mathbb {N}$ so that, for all $z,w \in X$ , if $\max _i |f_{\ell _i}(z) - f_{\ell _i}(w)| \leq 2 ^{-j}$ , then $|q(f_{\ell _1}(z),\ldots ,f_{\ell _n}(z)) - q(f_{\ell _1}(w),\ldots ,f_{\ell _n}(w))| < 2^{-(k+1)}$ . Let M a positive integer which bounds the sum of the absolute values of the coefficients of q. Let $K = \bigcup _{i=1}^{n}\{z \in X {\colon \,} d(x_{\ell _i}, z) \leq M2^{k+1}\}$ , so K is a finite union of closed rational balls. As $X^{\dagger }$ is computably proper, we can effectively determine a sequence of open rational balls of radius at most $2^{-j}$ , centered at points $x_{\nu _{1}},\ldots ,x_{\nu _{r}}$ , such that the sequence covers K. Let $N = \max _i |q(f_{\ell _1}(x_{\nu _i}),\ldots ,f_{\ell _n}(x_{\nu _i}))|$ , so N is computable since $X^{\dagger }$ is computable.

Now, for all $z \in X$ , either there exists $x_{\nu _{m}}$ such that $d(x_{\nu _{m}}, z) < 2^{-j}$ , or $z \not \in K$ so $|q(f_{\ell _1}(z),\ldots ,f_{\ell _n}(z))| \leq 2^{-(k+1)}$ . If $d(x_{\nu _m}, z) < 2^{-j}$ , then since

$$\begin{align*}\max_i |f_{\ell_i}(x_{\nu_m}) - f_{\ell_i}(z)| = \max_{i}\bigg|\frac{d(x_{\ell_{i}}, z) - d(x_{\ell_{i}}, x_{\nu_{m}})}{(1 + d(x_{\ell_{i}}, x_{\nu_{m}}))(1 + d(x_{\ell_{i}}, z))}\bigg| \leq d(x_{\nu_m},z),\end{align*}$$

we can conclude $|q(f_{\ell _1}(z),\ldots ,f_{\ell _n}(z))| < N + 2^{-(k+1)}$ . Hence

$$\begin{align*}N \leq \left\lVert q(f_{\ell_1},\ldots,f_{\ell_n})\right\rVert \leq N + 2^{-(k+1)}.\end{align*}$$

Since N is computable, we can effectively determine a rational r such that $|\left \lVert q(f_{\ell _1},\ldots ,f_{\ell _n})\right \rVert - r| < 2^{-k}$ , as required.

If $C_0(X;\mathbb {R})$ admits a computable presentation as a real C*-algebra (real Banach algebra), then the real Banach space presentation formed from a computable sequence of the products of the special points is computable.

Now, we begin our investigation of the relationship between real C*-algebras and their complexifications.

We can easily extend our computability notions from complex C*-algebras to complex C*-algebras with an associated conjugation operation. This is, once again, an instance of the framework for arbitrary metric structures developed in [15]. Let B be a complex C*-algebra and let $\tau $ be a conjugation on B. We say $(B,\tau ,(z_{n})_{n \in \mathbb {N}})$ is a presentation of $(B,\tau )$ if $\{z_{n} {\colon \,} n \in \mathbb {N}\} \cup \{\tau (z_{n}) {\colon \,} n \in \mathbb {N}\}$ generates B as a complex C*-algebra. The rational points of $(B,\tau ,(z_{n})_{n \in \mathbb {N}})$ take the form $p(z_{i_{1}},\ldots ,z_{i_{j}};\tau (z_{i_{j+1}}),\ldots ,\tau (z_{i_{k}}))$ for $i_{1},\ldots ,i_{k} \in \mathbb {N}$ where p is a rational $*$ -polynomial in k noncommuting variables with no constant term. We can then define computable presentations and computable categoricity as we did for complex C*-algebras, where we now require isomorphisms to preserve $\tau $ .

Lemma 4.4. Let B be a complex C*-algebra and let $\tau $ be a conjugation on B. Let $A = \{b \in B {\colon \,} \tau (b) = b\}$ be the real C*-algebra determined by $(B,\tau )$ . Then any computable presentation of $(B,\tau )$ induces a computable presentation of A. Furthermore, if A is computably categorical as a real C*-algebra, then $(B,\tau )$ is computably categorical as a complex C*-algebra with conjugation.

Proof If $(B, \tau , (z_n)_{n \in \mathbb {N}})$ is a presentation of $(B,\tau )$ , then we consider the induced presentation $(A, (x_n)_{n \in \mathbb {N}})$ on A given by $x_{2n-1} = \frac {1}{2}(z_n + \tau (z_n))$ and $x_{2n} = \frac {1}{2i}(z_n - \tau (z_n))$ for $n \in \mathbb {N}$ . Let $(B,\tau )^{+}$ and $(B,\tau )^{\dagger }$ be computable presentations of $(B,\tau )$ . Let $A^{+}$ and $A^{\dagger }$ be the presentations of A induced by $(B,\tau )^{+}$ and $(B,\tau )^{\dagger }$ , respectively. Then $A^{+}$ and $A^{\dagger }$ are also computable. As A is computably categorical, there exists a computable isomorphism $\eta : A^{+} \to A^{\dagger }$ . Thus $\varphi : B^{+} \to B^{\dagger }$ , defined by $\varphi (z) = \eta \big (\frac {1}{2}(z + \tau (z))\big ) + i\eta \big (\frac {1}{2i}(z - \tau (z))\big )$ , is a computable isomorphism.

If B is abelian, then we can consider the $*$ -operation as a conjugation on B, and in this case, there is a strong converse.

Theorem 4.5. Let B be an abelian complex C*-algebra with a computable presentation. Let A be the subset of self-adjoint elements of B. Then A is a real C*-algebra, and any computable presentation of A induces a computable presentation of B. Furthermore, the following are equivalent:

1. (a) B is computably categorical as a complex C*-algebra.

2. (b) A is computably categorical as a real C*-algebra.

3. (c) A is computably categorical as a real Banach algebra.

Proof Note A is the real C*-algebra determined by $(B,*)$ . If $(A, (x_n)_{n \in \mathbb {N}})$ is a presentation of A, then we call $(B,(x_n)_{n \in \mathbb {N}})$ the induced presentation of B. Furthermore, if $(A,(x_n)_{n \in \mathbb {N}})$ is computable, then $(B,(x_n)_{n \in \mathbb {N}})$ is computable since

$$\begin{align*}\left\lVert r + is\right\rVert =\sqrt{\left\lVert(r+is)^*(r + is)\right\rVert} = \sqrt{\left\lVert r^2 + s^2\right\rVert}\end{align*}$$

for all rational points r and s of $(A,(x_n)_{n \in \mathbb {N}})$ .

(b) $\iff $ (c). This follows since $* : A \to A$ is simply the identity map.

(b) $\implies $ (a). By Lemma 4.4, if A is computably categorical as a real C*-algebra, then $(B,*)$ is computably categorical as a complex C*-algebra with conjugation. Since the conjugation on B is just the $*$ -operation, B is computably categorical as a complex C*-algebra.

(a) $\implies $ (b) Let $A^{+}$ and $A^{\dagger }$ be computable presentations of A. Let $B^{+}$ and $B^{\dagger }$ be the computable presentations on B induced by $A^{+}$ and $A^{\dagger }$ , respectively. As B is computably categorical, there exists a computable isomorphism $\varphi : B^{+} \to B^{\dagger }$ . Then $\varphi \restriction A : A^{+} \to A^{\dagger }$ is a computable isomorphism.

We can achieve a partial converse to Theorem 4.3 by extending the result, in [1], which states that a separable Stone space Z is computably metrizable if and only if ${C({Z};{\mathbb {R}})}$ has a computable presentation as a real Banach space. Here, a Stone space is a totally disconnected compact Hausdorff space, and we say a separable Stone space Z is computably metrizable if it admits a metric d such that $(Z,d)$ has a computable presentation.

Corollary 4.6. Let Z be a separable Stone space. Then the following are equivalent:

1. (a) Z is computably metrizable.

2. (b) ${C({Z};{\mathbb {R}})}$ has a computable presentation as a real Banach space.

3. (c) ${C({Z};{\mathbb {R}})}$ has a computable presentation as a real C*-algebra.

4. (d) ${C({Z};{\mathbb {C}})}$ has a computable presentation as a complex C*-algebra.

Proof (a) $\iff $ (b) is the result in [1].

(c) $\iff $ (d) was established above.

As shown in [19], every computably metrizable Stone space has a computably compact presentation. By Theorem 4.3, (a) $\implies $ (d).

Finally, (c) $\implies $ (b) follows by taking any real C*-algebra presentation which is computable and considering a computable sequence of the products of the special points.

We also have the following.

Corollary 4.7. ${C({[0,1]};{\mathbb {K}})}$ is not computably categorical as a C*-algebra over $\mathbb {K}$ .

Proof By Theorem 4.5, ${C({[0,1]};{\mathbb {K}})}$ is computably categorical as a C*-algebra over $\mathbb {K}$ if and only if ${C({[0,1]};{\mathbb {R}})}$ is computably categorical as a real Banach algebra. Melnikov and Ng showed in [35] that ${C({[0,1]};{\mathbb {R}})}$ is not computably categorical in the language of real Banach algebras.

This lies in contrast to the group situation, where every finitely generated group that admits a computable presentation is computably categorical (see [27]), since ${C({[0,1]};{\mathbb {K}})}$ is finitely generated with a computable presentation, even one that is finitely c.e. as witnessed by

$$\begin{align*}{C({[0,1]};{\mathbb{K}})} \cong {\mathrm{C}^{*} \langle{1,x}\operatorname{\mathrm{|}}{\operatorname{\mathrm{Iden}}(1;x),x=x^{*},\left\lVert x\right\rVert \leq 1, \left\lVert1 - x\right\rVert \leq 1};{\mathbb{K}}\rangle} , \end{align*}$$

but is not computably categorical.

5 Computable categoricity of finite-dimensional C*-algebras

Although Corollary 4.7 introduces a divergence between computable categoricity results for C*-algebras and for groups, in this section, we establish that finite-dimensional C*-algebras are, as one would expect, computably categorical.

The following is folklore for computable unital presentations, but since we may not have a unit we have to work a little harder.

Lemma 5.1. Let A be a C*-algebra over $\mathbb {K}$ with computable presentation $A^{\dagger }$ . Let x be a computable point of $A^{\dagger }$ which is self-adjoint and has finite spectrum $\sigma (x)$ . Then every element of $\sigma (x)$ is computable.

Proof We proceed by induction on the size of $\sigma (x) \setminus \{0\}$ . Clearly, if $\operatorname {\mathrm {card}}(\sigma (x) \setminus \{0\}) = 0$ , then $\sigma (x) = \{0\}$ where $0$ is computable.

Otherwise, let $u \in \sigma (x) \setminus \{0\}$ be such that $|u| = \max _{t \in \sigma (x)} |t| = \left \lVert x\right \rVert $ , so u is computable. Let $p(z) = z(z-u) \in \mathbb {R}[z]$ . Then $p(x) = x^2 - ux$ is a self-adjoint computable point of $A^{\dagger }$ and

$$\begin{align*}\operatorname{\mathrm{card}}(\sigma(p(x)) \setminus \{0\}) = \operatorname{\mathrm{card}}(p[\sigma(x)] \setminus \{0\}) < \operatorname{\mathrm{card}}(\sigma(x) \setminus \{0\}).\end{align*}$$

By the inductive hypothesis, every element of $\sigma (p(x))$ is computable. Since $\sigma (p(x)) = p[\sigma (x)]$ , every element of $\sigma (x)$ is a real root of the computable polynomial $p(z) - w \in \mathbb {R}[z]$ for some $w \in \sigma (p(x))$ . It is well known that the computable reals form a real closed field (see [40] for details). Thus every element of $\sigma (x)$ is computable.

With this, we are ready to show computable categoricity for finite-dimensional abelian real and complex C*-algebras.

Theorem 5.2. Every finite-dimensional abelian real C*-algebra is computably categorical as a real C*-algebra.

Proof Let A be an abelian finite-dimensional real C*-algebra, and let $A^{\dagger }$ be a computable presentation of A. By Fact 2.5, we can identify A with $\mathbb {R}^k \oplus \mathbb {C}^m$ for some positive integers k and m.

Let X be the set of self-adjoint rational points of $A^{\dagger }$ , and let Y be the set of skew-adjoint rational points of $A^{\dagger }$ , so the set of rational points of $A^{\dagger }$ is $X + Y$ . We know X is dense in $\mathbb {R}^{k}\oplus \mathbb {R}^{m}$ and Y is dense in $\{0\}^k \oplus {(i\mathbb {R})}^m$ . In particular, there must exist $x \in X$ such that x has distinct nonzero entries, and $y \in Y$ such that only the first k entries are zero. We view $\mathbb {R}^{k} \oplus \mathbb {R}^{m}$ as a subspace of ${B({\mathbb {R}^{k} \oplus \mathbb {R}^{m}};{\mathbb {R}})}$ where $\mathbb {R}^{k} \oplus \mathbb {R}^{m}$ acts on itself by multiplication. In this sense, the minimal polynomial of x must be of degree $k+m$ with a nonzero constant term. Then $x,\ldots ,x^{k+m}$ are linearly independent over $\mathbb {R}$ , so ${\mathrm {C}_{\mathrm {gen}}^{*} ({x};{\mathbb {R}})} = \mathbb {R}^{k}\oplus \mathbb {R}^{m}$ . Also, we can find $z \in \mathbb {R}^{k} \oplus \mathbb {R}^{m}$ such that the last m entries of $zy$ are i. Hence ${\mathrm {C}_{\mathrm {gen}}^{*} ({x,y};{\mathbb {R}})} = \mathbb {R}^k \oplus \mathbb {C}^m$ . By Corollary 2.19, $(A,x,y)$ is a computable presentation computably isomorphic to $A^{\dagger }$ via the identity map.

The entries of an element $z \in A$ belong to $\sigma _{A}(z)$ since if $a + ib$ is an entry of z for some $a,b \in \mathbb {R}$ , then $(z - a)^{2} + b^{2}$ is not invertible in A. Every element of $\sigma (x)$ is computable by Lemma 5.1, so in particular, every entry of x is computable. Similarly, $y^2$ is self-adjoint, so by Lemma 5.1, every element of $\sigma (y^2)$ is computable. Then every element of $\sigma (y)$ is computable, since $\sigma (y^2) = \sigma (y)^2$ , and the computable complex numbers form an algebraically closed field (see [44] for details). In particular, every entry of y is computable. Thus, by Corollary 2.19, $(A,x,y)$ is computably isomorphic to the standard presentation $\mathbb {R}^k \oplus \mathbb {C}^m$ .

Corollary 5.3. Every finite-dimensional abelian complex C*-algebra is computably categorical as a complex C*-algebra.

Proof By Fact 2.4, any abelian finite-dimensional C*-algebra can be identified with $\mathbb {C}^n$ for some $n \in \mathbb {N}$ . It can be observed, with the use of Theorem 4.5, that $\mathbb {C}^n$ is computably categorical as a complex C*-algebra if and only if $\mathbb {R}^n$ is computably categorical as real C*-algebra.

Since $\mathbb {H}$ is one of the building blocks of finite-dimensional real C*-algebras, but is not abelian, we separately show it is computably categorical.

Lemma 5.4. $\mathbb {H}$ is computably categorical as a real C*-algebra.

Proof Let $\mathbb {H}^{\dagger }$ be a computable presentation of $\mathbb {H}$ .

For any nonzero self-adjoint computable point x of $\mathbb {H}^{\dagger }$ , we know $x \in \mathbb {R}$ , and $\left \lVert x\right \rVert $ is computable. Hence $1 = \operatorname {\mathrm {sgn}}(x)\frac {x}{\left \lVert x\right \rVert }$ is a computable point of $\mathbb {H}^{\dagger }$ .

We apply the Gram–Schmidt process to a pair of $\mathbb {R}$ -linearly independent skew-adjoint computable points of $\mathbb {H}^{\dagger }$ , noting that $\langle a,b\rangle _{\mathbb {R}} = \frac {1}{2}(a^*b + b^*a)$ is a computable operation, to get a pair $p,q$ of $\mathbb {R}$ -orthonormal skew-adjoint computable points of $\mathbb {H}^{\dagger }$ .

Then $p^2 = -p^*p = -1 = -q^*q = q^2$ , and $0 = \langle p, q \rangle _{\mathbb {R}} = -\frac {1}{2}(pq + qp)$ so $pq = -qp$ . Thus there is an automorphism $\varphi $ of $\mathbb {H}$ which sends $1 \mapsto 1$ , $p \mapsto i$ , $q \mapsto j$ , and $pq \mapsto k$ . By Corollary 2.19, $(\mathbb {H},1,p,q)$ is a computable presentation computably isomorphic to $\mathbb {H}^{\dagger }$ . Therefore, $\varphi $ is a computable isomorphism from $\mathbb {H}^{\dagger }$ to the standard presentation $\mathbb {H}$ .

From the rigid characterization of subalgebras generated by a self-adjoint element, we are able to find a finite set of computable minimal projections which spans the set of self-adjoint elements.

Let A be a C*-algebra over $\mathbb {K}$ with computable presentation $A^{\dagger }$ . Let p be a computable projection in $A^{\dagger }$ . Then $pAp$ is a C*-algebra over $\mathbb {K}$ , and $A^{\dagger }$ induces a presentation $pA^{\dagger }p$ on $pAp$ formed from the products $pz_{1}\cdots z_{n}p$ where $z_{1},\ldots ,z_{n}$ are special points of $A^{\dagger }$ . By Proposition 2.18, $pA^{\dagger }p$ is a computable presentation of $pAp$ and the inclusion map from $pA^{\dagger }p$ to $A^{\dagger }$ is computable.

Theorem 5.5. Let A be a finite-dimensional C*-algebra over $\mathbb {K}$ with computable presentation $A^{\dagger }$ . Then there is a finite set M of computable minimal projections in $A^{\dagger }$ such that ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M})}$ is the set of self-adjoint elements of A.

Proof We proceed by induction on the $\mathbb {K}$ -dimension of A. Let X be the set of self-adjoint elements of A. Let Z be the subset of $A^{\dagger }$ -computable points of X, so Z is dense in X.

For $z \in Z$ , ${\mathrm {C}_{\mathrm {gen}}^{*} ({z};{\mathbb {K}})} \cong \mathbb {K}^n$ for some $n \in \mathbb {N}$ . By Theorem 5.2 or Corollary 5.3, $\mathbb {K}^{n}$ is computably categorical as a C*-algebra over $\mathbb {K}$ . In particular, there must be a family F of minimal projections in ${\mathrm {C}_{\mathrm {gen}}^{*} ({z};{\mathbb {K}})}$ , each computable with respect to $({\mathrm {C}_{\mathrm {gen}}^{*} ({z};{\mathbb {K}})},z)$ , such that $z \in {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({F})}$ . Since every projection in F is computable with respect to $({\mathrm {C}_{\mathrm {gen}}^{*} ({z};{\mathbb {K}})},z)$ , they must be also computable with respect to $A^{\dagger }$ by Proposition 2.18.

If $1$ is a minimal projection in A, then $X = \mathbb {R} = {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({1})}$ and $1$ is $A^{\dagger }$ -computable. In that case, we just let $M = \{1\}$ .

Suppose $1$ is not a minimal projection in A. Then there exists $z \in Z$ such that ${\mathrm {C}_{\mathrm {gen}}^{*} ({z};{\mathbb {K}})}$ is not isomorphic to $\mathbb {K}$ , so must contain a copy of $\mathbb {K} \oplus \mathbb {K}$ . Hence, there is a nontrivial computable projection q in $A^{\dagger }$ . Let N be the set of all nontrivial projections computable with respect to $A^{\dagger }$ . If $1$ is $A^{\dagger }$ -computable, then $1 - q \in N$ , so ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({N})} = {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({N \cup \{1\}})} = {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({Z})} = X$ . If $1$ is not $A^{\dagger }$ -computable, we directly see ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({N})} = {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({Z})} = X$ .

Let K be a finite subset of N such that ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({K})} {\kern-1.5pt}={\kern-1.5pt} {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({N})} {\kern-1.5pt}={\kern-1.5pt} X$ . For any $p {\kern-1.5pt}\in{\kern-1.5pt} K$ , $pAp$ is a C*-subalgebra of A over $\mathbb {K}$ of strictly less dimension. By the inductive hypothesis, there is a finite set $M_p$ of computable minimal projections in $pA^{\dagger } p$ such that ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M_p})}$ is the set of self-adjoint elements of $pAp$ . In particular, $p \in {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M_p})}$ . Every projection r which is minimal in $pAp$ is also minimal in A since for $t \in A$ if $t \leq r$ , then $t \leq p$ , so $t \in pAp$ . Also, each $r \in M_p$ is computable with respect to $A^{\dagger }$ . If we let $M = \bigcup _{p \in K} M_p$ , then M satisfies the required conditions.

As an immediate application, we can reduce the computable categoricity of a direct sum to the computable categoricity of its summands.

Let A and B be C*-algebras over $\mathbb {K}$ with computable presentations $A^{\dagger }$ and $B^{\dagger }$ , respectively. These presentations induce a computable presentation $A^{\dagger }\oplus B^{\dagger }$ on $A \oplus B$ formed from points $(z,0)$ and $(0,w)$ where z is a special point of $A^{\dagger }$ and w is a special point of $B^{\dagger }$ .

Theorem 5.6. Let A and B be finite-dimensional C*-algebras over $\mathbb {K}$ which are computably categorical as C*-algebras over $\mathbb {K}$ . Then $A \oplus B$ is computably categorical as a C*-algebra over $\mathbb {K}$ .

Proof Let ${(A \oplus B)}^+$ be a computable presentation of $A \oplus B$ . By Theorem 5.5, there is a finite set M of computable minimal projections in ${(A \oplus B)}^+$ such that ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M})}$ is the set of self-adjoint elements of $A \oplus B$ . Any minimal projection in $A \oplus B$ must belong to either A or B by minimality. For $X = A$ or $X = B$ , let $M_{X}$ be the subset of M which belongs to X. Also, let $Z_{X}$ be the set of products $qz_{1} \cdots z_{n}p$ where $z_{1},\ldots ,z_{n}$ are special points of $(A \oplus B)^{+}$ and $p,q \in M_{X}$ . Note $Z_A \subseteq A$ and $Z_B \subseteq B$ . Since $1 \in {\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M})}$ , we have ${\mathrm {C}_{\mathrm {gen}}^{*} ({Z_A \cup Z_B};{\mathbb {K}})} = A \oplus B$ . Hence ${\mathrm {C}_{\mathrm {gen}}^{*} ({Z_A};{\mathbb {K}})} = A$ and ${\mathrm {C}_{\mathrm {gen}}^{*} ({Z_B};{\mathbb {K}})} = B$ . Then $(A, Z_A)$ and $(B, Z_B)$ are computable presentations of A and $B,$ respectively, by Proposition 2.18, and $(A,Z_{A}) \oplus (B,Z_{B})$ is a computable presentation computably isomorphic to $(A \oplus B)^{+}$ by Corollary 2.19.

Let $A^{\dagger }$ and $B^{\dagger }$ be computable presentations of A and $B,$ respectively. Since A is computably categorical, there exists a computable isomorphism $\varphi $ from $A^{\dagger }$ to $(A, Z_A)$ . Similarly, since B is computably categorical, there exists a computable isomorphism $\psi $ from $B^{\dagger }$ to $(B, Z_B)$ . Then $\varphi \oplus \psi : A^{\dagger } \oplus B^{\dagger } \to {(A \oplus B)}^+$ is a computable isomorphism.

Thus, by Facts 2.4 and 2.5, in order to prove computable categoricity for arbitrary finite-dimensional C*-algebras, it suffices to consider the matrix algebras. We would like to induct on the dimension of the matrix algebra, but first we need a way to access matrix algebras of smaller dimension.

Let $\mathbb {D}$ denote $\mathbb {R}$ , $\mathbb {H}$ , or $\mathbb {C}$ as a C*-algebra over corresponding $\mathbb {K}$ .

Lemma 5.7. Let $\mathcal {H}$ be a Hilbert space over $\mathbb {D}$ . Let ${(p_i)}_{i=1}^n$ be a sequence of minimal projections in ${B({\mathcal {H}};{\mathbb {D}})} $ . If $p_{m+1}$ does not commute with $q_m := \bigvee _{i=1}^m p_i$ for any $1 \leq m < n$ , then ${\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^n p_i{B({\mathcal {H}};{\mathbb {D}})} p_i};{\mathbb {K}})} \cong M_n(\mathbb {D})$ .

Proof We proceed by induction on the length of the sequence. We denote ${B({\mathcal {H}};{\mathbb {D}})} $ by A for clarity.

It can be observed that ${\mathrm {C}_{\mathrm {gen}}^{*} ({pAp};{\mathbb {K}})} = pAp = {B({p\mathcal {H}};{\mathbb {D}})} \cong \mathbb {D}$ for any minimal projection p in A.

Now, let ${(p_i)}_{i=1}^{n+1}$ be as stated such that ${\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^n p_i A p_i};{\mathbb {K}})} \cong M_n(\mathbb {D})$ . Since $M_n(\mathbb {D}) \cong {\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^n p_i A p_i};{\mathbb {K}})} \subseteq {B({q_n\mathcal {H}};{\mathbb {D}})}$ , by dimensionality we must have $\mathrm {C}_{\mathrm {gen}}^{*} (\bigcup _{i=1}^n p_i A p_i;{\mathbb {K}}) = {B({q_n\mathcal {H}};{\mathbb {D}})}$ . Then $q_n$ must be of $\mathbb {D}$ -rank n, so $q_{n+1}$ is of $\mathbb {D}$ -rank $n+1$ as $p_{n+1}$ does not commute with $q_n$ . Hence

$$\begin{align*}{\mathrm{C}_{\mathrm{gen}}^{*} \bigg(\kern2pt{\bigcup_{i=1}^{n+1} p_i A p_i};{\mathbb{K}} \bigg)} \subseteq {B({q_{n+1}\mathcal{H}};{\mathbb{D}})} \cong M_{n+1}(\mathbb{D}). \end{align*}$$

For each $a \in \mathbb {D}$ , we let $R_{a} : \mathcal {H} \to \mathcal {H}$ be multiplication on the right by a. Let $w \in {B({q_{n+1}\mathcal {H}};{\mathbb {K}})}$ commute with ${\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^{n+1} p_i A p_i};{\mathbb {K}})}$ . In particular, $wq_n$ belongs to the commutant of ${B({q_n\mathcal {H}};{\mathbb {D}})}$ in ${B({q_n\mathcal {H}};{\mathbb {K}})}$ , so is of the form $R_x q_n$ for some $x \in \mathbb {D}$ . Also, $wp_{n+1}$ belongs to the commutant of ${B({p_{n+1}\mathcal {H}};{\mathbb {D}})} = p_{n+1}Ap_{n+1}$ in ${B({p_{n+1}\mathcal {H}};{\mathbb {K}})}$ , so is of the form $R_y p_{n+1}$ for some $y \in \mathbb {D}$ . As w commutes with $p_{n+1}$ , we have that

$$\begin{align*}R_x p_{n+1}q_n = p_{n+1}R_x q_n = p_{n+1}wq_n = wp_{n+1}q_n = R_y p_{n+1}q_n.\end{align*}$$

Since $p_{n+1}$ does not commute with $q_n$ , $p_{n+1}q_n$ is nonzero, so $x = y$ . Then $w = R_{x}q_{n+1}$ since $q_{n+1}\mathcal {H} = p_{n+1}\mathcal {H} + q_n\mathcal {H}$ . Hence w commutes with ${B({q_{n+1}\mathcal {H}};{\mathbb {D}})}$ . Thus, by Definition 2.13,

$$\begin{align*}{\mathrm{C}_{\mathrm{gen}}^{*} \bigg({\bigcup_{i=1}^{n+1} p_i A p_i}; {\mathbb{K}}\bigg)} = {\mathrm{C}_{\mathrm{gen}}^{*} \bigg({\bigcup_{i=1}^{n+1}p_i A p_i};{\mathbb{K}} \bigg)}" = {B({q_{n+1}\mathcal{H}};{\mathbb{D}})}" = {B({q_{n+1}\mathcal{H}};{\mathbb{D}})} .\end{align*}$$

Now, we are ready to show matrix algebras are computably categorical.

We identify $M_n(\mathbb {D})$ with the collection of matrices in $M_{n+1}(\mathbb {D})$ which have all zeros in their last column and row.

Theorem 5.8. $M_n(\mathbb {D})$ is a computably categorical C*-algebra over $\mathbb {K}$ .

Proof We proceed by induction on n.

Observe $\mathbb {D}$ is computably categorical as a C*-algebra over $\mathbb {K}$ by Theorem 5.2, Corollary 5.3, or Lemma 5.4.

Now, assume $M_{n}(\mathbb {D})$ is computably categorical. For ease of reading, we denote $M_{n+1}(\mathbb {D})$ by A. Let $A^{\dagger }$ be a computable presentation of A.

To make use of the inductive hypothesis, we determine a subalgebra B isomorphic to $M_{n}(\mathbb {D})$ which is computably included in $A^{\dagger }$ . By Theorem 5.5, there is a finite set M of computable minimal projections in $A^{\dagger }$ such that ${\operatorname {\mathrm {span}}_{{\mathbb {R}}}({M})}$ is the set of self-adjoint elements of A. We construct a sequence $(p_i)_{i=1}^{n+1}$ of minimal projections from M so that $p_{k+1}$ does not commute with $q_k$ for $1 \leq k < n+1$ , where $q_k = \bigvee _{i=1}^k p_i$ . Choose $p_1 \in M$ . Suppose we have constructed $(p_i)_{i=1}^k$ for some $k \leq n$ . If $q_k$ commutes with every projection in M, then $q_k$ commutes with every self-adjoint element of A, so $q_{k} = dI$ for some nonzero $d \in \mathbb {D}$ . However, $q_k$ has rank at most k, while $dI$ has rank $n+1$ . Thus, we may choose $p_{k+1} \in M$ which does not commute with $q_k$ . Let $B = {\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^n p_iAp_i};{\mathbb {K}})}$ . Let $B^{\dagger }$ be the presentation of B formed from the special points of $p_1A^{\dagger }p_{1},\ldots ,p_nA^{\dagger }p_{n}$ . Then $B^{\dagger }$ is computable and the inclusion from $B^{\dagger }$ into $A^{\dagger }$ is computable by Proposition 2.18. By Lemma 5.7, we have ${\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^{n+1} p_iAp_i};{\mathbb {K}})} \cong M_{n+1}(\mathbb {D})$ and $B \cong M_n(\mathbb {D})$ . Hence ${\mathrm {C}_{\mathrm {gen}}^{*} ({\bigcup _{i=1}^{n+1} p_iAp_i};{\mathbb {K}})} = A$ and $B = {B({q_n\mathbb {D}^{n+1}};{\mathbb {D}})}$ .

Let Z be the standard orthonormal basis of $\mathbb {D}$ over $\mathbb {K}$ . By the inductive hypothesis, $M_n(\mathbb {D})$ is computably categorical over $\mathbb {K}$ . In particular, there is a system of matrix units $(f^z_{kj} {\colon \,} 1 \leq k,j \leq n, z \in Z)$ , computable with respect to $B^{\dagger }$ so computable with respect to $A^{\dagger }$ , such that $B = {\mathrm {C}_{\mathrm {gen}}^{*} ({\{f^z_{kj} {\colon \,} 1 \leq k,j \leq n, z \in Z\}};{\mathbb {K}})}$ .

Let $(e^z_{kj} {\colon \,} 1 \leq k,j \leq n+1, z \in Z)$ be the standard system of matrix units for $M_{n+1}(\mathbb {D})$ . We find a unitary U in $M_{n+1}(\mathbb {D})$ such that $U^{*}f_{kj}^{z}U = e^{z}_{kj}$ for $1 \leq k,j \leq n$ and $z \in Z$ . To that end, observe we can extend a $\mathbb {D}$ -orthonormal basis on $(\sum _{k=1}^n f_{kk})(\mathbb {D}^{n+1})$ to one for $\mathbb {D}^{n+1}$ , so there exists a unitary $V \in M_{n+1}(\mathbb {D})$ such that $V^*BV = M_n(\mathbb {D})$ . Then $(V^*f^z_{kj}V {\colon \,} 1 \leq k,j \leq n, z\in Z)$ forms a system of matrix units for $M_n(\mathbb {D})$ . Before we find U, we show there exists a unitary u in $M_{n}(\mathbb {D})$ such that $u^{*}V^{*}f^{z}_{kj}Vu = e^{z}_{kj}$ for $1 \leq k,j \leq n$ and $z \in Z$ . There are two cases. If the center of $\mathbb {D}$ is $\mathbb {K}$ , then u exists by Corollary 2.21. If the center of $\mathbb {D}$ is not $\mathbb {K}$ , it must be that $\mathbb {D} = \mathbb {C}$ , $\mathbb {K} = \mathbb {R}$ , and $Z = \{1,i\}$ . Then $\sum _{k=1}^{n} V^*f_{kk}^i V$ belongs to the center of $M_{n}(\mathbb {C})$ , and ${(\sum _{k=1}^{n} V^*f_{kk}^i V)}^2 = -I$ , so $\sum _{k=1}^{n} V^*f_{kk}^i V = \pm i$ . By possibly replacing $f_{kj}^i$ by their negations for $1 \leq k,j \leq n$ , we may assume $\sum _{k=1}^{n} f_{kk}^i = i$ . Then there exists a unitary matrix $u \in M_n(\mathbb {C})$ such that $u^*V^*f_{kj}Vu = e_{kj}$ for $1 \leq k,j \leq n$ , hence $u^*V^*f_{kj}^z Vu = e^z_{kj}$ for $1 \leq k,j \leq n$ and $z \in Z$ . For both cases, we let $U = V(u + e_{(n+1)(n+1)})$ .

Using U, we show we can construct a system of matrix units for A that is computable with respect to $A^{\dagger }$ . As $U^*p_{n+1}U$ is a projection which does not commute with the identity in $M_n(\mathbb {D})$ , there must exist $1 \leq \ell \leq n$ such that the $(n+1,\ell )$ th entry of $U^*p_{n+1}U$ is nonzero. For $z \in Z$ , let $w_z = p_{n+1}f_{\ell \ell }^z - \sum _{k=1}^n f_{kk}p_{n+1}f_{\ell \ell }^z$ . Then there exists a nonzero $d \in \mathbb {D}$ such that $U^*w_z U = d e^z_{(n+1)\ell }$ for $z \in Z$ . Note $\left \lVert d\right \rVert = \left \lVert w_1\right \rVert $ is computable. Now, we are ready to extend the system of matrix units. For $z \in Z$ , let

$$ \begin{align*} f^z_{(n+1)k} &= \frac{1}{\left\lVert d\right\rVert} w_z f_{\ell k} \text{ for } 1 \leq k \leq n,\\ f^z_{k(n+1)} &= \frac{1}{\left\lVert d\right\rVert} f^z_{k\ell}w_1^* \text{ for } 1 \leq k \leq n,\\ \text{and } f^z_{(n+1)(n+1)} &= \frac{1}{\left\lVert d\right\rVert^2}w_z w_1^*. \end{align*} $$

Then for $z \in Z$ , we observe

$$ \begin{align*} U^*f^z_{ij}U &= e^z_{kj} \text{ for } 1 \leq k,j \leq n,\\ U^*f^z_{(n+1)k}U &= \frac{d}{\left\lVert d\right\rVert}e^z_{(n+1)k} \text{ for } 1 \leq k \leq n,\\ U^*f^z_{k(n+1)}U &= e^z_{k(n+1)}\frac{d^*}{\left\lVert d\right\rVert} \text{ for } 1 \leq k \leq n,\\ \text{and } U^*f^z_{(n+1)(n+1)}U &= \frac{d}{\left\lVert d\right\rVert}e^z_{(n+1)(n+1)}\frac{d^*}{\left\lVert d\right\rVert}. \end{align*} $$

We only need to tweak our unitary conjugation. Let $x_{1},\ldots ,x_{n+1}$ be the standard $\mathbb {D}$ -orthonormal basis for $\mathbb {D}^{n+1}$ . If $W \in M_{n+1}(\mathbb {D})$ is the unitary matrix which sends $x_{i}$ to itself for $1 \leq i \leq n$ and sends $x_{n+1}$ to $x_{n+1}\frac {d}{\left \lVert d\right \rVert }$ , then ${(UW)}^*f^z_{kj}UW = e^z_{kj}$ for $1 \leq k,j \leq n+1$ and $z \in Z$ . Note each member of $(f^z_{kj} {\colon \,} 1 \leq k,j \leq n+1, z \in Z)$ is computable with respect to $A^{\dagger }$ , so by Corollary 2.19, $(A, (f^{z}_{kj} {\colon \,} 1 \leq k,j \leq n+1, z \in Z))$ is computably isomorphic to $A^{\dagger }$ via the identity map. Thus conjugation by $UW$ gives a computable isomorphism from $A^{\dagger }$ to the standard presentation $M_{n+1}(\mathbb {D})$ .

Corollary 5.9. Every finite-dimensional C*-algebra over $\mathbb {K}$ is computably categorical as a C*-algebra over $\mathbb {K}$ .

Since the identity is computable with respect to the standard presentation of any finite-dimensional C*-algebra, and automorphisms preserve the identity, we also have the following.

Corollary 5.10. Let A be a finite-dimensional C*-algebra over $\mathbb {K}$ . The identity is computable with respect to any computable presentation of A, and A is computably categorical as a unital C*-algebra over $\mathbb {K}$ .

Acknowledgements

We would like to thank Isaac Goldbring and Tim McNicholl for their truly invaluable feedback on earlier drafts of the manuscript. We would also like to thank the anonymous referee from this journal who suggested many improvements.