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.
> 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.
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.
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.
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.
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.
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.
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.
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.
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.
> 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 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.
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.
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.
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.
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.
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.
> 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?
> 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.
> 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.
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.
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.
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).
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.
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).
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.
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 ?
> 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).
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...
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).
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.
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?
As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ.
Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities.
* How many natural numbers are there? Countable
* How many rational numbers are there? Countable
* How many numbers are solution to a polynomial? Countable
* How many numbers are the output of any turing machine (including programs that run forever, producing an infinite decimal)? Countable
* How many numbers are the answer to any maths problem anyone can write down (where the problem has at most a countable number of answers)? Countable.
If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have, is countable, why do we need the other uncountables?
This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number
It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).
I recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem.
Yes. An uncountable number are in the Library of Babel.
(actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.)
Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.
The Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language.
However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.
the number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.
One of the great theorems in logic is the Lowenheim-Skolem theorem [1], which says that if a countable first-order model has an infinite model, then there is a countably infinite model. For example, there is a countably infinite model for the theory of reals.
I have heard that Skolem [2] used this theorem as a basis for his belief that uncountable sets can be avoided, and countably infinite sets suffice.
Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist. It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well.
Admittedly it's hard for me to envision a world where notions of countability will ever have real-world uses, but I also consider calling it "a fun maths game" rather reductionist, and frankly, poor taste (especially if you're going to say something like "intrinsic truth or falsity").
Give him three pence, since he must make gain out of what he learns.
Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas):
How many sets of natural numbers are there? An uncountable number.
Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
In this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.
For sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc
One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC
I think the only axiom you need to rethink from ZF is powersets (since I think that's the only axiom that produces uncomputable sets from computable ones (ignoring the AC, briefly)). What you'd replace it with (some sort of one based on comprehension, presumably) I couldn't say though.
Indeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.
I've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)
I tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.
> How many sets of natural numbers are there? An uncountable number.
But, at most countably many of those sets will ever be individually thought about by any human being. So there are only countably many (and maybe more strongly finitely many) subsets which any human being could ever possibly think about, and an uncountable remainder which are unthinkable. In order to do mathematics, do we really need to posit the existence of an uncountable number of objects no human mind will ever be able to individually consider?
> Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
You could introduce a set theory where from a countable set you can only infer the existence of its computable subsets, or its first order definable subsets, or something like that. Not sure why that should feel any less "real" than an uncountable infinity of mathematical objects about which no one will ever individually think.
> But, at most countably many of those sets will ever be individually thought about by any human being.
If your arguments are tied to such physical constraints, then there aren't even countably infinite natural numbers unless the Universe is infinite in space or in time (such that there can be infinite humans or "thinkers").
Better yet, just consider all deduction as "a fun language game," rather than having any intrinsic truth or falsity. If you assume a whole bunch of stuff and the axiom of choice, you can get these interesting things over here. If you assume that same bunch of stuff but not the axiom of choice, you get this other interesting stuff over there.
Which assumptions to use at any given time just depend on what you're trying to do. If I'm trying to count my sheep, I just need enough axioms to get me addition of natural numbers. If I'm trying to model some mechanical trajectory, maybe I ought to grab some reals. Got circles? Adding imaginary numbers to the reals makes that easy, even though imaginary numbers are totally "fake." Using sentences that might not make sense? Maybe avoiding the excluded middle is a good idea.
One of the observations in programming language semantic proofs is that one doesn't need coinduction. Statements can be proven by good old fashion induction, by indexing them with the number of steps in the computation, then proving they hold for any finite number of steps.
I suspect the same technique applies to analysis. We don't need to prove a statement holds for reals with "infininte" number of digits, but merely for all rationals with finite k digits, where k is a parameter of the proof, thus can be arbitrarily large.
- Every real number can be represented as a limit of rational numbers, which are uncountable.
- So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge.
Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence).
You can still work with the remaining set, but formulating and proving theorems, is going to be much harder.
- If integrals over f and g exists, then the integral over f * g does not need to exists.
- E.g. Integrals over bounded regions will not always exists.
- Theorem of Montonic convergence fails
- Function spaces will not be complete (L2).
A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.
My argument aws: The constructible numbers are not "complete". You can always find cauchy sequences of constructible numbers that do not converge to a constructible number.
If you add the requirement that the sequence itself must be constructible things _might_ change. It depends on how you define constructible sequence.
I thought Cantors argument would show that there are uncountable constructible sequences:
- Assume there are countable many C[1], C[2]
- Construct a new one D = C[1][1] + 1, C[2][2] + 1, ...
- D in constructible, hence it's on the list: C[j] = D
- But D[j] =/= C[j][j]
- Contradiction.
This proof is however not correct. The sequence D does not need to be constructible.
Are the computable numbers continuous? If not, is that a problem for analysis? If so, can you construct some computable analogue of continuity which is sufficient?
Nothing wrong with that, it's still a computable number -- I'm not suggesting doing away with all real numbers, just the non-computable ones.
I don't claim to have thought through every detail, but having now gone and done some reading, this seems fine in the world of constructivism, which only requires computable numbers (and therefore only countable infinities of numbers)
> As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity.
Is a hammer true or false? I don't know, but it's good for hitting nails.
Yeah, a hammer is definitely useful, but I think the point he's trying to make is that the notion of uncountable sets isn't very useful outside of things like set theory.
You could have answered all of your questions with "finitely many", because, after all, we can each only perform a finite number of actions in the world.
In general, the infinite hierarchy of infinite sets "exists" because we can define it.
No mathematical object exists exactly in the real world. E.g. you will never see a physically perfect square. The whole point of mathematics is that it's a simplified model of reality that's easier to work with for some purposes, and that's as true of uncountable infinities as it is of anything else in maths.
OP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true.
By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.
I know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.
Oh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.
Yes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.
There are many problems with this puzzle that go against the intuition.
- the number of prisoners is infinite, so they will never finish answering the question. At any point in time, only a finite number of prisoners will be freed.
- a single prisoner must process an infinite amount of information to reach the decision. In fact, by observing only a finite number of hats he cannot possibly choose the answer.
- the number of equivalence classes is uncountable. Not even a countably infinite number of prisoners can possibly have enough time to pick out a single element from every equivalence class.
As soon as you start treating the axiom of choice as a superpower for a conscious being you are in conceptual la la land.
How do I guess the color of my hat if there's an uncountable number of possible colors? Doesn't that mean that communicating the value of that color involves transmitting an infinite amount of informtion?
Quick, tell me your favourite number between 0 and 1.
How did you do that? Weren't there an uncountable number of possible numbers?
Ah, you may say, but I obviously wasn't going to choose one with an infinite information content, so all but countably many possible numbers had probability 0.
Which is true. But in fact it's true that whenever you have a probability measure on an uncountable space then all but countably many elements have probability 0, so that escape clause applies equally well to the hat colours.
When we think of numbers between 0 and 1 we aren't thinking of Real numbers.
Name a transcendental number between 0 and 1. Which one springs to mind? Maybe, if you're lucky you can come up with some famous transcendental number and "scale" it to lie within the interval (pi over ten!).
The numbers we live with are a finite dimensional vector field over a bounded subset of algebraics - not even countable.
But the axiom of choice applies to all sets, not just ones that you can easily choose a number from. For instance, what is your favorite non-computable number between 0 and 1?
I think the intuition that such infinite games make sense requires the axiom of determinacy to be well founded. The axiom of determinacy has been known to contradict the axiom of choice since the early 1960s (i.e. it is inconsistent to have both the axiom of choice and the axiom of determinacy).
If we actually define a specific finite number N in the equivalence relation "two such sequences [are] ‘equivalent’ if they are equal after [N] entries", no one is in a position to take advantage of the equivalence classes.
Either their position <= N, in which case the equivalence class does not specify the color of their hat...
Or their position > N, in which case they cannot see the entire sequence after N entries and thus cannot determine which equivalence class the sequence belongs to.
N is not fixed, so we're always in case (i), position ≤ N.
The equivalence class does indeed not specify the colour of the hat. The invocation of the Axiom of Choice was used to tell the prisoner what to guess in that equivalence class, although there is no guarantee that it is correct in their specific case.
How does a prisoner know where they are in the pre-chosen sequence?
Seeing only an infinite number of hats ahead, which match some pre-chosen sequence after an unspecified finite number of hats, how do they know if they are in position, 1, .... i-1, i, i+1, etc?
I mean, even if you know which equivalence class the sequence belongs to, you won't be able to guess at the color of your own hat without knowing your position.
What an interesting thought experiment. Lying in bed last night, the best I could come up with (before seeing the optimal solution this morning) was an average of 83 with a minimum of 66.
The prisoners agree that every third prisoner, beginning with the first, uses "white" to convey that the subsequent two prisoners are wearing the same color and "black" to convey different colors. Since the second prisoner in each triple knows the color of the third, he can deduce his own color, leaving the third prisoner to also deduce his own color. And of course there's a 50/50 chance the sacrificial first prisoner in the triple still gets out. I suppose this could be improved upon by later prisoners having a longer memory, but I've already seen the optimal solution. ;)
The axiom of choice is used to demonstrate the existence of something, in this case a perfect strategy.
However, if said strategy's implementation requires actual infinities, eg each prisoner having an infinite memory, then that is why you find it intuitively objectionable.
It is useful here to think of computer algorithms and not just math. While mathematical arguments have no problem supposing infinite amounts of actors, the next question is whether each actor can have infinite memory.
In mathematics, infinity can be thought of as a property of a set. It can also be thought of as some limit of an infinite sequence of operations on sets, which is a statement that is simultaneously true about each member of that sequence.
This is useful because it can tie constructions we observe in the real world into patterns that approximate and converge to the limit of this infinite sequence. And then the question is how the computational complexity grows.
So in your example here, each FINITE set of prisoners can't coordinate a strategy. So there is no "approaching a limit" - the thing only starts working with an infinite set of prisoners, each of whom has infinite memory etc. And that is why you get your intuition alarm bells go off :)
But it is even more than that. Your construction requires each prisoner to use the axiom of choice in order to take an action based on the NAME of the chosen member which is used to demonstrate the existence of a sequence of actions that satisfies a certain property. However, when the axiom of choice is used normally, it is not used to actually NAME the chosen element, but merely work with it like a black box. By NAME, I mean an id that distinguishes it from all other elementa, and lets you pick it out and examine is properties THAT ARE DIFFERENT than all other elements in that set.
In other words, Sure, you can assume that the chosen "representative" sequence has the same property as any other in the equivalence class -- namely that all but finitely many terms are equal. BUT the part where you "cheat" is having the prisoner "find out" more than that about the representative sequence, in particular its initial values up to an arbitrary depth.
The axiom of choice always seemed intuitively wrong to me. You can't just take a set and arbitrarily pick something out of it! Making a choice requires information, and you can't pluck information out of thin air at whim; applying the axiom amounts to creating information out of nothing.
I suppose this is because i'm not a mathematician, but have a natural sciences background. In the physical universe, memorably, "the law that entropy always increases holds, I think, the supreme position among the laws of Nature" [1], and so we do not accept the mathematicians' fake information.
More specifically related to choice from a set, Curie's principle that "when certain causes produce certain effects, it is the elements of symmetry of the causes that may be found in the effects produced" [2] forbids something uniform from becoming arbitrarily non-uniform; whenever that appears to happen, there must be some hidden cause which already carries that non-uniformity.
[2] https://hal.archives-ouvertes.fr/jpa-00239814 - "Enfin, lorsque certaines causes produisent certains effets, les éléments de symétrie des causes doivent se retrouver dans les effets produits."; please excuse the not-so-literal translation
The axiom isn't exactly about being able to pick an arbitrary element out of an arbitrary set. It says that if you have a collection of nonempty sets, then there is a function f from the collection X of sets to the union of the collection of sets, with f(A) an element of A, for A in X. To say each A is nonempty is kind of already saying that we can pick out an element from each set. The axiom just goes on to say that there is an actual function which does the picking out.
I think of it as taking the meta-level (a statement that every set in a collection of sets is nonempty) to the set level (there exists a function which picks out one of those elements for each set in the collection).
The axiom doesn't actually say what the function is. It just says that the set of functions with the given picking-out property is nonempty.
A similar statement to the axiom is that every sequence of nonempty sets A_1,A_2,... has at least one sequence a_1,a_2,... with a_i in A_i.
A consequence of the axiom of choice is that every vector space has at least one basis. I'm not sure whether every vector space having a basis is equivalent to the axiom of choice, though.
> You can't just take a set and arbitrarily pick something out of it! Making a choice requires information
True, but how can you "have a set", i.e. reference a set in any way, without having information about that set? There seems to be a requirement of some bare minimum of information enough to specify the set, and so enough to pick out a member of the set.
Having enough information to specify the set isn't enough to pick out one particular member.
For example, if i say "the colours teal, maroon, and taupe", you have enough information to know what's in the set, but no extra information that would let you pick one element out of it.
Well the issue is whether its possible in principle to define such a function for all possible sets. But if you can enumerate the elements of the set, such a function is simply to pick the first element.
So the issue is how much information is necessary to guarantee that its possible in principle to construct such a function. It should be clear that enough information to enumerate each set is enough to create a decision function. The remaining question seems to be whether one can specify a countable set of countable sets without specifying enough info about each member set to enumerate the set's members. It seems trivial that a set with countable elements is enumerable, but I might be missing some subtlety.
I'd assume that even if in every case the number of incorrect guesses is finite, the expected number of people that fail to guess their color is infinite.
Im not sure what you mean by "expected number." Do you mean if you try to guess how many inmates the warden has managed to guarantee will fail? Per the article, the warden can guarantee that an "arbitrarily large finite number of them" will fail. But it's still always finite despite being unbounded. If you want to predict a lower bound on the number of failures the warden has guaranteed, you just have to guess a larger natural number than the warden. :)
Interesting observation! Yes, I think reduced to its essence, it boils down to: the expected value of "a finite number" is infinity. Which is strange in itself.
So you end up with a sequence that converges to 100%, but that convergence never starts, but it certainly happens eventually.
I guess a similar, less verbose thing would be "pick a random rational in (0, 1)". In decimal representation it'll repeat after "a finite number" of random digits, but "a finite number" again is expected to be infinity. So is a random rational really rational? Someone more educated on set theory will have to comment.
If you take any finite subset of N prisoners, it's easy to see that they won't do better than chance, so the expectation is for N/2 of them to guess wrongly. Since N can be arbitrarily large, your intuition is correct.
I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it.
Two things that have bugged me for a while:
- why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets?
- There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?
The axiom of choice is about making an infinite number of arbitrary choices simultaneously. If you can specify some rule, this rule is just one choice. Finitely many choices are always fine and don't need the axiom of choice.
If you have a finite set, you can number its elements and make rules by saying "let's take the element with the smallest number having this or that property", so you don't need the axiom of choice when dealing with finite sets.
The point of Russell's shoes versus socks analogy is that shoes are distinguishable while socks aren't:
To choose one shoe from each of an infinite set of pairs of shoes, you can always choose the left shoe, or specify some pattern (so you don't need the axiom of choice), whereas when choosing socks, you have to make an arbitrary choice to select one from each pair (so you do need the axiom of choice).
The main problem is taking a statement about a set ("for every A in X, A is nonempty") to the existence of a set ("there is a function f [which in ZFC is considered to be a set] such that for all A in X, f(A) is in A").
If you are able to create a statement P(A,a) that for every A in X is true for exactly one a in A, then it follows from the axiom of replacement that there is such a choice function. The axiom of choice seems to say that it suffices to make a statement P(A,a) that for every A in X is true for at least one a in A.
The axiom of replacement helps actually construct such a choice function, whereas the axiom of choice just asserts one ought to exist since "at least one" seems good enough.
To use the axiom of replacement, you have to use some structure for A. For instance, with the finite set example, it might be that each A is not just a set, but a set which is in bijective correspondence with a natural number, where there is a distinguished bijection. Then, you could just say that P(A,a) is true exactly when a is the image of 0 under the bijection.
If you're interested in the Axiom of Choice, Godel, finitism, pseudo-randomness, complexity, information, and other foundational topics, check out the indie film "Digital Physics" on iTunes, Amazon, or Vimeo. Free packs of trading cards (with gum!) are available too! Check the website.
This problem has exactly the wrong setup for using th the axiom of choice:
First, the axiom of choice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. So the author is using something stronger than the axiom of choice to arrive at his paradox.
Second, if you actually are in a situation where you have to choose from a countably infinite number of sets, you only need the axiom of choice if there is no selection rule for choosing an element available. In this case there is a rule you can use, namely: select the sequence in which the "finite prefix" is all zeros.
[0]: the number of equivalence classes is uncountable because there is a 1:1 relation between the equivelance class and an the infinite sequence that is common to all the sequences in the equivalence class once theirs uncommon prefixes have been truncated.
> the axiom of choice requires that you have a countable number of sets that you are choosing elements from
You're referring to the "axiom of countable choice", which is a different axiom. The Wikipedia entry for the axiom of choice makes it clear that the number of sets can be uncountable.
> select the sequence in which the "finite prefix" is all zeros
This doesn't really make sense as a selection rule. The size of the prefix can vary between pairs of members from the same equivalence class.
> First, the axiom of voice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0].
No it does not? The axiom of countable choice [0] is a strictly weaker axiom.
The axiom of choice applies to index sets of arbitrary size. Indeed there is an axiom of countable choice for those who don't like the axiom of choice.
Infinities aren't real, so you shouldn't be surprised if unrealistic things happen when you invoke infinities. That you can duplicate a sphere by cutting it into a finite number of pieces and reassembling it is a "fact" in the same sense as "Luke Skywalker destroyed the Death Star". It might be interesting and culturally important, but it's talking about fictional entities. Both spheres and arbitrarily detailed pieces of spheres only exist in the imaginations of mathematicians. The Axiom of Choice is obviously true, and the fact that it lets you invent weird sounding stories from weird components is no evidence against it. Don't confuse mathematical tools with reality.
Mathematics is formalised is to avoid this sort of philosophizing.
I used to think, for example, that the dirac delta function was mathematical fiction - a mathematical "hack". But then in an engineering control systems class, we did an experiment where we used a step function to approximate a dirac delta function. I could see the results both on the computer screen and in physical reality through a mass-spring-damper system. From that moment on I saw the dirac delta function in the same way that I see cosine/sine: The reason it works in math is because it has a basis in physical reality.
The lesson to be learned here, is that you don't know in advance whether something is obvious or not. To me, it doesn't make sense to decide whether the axiom of choice can be justified by looking at the axiom itself. You have to look at where it's used and required, and whether the proofs convey something that matches your physical intuition.
You need to draw a line between mathematical entities that have "a basis in physical reality" or not. For most people, performing an infinite computation is what puts the axiom of choice firmly on the fiction side, as an impossible procedure, regardless of the application and the outcome.
The Dirac delta function is a mathematical fiction. It doesn't look weird in your case because you didn't mix it with any other weird mathematical fictions. But maybe somebody could invent a system that violated conservation of energy by using Dirac deltas. That wouldn't mean the Dirac delta is a bad fiction, because if you actually tried to build it using your step function approximation it wouldn't work.
Treating it as a function is the fiction (and the reason is probably that the average college freshman doesn't know what a distribution is). But it's "enough" like a function that unless you look too closely, no real problems arise from glossing over the function/distribution distinction.
You're right, but what I should have emphasized is that if you accept that cos/sin are based in physical reality because they model a circle, then you have to have just as much faith in the dirac delta.
Cos/sin are infinitely precise, and can't be reduced to algebra (as opposed to calculus/analysis). This in itself is an idealisation, a fiction.Sin/cos seem natural because they model the ideal unit circle, while the dirac delta is natural because it models an ideal impulse. The latter seems more abstract than the former because we all have been exposed to unit circles, but usually we are not exposed to unit impulses.
You can apply a step function to a mass-spring-damper system, then observer the response. Thereafter, you can make the step function narrower but taller and observer the response. As you continue this process, the response approaches something simple. Maybe this way of thinking about the dirac delta in obvious to everyone, but to me it was a major breakthrough because I couldn't imagine how something infinitely tall and infinitely narrow could model anything in the real world.
So my ultimate takeaway message is that cos/sin are to an n-gon what the dirac delta is to a step function, and that they are just as "real" as one another. Alternately, the dirac delta doesn't work for "symbolic" or algebraic reasons. It's an idealisation of reality, not an abstraction _away_ from reality for the sake of convenience (e.g. how we sometimes artificiallyl define 0^0 (zero to the zero) to be 1 in some cases or 0 in other cases)).
I was under the impression that we were talking about mathematics and not physical reality.
In mathematics, cos/sin are just functions cos:R -> R and sin:R -> R. As far as functions go, Dirac delta is kind of a fiction because we don't have a function δ: R -> R. That's why I think that your initial characterization was correct.
Of course if we define it with distribution or measure then we don't have this issue.
> Maybe this way of thinking about the dirac delta in obvious to everyone, but to me it was a major breakthrough because I couldn't imagine how something infinitely tall and infinitely narrow could model anything in the real world.
By the way, if you're looking for intuition on the Dirac delta I think a good way to think of it is just the identity element under convolution. Equivalently, you can think of it as a thing whose Fourier transform is 1.
There are a small number of people who think it's obviously false! (I'm not one of them). And a larger number who think it's not obviously true nor obviously false.
There's the old joke that the axiom of choice is obviously true, the well-ordering theorem is obviously false, and Zorn's lemma is too complicated to say.
"The GEODE" in GPS navigation is at least a culturally significant fiction. Of course, it's obviously not very infinite. But it's something very much like a sphere that also happens to have significant practical import.
So what bothered the author was the axiom of choice and not the part where a prisoner with a finite brain needs to memorize an infinite amount of information and then perform a computation on infinite information to compute the equivalence class? For this strategy to work you must assume that the prisoners are capable of carrying out noncomputable computations, too. That's the more problematic assumption.
In the comments to the linked article there's a nice explanation by Terry Tao of why this is not so spectacular, in the sense that our intuition with probabilities here relies on Fubini's theorem, which in this case do not apply due to measure theoretic obstacles. But, again, our intuition of probability fails with much easier examples.
Here follows Terence Tao's comment (refer to the original to have proper rendering of math symbols):
"This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.
Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above.
If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space {\Bbb Z}_2^{\Bbb N}), and one uses the strategy coming from the axiom of choice, then the event E_j that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that E_j and its translate E_j + e_j partition {\Bbb Z}_2^{\Bbb N} where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem – if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here.
There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group \lim_{n \to \infty} {\Bbb Z}_2^n is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)"
An axiom is simply a statement that is defined as being true. Often times on grounds of being self-evident. For example, one of Euler's axioms is "Things that are equal to the same thing are also equal to one another".
Whereas Euler's may seem pretty tame, the Axiom of Choice is not. That's why some people think it might be wrong.
Suppose, I choose "This sentence is false" as an axiom. having it as an axiom allows me to reason from its content that it is false and thus I have a contradiction.
But the Axiom of Choice doesn't lead to contradictions (unless Zermelo Fraenkel set theory itself contains contradictions). The Axiom of Choice just leads to some non-intuitive results.
If prisonners follow the last strategy, the dude number 0 as a probability of finding his hat of 50% and the dude number 1 000 000 50%. Why? because nobody knows how many times they will lose. Those who are sure to win are those close to infinity... This have nothing to do with Axiom of Choice. But only because almost all the mass of your distribution is near infinty. With or without Axiom of Choice this things exist.
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.