6 ms·

The problem solution in the article uses the axiom of choice to construct a "nonprincipal ultrafilter" on the natural numbers. This is actually weaker than the

by fmap 10y ago

The problem solution in the article uses the axiom of choice to construct a "nonprincipal ultrafilter" on the natural numbers. This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. It's a nice exercise to show that with the same assumptions as in the article you can decide the halting problem. (hint: consider the boolean sequence where the nth element is true iff the Turing machine halts within n steps) As for the axiom of choice, the real problem is trying to claim that it is right or wrong in the first place. Mathematics as a whole has never quite recovered from the failure of Hilbert's program... The bottom line is that there is no complete and consistent notion of "truth". There is no objective mathematical reality, because it cannot include a statements about its own consistency (and it's easy to translate this into "statements about certain hard problems", by exactly the same process we use to show that some problems are NP complete by reduction from another NP complete problem). On the other hand, this is not actually detrimental to mathematical practice. It only means that you have a lot more freedom in modeling your problem domain. For instance, it turns out that set theory with the axiom of choice is a horrible place to do probability theory in (non-measurable sets and functions are a direct consequence, and you have to go to a lot of trouble to exclude them everywhere). If ZFC was part of some objective mathematical reality, then this would in some sense be unavoidable, since ultimately you want to make statements describing reality. On the other hand, once we realize that this assumption is just plainly false, we can start looking for more refined models.

cygx 10y ago
There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?
- candiodari 10y ago
  > Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized? No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem. If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.
  - cygx 10y ago
    Ok. Not sure I buy that (eg right now, we have no reason to believe that the lifetime of the universe is finite), but that's not what I was getting at: My point is that at worst, the incompleteness theorems only imply that we won't be able to write down all the rules that govern the universe.
    - Tloewald 10y ago
      No incompleteness proves that there will be statements that are true or false that cannot be proven to be true or false. Not being able to write all the rules is a completely different and unrelated thing.
      - wbhart 10y ago
        If they can neither be proved true or false within the system, that means their truth or falsity can be added as axioms to the system and a contradiction will never be reached. So I can assume them to be true or false, and develop perfectly consistent mathematics. In this way, I can always add more rules to the system (albeit a nonstandard one).
        lurker83256 10y ago
        This is a misunderstanding. Statement A is actually true in the system, you just cannot prove that it is true. Adding an axiom specifying its falsity would be a contradiction (although you could not prove this).
        baddox 10y ago
        Adding either the Godel sentence or its complement would ruin the consistency of the axiomatic system, because the whole point of the Godel sentence is that it claims that itself cannot be proven to be true in its axiomatic system. But you don't get to add axioms to an axiomatic system anyway, because doing so yields a new axiomatic system to which the original Godel sentence does not refer.
- akud 10y ago
  Was going to say the same thing. Most of my professors were secretly platonists, though they had to pass as formalists to get respect in polite society. It's hard to make absolute claims about the nature of mathematical reality; the formalists need to explain why math is so successful in the real world, and the platonists need to give an account of the ontological nature of mathematical objects.
  - breuleux 10y ago
    > why math is so successful in the real world Well, math is a universal approximator -- if there are patterns in what we observe of reality, math can fit them, but that's a far cry from them "being" math. Other formal systems like Turing machines or Lambda calculus can also approximate anything (including each other, naturally) with different primitives... and they have an easier ontology (as far as I can tell). I mean, if you posit that fundamental reality is a computer of sorts, you get your ontology, and you get math as a very good formalism to describe the particular program we're in.
- fmap 10y ago
  Yes, and indeed Gödel himself believed in an objective mathematical reality. What I meant to say is that the commonly accepted basis for mathematics (first order logic and ZFC) was first justified using arguments which later turned out to be false. Logically, we are not finding better and better approximations to some mathematical laws of nature, but rather making a series of arbitrary choices (you can assert the truth or falsity of any independent statement). Philosophically, we can argue about the sense in which the continuum hypothesis ought to be true or false (that is what Gödel did), but practically it makes more sense to think of logic as a tool that you build to describe and solve specific problems.
skissane 10y ago
> There is no objective mathematical reality, because it cannot include a statements about its own consistency Godel's first theorem says no formal system with recursively enumerable axioms and which is powerful enough to express elementary arithmetic can be both consistent and complete. Most people adopt the response – alas, that means no formal systems we can devise can ever be complete (except for systems too weak to express arithmetic, which are not very useful). But, paraconsistency and dialetheism give us another response: yes, we can have complete formal systems with recursively enumerable axioms and which are powerful enough to express elementary arithmetic. Okay, they'll be inconsistent, but inconsistency is not as bad as you thought it was. We can contain the inconsistency to some small area in which it isn't going to bother you, you'll scarcely notice that it is there. We can hide the contradictions in the closet and go on our merry way not thinking about their existence except on rare occasions. If mathematics is inconsistent, does that make mathematics objectively unreal? Only if we insist objective reality must be consistent. If objective reality contains dialetheias, then inconsistent mathematics can be objectively real.
- monochromatic 10y ago
  Having only read the wiki page about dialetheism, it seems a lot more like philosophy than math or logic. Meh.
  - skissane 10y ago
    The whole topic has both its more philosophical aspects and its more mathematical aspects. If you want to explore the more mathematical aspects, you probably want to start here https://en.wikipedia.org/wiki/Paraconsistent_mathematics https://en.wikipedia.org/wiki/Paraconsistent_mathematics and then end up reading something like https://www.amazon.com/Inconsistent-Mathematics-Its-Applications/dp/0792331869 https://www.amazon.com/Inconsistent-Mathematics-Its-Applicat... EDIT: see also https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/12633603_Real%20Analysis%20in%20Paraconsistent%20Logic_a.pdf https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/1263...
    - monochromatic 10y ago
amelius 10y ago
Wikipedia ([1]) describes some ways around Godel's incompleteness theorem. [1] https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_program_after_G.C3.B6del https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_...
caf 10y ago
This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. Presumably this is an ever-present hazard in any proof using the axiom of choice - in this case it is relatively obvious, but how easy is it to accidentally rely on such an uncomputable object in a dusty corner of your proof?

by fmap 10y ago

cygx 10y ago

There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?

candiodari 10y ago
> Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized? No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem. If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.
- cygx 10y ago
  Ok. Not sure I buy that (eg right now, we have no reason to believe that the lifetime of the universe is finite), but that's not what I was getting at: My point is that at worst, the incompleteness theorems only imply that we won't be able to write down all the rules that govern the universe.
  - Tloewald 10y ago
    No incompleteness proves that there will be statements that are true or false that cannot be proven to be true or false. Not being able to write all the rules is a completely different and unrelated thing.
    - wbhart 10y ago
      If they can neither be proved true or false within the system, that means their truth or falsity can be added as axioms to the system and a contradiction will never be reached. So I can assume them to be true or false, and develop perfectly consistent mathematics. In this way, I can always add more rules to the system (albeit a nonstandard one).
      - lurker83256 10y ago
        This is a misunderstanding. Statement A is actually true in the system, you just cannot prove that it is true. Adding an axiom specifying its falsity would be a contradiction (although you could not prove this).
        baddox 10y ago
        Adding either the Godel sentence or its complement would ruin the consistency of the axiomatic system, because the whole point of the Godel sentence is that it claims that itself cannot be proven to be true in its axiomatic system. But you don't get to add axioms to an axiomatic system anyway, because doing so yields a new axiomatic system to which the original Godel sentence does not refer.
akud 10y ago
Was going to say the same thing. Most of my professors were secretly platonists, though they had to pass as formalists to get respect in polite society. It's hard to make absolute claims about the nature of mathematical reality; the formalists need to explain why math is so successful in the real world, and the platonists need to give an account of the ontological nature of mathematical objects.
- breuleux 10y ago
  > why math is so successful in the real world Well, math is a universal approximator -- if there are patterns in what we observe of reality, math can fit them, but that's a far cry from them "being" math. Other formal systems like Turing machines or Lambda calculus can also approximate anything (including each other, naturally) with different primitives... and they have an easier ontology (as far as I can tell). I mean, if you posit that fundamental reality is a computer of sorts, you get your ontology, and you get math as a very good formalism to describe the particular program we're in.
fmap 10y ago
Yes, and indeed Gödel himself believed in an objective mathematical reality. What I meant to say is that the commonly accepted basis for mathematics (first order logic and ZFC) was first justified using arguments which later turned out to be false. Logically, we are not finding better and better approximations to some mathematical laws of nature, but rather making a series of arbitrary choices (you can assert the truth or falsity of any independent statement). Philosophically, we can argue about the sense in which the continuum hypothesis ought to be true or false (that is what Gödel did), but practically it makes more sense to think of logic as a tool that you build to describe and solve specific problems.

skissane 10y ago

> There is no objective mathematical reality, because it cannot include a statements about its own consistency Godel's first theorem says no formal system with recursively enumerable axioms and which is powerful enough to express elementary arithmetic can be both consistent and complete. Most people adopt the response – alas, that means no formal systems we can devise can ever be complete (except for systems too weak to express arithmetic, which are not very useful). But, paraconsistency and dialetheism give us another response: yes, we can have complete formal systems with recursively enumerable axioms and which are powerful enough to express elementary arithmetic. Okay, they'll be inconsistent, but inconsistency is not as bad as you thought it was. We can contain the inconsistency to some small area in which it isn't going to bother you, you'll scarcely notice that it is there. We can hide the contradictions in the closet and go on our merry way not thinking about their existence except on rare occasions. If mathematics is inconsistent, does that make mathematics objectively unreal? Only if we insist objective reality must be consistent. If objective reality contains dialetheias, then inconsistent mathematics can be objectively real.

monochromatic 10y ago
Having only read the wiki page about dialetheism, it seems a lot more like philosophy than math or logic. Meh.
- skissane 10y ago
  The whole topic has both its more philosophical aspects and its more mathematical aspects. If you want to explore the more mathematical aspects, you probably want to start here https://en.wikipedia.org/wiki/Paraconsistent_mathematics https://en.wikipedia.org/wiki/Paraconsistent_mathematics and then end up reading something like https://www.amazon.com/Inconsistent-Mathematics-Its-Applications/dp/0792331869 https://www.amazon.com/Inconsistent-Mathematics-Its-Applicat... EDIT: see also https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/12633603_Real%20Analysis%20in%20Paraconsistent%20Logic_a.pdf https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/1263...
  - monochromatic 10y ago

amelius 10y ago

Wikipedia ([1]) describes some ways around Godel's incompleteness theorem. [1] https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_program_after_G.C3.B6del https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_...

caf 10y ago

This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. Presumably this is an ever-present hazard in any proof using the axiom of choice - in this case it is relatively obvious, but how easy is it to accidentally rely on such an uncomputable object in a dusty corner of your proof?