Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups

点击翻译按钮获取中文摘要

One of the most amazing results of twentieth century mathematics was the discovery by Alonzo Church and Alan Turing that there are problems in mathematics which cannot be solved, in the sense that there is no algorithm to solve them. This means that no matter how powerful a computer you use to help you, there are some mathematical problems that you will still not be able to solve. If the problem that cannot be solved is in the form of a "yes" or "no" question, then we call it an undecidable problem. On the other hand, if it can be solved, then we say that it is a decidable problem. There are many decision problems that arise naturally in algebra. Important examples include the word problem, which asks us to decide whether two different algebraic expressions are equal to each other, and the membership problem, which asks us to decide whether one element in an algebraic structure can be expressed in terms of another collection of elements. Being able to solve problems like these is important when studying infinite algebraic structures. The main topic of this project is to investigate a range of decision problems like these for three classes of algebraic objects called groups, monoids and inverse semigroups. These three classes arise naturally in the study of symmetry and partial symmetry in mathematics. An important tool for defining infinite groups, monoids and inverse semigroups, is given by the theory of presentations in generators and relations. The idea is that the elements of the group or monoid are represented by strings of letters, called words. We are also given a set of defining relations, which are rules telling us that certain pairs of words are equal to each other. Two words are then equal if one can be transformed into the other by applying the relations. For example, if we use the letters x and y, and we have a single defining relation xy=yx, then the words xyx and yxx are equal since xyx = (xy)x = (yx)x = yxx. On the other hand, the words xy and yy are not equal. The problem of determining whether or not two words are equal to each other is the word problem mentioned above. When we define a monoid or group using a presentation, by increasing the number of relations we can increase the complexity of the monoid or group that we define. If there are no relations these are called free monoids and groups, and because of their simple structure several natural decision problems, like the word problem, can be seen to be decidable in these cases. In contrast, it is known that there are monoids, groups, and inverse semigroups which are defined by finitely many generators and relations, but have undecidable word problem. The situation is the similar for the many other decision problems arising in algebra. It is natural to ask whether groups or monoids which are close to being free, in some sense, will have good algorithmic properties. An important positive result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. On the other hand, it was recently discovered that there are inverse monoids defined by a single defining relation that have undecidable word problem. However, it remains an important longstanding open problem whether the word problem is decidable for one-relator monoids. There are many fascinating open problems like this one which ask fundamental questions about where the boundary between decidability and undecidability lies for finitely presented groups, monoids and inverse semigroups. In this project we will explore a range of interrelated problems of this kind. This will be done by developing geometric and topological methods, which use the "shape" of these algebraic objects, or the way they interact with spaces, to shed light on their algorithmic properties.