Degrees of presentability of structures. I

Presentations of structures in admissible sets, as well as different relations of effective reducibility between the structures, are treated. Semilattices of degrees of Σ-definability are the main object of investigation. It is shown that the semilattice of degrees of Σ-definability of countable structures agrees well with semilattices of T-and e-degrees of subsets of natural numbers. Also an attempt is made to study properties of the structures that are inherited under various effective reducibilities and explore how degrees of presentability depend on choices of different admissible sets as domains for presentations. Supported by RFBR grant Nos. 05-0100481 and 06-0104002, by the Council for Grants (under RF President) for State Support of Young Candidates of Science and Their Supervisors via project MK-1239.2005.1, and via INTAS project YSF 04-83-3310. __________ Translated from Algebra i Logika, Vol. 46, No. 6, pp. 763–788, November–December, 2007.     

关于序半群的N—类

本文给出了关于序半群 N—类的若干等价性质     

逆半群半格上的自然偏序关系

首先讨论逆半群Sa的半上的自然偏序与各Sa上的自然偏序之间的关系，然后讨论逆半群Sa的半格S的幂等元集Ea的闭包限制在Sa上与Ea的闭包的关系．     

Algebras Defined from Ordered Sets and the Varieties they Generate

We investigate ways of representing ordered sets as algebras and how the order relation is reflected in the algebraic properties of the variety (equational class) generated by these algebras. In particular we consider two different but related methods for constructing an algebra with one binary operation from an arbitrary ordered set with a top element. The two varieties generated by all these algebras are shown to be well-behaved in that they are locally finite, finitely based, and have an equationally definable order relation. We exhibit a bijection between the subdirectly irreducible algebras in each variety and the class of all ordered sets with top element. We determine the structure and cardinality of the free algebra on n-free generators and provide sharp bounds on the number of n-generated algebras in each variety. These enumeration results involve the number of quasi-orders on an n-element set.     

REPRESENTATION OF POSETS

In this paper we give new criterions for left distributive posets to have neatest representations. We also illustrate a construction that would embed left distributive posets into representable semilattices.     

The common structure graph: Common structural features of a set of graphs

A method is proposed for abstracting the common features of a set of graphs. It is based on the graph homomorphisms that a set of graphs share. A semilattice structure is imposed on the partial order of graph homomorphisms of a set of graphs. The ‘common structure graphs’ are defined in relation to this semilattice.     

Algebraic coalitions: 2

This paper continues the investigation of [2] into the notions of algebra in and of coalition. Here these notions are characterized for the variety of semilattices, more generally for any variety of inverse semigroups, and for subtractive varieties. Received June 25, 1997 accepted in final form October 16, 1998.     

Some remarks on completion of numberings

We present some examples and constructions in the theory of complete numberings and completions of numberings that partially answer a few questions of [1].     

乘法半群为左正规纯正群的半环

研究了加法半群为半格,乘法半群为左正规纯正群的半环．证明了此类半环（S,＋,．）可以嵌入到半格（S,＋）的自同态半环中．构造S的一个特定的偏序关系,得到了（S,·）上的自然偏序与所构造偏序相等的等价条件．     

On Matroids and Orlik-Solomon Algebras

In this paper we axiomatize combinatorics of arrangements of affine hyperplanes, which is a generalization of matroids, called quasi-matroids. We show that quasi-matroids are equivalent to pointed matroids. On the other hand, the Orlik-Solomon (OS) algebra of a quasimatroid can be constructed. We prove that the OS algebra of a quasi-matroid is isomorphic to the direct image of the OS algebra of a matroid by the linear derivation.AMS Subject Classification: 03B35, 13D03, 52C35.