Blog Archives

Topic Archive: Automorphisms

CUNY Logic WorkshopFriday, May 15, 20152:00 pmGC 6417

Rebecca M. Steiner

Effective symmetry breaking

Vanderbilt University

Symmetry breaking involves the coloring of elements of a structure so that the only automorphism of the structure which respects the coloring is the trivial one. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize to n-colorings for fixed n and for variable n. Then, we suppose the tree is no longer finite branching, and we observe what happens to the difficulty of computing a 2-coloring.

Andrey Morozov
Sobolev Institute of Mathematics, Novosibirsk State University
Prof. Andrey Morozov received his doctorate in 1983, as a student of Sergey Goncharov at Novosibirsk State University, Russia. Since then he has risen to serve as Head of the Laboratory of Logical Systems at Novosibirsk, and has held assorted visiting positions in other countries during that time as well. He studies computability theory, with a focus on Sigma-definability and computable model theory.
CUNY Logic WorkshopFriday, April 25, 20142:00 pmGC 6417

Alf Dolich

Maximal Automorphisms

The City University of New York

Given a model M, a maximal automorphism is one which fixes as few points in M as possible. We begin by outlining what the correct definition of “as few points as possible” should be and then proceed to study the notion. An interesting question arises when one considers the existence of maximal automorphisms of countable recursively saturated models. In particular an interesting dichotomy arises when one asks whether for a given theory T all countable recursively saturated models of T have a maximal automorphism. Our primary goal is to determine which classes of theories T lie on the positive side of this dichotomy. We give several examples of such classes. Attacking this problem requires a detailed understanding of recursive saturation, which we will also review in this talk.