Blog Archives

Topic Archive: interpretation

CUNY Logic WorkshopFriday, December 5, 20142:00 pmGC 6417

Russell Miller

Computable functors and effective interpretations

City University of New York

We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories C and D whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor F from C to D should be effective: given a structure M from C as an oracle, it should compute the structure F(M) in D, and given a C-morphism g from M to N as an oracle, it should compute the D-morphism F(g) from F(M) to F(N). Moreover, one would hope for F to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an F to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.

Recent joint work by Harrison-Trainor, Melnikov, Montalbán, and the speaker has established that computable functors are closely connected to Montalban’s notion of effective interpretation of one class C of countable structures in another class D. We will explain the connections and discuss the extent to which they realize the model-theorist’s suspicion that functors are really just another version of interpretations.

Model theory seminarFriday, November 22, 201312:30 pm

Alice Medvedev

Dividing and conquering: locally definable sets as stand-alone structures

City College -- CUNY

In what sense is the ring of polynomials in one variable over a field k interpretable in k? In what sense is the subgroup of G generated by a definable subset D of G interpretable in G? These questions have been answered in various particular contexts by various people. We set up a general formalism to treat such piece-wise interpreted objects as stand-alone multi-sorted first-order structures. This formalism is motivated by our quest to create a model-theoretically tractable analog of sheaf theory. This is a very preliminary report on joint work with Ramin Takloo-Bighash.