RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 Video Library Archive Most viewed videos Search RSS New in collection

You may need the following programs to see the files

Workshop on Proof Theory, Modal Logic and Reflection Principles
October 18, 2017 12:50–13:25, Moscow, Steklov Mathematical Institute

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

D. Saveliev
 Video records: MP4 949.7 Mb MP4 260.3 Mb

Abstract: 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.