Dissertations, Theses, and Capstone Projects

Date of Degree

6-2020

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Olga Kharlampovich

Committee Members

Ilya Kapovich

Vladimir Shpilrain

Subject Categories

Algebra | Logic and Foundations

Keywords

Diophantine Problem, bi-interpretability, first-order logic, metabelian groups, Baumslag-Solitar group, wreath products, free monoid

Abstract

We first show that arithmetic is bi-interpretable (with parameters) with the free monoid and with partially commutative monoids with trivial center. This bi-interpretability implies that these monoids have the QFA property and that finitely generated submonoids of these monoids are definable. Moreover, we show that any recursively enumerable language in a finite alphabet X with two or more generators is definable in the free monoid. We also show that for metabelian Baumslag-Solitar groups and for a family of metabelian restricted wreath products, the Diophantine Problem is decidable. That is, we provide an algorithm that decides whether or not a given system of equations in these groups has a solution.

Share

COinS