Comment by saithound | Hacker News Reader

Comment by saithound | Hacker News Reader

Parent Full thread

> This is the standard nested interval proof

It is not.

I'll be honest: your one sentence response tells me you did not read the proof above in any detail.

I chose Nelson's proof precisely because its construction is well-studied and well-understood. The same construction of a mesh containing all standard points, with the coloring forcing a tiny multicolored cell, extends from the interval to the triangle. In one dimension you get two adjacent differently colored points; in two dimensions you get an infinitesimal triangle whose three vertices have the three relevant colors. Taking their common standard part and applying continuity gives a short proof of Brouwer's fxied-point theorem on the triangle.

But it is well-understood (there's a whole field studying such questions [2]) that the nested interval proof of the Intermediate Value Theorem does not generalize to proving Brouwer's fixed point theorem on the triangle [1]. This fact can be derived from a computability argument as well [3].

Nelson's argument does generalize to prove Brouwer, so it's not the nested intervals argument. But really, nobody cares about these technical reasons. It's obvious to most math undergraduates that Nelson's proof is not the nested interval proof, the clear absence of any nested construction kinda gives it away. The only reason it was necessary to get technical is that you did not really inspect the proof before claiming it was nested intervals. The technical results cited above are just a formal way to show that any correspondence you might imagine between the two proofs is just not there.

[1] Shioji/Tanaka: "Fixed Point Theory in Weak Second-Order Arithmetic", Annals of Pure and Applied Logic v47, pp 167188 (1990).

[2] https://en.wikipedia.org/wiki/Reverse_mathematics

[3] Potgieter: "Computable counter-examples to the Brouwer fixed point theorem", https://arxiv.org/abs/0804.3199 (2008).

What you just described is a classic proof of Brouwer's fixed point theorem using Sperner's lemma. The proof you cited earlier does not generalize to it on its own, the Sperner's lemma is a crucial combinatorial ingredient. It's crucial, because it only works on spaces with the topology of the triangle; you cannot perform the same argument on, say, an annulus.

In the standard formulation, you apply the Sperner's lemma to find smaller and smaller triangles, and apply compactness, precisely as in the standard proof of intermediate value theorem.

The rest of your post, where you quote reverse mathematics stuff, is completely irrelevant to the point I was making. Nothing I said is about what theorems follows from what axioms, but rather whether nonstandard analysis is meaningfully different, clearer, or more useful language than standard one. It is not.

You made a sweeping claim that nonstandard analysis arguments are the exact same arguments, wrapped in nonstandard langauge. I explained that (while your other claims about simplicity may be valid) this is not so and detracts from the rest of your points. I challenged you to defend your "same arguments" claim by finding any standard analysis textbook which teaches a standard language version of Nelson's argument as a proof of the IVT. Let me recap what happened since then:

1. Two comments ago you confidently claimed that Nelson's IVT proof is "the standard nested interval proof" with the limiting step written in nonstandard language. That is a straightforward claim about the structure of the proof, one that you didn't bother to substantiate, and that is straightforwardly false.

2. After I explained why it's false (Nelson's construction proves BFPT, which no nested interval type proof can do), you changed your response: now the Sperner lemma was a "crucial additional ingredient". But Nelson's combinatorial step, that opposite endpoint colors force a blue-red interval, _is_ the one-dimensional instance of the Sperner lemma (and indeed the base case when you prove Sperner's lemma for arbitrary dimensional simplices by induction; the analytic part is independent of dimension, once you find an infinitesimal multicolored simplex, you take its common standard part and apply continuity exactly as before).

3. Then you wrote this:

> In the standard formulation, you apply the Sperner's lemma to find smaller and smaller triangles, and apply compactness, precisely as in the standard proof of intermediate value theorem.

There is a standard proof of Brouwer via the Sperner lemma, and it is _also_ not of the same form as the standard nested interval proof of the IVT. In the nested interval proof, you find a sign-change interval, then find a smaller sign-change interval inside it, and so on. The intersection of all of these contains a point, and that's your zero. Nelson's proof does not do this, and neither does the standard proof of Brouwer via the Sperner lemma: you do not, and cannot, take a 3-color interior triangle, then find a smaller 3-color interior triangle inside it and so on. Even the first step would not work, since the inherited labelling does not satisfy the right boundary condition relative to the small triangle!

And this is also why the computability paper I cited ("where I quote reverse mathematics stuff" ;) was very much relevant. There can be no effective "nested triangle" proofs of the Brouwer fixed point theorem at all, because such a proof would let you compute a Brouwer fixed point, and there are examples of computable maps on the triangle without computable fixed points. If Nelson's IVT proof was the nested interval proof, then swapping in the higher-dimensional Sperner step would give a nested-type proof of BFPT. No such proof can exist. Since Nelson's argument proves the BFPT without any change to the analytic part, it is not a nested interval type argument.

