RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2024 Volume 31, Issue 1, Pages 19–34 (Mi da1337)

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


 English version:
Journal of Applied and Industrial Mathematics, 2024, 18:1, 60–69


© Steklov Math. Inst. of RAS, 2024