Subject: Re: [HM] ... and the unique factorization theorem
From: Carlos Cesar de Araujo (carlos.cesar@taskmail.com.br)
Date: Thu Feb 10 2000 - 05:04:32 EST
First and foremost, I would like to congratulate Walter Felsher once
more for his precise, concise and lucid presentation. On the other
hand, I know from my own experience that logical issues can give
anyone a big headache. So, to avoid any misunderstandings, I want to
add one clarification.
I did not say that
(a) the fundamental theorem "is not EXPRESSIBLE in 1st order
arithmetic".
I said that
(b) the fundamental theorem is not a first-order statement.
Indeed, the fundamental theorem is usually stated (at least by
algebraists) in the form
(c) (Ax) (E! f ) x = Product [ p^f(p), p\in P],
where $P$ is the set of natural primes and $f$ ranges over the
functions from $P$ to $N$ such that f(p)=0 from a certain $p$ on.
Ugh! Donald Knuth may well be right in saying that this is an
outstanding example of "bad style". From the logical point of view,
however, (c) is not a first-order sentence. (In a first-order
sentence, the quantifiers refer only to the atomic elements and never
to sets or functions between those elements.) But this does not mean
that (c) is not expressiBLE in a first-order framework. This is really
possible for many important mathematical results, usually by means of
coding tricks (as in Felsher's note) or some sort of skolemization or
.... By the way, it is well known among logicians that (c) can be
proved even in PRA --- the Primitive Recursive Arithmetic. As far as I
know, this specific result appeared for the first time in [Skolem,
Thm. 74].
Analogously, given, say, a ordered field $K$, the statement
"$K$ has no formally real proper algebraic extension field"
is not of 1st order, but, interestingly, it is provably equivalent to
an infinite denumerable set of first-order sentences. On the other
hand, while the statement
"$K$ is archimedean"
seems to be reducible to a set of first order sentences, it is not
(basically because for every $K$ we can construct a nonarchimedean $L$
having the same set of true first-order sentences). This result may
well lend to confusion, since the archimedean property is expressible
by the sentence
Ax Ey (y in N & x < y),
which appears to be of first-order. The difficulty here stems from the
impossibility of a first-order reduction for the predicate "y in N".
We can, of course, define $N$ in $K$ as the intersection of all
subsets of $K$ that are closed under suc(x) = x +1 --- but this
definition uses quantification over all subsets of $K$.
[Skolem] --- {\it The foundations of elementary arithmetic established
by means of the recursive mode of thought, without the use of apparent
variables ranging over infinite domains}, From Frege to Goedel, A source
book in mathematical logic, 1879--1931 (J. van Heijenoort, editor),
pp. 302--334.
Carlos C\'esar de Ara\'ujo
This archive was generated by hypermail 2b28 : Thu Feb 10 2000 - 11:13:53 EST