Four pointers to the literature from the last 25 years on applications of Kolmogorov complexity to mathematical logic:
Applications of Kolmogorov complexity to computable model theory (2007).
In this paper we answer the following well-known open question in
computable model theory. Does there exist a computable not
ℵ$_0$-categorical saturated structure with a unique computable
isomorphism type? Our answer is affirmative and uses a construction
based on Kolmogorov complexity.
Logical operations and Kolmogorov complexity (2002).
Conditional Kolmogorov complexity can be understood as the complexity
of the problem $Y\rightarrow X$, where $Y$ is the problem “construct
$y$” and $X$ is the problem “construct $x$”. Other logical operations
($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way,
extending Kolmogorov interpretation of intuitionistic logic and Kleene
realizability.
The Kolmogorov expression complexity of logics (1997).
We introduce the Kolmogorov variant of Vardi's expression complexity.
We define it by considering the value of the Kolmogorov complexity
$C(L[{\cal A}])$ of the infinite string $L[{\cal A}]$ of all truth
values of sentences of $L$ in ${\cal A}$. The higher is this value,
the more expressive is the logic $L$ in ${\cal A}$.
Kolmogorov complexity and the second incompleteness theorem (1995).
It is well known that Kolmogorov complexity has a close relation with
Gödel’s first incompleteness theorem. In this paper, we give a new
formulation of the first incompleteness theorem in terms of Kolmogorov
complexity, that is a generalization of Kolmogorov’s theorem, and
derive a semantic proof of the second incompleteness theorem from it.
