
Re: [HM] ... and the unique factorization theorem
Posted:
Feb 10, 2000 5:04 AM


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 firstorder 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 firstorder sentence. (In a firstorder 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 firstorder 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 firstorder 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 firstorder 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 firstorder. The difficulty here stems from the impossibility of a firstorder 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, 18791931 (J. van Heijenoort, editor), pp. 302334.
Carlos C\'esar de Ara\'ujo

