May 2018 - mathfun@mailman.xmission.com

[math-fun] 60-Year-Old Maths Problem Partly Solved By Amateu
by Ray Tayek 04 May '18

04 May '18

https://science.slashdot.org/story/18/05/04/1521239/60-year-old-maths-probl… Posted by msmash on Friday May 04, 2018 @11:22AM from the unravelling-mysteries dept. An amateur mathematician has made the first breakthrough in more than 60 years towards solving a well-known maths problem. From a report:/Aubrey de Grey, who is more widely known as a maverick biologist intent on extending the human lifespan, has taken the academic world by surprise after announcing a new solution to the so-called Hadwiger-Nelson problem <https://www.theguardian.com/science/2018/may/04/60-year-old-maths-problem-p…>. The problem <http://mathworld.wolfram.com/Hadwiger-NelsonProblem.html> sounds deceptively simple, but despite some professionals spending years trying to crack it, progress has stalled since shortly after the puzzle was first posed in 1950. "Literally, this is the first progress in more than 60 years," said Gil Kalai, a mathematician at Hebrew University of Jerusalem. The problem is as follows. Imagine a collection of dots connected by lines. The dots can be arranged any way at all, the only rule is that all the connecting lines must be of equal length. For instance, in a square the diagonal would not be joined up, but the outer edges would be. Now, colour in all the dots so that no two connected points have the same colour. How many colours are required. For a square, the answer would be two. But the Hadwiger-Nelson problem asks what the minimum would be for any configuration -- even one that extends across a plane of infinite size./ -- Honesty is a very expensive gift. So, don't expect it from cheap people - Warren Buffett http://tayek.com/

2 1

[math-fun] paleocybernetic obscurity
by Bill Gosper 04 May '18

04 May '18

(Old timers only.) Identify: qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6qz6... --rwg

2 2

Re: [math-fun] Set of all sets question
by Dan Asimov 04 May '18

04 May '18

The philosophical problem concerning me here is nothing new. Andy has focused things by pointing to the *union* of the A(beta). It just feels intuitively that given a bunch of nested sets (that *exist*), then their union "ought to" exist as well. And the fact that in some systems the set of all sets can exist (as a class) lends credence to that intuition. —Dan ----- On Thursday, May 3, 2018, Andy Latto <andy.latto(a)pobox.com> wrote: > On Thu, May 3, 2018 at 4:19 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: > > QUESTION: > > --------- > > How can it be that each A(beta) exists, and for that matter any subset > of them exists, > > but all of them cannot exist at once (without contradiction)? > > I don't understand what you think is a contradiction. All of them can > and do exist at once. Their union does not exist (if using ZF) or is a > class but not a set (if using Goedel-Bernay), but this is not a > contradiction, because the union axiom only says that given a *set* of > sets, the union set also exists. It does not guarantee the existence > of the union of any class of sets exists. ... -----

2 1

[math-fun] Set of all sets question
by Dan Asimov 03 May '18

03 May '18

We know that the Class of all sets Sets cannot be a set, because this would imply the existence of the set X = {s in Sets | s is not a member of s}, but X belongs to X if and only if it doesn't, hence Contradiction. But we are told that it makes perfect sense to speak of all sets no larger than some fixed cardinal number = beta. Let the set of all sets that are no larger than the cardinal beta be denoted by A(beta): A(beta) = {s in Sets | card(s) <= beta}. QUESTION: --------- How can it be that each A(beta) exists, and for that matter any subset of them exists, but all of them cannot exist at once (without contradiction)? —Dan

4 3

Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
by hbaker1 02 May '18

02 May '18

