Minimal signatures with undecidability of representability by binary relations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929551807873024 |
|---|---|
| author | Hirsch, Robin Jackson, Marcel Šemrl, Jaš |
| author_facet | Hirsch, Robin Jackson, Marcel Šemrl, Jaš |
| contents | A semigroup of binary relations (under composition) on a set $X$ is \emph{complemented} if it is closed under the taking of complements within $X\times X$. We resolve a 1991 problem of Boris Schein by showing that the class of finite unary semigroups that are representable as complemented semigroups of binary relations is undecidable, so composition with complementation forms a minimal subsignature of Tarski's relation algebra signature that has undecidability of representability. In addition we prove similar results for semigroups of binary relations endowed with unary operations returning the kernel and cokernel of a relation. We generalise to signatures which may include arbitrary, definable operations and provide a chain of weaker and weaker signatures, each definable in the previous signature, each having undecidability of representability, but whose limit signature includes composition only, which corresponds to the well known, decidable and finitely axiomatised variety of semigroups. All these results are also proved for representability as binary relations over a finite set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_15906 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimal signatures with undecidability of representability by binary relations Hirsch, Robin Jackson, Marcel Šemrl, Jaš Logic 03G15 (Primary) 03E20 20M20 03D35 (Secondary) A semigroup of binary relations (under composition) on a set $X$ is \emph{complemented} if it is closed under the taking of complements within $X\times X$. We resolve a 1991 problem of Boris Schein by showing that the class of finite unary semigroups that are representable as complemented semigroups of binary relations is undecidable, so composition with complementation forms a minimal subsignature of Tarski's relation algebra signature that has undecidability of representability. In addition we prove similar results for semigroups of binary relations endowed with unary operations returning the kernel and cokernel of a relation. We generalise to signatures which may include arbitrary, definable operations and provide a chain of weaker and weaker signatures, each definable in the previous signature, each having undecidability of representability, but whose limit signature includes composition only, which corresponds to the well known, decidable and finitely axiomatised variety of semigroups. All these results are also proved for representability as binary relations over a finite set. |
| title | Minimal signatures with undecidability of representability by binary relations |
| topic | Logic 03G15 (Primary) 03E20 20M20 03D35 (Secondary) |
| url | https://arxiv.org/abs/2410.15906 |