The expressibility problem in a~lattice with closure operation

N. G. Parvatov

Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 83-103.

Résumé

In this paper we consider the problem of expressibility of an element of the complete lattice equipped with the closure operation. We find conditions under which this problem has a solution in the form of finite lower neighbourhood. The most interesting case of the complete lattice $\mathscr B(P)$ of ordered (by inclusion) subsets of the set $P$ is considered separately. It is shown that existence of a finite lower neighbourhood for each generated closed element of this lattice implies finitariness of the operation of closure in it. In the case of the lattice $\mathscr B(P)$ with finitary closure, we find constructive sufficient conditions for existence of a finite lower neighbourhood of its element. We thus generalise Kuznetsov's theorem on functional completeness. The case of the Galois closure induced by some Galois correspondence between lattices of subsets is studied separately. In this case we find necessary and sufficient conditions for existence of a finite lower neighbourhood of an element of the lattice. This generalises, along with Kuznetsov's theorem, Yablonskii's theorem on predicate-describable classes of functions of finite-valued logic. Along with the expressibility problems, we consider the possibility to determine closed elements of the lattice $\mathscr B(P)$ in particular, elements of lower neighbourhoods, by finite forbidding sets under some preordering of the set $P$, and in the case of the Galois closure, by finite descriptions. The theorems we proved are accompanied by examples of their usage.

Bibliographie

[1] Kurosh A. G., Lektsii po obschei algebre, Lan, Sankt-Peterburg, 2005

[2] Kon P., Universalnaya algebra, Mir, Moskva, 1968 | MR

[3] Birkhoff G., Frink O., “Representations of lattices by sets”, Trans. Amer. Math. Soc., 64 (1948), 299–316 | MR | Zbl

[4] Kuznetsov A. V., “Struktury s zamykaniem i kriterii funktsionalnoi polnoty”, Uspekhi matem. nauk, 16:2 (1961), 201–202

[5] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986 | MR

[6] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy Matematicheskogo instituta im. V. A. Steklova AN SSSR, 51, 1958, 5–142 | MR | Zbl

[7] Yablonskii S. V., “O stroenii verkhnei okrestnosti dlya predikatno-opisuemykh klassov v $P_k$”, Doklady AN SSSR, 218:2 (1974), 304–307

[8] Bondarchuk V. G., Kalyuzhnyi L. A., Kotov V. N., Romov B. A., “Teoriya Galua dlya algebr Posta”, Kibernetika, 1969, no. 3, 1–10; no. 5, 1–9

[9] Maltsev A. I., Iterativnye algebry Posta, Izd-vo NGU, Novosibirsk, 1976 | MR

[10] Maltsev A. I., “Iterativnye algebry i mnogoobraziya Posta”, Algebra i logika, 5:2 (1966), 5–24 | MR

[11] Parvatov N. G., “Zamechaniya o konechnoi porozhdaemosti zamknutykh klassov”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 11:3 (2004), 32–47 | MR | Zbl

[12] Parvatov N. G., “Nasledstvennye sistemy diskretnykh funktsii”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 14:2 (2007), 76–91 | MR

[13] Distel R., Teoriya grafov, Izd-vo In-ta matematiki, Novosibirsk, 2002

[14] Yablonskii S. V., “O nevozmozhnosti eliminatsii perebora vsekh funktsii iz $P_2$ pri reshenii nekotorykh zadach teorii skhem”, Doklady AN SSSR, 124:1 (1959), 44–47 | MR

[15] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, 1963, 61–80 | MR

[16] Rige Zh., “Binarnye otnosheniya, zamykaniya, sootvetstviya Galua”, Kiberneticheskii sbornik, 7, 1963, 129–185