Systems of propositions referring to each other: a model-theoretic view

We investigate arbitrary sets of propositions such that some of them state that some of them (possibly, themselves) are wrong, and criterions of paradoxicality or non-paradoxicality of such systems. For this, we propose a finitely axiomatized first-order theory with one unary and one binary predicates, $\mathrm{T}$ and $\mathrm{U}$. An heuristic meaning of the theory is as follows: variables mean propositions, $\mathrm{Tx}$ means that $\mathrm{x}$ is true, $\mathrm{Uxy}$ means that $\mathrm{x}$ states that $\mathrm{y}$ is wrong, and the axioms express natural relationships of propositions and their truth values. A model $\mathrm{(X,U)}$ is called non-paradoxical iff it can be expanded to some model $\mathrm{(X,T,U)}$ of this theory, and paradoxical otherwise. E.g. a model corresponding to the Liar paradox consists of one reflexive point, a model for the Yablo paradox is isomorphic to natural numbers with their usual ordering, and both these models are paradoxical.
We show that the theory belongs to the class $\Pi_2^0$ but not $\Sigma_2^0$ and is undecidable. We propose a natural classification of models of the theory based on a concept of collapsing models. Further, we show that the theory of non-paradoxical models, and hence, the theory of paradoxical models, belongs to the class $\Delta_1^1$ but is not elementary. We consider also various special classes of models and establish their paradoxicality or non-paradoxicality. In particular, we show that models with reflexive relations, as well as models with transitive relations without maximal elements, are paradoxical; this general observation includes the instances of Liar and Yablo. On the other hand, models with well-founded relations, and more generally, models with relations that are winning in sense of a certain membership game are non-paradoxical. Finally, we propose a natural classification of non-paradoxical models based on the above-mentioned classification of models of our theory.
This work was supported by grant 16-11-10252 of the Russian Science Foundation.