The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » Inactive » Historia-Matematica

Topic: [HM] Euclid and the unique factorization theorem
Replies: 6   Last Post: Feb 13, 2000 3:15 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Carlos Cesar Araujo

Posts: 9
Registered: 12/3/04
Re: [HM] ... and the unique factorization theorem
Posted: Feb 10, 2000 5:04 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.