Abstract
Approximately finite-dimensional (AF) C⋆-algebras were introduced in 1972 by Bratteli, generalizing earlier work of Glimm and Dixmier. In a recent paper, the author presents a natural one-one correspondence between Lindenbaum algebras of the infinite-valued sentential calculus of Łukasiewicz, and AF C⋆-algebras whose Grothendieck group (KO) is lattice-ordered. Thus, any such algebra \(\mathfrak{A}\) can be encoded by some theory Φ in the Łukasiewicz calculus, and Φ uniquely determines \(\mathfrak{A}\), up to isomorphism. In the present paper, Glimm's universal UHF algebra, the Canonical Anticommutation Relation (CAR) algebra, and the Effros-Shen algebras corresponding to quadratic irrationals are explicitly coded by theories whose decision problems are solvable in deterministic polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bratteli O (1972) Inductive limits of finite dimensional C⋆-algebras. Trans Amer Math Soc 171: 195–234
Chang C C (1958) Algebraic analysis of many valued logics. Trans Amer Math Soc 88: 467–490
Cook S A (1971) The complexity of theorem proving procedures. In: Proceedings 3rd ACM Symp on Theory of Computing, pp. 151–158
Effros E G (1981) Dimensions and C⋆-algebras. CBMS Regional Conference Series in Math. vol 46 AMS, Providence RI
Effros E G,Rosenberg J (1978) C⋆-algebras with approximately inner flip. Pacific J Math 77: 417–443
Effros E G, Shen C-L (1980) Approximately finite C⋆-algebras and continued fractions. Indiana Univ Math J 29: 191–204
Garey M R, Johnson D S (1979) Computers and Intractability. W H Freeman, San Francisco
Glimm J G (1960) On a certain class of operator algebras. Trans Amer Math Soc 95: 318–340
Knuth D E (1981) The Art of Computer Programming. Seminumerical Algorithms, vol 2. Addison-Wesley, Reading, MA
Lang S (1966) Introduction to Diophantine Approximations. Addison-Wesley, Reading MA
McNaughton R (1951) A theorem about infinite-valued logic. J Symbolic Logic 16: 1–13
Mundici D (1986) Interpretation of AF C⋆-algebras in Łukasiewicz sentential calculus. J Functional Analysis 65: 15–63
Tarski A, Łukasiewicz J (1956) Investigations into the Sentential Calculus. In: Logic, Semantics, Metamathematics. Oxford University Press, Oxford, pp. 38–59.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Mundici, D. (1987). The Turing complexity of AF C*-algebras with lattice-ordered KO . In: Börger, E. (eds) Computation Theory and Logic. Lecture Notes in Computer Science, vol 270. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18170-9_171
Download citation
DOI: https://doi.org/10.1007/3-540-18170-9_171
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18170-5
Online ISBN: 978-3-540-47795-2
eBook Packages: Springer Book Archive