FOM: 50:Enormous Integers/Number Theory
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jul 17 18:39:50 EDT 1999
This is the 49th in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:
1:Foundational Completeness 11/3/97, 10:13AM, 10:26AM.
2:Axioms 11/6/97.
3:Simplicity 11/14/97 10:10AM.
4:Simplicity 11/14/97 4:25PM
5:Constructions 11/15/97 5:24PM
6:Undefinability/Nonstandard Models 11/16/97 12:04AM
7.Undefinability/Nonstandard Models 11/17/97 12:31AM
8.Schemes 11/17/97 12:30AM
9:Nonstandard Arithmetic 11/18/97 11:53AM
10:Pathology 12/8/97 12:37AM
11:F.O.M. & Math Logic 12/14/97 5:47AM
12:Finite trees/large cardinals 3/11/98 11:36AM
13:Min recursion/Provably recursive functions 3/20/98 4:45AM
14:New characterizations of the provable ordinals 4/8/98 2:09AM
14':Errata 4/8/98 9:48AM
15:Structural Independence results and provable ordinals 4/16/98
10:53PM
16:Logical Equations, etc. 4/17/98 1:25PM
16':Errata 4/28/98 10:28AM
17:Very Strong Borel statements 4/26/98 8:06PM
18:Binary Functions and Large Cardinals 4/30/98 12:03PM
19:Long Sequences 7/31/98 9:42AM
20:Proof Theoretic Degrees 8/2/98 9:37PM
21:Long Sequences/Update 10/13/98 3:18AM
22:Finite Trees/Impredicativity 10/20/98 10:13AM
23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM
24:Predicatively Unfeasible Integers 11/10/98 10:44PM
25:Long Walks 11/16/98 7:05AM
26:Optimized functions/Large Cardinals 1/13/99 12:53PM
27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM
28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM
28':Restatement 1/28/99 5:49AM
29:Large Cardinals/where are we? I 2/22/99 6:11AM
30:Large Cardinals/where are we? II 2/23/99 6:15AM
31:First Free Sets/Large Cardinals 2/27/99 1:43AM
32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM
33:A Variant 3/4/99 1:52PM
34:Walks in N^k 3/7/99 1:43PM
35:Special AE Sentences 3/18/99 4:56AM
35':Restatement 3/21/99 2:20PM
36:Adjacent Ramsey Theory 3/23/99 1:00AM
37:Adjacent Ramsey Theory/more 5:45AM 3/25/99
38:Existential Properties of Numerical Functions 3/26/99 2:21PM
39:Large Cardinals/synthesis 4/7/99 11:43AM
40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
This concerns the generation of big numbers in elementary number theory.
We consider the following property *(k,A) of integers k >= 1 and sets A of
positive integers:
1. No element of A divides any different element of A.
2. For all x in A greater than k, x divides the product of all y in A less
than x.
THEOREM 1. For all k >= 1, there are finitely many A such that *(k,A), all
of which are finite. However, this cannot be proved in RCA_0. It is
equivalent to "the Ackerman function exists" over RCA_0.
So we have defined a specific finite mathematical structure associated with
any given k >= 1: the family of all sets obeying property *(k).
Let's look at some small k. We write #(k) for the largest cardinality of
any A such that *(k,A). Note that by 2, a bound on the largest numbers
appearing in any of the A's and the number of A's can be given in terms of
#(k).
#(1) = 1.
#(2) = 1.
#(3) = 2.
#(4) = 2.
#(5) = 3.
#(6) = 3.
#(7) = 4.
#(8) = 4.
#(9) = 5.
#(10) = 7.
#(11) = 8.
#(12) = 8.
#(13) = 9.
#(14) >= 530.
#(22) >= t, where t is an exponential stack of s 2's, where s is an
exponential stack of 2^1032 2's.
NOTE: These calculations up through #(13)
THOEREM 2. Let k >= 14. #(k) is at least the unary Ackerman function at t,
where t is the number of primes <= k/2. #(k) is at most the unary Ackerman
function at k.
More information about the FOM
mailing list