News for hackers. Stuff that matters.
Re:The Axiom of Choice Is Wrong (2007) by fmap on Sunday February 05, 2017 @05:58AM (#13571810)
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.

Re:The Axiom of Choice Is Wrong (2007) by skissane on Sunday February 05, 2017 @04:23PM (#13574717)
> 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.

Re:The Axiom of Choice Is Wrong (2007) by monochromatic on Sunday February 05, 2017 @04:57PM (#13574891)
Having only read the wiki page about dialetheism, it seems a lot more like philosophy than math or logic. Meh.
Re:The Axiom of Choice Is Wrong (2007) by skissane on Sunday February 05, 2017 @05:02PM (#13574922)
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 and then end up reading something like https://www.amazon.com/Inconsistent-Mathematics-Its-Applicat...

EDIT: see also https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/1263...

Re:The Axiom of Choice Is Wrong (2007) by monochromatic on Monday February 06, 2017 @05:53PM (#13585091)
Thanks for that last link. I'm working my way through it, and there's interesting material here.
Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @06:47AM (#13571944)
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?

Re:The Axiom of Choice Is Wrong (2007) by akud on Sunday February 05, 2017 @02:50PM (#13574173)
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.
Re:The Axiom of Choice Is Wrong (2007) by breuleux on Sunday February 05, 2017 @05:31PM (#13575083)
> 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.

Re:The Axiom of Choice Is Wrong (2007) by candiodari on Sunday February 05, 2017 @06:53AM (#13571971)
> 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.

Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Sunday February 05, 2017 @02:35PM (#13574097)
> Real space doesn't appear to be infinite

Citation needed. People keep saying things like this ("real space isn't infinite" or "real spacetime must be discrete") but never show their work.

Re:The Axiom of Choice Is Wrong (2007) by smilliken on Sunday February 05, 2017 @04:08PM (#13574660)
Nobody has proof, and it's probably unknowable. It could be that we're a discrete system embedded in a continuous system. Or it could be we're in a seemingly continuous system which is actually embedded in a high precision discrete system.

That being said, nature has given us very strong hints at discretization. For example: https://en.m.wikipedia.org/wiki/Planck_length. Because of uncertainty principle, we can't measure distances less than that. In a similar way, time also appears to be discretized, along with energy and mass.

Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Sunday February 05, 2017 @06:00PM (#13575237)
The fact that we don't know what's going on within the Planck length doesn't demonstrate that spacetime is discretized; I don't even think it strongly indicates it, unless you're already predisposed to think that way. Anyway, that seems to have no bearing on whether the universe is infinite.
Re:The Axiom of Choice Is Wrong (2007) by warrenpj on Sunday February 05, 2017 @06:07PM (#13575278)
There was a post here two weeks ago discussing this exact problem. [1] It starts by explaining Democritus' reasoning that matter must be made of discrete atoms. The main point of the article is that a similar logic applies to the future theory of quantum gravity; space and time too must be discrete.

From the article:

> Importing the atomic philosophy of Democritus into modern physics might be essential for reconciling general relativity (which assumes a continuous reality) with quantum mechanics (which very much does not).

As far as infinite vs finite space: because there is a fixed rate of information propagation, we only need to show that time is finite in extent, and it follows that space is also finite. We know that the visible universe is finite (by looking in the sky) and we can explain why: the big bang happened at a finite time in the past.

We don't know if the universe will have a finite future, but it might be the case. One possible cause of a finite future could be accelerating expansion of the universe due to dark energy. [2]

Of course there are other interpretations of "real space", but this one (causally connected) seems parsimonious to me.

[1] https://news.ycombinator.com/item?id=13466254

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

Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @07:06PM (#13575535)
we only need to show that time is finite in extent, and it follows that space is also finite [...]

That does not follow: As our universe is spatially flat (or close to it), it is consistent with the infinite-space Friedmann model. The cosmic horizon that bounds the observable universe would still exist due to the metric expansion of space.

Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Sunday February 05, 2017 @06:26PM (#13575362)
To the best of my knowledge, mainstream quantum mechanics assumes continuous spacetime, so the argument that the primary reason it can't be reconciled with general relativity is continuity seems pretty specious to me. And it's possible to come up with a model where the universe is infinite but the visible universe is finite. In fact, I believe FLRW is one such a model, and is supported with high accuracy by the latest experimental observations. So again, your argument doesn't seem that compelling to me.
Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @06:54PM (#13575490)
And it's possible to come up with a model where the universe is infinite but the visible universe is finite. In fact, I believe FLRW is one such a model

Just to clarify, FLRW is a class of models, which includes ones with finite as well as infinite space. We've been able to determine that our universe is close to spatially flat. However, that does not mean it's infinite: If spatial curvature is positive but small compared to the cosmic horizon (which is due to spatial expansion), we won't be able to tell.

That said, even given finite space, spacetime can of course still be infinite if the universe does not recollapse.

Re:The Axiom of Choice Is Wrong (2007) by warrenpj on Sunday February 05, 2017 @07:47PM (#13575693)
> To the best of my knowledge, mainstream quantum mechanics assumes continuous spacetime, so the argument that the primary reason it can't be reconciled with general relativity is continuity seems pretty specious to me.

Your criticism is right and that is a bad argument. The real reasons they are hard to reconcile are technical (see for example [1]), and not mentioned in the source I referred to.

The article only says that a discrete theory of spacetime "might be essential" for the reconciliation; the arguments for this are philosophical - it would be beautiful and historically completing. Read the article if you're interested in the arguments, which aren't included in my comments.

> And it's possible to come up with a model where the universe is infinite but the visible universe is finite. In fact, I believe FLRW is one such a model, and is supported with high accuracy by the latest experimental observations.

I agree with you that the universe could be infinite, but that doesn't contradict my previous comment. I explained that I was talking about local (causally connected to us) space-time, only. I admit this is a bit of a trick, but the parent comment used the term "real space" which I interpreted in such a way to favour an argument for finite space.

> So again, your argument doesn't seem that compelling to me.

I've given reasons but I think it might be helpful to restate what I am actually claiming. I admit I don't know that space and time are discrete. The source I gave is a poetic and philosophical argument that it might be. I think it's established fact that energy and matter are, and that time is finite in the past, so the visible universe is finite. I think it's possible that the future is finite too.

I don't know what FLRW is. My best guess is https://en.wikipedia.org/wiki/Friedmann–Lemaître–Robertson–W...

[1] http://www.theory.caltech.edu/people/jhs/strings/str115.html

Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @07:58PM (#13575745)
> I think it's established fact that energy and matter are, and that time is finite in the past, so the visible universe is finite.

None of that is established, actually:

Metric expansion of space comes with a cosmic event horizon where redshift goes to infinity. While the energy contained within that region is finite, there's no reason to assume that the universe outside the horizon looks any different than inside the horizon, and it might very well be spatially infinite.

As to time being finite in the past, it is possible to generalize Einstein's equations so that they can be extended past the big bang singularity, and what you get is a mirror universe on the other side. The issue here is that as we approach Planck scale, quantum gravity becomes relevant, and we have no predictive theory of that.

Re:The Axiom of Choice Is Wrong (2007) by naasking on Sunday February 05, 2017 @03:35PM (#13574473)
Google "Bekenstein Bound".
Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Sunday February 05, 2017 @05:58PM (#13575228)
That doesn't prove anything about the continuity (or lack thereof) of spacetime, just indicates that energy is discretized. Also has no bearing on the original statement about infinity.

It's also worth pointing out that the original statement is nonsensical because the theory of real closed fields doesn't suffer from incompleteness in the first place, so there's no need to "save" it from paradox the way you have to save Peano arithmetic.

Re:The Axiom of Choice Is Wrong (2007) by naasking on Sunday February 05, 2017 @07:50PM (#13575704)
The Bekenstein bound, as a starting point, addresses the more general point that all of known physics needs only computable abstractions. Continuous abstractions are merely for our convenience, and not fundamental as far as we've seen, which does address your specific question about whether space is truly continuous.
Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @08:11PM (#13575797)
Continuous abstractions are merely for our convenience, and not fundamental as far as we've seen

I do not see how that's true for quantum mechanics (take linear superposition as just one example). People may speculate about discrete underpinnings, but at this time, it's merely speculation.

Re:The Axiom of Choice Is Wrong (2007) by naasking on Sunday February 05, 2017 @08:48PM (#13575958)
We simulate quantum mechanics on classical computers all the time. Superposition requires exponentially more resources in some cases, but it doesn't somehow make QM non-discrete.
Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @09:09PM (#13576044)
The point is that according to ordinary QM, any of the states you can construct via superposition are physical.

Eg for the qubit, the state space is the Bloch sphere, which is continuous.

Re:The Axiom of Choice Is Wrong (2007) by naasking on Monday February 06, 2017 @08:45AM (#13579310)
Which is a property of our formalism, not reality. Any state we'd care to actually observe necessarily has finite precision, so the internal mechanics of our formalism to model this process utilizing infinities is an artifact only of our formalism, not of reality.

Furthermore, quantum computing and classical computing are known to have the same computational power, just different computational complexity, ie. any quantum system can be simulated by a classical system with exponential slowdown, at worst.

There are plenty of papers exploring this territory [1,2,3] if you want further details. There are older references but they're not easily available online.

[1] Computability in Quantum Mechanics, 1995, https://philpapers.org/rec/MYRCIQ

[2] Effectively calculable quantum mechanics, 2015, https://arxiv.org/pdf/1508.03879.pdf

[3] Constructive physics, https://arxiv.org/pdf/0805.2859.pdf

Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Monday February 06, 2017 @12:09PM (#13581515)
> Which is a property of our formalism, not reality. Any state we'd care to actually observe necessarily has finite precision, so the internal mechanics of our formalism to model this process utilizing infinities is an artifact only of our formalism, not of reality.

But this is exactly my point. The fact that our observations have finite precision doesn't say anything about the underlying reality. That's the part that you're asserting. If it also turns out that assuming the underlying system is continuous results in much more compact theories than assuming otherwise, why is the obvious conclusion that spacetime is in fact discrete?

Re:The Axiom of Choice Is Wrong (2007) by naasking on Monday February 06, 2017 @06:44PM (#13585487)
> But this is exactly my point. The fact that our observations have finite precision doesn't say anything about the underlying reality. That's the part that you're asserting.

I'm not sure what you think I've asserted, but my only actual assertions are that all of modern physics requires only computable abstractions, and thus, continuous abstractions aren't strictly necessary.

I can certainly make the case that a continuous ontology requires more ontological commitments than a discrete ontology, but I haven't said anything along those lines thus far.

> If it also turns out that assuming the underlying system is continuous results in much more compact theories than assuming otherwise, why is the obvious conclusion that spacetime is in fact discrete?

What is the meaning of "compactness"? A proper comparison of theoretical parsimony requires comparing the Kolmogorov complexity. Compressing ontologies positing reals and/or rationals are definitely less parsimonious than ontologies positing only naturals.

Re:The Axiom of Choice Is Wrong (2007) by Jweb_Guru on Monday February 06, 2017 @11:27PM (#13587014)
> What is the meaning of "compactness"? A proper comparison of theoretical parsimony requires comparing the Kolmogorov complexity. Compressing ontologies positing reals and/or rationals are definitely less parsimonious than ontologies positing only naturals.

As far as I can tell, by this argument there is literally nothing that would convince you that anything but a discrete theory was correct. So I don't think it's a very interesting argument, sorry. But thank you for explaining your viewpoint.

Re:The Axiom of Choice Is Wrong (2007) by naasking on Wednesday February 08, 2017 @12:23PM (#13600066)
I've presented my argument why I don't think it's possible for a continuous ontology to be simpler than a discrete ontology, but if you think that's incorrect, then let's hear it.
Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @07:12AM (#13572048)
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.

Re:The Axiom of Choice Is Wrong (2007) by Tloewald on Sunday February 05, 2017 @10:25AM (#13572723)
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.

Re:The Axiom of Choice Is Wrong (2007) by wbhart on Sunday February 05, 2017 @10:36AM (#13572766)
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).
Re:The Axiom of Choice Is Wrong (2007) by baddox on Sunday February 05, 2017 @12:24PM (#13573356)
A Godel sentence claims that itself cannot be proven in its axiomatic system. If you add another axiom, you have a new axiomatic system that can prove the Godel sentence in the original axiomatic system, but the new axiomatic system will have its own new Godel sentence.
Re:The Axiom of Choice Is Wrong (2007) by lurker83256 on Sunday February 05, 2017 @11:54AM (#13573204)
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).
Re:The Axiom of Choice Is Wrong (2007) by baddox on Sunday February 05, 2017 @12:27PM (#13573378)
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.
Re:The Axiom of Choice Is Wrong (2007) by drdeca on Sunday February 05, 2017 @01:30PM (#13573697)
I think by adding the axiom, they mean considering the axiom system with the old axioms, and also the one being added?

So, assuming the initial system is consistent, adding the godel sentence, or its negation, produces a new consistent system, iirc. But in the second case, it would be omega-inconsistent ?

Re:The Axiom of Choice Is Wrong (2007) by lmm on Sunday February 05, 2017 @01:45PM (#13573800)
> 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.

Assuming the original system was consistent (which you can never prove), yes.

But that doesn't help you, because the new system with these additional axioms will still, provably, contain statements that can't be proven true or false within that system (or else be inconsistent). (Turing did try some programme where you keep adding new axioms and take the transitive closure over all the axioms you'd add, but AIUI that doesn't work out either).

Re:The Axiom of Choice Is Wrong (2007) by cygx on Sunday February 05, 2017 @01:43PM (#13573781)
No incompleteness proves that there will be statements that are true or false that cannot be proven to be true or false.

Careful there: Gödels first incompleteness theorem proves that in a consistent effectively axiomatized formal system, there will be statements that are true or false that cannot be proven to be true or false.

So let's assume there were such a thing as objective mathematical reality and that it could be formalized as The System. As far as I'm aware, all the incompleteness theorem implies is that The System's set of theorems is not recursively enumerable (ie we will never be able to 'write them down').

All we can do is craft necessarily incomplete subsystems applicable to areas of our interest. It's a bit sad that humans will never know the Whole Truth, but such is life...

Re:The Axiom of Choice Is Wrong (2007) by Tloewald on Monday February 06, 2017 @11:50AM (#13581281)
I'm being quite careful: 'consistent effectively axiomatized formal system' is implied by my use of the word 'proves'.
Re:The Axiom of Choice Is Wrong (2007) by pron on Sunday February 05, 2017 @04:40PM (#13574798)
That doesn't really matter. If all you care about is physical reality, you have to apply its implications on everything, and Gödel's incompleteness reappears in a different form. First, consider that undecidability is more general -- i.e., stronger -- than incompleteness, as undecidability implies incompleteness but not vice-versa. If you admit infinity, then you have undecidability and therefore incompleteness. If you don't have infinity because you decide to only care about physical reality, then you don't have undecidability, but then you must treat time as physical (and therefore finite) as well.

While you no longer have undecidability (and therefore no incompleteness, either), you do have its finite form, namely infeasibility (due to computational complexity), which, given an assumption that time is finite, amounts to precisely the same result. Almost every theorem about undecidability can be generalized to infeasibility. For example, instead of undecidability of the halting problem, we get infeasibility of the bounded halting problem (that's the basis for the hierarchy theorems, which gave birth to the notion of computational complexity, just as the halting problem gave birth to the notion of computability). Similarly, by bounded halting, instead of a consequence of incompleteness, i.e. "there are statements that can neither be proven nor falsified", you get "there are statements that can be neither feasibly proven nor falsified" -- this is a direct corollary of the hierarchy theorems -- and the problem remains the same. The only question is whether you're willing to admit infinity (or what kinds of infinity you're willing to admit) as a convenience, or as an approximation of large finite quantities. But choosing not to admit infinity doesn't really make anything simpler (on the contrary, things may get more tedious).

Re:The Axiom of Choice Is Wrong (2007) by fmap on Sunday February 05, 2017 @06:19PM (#13575334)
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.

Re:The Axiom of Choice Is Wrong (2007) by amelius on Sunday February 05, 2017 @05:07PM (#13574944)
Wikipedia ([1]) describes some ways around Godel's incompleteness theorem.

[1] https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_...

Re:The Axiom of Choice Is Wrong (2007) by caf on Sunday February 05, 2017 @06:27PM (#13575367)
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?