MR1900645 (2003d:03001)
Rautenberg, Wolfgang(D-FUB-2)
Einführung in die mathematische Logik. (German. German summary) [Introduction to mathematical logic]
Second edition.
Friedr. Vieweg & Sohn, Braunschweig, 2002. xvi+256 pp. ISBN 3-528-16754-8
03-01 (68N17)

---

The first edition has been reviewed [MR1456719 (98c:03002)]. The main changes in the second edition are revised and expanded Chapters 6 and 7, which now cover in particular Gödel's second incompleteness theorem.

\{The author has informed MR that he wishes to thank W. Buchholz for his valuable suggestions, which the author forgot to do in the book's introduction.\}

MR1456719 (98c:03002)
Rautenberg, Wolfgang
Einführung in die mathematische Logik. (German. German summary) [Introduction to mathematical logic]
Ein Lehrbuch mit Berücksichtigung der Logikprogrammierung. [A textbook with consideration of logic programming] Lehrbuch Mathematik. [Mathematics Textbook]
Friedr. Vieweg & Sohn, Braunschweig, 1996. xii+250 pp. ISBN 3-528-06754-3
03-01 (68N17)

---

This text consists of seven chapters: Propositional logic; Predicate logic; Gödel's completeness theorem; Fundamentals of logic programming (term models; Herbrand's theorem; resolution for propositional logic; unification); Elements of model theory; Incompleteness and undecidability; On the theory of self-reference (the theorems of Gödel and Löb; the modal logic G; modal treatment of self-reference).
Previous Item

MR1270449
Rautenberg, Wolfgang(D-FUB)
Elementare Grundlagen der Analysis. (German. German summary) [Elementary foundations of analysis]
Bibliographisches Institut, Mannheim, 1993. xii+152 pp. ISBN 3-411-16611-8
26-01

---

{There will be no review of this item.}


Previous Item

MR1204877 (94f:03015)
Rautenberg, Wolfgang(D-FUB-2)
On reduced matrices. (English. English summary)
Studia Logica 52 (1993), no. 1, 63--72.
03B22 (03B20 08B05)

---

Summary: "It is shown that the class of reduced matrices of a logic $\vdash$ is a first-order $\forall \exists$-class provided the variety associated with $\vdash$ has the finite replacement property in the sense of B. Herrimann and the author \ref[Z. Math. Logik Grundlag. Math. 38 (1992), no. 4, 327--344]. This applies in particular to all 2-valued logics. For 3-valued logics the class of reduced matrices need not be first-order."

This short paper with a general title is filled with nonsimple information and interesting remarks concerning algebraic aspects of logic. It also contains some open questions, which will be most interesting if the answers turn out to be positive.

Reviewed by Jan Bernert
Previous Item

