News for hackers. Stuff that matters.
Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Thursday February 23, 2017 @09:54AM (#13714270)
> a lot of ordinary mathematics that is outside of ZFC

A lot of ordinary math? I think there's one if not two exaggerations in there.

> My opinion is still that ZFC itself is unnatural as a foundation for mathematics, precisely because we have to do so much encoding to get anything useful out of it.

One of the things Friedman likes to emphasize about the foundation of math is that there is very little you actually need to do with it. A good foundation is one that you don't even need to know is there. Most mathematicians don't work in any formalism, so a foundation doesn't need to be useful. It's not as if anyone actually needs to do all those tedious set encodings.

Except that many of those who call for new foundations are really interested in mechanical proof checkers, and those do have to be useful. In order to make these arguments less religious, I think it would be worthwhile to adopt Turing's mathematical philosophy, which called for adopting mathematical foundations on an ad-hoc basis (or even no foundation at all). In other words, choose whatever foundation (if any) for the task at hand. This would make it easier to argue that, say, type theory is a more convenient core for proof checkers.

> This is not a direction that Friedman considers worthwhile, because he thinks that first-order logic and ZFC are inevitable.

That's not how I read him. He thinks that FOL and ZFC are good enough, and as foundations don't matter in practice (a good foundation is one you can ignore; I think that's a quote by him), it would take some achievement to justify seriously considering alternatives. He even says what it would take: easier teaching and/or easier proofs. So far no alternative foundation has been able to improve either one.

Re:Harvey Friedman bringing incompleteness and infinity out ... by eastWestMath on Thursday February 23, 2017 @11:24AM (#13715122)
>In order to make these arguments less religious, I think it would be worthwhile to adopt Turing's mathematical philosophy, which called for adopting mathematical foundations on an ad-hoc basis (or even no foundation at all). In other words, choose whatever foundation (if any) for the task at hand. This would make it easier to argue that, say, type theory is a more convenient core for proof checkers.

I think you're misrepresenting the category theorists, they're usually the ones arguing for choosing whatever foundation is convenient for a given domain. A lot of the time, this is a type theoretic foundation because a lot of modern mathematics is about pretending you have function types when you don't actually have function types in your category (such as differential geometry) or that all you care about is a "core" set of operations and the rest of the framework you're working in simply gets in the way (such as Hilbert spaces vs. compact closed dagger categories in categorical quantum mechanics). And if you know already knew dependent type theory then synthetic homotopy theory is easier than classical homotopy theory, some proofs in homotopy theory can take several lectures to present and even then it will still be pretty hard to see why they hold.

It's just weird to see people thing the category theorists are the one being impractical compared to the set theorists like Friedman. I can't think of a categorical logician who doesn't have an active line of research outside of logic; usually in topology, computability, quantum mechanics, or algebraic geometry. They're not just logicians but active researchers in computer science, physics and mathematics, logic is a powerful tool and should be applied in these fields.

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Thursday February 23, 2017 @03:06PM (#13717253)
I'm not trying to rule who is more reasonable (and frankly, I have no idea) and certainly not to misrepresent category theorists (whom I didn't mention), but just respond to fmap's statement that "ZFC itself is unnatural as a foundation for mathematics", which assumes that 1. a foundation is something is regularly used for anything, and 2. that it is something that is both fixed and essential for mathematics; in other words that the name "foundation", rather than signifying the study of math at the lowest levels, actually refers to something fundamental mathematics "rests on". Very little math is done on top of a formal foundation at all, and most of math does not even require a foundation. In fact, it is questionable whether any formal "foundations" are really foundational, or, as Wittgenstein called them, "just another calculus". If that is the case, it's meaningless to argue that ZFC isn't a natural foundation for mathematics, because in spite of the name, it may not really be a foundation at all; just another calculus that is called "foundational" because of its level of discourse, in which case the arguments against it can only be aesthetic or pragmatic. In order to be pragmatic, you need to say what for what uses the foundation is inadequate.

But I think it's naive to pretend that there's no fight over aesthetics here, which is why I mentioned Turing, as I see a return to logicistic (as in logicism) arguments (which view mathematical foundations as truly fundamental) in new form, while Turing's philosophy manages to, according to Wittgenstein, avoid "needless dogmatism and dispute". I strongly encourage anyone interested in the subject to read Juliet Floyd's fascinating paper on Turing's mathematical philosophy: https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf

Re:Harvey Friedman bringing incompleteness and infinity out ... by hyperpape on Thursday February 23, 2017 @11:17AM (#13715069)
Algebraic geometry seems entirely like ordinary math, in the funny sense where it doesn't mean "elementary" but "the kind of thing mathematicians who don't intrinsically care about foundations like to do".
Re:Harvey Friedman bringing incompleteness and infinity out ... by catnaroek on Thursday February 23, 2017 @01:36PM (#13716431)
If anything, if we want to take computation more seriously, we should adopt a foundation that accounts for non-terminating computation natively. One defect of MLTT is that, when you add non-terminating computation to it, the mathematical structures you can describe in it get horribly deformed. So MLTT users tend to limit themselves to a world where computation can't be expressed unless you have established beforehand that it will halt. What a sorry state of affairs! (Of course, ZFC is even worse in this regard, at least in MLTT you have a more or less direct relationship between programming and proving.)

Fortunately, I think the solution already exists, although the details might yet have to be polished: take Paul Blain Levy's “call by push value” (which distinguishes between values and computations), and make the dependent type formers (sigma and pi) range over values and only values...

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Thursday February 23, 2017 @02:02PM (#13716680)
> If anything, if we want to take computation more seriously, we should adopt a foundation that accounts for non-terminating computation natively... Of course, ZFC is even worse in this regard.

I really don't understand this line of argument, regardless of the conclusion. Does the application of math to physics suggest that we should adopt a logical foundation of mathematics that does not allow expressing speed quantities greater than the speed of light? This notion may not be as far-fetched as it may seem, because the sole justification for defining problems that take an infinite number of steps to compute as "non-computable" in the first place was physical, as was Brouwer's justification for intuitionistic mathematics. Moreover, Turing quickly realized that computability (or its converse, non-termination) are crude approximations for feasibility (or tractability), that was more fully developed later. And we could continue this argument further to any degree, so why stop at computability?

Re:Harvey Friedman bringing incompleteness and infinity out ... by catnaroek on Thursday February 23, 2017 @03:18PM (#13717375)
With all due respect to physicists and their work, physics doesn't belong in the foundation of mathematics. If our understanding of physics changed drastically tomorrow (an admittedly very improbable event), all mathematics not directly related to physics should remain unaffected. On the other hand, computation does belong in the foundations: constructing and verifying proofs (even informal ones) is computing, and it is the role of foundations to tell us how those computations can be carried out in a pleasant way. Any change in our understanding of computation should lead us to revise how we construct and verify proofs.
Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Thursday February 23, 2017 @03:28PM (#13717442)
But the definition of computation is physical. The Church-Turing thesis is a physical hypothesis. It is conceivable that a new physical discovery will contradict the Church-Turing thesis, and with it the definition of what is computable (and in particular how we construct and verify proofs, which is but a small part of computation).
Re:Harvey Friedman bringing incompleteness and infinity out ... by catnaroek on Thursday February 23, 2017 @03:40PM (#13717558)
> But the definition of computation is physical.

A lot of mathematics is inspired by physical considerations, but mathematical concepts are themselves not physical. In particular, computation is just having state transitions, not necessarily in a physical system. (Just like recursion is any form of self-reference in any definition, not necessarily procedure definitions.)

> The Church-Turing thesis is a physical hypothesis.

Then let's not mention it, and stick to what can be dealt with mathematically.

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Thursday February 23, 2017 @05:20PM (#13718376)
> A lot of mathematics is inspired by physical considerations, but mathematical concepts are themselves not physical.

I'm not sure I understand your point. It is true that any computation can be modeled mathematically, but so can any other physical process. Also, computation does not require a specific physical implementation and is an abstract concept, but so what? Gödel, Turing and von Neumann were very well aware that computation is a physical/philosophical concept described mathematically, not a purely mathematical one.

> Then let's not mention it, and stick to what can be dealt with mathematically.

But the definition of what is computable and what isn't depends on the Church-Turing thesis.

Re:Harvey Friedman bringing incompleteness and infinity out ... by eastWestMath on Thursday February 23, 2017 @11:27PM (#13721006)
Computation is an entirely abstract thing. Nowhere does the definition of Turing machines or the lambda calculus makes any reference to actual physical things.
Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Friday February 24, 2017 @03:15AM (#13721963)
Church doesn't really define computation[1], and Turing most certainly bases his entire definition (the first ever definition of computation) on multiple references to physical things (finite "states of mind", limits of what can be read or manipulated at any one time etc.). Brouwer also bases intuitionism on the physical, when he appeals to the limited capability of a finite (idealized) mind. Computation carried out with an infinitely fast (in terms of physical time) and/or infinitely large computer is not Turing computation.

[1]: He conjectures that LC coincides with what he calls a "a vague intuitive notion" of an algorithm, and when he tries to make a rigorous argument he finds that he needs to rely on circularity, and writes this: "if this [circular] interpretation or some similar one is not allowed, it is difficult to see how the notion of an algorithm can be given any exact meaning at all."

Re:Harvey Friedman bringing incompleteness and infinity out ... by fmap on Friday February 24, 2017 @04:21AM (#13722223)
Can you link to some of the references you cite? That seems like an interesting read.

As for computability being a physical notion, I can't speak to the motivation of Church and his students, but I do know that there are characterizations of total computable functions in domain theory which make no mention of physics. The intuition about computable functions is that they are precisely the functions whose output for any given input depends only on a finite part of the input. The really interesting thing about the Church Turing thesis is that there are so many different models of computation that capture precisely this idea (the surprising part is that these very simple models are expressive enough to cover all computable functions).

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Saturday February 25, 2017 @06:03AM (#13731033)
P.S.

I also strongly recommend the excellent 1988 paper by Robin Gandy, The Confluence of Ideas in 1936, published in The Universal Turing Machine A Half-Century Survey (ed. Rolf Herken), 1995[1] (pp. 51-102).

Gandy gives a full historical background of who knew what in 1936, what the general state of knowledge was at the time, and the reception of both Church's and Turing's papers.

[1]: https://www.amazon.com/Universal-Turing-Machine-Half-Century...

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Friday February 24, 2017 @07:33AM (#13723010)
> Can you link to some of the references you cite? That seems like an interesting read.

Sure.

It's best to start with Jean van Heijenoort's seminal From Frege to Gödel A Source Book in Mathematical Logic, 1879-1931[1]. It includes the original texts by Hilbert, Brouwer and many others, but the text I personally found most interesting was Hermann Weyl's, which I quoted here[2] nearly in full (in the parent comment I quoted some relevant passages from Brouwer and Hilbert; in fact, it was as part of that Reddit discussion that I found the references and learned what little I know of the philosophy of mathematics).

I've also found Juliet's Floyd's discussion of Turing's (and Wittgenstein's) mathematical philosophy[3] fascinating. She pinpoints how and why Turing viewed the philosophy of mathematics the way he did, how that view led him to the discovery of computation, and why people like Gödel and others found that to be such a profound philosophical breakthrough.

The Stanford Encyclopedia of Philosophy's entry on the philosophy of mathematics gives a good overview[4].

> The intuition about computable functions is that they are precisely the functions whose output for any given input depends only on a finite part of the input.

Once you know what computation is, you can define it in many ways. But why would that definition coincide with what we call computation? You can define foo to be such functions, but why are you calling them computable? And, BTW, even the very definition of finite possibly (I'm not sure about this point) requires reliance on the physical due to the multiple models of FOL and the problems with SOL.

> The really interesting thing about the Church Turing thesis is that there are so many different models of computation that capture precisely this idea

It is absolutely trivial to come up with a super-Turing mathematical model (e.g. just use reals, as in "pick the supremum of this bounded set of reals", or use a Turing machine with an infinite number of heads). All those other models are somehow based on capturing an intuitive notion of the human thought process, which is completely physical, and therefore, it is not surprising that they coincide. Turing was just the first who was able to give the notion a precise mathematical meaning. If you go back to the inception of those ideas, from Brouwer's intuitionism, Hilbert's formalism and even to the far older notion of the algorithm, you see that they're all tied to the capabilities of a physical human mind.

It's true that not all of those ideas actually mention physics because not all thinkers necessarily believed the mind to be completely physical, but they're all based on the idea of a limited mind, which I think we can safely call physical.

[1]: http://www.hup.harvard.edu/catalog.php?isbn=9780674324497

[2]: https://www.reddit.com/r/programming/comments/5k1v04/is_math...

[3]: https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf

[4]: https://plato.stanford.edu/entries/philosophy-mathematics/

Re:Harvey Friedman bringing incompleteness and infinity out ... by eastWestMath on Friday February 24, 2017 @10:25AM (#13724435)
The lambda calculus preceded Turing machines, in fact Turing worked on the lambda calculus before he published his work on Turing machines. Where on Earth did you pick up this rubbish?
Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Friday February 24, 2017 @11:51AM (#13725313)
Oh, I picked it up from Church's original 1936 paper. Those were direct quotes. Did you actually read Church's An Unsolvable Problem of Elementary Number Theory and Turing's On Computable Numbers? If so, could you point out Church's rigorous definition of computation?

BTW, while the lambda calculus does indeed precede Turing's work, its recognition as a universal expression of what is calculable happened at exactly the same time. But regardless, Church does not define the notion of computation, while Turing does.

But you don't have to take my word for it. You can find such rubbish by Gandi (who called Turing's work a "paradigm of philosophical analysis"), Davis, Gödel and many others: Gödel offered enthusiastic praise when he wrote that Turing offered "the precise and unquestionably adequate definition of the general concept of formal system" (Floyd, https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf)

The belief that Church defined computation rigorously when he solved the Entschidungsproblem using the lambda calculus rather than just made an imprecise conjecture is a common mistake and historical revisionism. If anyone came close to defining computation before Turing, that would have been Brouwer.

Also, I don't know if Turing worked on lambda calculus before he wrote On Computable Numbers. After completing the manuscript, he saw Church's new paper and incorporated it in an appendix. Do you have any reference for that?

Re:Harvey Friedman bringing incompleteness and infinity out ... by eastWestMath on Friday February 24, 2017 @12:24PM (#13725615)
>The belief that Church defined computation rigorously when he solved the Entschidungsproblem using the lambda calculus rather than just made an imprecise conjecture is a common mistake and historical revisionism.

Ok I'm out, you do you man.

Re:Harvey Friedman bringing incompleteness and infinity out ... by pron on Friday February 24, 2017 @04:05PM (#13727891)
You're free to believe what you want, or you can go read the abundant material, starting with Church's paper. If you find a thorough treatment of the concept of computation, you can write a paper about it. Church himself explicitly writes that he's unable to give a precise definition. Church was the first (scooping Turing by a few months) to claim that a certain formalism is what we now call Turing complete, i.e., universal with respect to the "vague intuitive notion" of the algorithm, but he was unable to provide a satisfactory justification for his claim (he made a circular argument and then gave up, writing the sentence I quoted above).

Turing, on the other hand, gives a fundamental treatment of what computation is, independent of any particular formalism (in his review of Turing's paper, Church described it as explaining how to construct "arbitrary" computing systems, and Gödel said, in the quote I've given, that Turing was able to give a general, universal, treatment of what a formal system is).

While I can't argue with your claim that Turing had worked with lambda calculus prior to writing On Computable Numbers when he was 24, I have seen no mention of this, but would be happy to see a reference.

Re:Harvey Friedman bringing incompleteness and infinity out ... by AnimalMuppet on Thursday February 23, 2017 @04:34PM (#13718016)
> constructing and verifying proofs (even informal ones) is computing

I'd like to see your proof for that assertion...