Remarks on Tarski’s problem concerning \(({\mathbb{R}},+,\cdot,\exp)\).

*(English)*Zbl 0585.03006
Logic colloquium ’82, Proc. Colloq., Florence 1982, Stud. Logic Found. Math. 112, 97-121 (1984).

[For the entire collection see Zbl 0538.00003.]

A theory T, extending the theory of dense linear ordering, is of finite type if in each of its models every definable set has only finitely many connected components. For such extensions of \(Th({\mathbb{R}},<,...)\), a partial characterization of definable subsets of \({\mathbb{R}}^ n\) and definable functions on subsets of \({\mathbb{R}}^ n\) is given. Namely, the main result is: Let \(n\geq 1\). (a) For each definable set \(X\subset {\mathbb{R}}^{n-1}\) and definable f:X\(\to {\mathbb{R}}\) there is a finite partition of X into definable sets on each of which f is continuous. (b) Given any finite family of definable subsets of \({\mathbb{R}}^ n\), there is a (cylindrical) decomposition of \({\mathbb{R}}^ n\) partitioning each set from the given family.

The method of cylindrical decomposition, used in the proof (as well as in the above statement), is ”partly alternative to, partly a considerable sharpening of the notion of quantifier elimination”. So the paper is a continuation of the well-known work of Tarski on decidability of the theory of real closed fields, being a step in extending Tarski’s results on \(Th({\mathbb{R}},+,\cdot,\exp)\). Since it is not easy to prove if the theory \(Th({\mathbb{R}},+,\cdot,\exp)\) is of finite type (what is suggested in the paper), the results cannot be simply applied.

Some interesting remarks are given on the possibilities and ways of attacking Tarski’s problem (or rather - what the author calls the realistic part of this problem).

A theory T, extending the theory of dense linear ordering, is of finite type if in each of its models every definable set has only finitely many connected components. For such extensions of \(Th({\mathbb{R}},<,...)\), a partial characterization of definable subsets of \({\mathbb{R}}^ n\) and definable functions on subsets of \({\mathbb{R}}^ n\) is given. Namely, the main result is: Let \(n\geq 1\). (a) For each definable set \(X\subset {\mathbb{R}}^{n-1}\) and definable f:X\(\to {\mathbb{R}}\) there is a finite partition of X into definable sets on each of which f is continuous. (b) Given any finite family of definable subsets of \({\mathbb{R}}^ n\), there is a (cylindrical) decomposition of \({\mathbb{R}}^ n\) partitioning each set from the given family.

The method of cylindrical decomposition, used in the proof (as well as in the above statement), is ”partly alternative to, partly a considerable sharpening of the notion of quantifier elimination”. So the paper is a continuation of the well-known work of Tarski on decidability of the theory of real closed fields, being a step in extending Tarski’s results on \(Th({\mathbb{R}},+,\cdot,\exp)\). Since it is not easy to prove if the theory \(Th({\mathbb{R}},+,\cdot,\exp)\) is of finite type (what is suggested in the paper), the results cannot be simply applied.

Some interesting remarks are given on the possibilities and ways of attacking Tarski’s problem (or rather - what the author calls the realistic part of this problem).

Reviewer: A.Wojciechowska