News for hackers. Stuff that matters.
Re:One-sentence proof of Fermat's theorem on sums of two squ... by Chinjut on Tuesday July 26, 2016 @06:07PM (#12169085)
Sure, Markov's principle matters for some things, but it seems to me Markov's principle doesn't really matter for this particular claim ("for every prime p, such-and-such a decidable property phi(p) is true"), since the only unbounded quantifier is the initial universal one. Any classical proof of a Pi_1 (or even Pi_2, using the Friedman translation) proposition can be straightforwardly turned into an intuitionistic proof of the same proposition (technically, I mean specifically that Peano Arithmetic is Pi_2-conservative over Heyting Arithmetic [and I suppose there are similar results for stronger systems but we don't need those]).

So there is no surprise that this particular statement's proof is constructive, given that it is classically provable at all [again, technically, I am referring to classical provability in PA, but it would be shocking if Fermat's old proof, or any other anyone bothered with for a statement of this sort, had somehow relied on anything beyond PA]. For other more quantifier-complex classical theorems, it would be of more note to observe whether a particular proof could be made constructive (in the mere sense of intuitionistic mathematics) or not, but for this one, there's nothing to it.

Anyway, I think I'm arguing pedantically about something there's no reason for me to argue about at all. Sorry about that! I think we're both in agreement that this is great, its constructiveness is great, math is great. Hooray!

Re:One-sentence proof of Fermat's theorem on sums of two squ... by fmap on Tuesday July 26, 2016 @06:44PM (#12169289)
Yeah, I don't think we actually disagree here... all I was saying is that there are proofs which are genuinely non-constructive, and this isn't one.

You are arguing that this usage of "constructive" is basically meaningless for statements like this. It could only make a difference for artificial examples or artificially complicated proofs. This is definitely true.

To be honest, I shouldn't have brought this up in the first place. I know what the author meant by claiming the proof is non-constructive (it doesn't give a formula for computing x,y such that x^2 + y^2 = p), and this is the idiomatic usage of the word non-constructive for this particular field. It's just different from the rest of the world, but that's nothing new.

Re:One-sentence proof of Fermat's theorem on sums of two squ... by oggy on Wednesday July 27, 2016 @05:30AM (#12171518)
Thanks for that post, that's interesting. Do you by chance have any pointers to a good textbook that covers these things?