RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2010 Volume 49, Number 2, Pages 181–194 (Mi al435)

This article is cited in 1 paper

Definability of closure operations in the $h$-quasiorder of labeled forests

A. V. Zhukova, O. V. Kudinovb, V. L. Selivanovc

a Novosibirsk State Pedagogical University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
c A. P. Ershov Institute of Informatics Systems Sib. Br. RAS, Novosibirsk, Russia

Abstract: We prove that natural closure operations on quotient structures of the $h$-quasiorder of finite and (at most) countable $k$-labeled forests ($k\ge3$) are definable provided that minimal nonsmallest elements are allowed as parameters. This strengthens our previous result which holds that each element of the $h$-quasiorder of finite $k$-labeled forests is definable in the first-order language, and each element of the $h$-quasiorder of (at most) countable $k$-labeled forests is definable in the language $L_{\omega_1\omega}$; in both cases $k\ge3$ and minimal nonsmallest elements are allowed as parameters. Similar results hold true for two other relevant structures: the $h$-quasiorder of finite (resp. countable) $k$-labeled trees and $k$-labeled trees with a fixed label on the root element.

Keywords: labeled forest, labeled tree, $h$-quasiorder, definability, closure operation.

UDC: 510.532

Received: 29.10.2008


 English version:
Algebra and Logic, 2010, 49:2, 120–129

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024