|
The expressibility problem in a lattice with closure operation
N. G. Parvatov
Abstract:
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.
Received: 18.11.2008
Citation:
N. G. Parvatov, “The expressibility problem in a lattice with closure operation”, Diskr. Mat., 22:4 (2010), 83–103; Discrete Math. Appl., 20:5-6 (2010), 567–589
Linking options:
https://www.mathnet.ru/eng/dm1121https://doi.org/10.4213/dm1121 https://www.mathnet.ru/eng/dm/v22/i4/p83
|
Statistics & downloads: |
Abstract page: | 388 | Full-text PDF : | 185 | References: | 57 | First page: | 17 |
|