Tarsky A. Undecidable theories (1971)(400dpi)(T)(105s)_MAml

Home / lib / M_Mathematics / MA_Algebra / MAml_Mathematical logic /

Tarsky A. Undecidable theories (1971)(400dpi)(T)(105s)_MAml_.djvu

Size 6.1Mb
Date Feb 9, 2005

It suffices
for the proof of Theorem 3 and Corollary 4 outlined below; how-
however, condition (iii) will be essentially involved in the proof of
Theorem 1 and Corollary 2...
If the sentence Em(Am) is valid in T, then, by A) (with n = m) and
D), the sentence ~ WiAj^) is valid...
To show this, consider the system 9tt = < U, 0, S, ¦+-, • ) constructed
in the following way...
Theorem 6, Every recursive function is definable in Theory
R and hence also in every extension of R, The same applies to every
recursive set of natural numbers...
As was pointed out in 1.3, every theory which is not axiomatizablc
is automatically undecidable...
UNPECIDABILITY OF SUBTHEORfiES OF ARITHMETIC 63
(iv) a; + y = 0 if x - y — 0, x + y^l if x?y e t7 and x
or y = L
The decidability of Tx is simply a consequence of the fact that
the universe U of the model 9J? is finite...
A sentence
is valid in T6 if it is satisfied in the system <( N, 1, S\ ©, *, 0, S, +
where N, 1, 03 S9 + have their usual meaning while S', ®> and
are defined by the conditions
OTHER ARITHMETICAL THEORIES AND VARIOUS THEORIES OF RINGS 65
jST'O = 0, S'n - Sn if n ^ 0;
n © p = 0 if ?i = 0 or p=0\ n<&p = n I p— 1 if n^0 and j;^0;
n • p _ o for all n,p e A\
m m «
Let T+ be a theory with three constants: 0, S, +; a sentence of
T+ is valid in T+ if it is valid in T6, i.e., is satisfied in the system
(N, 0,5, +) where all the symbols have their usual meaning...
The elementary theories of rings, commutative
rings, integral domains, ordered rings, and ordered commutative
rings, without or with unit, are undecidable...
(From the above it follows that A4) is a possible definition
of S in T.)
In every ordered ring the formula x-z ^ y*z with z ^ 0 implies
x = y...
The non-logical constants of J4 are +> the individual con-
constant 1 used with the ordinary arithmetical meaning, and the binary
predicate | denoting the relation of divisibility between integers...
The essence of the proof just outlined clearly consists in showing that
in the arithmetic of integers multiplication is definable in terms of addition,
divisibility, and the number 1...
/' is defined to be the set of all iterations (powers) of c, i.e., the set
of all functions cm, with wcl, such that
E) cm(k) = k + m for every k e /...
On the other hand, various interesting extensions of G are known
to be undecidable, though not essentially undecidable...
Consider, for instance,
the axiomatic theory F in which © occurs as the only non-logical
constant while the set of non-logical axioms consists of Fv .T6, F1
and the following sentence:
F9...
Decision problem, 3f., 30, 32, 34f\, 39f., 86; see also: Restricted — —;
— procedure, 3, 14, 63
Deduction theorem, 6, 9f., 12
Definable (function, relation, set), definability, 31, 40fM 44ff., 49f., 55f.# 60f,
Defining, (formula), 44ff., 56
Definition, see: Possible —, Recursive —
Derivable [logically — ] (sentence), derivability 7ff.f llff., and passim
Detachment [modus ponens], see: Operation of —
Diagonal function [D], 40, 46
Direct method (in proofs of undecidability), 3, 5, 39f...