1990 | OriginalPaper | Buchkapitel
Modal Characterization of the Classes of Finite and Infinite Quasi-Ordered Sets
verfasst von : Dimiter Vakarelov
Erschienen in: Mathematical Logic
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
To formulate the main aim of this paper we will begin with some definitions and notations. A system $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{U} $$=(U,≤), where U≠Ø and ≤ is a binary relation in U, is called quasi-ordered set — qoset for short, — if the relation ≤ is reflexive and transitive one. By QO, QOfin and QOinf we will denote respectively the class of all qosets, all finite qosets and all infinite qosets. If U is a qoset and in addition the relation ≤ is an antisymmetric one /x≤y & y≤x → x=y/ then U is called partially ordered set — poset for short. By PO, POfin and POinfwe denote respectively the class of all posets, all finite posets, and all infinite posets. It is a well known fact that the modal logic S4 is complete in the classes QO and QOfin. So QO and QOfin cannot be separated by S4. However, the situation is different when we consider posets: S4 is complete in the class POinf but not in the class POfin and S4Grz / the so called Grzegorczik system/ is complete in POfin but not in POinf /see [l]/. Roughly speaking, we will say in this case, that S4 is a modal characterization of POinf and S4Grz is a modal characterization of POfin.