[FOM] 769: Complexity of Integers 1
Harvey Friedman
hmflogic at gmail.com
Thu Sep 7 00:30:20 EDT 2017
I want to pursue this systematically and foundationally. Obviously I
am going to get involved in many matters which are well known, sort of
known, or poorly known. I hope readers will comment on the literature
as I discuss this.
A very interesting way of assigning complexities to n in N (N is the
set of all nonnegative integers) is naturally associated with any
given structure M in the sense of elementary model theory. We assume M
is based on any set of constant, relation, and function symbols, and
always includes the special relation symbol = with its usual
interpretation.
The complexity measure #M associated with M is denied as follows. Let
n in N be given. #M(n) is the least length of a formula phi in the
language of M with at most the free variable v, such that {d in
dom(M): M satisfies phi[d]} has cardinality n.
Note that this definition makes good sense for any M, and avoids
having to talk about how integers are recognized in M.
However, note that for impoverished structures, some nonnegative
integers may not have a complexity. Of course, if there are infinitely
many elements which are 0-definable, then every nonnegative integer
has a complexity. We will only be working with structures where
infinitely many elements are 0-definable.
Because = is automatically in the language of M, clearly #M is defined
at every n in N. So #M:N into N.
We need to discuss how we count the length of formulas. Because unary
function symbols can stack, we have to allow unary function symbols as
part of the count, and it is artificial not to allow general function
symbols in the count. Then for naturally, we really should allow
constant, relation, and function symbols as part of the count, and
obviously variables. Since quantifiers are attacked to variables, we
do not need to count them. Also there is no need to count
propositional connectives because there only negations can stack, but
they stack with no effect.
So we have decided to count the length of phi here as follows. It is
the total number of occurrences of variables, constant symbols,
function symbols, and relation symbols.
We now give a list of structures M and look at the corresponding #M.
Equality is always understood as part of M.
By the decision procedures for the theories of 1,2,3, of (N,<), we
know that #M is a low level recursive function. The computer can
certainly help with computing exact values here, if we need it.
1. (N,<).
2. (N,0,S).
3. (N,+,<),
4. (R,+,x), (R,+,x,<).
5. (N,+,x), (N,+.x.<).
6. (V(omega),epsilon).
7. (V(alpha),epsilon), for various alpha.
8. (V,epsilon).
9. (POW(V),epsilon). I.e., classes under membership.
The first issue that arises is to at least get a table of actual
computations of #M at some numbers. Obviously we should first try tiny
numbers, and consider what we can do with bigger numbers. This is all
that we will address in this projected series for a while.
1. (N,<)
What about 0? not(v = v) has three symbols. There is no formula with
fewer symbols. So #M(0) = 3.
What about 1? If there are no quantifiers then it must be a
propositional combination of v = v. This won't do. So there must be at
least one quantifier. (forall x)(not(x < v)) defines a set of
cardinality 1. Thus #M(1) <= 4. We have to rule out #M(1) = 3. Since
there must be a quantifier, we have a sub formula of the form
(therexists w)(phi) or (forall w)(phi). As we are looking at length 3,
we already see 4. Hence #M(1) = 4.
THEOREM 1.1. #M(0) = 2, #M(1) = 4. For n >= 2, #M(n) <= 4n.
Proof: v < n if and only if (forall x1,...,xn)(not(x1 < ... < xn < v),
which has complexity 4n QED
QUESTION: Is this an equality?
2. (N,0,S)
THEOREM 2.1.#M(0) = #M(1) = 3. For n >= 2, #M(n) =
THEOREM 2.1.#M(0) = #M(1) = 3. For n >=2, #M(n) <= 5n.
Proof: #M(0) = #M(1) = 3 using v not= v, v = 0. Let n >= 2. 0 <= v <=
n-1 if and only if (therexists x1,...,xn-1)(x1 = S0 and ... and xn-1 =
Sxn-2 and (v = 0 or v = x1 or ... or v = xn-1)), which has complexity
n-1 + 4(n-1) + 3n = 8n-5. QED
QUESTION: Is this an equality?
************************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 769th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
711: Large Cardinals and Continuations/21 9/18/16 10:42AM
712: PA Incompleteness/1 9/23/16 1:20AM
713: Foundations of Geometry/1 9/24/16 2:09PM
714: Foundations of Geometry/2 9/25/16 10:26PM
715: Foundations of Geometry/3 9/27/16 1:08AM
716: Foundations of Geometry/4 9/27/16 10:25PM
717: Foundations of Geometry/5 9/30/16 12:16AM
718: Foundations of Geometry/6 101/16 12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7 10/2/16 1:59PM
721: Large Cardinals and Emulations//23 10/4/16 2:35AM
722: Large Cardinals and Emulations/24 10/616 1:59AM
723: Philosophical Geometry/8 10/816 1:47AM
724: Philosophical Geometry/9 10/10/16 9:36AM
725: Philosophical Geometry/10 10/14/16 10:16PM
726: Philosophical Geometry/11 Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25 10/20/16 1:37PM
728: Philosophical Geometry/12 10/24/16 3:35PM
729: Consistency of Mathematics/1 10/25/16 1:25PM
730: Consistency of Mathematics/2 11/17/16 9:50PM
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
740: Philosophy of Incompleteness/2 1/7/16 8:33AM
741: Philosophy of Incompleteness/3 1/7/16 1:18PM
742: Philosophy of Incompleteness/4 1/8/16 3:45AM
743: Philosophy of Incompleteness/5 1/9/16 2:32PM
744: Philosophy of Incompleteness/6 1/10/16 1/10/16 12:15AM
745: Philosophy of Incompleteness/7 1/11/16 12:40AM
746: Philosophy of Incompleteness/8 1/12/17 3:54PM
747: PA Incompleteness/2 2/3/17 12:07PM
748: Large Cardinals and Emulations/30 2/15/17 2:19AM
749: Large Cardinals and Emulations/31 2/15/17 2:19AM
750: Large Cardinals and Emulations/32 2/15/17 2:20AM
751: Large Cardinals and Emulations/33 2/17/17 12:52AM
752: Emulation Theory for Pure Math/1 3/14/17 12:57AM
753: Emulation Theory for Math Logic 3/10/17 2:17AM
754: Large Cardinals and Emulations/34 3/12/17 12:34AM
755: Large Cardinals and Emulations/35 3/12/17 12:33AM
756: Large Cardinals and Emulations/36 3/24/17 8:03AM
757: Large Cardinals and Emulations/37 3/27/17 2:39AM
758: Large Cardinals and Emulations/38 4/10/17 1:11AM
759: Large Cardinals and Emulations/39 4/10/17 1:11AM
760: Large Cardinals and Emulations/40 4/13/17 11:53PM
761: Large Cardinals and Emulations/41 4/15/17 4:54PM
762: Baby Emulation Theory/Expositional 4/17/17 1:23AM
763: Large Cardinals and Emulations/42 5/817 2:18AM
764: Large Cardinals and Emulations/43 5/11/17 12:26AM
765: Large Cardinals and Emulations/44 5/14/17 6:03PM
766: Large Cardinals and Emulations/45 7/2/17 1:22PM
767: Impossible Counting 1 9/2/17 8:28AM
768: Theory Completions 9/6/17 9/4/17 9:13PM
Harvey Friedman
More information about the FOM
mailing list