# ASL January 2014 Newsletter, ASL Announcements

** In Memoriam: Ivan Soskov
**Ivan Soskov passed away suddenly and unexpectedly on May 5, 2013 in
Sofia at the age of 58. He was a remarkable man, not only as a
mathematician, but also as a person. His contributions to
computability theory are deep and will continue to bear fruit long
after his death, as will his contributions to the logic group in
Bulgaria and to the computability theory community around the world.

Soskov was born on September 23, 1954, in Stara Zagora in southern
Bulgaria. When he was 13 he moved to Sofia to attend the National High
School of Mathematics and Sciences, a school dedicated to offering an
introduction to mathematics to the most talented students. He earned his
undergraduate degree in mathematical logic from Sofia University in 1979.
He was awarded his Ph.D. in 1983 from the same university, under the supervision
of Dimiter Skordev, for his thesis entitled, * Computability
in partial algebraic systems*.
Starting in 1986, a
series of international conferences organized by the Department of
Mathematical Logic at Sofia University took place at which prominent scientists
from around the world participated. It was at one of these
conferences that Soskov met Yiannis Moschovakis, from UCLA.
Moschovakis had invented the notions of Prime and Search
Computability, which were at the heart of Soskov's Ph.D. dissertation, and guided his
research later in life. Soskov spent two years (1991-1993) as a
visiting professor at UCLA, working with Moschovakis.

Soskov spent his career at Sofia University. He went from programmer in the Computing Laboratory to being the Dean of the Faculty of Mathematics and Computer Science. For many years he played a major role in the research administration of Sofia University, filling many important roles, such as that of the chair of the Council of Deans of the University. Soskov supervised 15 Master's students and he had three Ph.D. students: Stela Nikolova (1992), Vessela Baleva (2002), and Hristo Ganchev (2009).

Soskov's main area of interest was computability theory. Within this field, he worked on computable structure theory, enumeration degrees, and on connections between these. He proved some beautiful results, but he was also a theory builder who introduced many new notions that are relevant today. A few of these results are described below; a more extensive and detailed paper is being written by Ganchev and Skordev.

The notion of the jump of a structure has become a popular topic of
investigation in recent years. It helps us understand some general
behaviors that are present in different classes of structures, and
has very nice properties that can be proved in full generality. The
first definition of the jump of a structure was given by Soskov in a
special session in computability theory during Logic Colloquium
2002 in Münster. The first appearance in print of this definition is
in the Ph.D. thesis, * The jump
operation for structure degrees* of his student Vessela Baleva. Morozov, Puzarenko,
Stukachev, and Montalban then developed equivalent definitions
that worked in the different settings they were considering.

There are two jump inversion theorems for this notion of jump which are quite useful. The first jump inversion theorem says that for every countable structure $\mathcal A$ that codes $0'$ there is a structure $\mathcal B$ whose jump is equivalent to $\mathcal A$. This result was independently proved by Goncharov, Harizanov, Knight, McCoy, R. Miller and Solomon, and by Soskov and Soskova, in both cases for the notion of Muchnik equivalence, but using very different proofs. It was in this paper of Soskov and Soskova that they introduced the use of Marker's extension in this context. Since then, this has been a useful tool for other applications, as for instance in Stukachev's proof that the first jump inversion theorem holds for the stronger notion of $\Sigma\/$-equivalence. The second jump inversion theorem says that the degree spectrum of the jump of a structure consists of the jumps of the degrees on the spectrum of the original structure. Soskov claimed this result in the Logic Colloquium 2002, and many proofs have appeared since then.

One of Soskov's most beautiful results is that intrinsically hyperarithmetic relations are the same as relatively intrinsically hyperarithmetic relations. Given a computable structure $\mathcal A$, a relation $R$ on $\mathcal A$ is said to be relatively intrinsic hyperarithmetical if on all copies $(\mathcal B,R^{\mathcal B})$ of $(\mathcal A,R)$, we have that $R^{\mathcal B}$ is hyperarithmetic in $\mathcal B$. We say that $R$ is intrinsically hyperarithmetic if the same is true when we restrict ourselves to computable structures $\mathcal B$. These notions have been widely studied for other complexity classes other than hyperarithmetic---we have intrinsically computable, intrinsically c.e., intrinsically $\Sigma_\alpha$, etc. In all these cases, the "relativized'' notion has a nice structural characterization, while the un-relativized one does not. Soskov's surprising result says that these notions are equivalent when looking at hyperarithmetic relations.

Another important result of Soskov is the relativized jump inversion theorem for enumeration degrees. He showed that given a set $B$, there is a total $F$ such that $B'$ is enumeration equivalent to $F'$, where the jump here is the enumeration-jump. In that same paper he proved a much more general result for simultaneously inverting various iterations of the jumps--something that occurs when one is looking at relations of different levels of complexity within a structure. This idea led him to define the $\omega\/$-enumeration degrees. By now, there are several papers by various authors written on this notion.

We mention one last particularly interesting result. Using the construction of Goncharov, Harizanov, Knight, McCoy, R. Miller and Solomon, one can see that the first jump inversion theorem holds for all successor ordinals. That is, for a successor ordinal $\alpha$, if $\mathcal A$ is a structure which codes $0^{(\alpha)}$, then there is a structure $\mathcal B$ whose $\alpha\/$th jump is Muchnik-equivalent to $\mathcal A$. However for a long time it was not known what happened at limit levels. Earlier in 2013 Soskov showed that the $\omega\/$-jump inversion does not always hold. This was quite unexpected, and the proof required looking outside the Turing degrees and into the enumeration degree spectra of these structures.

Soskov's contributions were not limited to his mathematical results.
He did a lot to maintain logic as a strong field in Bulgaria, and to grow
the visibility of the Bulgarian logic group in the world, making Sofia
into one of the centers in logic in Europe. With his humble and
charming personality, he had a lasting impact on the people who worked
with him. It is a great loss for all of us.