[FOM] 776: Logically Natural Examples 1
Harvey Friedman
hmflogic at gmail.com
Thu Dec 21 01:00:40 EST 2017
There are many many centrally important situations in mathematical
logic where it is easy to prove the existence of a certain kind of
often fundamental object, yet we don't have a clue as to how to give a
natural example.
In most of the cases I am thinking about, we also have no way to state
a necessary condition for naturalness, and prove that that condition
cannot be met.
Of course, there are a number of classic situations like this where we
*can* state a compellingly necessary condition for naturalness, and
prove that that condition cannot be met.
SOME WELL KNOWN EXAMPLES FROM LOGIC AND CORE MATH
In core mathematics, there are myriad situations in almost every
context where we construct natural examples from the outset. Sometimes
it is far easier to prove the existence of an example, but much more
difficult to give a natural example. However, usually, after the
existence of an example, one is able to provide natural examples, and
sometimes this is incomparable more difficult. In the preponderance of
cases, in core mathematics, there are natural examples to be found.
In logic, however, it appears that in very many fundamental
situations, we don't know how to give natural examples. Here we mean
natural from the point of view of mathematical logic, and not the
generally higher standard of natural from the point of view of core
mathematics.
Generally speaking, it is only in rather set theoretic cases that we
know how to give a compelling necessary condition for (logical)
naturalness, and prove that it is impossible. In so many cases, we are
clueless as to what is going on.
An extremely famous example in mathematics surrounds rational numbers.
This and related examples are extremely revealing, but I warn you that
what I am about to say does not at all match the historical record.
There is an easy diagonal argument that there are real numbers that
are not rational. Is there a natural example of a real number that is
not rational? The answer is yes: the square root of 2. This is
extremely mathematically natural.
Historically, the natural example greatly preceded the easy diagonal
argument(!).
The same with the easy diagonal argument that there are real numbers
that are not algebraic. Is there a natural example of a real number
that is not algebraic? Yes. E.g., the extremely mathematically natural
e and pi.
Turning to set theory, we know, and it is very important to know, in
full blown set theory, that there is a well ordering of the set R of
all real numbers. Is there a natural example of a well ordering of R?
It is completely compelling that provable ZFC definability is
necessary for logical naturalness.
THEOREM (Cohen)? Assume ZFC is consistent. There is no formula phi(x)
in the language of set theory, with only the free variable x, such
that ZFC proves that the unique solution to phi(x) is a well ordering
of R.
And the above Theorem can be greatly strengthened to replace ZFC by
any of the usual extensions of ZFC by large cardinals.
Another famous one.
THEOREM (Solovay) Assume ZFC is consistent. There is no formula phi(x)
in the language of set theory, with only the free variable x, such
that ZFC proves that the unique solution to phi(x) is a non Lebesgue
measurable subset of R.
which also can be greatly strengthened by using any of the usual
extensions of ZFC by large cardinals.
*LIST OF OPEN NATURALNESS ISSUES IN THE COUNTABLE*
1. There are two subsets of N neither of which is recursive in the other.
2. There is a polynomial with integer coefficients, of several
variables, whose range over integer arguments is not recursive.
3. There is a countable set of subsets of N which forms a model of WKL
but not a model of ACA.
4. There is a countable set of subsets of N which forms a model of ATR
but not a model of Pi11-CA0.
5. There is a countable set of subsets of N which forms a model of
Pi11-CA0 and which is not a beta model.
6. There is a complete theory extending Peano Arithmetic other than
the set of true sentences of Peano Arithmetic. Even replace Peano
Arithmetic by Bounded Arithmetic (Sigma_0).
7. There is a countable nonstandard model of Peano Arithmetic, or even
Bounded Arithmetic, even just up to isomorphism.
8. Focused form of 7. There is a countable nonstandard model of the
true sentences of arithmetic, with Scott set the arithmetic sets,
9. There is a non principal ultrafilter on the set of all recursive
subsets of N. Replace recursive by primitive recursive, elementary
recursive, polynomial time computable, and so forth. On the arithmetic
subsets of N, on the hyperarithmetic subsets of N, on the
constructible subsets of N, etcetera. There is a non principal
ultrafilter on some set of subsets of N forming a model of RCA.
*SOME REMARKS ON 1-9*
In thinking about these, some interesting things arise.
I emphasize again that when proposing 1-9 here, I am not asking for
mathematical naturalness, but rather math logic naturalness. The
former is generally more difficult.
With regard to mathematical naturalness, I have long been episodically
involved in providing mathematically natural equivalents of math logic
natural notions. This is a different project, also something I will be
writing about separately. In that project, we start with obviously
natural notions from the logical standpoint. Then we treat them
strictly mathematically.
1. Note that {(x,y): x,y are not recursive in each other} has measure
1 in K x K, where K is the Cantor space of subsets of N. This is by
Fubini's Theorem after you see that this set is Borel.
There is already an issue about giving a logically natural non
recursive subset of N. What about halting sets? Well, that depends on
Goedel numberings, the usual way it is done. It is difficult to argue
for a particular Goedel numbering, but not entirely impossible. You
can also take the set of integral polynomials with no solution. But
that doesn't give a subset of N unless you code the integral
polynomials as integers: any such coding can be easily objected to. I
addressed this problem in two papers, where I proposed something even
more ambitious: a strictly mathematical definition of a non recursive
subset of N. See
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#44 appeared in TAMS
As far as logically natural is concerned, we include computer science
natural, and so we can freely use the commonly accepted preferred
formulation of Turing Machines used for, e.g., the Busy Beaver
problem.
These are two way infinite TMs with two tape symbols 0,1,
deterministic, The tape starts off with all 0's in both directions,
and the reading head at the square numbered 0. Transitions first write
and then move left or right one square according to the state and the
tape symbol being read.
LOGICALLY NATURAL NON RECURSIVE f:N into N. f(n) is the number of TMs
with n states that halt.
LOGICALLY NATURAL NON RECURSIVE SUBSET OF N. The range of f.
There is a QUIBBLE here and it seems like the paper #44 cited above is
immune to. Namely, this model of computation, no matter how commonly
accepted now in CS, is (a wee bit) ad hoc.
THEOREM of the future. The above model of computation is the simplest
one in a certain very natural category of complete models of
computation.
But what if we only get a convicting natural finite set of natural
complete models of computation? Then we would get a finite set of
functions f(n) as above, and then take the union of their ranges for
the logically natural non recursive set of integers. I.e., the set of
all "halt counting numbers" of a natural complete model of
computation.
2 - 9. TO BE CONTINUED.
************************************************************************
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 776th 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/4/17 9:13PM
769: Complexity of Integers 1 9/7/17 12:30AM
770: Algorithmic Unsolvability 1 10/13/17 1:55PM
771: Algorithmic Unsolvability 2 10/18/17 10/15/17 10:14PM
772: Algorithmic Unsolvability 3 Oct 19 02:41:32 EDT 2017
773: Goedel's Second: Proofs/1 Dec 18 20:31:25 EST 2017
774: Goedel's Second: Proofs/2 Dec 18 20:36:04 EST 2017
775: Goedel's Second: Proofs/3 Dec 19 00:48:45 EST 2017
Harvey Friedman
More information about the FOM
mailing list