[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