[FOM] 776: Logically Natural Examples 1
Joe Shipman
joeshipman at aol.com
Thu Dec 21 08:45:00 EST 2017
Your examples where ZFC can’t prove that a definition specifies an object with the desired properties go away if V=L. What’s the weakest alternative to V=L that allows a well-ordering of the reals, or a nonmeasurable set, to be uniquely defined? From a definable well-ordering of the reals, one can define a non-measurable set, but can you get a definable well-ordering of the reals from a plausible set-theoretic axiom weaker than V=L? CH doesn’t count, it just says there exists a bijection with aleph_1 but does not provide one like V=L does.
— JS
Sent from my iPhone
> On Dec 21, 2017, at 1:00 AM, Harvey Friedman <hmflogic at gmail.com> wrote:
>
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list