But that's the heart of the incompleteness theorem: *any* theory strong enough to describe number theory or Turing Machines has certain true statements that have no (finite) proofs. Recall that proofs are finite sequences generated by non-deterministic machines from axioms and rules of inference in an attempt to list all theorems. By a strong analogy to diagonalization of an attempt to list all of the numeral sequences of the real numbers, we can construct a new real number not on the list; and hence we can construct a new truth not on the list of provable theorems. -----Original Message----- >From: Cris Moore <moore(a)santafe.edu> >Sent: Apr 30, 2018 10:42 PM >To: hbaker1 <hbaker1(a)pipeline.com>, math-fun <math-fun(a)mailman.xmission.com> >Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? > >Right, the Halting Problem is asymmetric: there’s a finite proof of halting if it halts, but not necessarily a finite proof that it runs forever if it runs forever. > >Cris > >> On Apr 30, 2018, at 11:02 PM, hbaker1 <hbaker1(a)pipeline.com> wrote: >> >> Turing Machines which halt: "recursively enumerable" == "RE" >> Turing Machines which don't halt: complement of RE. >> >> Turing proved that they aren't the same sets. >> >> Thus, RE sets are kind of "fractals", in that their boundaries are a little difficult to determine -- at least from one direction. >> >> -----Original Message----- >>> From: Cris Moore <moore(a)santafe.edu> >>> Sent: Apr 30, 2018 2:28 PM >>> To: math-fun <math-fun(a)mailman.xmission.com> >>> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? >>> >>>> On Apr 30, 2018, at 3:21 PM, Cris Moore <moore(a)santafe.edu> wrote: >>>> >>>> However, we should be careful, since even questions about the halting of Turing machines — which are certainly first-order claims about the integers — can be independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf> <https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf>> >>> >>> Sorry, continuing: note that if a Turing machine halts in finite time, there is a finite proof of that fact — namely, run it and see what happens. But if it runs forever, proving that it does so might be difficult. >>> >>> But surely there is a truth of the matter here! The Turing machine will either run forever, or it won’t. I find it hard to be a pluralist here. >>> >>> - Cris

6 6

[math-fun] Radix-r numbers; |r|=1, r=log(ik)
by hbaker1 02 May '18

02 May '18

Approximately represent complex numbers in radix r, where r=log(ik), for some integer k>0, i=sqrt(-1). Several choices of numerals: {0,1}, {0,i}, {0,1,i}, {0,+-1,+-i}. So |r|=1, and we have good approximations to *random walks*. This is not a particularly efficient number system, so is there an efficient algorithm to compute an approximation?

1 0

Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
by hbaker1 02 May '18

02 May '18

I would imagine that it would be impossible for a CH-denier to get tenure in any major American university math department today. I suspect that YouTube and Twitter will suppress any postings by CH-deniers, as well. CH-deniers disrupt the entire Hilbert Program.

1 0

Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
by Henry Baker 01 May '18

01 May '18

It's pretty clear: if there are consistent models with CH and consistent models w/o CH, then that makes CH *independent* -- to choose whichever way you please. Just like the Euclid's parallel postulate: if you like it, you get Euclid's plane geometry, whereas if you don't like it, you get one of the non-flat geometries -- e.g., Einstein. That's mathematics/mathematical logic. Now consider physics. I find CH completely antithetical to quantum theory -- e.g., "ultraviolet catastrophe" and all that. So while CH is really nice for a lot of math, I don't think that it describes post-19th C. physics very well. Curiously, much of the math of QM seems to make liberal use of CH, so something's wrong with the math at the basis of QM. I believe that this was the essence of Fredkin's, Bennett's, Feynman's (?) etc., arguments. BTW, I seriously doubt that TPC is independent, but I don't have any proofs. At 04:29 PM 4/29/2018, Dan Asimov wrote: >The twin prime conjecture (TPC) says there are infinitely many pairs of prime numbers separated only by 2, like 3 and 5, 5 an 7, 11 and 13, etc. > >No one knows if it's true or false. > >But whichever is the case, it might not be possible to *prove* this fact. > >A similar situation is the Continuum Hypothesis (CH), which states that there is no infinity strictly larger than the size of the integers and strictly smaller than the size of the real numbers. > >Kurt Goedel proved about 1940 that CH was consistent with the axioms of set theory (ZF, for Zermelo-Frankel), and Paul Cohen proved in 1963 that the negation of CH was *also* consistent with ZF. > >So in this case there is *no doubt*: There exists neither a proof of CH, nor a proof of its negation ~CH, purely based on the axioms ZF+AC of set theory. > >Question: >--------- > >So, does that mean that CH is neither really true nor really false, but some third option? > >Or what? > >I'm curious what people think about this. > >ÂDan

5 5

Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
by hbaker1 01 May '18

01 May '18

