Subject: [HM] ... and the unique factorization theorem
From: Walter Felscher (walter.felscher@uni-tuebingen.de)
Date: Wed Feb 09 2000 - 08:55:41 EST
In his note from February 5th , Mr. de Araujo has observed that the
uniqueness of prime factor decomposition is not expressible in 1st order
arithmetic because it makes use of the notion of an arbitrary sequence of
finitelength.
The extension of 1st order arithmetic by elementary (recursive)
functions (in the sense of Kalmar) permits to express and prove a
(unique) elementary prime factor decomposition, and that uniqueness
can be extended to any larger class of functions from which the
functions are to be taken which express the prime factors and
exponents of a decomposition.
* * *
The elementary (in the sense of Kalmar) functions are defined to form
the smallest class of functions which contains
the constant function with value 1
the projection functions p_i,k defined by p_i,k(x_0,...,x_k-1) = x_i
+ (addition)
. (multiplication)
-. limited subtraction: x-.y = x-y if x-y > 0 , and x-.y=0 else .
and is closed under all operators SUM and PRO of bounded summation
and production, transforming (k+1) ary functions f_k+1 into (k+1)-ary
functions SUM_f_k+1 , PRO_f_k+1 defined by
(SUM_f_k+1)(x_0,...,x_k-1, n) = sumof < f_k+1(x_0,...x_k-1,i) | i<=n >
(PRO_f_k+1)(x_0,...,x_k-1, n) = productof < f_k+1(x_0,...x_k-1,i) | i<=n > .
Observations:
1. The functions MOD and QU are elementary where
MOD(0,y)=y , 0 <= MOD(x,y) < x for x>0 .
y = QU(x,y).x + MOD(x,y) for all x,y , QU(0,y) = 0 .
2. The set of all prime numbers is elementary .
3, The function PRINO is elementary which gives as PRINO(n) the n-th
prime number p , PRINO(0)=2 .
4. The function EXP is elementary where EXP(x,0)=EXP(x,1)=0 and for y>1
EXP(x,y) is the largest exponent with which PRINO(x) divides y .
5. The function LEN is elementary where LEN(0)=LEN(1)=0 and for y<1
LEN(y) is x+1 for the largest x such that PRINO(x) divides y .
6. A number is a sequence number if it is of the form
productof < PRINO(i)^(1+x_i) | i<n > for numbers x_0,...,x_n-1 .
The set SEQ of all sequence numbers x is characterized by
x>1 and for all i<len(x) : prino(i) divides x ;
hence it is elementary.
The functions CAR and CDR are elementary where
if x>1 then CAR(x) = PRINO(LEN(x)-.1)^EXP(LEN(x)-.1),x)
if x<=1 then CAR(x) = 0
if x>1 then CDR(x) = QU(CAR(x),x)
if x<=1 then CDR(x) = 0 .
Lemmas:
1. If x>1 then CAR(x)>0 and x = CDR(x).CAR(x)
2. If LEN(x)=1 then CDR(x)=1 ,
if LEN(x)>0 then CDR(x)<x and LEN(CDR(x)) <= LEN(x)-1
3. If x>1 then for all i<LEN(x)-1 : EXP(i,CDR(x)) = EXP(i,x)
4. If x in SEQ and LEN(x)>1 then CDR(x) in SEQ and LEN(x)=1+LEN(CDR(x))
5. If x>0 , y>0 , LEN(x)=LEN(y) , CAR(x)=CAR(y) , CDR(x)=CDR(y) then x=y
6. If EXP(j,x)>0 then j < LEN(CDR(x)) or j = LEN(x)-1
Theorem 1
If x>0 then x = productof < PRINO(i)^EXP(i,x) | i<LEN(x) >
If x>1 then CDR(x) = productof < PRINO(i)^EXP(i,x) | i<LEN(x)-1 > .
The functions standing here on the right hand side are elementary, and
so the above representation of x may be called the elementary prime
factor decomposition; every prime factor of x occurs there with the
maximal exponent with which it divides x .
Uniqueness of prime factor decomposition refers, of course, to
arbitrary representations, and in order to express them one will want
to leave the class of elementary functions. So let n be a positive
number, let f, g be arbitrary functions with f(i)<f(i+1) for i<n-1 ,
and g(i)>0 for i<n . The confluent product of the sequence
<PRINO(f(i)) | i<n > and the sequence <g(i) | i<n > is the number
x = productof < PRINO(f(i))^g(i) | i<n > .
There still holds
Theorem 2
The primes PRINO(j) dividing x = productof < PRINO(f(i))^g(i) | i<n >
are precisely the PRINO(f(i)) with i<n , and then EXP(f(i),x) = g(i) .
W.F.
This archive was generated by hypermail 2b28 : Wed Feb 09 2000 - 09:40:46 EST