Definability of relations by semigroups of isotone transformations
A. A. Klyushina,
I. B. Kozhukhovbc,
D. Yu. Manilovd,
A. V. Reshetnikovb a Cadence Design Systems, Bld. 1 Penrose Dock, Penrose Quay, Cork, T23 KW81, Ireland
b National Research University of Electronic Technology, 1 Shokin Square, 124498 Moscow, Russia
c Lomonosov Moscow State University, 1 Leninskie Gory, 119991 Moscow, Russia
d ELVEES Research and Development Center, 14 Bld. 14 Konstruktor Lukin Street, 1244660 Zelenograd, Moscow, Russia
Abstract:
In 1961, L. M. Gluskin proved that a given set
$X$ with an arbitrary nontrivial quasiorder
$\rho$ is determined up to isomorphism or anti-isomorphism by the semigroup
$T_\rho(X)$ of all isotone transformations of
$(X,\rho)$, i. e., the transformations of
$X$ preserving
$\rho$. Subsequently, L. M. Popova proved a similar statement for the semigroup
$P_\rho(X)$ of all partial isotone transformations of
$(X,\rho)$; here the relation
$\rho$ does not have to be a quasiorder but can be an arbitrary nontrivial reflexive or antireflexive binary relation on the set
$X$. In the present paper, under the same constraints on the relation
$\rho$, we prove that the semigroup
$B_\rho(X)$ of all isotone binary relations (set-valued mappings) of
$(X,\rho)$ determines
$\rho$ up to an isomorphism or anti-isomorphism as well. In addition, for each of the conditions
$T_\rho(X)=T(X)$,
$P_\rho(X)=P(X)$,
$B_\rho(X)=B(X),$ we enumerate all
$n$-ary relations
$\rho$ satisfying the given condition. Bibliogr. 8.
Keywords:
semigroup of binary relations, isotone transformation.
UDC:
512.534.1
Received: 28.08.2023
Revised: 06.09.2023
Accepted: 22.09.2023
DOI:
10.33048/daio.2024.31.783