May 6
Alexei Miasnikov,
Stevens Institute of Technology
Rich algebraic structures and weak second order logic
“What can one describe by first-order formulas in a given algebraic structure A?” - is an old and interesting question. Of course, this depends on the structure A. For example, in a free group only cyclic subgroups (and the group itself) are definable in the first-order logic, but in a free monoid of finite rank any finitely generated submonoid is definable. An algebraic structure A is called rich if the first-order logic in A is equivalent to the weak second order logic. Surprisingly, there are a lot of interesting groups, rings, semigroups, etc., which are rich. I will discuss some of them and then describe various algebraic, geometric, and algorithmic properties that are first-order definable in rich structures and apply these to some open problems. Weak second order logic can be introduced into algebraic structures in different ways: via HF-logic, or list superstructures over A, or computably enumerable infinite disjunctions and conjunctions, or via finite binary predicates, etc. I will describe a particular form of this logic which is especially convenient to use in algebra and show how to effectively translate such weak second order formulas into the equivalent first-order ones in the case of a rich structure A.