The Axiom of Choice Is Wrong (2007)
cornellmath.wordpress.com
cornellmath.wordpress.com
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.
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.
EDIT: see also https://ir.canterbury.ac.nz/bitstream/handle/10092/5626/1263...
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?
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.
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.
Citation needed. People keep saying things like this ("real space isn't infinite" or "real spacetime must be discrete") but never show their work.
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.
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
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.
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.
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
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.
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.
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.
Eg for the qubit, the state space is the Bloch sphere, which is continuous.
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
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?
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.
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.
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.
Not being able to write all the rules is a completely different and unrelated thing.
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 ?
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).
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...
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).
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.
[1] https://en.wikipedia.org/wiki/Hilbert's_program#Hilbert.27s_...
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?
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?
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).
[0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...
(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.
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.
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.
[1] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...
[2] http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.h...
the solution to any problem any could ever have
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.If you can write down a problem as a finite string, then the set of all problems must be countable.
Kontsevich and Zagier introduce and develop this concept quite far:
> https://en.wikipedia.org/wiki/Maxim_Kontsevich
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):
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.
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.
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.
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").
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.
Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.
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.
Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?
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.
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.
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)
Is a hammer true or false? I don't know, but it's good for hitting nails.
In general, the infinite hierarchy of infinite sets "exists" because we can define it.
This is trivially true, since there are only countable (finite) expressions and problems.
> why do we need the other uncountables?
You can't do calculus without reals.
http://math.stackexchange.com/questions/1880741/why-cant-cal...
And calculus is pretty important (e.g. for any branch of physics ever).
2^ℵ₀
Which I just managed to encode using a finite number of symbols :)
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.
- 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.
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?
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.
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.
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.
Unless I'm missing something.
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.
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.
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. ;)
Interested to hear others' attempts.
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.
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.
[1] https://en.wikipedia.org/wiki/Second_law_of_thermodynamics
[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
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.
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.
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.
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.
Am I right about this?
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.
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?
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).
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.
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.
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.
No it does not? The axiom of countable choice [0] is a strictly weaker axiom.
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.
Can you expand on this? The Dirac delta function is not a function from R to R for example.
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)).
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.
but it's known that it does not extend!
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.)"
Whereas Euler's may seem pretty tame, the Axiom of Choice is not. That's why some people think it might be wrong.
In this way at least, that axiom is "wrong".
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.