SCHEDULE FOR OBERWOLFACH SEMINAR IN COMPUTABILITY 2018:
(abstracts can be found at the end)
MONDAY:
08:00-09:00 BREAKFAST
09:00-09:15 Housekeeping/Information for Participants
09:15-10:00 Ludovic Patey: Pigeons do not jump high
10:30-10:50 Klaus Ambos-Spies: Uniformly multiply permitting c.e. sets
and lattice embeddings into the c.e. degrees
11:00-11:20 Alberto Marcone: Computability and incomputability of
projection functions in Euclidean space
12:30-13:30 LUNCH
14:30-16:00 COFFEE AND CAKE
16:00-16:20 Klaus Weihrauch: Computable planar curves intersect in a
computable point
16:30-16:50 Arno Pauly: Almost-total degrees, graph-cototal degrees and a
theorem by Sierpinski
18:30-19:30 DINNER
TUESDAY:
08:00-09:00 BREAKFAST
09:15-10:00 Joe Miller: Characterizing the continuous degrees
10:30-10:50 Veronica Becher: Randomness as uniform distribution modulo
one
11:00-11:20 Sergey Goncharov: Rogers semilattices of generalized
computable numberings
12:30-13:30 LUNCH
14:30-16:00 COFFEE AND CAKE
16:00-16:20 Jack Lutz: Who asked us? How the theory of computing answers
Questions that weren’t about computing
16:30-16:50 Uri Andrews: On building models of Solovay theories
18:30-19:30 DINNER
20:00-21:00 Open problem session
WEDNESDAY:
08:00-09:00 BREAKFAST
09:15-10:00 Takayuki Kihara: Topologizing the degree theory
10:30-10:50 Keng Meng (Selwyn) Ng: A degree characterisation of strong
jump traceability
11:00-11:20 Matthew Harrison-Trainor: When is a property expressed in
infinitary logic also pseudo-elementary?
11:30-11:50 Noam Greenberg: Cardinal characteristics, highness classes,
Weihrauch reducibility, and forcing
12:30-13:30 LUNCH
FREE AFTERNOON
18:30-19:30 DINNER
THURSDAY:
08:00-09:00 BREAKFAST
09:15-10:00 Russell Miller: Effective classification and measure
for countable structures
10:30-10:50 Ted Slaman: Exponents of irrationality and transcendence and
effective Hausdorff dimension
11:00-11:20 Mariya Soskova: Randomness relative to an enumeration oracle
12:30-13:30 LUNCH
14:30-16:00 COFFEE AND CAKE
16:00-16:20 Laurent Bienvenu: On low for speed sets
16:30-16:50 Reed Solomon: Partial results on the complexity of roots of
polynomials over Hahn fields and Puiseux fields
18:30-19:30 DINNER
20:00-20:20 Elvira Mayordomo: A point-to-set principle for separable
metric spaces
20:30-20:50 George Barmpalias: Algorithmic learning of probability
distributions from random data in the limit
21:00-21:20 Steffen Lempp: Finite final segments of the d.c.e. degrees
21:30-21:50 Satyadev Nandakumar: Martingales and restricted ratio betting
FRIDAY:
08:00-09:00 BREAKFAST
09:15-10:00 Linda Brown Westrick: Determined Borel codes in reverse math
10:30-10:50 Sasha Shlapentokh: All things diophantine: stability,
definability and undecidability
11:00-11:20 Adam Day: Algorithmic randomness and amenable groups
11:30-11:50 Bakhadyr Khoussainov: On finitely presented expansions of
semigroups, groups, and algebras
12:30-13:30 LUNCH
14:00-14:20 Damir Dzhafarov: Existence of fixed points for monotone
operators
14:30-16:00 COFFEE AND CAKE
18:30-19:30 DINNER
SATURDAY:
08:00-09:00 BREAKFAST
ABSTRACTS:
Ludovic Patey: Pigeons do not jump high
Abstract: The infinite pigeonhole principle asserts that every set of
integers admits an infinite subset in it or its complement. This
seemingly trivial principle surprisingly admits highly non-trivial
computability-theoretic features, when considering non-computable
instances. In particular, one may wonder whether there is an instance of
the pigeonhole principle whose solutions are all high. The answer to this
question will be given during this talk, although the careful reader
might find a subtle clue in the title. This is joint work with Benoit
Monin.
Klaus Ambos-Spies: Uniformly multiply permitting c.e. sets and lattice
embeddings into the c.e. degrees
Abstract: We introduce a new permitting property of c.e. sets called
uniform multiple permitting. This notion is wtt-invariant and the c.e.
wtt-degrees which do not contain any sets with this property form an
ideal. The Turing degrees of the sets with the uniform multiple property
are the c.e. not totally $\omega$-c.e. degrees. So this new property
gives an alternative characterization of the permitting power of those
degrees. We apply our permitting notion in order to obtain some new
results on the c.e. not totally $\omega$-c.e. degrees. For instance we
show that there are some finite lattices such that a c.e. degree bounds
an embedding of such a lattice in the c.e. degrees if and only if the
degree is not totally $\omega$-c.e. An example of such a lattice is the
7-element lattice $S_7$ which is meet-semidistributive but not join-
semidistributive. (Joint work with Nadine Losert)
Alberto Marcone: Computability and incomputability of projection
functions in Euclidean space
Abstract: Projecting a point over a non-empty closed subset of the
Euclidean space is deeply grounded in our geometrical intuition of the
spatial continuum and has many important applications in several areas of
mathematics. We study the complexity of this projection operator (and of
a natural approximate version of it) in the Weihrauch lattice. The answer
does depend on the way the closed set is given and, in some cases, on the
dimension of the Euclidean space.
Klaus Weihrauch: Computable planar curves intersect in a computable point
Abstract: Consider continuous mappings f,g (paths) from the closed unit
interval to the closed unit square such that f(0) = (0, 0), f(1) = (1,
1), g(0) = (0, 1) and g(1) = (1, 0) . We prove that there is a computable
point of intersection if the paths are computable.
Arno Pauly: Almost-total degrees, graph-cototal degrees and a theorem by
Sierpinski
Abstract: I will showcase the close connection between substructures of
the enumeration degrees and properties of second-countable topological
spaces by an open question: Is every almost-total enumeration degree a
graph-cototal enumeration degree? Translating this question into the
language of topological spaces yields an extension of Sierpinski's
theorem regarding non-existence of countable closed partitions of
connected compact metric spaces.
Joe Miller: Characterizing the continuous degrees
Abstract: The continuous degrees measure the computability-theoretic
content of elements of computable metric spaces. They properly extend the
Turing degrees and naturally embed into the enumeration degrees.
Although nontotal (i.e., non-Turing) continuous degrees exist, they are
all very close to total: joining a continuous degree with a total degree
that is not below it always results in a total degree. We call this
curious property almost totality.
We prove that the almost total degrees coincide with the continuous
degrees. Since the total degrees are definable in the partial order of
enumeration degrees (Cai, Ganchev, Lempp, Miller, Soskova), we see that
the continuous degrees are also definable. Applying earlier work on the
continuous degrees, this shows that the relation “PA above” on the total
degrees is definable in the enumeration degrees.
In order to prove that every almost total degree is continuous, we pass
through another characterization of the continuous degrees that slightly
simplifies one of Kihara and Pauly. Like them, we identify our almost
total degree as the degree of a point in a computably regular space with
a computable dense sequence, and then we apply the effective version of
Urysohn's metrization theorem (Schroeder) to reveal our space as a
computable metric space.
This is joint work with Uri Andrews, Greg Igusa, and Mariya Soskova.
Veronica Becher: Randomness as uniform distribution modulo one
Abstract: How is the notion of randomness of algorithmic information
theory related to the notion of uniform distribution? In this talk we
study Martin-Löf randomness for real numbers in terms of uniform
distribution of sequences. We present a necessary condition for a real
number to be Martin-Löf random, and a strengthening of that condition
which is sufficient for Martin-Löf randomness. For this strengthening, we
define a notion of uniform distribution relative to the computably
enumerable open subsets of the unit interval. We call the notion
Sigma^0_1-uniform distribution.
This is joint work with Serge Grigorieff.
Sergey Goncharov: Rogers semilattices of generalized computable
numberings
Abstract: A comprehensive and extensive study of generalized computable
numberings was initiated at the end of the past century, through a
unifying approach towards a notion of a computable numbering for a
family of sets of constructive objects, suggested in the paper of
S. Goncharov and A. Sorbi [1]. A program of such a study was outlined
in the authors' paper [2]. The study of the Ershov hierarchy was
started by S. Goncharov and S. Lempp [3] and for the analytical
hierarchy by Owings [4]. One of the interesting questions in the
analytical hierarchy is connected with computable Friedberg numberings.
Owings [4] proved that the family of all Sigma^1_1-sets has no
Sigma^1_1-computable Friedberg numbering but M. Dorzhieva (in print)
proved the Owings result without metarecursion and proved that the family
of all Sigma^1_2-sets has no Sigma^1_2$-computable Friedberg numbering.
Nevertheless, the questions for n>2 are open.
The question for the Rogers semilatticas R^0_n of the arithmetical
Sigma^0_n-computable sets and Sigma^0_n-computable numberings was solved
in [5] and [6], but it is open whether R^0_n and R^0_{n+1} are isomorphic
if n>2.
There are interesting questions about computable numberings relative to
classes of Ershov Hierarchy.
Together with A. Sorbi and S. Badaev, the following result was proved:
Theorem: There exist an infinite family S of Sigma^{-1}_n-sets (for n>2)
with Rogers semilattices R^{-1}_n(S) of all Sigma^{-1}_n-numberings of
the family S with exactly two different elements alpha and beta such
that the Sigma^{-1}_n-computable numbering alpha is a Friedberg numbering
and for any Sigma^{-1}_n-computable numbering gamma of this family, if
alpha is not equivalent to gamma then beta <= gamma.
Open question about finite families with these properties remain.
Bibliography:
[1] S. S. Goncharov, A. Sorbi. Generalized computable numberings and
nontrivial Rogers semilattices. Algebra and Logic, 1997, vol. 36, no. 6,
pp. 359–369.
[2] S. A. Badaev, S. S. Goncharov. Theory of numberings: Open problems.
In: Computability Theory and its Applications, P. Cholak, S. Lempp, M.
Lerman and R. Shore eds., Contemporary Mathematics, American Mathematical
Society, 2000, vol. 257, pp. 23-38, Providence, RI.
[3] S. S. Goncharov, S. Lempp, D. R. Solomon. Friedberg numberings of
families of n-computably enumerable sets. Algebra and Logic, 2002, vol.
41, no. 2, pp. 81–86.
[4] James C. Owings, Jr. The meta-r.e. sets, but not the Pi^1_1-sets, can
be enumerated without repetition, The Journal of Symbolic Logic, Volume
35, Number 2, June 1970.
[5] S. A. Badaev, S. S. Goncharov, A. Sorbi. Isomorphism types of Rogers
semilattices for families from different levels of the arithmetical
hierarchy. Algebra and Logic, 2006, vol. 45, no. 6. pp. 361–370.
[6] S. Yu. Podzorov, Numbered distributive semilattices, Siberian Adv.
Math. 17 (2007), no. 3, 171-185.
Jack Lutz: Who asked us? How the theory of computing answers questions
that weren’t about computing
Abstract: It is rare for the theory of computing to be used to answer
open mathematical questions whose statements do not involve computation
or related aspects of logic. This talk discusses recent developments that
do exactly this. After a brief review of algorithmic information and
dimension, we describe the point-to-set principle (with N. Lutz) and its
application to two new results in geometric measure theory. These are
(1) N. Lutz and D. Stull's strengthened lower bounds on the Hausdorff
dimensions of generalized Furstenberg sets, and
(2) N. Lutz's extension of the fractal intersection formulas for
Hausdorff and packing dimensions in Euclidean spaces from Borel sets to
arbitrary sets.
Uri Andrews: On building models of Solovay theories
Abstract: If M is a recursive structure, then the E_n-fragment of the
theory of M is uniformly Sigma^0_n. In general, we call a theory with
this property a Solovay theory. Knight (with some shared credit to
Solovay) gave a characterization of precisely the degrees that compute
some model of every Solovay theory. It is the same as the degrees that
compute a nonstandard model of true arithmetic. One can ask how hard it
is to compute every model of a Solovay theory. Of course, no degree does
this for every Solovay theory, as some Solovay theories have continuum
many models (true arithmetic for example). When we restrict to a nice
class C of theories which do not have continuum many countable models,
this question becomes meaningful and important again. I think of this as
asking what understanding we need to have of a theory in C, beyond the
obvious, to know how to build its models. I'll discuss results giving the
answer for the class of countably categorical theories (due to Knight '94
improving a result of Lerman and Schmerl '79) and recent results about
the class of strongly minimal theories.
Takayuki Kihara: Topologizing the degree theory
Abstract:
I will survey my recent works with collaborators on the topological
generalization of the degree theory. My first motivation for
topologizing the Turing degree theory came from my attempt to solve
the generalized Jayne-Rogers conjecture, one of the most attractive
open problems in descriptive set theory. After a few years of work,
the topologized Turing degree theory has turned out to have many other
applications. This theory has clarified the relationship between the
Turing degree theory and infinite dimensional topology (joint with
Arno Pauly). This theory has enabled us to utilize nonmetrizable
topology to explore the structure of the enumeration degrees (joint
with Steffen Lempp, Keng Meng Ng, and Arno Pauly).
In the latter part of this talk, I will focus on a generalization of
the truth-table degrees in computable metric spaces, which is recently
introduced by McNicholl-Rute. We apply the Jayne-Rogers theorem to
characterize the notion of the generalized tt-degree in the context of
the first-level Borel isomorphism. This characterization is the
guidepost which indicates the right way to go. First-level Borel
isomorphisms have appeared in several literatures in topological
dimension theory. Thus the theory of effective topological dimension
naturally emerges. For instance, by the topological method called
"condensation of singularities," we show that, for any positive integer
n, every weakly 1-generic Turing degree contains a tt-degree which is
(n+1)-dimensional, but not n-dimensional.
Keng Meng (Selwyn) Ng: A degree characterisation of strong jump
Traceability
Abstract: We discuss recent work which explores the unexpected
relationship between strong jump traceability and ideals originating in
the study of c.e. degrees. Given a downwards closed class L, the ideal
Pres(L) is the class of all Delta2 degrees a such that a+b is in L for
every b in L. We investigate this for certain lowness classes L.
Matthew Harrison-Trainor: When is a property expressed in infinitary
logic also pseudo-elementary?
Abstract: Some non-elementary properties, such as reachability in a
graph, are expressible both in infinitary logic and in a pseudo-
elementary (or co-pseudo-elementary) way. On the other hand, some
properties, such as well-foundedness, are expressible in only one of
these ways. We will give an explanation of what kinds of infinitary
sentences can be expressed in a pseudo-elementary way.
This is joint work in progress with Barbara Csima and Nancy Day.
Noam Greenberg: Cardinal characteristics, highness classes, Weihrauch
reducibility, and forcing
Abstract: Vojtas showed that many cardinal characteristics of the
continuum, including all those appearing in the Cichon diagram, arise
from binary relations considered as problems, with the cardinal being the
smallest size of a set which includes solutions for all instances. ZFC-
provable cardinal inequalities arise from morphisms between these binary
relations.
In his thesis, Rupprecht introduced highness classes in computability
which correspond to these cardinals by considering the very same binary
relations (see also Brendle, Brooke-Taylor, Nies and Ng). He showed that
computable morphisms prove implications between these highness classes.
The morphisms are (not necessarily uniform) strong Weihrauch reductions.
Some implications in both set theory and computability require not only
morphisms but manipulations of problems, operations which have been
studies in both the Weihrauch lattice and in set theory. We discuss this
correspondence, how it relates to several results in algorithmic
randomness, and how to calibrate computational strength by working over
ideals.
Russell Miller: Effective classification and measure for countable structures
Abstract: Model theorists and descriptive set theorists have considered
the class of all atomic diagrams of structures with domain omega
belonging to a given class $C$ of structures, and have used it in
attempts to classify the countable models of C up to isomorphism. We
continue these efforts from the perspective of computable structure
theory. For classes C for which the isomorphism problem is not too
difficult, it is sometimes possible to give an effective classification
of the countable structures in C, up to isomorphism. More commonly, it
becomes possible to do so once one adds certain well-chosen definable
predicates to the language, thus taking a (partial) Morleyization.
We will give several specific examples of this process, including the
class of algebraic fields of characteristic 0, the class of finite-
branching infinite trees, the class of archimedean real closed fields,
and the class of torsion-free abelian groups of rank n. In some cases,
classification can be accomplished by a computable homeomorphism onto
Cantor space or Baire space. In these cases, it then becomes possible to
put a measure on the class, which can be used to define randomness
notions and also to consider the prevalence of properties such as
relative computable categoricity. In other cases, effective
classification can be done if one allows an equivalence elation on
Cantor space or Baire space as part of the description.
Portions of this work are joint with Johanna Franklin and with Fokina, S.
Friedman, Rossegger, and San Mauro.
Ted Slaman: Exponents of irrationality and transcendence and effective
Hausdorff dimension
Abstract: We will discuss the similarities between measuring the
describability of a real number in terms of Diophantine Approximation or
by measuring it in terms of Kolmogorov Complexity. This is joint work
with Veronica Becher and Jan Reimann.
Mariya Soskova: Randomness relative to an enumeration oracle
Abstract:
We initiate the study of algorithmic randomness relative to an
enumeration oracle. The enumeration degrees can be viewed as an extension
of the Turing degrees: the substructure of the total enumeration degrees
is an isomorphic copy of the Turing degrees within the wider context of
the enumeration degrees. In this sense, the notion of randomness for
total enumeration oracles can be inferred from the corresponding notion
for Turing oracles. There are two distinct approaches to extending this
notion to non-total enumeration degrees. The first one is to define
randomness relative to a non-total enumeration oracle in terms of the
total enumeration oracles that are comparable with it. On the other hand,
most of the notions in algorithmic randomness, and all of those most
closely related to Martin-L\" of randomness, can be expressed in terms of
c.e. sets. So when we relativize these notions to an oracle X, we are
usually interested in the X-c.e. sets. The second approach to
generalizing from Turing degrees to enumeration degrees is
straightforward: to relativize a randomness notion to the enumeration
degree of a set A we simply replace X-c.e. with c.e. in every enumeration
of A (i.e., enumeration reducible to A). The resulting definitions are
easily seen to be unchanged for the total degrees, demonstrating that
this notion of randomness does lead to an extension of the original one.
We show that there are oracles for which this notion does not coincide
with the notions obtained via our first approach. Thus moving to the
context of the enumeration degrees gives rise to a notion of relative
randomness that does not reduce to one expressible in the Turing world
by relativizing to sets of oracles. For non-total degrees, we find
that some familiar theorems are preserved, perhaps with more subtle
proofs, while other theorems may fail. For example, there need not be a
universal Martin-Loef test relative to the enumeration degree of A, and
there are continuum many enumeration degrees that are low for randomness.
This is joint work with Joe Miller.
Laurent Bienvenu: On low for speed sets
Abstract: Relativizing computations of Turing machines to an oracle is a
central concept in the theory of computation, both in complexity theory
and in computability theory(!). Inspired by lowness notions from
computability theory, Allender introduced the concept of “low for speed”
oracles. An oracle A is low for speed if relativizing to A has
essentially no effect on computational complexity, meaning that if a
decidable language can be decided in time f(n$ with access to oracle A,
then it can be decided in time poly(f(n)) without any oracle. The
existence of non-computable such A's was later proven by Bayer and
Slaman, who even constructed a computably enumerable one, and exhibited a
number of properties of these oracles as well as interesting connections
with computability theory. We pursue this line of research, answering the
questions left by Bayer and Slaman and give further evidence that the
structure of the class of low for speed oracles is a very rich one. This
is joint work with Rod Downey.
Reed Solomon: Partial results on the complexity of roots of polynomials
over Hahn fields and Puiseux fields
Abstract: Let K be an algebraically closed field of characteristic zero
and G be a divisible ordered abelian group. The associated Hahn field and
the field of Puiseux series are both algebraically closed. We will give
preliminary partial results on the complexity of finding roots in these
fields. This work is joint with Julia Knight and Karen Lange.
Elvira Mayordomo: A point-to-set principle for separable metric spaces
J. Lutz and N. Lutz (2017) have recently proven a point-to-set principle for
Euclidean and Cantor spaces. This result is a characterization of classical
Hausdorff dimension in terms of relativized effective dimension. This implies
that geometric measure results regarding Hausdorff dimension can be shown using
solely effective methods. Several interesting classical results have already
been proven using this principle (please refer to Jack Lutz's presentation
on Tuesday for details on these).
In this talk a point-to-set principle for any separable metric space will be
presented. We will first present an effectivization of dimension in terms of
Kolmogorov complexity that is valid for any separable space, and then show
that the classical Hausdorff dimension of any set is the minimum on all
oracles of the relativized effective dimension. We expect that better
Hausdorff dimension bounds will be proven as consequences of this theorem.
George Barmpalias: Algorithmic learning of probability distributions from
random data in the limit
Abstract: We study the problem of identifying a probability distribution
for some given randomly sampled data in the limit, in the context of
algorithmic learning theory as proposed recently by Vinanyi and Chater.
We show that there exists a computable partial learner for the computable
probability measures, while by Bienvenu, Monin and Shen, it is known that
there is no computable learner for the computable probability measures.
Our main result is the characterization of the oracles that compute
explanatory learners for the computable (continuous) probability measures
as the high oracles. This provides an analogue of a well-known result of
Adleman and Blum in the context of learning computable probability
distributions. We also discuss related learning notions such as
behaviorally correct learning and other variations of explanatory
learning, in the context of learning probability distributions from data.
This is joint work with Frank Stephan.
Steffen Lempp: Finite final segments of the d.c.e. degrees
Abstract: Ever since the existence of a maximal incomplete d.c.e. degree
was established, the question of exactly which finite final segments
exist in the d.c.e. degrees has been an interesting open question. In
this talk, I will report on progress toward establishing that all finite
distributive lattices are final segments; some partial results exist,
challenges lie ahead, and there is a larger class, the so-called finite
interval dismantlable lattices, which may be realized using the same
techniques.
This is joint work with Yiqun Liu, Yong Liu, Selwyn Ng, Cheng Peng,
Guohua Wu and Yue Yang, all from Singapore.
Satyadev Nandakumar: Martingales and restricted ratio betting
Abstract: Let A and B be two finite sets of computable real numbers which
denote the allowable wagers that martingales can make. Following the
terminology in Chalcraft et. al., an A-martingale is a martingale whose
wagers are limited to elements in A, and a B-martingale has wagers
limited to elements in B. In Chalcraft et al., the authors establish
necessary and sufficient conditions for some A-martingale to succeed
betting on sequences that B-martingales can succeed betting on.
In this paper, we investigate the analogous question of comparative
betting power of martingales when the ratios of bets are restricted to
a finite set which excludes 1. This contrasts with the setting of simple
martingales and almost simple martingales as investigated by Ambos-
Spies and Mayordomo. Without loss of generality, we will restrict
the ratios to rational numbers, and the general case of finite sets of
computable real ratios is similar. We derive necessary and sufficient
conditions for deciding when a set of ratios allows greater power in
betting as compared to another.
(Joint work with Sumedh Masulkar and Keng Men Ng.)
Linda Brown Westrick: Determined Borel codes in reverse math
Abstract: The standard definition of a Borel code in reverse math
doesn't require the model to believe that each real is either in the
coded set or in its complement. In fact, the statement "for every Borel
coded set, either it or its complement is non-empty" already implies ATR.
We define a determined Borel code to be a Borel code with the property
that every real is contained either in the coded set or in its
complement. While the statement "every Borel set has the property of
Baire" is equivalent to ATR due to the above-mentioned technicality, the
statement "every determined Borel set has the property of Baire" is not.
We discuss the location of this statement relative to ATR, theories of
hyperarithmetic analysis, and the existence of hyperarithmetic generics.
This is joint work with Astor, Dzhafarov, Montalbán and Solomon.
Sasha Shlapentokh: All things diophantine: stability, definability and
Undecidability
We discuss the cur rent state of affairs with respect to using elliptic
curves (and abelian varieties in general) to show first-order and
Diophantine definability of Z over subrings of algebraic extensions of Q,
Proving that the first-order or existential theory of these rings is
undecidable.
Adam Day: Algorithmic randomness and amenable groups
Abstract: The main space studied in algorithmic randomness is the space
of all infinite binary strings. It is possible to transfer the study of
algorithmic randomness to the set of functions from G to {0,1} where G is
a countable group. In the case that G is amenable, different notions of
complexity such as entropy and effective dimension can be translated to
the new space as well. We give an effective version of the Shannon-
McMillian-Breiman theorem in this setting. We also extend a result of
Simpson equating topological entropy and Hausdorff dimension. This proof
makes use of work of an interesting lemma of Ornstein and Weiss which we
also outline.
Bakhadyr Khoussainov: On finitely presented expansions of semigroups,
groups, and algebras
Abstract: Finitely presented structures, such as groups and semigroups,
are of foundational interest in algebra and computation. Finitely
presented structures necessarily have c.e. word equality and these
systems are finitely generated. Not all c.e. and finitely generated
structures are finitely presented. This work is concerned with finding
finitely presented expansions of finitely generated structures.
Expansions of structures, such as turning groups into rings or
distinguishing subsets in the underlying structures, is an important
method used in algebra, model theory, and various areas of computer
science. Bergstra and Tucker [1] [2] proved that all c.e. algebraic
systems with decidable word problem have finitely presented expansions.
Then they [1] [2] and, independently, Goncharov [3] asked if every
finitely generated c.e. algebraic system has a finitely presented
expansion. We build examples of finitely generated c.e. semigroups,
algebras (rings that are vectors spaces over fields), and groups that
fail to possess finitely presented expansions. We also construct examples
of a residually finite and immune group, answering the question of
Miasnikov and Osin from [4]. Our proofs are based on the interplay
between key constructions, concepts, and results from computability
theory (simple set constructions), universal algebra (residually finite
structures), and classical algebra (Golod- Shafaverevich theorem [7]).
The work is joint with D. Hirschfeldt, and independently with A. Miyasnikov.
[1] J.A. Bergstra, J.V.Tucker. Initial and Final Algebra Semantics for
Data Type Specifications: Two characterization Theorems, SIAM J. Comput.
12, 1983.
[2] J.A.Bergstra, J.V.Tucker, Algebraic Specifications of Computable and
Semicomputable DataTypes, Theoretical Comp. science, 50, 1987.
[3] Logic Notebook (Open questions in Logic), Novosibirsk University
Press, editors Yu.Ershov and S. Goncharov, 1989.
[4] A. Miasnikov, D. Osin. Algorithmically finite groups. Journal of Pure
and Applied Algebra, Volume 215, Issue 11, November 2011, pp. 2789-2796.
[5] B. Khoussainov, D. Hirschfeldt. On finitely presented expansions of
semigroups. Algebra and Logic, 51, 435-445, 2012.
[6] B. Khoussainov, A. Miasanikov. Finitely presented expansions of
semigroups, groups, and algebras, TAMS, 2015.
[7] E.S. Golod, I.R. Shafarevich. On the class field tower, Izv. Akad.
Nauk SSSR 28: 261-272 (in Russian), 1964.
Damir Dzhafarov: Existence of fixed points for monotone operators
Abstract: I will discuss work in progress with Sean Walsh concerning the
logical strength of the existence of fixed points for monotone operators.
It is easy to see that repeatedly applying such an operator to the empty
set must result in a fixed point, and in fact, this will be the least
fixed point under inclusion. The strength of the existence of least fixed
points was analyzed already by Cenzer and Remmel, but the situation for
arbitrary fixed points, as opposed to least, is quite different from
theirs. For example, Cenzer and Remmel showed that the existence of least
fixed points for computable monotone operators is equivalent to ACA_0,
while we show that the existence of general fixed points is equivalent to
WKL_0. I will mention partial results concerning the existence of fixed
points for various other classes of operators. Part of our motivation is
understanding the strength of constructions of formal theories of truth
in the style of Kripke; we present a proof of Kripke’s fixed point
theorem in Pi^1_1-CA_0.