First order complexity of random structures

14^th March 2023, 13:00 Ashton Lecture Theatre
Dr. Maksim Zhukovskii
Department of Computer Science, University of Sheffield

Abstract

The classical 0-1 law for first order logic states that for any finite relational signature its random uniform n-structure obeys the 0-1 law, i.e. every first order sentence is either true with asymptotical probability 1, or false with asymptotical probability 1. It can be viewed as the triviality of first order behaviour of such distributions. For other distributions the behaviour changes and becomes more complex. In particular, it is known that sparse random graphs with probability of appearance of an edge p=n^{-a} does not obey even the first order convergence law for rational a, while when p=c/n the convergence law holds, and the set of limits is well studied. We introduce the notion of first order complexity of random structures, present a natural hierarchy of complexity classes and define a reduction that, in particular, can be used to transfer 0-1 laws between random structures.