Doesn't it get worse? Aren't there *particular* TM's whose haltingness can be arbitrarily chosen? I.e., "TM XYZ halts" becomes an axiom *independent* of the rest of arithmetic? -----Original Message----- >From: Cris Moore <moore(a)santafe.edu> >Sent: May 1, 2018 6:19 AM >To: hbaker1 <hbaker1(a)pipeline.com>, math-fun <math-fun(a)mailman.xmission.com> >Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? > >I agree with all this: indeed my favorite way to prove the first Incompleteness Theorem is the undecidability of the Halting Problem. For any set of axioms, there is a Turing machine which 1) never halts and 2) that set of axioms cannot prove that it never halts. Otherwise the Halting Problem would be decidable. > >But don’t you agree that the Halting Problem has a definite truth value? In other words, that a given Turing machine (with a given input) either runs forever or doesn’t, regardless of our ability to prove it? Or does the unprovability of non-halting make you a pluralist on this topic — that if we can’t prove non-halting in ZFC (say), then we can have it either way? > >- Cris > >> On May 1, 2018, at 7:02 AM, hbaker1 <hbaker1(a)pipeline.com> wrote: >> But that's the heart of the incompleteness theorem: *any* theory strong enough to describe number theory or Turing Machines has certain true statements that have no (finite) proofs. >> >> Recall that proofs are finite sequences generated by non-deterministic machines from axioms and rules of inference in an attempt to list all theorems. >> >> By a strong analogy to diagonalization of an attempt to list all of the numeral sequences of the real numbers, we can construct a new real number not on the list; and hence we can construct a new truth not on the list of provable theorems. >> >> -----Original Message----- >>> From: Cris Moore <moore(a)santafe.edu> >>> Sent: Apr 30, 2018 10:42 PM >>> To: hbaker1 <hbaker1(a)pipeline.com>, math-fun <math-fun(a)mailman.xmission.com> >>> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? >>> >>> Right, the Halting Problem is asymmetric: there’s a finite proof of halting if it halts, but not necessarily a finite proof that it runs forever if it runs forever. >>> >>> Cris >>> >>>> On Apr 30, 2018, at 11:02 PM, hbaker1 <hbaker1(a)pipeline.com> wrote: >>>> >>>> Turing Machines which halt: "recursively enumerable" == "RE" >>>> Turing Machines which don't halt: complement of RE. >>>> >>>> Turing proved that they aren't the same sets. >>>> >>>> Thus, RE sets are kind of "fractals", in that their boundaries are a little difficult to determine -- at least from one direction. >>>> >>>> -----Original Message----- >>>>> From: Cris Moore <moore(a)santafe.edu> >>>>> Sent: Apr 30, 2018 2:28 PM >>>>> To: math-fun <math-fun(a)mailman.xmission.com> >>>>> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? >>>>> >>>>>> On Apr 30, 2018, at 3:21 PM, Cris Moore <moore(a)santafe.edu> wrote: >>>>>> >>>>>> However, we should be careful, since even questions about the halting of Turing machines — which are certainly first-order claims about the integers — can be independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf> <https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf>> >>>>> >>>>> Sorry, continuing: note that if a Turing machine halts in finite time, there is a finite proof of that fact — namely, run it and see what happens. But if it runs forever, proving that it does so might be difficult. >>>>> >>>>> But surely there is a truth of the matter here! The Turing machine will either run forever, or it won’t. I find it hard to be a pluralist here. >>>>> >>>>> - Cris

2 1

Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
by hbaker1 01 May '18

01 May '18

Turing Machines which halt: "recursively enumerable" == "RE" Turing Machines which don't halt: complement of RE. Turing proved that they aren't the same sets. Thus, RE sets are kind of "fractals", in that their boundaries are a little difficult to determine -- at least from one direction. -----Original Message----- >From: Cris Moore <moore(a)santafe.edu> >Sent: Apr 30, 2018 2:28 PM >To: math-fun <math-fun(a)mailman.xmission.com> >Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ? > >> On Apr 30, 2018, at 3:21 PM, Cris Moore <moore(a)santafe.edu> wrote: >> >> However, we should be careful, since even questions about the halting of Turing machines — which are certainly first-order claims about the integers — can be independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf> <https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf>> > >Sorry, continuing: note that if a Turing machine halts in finite time, there is a finite proof of that fact — namely, run it and see what happens. But if it runs forever, proving that it does so might be difficult. > >But surely there is a truth of the matter here! The Turing machine will either run forever, or it won’t. I find it hard to be a pluralist here. > >- Cris

2 1