When is scalar multiplication decidable?
type: Item
instance of: scholarly article
title: When is scalar multiplication decidable?
zbMATH Open document ID: 1446.03029
author: Philipp Hieronymi
published in: Annals of Pure and Applied Logic
publication date: 2019-07-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/1505.08055
review text: A real number is called quadratic, if it is a root of a quadratic polynomial with rational coefficients. The scalar multiplication by \(a\in\mathbb{R}\) is the function \(\lambda_a\colon\mathbb{R}\rightarrow\mathbb{R}\) defined by \(\lambda_a(x)=a\cdot x\). The question of the decidability of the structure \(\mathcal{S}_a=\langle\mathbb{R};<,+,\mathbb{Z},\lambda_a\rangle\) was left open in an earlier paper of the author [J. Symb. Log. 81, No. 3, 1007--1027 (2016; Zbl 1436.03208)] which is a prerequisite for reading the present paper. The main result (Theorem D) is that for \(d\in\mathbb{Q}\), the function \(\lambda_{\sqrt{d}}\) is definable in \(\mathfrak{A}_{\sqrt{d}}=\langle\mathbb{R};<,+,\mathbb{Z},\mathbb{Z}\sqrt{d}\rangle\). Since it was proved in [loc. cit.] that \(\mathfrak{A}_{\sqrt{d}}\) is decidable for \(d\in\mathbb{Q}\), then it follows that \(\mathcal{S}_a\) is decidable for quadratic real \(a\). An earlier result of the author with \textit{M. Tychonievich} [Proc. Am. Math. Soc. 142, No. 9, 3259--3267 (2014; Zbl 1337.03054)] states that \(\mathcal{S}_a\) is undecidable, when \(a\) is not quadratic. This implies that the structure \(\mathcal{S}_a\) is decidable, if and only if \(a\) is quadratic (Theorem A). The following theorems are obtained as corollaries of Theorem A: Theorem B: For \(S\subseteq\mathbb{R}\), the structure \(\langle\mathbb{R};<,+,\mathbb{Z},\{\lambda_b\}_{b\in S}\rangle\) defines the same sets as exactly one of the following structures: (i) \(\langle\mathbb{R},<,+,\mathbb{Z}\rangle\), (ii) \(\mathcal{S}_a\), for some quadratic \(a\in\mathbb{R}\setminus\mathbb{Q}\), (iii) \(\langle\mathbb{R},<,+,\cdot,\mathbb{Z}\rangle\). The three cases are exclusive. Theorem C: Let \(K\) be a subfield of \(\mathbb{R}\). The theory of the ordered \(K\)-vector space \(\mathbb{R}\) expanded by a predicate for \(\mathbb{Z}\) is decidable, if and only if \(K\) is a quadratic field. The paper finishes with some open questions, one of which is that whether …
reviewed by: Saeed Salehi
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03C64
Mathematics Subject Classification ID: 03C60
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 11A67
Mathematics Subject Classification ID: 11U05
zbMATH DE Number: 7078382
zbMATH Keywords: decidability
zbMATH Keywords: definability
zbMATH Keywords: scalar multiplication
zbMATH Keywords: expansions of real ordered additive groups
MaRDI profile type: Publication
OpenAlex ID: W2963357655
arXiv ID: 1505.08055
cites work: Pairs of theories satisfying a Mordell–Lang condition
cites work: An effective decision procedure for linear arithmetic over the integers and reals
cites work: Q4219027
cites work: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
cites work: Defining the set of integers in expansions of the real field by a closed discrete set
cites work: EXPANSIONS OF THE ORDERED ADDITIVE GROUP OF REAL NUMBERS BY TWO DISCRETE SUBGROUPS
cites work: Q5155665
cites work: Interpreting the projective hierarchy in expansions of the real line
cites work: Expansions of dense linear orders with the intermediate value property
cites work: Definability and decision problems in arithmetic
cites work: Q4341842
cites work: Q4477876
cites work: Logical number theory I. An introduction
cites work: Q3840696
cites work: The Büchi Complementation Saga
cites work: Q5665234
Wikidata QID: Q127945116
DOI: 10.1016/J.APAL.2019.05.001
Recommended article: What Else Is Decidable about Integer Arrays?
Recommended article: Verification, Model Checking, and Abstract Interpretation
Recommended article: Q5155665
Recommended article: Public Key Cryptography - PKC 2006
Recommended article: When Is Reachability Intrinsically Decidable?
Recommended article: When is arithmetic possible?
Recommended article: Q3397629
Recommended article: Approximate computation of scalar products
Recommended article: Q4252796
description: scientific article