MR1161584 (93k:03031)
Rautenberg, Wolfgang(D-FUB-2)
Der Gödelsche Vollständigkeitssatz. (German) [Godel's completeness theorem]
Math. Semesterber. 39 (1992), no. 1, 13--28.
03C07 (03B10)

---

Summary (translated from the German): "The proof of Gödel's completeness theorem presented by us in this paper requires only a beginning knowledge of logic for its understanding (what a term, a formula, and a model are). We prove the completeness of both a Gentzen-type and a Hilbert-type calculus. The proofs are not new in principle, but in some not insignificant details they are, and thus relatively short. We also discuss the most important consequences of the theorem."
Previous Item

MR1155137 (93f:03004)
Rautenberg, Wolfgang(D-FUB-2)
Common logic of $2$-valued semigroup connectives.
Z. Math. Logik Grundlag. Math. 37 (1991), no. 2, 187--192.
03B05 (03B22 03G99)

---

This paper presents a continuation of the investigations of various reducts of the classical $2$-valued propositional consequence. Given a $2$-valued binary connective $f$, we denote by $\vdash^f$ the reduct of the $2$-valued propositional consequence $\vdash$ to formulas built up by means of $f$ only. Among all 16 binary connectives, only $\wedge$, $\vee$, $\leftrightarrow$ and $+$ (either-or) are both associative and properly binary, i.e., they depend on both their arguments. The logic $\vdash^*$ (the intersection of the logics $\vdash^\wedge$, $\vdash^\vee$, $\vdash^{\leftrightarrow}$ and $\vdash^+$) is finitely based, i.e., all common rules of $\wedge$, $\vee$, $\leftrightarrow,+$ can be derived from a finite set of rules \ref[cf. \cita MR1028842 (90m:03057) \endcit W. Rautenberg, Arch. Math. Logic 29 (1989), no. 2, 111--123; MR1028842 (90m:03057)]. In the paper it is shown that $\vdash^*$ has precisely 25 proper nontrivial strengthenings (i.e. $\vdash^*$ has "finite degree of maximality") and all of them are strongly finite, i.e., determined by finitely many finite matrices. Their inclusion diagram is presented. The method applied in the paper is purely algebraic and is based on considering subalgebras of products of some two-element algebras.

Reviewed by Wojciech Dzik
Previous Item

MR1124582 (92h:03003)
Rautenberg, Wolfgang
Unvollständigkeit, Unentscheidbarkeit, Nichtdefinierbarkeit. (German) [Incompleteness, undecidability, undefinability]
Mitt. Math. Sem. Giessen No. 202, (1991), iv+36 pp.
03-01 (03Dxx)

---

This paper contains a view of the complex of problems in connection with Gödel's fundamental research on the incompleteness of sufficiently expressive formal systems.

Reviewed by G. Asser
Previous Item

MR1096798
Pearce, David(D-FUB-Q1); Rautenberg, Wolfgang(D-FUB-2)
Propositional logic based on the dynamics of disbelief.
The logic of theory change (Konstanz, 1989), 243--258,
Lecture Notes in Comput. Sci., 465,
Springer, Berlin, 1991.
03B45 (68T27)

---

{This item will not be reviewed individually. For details of the collection in which this item appears see MR1096790 (91k:68010) .}


Previous Item

MR1077989
Jahns, C.; Rautenberg, Wolfgang
Common logic of binary connectives has finite maximality degree (preliminary report).
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 19 (1990), no. 2, 36--38.
03B22

---

{There will be no review of this item.}


Previous Item

MR1068901 (91m:03006)
Rautenberg, Wolfgang(D-FUB-2)
A calculus for the common rules of $\wedge$ and $\vee$.
Studia Logica 48 (1989), no. 4, 531--537.
03B20

---

Let $\vdash^\wedge$ and $\vdash^\vee$ be the closure operators corresponding to the $\wedge$ and $\vee$ fragments of classical logic, respectively.

The author proves that $\vdash^\wedge\cap \vdash^\vee$ is axiomatized by the following rules: $p$; $q·r/p·q$, $p·(q·r)/(p·q)·r$, $p·q/q·p$, $p·p/p$, $p/p·p$.

Moreover: (a) $\vdash^\wedge \cap \vdash^\vee$ has no proper nontrivial strengthenings other than $\vdash^\wedge$ and $\vdash^\vee$. (b) The three-element totally ordered semilattice with the designated element in the middle is an adequate matrix for $\vdash^\wedge \cap \vdash^\vee$.

Reviewed by Ventura Verdú
Previous Item

MR1028842 (90m:03057)
Rautenberg, Wolfgang(D-FUB-2)
Axiomatization of semigroup consequences.
Arch. Math. Logic 29 (1989), no. 2, 111--123.
03B99 (08B05 20M07)

---

A consequence $\vdash$ has a semantics in a variety $V$ of algebras if and only if $\alpha\vdash \beta$ whenever $\alpha=\beta\in\roman{Id}\,V$, where $\roman{Id}\,V$ is the equational theory of $V$. It is shown that a consequence determined by a variety $V$ of algebraic semigroup matrices is finitely based if and only if $V$ is finitely based. In general, this is not true. For a variety $V$ of commutative semigroups, a base for the consequence determined by $V$ is given. To answer the question whether the consequence determined by all 2-valued semigroup connectives $\wedge$, $\vee$, $\leftrightarrow$, $+$ is finitely based one has to consider the variety $V_3=V_1+V_2=_{\roman{df}}\,\roman{HSP}(V_1\cup V_2)$ with $V_1=V (\langle \{0,1\}; \vee\rangle)$ and $V_2=V(\langle\{0,1\};+\rangle)$. Since $V_3$ is finitely based, the consequence connected with $V_3$ is finitely based. A base can be given.

Reviewed by Klaus Denecke
Previous Item

MR1008694
Rautenberg, Wolfgang
The common rules of binary connectives are finitely based.
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 18 (1989), no. 2, 87--89.
03B99

---

{There will be no review of this item.}


Previous Item

MR0937860 (89a:03063)
Rautenberg, Wolfgang(D-FUB-2)
A note on completeness and maximality in propositional logic.
Rep. Math. Logic No. 21, (1987), 3--8 (1988).
03B99

---

From the introduction: "Let $\vdash$ be a structural consequence relation without nontrivial structural extensions. By means of examples we present a simple method for proving the completeness of a calculus for $\vdash$ and maximality itself, in one step. The idea is to work with substitutions rather than with valuations."
Previous Item

MR0887067 (88g:04004)
Rautenberg, Wolfgang
Über den Cantor-Bernsteinschen Äquivalenzsatz. (German) [On the Cantor-Bernstein equivalence theorem]
Math. Semesterber. 34 (1987), no. 1, 71--88.
04A20 (01A55 03E20 04-03)

---

The paper begins with some historical remarks on the Cantor-Bernstein equivalence theorem. Then several partially new proofs are given which do not use the natural numbers. The first proof makes use of fixed point sets, but uses neither the axiom of infinity nor the power set axiom. The second one uses Tarski's fixed point theorem on monotone mappings, and the third one proves the Cantor-Bernstein theorem for classes. In the final section the latter theorem is applied to obtain results concerning the class $U$ of all sets in a set theory $\supseteq \roman{KP}$ (Kripke-Platek) \ref[see \n K. J. Barwise\en, Admissible sets and structures, Springer, Berlin, 1975; MR0424560 (54 \#12519)]. For example, $U$ contains as many finite sets as general sets, and as many infinite sets as general sets. Every nonzero cardinality contains as many sets as $U$ itself.

Reviewed by E. Harzheim
Previous Item

MR0878304 (87m:03040)
Rautenberg, Wolfgang
Addendum to my "Note on implicational intermediate consequences" [Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 14 (1986), no. 3, 103--108; MR MR0822707 (87e:03085)].
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 15 (1986), no. 1, 34--35.
03B99

---

The author notes that Question 1 in his paper, whether each (not necessarily finitary) structural strengthening $C$ of the Hilbert calculus $C_H$ satisfies the deduction theorem, has been answered positively by \n A. Wrónski\en.
Previous Item

MR0877305 (88b:03037)
Rautenberg, Wolfgang(D-FUB)
Applications of weak Kripke semantics to intermediate consequences.
Studia Logica 45 (1986), no. 1, 119--134.
03B55

---

The aim of this article is the investigation of intermediate structural consequence relations $\vdash$, where $\vdash^{\rm i}$ $\subseteq$ $\vdash$ $\subseteq$ $\vdash^{\rm k}$ and $\vdash^{\rm i},\vdash^{\rm k}$ are the intuitionistic and the classical propositional consequence, respectively. The instrument of investigation is weak Kripke semantics. It is proved that the addition of a correct (not necessarily finitary) sequential rule $r$ to $\vdash^{\rm i}$ yields the classical consequence if and only if $r$ does not hold in the 2-element linear frame (this is a generalization of the Yankov criterion for 0-ary rules (axioms)). The implicationless intermediate fragments are studied. All maximal elements in the third counterslice are described. (There are four pieces, all tabular.)

Reviewed by V. V. Rybakov
Previous Item

MR0870320 (88f:40007)
Rautenberg, Wolfgang(D-FUB-2)
Zur Approximation von $e$ durch $(1+1/n)\sp n$. (German) [On the approximation of $e$ by $(1+1/n)\sp n$]
Math. Semesterber. 33 (1986), no. 2, 227--236.
40A25 (41A20)

---

Let $a_n=(1+1/n)^n$ $(n\in\bold N)$. On putting $x=1/n$ in the Maclaurin series of $f(x)=(1+x)^{1/x}$ $(0<x\le 1)$, $f(0)=e$, one obtains the expansion $(*)$ $a_n=f(1/n)=e(1-1/(2n)+11/(24n^2) -\cdots)$. Here $e=\lim a_n$ is Euler's number. The approximation of $e$ by this sequence is rather unsatisfactory, as can be seen from the representation $(0<)$ $e-a_n=e/(2n+11/6-\varepsilon_n/n)$, $\varepsilon_n=(5+O(1/n))/72$ $(n\to\infty)$, which follows directly from $(*)$. The author proves the inequalities $0< \varepsilon_n \le\varepsilon_1 =0.0489\cdots$. As a further consequence of the above expansion it is easily shown that $$r_n=e (1+5/(12n))/(1+11/(12n))$$ is the unique linear fractional approximation to $a_n$ for which $r_n-a_n=O(1/n^3)$ as $n\to\infty$. By a more careful analysis the author obtains an explicit estimate of this error term.

\{Reviewer's remark: There is a misprint in formula (5), p. 235. The correct version is given by $(*)$.\}

Reviewed by G. Ramharter
Previous Item

MR0797945 (87d:03092)
Rautenberg, Wolfgang(D-FUB-2)
Consequence relations of $2$-element algebras.
Foundations of logic and linguistics (Salzburg, 1983), 3--22,
Plenum, New York, 1985.
03B99

---

Summary: "We show that the consequence determined by a 2-element algebra has at most 7 proper nontrivial extensions and that it is finitely axiomatizable with sequential rules. This implies among other things the finite axiomatizability of each 2-valued consequence in a finite language."

{For the entire collection see MR0797944 (86h:03003).}
Previous Item

MR0727213 (85b:03029)
Rautenberg, Wolfgang(D-FUB-2)
Modal tableau calculi and interpolation.
J. Philos. Logic 12 (1983), no. 4, 403--423.
03B45 (03C40)

---

This paper deserves to be consulted by those following and contributing to recent investigations of modal propositional logics. The paper may be of especial interest to those concerned with systems with metamathematical applications, viz., the systems G of Lob and Gr of Grzegorczyk, even though no applications are discussed. The focus of the clear but complex exposition and the theorems, proved in considerable detail, is on completeness of tableau versions and interpolation, or lack thereof, for the several systems considered. In Section 2, completeness is shown constructively for: G, Gr, K, M, D, BS5, G.2, Gr.2, K4 and S4; the author also shows that these systems have cut-free axiomatizations, decidability and all the refinements of the finite model property obtained by K. Segerberg, D. H. J. de Jongh and others by different methods. In Section 3 he presents a uniform proof of interpolation for these systems. Section 4 is devoted to a discussion of interpolation, or its absence, for extensions of these systems. The paper closes with two problems: (1) Does interpolation for $L$ imply interpolation for $L(\square p\to p)$? (2) Construct a normal modal logic which has interpolation but fails to have the finite model property.

Reviewed by Charles F. Kielkopf
Previous Item

MR0692901 (84m:03035)
Rautenberg, Wolfgang
$2$-element matrices.
Studia Logica 40 (1981), no. 4, 315--353 (1982).
03B50 (03B20 03G25)

---

Author's summary: "Sections 1, 2 and 3 contain the main result, the strong finite axiomatizability of all 2-valued matrices. Since non-strongly finitely axiomatizable 3-element matrices are easily constructed the result reveals once again the gap between 2-valued and multiple-valued logic. Section 2 deals with the basic cases which include the important $F_i^\infty$ from Post's classification. The procedure in Section 3 reduces the general problem to these cases. Section 4 is a study of basic algebraic properties of 2-element algebras. In particular, we show that equational completeness is equivalent to the Stone property and that each 2-element algebra generates a minimal quasivariety. The results of Section 4 are applied in Section 5 to maximality questions and to a matrix-free characterization of 2-valued consequences in the lattice of structural consequences in any language. Section 6 takes a look at related axiomatization problems for finite algebras and matrices. We study the notion of a propositional consequence with equality and, among other things, present explicit axiomatizations of 2-valued consequences with equality."
Previous Item

MR0603335 (82e:03021)
Rautenberg, Wolfgang
Splitting lattices of logics.
Arch. Math. Logik Grundlag. 20 (1980), no. 3-4, 155--159.
03B45

---

The author proves a "splitting theorem" on normal modal logics, which was announced in his earlier paper [Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 6 (1977), no. 4, 193--201; MR0472480 (57 \#12180)]: If $L$ is any normal modal logic containing the thesis $(p\bigwedge\square p\bigwedge\cdots\bigwedge\square^mp)\supset\square^{m+1}p$, then for each finite subdirectly irreducible model $C$ of $L$, the logic determined by $C$ "splits" the lattice of all normal extensions of $L$, in a sense that the author borrows from R. McKenzie [Trans. Amer. Math. Soc. 174 (1972), 1--43; MR0313141 (47 \#1696)]. However, as the author points out, this result does not extend to all normal modal logics that lack the above thesis. In a footnote added in proof, the author mentions that W. J. Blok has subsequently characterized the models whose logics split the lattice of all modal logics. Blok's result, and further material on applications of the splitting theorem, are presented in the author's book [ Classical and nonclassical propositional logic, Vieweg, Braunschweig, 1979; MR0554370 (81i:03002)].

Reviewed by David Makinson
Previous Item

MR0554370 (81i:03002)
Rautenberg, Wolfgang
Klassische und nichtklassische Aussagenlogik. (German) [Classical and nonclassical propositional logic]
Logik und Grundlagen der Mathematik [Logic and Foundations of Mathematics], 22.
Friedr. Vieweg & Sohn, Braunschweig, 1979. xi+361 pp. ISBN 3-528-08385-9
03-01 (03Bxx 03Gxx)

---

Propositional logic---in particular modal and intuitionistic logic---is one of the fields in mathematical logic most accessible for an algebraization. More specifically: In recent years it became transparent that a series of problems could only be satisfactorily solved by invoking algebraic semantic methods. It is one of the major merits of this book that it presents this development for the first time in book form. It can be hoped that by reading this book many logicians will lose their aversion to algebraic methods, and, vice versa, many algebraists---possibly deterred from logic by the logicians' terminology---will become interested in propositional logic.

In addition to that, the book under review gives an excellent outline of the current state of propositional logic and it shows that this discipline is certainly a most lively part of mathematical logic.

Chapter I contains an introduction to the classical propositional calculus; special emphasis is laid on a generalized version of the interpolation theorem. Chapter II presents some deductive systems for the classical propositional calculus; a general treatment of deductive systems leads to results which are later used as a basis for representation theorems for some classes of logical matrices. In Chapter III a theory of logical matrices as an algebraic semantics for many-valued logics is developed. Due to the intended applications, the attention is mainly focused on matrices for implicative and modal logics.

Chapter IV, the central part of the book, is dedicated to modal logic. It begins with the introduction of the (relational) Kripke semantics for some of the best-known modal logics. The completeness of the standard systems with respect to this semantics is proven. A clarification of the relationship between the relational and the algebraic semantics yields an example of an incomplete modal logic. The lattice of all normal modal logics is studied in some detail. Chapter V treats intuitionistic logic in a way very much parallel to the treatment in Chapter IV. There one also has a (structurally incomplete) relational semantics in contrast to a complete algebraic one. The central topic of this chapter is the lattice of all intermediate logics. Finally, Chapter VI is an appendix in which the basic set-theoretic and algebraic notions and tools are compiled.

Though written as a textbook---the student will welcome the numerous exercises throughout the text as well as the well-selected bibliography---the book is also valuable for the expert in the field. It must be said, however, that its exposition, in particular the heavy use of abbreviations, makes it somewhat hard to read. It might be a good idea for a translation into English (which would be welcome) to take care of this minor deficiency.

\{Reviewer's remarks: The German terminology is sometimes rather unusual; some examples are "endlich basiert" (p. 100), "Opremum" (p. 156), "Splitlogik" (p. 223), "Subalgebra" instead of "Unteralgebra" (p. 320) and "simpel" instead of "einfach" (p. 340). As the author points out, on p. 187, line 11, `$\omega^r$ ist $R$-Struktur, also $R\subseteq L\omega\subseteq LB^*$', should be replaced by `$\text{In}\,\omega^r$, also auch in $B^*$, gelten $(\square r),(\square\rho)$'.\}

Reviewed by Peter Köhler
Previous Item

MR0534737 (80h:03032)
Rautenberg, Wolfgang
More about the lattice of tense logics.
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 8 (1979), no. 1, 21--26.
03B45 (03G10)

---

The author states, without proof, several results concerning tabular and pretabular propositional tense logics, and concerning the structure of the lattice of tense logics.

Reviewed by S. K. Thomason
Previous Item

MR0485213 (58 #5064)
Rautenberg, Wolfgang
Der Verband der normalen verzweigten Modallogiken. (German)
Math. Z. 156 (1977), no. 2, 123--140.
02C10

---

Denote by $K^k$ the $k$-fold ramified minimal normal modal logic (i.e., $K^k$ is like the system $K$ except for having $k$ possibility functors $\lozenge_1,\cdots,\lozenge_k$ instead of the single $\lozenge$), $k\geq 1$. Let $\scr N^k$ be the lattice of normal extensions of $K^k$. The author proves various results concerning the structure of $\scr N^k$. Among these are that $\scr N^k$ is a Heyting algebra, and the system of all tabular logics in $\scr N^k$ is a filter in $\scr N^k$, and hence a lattice. These results can be translated into theorems on the lattice of Boolean algebras with $k$ quasiclosure operations (a generalization of the notion of topological Boolean algebras) characterized by the laws $\lozenge(a\cup b)\leq\lozenge a\cup\lozenge b$ and $\lozenge 0=0$.

Reviewed by I. Ruzsa
Previous Item

MR0472480 (57 #12180)
Rautenberg, Wolfgang
The lattice of normal modal logics.
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 6 (1977), no. 4, 193--201.
02C10 (08A15)

---

Several results are presented on the structure of the lattice of normal modal logics, obtained by means of Jónsson's results on congruence-distributive varieties. \{The paper is a preliminary report, in the style of an abstract.\}

Reviewed by S. K. Thomason
Previous Item

MR0429491 (55 #2504)
Rautenberg, Wolfgang
Some properties of the hierarchy of modal logics. (Preliminary report)
Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic 5 (1976), no. 3, 103--105.
02C10

---

The author takes into consideration modal logics belonging to the class $EM^0$ of all extensions of $M^0$, where $M^0$ is the modal system of Feys-von Wright. It is well known that $EM^0$ is, with respect to inclusion, a complete lattice in which $M^0$ is the zero element and the trivial modal logic $M_\boxdot$ is the unit element. The author gives some interesting theorems on connections between $S5$, $S4$, $M^0$, $M_\boxdot$ and $B$ and other modal logics belonging to $EM^0$.

Reviewed by Jerzy Kotas
Previous Item

MR0414340 (54 #2443)
Korec, Ivan; Rautenberg, Wolfgang
Model-interpretability into trees and applications.
Arch. Math. Logik Grundlagenforsch. 17 (1975/76), no. 3-4, 97--104.
02G05 (02G15 02H05 05C05)

---

By a tree the authors mean a simple graph without circuits, where a simple graph is a structure with a binary irreflexive and symmetric relation. An $n$-separated graph, for $n\geq 0$, is a simple graph in which distinct circuits have at most $n$ points in common. K. Hauschild and the second author [Z. Math. Logik Grundlagen Math. 17 (1971), 47--55; MR0289300 (44 \#6491); Hauschild, H. Herre and the second author, ibid. 18 (1972), 457--480; MR0325390 (48 \#3737)] proved that the theory of $n$-separated graphs can be interpreted in the theory of 0-separated graphs. In the present paper the authors prove that this latter theory is interpretable in the theory of trees. They show that each tree is stable in some infinite cardinal and hence the same applies to $n$-separated graphs. They give a simplified proof of a result of the paper cited above, namely that each tree is, for all $n\geq 1$, elementary equivalent with respect to $n$ variable sentences to a tree of bounded finite valency, the bound being computable from $n$. They can then deduce the known results that the first order theory of trees and hence of $n$-separated graphs are decidable. The question is raised whether this bounded finite valency theorem extends to monadic second order formulas.

Reviewed by A. B. Slomson
Previous Item

MR0392784 (52 #13597)
Rautenberg, Wolfgang
Eine Synthese der axiomatischen und der kardinalen Definition der natürlichen Zahlen. (German)
Math.-Phys. Semesterber. 22 (1975), no. 2, 225--239.
10-01 (02G15)

---

The author's primary concern is pedagogical; he wishes to give a treatment of the foundations of classical arithmetic that is both psychologically natural and also admits a rigorous justification. He suggests the following order of development: characterization of a natural number sequence (in this matter at least a footnote on T. Skolem's work of 1933 and 1934 as well as later developments would seem in order), the existence of a natural number sequence in the framework of set theory using the axiom of infinity, Dedekind's justification for the recursive definition of functions, order defined by initial segments of a natural number sequence, addition and multiplication defined set theoretically.

Reviewed by D. Nelson
Previous Item

MR0337569 (49 #2338)
Hauschild, Kurt; Rautenberg, Wolfgang
Entscheidungsprobleme der Theorie zweier Äquivalenzrelationen mit beschränkter Zahl von Elementen in den Klassen. (German)
Collection of articles dedicated to Andrzej Mostowski on the occasion of his sixtieth birthday, I.
Fund. Math. 81 (1973), no. 1, 35--41.
02H05 (02G05)

---

Let $E_{n,m} (2\leq n\leq m<\omega)$ be the class of structures $\langle M,R_0,R_1\rangle$, where $R_0$ and $R_1$ are equivalence relations on $M$ such that (i) no two elements of $M$ are in both the relations $R_0$ and $R_1$, and (ii) the equivalence classes of $R_0$ have at most $n$ and those of $R_1$ at most $m$ elements. Let $E_n$ be defined analogously without cardinality restrictions for the classes of $R_1$.

The results are as follows: (1) (a) Th $E_n$ (the first-order theory of $E_n$, with or without identity) is recursively undecidable; (b) $E_n$ is a reduction class for predicate calculus; (c) $E_n$ is universal with respect to model interpretability. (2) (a) and (b) also hold for $E_{n,m}$ with $m>2$, while (c) does not hold, and $E_{2,2}$ is decidable.

(1) and (2) (a) are obtained by model interpretation from corresponding results for suitable classes of graphs, contained in the paper by the authors and H. Herre [Z. Math. Logik Grundlagen Math. 17 (1971), 47--55; MR0289300 (44 \#6491); ibid. 18 (1972), 457--480; MR0325390 (48 \#3737)]. This goes through also for the subclasses $\dot E_n,\dot E_{n,m}$ consisting of the structures with equivalence classes of exactly the cardinalities indicated. The result (a) is also established for the class of finite structures in $E_{2,3}$. Methods for getting (2)(b) and $¬(\text c)$ are mentioned.

\{For more complete bibliographic information about the collection in which this article appears, including the table of contents, see MR0332487 (48 \#10814).\}

Reviewed by W. Schwabhauser {For errata and/or addenda to the original MR item see MR 49 Errata and Addenda in the paper version}


Previous Item

MR0354338 (50 #6818)
Hauschild, Kurt; Herre, Heinrich; Rautenberg, Wolfgang
Entscheidbarkeit der elementaren Theorie der endlichen Bäume und verwandter Klassen endlicher Strukturen. (German. Russian, English, French summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 21 (1972), 497--502.
02G05 (05C30)

---

In der vorliegenden Arbeit wird die Entscheidbarkeit der folgenden Theorien bewiesen: (1) die elementare Theorie der endlichen Bäume; (2) die elementare Theorie der endlichen gerichteten Bäume; (3) die Theorie $T_n{}^{\text{fin}}$ der endlichen symmetrischen Graphen der Weite $\leq n$; (4) die Theorie $T_{\text{fin}}^n$ der endlichen $n$-separierten Graphen; und (5) die Theorie der endlichen gerichteten $n$-separierten Graphen.

Dabei wird $\germ G=\langle G,R\rangle$ ein Graph genannt, wenn $R$ eine irreflexive symmetrische binäre Relation auf $G$ ist. Der Graph $\germ G$ wird $n$-separiert genannt, wenn keine zwei Kreise mehr als $n$ Punkte gemeinsam haben. Für einen Punkt $a$ des Graphen $\germ G=\langle G,R\rangle$ sei $v(a)=\text{Card}\{x\colon\langle x,a\rangle\in R\}$ die Valenz von $a$. Das Supremum über alle $v(a)$ (wobei $a$ den Graphen $G$ durchläuft) wird die Valenz von $\germ G$ genannt und mit $v(\germ G)$ bezeichnet. Unter Verwendung von Ehrenfeucht-Spielen wird gezeigt, daß die Valenz-Funktion $V(n)=\text{Min}\{j\colon\forall\germ A\in B^{\text e}\exists\germ B\inB^{\text e}(\germ A\equiv{}_n\germ B\,&\,v(\germ B)\leq j)\}$ rekursiv ist (hier ist $B^{\text e}$ die Klasse aller endlichen Bäume). Danach wird gezeigt, daß jeder endliche Baum der Valenz $\leq t$ eine rekursive Majorante für die Längen-Funktion besitzt. Das impliziert die Entscheidbarkeit von $\text{Th}(B^{\text e})$. Aus diesem Ergebnis folgt (2). Unter Verwendung der Technik der Modell-Interpretierbarkeit werden die Ergebnisse (3), (4), (5) bewiesen. Die Beweise werden stellenweise nur skizziert.

Reviewed by U. Felgner
Previous Item

MR0347576 (50 #79)
Hauschild, Kurt; Herre, Heinrich; Rautenberg, Wolfgang
Entscheidbarkeit der monadischen Theorie $2$. Stufe der $n$-separierten Graphen. (German. Russian, English, French summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 21 (1972), 507--511.
02G05 (02H10 05C30)

---

In einer früheren Arbeit [Z. Math. Logik Grundlagen Math. 18 (1972), 457--480; MR0325390 (48 \#3737)] hatten die drei Autoren gezeigt, daß für jede natürliche Zahl $n$ die Theorie der ersten Stufe der $n$-separierten Graphen entscheidbar ist. Es wird in der vorliegenden Arbeit gezeigt, daß auch für jedes $n$ die monadische Theorie der zweiten Stufe der abzählbaren $n$-separierten Graphen entscheidbar ist. Dabei wird ein Graph $\germ G=\langle G,\sigma\rangle n$-separiert genannt, falls je zwei verschiedene (!) Kreise höchstens $n$ gemeinsame Punkte besitzen. Es wird gezeigt, daß die monadische Theorie $T^n$ der zweiten Stufe der $n$-separierten Graphen in der monadischen Theorie $T_0{}'$ der zweiten Stufe der Bäume modellinterpretierbar ist. Dazu wird $T^n$ in $T^0$ und $T^0$ in $T_0{}'$ modellinterpretiert. Der Beweis der Modellinterpretierbarkeit von $T^0$ in $T_0{}'$ macht wesentlichen Gebrauch von der zweiten Stufe indem über das einstellige (monadische) Prädikat "ist Weg" quantifiziert wird. Es ist demgegenüber unbekannt, ob auch die Theorie der ersten Stufe der 0-separierten Graphen in der Theorie der ersten Stufe der Bäume modellinterpretierbar ist.

Reviewed by U. Felgner
Previous Item

MR0325390 (48 #3737)
Hauschild, Kurt; Herre, Heinrich; Rautenberg, Wolfgang
Interpretierbarkeit und Entscheidbarkeit in der Graphentheorie. II. (German)
Z. Math. Logik Grundlagen Math. 18 (1972), 457--480.
02H15 (05C10)

---

Es sei $\Gamma_n$ die Klasse aller Graphen $G=\langle G,R\rangle$ ($R$ ist eine irreflexive symmetrische binäre Relation $\text{auf}\,G$), in denen alle Kreise höchstens die Länge $n+2$ haben. Ferner sei $T_n=\text{Th}(\Gamma_n)$ die Theorie der ersten Stufe von $\Gamma_n$. In der vorliegenden Arbeit wird der folgende Haupstatz bewiesen: Für jede natürliche Zahl $n\geq 0$ ist $T_n$ eine (rekursiv) entscheidbare Theorie. Der Beweis erfolgt in mehreren Schritten. Es wird zunächst ($§$ 2) gezeigt, daß die Theorie $T_{n+1}$ in der Theorie $T_n$ modellinterpretierbar ist. Als unmittelbare Konsequenz ergibt sich daraus, daß $T_{n+1}$ entscheidbar ist, falls $T_n$ entscheidbar ist. Es genügt also die Entscheidbarkeit von $T_0$, der Theorie der Bäume, nachzuweisen. Für ein Element $x$ eines Graphen $\langle G,R\rangle$ sei $\text{val}(x)=\text{Card}\{y;\langle x,y\rangle\in R\}$ die Valenz von $x$. Es wird bewiesen ($§$ 3), daß $T_0$ genau dann entscheidbar ist, wenn alle Erweiterungen der Form $T_0\cup\{¬\exists x\colon\text{val}(x)>k\}$ für $1\leq k\in\omega$ entscheidbar sind. Die letzteren Theorien sind nach einem bisher unpublizierten Satz des zweiten Ver-fassers (Dissertation, Berlin) aber alle entscheidbar. Also sind $T_0$ und $T_n$ entscheidbar. Mit den bisher entwickelten Methoden werden im anschließenden Paragraphen 4 die Entscheidbarkeit von vielen anderen Theorien bewiesen. Das graphentheoretisch interessante Maximalkreistheorem aus $§$ 1 wird benutzt um nachzuweisen, daß die Theorie $T^n$ der $n$-separierten Graphen quasi-endlichvalent ist. Dabei heißt ein Graph $\langle G,R\rangle n$-separiert, wenn je zwei seiner Kreise höchstens $n$ gemeinsame Punkte besitzen. Mit den Methoden von $§$ 3 folgt jetzt die Entscheidbarkeit von $T^n$. Als Korollare ergeben sich: (i) Die Theorie der $n$-separierten gerichteten Graphen ist entscheidbar; (ii) die Theorie $T_f$ einer einstelligen Funktion ist entscheidbar, und (iii) die Theorie $T_u$ aller Graphen, deren Kreise alle eine ungerade Länge haben, ist entscheidbar. Überraschend ist, daß demgegenüber die Theorie $T_g$ aller Graphen, in denen sämtliche Kreise eine gerade Länge haben, als unentscheidbar nachgewiesen wird. Auch die Theorie der $k$-chromatischen Graphen $(k\geq 2)$ ist unentscheidbar.

Die Arbeit kann unabhängig von Teil I [der erste und dritte Verfasser, dieselbe Z. 17 (1971), 47--55; MR0289300 (44 \#6491)] gelesen werden.

Reviewed by U. Felgner
Previous Item

MR0300879 (46 #39)
Hauschild, Kurt; Rautenberg, Wolfgang
Interpretierbarkeit in der Gruppentheorie. (German)
Algebra Universalis 1 (1971/72), 136--151.
02G05

---

The concept of interpretability used in this paper is a strong form of relative interpretability due to A. Tarski [ Undecidable theories, North Holland, Amsterdam, 1953; MR0058532 (15,384h); second printing, 1968; MR0244048 (39 \#5365)]. A theory $T$ is universal (with respect to interpretability) if every theory can be interpreted in a consistent extension of $T$. Universal theories are undecidable. The purpose of this paper is to show that various theories are universal. The proofs are carried out by the same model-theoretic technique that was used for undecidability proofs by M. O. Rabin [ Logic, methodology and philosophy of science\/ (Proc. 1964 Internat. Congr.), pp. 58--68, North Holland, Amsterdam, 1965; MR0221924 (36 \#4976)]. First, certain special theories of irreflexive symmetric graphs are shown to be universal. These theories are used to show that the following classes of algebras have universal theories: commutative cancellation semigroups (with identity), groups generated by elements of order 2, relatively free groups whose defining relations hold in all commutative groups, and relatively free groups defined by relations of the form $ab=ba$ between generating elements.

Reviewed by S. Comer
Previous Item

MR0289300 (44 #6491)
Rautenberg, Wolfgang; Hauschild, Kurt
Interpretierbarkeit und Entscheidbarkeit in der Graphentheorie. I. (German)
Z. Math. Logik Grundlagen Math. 17 1971 47--55.
02.74 (05.00)

---

Eine (in der ersten Stufe formalisierte) Theorie $T$ heiße interpretierbar in der Theorie $S$, falls es eine rekursive Injektion $Rd$ von der Sprache von $T$ in die von $S$ gibt, so daß stets $\alpha\in T$ genau dann, wenn $Rd(\alpha)\in S$. In den folgenden Resultaten wird eine solche Interpretierbarkeit jeweils dadurch gezeigt, daß auf universelle Weise für jedes $T$-Modell eine Einbettung in ein $S$-Modell angegeben wird, wobei die Klasse der so erhaltenen $S$-Modelle die Modellklasse einer endlichen Erweiterung von $S$ ist.

Ein Graph vom Range $n\geq 1$ (für $n=1$ ein einfacher Graph) ist hier eine Struktur $\germ G=\langle G,r_1,\cdots,r_n\rangle$, wobei $r_1,\cdots,r_n$ binäre Relationen über $G$ ("Kantenmengen") sind. $\germ G$ heißt ungerichtet, falls alle $r_\nu$ symmetrisch sind. $\germ G$ heißt höchstens $m$-valent, falls jeder "Punkt" $p\in G$ höchstens $m$ Kanten angehört. Es wird u.a. gezeigt: (1) Die Theorie der höchstens $m$-valenten Graphen beliebigen Ranges $n$ ist in der Theorie der einfachen ungerichteten (reduzierten) höchstens 3-valenten Graphen interpretierbar. (2) Die Theorie der (gerichteten oder ungerichteten) höchstens $m$-valenten Graphen vom Rang $n$ ist nur im Falle $m\leq 2$ entscheidbar. Korollar: Die logische Theorie zweier vor- und nacheindeutiger Relationen ist unentscheidbar (diejenige einer solchen Relation ist dagegen entscheidbar). (3) Die Theorie der gerichteten Graphen mit höchstens $m$ Ausgangskanten für jeden Punkt ist für $m\geq 2$ unentscheidbar, sogar unter der zusätzlichen Einschränkung, daß in jeden Punkt höchstens 2 Eingangskanten münden (für $m=1$ ist sie dagegen entscheidbar nach A. Ehrenfeucht [Notices Amer. Math. Soc. 6 (1959), 268, Abstract 556--37]. (4) Die Theorie der höchstens $m$-valenten Graphen der Höchstweite $l$ (d.h., bei denen Zyklen höchstens die Länge $l$ besitzen) ist für beliebiges $l,m$ in der Theorie $T_B$ der Bäume (d.h. der einfachen Graphen ohne Zyklen) interpretierbar und damit (wie $T_B$) entscheidbar. Die Entscheidbarkeit von $T_B$ wird gezeigt (Skizze, ausführliche Darstellung angekündigt) durch Rückführung auf ein Resultat von Ehrenfeucht [loc. cit.].

Reviewed by W. Schwabhäuser
Previous Item

MR0332469 (48 #10796)
Herre, Heinrich; Rautenberg, Wolfgang
Das Basistheorem und einige Anwendungen in der Modelltheorie. (German. Russian, English, French summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 19 (1970), 579--583.
02H05 (02G15 02J05)

---

The authors first consider conditions for an element of a Boolean algebra, etc., to belong to a subalgebra, and hence conditions for a subset to be a basis of (i.e., to generate) the algebra. For example, if $B$ is a Boolean algebra, $a\in B$, and if $M$ is a sub-upper-semi-lattice of $B$, then $a\in M$ if and only if each ultrafilter $U$ of $B$ containing $a$ shares with $M$ an element $b\leq a$; a subset $X$ of a Boolean algebra generates $B$ if each ultrafilter $U$ of $B$ is generated by $U\cap B(X)$, where $B(X)$ is the sub-algebra generated by $X$. Using these results, the authors give proofs of four known theorems. They are: a formula is preserved under extension models of a theory $T$ if and only if it is equivalent under $T$ to an existential formula; Beth's theorem about definability; Hanf's theorem about a necessary and sufficient condition for models of the theory of one binary relation to be elementarily equivalent and Ju. L. Er\v sov's condition [Algebra i Logika Sem. 3 (1964), no. 3, 17--38; MR0180490 (31 \#4725)] for two separable Boolean algebras to be elementarily equivalent.

Reviewed by M. Yasuhara
Previous Item

MR0329880 (48 #8220)
Hauschild, Kurt; Rautenberg, Wolfgang
Universelle Interpretierbarkeit in Verbänden. (German. Russian, English, French summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 19 (1970), 575--577.
02G05 (02H15 06A35)

---

A first-order theory $T$ is said to be universal if every first-order theory $S$ with the same language $L(T)$ is relatively interpretable in an extension of $T$ with language $L(T)$. For lattices with zero element, $\cap$-atomic [$\cap$-atomless] means the same as atomic [atomless], while a lattice is called $\cup$-atomic or $\cup$-atomless if its dual lattice is $\cap$-atomic or $\cap$-atomless, respectively.

The authors show that the following theories are universal: (1) the theory of lattices of length $\leq 3$; (2) the theory of $\cap$-atomic and $\cup$-atomless distributive lattices; (3) the theory of $\cap$-atomic and $\cup$-atomic distributive lattices; (4) the theory of $\cap$-atomless and $\cup$-atomless distributive lattices. This gives the consequence that these theories (and subtheories with the same language) are recursively undecidable.

Reviewed by W. Schwabhauser
Previous Item

MR0278159 (43 #3890)
Rautenberg, Wolfgang
Axiomatische Theorie der Translationsgruppen affiner Räume und Translationsebenen. (German)
Math. Nachr. 46 1970 171--182.
50.05

---

The author's aim is to replace geometric arguments by algebraic arguments in a so-called $T$-module. Let $\|$ (parallel) be an equivalence relation on the non-zero elements of an abelian group $M$. A ray $L(a)$ ($a\neq 0$ in $M$) is an equivalence class (plus 0). $(M,\|)$ is called $T$-module if the rays are subgroups of $M$ and if always $L(b+c)\subset L(b)+L(c)$. A multiplier of $M$ is an endomorphism that maps every ray into itself. The multipliers form a field $K$, making $M$ into a $K$-space. $M$ is Desarguesian if the multiplier field $K$ is transitive on each ray. This is equivalent to the following Desargues configuration: $a\|a'$, $b\|b'$, $c\|c'$, $a-b\|a'-b'$, $a-c\|a'-c'$ imply that $b-c\|b'-c'$. $a$ is dependent on $b,\cdots,c$ if $a\in L(b)+\cdots+L(c)$. The rank of $M$ is the maximal number of independent elements. $\text{rank}(M,\|)\leq\dim(M,K)$. $M$ is Desarguesian if and only if rank = dimension. $M$ can be non-Desarguesian only if $\text{rank}(M)=2$. In that case $M\simeq L\oplus L$ for every ray $L$. Finally, all non-Desarguesian $T$-modules $L\oplus L$ are constructed, given a Desarguesian $T$-module $L$.

Reviewed by A. Cronheim
Previous Item

MR0247560 (40 #825)
Rautenberg, Wolfgang
Euklidische und Minkowskische Orthogonalitätsrelationen. (German)
Fund. Math. 64 1969 189--196.
50.05

---

Eine Relation zwischen den Geraden einer Translationsebene heißt Orthogonalitätsrelation, wenn (O$_{\text 1}$) Orthogonalität nur von den Richtungen ab hängt; (O$_{\text 2}$) der Höhesatz für Dreiecke gilt; (O$_{\text 3}$) eine Richtung nur eine Lotrichtung hat; (O$_{\text 4}$) es wenigstens zwei orthogonale Paare gibt.

Diese Forderungen kennzeichnen die euklidischen und minkowskischen Orthogonalitätsrelationen zusammen mit keinen bzw. zwei selbstorthogonalen Richtungen. Sie sind durch drei kollineare Punkte $O,A,B$ und einen Punkt $C$ nicht auf $AB$ bestimmt $(AB\perp OC,CA\perp CB)$.

Die Relation $V(O;A,B)$ gilt, da es einen Punkt $D$ auf $OAB$ gibt, der koordinatenmäßig das geometrische Mittel der Punkte $A$ und $B$ bezüglich $O$ ist. (Alles wird aber kurz und elegant synthetisch hergeleitet.) Die Relation ist notwendig und hinreichend für minkowskische Orthogonalität, und gilt dann für jedes Tripel. In einer angeordneten Ebene ist die Orthogonalität euklidisch, sobald zwei (und damit alle) orthogonale Paare sich trennen.

Ein Geradenpaar heißt kommensurabel wenn sein Schnittpunkt auf dem Mittellot einer Strecke mit End-punkten auf den Geraden liegt, oder die Geraden parallel sind. Ein orthogonales, nicht selbstorthogonales, kommensurables Paar trennt sich in einer angeordneten Ebene.

Weiter gilt: $V(O;A,B)$ gilt genau dann, wenn es einen Punkt $C$ gibt, sodaß $OA$ und $OC$ kommensurabel sind bezüglich $AB\perp CA$, $CO\perp CB$.

Gilt $V(A;B,C)$ für alle Tripel, dann sind alle Paare kommensurabel für jede Orthogonalitätsrelation; gilt von $V(A;B,C)$, $V(B;A,C)$, $V(C;A,B)$ für jedes Tripel höchstens eine nicht, dann gilt dasselbe für jede euklidische Orthogonalitätsrelation.

Reviewed by G. J. Schellekens
Previous Item

MR0227010 (37 #2595)
Rautenberg, Wolfgang
Unterscheidbarkeit endlicher geordneter Mengen mit gegebener Anzahl von Quantoren. (German)
Z. Math. Logik Grundlagen Math. 14 1968 267--272.
02.54

---

For any linearly ordered sets $A$ and $B$ and any positive integer $n$, let $A\equiv_nB$ be the assertion that every sentence with at most $n$ quantifier occurrences in a first-order language with identity and one binary predicate symbol $<$ is true of $A$ if and only if it is true of $B$. For any positive integer $k$, let $I_k$ be a finite linearly ordered set with $k$ elements. For each positive integer there exists an integer $q_n$ which is the least positive integer such that $I_k\equiv_nI_m$ for all $k$, $m\geq q_n$. It is shown that $q_n$ is determined by the recursion equations $q_1=1$, $q_2=2$, $q_{n+1}=2q_n$ for even $n$, and $q_{n+1}=2q_n+1$ for odd $n$.

Reviewed by M. R. Krom
Previous Item

MR0221925 (36 #4977)
Rautenberg, Wolfgang
Nichtdefinierbarkeit der Multiplikation in dividierbaren Ringen. (German)
Z. Math. Logik Grundlagen Math. 14 1968 59--60.
02.57 (06.00)

---

A ring is divisible if its abelian group is divisible. The author proves that for every ordered divisible ring with a unit element (in particular, for every ordered field) multiplication is not explicitly elementarily definable in terms of $0$, $+$, $<$, and $1$.

Reviewed by S. Comer
Previous Item

MR0218228 (36 #1316)
Rautenberg, Wolfgang
Elementare Schemata nichtelementarer Axiome. (German)
Z. Math. Logik Grundlagen Math. 13 1967 329--366.
02.50

---

Peanosches Induktionsaxiom, Dedekindsches Stetigkeitsaxiom, Wohlordnungsaxiom, Archimedisches Axiom sind Beispiele für Axiome, deren Modellklassen nicht elementar sind. Da solche Axiome aber gewöhnlich nur für spezielle Klassen von Algebren formuliert werden, kann man ihre elementare Theorie $T$ betrachten, die sich auf die Modelle der speziellen Algebrenklasse bezieht. Neben dieser elementaren Theorie werden elementare Axiomenschemata $S$ nichtelementarer Axiome interessieren, deren Gültigkeitsbereich auf die speziellen Algebrenklassen beschränkt ist. Hervorgehend aus dieser beschriebenen Situation, hat man eine Reihe von Fragen, denen sich der Autor (hinsichtlich Wohlordnungsschema, Schemata zum Archimedischen Axiom) widmet: Beziehungen zwischen $S$ und $T$, Entscheidbarkeit und Axiomatisierbarkeit von $T$, Strukturanalyse des Raumes der vollständigen Erweiterungen (CE-Raum) und der Booleschen Algebra der endlichen Erweiterungen (FE-Algebra) für $S$ und $T$, Beziehungen zwischen CE-Raum und FE-Algebra. Als Beispiele aus der Fülle von Einzelresultaten nennen wir: Nichtendliche Axiomatisierbarkeit des Wohlordnungs-schemas, neuer Beweis der Entscheidbarkeit dieses Schemas; Nichtaxiomatisierbarkeit der elementaren Theorie der archemidisch geordneten Körper (und dichten Ringe).

Reviewed by W. Benz
Previous Item

MR0218227 (36 #1315)
Rautenberg, Wolfgang
Die elementare Theorie der diskret geordneten Mengen. (German. English, French summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 15 1966 677--680.
02.50

---

The paper is concerned with some technical results concerning the theory (in elementary predicate calculus) of discrete linear order, i.e., of a linear order such that every element except the last element (if any) has an immediate predecessor. The decidability of this theory follows from a result announced by A. Ehrenfeucht [Notices Amer. Math. Soc. 6 (1959), 268, Abstract 556--37]. The author describes a method of eliminating quantifiers, as well as other results concerning representation of formulae and model-theoretic properties.

Reviewed by H. B. Curry
Previous Item

MR0203552 (34 #3402)
Rautenberg, Wolfgang
Über Hilberts Schnittpunktsätze. (German)
Z. Math. Logik Grundlagen Math. 12 1966 57--59.
50.05 (50.10)

---

Der Verfasser behandelt die auf D. Hilbert [ Grundlagen der Geometrie, achte Auflage, Teubner, Stuttgart, 1956; MR0080308 (18,227a); englische Übersetzung, Open Court, La Salle, Ill., 1959; MR0116216 (22 \#7011); neunte Auflage, Teubner, Stuttgart, 1962; MR0177322 (31 \#1585)] zurückgehende Frage, welche mit den Begriffen "Punkt", "Gerade", "inzident", "zwischen" formulierbaren Sätze der ebenen reellen euklidischen Geometrie bereits in der ebenen affinen Geometrie mit Pappus-Pascal und Anordnung beweisbar sind. Zu ihnen gehören, wie Hilbert [loc. cit.] skizziert hat, die "reinen Schnittpunktsätze", die der Verfasser begrifflich präzisiert, aber auch noch weitere Sätze, die die Quantifikatoren "es gibt" und "für alle" nur in eingeschränkter Weise enthalten.

Um dies zu beweisen, benutzt der Verfasser die Möglichkeit, jeden geordneten Körper reell abzuschliessen, und die Vollständigkeit der Theorie der geordneten affinen Ebenen über reell abgeschlossenen Körpern [A. Tarski, The axiomatic method\/ (Proc. Internat. Sympos., Univ. of California, Berkeley, Calif., 1957--1958), pp. 16--29, North-Holland, Amsterdam, 1959; MR0106185 (21 \#4919)]. An Hand dieser Probleme erläutert er den Begriff der Persistenz einer Relation in einer elementaren Theorie bezüglich eines Modellpaares $µ\subsetµ'$ der Theorie [siehe A. Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland, Amsterdam, 1963; MR0153570 (27 \#3533)].

Reviewed by F. Bachmann
Previous Item

MR0195736 (33 #3934)
Rautenberg, Wolfgang
Hilberts Schnittpunktsätze und einige modelltheoretische Aspekte der formalisierten Geometrie. (German. Engglish summary)
Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe 14 1965 409--415.
02.50 (50.05)

---

The first part gives a brief introduction to the model-theoretic approach to elementary geometry. Then, the notion of persistence of geometric relations is discussed, using as main tool the following theorem. Let $T'$ be an extension by definition of a theory $T$, and $R$ a defined relation in $T'$. If $R$ has both a $\exists$-definition and a $\forall$-definition, then $R$ is persistent with respect to $T$. Whereas the notions of collinearity of points and coincidence of lines are easily seen to be persistent by use of this test, the notion of parallelism presents difficulties which so far seem to be unresolved. Finally, the results on persistence are applied to the problem whether a Hilbert "Schnittpunktsatz" can be proved from the axioms of groups I and II only (i.e., without the use of continuity axioms), and an affirmative answer is obtained.

Reviewed by J. E. Fenstad
Previous Item

MR0171710 (30 #1937)
Rautenberg, Wolfgang
Beweis des Kommutativgesetzes in elementar-archi- medisch geordneten Gruppen. (German)
Z. Math. Logik Grundlagen Math. 11 1965 1--4.
02.50

---

A (totally) ordered group $G$ is said to be Archimedean if for each pair of positive (greater than the identity) elements $a,b$ of $G$ there is a positive integer $n$ such that $b<a^n$. A lower segment of $G$ is a proper subset $S$ of $G$ such that $x<y\in S$ implies $x\in S$. It is well known that $G$ is Archimedean if and only if (A) for each lower segment $S$ of $G$, and for each positive $c\in G$, $S$ is a proper subset of $Sc$. The author defines an ordered group to be elementarily Archimedean if condition (A) holds for those lower segments which can be defined in elementary language. By a well-known theorem of Hölder, every Archimedean ordered group is a subgroup of the real numbers, and hence is commutative. The author proves that every elementarily Archimedean ordered group is commutative. The result does not follow from Hölder's theorem since there are elementarily Archimedean ordered groups which are not Archimedean (but the author does not give any examples).

Reviewed by W. C. Holland
Previous Item

MR0157273 (28 #509)
Rautenberg, Wolfgang
Konstruktionen in der hyperbolischen Geometrie. (German)
Math. Nachr. 25 1963 151--158.
50.40

---

The following three construction postulates are admitted: (1) To construct the line through two different points; (2) To construct the point of intersection of two inter-secting lines; (3) To construct the parallel through a point to a half-line. The author describes simple constructions for perpendiculars and for the common parallel to two half-lines. He also shows how to construct a segment $CD$, congruent to a given segment, on a given half-line with endpoint $C$. All these constructions follow from well-known theorems of projective geometry, applied to Klein's model for hyperbolic geometry.

Reviewed by A. Heyting
Previous Item

MR0152439 (27 #2419)
Rautenberg, Wolfgang
Bemerkung zur Axiomatik der Vektorgeometrie. (German)
Z. Math. Logik Grundlagen Math. 9 1963 173--174.
02.54 (50.05)

---

From the author's introduction: "Als elementare euklidische Inzidenzgeometrie (EIG) bezeichnen wir die axiomatische Theorie der Hilbertschen Inzidenzaxiome einschließlich des Desarguesschen Satzes. Ein Modell dieser Theorie heiße ein euklidischer Inzidenzraum (EIR). Jedem EIR entspricht ein Vektorraum; Vektoren sind die Klassen gleichgerichteter gleich langer Strecken und Operatorenkörper ist der zu EIR gehörende Skalarkörper. Es ist leicht zu zeigen, daß die Klasse aller Vektorräume der EIG in der üblichen Weise folgendermaßen axiomatisch charakterisiert werden kann: (i) die Vektoren bilden einen Modul, (ii) die Skalare bilden einen Schiefkörper, (iii) es gelten das Assoziativgesetz und die Distributivgesetze für die Skalar-Vektor-Multiplikation. Diese Art der axiomatischen Charakterisierung der Vektorräume als Operatorstrukturen kann, wie hier dargelegt werden soll, ersetzt werden durch ein Axiomensystem, welches nur Variable für Vektoren enthält, die Vektoraddition und eine zweistellige Relation $\Lambda(a,b)$, welche besagt, daß die Vektoren $a$ und $b$ linear abhängig sind."
Previous Item

MR0147367 (26 #4883)
Rautenberg, Wolfgang
Über metatheoretische Eigenschaften einiger geometrischer Theorien. (German)
Z. Math. Logik Grundlagen Math. 8 1962 5--41.
02.54

---

(i) There is no decision method for the subsystems of the euclidean, hyperbolic and projective geometry of the space and of the arguesian plane with incidence as unique primitive relation. (ii) There is no decision method for the elementary theory of groups with any supplementary axioms satisfied by the group of movements. Moreover, two sets of axioms are discussed: (iii) an infinite set of elementary axioms of the plane geometry with the relations of incidence and betweenness; (iv) a finite set of axioms involving the non-elementary archimedean axiom with the relations of incidence, betweenness and congruence. Theorems: The system (iii) is complete. The class of models of the system (iv) is equal to the class of cartesian spaces of dimension 2 over commutative fields with archimedean order.

Reviewed by S. Ja\'skowski
Previous Item

MR0137648 (25 #1099)
Rautenberg, Wolfgang
Unentscheidbarkeit der euklidischen Inzidenzgeometrie. (German)
Z. Math. Logik Grundlagen Math. 7 1961 12--15.
02.74

---

Let a theory be called completely undecidable if it contains a finitely axiomatizable essentially undecidable subtheory. The the relativized arithmetic of rational numbers $\text P(+,·,R)$ is completely undecidable. Let $\text E(i,0,e,g)$ be elementary rational plane cartesian geometry, where variables range over rational points and lines, $xiy$ is true if and only if $x$ is a point, $l$ a line and $x$ is incident with $y$, 0 is the origin, $g$ the axis of $X$ and $e$ the point $(1,0)$. It is shown that $\text P(+,·,R)$ is interpretable in $\text E(i,0,e,g)$; hence the latter theory is completely undecidable, and likewise every subtheory of the latter that contains $i$. Among these subtheories are plane euclidean incidence geometry and the theories of irreflexive relations, of asymmetrical relations and of transitive relations. The geometrical results remain valid if the relation of betweenness is added to the theory.

Reviewed by A. Heyting
Previous Item

MR0124196 (23 #A1513)
Asser, Günter; Rautenberg, Wolfgang
Ein Verfahren zur Axiomatisierung der Kontradiktionen gewisser zweiwertiger Aussagenkalküle. (German)
Z. Math. Logik Grundlagen Math. 6 1960 303--318.
02.10

---

The authors consider two-valued logical calculi $K$ with finite numbers of basic functors and proof relations $R$, and define for them a duality relation $\Delta$. They show that if $K$ has a duality relation, then it has a normal duality, where normality is defined by the authors to possess four simple properties. A calculus $K$ with a normal involutory duality is said to be strongly dualizable. It is shown that if $K$ is strongly dualizable, $X$ is a set of sentences, and $\germ R$ a set of proof relations, then $[X,\germ R]$ is an axiomatization of the identities of $K$ if and only if the dual pair $[\Delta X,\Delta\germ R]$ is an axiomatization of its contradictions. Conditions for obtaining axiomatizations of the contradictions of $K$ are then obtained in cases that $\Delta$ is a more general duality relation and the proof relations of $\germ R$ are restricted to be regular, where regularity is defined in terms of the form of statements in the given relation. Examples are supplied at the end of the paper.

Reviewed by E. J. Cogan
Previous Item