What is the Axiom of Choice?
jaydaigle.net
jaydaigle.net
> As there are infinitely many sets, instead of going through them manually, you have to find an algorithm [to select an item from each set]. So Person A tells the other player an algorithm to select an element. Then that other player finds a set where the algorithm fails.
> If you, for example say: "Take the smallest element", then I say "One of my sets is all negative integers, it doesn't have a smallest element."
> Then maybe you say: "Take the smallest element, or if it does not have that, take the largest." Then I say "One of my sets is all integers, which has neither". Then maybe you add: "If it has neither, take the element closest to 0 (in case of tie, take the larger one)". Then I say: "What about the set of all integers and all their reciprocals? It doesn't have an element closest to 0 either."
> When Person A gives up and says: "Look, there's some algorithm that does it, right, why do I have to recite it manually?", then that person has taken the Axiom of Choice. If they say "Okay, fine, you win, there's no algorithm you can't find a counterexample to", then that person rejects the Axiom of Choice.
It's Countable Choice, and of course the essence of Countability (why it's our favorite cardinality) is that almost all of our intuition about finite numbers can be correctly applied to countable infinities.
Uncountable Choice (a set for every Real number, a choice from every set) is where thing ago off the rails and ZF looks substantially different from ZFC.
Why would a set of "negative numbers" not have a smallest element?
Negative numbers are also ordered in a number line (-5 is smaller than -2 for example).
They are orderable ... For all x, y in R, either x >= y or x < y.
But R is not bounded (no inf, sup) and therefore has no minimum and no maximum.
Relatedly, every set gets a supremum and an infumum. (The first two must be members of the set. The second two can lie outside the set).
Without the extension, you need to make an exception for unbounded sets with the above rules.
So you can have a set like "all real numbers greater than 0". It doesn't have an obvious first element, even though you can always compare any two numbers and say "this one is less than that one".
There may be a non-obvious first element, i.e. some strategy for picking a first element that applies to all sets. That's the Well-Ordering Principle. Which feels false to most mathematicians, but it's equivalent to the Axiom of Choice, which feels true.
I don't know the proof but there could be no algorithm like that for real numbers.
You're looking at it from a philosophical perspective where people care about whether the axiom is "true" or not. Other approaches to mathematics don't care, because they view its value not in some metaphysical notion of truth but in utility. They might say: this proof requires the axiom of choice and that proof doesn't, without assigning either one any value beyond utility (where utility might be, in some case, just their intellectual edification). I think this is what the article is trying to drive at as well. We can't "accept" or "reject" the axiom of choice based on some philosophical grounds, because those philosophical grounds would need to involve infinities [1], which, themselves, are not philosophical but mathematical. We either choose to use it or not based not on where we come from but on where we want to go.
[1]: The view that mathematical philosophy could be derived from core basic principles outside of mathematics was called Logicism, and was favoured by Bertrand Russell. Unfortunately, mathematical systems without some mathematical (i.e. non-"logical") axioms are quite limited, and almost all of them include at least one mathematical axiom, usually one that is equivalent to the existence of the natural numbers.
Isn’t this a philosophical perspective?
So it is a philosophical perspective…?
So one is not metaphysical because it is a tool to achieve ends?
(Sorry, if I come across as argumentative, I don’t mean to. I’m genuinely just curious.)
Or at least, that's the way I read it. The question of the value of metaphysics is an open one, which easily comes to dominate other questions if allowed to. I think the OP is saying, "I'm going to make a metaphysical commitment, and let other people worry about whether doing so is good metaphysics." (And there's good reason to think that it isn't -- but it's unclear whether that matters, or should matter.)
My apologies, but I think I’ve understood where I misread your comment. Thanks for being patient!
What's an example without any axioms? It doesn't seem like you can do anything without say ∀x: x=x (which I believe is reciprocal identity.)
a = the algorithm
A = set of all selection algorithms
b = any set
def a(x):
while True:
f = a(A) # you have to select an algorithm from the set of selection algorithms
result = f(x)
if result is None:
A = A - f # set of all selection algorithms without f
continue
else:
return result
a(b) #will always return a result or not terminate for any choice of b?
I'm looking at it and such an algorithm is defined in terms of itself (like a factorial, which is legal) and may never terminate (which also legal because an algorithm selecting the smallest number from all sets that only contain positive numbers will never terminate either).
Wait but then if you look at the code it provably will never terminate because A does not shrink as it recurses.
Moreover, you'd probably want to limit the tries to algorithms that terminate. But that brings you into the halting problem.
I think us programmers think in terms of time. But in math there is no time so whether you do things in parallel or procedural is irrelevant. That's why you can discuss infinities in math.
Nope, you don't need the axiom of choice to define the sequence of all algorithms. The axiom of choice allows you to order any arbitrary set, but you don't need it for things you can construct an explicit order for, like the natural numbers. In the case of all algorithms, it's somewhat straightforward to construct the set of all of them. You can construct the sequence of all strings, right? You can construct them as "", "a", "b", "c", ... "y", "z", "aa", "ab", ... "ay", "az", "ba", "bb", ... Now, pick a programming language, like C. Given any valid string, you can determine if it is a valid C program in finite time, and if so you can convert it into a set of instructions to use in the dove-tailing procedure in finite time. Take the list of all strings in the manner described above. For each one interpret it as a C program, or if it's got invalid syntax interpret it as a program that immediately halts. Now you've got an enumerable sequence of algorithms. Since C is Turing complete you'll find every single algorithm in that sequence. There will be a ton of duplicates (for whatever notion of equivalence you want to use) but all the algorithms will be there, and in a well-defined order that you can enumerate through.
No. I'm saying selecting an algorithm out of the set of all algorithms.
I'm not saying defining the set of all algorithms.
Then you don't need to "randomly pick" an algorithm. You just start with the first algorithm in the sequence, and keep going.
That is still random. You are arbitrarily picking an encoding, (English) in this case. Why not a Russian programming language or Chinese? How did you *select* your encoding out of the set of all encodings?
The act of assigning order to an unordered set is arbitrary. ABC order is a made up concept. It's not numerical, it's an arbitrary language and an arbitrary order that's a by product of human culture. Thus invoking this is at it's essence invoking the axiom of choice. You are arbitrarily selecting an algorithm.
You only need the axiom of choice if you need to pick an element out of a set WITHOUT SPECIFYING which one you are picking. And sometimes not even then. For instance, if you want to prove all elements in a set have a certain property, often you will see proofs take the form "pick an element of that set, assume it doesn't have this property, then by X, Y, and Z we have a contradiction, thus all elements have that property". That doesn't involve the axiom of choice at all, even though a straight reading of that statement makes it sounds like we are making a choice. In truth that proof is saying we can do this with every single element of that set, so you aren't really making a "choice". You only need the axiom of choice when you are, say, stating the existence of a function without defining what that function is. For an example of an actual invocation of the axiom of choice, check out the proof sketch in the wikipedia article on Zorn's Lemma: https://en.wikipedia.org/wiki/Zorn%27s_lemma .
You can phrase things like Gödel did. For any encoding of algorithms into natural numbers which is bijective (ignoring invalid syntax), enumerate the algorithms as 0, 1, 2, 3, ... using the bijection, and then run them in parallel by taking steps [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...] The user provides an encoding, without invoking the Axiom of Choice.
I can say arbitrary stuff like the set of all sets with positive numbers but when I say the set of all algorithms written in English and C++ suddenly I'm getting too specific. Where is the line drawn?
Algorithms themselves have no specific order. In order to define enumeration you must first start off by *selecting* which algorithm gets the first enumeration. This is a completely arbitrary choice.
And yes, which particular encoding you decide to use is arbitrary, but the point is that you can enumerate the set of all algorithms, and thus you can select one without needing the axiom of choice.
Try to select an algorithm out of the set of all algorithms without using an encoding. If you must use an encoding, please ensure that it's not a "particular" encoding.
You can't.
The point is all encodings in the known universe are "particular."
Additionally, to even use an encoding you have to *select* and encoding from the set of all encodings.
One way of selecting an algorithm is to select a way to encode the algorithms.
It's easy to see that this is true. You chose an arbitrary example above. Try to do the same without choosing anything arbitrary. You can't.
def a(x):
return a(x)By _assuming_ that program terminates, you are yourself taking the axiom of choice.
If it _does_ terminate, then it's not an axiom anymore it's a proof.
The axiom of choice is an assumption that is neither known to be true or false.
But I'd also add that you can have a choice function that isn't an "algorithm". An algorithm, at least in the sense I'd generally interpret the word, has finitely many instructions and at most countably many steps. If we have uncountably infinitely many uncountably infinite sets, it is possible to have a choice function that can't be described in a finite algorithm.
Like, think about a well-ordering of the reals. If you believe the axiom of choice, then one exists. But you can't tell me what it is, because that would involve handing me infinite amounts of information. And similarly you can't write down an algorithm to produce it, without writing down infinite amounts of data.
No my algorithm above will never terminate. There's a recursive call where the input never shrinks and it won't converge on a base case.
It's equivalent to saying
def f(x):
return f(x)
Basically ketralnis is clarifying context which is sort of lost with my post. There's an axiom and do you believe in the axiom of not?
If the axiom can be proven then it is not an axiom. But a theorem. What I'm doing here is kind of pointless because we know it's an axiom by definition, the question is whether this axiom is valid or not. Attempting to prove the axiom is a a signal that I'm lacking clarity with the logic here.
1. Find any solid object.
2. Divide that object in infinite, dimensionless fragments.
3. Make as many copies as you want with the infinite fragments.
4. Reform the original object with the remaining fragments.
... I still have fragments please help.
Point (2) is fundamentally wrong in a critical way. The whole point of the Banach-Tarski Theorem is that you only have finitely many pieces. Of course these pieces are composed of infinitely many points, but it's a finite number of "pieces".
Others may find it amusing, sense of humour vary widely. Usually I just shrug and move on, but in the essence of this "joke" you've genuinely misrepresented the entire point.
This theorem is often quoted as "mathematically-proven way to deconstruct a sphere and build two identical spheres", but this can't translate to reality in any way, it's an abstract thought exercise. Of course, "mathematically-proven way to deconstruct a sphere and build two identical spheres in your imagination" doesn't sound as cool.
We model spheres as collections of points, and given a collection of points there is a fairly obvious way to model the idea of moving that collection around in a way that reflects moving a physical object. The problem is, given a sphere, we can partition the points into six sets, move those sets around, and recombine them to give us two spheres the same size as the initial one. In a very real sense, in this model we can "cut up" a sphere, then rearrange the pieces to make two spheres. We've doubled our volume.
Clearly this is nonsense, and it shows the limitations of the model. But equally, it tells us something important about the maths we use every day to model buildings, bridges, fluid flow, and more.
All models are wrong, some models are useful. -- George E. P. Box
I would add:
Some things are nonsense, but sometimes the nonsense can tell us useful things about the way the models are wrong.
And the footnote following this statement:
> At the beginning of the 20th century, Bertrand Russell and others found deep contradictions in the naive version of set theory in use at the time, and the ZF axioms were developed to avoid those problems. But we’d rather avoid doing it again.
My understanding is that the “constructive” mathematicians objected strenuously to these proposed foundational “solutions”. It’s starting to look like they may have been on to something, as there is an ongoing effort (since 2013 at least) to recast the foundations in a manner that accommodates both traditional and intuitionistic approaches.
Short anecdote to confirm that this might gain traction: I’m a comp sci PhD student (focus on cryptography) and just yesterday I met with a math professor to ask her to serve on my advising committee. I had some brief run-ins with Homotopy Type Theory (the proposed “new foundations”) and was hoping she might be familiar with it—as it turns out, some of her own students had recently convinced her to start a weekly jam session where they gradually work through the HoTT textbook. She invited me to join them and I eagerly accepted :-)
> If we have infinitely many pairs of shoes we don’t need the axiom of choice, since we can just take the left shoe from each pair; but if we have infinitely many pairs of socks, we do need the axiom of choice.
- Bertrand Russell
So randomness seems like a good fit for "choice" here, no? Or maybe call it ambivalence, or indifference. If the objects are truly unidentifiable, can it possibly matter which one you choose?
As the argument surely goes...
(The first journal he submitted it to rejected the paper with the comment "this is not mathematics, this is theology")
Anyway, I hope they gave him a Ph.D for that comment, lolol.
Oh and yikes, did Hilbert just bring roots of polynomials into the mix?
The axiom of choice is exactly the thing that tells us that we can make "random" choices. The way set theory works is that you have axioms to talk about intuitions of sets. So you might say that such a reasonable intuition is that we can make "make unlimited random choices", but this is exactly the axiom of choice!
It's not about a choice from an infinity but an infinity of choices.
This is my preferred quote about the AOC:
> The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?
Jerry Bona. https://en.wikipedia.org/wiki/Jerry_L._Bona
Can you always pick the center of each universe in a universe of infinite universes ? Any point can be the center, you just need to pick one.
A sphere has a center which is in that sphere but not on the surface (boundary) of the sphere.
A 4-sphere has a center which is in that hypersphere but not in the volume boundary of the hypersphere.
...
It is entirely possible that the universe is a 3s1t shape which is part of the boundary of an NsNt shape, and there is a center to it which is not usefully accessible -- or even discoverable -- from anywhere in the universe.
Still centerless seems like it could carry less baggage and be just as "correct", but IDK.
I mean... they're not in exactly the same position and state at exactly the same time, no? That would seem to distinguish them.
> Or might this imply that the electrons are actually distinguishable in some way? Or maybe I should re-phrase; could each electron actually have some (possibly hidden) identity?
I still don't see what that has to do with the above. The context with and relation to their surroundings seems entirely sufficient to distinguish between electrons, so they're not indistinguishable, even if, in isolation, they are.
I suspect that's key to why the axiom of choice has to be an axiom (and how this may pop up from time-to-time in the realm of computer science problems).
if it does, then "I select one at random." That could be accomplishable without a guarantee that I can tell you how to select (in finite time) the same element I selected.
> The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?
Turns out, it depends which socks you buy - there are makes which are different, and ones which aren't. examples at https://www.quora.com/Is-there-a-left-and-right-sock-in-a-pa... including toe-socks but not limited to them.
I think the article artfully uses a framing of the problem that hides the inherent, inexorable alienness of infinite sets under a familiar-seeming surface just long enough for it to come bursting out in the solution. It's a trick of timing. If your brain lingers on the problem long enough, you realize that the problem itself violates our ordinary intuitions, independent of the solution. The idea of an infinite number of people agreeing on and memorizing representative members of R^N from each equivalence class and then determining the relevant equivalence class by reading an infinite number of real numbers from an infinite number of hats is completely fantastical. How could any solution to this problem not be nuts?
More to the point, if the problem is presented without a bonkers framing that already violates our intuition, is the solution from the Axiom of Choice still counterintuitive? I didn't find it to be so when I first encountered it in class. Maybe the intuitiveness depends entirely on the metaphor used to bring intuition to bear.
Infinity is so weird that it's really hard to agree on what infinity "should" look like. And the axiom of choice only matters in situations where the weirdness of infinity really kicks in.
So yeah, some people look at the whole list of AoC equivalents and think they all seem pretty reasonable. And other people look at the list and think none of them seem that plausible. And a lot of us are split, and find some of the claims obviously true and others obviously false.
One of my goals in this piece was to try to let everyone see both sides of this: why you might find the axiom compelling and why you might find it troubling. And then to offer a pragmatic resolution at the end, which is basically another take on what you just said.
> * If we have one set, we can definitely pick an element from it.
Can we? How?
The point of a set is that it doesn't distinguish between its elements in any way. It's not ordered, there is no special element, etc. So how can you pick one element from a set?
If you pick a total ordering over the elements in the set, then you can easily pick the smallest, or largest. But that's not picking an element from a set, it's picking an element from a specific ordering of that set! You can't do that without coming up with an actual ordering!
Is picking an element from a single finite set something you can build using ZF? Or is it another, less controversial, axiom? What do constructivists think about this? Is there a flavour of mathematics where this axiom is not assumed? What are the consequences of that?
In ZF it's tautological by the axiom of regularity[0]. If you have a non-empty set X, there is an element y such that y ∈ X and X and y are disjoint.
If set theorists do not make that distinction, then that is the answer to my question!
Being precise is especially important in math.
Edit: I think the above might be wrong actually, I haven't had a proper set theory course yet but it looks like "existential instantiation" [0] is what allows you to "choose" the element here (possibly?) but this sits within the logic that proceeds ZF set theory.
Also see [1] for a decent discussion on AOC for finite sets.
[0] https://en.wikipedia.org/wiki/Existential_instantiation [1] https://math.stackexchange.com/questions/132717/do-we-need-t...
There's another answer which talks about the connection to AC:
https://math.stackexchange.com/a/365282/487512
But really, the second answer to the question you posted is the real explanation:
https://math.stackexchange.com/a/132910/487512
Essentially, we're not actually choosing an element from the set. We're defining a new symbol, and saying that it could represent any element in the set. But you can use that symbol pretty much as if it was one particular, but unknown, element of that set.
If I have understood this correctly, then if you "choose" some element a from a set X, and prove some proposition P(a), then you have really proved that for all e in X, P(e).
Since it's just one set and not a collection of sets, you don't need some general rule that will give you a well-defined element from each set in your collection.
Am I missing something?
But what does it mean to pick an element infinitely many times? You have to be very careful about your assumptions there, an inductive proof would only prove you can pick an arbitrarily large number of such elements. To say that you can make a set picking one element each from a infinite collection of sets, even countably infinite, is something you cannot prove inductively. It requires another axiom.
And admitting this axiom suddenly paradoxes like Banach-Tarski are possible.
If so, why can't you do that to fully order any set? Just pick an arbitrary element - that's the smallest one. Now take the original set minus that element, and repeat. Bingo, an ordering!
Maybe you can? Maybe it's only infinite sets where this doesn't work?
You could definitely come up with alternative logical systems to first order logic where "just pick an arbitrary element" is not considered a valid proof strategy, but this would be more an exercise in philosophy and logic than in mathematics. There are good practical reasons for mathematicians to like classical first order logic (such as the fact that Godel's completeness theorem applies to it), so it would be hard to convince most mathematicians to switch to any other logical system. Making classical first order logic weaker makes it unpleasant for the purposes of getting things done for not enough benefit (although intuitionists will fight you over this claim), while trying to make it stronger leads to problems where your logical system needs to magically give you access to truths which are uncomputable in order to be complete ("abstract model theory" tries to make this claim precise).
The trouble is that first order logic doesn't have a built-in concept of "infinity", let alone a rule that says it is valid to "just pick an arbitrary infinite sequence", let alone the full strength of the axiom of choice (which applies even to sets so large that their elements can't be listed via a "sequence"). Such a logical rule can only be added in a logical system which can talk about arbitrary sets or infinite sequences in the first place, which goes beyond first-order logic. So rather than having this rule be a rule of pure logic, the workaround is to add it as a mathematical axiom that applies to the (first order) mathematical theory of sets, which is meant to be a practical approximation to the (ungraspable) "true" collection of rules for "higher order logic".
I suppose, if one had a Turing machine with an oracle for the halting problem, it could produce some elements of this set. And then you could ask, what is the shortest program which generates an element of this set. And then if you had multiple shortest programs, you could order them lexicographically. So that's a way you could pick out a single element in principle, even though it is impossible in practice.
Another example would be the set of numbers that are first-order undefinable. (Meaning, numbers for which there does not exist any sentence in first-order logic which is true only for that number). There is no way using first-order logic to pick out a unique element of that set. But I suppose there is some number which is second-order definable but not first-order definable, and hence we could use a sentence of second order logic to uniquely locate a member of the set of first-order undefinable numbers.
As a generalisation – you can define a set such that you can't pick out any individual member of it using certain resources. But it seems like there is always some way to pick out a unique member of such a set using more resources (a higher Turing degree, higher order logic, etc). Can you define a set so you can't pick out an individual member of it no matter how much resources you use? I think the answer to that is "no".
What is a function: It's a set of tuples where every tuple (x, y) means: x is mapped to y. Of course there must be exactly one tuple for every "x".
(Tuples btw are usually a short notion for {{x}, {x,y}}. They exist always by the axiom of pairing. By the axiom of extensionalty, they fulfill the universal property of pairs, i.e. (x, y) = (z, w) iff x = z and y = w.)
Assume x is a single nonempty set. Picking means: Finding a function {x} -> x. But this is easy: ∃y(yϵx) because x is nonempty, and then we can build our function, which consists just of the single tuple (x, y).
It also works for finite sets of sets since you can do it manually n times, the formula just gets longer.
It's a standard definition that means we can talk about ordered pairs but still ground it in set theory.
OTOH, if we only know the set is non-empty we cannot pick an element from it. Because assume we could. Let P be a truth value and let S={x in {1} | P}. From not not P, prove S is non-empty, so by assumption we can pick an element of it, so it is inhabited. If it is inhabited, then P. We've just proved P from not not P.
https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...
Also submitted as a separate item:
https://news.ycombinator.com/item?id=27855143
Broadly (and as this article explains), AC says that given any collection of non-empty sets, you're allowed to "choose" a set that contains one thing from each of them. In set theory terms, the "product" of non-empty sets is non-empty.
This has some uncomfortable consequences.
Metamath lets you state your axioms, then show that proofs build from their axioms. Each such collection of axioms & proofs is called a "database". There are Metamath databases that build on intuitionistic logic <http://us.metamath.org/ileuni/mmil.html> and New Foundations <http://us.metamath.org/nfeuni/mmnf.html> among others.
The largest Metamath database by far uses ZFC (Zermelo-Fraenkel Set Theory with the Axiom of Choice). That's the Metamath Proof Exporer (MPE) database: <http://us.metamath.org/mpeuni/mmset.html>. But even in that database, it's avoided where possible. Its conventions say, "We prefer proofs that depend on fewer and/or weaker axioms, even if the proofs are longer. In particular, we prefer proofs that do not use the axiom of choice where such proofs can be found. The axiom of choice is widely accepted, and ZFC is the most commonly-accepted fundamental set of axioms for mathematics. However, there have been and still are some lingering controversies about the Axiom of Choice. Therefore, where a proof does not require the axiom of choice, we prefer that proof instead. E.g., our proof of the Schroeder-Bernstein Theorem (sbth) does not use the axiom of choice. In some cases, the weaker axiom of countable choice (ax-cc) or axiom of dependent choice (ax-dc) can be used instead." <http://us.metamath.org/mpeuni/conventions.html>
There is much to say—mathematically, computationally and philosophically—on the axiom of choice and its variants (countable choice, dependent choice) and subtle interactions with other axioms.[1][2][3]
From my experience most mathematicians accept the axiom of choice (or an equivalent statement such as Zorn's lemma[4][5] or Teichmüller-Tukey[6]) because of its pervasiveness and usefulness in many areas of math, such as completeness of first-order logic, existence of a basis of any vector space, showing products of compact topological spaces are compact, and more.
[0] Diaconescu's theorem https://en.wikipedia.org/wiki/Diaconescu%27s_theorem
[1] Exposition of choice, LEM, etc. in Coq http://adam.chlipala.net/cpdt/html/Universes.html
[2] Choice vs. countable choice https://mathoverflow.net/questions/22990/choice-vs-countable...
[3] Martin-Löf on choice https://raw.githubusercontent.com/michaelt/martin-lof/master...
[4] Zorn's lemma https://en.wikipedia.org/wiki/Zorn%27s_lemma
[5] How to use Zorn's lemma https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lem...
[6] Teichmüller–Tukey lemma https://en.wikipedia.org/wiki/Teichm%C3%BCller%E2%80%93Tukey...
EDIT: misread
EDIT: Apologies, misunderstood.
I agree and understand that it's not a matter of "right" or "wrong", but I do find myself looking a bit askance at "proofs" of statements in which a mathematician writes the equivalent of a few kilobytes of proof statements (in a suitable encoding), which has to be paired with an infinite number of unknowable bits, which the mathematician is not only incapable of providing in practice but often incapable of providing even in theory, to be "true". Mathematicians often claim to find the axiom aesthetic; I find it to be quite the contrary. When you look at proofs from an information-theoretic point of view, the Axiom of Choice is literally an infinitely-sized wart on the side of any proof that uses it.
For example, if I were to require "all sets are finite", then the Axiom of Choice is trivial. The Axiom of Constructibility still allows infinite sets (and even uncountable sets), but it's still limited enough that the Axiom of Choice holds.
You can almost think of it as requiring all sets to have source code, and then just alphabetizing the source code in order to pick a set.
When discussing hypothetical FTL technologies, I often like to say that it's no great surprise that if you allow one impossibility (negative mass) it's no surprise that you get another (FTL). Similarly, if you allow an uncountably infinite amount of information to be magicked into your proof, it's no surprising that you may get a confusing result like the Banach-Tarski paradox. From my perspective, the confusing step isn't when you have two spheres where you used to have one, the confusing step is when you made uncountably-infinitely-precise cuts with no ability to produce the cuts in question. I'm not confused by the end result, I'm confused at that step. So to speak. I'm not literally confused, obviously, only my sense of aesthetics is.
While I am naturally much more sympathetic to intuitionistic/constructible mathematics than the general math community is, I won't go so far as to insist it is the only one true math, since I don't think there is such a thing. I just think that from an information theoretic perspective, calling the instantiation of infinite unknowable amounts of information into a proof "aesthetic" is, well, not a term I'd use. I find Axiom of Choice generally gross.
Think about how much information is involved in presenting an infinite collection of sets! When I say even something as simple as "Let x be a real number" I'm already invoking infinitely many bits of information. Things have already gotten weird, you just haven't noticed because we've hidden it.
The axiom of choice is saying something like, okay, we somehow have this infinite pile of information sitting around; now we're allowed to interact with it. And if you don't like that, your problem might be with the infinite amount of information we started with. (Or it might not; yes-choice and no-choice are both totally valid positions.)
But in practice it doesn't matter that much because you never actually do start with infinite amounts of information, and so you don't need an infinite-amounts-of-information processor. But if we have finite amounts of information that we're pretending are infinite to simplify things, we can also process the finite amounts of information and pretend we're processing infinite information.
[1] https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_abso...
> You don’t have to explain how you’re choosing elements. We’ll just assume you can make it work somehow.
Very interesting remark. The way I think about it now after reading your article is: If you prove something with the axiom of choice, all you need to do is provide an ordering to get practical results from it. If you fail to do so, oh well.
That being said, I don't think you need R (the reals) for practical applications, countably infinite sets like IQ (intervals over Q) are enough and the well-ordering rule doesn't seem paradoxical anymore (countably infinite sets can be ordered as there is a bijection to N).
Example: Pi can be approximated arbitrarily close with a lower and upper bound on Q. The functions used to derive the lower and upper bound with arbitrary precision (also a number in Q) are Pi in this sense
Is this even possible? One of the premises in the article. Won't it be infinity backwards for the nth person?
The "..." signifies that there are infinitely many such numbers, so there is no largest natural number but there is a smallest (1 is smallest). In that sense it is infinite in only one direction - written here it is infinite to the right but has an end at the left.
Nothing special happens as you "approach infinity" and in fact that's not a thing you can do. No matter how high you count, you have only have counted finitely many numbers and there are an infinite set more that you have not counted.
I can imagine the common-sense "Of course you can choose one element" assumption breaks down if we add the constraint that you need to in some way be able to have another actor choose the same element. Because for an uncountably-infinite-sized set of uncountably-infinite-sized sets, perhaps there is no way to label individual elements such that if I choose A, someone else can also choose A (how will we know they're the same A?).
(If you think you can make one random choice at a time, you're endorsing the axiom of finite choice, which is just true. Determinism doesn't matter here, but "at the same time" matters a lot.)
As the article notes, these particular infinite families are easy to produce a choice function for: just take the least element of each set. But not all infinite families have enough determined structure for that kind of rule.
If we tried to make it impossible to construct an infinite family of sets, we'd have to disallow relatively reasonable families like the ones I described above. Those are pretty useful, though, so it makes sense to address the problem further downstream.
(I suppose another avenue is to try to isolate the features that make the above families "reasonable" and others unreasonable, so that only reasonable families can be constructed. That seems somewhat fraught, though.)
A good, fairly intuitive example is integration where, I think, it's common to prove convergence using AoC in the multidimensional case.
More or less, you want to integrate a function over, say, a square. We'll do it with a generalization of the Riemann sum by arbitrarily dividing up that square into little squares, measuring the function at one place in each square, multiplying the areas by those measurements, and summing.
Then we take that process to its infinite limit. We have to be smart here, but we end up with an infinite set of contiguous pieces of our original square. Or, an infinite set of sets. We'd like to measure our function once from each of those pieces, so we need to choose one point from each piece. Which is easily dispatched with AoC.
(In 1-dimensional integration, each subdivision of the domain has a total ordering, so you don't necessarily need AoC. Technically my example of a square also has a total ordering, so we could get away with not using AoC, but as you start to twist coordinates in the domain space more and more you can imagine places where seeking out an ordering of the space might be challenging. But no matter, AoC still works!)
0.35578439999999999999...
0.35578440000000000000...
0.35578440000000000000...
0.45578440000000000000...
0.85578440000000000000...
0.35578233333333333333...
There are infinitely many families.
Now suppose that there is a council meeting, and every family needs to send one representative. To do so you need to choose one number from each family, and it's not clear how to do that. I invite you to try to think of a rule that works for all families.
So to choose one number from each family we need the Axiom of Choice.
My question is: why is it problematic only when you have to choose?
I mean, what's wrong with choosing a random element from every set? Why do you need a rule?
Where is the "problem"?
If it's only finitely many sets, finitely many choices, people are usually pretty happy with: "Well, choose one, then another, then another, and in a finite amount of time you'll be done, so that's OK."
If it's countably many sets then many people are happy saying: "Well, choose your first one in an hour, then the next one in 1/2 an hour, then the next in 1/4 of an hour, and so on, and after 2 hours you'll have made all your choices, so that's OK."
But with uncountably many sets neither of those works, and so you need an axiom to tell you that this is a permitted operation.
BTW, it's a separate issue, but in your first line, the part in parentheses does not imply, and is not an explanation of, the first part. These statements:
A: The reals are uncountably infinite;
B: There's an infinite number of real numbers between any two random real numbers.
(To start you off, the second statement is true of the rationals, and of the algebraics, both of which are countable).
I could understand the objection if one objected to the concept of infinity in the first place. Like "infinity is not real therefore any logical statement you make about it is non-sense".
What I don't understand is the mindset that would accept to be presented with an infinite number of sets but then not accept that you can choose an element from each set, because "the procedure will never be done" or something like that.
Similarly defining an infinite collection of sets.
However, if I have an uncountable collection of non-empty sets, sometimes you can tell me how to choose one from each (for example, if I have uncountably many pairs of shoes then you can just say "pick the left one"), but within the axioms of set theory, if all you know is that there are infinitely many non-empty sets, the ZF axioms don't allow you to declare that there is a function which when given one of the sets, returns to you an element from that set.
Your statements seem to be saying "If you accept that there are infinite sets then you must accept that the Axiom of Choice is 'True'."
That turns out not to be the case. There are sets of axioms that result in systems that have infinite sets but in which the Axiom of Choice is not 'True'.
Perhaps I've mis-characterised your position.
The problem with this axiom is that it can't be formally proven from ZF axioms. But there are a lot of other natural things that can't be proven in ZF. For example, the consistency of ZF can't be proven in ZF due to Godel's incompleteness.
Steve Wolfram should grow some balls and say he doesn’t believe it either.
Particularly I think those "real" numbers are phony compared to the integers and rationals. (At least the latter have names)
For example, if you have the real speed of a car at every point in time as well as the position, then nominally, in infinite world, the speed is just the derivative of the position curve.
But if you are in finite world, then the derivative curve in infinite world is the limit of the speed curve (and note that limit does not mean upper bound).. it just is a useful tool for reasoning what will happen if you take a more fine grained set of measurements.
For some fineness of measurement, there will be a point at which your observed speed curve is always within epsilon of the ideal one.
Good article