Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

Axiomatization and undecidability results for metrizable betweenness relations


Authors: Robert Mendris and Pavol Zlatoš
Journal: Proc. Amer. Math. Soc. 123 (1995), 873-882
MSC: Primary 03B25; Secondary 03B30, 03C52, 03C65, 03D35, 08A02
DOI: https://doi.org/10.1090/S0002-9939-1995-1219728-7
MathSciNet review: 1219728
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let d be a metric on a nonempty set A. The ternary betweenness relation $ {T_d}$ induced by d on A is defined by

$\displaystyle {T_d}(x,y,z) \Leftrightarrow d(x,y) + d(y,z) = d(x,z)$

for $ x,y,z \in A$. Allowing the range of d to vary over some "reasonable" ordered additive algebraic structures (not just the real numbers), we will prove that the class $ \mathcal{M}$ of all metrizable ternary structures, i.e., the class of all structures $ (A,{T_d})$, where d is some metric on A, is an elementary class which can be axiomatized by a set of universal Horn sentences. Further, using an algorithm of linear programming, we will show that the first-order theory of $ \mathcal{M}$ is recursively axiomatizable and its universal part is decidable. On the other hand, the theory of $ \mathcal{M}$ is not finitely axiomatizable and the theory of finite members of $ \mathcal{M}$ is hereditarily undecidable.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03B25, 03B30, 03C52, 03C65, 03D35, 08A02

Retrieve articles in all journals with MSC: 03B25, 03B30, 03C52, 03C65, 03D35, 08A02


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1995-1219728-7
Keywords: Betweenness relation, geometry, metric, ordered group, ordered field, first-order theory, elementary class, axiomatization, universal Horn sentence, decidable, hereditarily undecidable, interpretation, semantic embedding, linear programming, graph
Article copyright: © Copyright 1995 American Mathematical Society