Blog Archives

Topic Archive: decidability

CUNY Logic WorkshopFriday, November 13, 20152:00 pmGC 6417

Philipp Hieronymi

Diophantine approximation, scalar multiplication and decidability

University of Illinois Urbana-Champaign

It has long been known that the first order theory of the expansion (R,<,+,Z) of the ordered additive group of real numbers by just a predicate for the set of integers is decidable. Arguably due to Skolem, the result can be deduced easily from Buechi's theorem on the decidability of monadic second order theory of one successor, and was later rediscovered independently by Weispfenning and Miller. However, a consequence of Goedel's famous first incompleteness theorem states that when expanding this structure by a symbol for multiplication, the theory of the resulting structure (R,<,+,*,Z) becomes undecidable. This observation gives rise to the following natural and surprisingly still open question: How many traces of multiplication can be added to (R,<,+,Z) without making the first order theory undecidable? We will give a complete answer to this question when "traces of multiplication" is taken to mean scalar multiplication by certain irrational numbers. To make this statement precise: for b in R, let f_b: R -> R be the function that takes x to bx. I will show that the theory of (R,<,+,Z,f_b) is decidable if and only if b is quadratic. The proof rests on the observation that many of the Diophantine properties (in the sense of Diophantine approximation) of b can be coded in these structures.

CUNY Logic WorkshopFriday, September 20, 20132:00 pm

Isaac Goldbring

A survey of the model theory of tracial von Neumann algebras

University of Illinois Chicago

Von Neumann algebras are certain algebras of bounded operators on Hilbert spaces. In this talk we will survey some of the model theoretic results about (tracial) von Neumann algebras, focusing mainly on (in)stability, quantifier-complexity, and decidability. No prior knowledge of von Neumann algebras will be necessary. Some of the work presented is joint with Ilijas Farah, Bradd Hart, David Sherman, and Thomas Sinclair.