5 ms·

As others have mentioned, the article is missing a crucial constraint, which is essentially that it holds on the closed unit ball and spaces homeomorphic to it.

As others have mentioned, the article is missing a crucial constraint, which is essentially that it holds on the closed unit ball and spaces homeomorphic to it. As you mentioned, it's also not intuitive. It's by now well-digested, but it's a fairly surprising theorem, even to Brouwer. Finally, it's not constructive. Generally you can't figure out which point is fixed. If I recall correctly, frustration with this fact fueled Brouwer's interest in intuitionism, which gives us a type of logic where some propositions are neither true nor false but essentially undecidable. I'm not sure what you mean by a "particle" in your sentence. If you mean to go down to the quantum scale, then I'm sure all sorts of things go wrong in trying to apply the theorem. For one, even talking about the position of a particle at all is very different from talking about a point in Euclidean space. If you don't mean to go down to the quantum scale, then lots of maps have fixed points. Rotations an reflections are two large classes of examples.

vlovich123 5y ago
Does intuitionism go beyond Gödel’s incompleteness theorem? Or is it an unrelated thing?
- skulk 5y ago
  This philosophy.se post answers that question: https://philosophy.stackexchange.com/questions/7194/how-is-g%C3%B6dels-incompleteness-theorem-interpreted-in-intuitionistic-logic https://philosophy.stackexchange.com/questions/7194/how-is-g...
- deleted 5y ago
  [deleted]
- SquishyPanda23 5y ago
  They are different things, although "unrelated" might be a bit strong. I'm sure there are interesting things to say about the incompleteness theorem and intuitionistic logic. Intuitionistic logic is a logic that is weaker than classical logic in the sense that there are some proofs in classical logic that don't work in intuitinistic logic. Specifically, the law of the excluded middle (either A is true or not A is true") does not hold. You can convince yourself that this is a reasonable type of logic by interpreting "A is true" to mean "I have a proof of A", and likewise "not A is true" means "I have a proof of not A". Then it's pretty reasonable that you neither have a proof of A or of not A. I haven't read Godel's proof, but my understanding is that he uses intuitionistic logic in some of the key steps. Since facts in intuitionistic logic are also facts in classical logic, then I believe the incompleteness theorem holds in both logics. But I'm not at all an expert here, so someone please correct me if I'm wrong. "Intuitionism" also refers to a specific philosophy of mathematics. But a lot of people just use the word to refer to the logic that came out of that philosophical school. Intuitionistic logic is also very common in type theory, so a lot of proof assistants use it.
  - TeMPOraL 5y ago
    >>> intuitionism, which gives us a type of logic where some propositions are neither true nor false but essentially undecidable. Between math and software development, I feel I've encountered this idea at least three times (+ rediscovered it independently), under different names - "3-value logic", "3-state booleans" - without ever hearing about "intuitionism". Thanks for mentioning it, and now I wonder how it all relates (i.e. I'm about to get stuck on Wikipedia). > interpreting "A is true" to mean "I have a proof of A", and likewise "not A is true" means "I have a proof of not A". Makes me think of an interesting progression I've also seen when studying maths and then (classical) AI algorithms. You start with boolean logic, then figure out you need to represent lack of knowledge/certainty and get 3-state logic. Then someone notices that there are degrees to being sure, and you get fuzzy logic[0], representing logical values as real numbers. And then someone notices that this smells awful lot like probability theory, and you get Bayesian probability as applied to reasoning, with all the extra concepts like using whole probability distributions as first-class logic values. -- [0] - I'm not sure how much mathematical rigour there is to it; it's something I've learned when studying AI for videogames.
    - SquishyPanda23 5y ago
      This is an interesting point. I haven't really thought about the connection between intuitionistic logic and three-valued logic before. They are different logics in general though. 3-value logic is more like the A is True, False or None/Unknown. Another interpretation one can put on intuitionistic logic is game semantics. Here a statement is true if the verifier has a winning strategy to prove the proposition. It's false if the falsifier has a winning strategy. Then intuitionistic logic corresponds roughly to the idea that some games don't have a winning strategy for either player. So here (and in the proofs example I gave above) is that we get an idea of "neither true nor false" that is represented by the lack of an explicit rule for concluding truth or falsity in some cases. In contrast, 3-valued logic gets at the idea of "neither true or false" by introducing another symbol (e.g. "None" or "-1") together with new operators that operate on sentences with that symbol. So we get one from classical logic by deleting something (namely the law of the excluded middle) and the other by adding something.
im3w1l 5y ago
> Generally you can't figure out which point is fixed. So just thinking out loud here but like in the 1d case... The set will be an interval [a,b] Let g(x) = f(x) - x g(a) >= 0 and g(b) <= 0. Now we can use the intermediate value value theorem and binary search to find (get arbitrary close) a point with g(x) = 0 (i.e. fix point of f). Not possible to do such searches in higher dimensions?
- ChrisKnott 5y ago
  I'm not sure that even works in 1 dimension...? I don't think you necessarily have g(a) >= 0 and g(b) <= 0. Finding the starting points for binary search might be essentially as hard as finding the fixed point.
  - im3w1l 5y ago
    a <= f(x) <= b Hence a <= f(a), so 0 <= f(a) - a = g(a)
