Selected Matches for: Author=rautenberg,wolfgang
Return to headlines
Next Item
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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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.\}
Next Item
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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
{There will be no review of this item.}
Previous Item
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
{This item will not be reviewed individually. For details of the collection in which this item appears see
MR1096790 (91k:68010) .}
Previous Item
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
{There will be no review of this item.}
Previous Item
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
{There will be no review of this item.}
Previous Item
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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
Next 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
Next 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
Next Item
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next Item
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
Next 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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next Item
MR0300879 (46 #39)
Hauschild, Kurt;
Rautenberg, Wolfgang
Interpretierbarkeit in der Gruppentheorie.
(German)
Algebra Universalis 1 (1971/72), 136--151.
02G05
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next Item
MR0278159 (43 #3890)
Rautenberg, Wolfgang
Axiomatische Theorie der Translationsgruppen affiner Räume und Translationsebenen.
(German)
Math. Nachr. 46 1970 171--182.
50.05
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next Item
MR0203552 (34 #3402)
Rautenberg, Wolfgang
Über Hilberts Schnittpunktsätze.
(German)
Z. Math. Logik Grundlagen Math. 12 1966 57--59.
50.05 (50.10)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next 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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next Item
MR0157273 (28 #509)
Rautenberg, Wolfgang
Konstruktionen in der hyperbolischen Geometrie.
(German)
Math. Nachr. 25 1963 151--158.
50.40
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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)
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Next 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
Next Item
MR0137648 (25 #1099)
Rautenberg, Wolfgang
Unentscheidbarkeit der euklidischen Inzidenzgeometrie.
(German)
Z. Math. Logik Grundlagen Math. 7 1961 12--15.
02.74
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
References: 0 | Reference Citations: 0 | Review Citations: 0 |
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
Return to headlines