> 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.
> ... then that person rejects the Axiom of Choice.
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.
It is a perspective in the philosophy of mathematics that rejects the idea that all of mathematics is necessarily anchored in philosophical truths beyond itself.
Of course. I think you may have misread my original comment, which compared two philosophical perspectives on mathematics, one philosophical perspective that views mathematics as an expression of some truth beyond mathematics, and another philosophical perspective that sees mathematics as a tool to achieve some ends.
It is a metaphysical statement about whether metaphysics is important in this instant, rather than being dispensed with in favor of something useful. It's picking a particular metaphysics rather than being bogged down in the meta-metaphysical question of the necessity of metaphysics.
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.)
For some reason you keep skipping the qualifiers in what I write. It does not say "some metaphysical notion" but "some metaphysical notion of truth". In other words, what matters isn't whether an axiom is "true" or not in some way that is external to mathematics, but what use could be made of that axiom. You did the same above; I didn't write "from a philosophical perspective" but "from a philosophical perspective where ..."
I think Russell would consider that a logical axiom, and it commonly is an axiom of predicate logic with equality. BTW, by "logic", he didn't mean just a specific set of familiar axioms, but any axiom which could be considered "obviously true" and didn't involve numbers specifically. https://en.wikipedia.org/wiki/Logicism
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.
Can't you get countable choice with zf? Countable means there is a bijection to the naturals, so you can always pick the element that corresponds with 0.
The algorithm that executes an element from the set of all algorithms one at a time until an algorithm succeeds to select an element from a set will work on any set and itself?
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?
Obviously there's problems with this because I'm not a mathematician and I'm just making stuff up off the top of my head. But would any one who's an expert care to explain what's the issue with the above?
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.
You can run a countably infinite sequence of algorithms in parallel and stop when one of them terminates without running into the halting problem. Say you have a set of algorithms, numbered 1, 2, 3, ... and each algorithm consists of a sequence of instructions (with jumps and gotos), where each instruction takes a finite amount of time to run. The algorithm is as follows: run the first instruction for algorithm 1, then the next instruction for algorithm 1, then the instruction for algorithm 2, then 1 again, then 2, then 3, then 1, 2, 3, and 4, and you can see the pattern now. If any of them reaches the halt instruction halt. Even if all but one of these algorithms runs forever, you'll still eventually halt when that one algorithm completes. I believe this approach is called dove tailing
Can you iterate through a set without * selection *? I'm confused about this part. It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.
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.
> It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.
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.
As my retort to that common mentioned, he is wrong.
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.
Gödel worried about this, and one of the lemmas leading up to their First Incompleteness theorem is that the encoding doesn't matter, as long as it's a bijection on valid algorithms. (Numbers which code for invalid algorithms, perhaps due to syntax errors, can be ignored.) Gödel also was the one who showed that such encodings are possible and useful in the first place, so the problem of arbitrary encodings started and ended with him.
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 think you're misunderstanding the axiom of choice, focusing too much on the literal word "choice". Sure, that ABC order is arbitrary, but so are most mathematical constructions! How did I "select" that encoding? By defining it! By your definition of the axiom of choice, literally defining any set at all (besides the null set and the set of natural numbers, which are defined in their own axioms) would require invoking the axiom of choice.
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 .
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?
Your assuming all algorithms are defined in terms of English that's how you can order them alphabetically. English is an arbitrary language that comes from human culture. Same with a programming language. You are defining a set in terms of concepts that are cultural.
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.
No, I'm not assuming any particular encoding of an algorithm. I'm just assuming by "algorithm" you mean a computable function, and we know there are only countably many computable functions. This is not a cultural notion.
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.
Your own example used the word "alphabetical." So your example is false because it uses a "particular" encoding.
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.
Yes, I chose one arbitrary method of enumeration. That’s not important to the point, which is that algorithms are enumerable and thus you don’t need the axiom of choice to select one out of the set of all algorithms.
ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.
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.
> ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.
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)
which is a pointless (but true) statement. The whole thing is distracting everyone.
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.
I assume you're joking, but in case anyone thinks your description is accurate, it's wrong in a significant way.
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.
I tried to joke about how real objects don't have an infinite number of surface points.
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.
For anyone still following, the theorem is perhaps best described like this:
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.
For (any subset of)rational numbers there exist many simple algorithms to form an ordering. eg. Take the number is reduced for `(+/-)a/b`. A number is smaller if its `a+b` is smaller. In case of tie number is smaller if its `a` is smaller. Even in case of tie positive number is smaller.
I don't know the proof but there could be no algorithm like that for real numbers.
This makes sense. I read the set being "all negative numbers" in the sense of a set of numbers all of which are negative, not in the sense "the set that has every negative number".
The set of positive integers starts {1, 2, 3, …} and there are no positive integers smaller than 1. On the other hand the set of positive real numbers has no smallest element, since for any positive real number x, the number x/2 is smaller and still a positive real. It’s not that the reals are unorderable (they are most certainly ordered), it’s that certain subsets of the reals do not necessarily contain a minimum/maximum.
It's not just about ordering, but well-ordering. Which says not just that you can put them in order, but that you can put them in order with a first element (one that's always less than all of the others).
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.
How does it contradict that? The set of negative integers does not have a least element, and neither does the set of negative reals. (But the former does have a greatest element (–1) while the latter doesn’t have that, either.)
> Similarly, if we could prove the axiom of choice from the ZF axioms, we would have to either accept it as true, or completely rework all the foundations of math.
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?
> So randomness seems like a good fit for "choice" here, no?
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.
The original statement of the axiom I heard was "it's possible to make an infinite number of arbitrary choices" - I think that's a good word for what you're getting at. Of course it doesn't matter which you choose - the axiom doesn't tell you anything about which you can choose - but whether you can choose at all is important. E.g. Hilbert's basis theorem relies on the idea that given an infinite-dimensional space you can always "start somewhere" - it doesn't matter specifically where, but it matters that you can pick a specific point in the space to start from.
(The first journal he submitted it to rejected the paper with the comment "this is not mathematics, this is theology")
I have never considered that there might not be a distinction, it always seems to me that the heels are different at least. Feet are different, shoes are different, so why would socks not also be shaped for the feet and mirrored left/right in the same way?
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'm sorry if this is a stupid question... but what on earth is the center of the universe? Must there even be such a concept? If the universe is truly infinite, I would think that implies it can be both expanding and centerless at the same time.
A circle has a center which is a point in that circle such that the distance(s) from the center to every point on the boundary of the circle is the same. The center is within the space of the circle but not on the boundary.
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.
I'm not really qualified to go into this, but maybe read a little bit about the Pauli-Exclusion Principle works. I get the feeling that might be illuminating.
> > Atoms are able to select which indistinguishable electrons will fill the lowest energy orbitals.
> 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.
It can definitely matter---if I mutate one of the socks and the mutation doesn't show up on the other, I've got a problem if I'm assuming equivalence is equality.
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).
Something I'm unclear on is whether the axiom of choice implies determinism.
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.
I have always thought that Mr Russell is wrong with that cheeky quote. With the socks you also dont need the AOC. Why? because if you have a pair of identical socks (I think that was what Russell had in mind) then effectively you have a set of cardinality 1.If the socks are different, choose the lightest, if there is a tie between them choose the longest, and so on,if for all the tests the socks are tied declare them the same and back to point 1.
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?
The article leans pretty hard on the hat problem to show that the Axiom of Choice has intuitively unacceptable consequences, but I don't see why the solution is so "ridiculous," as they put it. Here's one "intuitive" way of looking at the problem: every person in the line sees an infinite number of hats in front of them, but not the finite number behind them. Intuitively, they see 100% of the information in the problem. The amount of information each of them can see is infinite, and the amount they can't see is finite. Is it so strange then that they only make a finite number of wrong guesses, and an infinite number of correct ones?
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.
I'd agree with this entirely, honestly. (Including the sleight-of-hand I'm engaging in to make things seem exactly the right amount of weird; see footnote 14.)
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.
> So here are a few things that don’t cause controversy:
> * 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?
All formulas and statements are expressed in first-order logic. It has no such phrase as "pick". But picking (in the axiom of choice) means: Finding a function that maps every set to an element of this set.
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.
A tuple (ordered pair commonly called) is `(x,y)`. The standard set theory definition underpinning this is that `(x,y)` is shorthand for the set of two elements `{ {x}, {x, y} }`. Where the "first coordinate" is the set with one element, and the "second coordinate" is the element in the set with two items that is not in the set with one item.
It's a standard definition that means we can talk about ordered pairs but still ground it in set theory.
I think the commenter means that just because you know an element with a certain property is in the set, we can't conclude that there is a way to "choose" such an element. All we know is there exists at least one of these elements, there could be one (in which case we have a choice function that is well defined, choose the one element that satisfies the property) or there could be infinitely many such elements and we're stuck back at the beginning to construct a choice function.
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.
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).
I mean that you can write a function (with a precise definition!) which, applied a set, evaluates to an element of that set. This function must work for any set, without any further information.
I know next to nothing about set theory, but. If you have a single set, you must know its elements or some rule that defines its elements. You can then just pick an arbitrary element that is part of the set at will and let that be your choice.
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.
Let me give a more concrete example. Take the set of uncomputable real numbers. You can write out a formal definition of that set, you can prove that it is infinite and uncountable. But you can't produce any element of it. So you can't actually pick an arbitrary element of it, since you can't know what any of the elements are. Is there even any general rule you can use to pick out a single element? – you can't pick the smallest or largest element, since for every element there will be a smaller or larger one; nor can you pick the element closest to zero, since for every element there will be one closer to zero, and zero itself is not an element.
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".
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.
But how do you pick that one element? Remember, a set does not distinguish between its elements. So if you're going to pick one, you need to introduce some method to do that. Do mathematicians consider "just pick an arbitrary element" sufficient?
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?
Mathematicians do consider "just pick an arbitrary element" sufficient. This is baked into the system of "first order logic" - the standard use of existential quantifiers in logic allows for proofs that make any finite number of arbitrary choices, but the proof gets longer as the number of arbitrary choices increases (so a straightforward attempt to prove that you could make an infinite sequence of arbitrary choices, in first order logic, would lead to an infinitely long proof). The first order logical system behind modern mathematics is both powerful, and limited, in this very particular strange way.
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".
The example of equivalence classes of sequences from the article (in the problem with hats) is very demonstrative. If I give you a class somehow – how are you gonna pick an element from it?
Constructively, a proof that a set is inhabited is exactly an element of that set, so if we know the set is inhabited we can just pick that element.
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.
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.
It's interesting to look at how people have handled the axiom of choice in Metamath, since the axiom of choice has long had some controversy.
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>
Somewhat not well known among all mathematical circles, but Diaconescu's theorem states that the law of the excluded middle follows from the axiom of choice[0]. This means if you wish to work in constructive mathematics (which has great overlap with computer science), not only you must not take LEM as given but also not take choice as given.
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.
Unsurprisingly, I'm biased in the direction of the Computer Science flavor of mathematics, which leads me to say: Of course the Axiom of Choice is useful. Why wouldn't an axiom that allows you to wave your hand and produce infinite amounts of information that you have no mechanism to produce any of be useful? Of course it's useful to invoke infinite amounts of information from thin air. Indeed, uncountably infinite amounts of information, or any aleph-X you please amounts of information.
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.
This isn't necessarily true; you can also limit which sets are valid sets in a way that guarantees that choosing an element from these sets is well defined. For example, the Axiom of Constructibility basically limits which sets exist, in a way that allows you to always use the Axiom of Choice because your sets have a specific fine grained structure you can use to well-order them.
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.
Yes, it's true that you can use the Axiom of Choice in ways that don't invoke infinite information, and yes, those would be OK with me from an aesthetic point of view. (Again let me emphasize my complaint here is not that it is "invalid" but that I find it very unaesthetic, contra many conventional mathematicians.) But things like the Banach-Tarski paradox definitely require infinite amounts of information (uncountable infinite in this case, I believe) with, as far as I know, no mechanism for producing it. As far as I know, it's just an existence proof.
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.
My take on this is that the axiom of choice allows you to produce infinite amounts of information, if and only if you start with infinite amounts of input.
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.
Confused about this. Isn't the comp-sci perspective to use the effective topos and computable partial functions? In that case, LEM fails and so must AOC; instead, we have Markov's Principle.
I mean a computer science perspective on the Axiom of Choice itself.
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.
Is the existence of basis in every vector space really useful? I think in analysis, people mostly work with Schauder basis rather than Hamel basis. I am not aware of any important result that uses the existence of Hamel basis in an infinite-dimensional vector space. This is not a criticism about your comment, but an honest question.
I am not a fan of the axiom of choice, and open-minded about truth values beyond true and false. So I'm really curious about the progress of constructive mathematics, regarding proving known results with non-ZNF axioms, and maybe establishing some more "intuitively satisfying" (whatever that may mean) results where ZNF gives subjectively bogus results like Banach-Tarski?
A lot of people blame Banach-Tarski on the axiom of choice. I disagree. I think it's in essence just a variant of the Hilbert hotel, with the axiom of choice merely serving as part of the machinery for this manifestation. In other words, it's just a counterintuitive but true consequence of the nature of infinity. As such, I think any mathematical system that acknowledges infinity, is going to have such counterintuitive results.
Constructive mathematics by it's nature does not use LEM. The idea is that proof of existance must be done by construction of the object in question. LEM implies DNE, which means existance can be shown by showing non-existance is not the case.
Veritasium describes a similar situation (not the AOC); a hotel that has infinite rooms and what happens when an infinite number of buses each with an infinite number of guests pulls up.
To build upon the "Just relax" section: by Shoenfield's absoluteness theorem[1], if ZFC proves some Sigma^1_3 statement, then ZF also proves it. In particular, the Axiom of Choice has no arithmetic consequences, and thus has no effect on number theory, nor what you are able to prove about the correctness of any particular algorithm, etc.
This is super cool and I wish I'd known about it before writing the piece; I'd have been comfortable being a lot more muscular in the conclusion. This seems like it makes precise my suggestion that the axiom of choice only matters for aggressively infinite and unphysical statements.
> 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
> Let’s assume there is a first person in the line, so it’s not infinite in both directions; you have infinitely many people in front of you, but only finitely many behind
Is this even possible? One of the premises in the article. Won't it be infinity backwards for the nth person?
They're just describing a set of people you could consider ordered by positive integers. The first person has no one behind them, the nth person has n-1 people behind them
The natural numbers (positive integers) are the numbers 1, 2, 3 , 4, 5, ....
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.
Is there a missing "deterministically" in the axiom of choice statement?
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?).
But what does "picking at random" mean? If you think it's obvious that you can just make infinitely many random choices at the same time, you're endorsing the axiom of choice.
(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.)
Ah this is super helpful. I’m here stuck thinking “just pick any element at random”. Needing to have deterministically consistent pickings from infinite sets makes the problem clear and much more interesting.
I think that's why the "infinite socks vs. infinite shoes" are mentioned---because the socks are equivalent so you can't tell by the 'label' which one you grabbed.
Why is it only a problem when you have to choose from an infinite amount of sets? Why isn't the problem that you can get an infinite number of sets in the first place?
Consider all the "real" numbers x that are in the range 0 <= x < 1. We can talk about what the real number are separately, but you can think of them as being infinite decimals starting with "zero point ...". We consider two decimals to represent the same number if one ends with all 9s and the other is identical except for the last non-nine number, and has "n+1" in that place, then all zeros. So these decimal sequences represent the same number:
OK, now say that two of these numbers are related, they are in the same family, if their difference is a rational number. So these numbers are all related:
... and so on. These number are all in the same family. We can show that if a is related to b, and b is related to c, then a is related to c ... being in the same family is transitive.
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.
The axioms of ZF set theory don't let you say "Just choose one at random from each of these uncountable many sets." To simply "choose one at random" you need an axiom to say that you are allowed to do that.
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.
These are largely unconnected. If you think otherwise then you might want to be a bit more careful and precise in your thinking. You might, of course, have simply mis-spoken yourself, in which case it's not a big deal.
(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.
I can present you with a definition that specifies an infinite set. If you ask for an element, I can give you one. If you present me with a thing, I can tell you if it's in the set. In a very real sense it is completely specified.
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'.
Another perspective on the Axiom of Choice would be to formulate it as “you can select one element from each set in a given set of sets, and the selected elements form a set”. So we accept the existence of infinite sets (since we have an axiom stating that infinite sets exist), but acknowledge that they are tricky and that not every “collection” of whatever constitutes a set. For example, a collection of all sets does not constitute a set. In this interpretation, you can still choose one element from a set of sets, but the Axiom of Choice tells you in addition that the result of such choosing is not just a collection of elements, but itself a set, so you can apply all other axioms and theorems of set theory to it.
It happens regularly when, surprise, you deal with infinities in some other place.
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!)
If you allow yourself the infinite set of the natural numbers, you can pretty easily get an infinite set of sets. For instance, for every natural N, take the set of naturals less than N. Or greater than N, if you'd like an infinite set of infinite sets.
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.)
If you have a finite number of non-empty sets you can construct a choice function by induction. Of course induction won't get you beyond a finite amount of sets.
To me, the Axiom of Choice is absolutely natural – if we can pick one element of a set then we surely can pick elements from a collection of sets, who cares that this collection can be infinite.
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.
I don’t think it’s a question of ‘belief’. AOC is logically independent of the other ZF axioms: you may find it aesthetically ugly (a viewpoint I’m sympathetic to). But you can’t disbelieve it any more than you can disbelieve Euclid’s parallel postulate.
Here's a professor of math in some Australian university who has pursued a philosophy of mathematics while basically rejecting infinities, axiom of choice, and reals.
Interesting article... The derivative problem is particularly enlightening I think. A derivative is a limit. Thus the answer you get for a derivative is also a limit.
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.
> 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.