Semigroup actions on posets and preimage quasi-orders
- PDF / 593,805 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 186 Views
Semigroup actions on posets and preimage quasi-orders Tim Stokes
Received: 7 January 2011 / Accepted: 22 August 2012 / Published online: 5 October 2012 © Springer Science+Business Media New York 2012
Abstract Structures consisting of a semigroup of (partial) functions on a set X, a poset of subsets of X, and a preimage operation linking the two, arise commonly throughout mathematics. The poset may be equipped with one or more set operations, up to Boolean algebra structure. Such structures are finitely axiomatized here in terms of order-preserving semigroup actions on posets. This generalises Schein’s axiomatization of semigroups of partial functions equipped with the first projection quasi-order. Keywords Semigroup · Semigroup action · Poset · First projection quasi-order 1 Introducing transets Some notation. For a non-empty set X: • R(X) denotes the semigroup of binary relations on X under composition; • T (X) denotes the semigroup of transformations on X (everywhere-defined functions X → X), which is a subsemigroup of R(X); • I(X) denotes the semigroup of injective transformations on X; • P(X) denotes the semigroup of partial transformations on X, which we also refer to as functions on X; • S(X) denotes the symmetric group on X. A function semigroup is a subsemigroup of P(X), and a function monoid is a function semigroup that contains the identity map. Similarly, a transformation semigroup is a subsemigroup of T (X), and a transformation monoid is a transformation semigroup that contains the identity map. Communicated by Mikhail Volkov. T. Stokes () Department of Mathematics, The University of Waikato, Hamilton, New Zealand e-mail: [email protected]
Semigroup actions on posets and preimage quasi-orders
541
If f ∈ P(X) and Y ⊆ X, the preimage of Y under f is denoted by f −1 (Y ). The poset of all subsets of X under set inclusion is denoted by 2X . 1.1 First projection and function transets In [17], Schein axiomatized the first projection quasi-order on function semigroups. This quasi-order is defined on P(X) by setting f g if the domain of f is a subset of the domain of g. Schein’s axioms were the following universal sentences: f g
⇒
hf hg
f g f.
(1) (2)
Any semigroup equipped with an abstract quasi-order satisfying these laws is a first projection quasi-ordered semigroup. In fact, for any function semigroup S in P(X), and any subset Y of X, one may define the quasi-order Y on S by setting f Y g whenever f −1 (Y ) ⊆ g −1 (Y ). (The first projection quasi-order on S is obtained by letting Y = X.) Such preimage quasiorders satisfy (1) above, but not (2) in general. We shall show that (1) provides a complete axiomatization of preimage quasi-orders. However, our main object is to consider semigroups equipped with whole families of such quasi-orders, themselves partially ordered according to the subsets used to define them. Let Q be a set. If (P , ≤) is a poset and f : Q → P is a surjective function from the set Q to P , then defining s t if and only if f (s) ≤ f (t) gives a quasi-order
Data Loading...