You first misidentified Nelson's proof as nested intervals, and then treated Sperner as an additional ingredient even though the coloring step in Nelson's proof is already the corresponding Sperner argument. Those are both fairly serious misunderstandings about these proof. Given this, I don't think our exchange leaves readers with much confidence in your assessment of NSA's drawbacks and benefits. That's a disappointing outcome, as far as I'm concerned. There are good arguments to make that NSA adds little value to undergraduate education, such as simplicity or the difficulty of the prerequisites, and good conversations to be had about them. But "NSA proofs are the same proofs wrapped in a different language" is not one, and I wish you had just narrowed it instead of doubling down.

I never said the triangles in the standard proof are going to be nested, so your whole segue into reverse mathematics is, just like I said, irrelevant. The point of the argument is that you can find a sequence of triangles with differently colored vertices, the vertices of which all converge to the same point (thanks to compactness), which contradicts continuity of the retraction on the boundary. The nonstandard version of this is exactly the same argument, it just replaces the explicit limiting step that contradicts continuity with the an argument that uses the nonstandard formulation of continuity in terms of infinitesimals.

If that makes it easier for you to understand it, in the standard proof, you also color every point of the rectangle, with the color of the edge it retracts to (picking the colors of the vertices of the big triangle arbitrarily, just making sure that the color of each vertex is a color of one of the edges it belongs to, not one of the opposite edges). Then, an easy argument from continuity shows that no interior point will have points of three different colors arbitrarily close to it. Finally, applying Sperner's lemma as above proves that such point must nevertheless exist, obtaining contradiction with the existence of the retraction.

and then treated Sperner as an additional ingredient even though the coloring step in Nelson's proof is already the corresponding Sperner argument.

I don't understand what are you saying here. What I'm saying is that for the coloring proof of BFPT to work, whether clothed in standard or nonstandard language, you must perform a combinatorial argument that uses a topology of a triangle as a necessary ingredient, similar in shape to the proof of Sperner's lemma.

You opened with the claim that nonstandard analysis hasn't caught on because it's "mostly the exact same arguments wrapped in slightly different language". I pointed out that the arguments are in fact very distinct: e.g. Nelson's proof of the intermediate value theorem is something that any NSA student would see, but no standard textbook teaches IVT by a standard language counterpart of it.

One post later, you answered that Nelson's IVT argument is in fact the "standard nested interval proof" with the limiting step rewritten in nonstandard language.

That claim is simply wrong. Why? Because Nelson's construction straightforwardly generalises to Brouwer, while the nested intervals proofs cannot. The discussion of reverse mathematics / computability is not a tangent, it explains precisely why Nelson's proof can generalise to give the BFPT in two dimensions, whereas the nested intervals proofs (which you claim is the same) cannot.

You then brought up that the BFPT generalisation of Nelson's argument needs the Sperner lemma as "crucial additional ingredient". Now you make the same point again:

> What I'm saying is that for the coloring proof of BFPT to work, whether clothed in standard or nonstandard language, you must perform a combinatorial argument that uses a topology of a triangle as a necessary ingredient, similar in shape to the proof of Sperner's lemma.

Presumably you keep pointing this out because you think it justifies some claim like '1D Nelson is actually nested intervals with the limiting step recast in nonstandard language, even if the 2D generalization of Nelson is not'.

But it does not. The combinatorial content is the same, the 1-dimensional interval case uses the topology of the domain just as much as the 2-dimensional triangle case does. The 2D argument wouldn't work on the annulus, and the 1D version would not work on the union of two disjoint intervals. The Sperner lemma is present in 1D, and present in 2D. If instead your point is only that proving the BFPT requires a harder case of the Sperner lemma than IVT, then of course it does. But what relevance does that have to the original claim that Nelson's IVT proof is the nested-interval proof? The proof of the Sperner lemma is pure combinatorics, it does not involve any (standard or nonstandard) analysis.

Or have you changed your mind on your earlier claim that Nelson's proof is "is the standard nested interval proof"?

If so, I think that's great, and closes the thread on whether NSA is largely the same arguments, since even the first proofs of the basic results are different.

If you still think that it's the nested interval proof, well, I am not sure what else to say, apart from linking the literature which studies this exact question, that I've already done, and that you dismissed as a tangent.

Either way, this discussion went on for too long at this point, so I won't monitor it further.

Reply on news.ycombinator.com