- SquishyPanda23 5y ago
  You can generally approximate the fixed point. You can possibly do this to arbitrary precision, but I'm not sure. This is useful for practical applications, but it's not the same as knowing the fixed point for mathematical applications. E.g. you may want to prove that some function preserves the irrational number pi. But you may not be able to prove it, only show that computations make your conjecture more and more likely.

vlovich123 5y ago

Does intuitionism go beyond Gödel’s incompleteness theorem? Or is it an unrelated thing?

skulk 5y ago
This philosophy.se post answers that question: https://philosophy.stackexchange.com/questions/7194/how-is-g%C3%B6dels-incompleteness-theorem-interpreted-in-intuitionistic-logic https://philosophy.stackexchange.com/questions/7194/how-is-g...
deleted 5y ago
[deleted]
SquishyPanda23 5y ago
They are different things, although "unrelated" might be a bit strong. I'm sure there are interesting things to say about the incompleteness theorem and intuitionistic logic. Intuitionistic logic is a logic that is weaker than classical logic in the sense that there are some proofs in classical logic that don't work in intuitinistic logic. Specifically, the law of the excluded middle (either A is true or not A is true") does not hold. You can convince yourself that this is a reasonable type of logic by interpreting "A is true" to mean "I have a proof of A", and likewise "not A is true" means "I have a proof of not A". Then it's pretty reasonable that you neither have a proof of A or of not A. I haven't read Godel's proof, but my understanding is that he uses intuitionistic logic in some of the key steps. Since facts in intuitionistic logic are also facts in classical logic, then I believe the incompleteness theorem holds in both logics. But I'm not at all an expert here, so someone please correct me if I'm wrong. "Intuitionism" also refers to a specific philosophy of mathematics. But a lot of people just use the word to refer to the logic that came out of that philosophical school. Intuitionistic logic is also very common in type theory, so a lot of proof assistants use it.
- TeMPOraL 5y ago
  >>> intuitionism, which gives us a type of logic where some propositions are neither true nor false but essentially undecidable. Between math and software development, I feel I've encountered this idea at least three times (+ rediscovered it independently), under different names - "3-value logic", "3-state booleans" - without ever hearing about "intuitionism". Thanks for mentioning it, and now I wonder how it all relates (i.e. I'm about to get stuck on Wikipedia). > interpreting "A is true" to mean "I have a proof of A", and likewise "not A is true" means "I have a proof of not A". Makes me think of an interesting progression I've also seen when studying maths and then (classical) AI algorithms. You start with boolean logic, then figure out you need to represent lack of knowledge/certainty and get 3-state logic. Then someone notices that there are degrees to being sure, and you get fuzzy logic[0], representing logical values as real numbers. And then someone notices that this smells awful lot like probability theory, and you get Bayesian probability as applied to reasoning, with all the extra concepts like using whole probability distributions as first-class logic values. -- [0] - I'm not sure how much mathematical rigour there is to it; it's something I've learned when studying AI for videogames.
  - SquishyPanda23 5y ago
    This is an interesting point. I haven't really thought about the connection between intuitionistic logic and three-valued logic before. They are different logics in general though. 3-value logic is more like the A is True, False or None/Unknown. Another interpretation one can put on intuitionistic logic is game semantics. Here a statement is true if the verifier has a winning strategy to prove the proposition. It's false if the falsifier has a winning strategy. Then intuitionistic logic corresponds roughly to the idea that some games don't have a winning strategy for either player. So here (and in the proofs example I gave above) is that we get an idea of "neither true nor false" that is represented by the lack of an explicit rule for concluding truth or falsity in some cases. In contrast, 3-valued logic gets at the idea of "neither true or false" by introducing another symbol (e.g. "None" or "-1") together with new operators that operate on sentences with that symbol. So we get one from classical logic by deleting something (namely the law of the excluded middle) and the other by adding something.

im3w1l 5y ago

> Generally you can't figure out which point is fixed. So just thinking out loud here but like in the 1d case... The set will be an interval [a,b] Let g(x) = f(x) - x g(a) >= 0 and g(b) <= 0. Now we can use the intermediate value value theorem and binary search to find (get arbitrary close) a point with g(x) = 0 (i.e. fix point of f). Not possible to do such searches in higher dimensions?

ChrisKnott 5y ago
I'm not sure that even works in 1 dimension...? I don't think you necessarily have g(a) >= 0 and g(b) <= 0. Finding the starting points for binary search might be essentially as hard as finding the fixed point.
- im3w1l 5y ago
  a <= f(x) <= b Hence a <= f(a), so 0 <= f(a) - a = g(a)
SquishyPanda23 5y ago
You can generally approximate the fixed point. You can possibly do this to arbitrary precision, but I'm not sure. This is useful for practical applications, but it's not the same as knowing the fixed point for mathematical applications. E.g. you may want to prove that some function preserves the irrational number pi. But you may not be able to prove it, only show that computations make your conjecture more and more likely.