Comment by impostervt
Comment by impostervt 5 days ago
I've never quite gotten the axiom of choice. Can anyone ELI5?
Comment by impostervt 5 days ago
I've never quite gotten the axiom of choice. Can anyone ELI5?
> The Cartesian product of nonempty sets is nonempty. > > This is obvious!, you might say — obviously we can just pick one element from each set and be done with it. But the statement that we can pick an element from each set is the axiom of choice.
No? I don’t see how this relates to AC at all. AC is about making an infinite number of choices at once – if you’re just making two choices (or, more generally any finite number of choices), as is needed here to prove that this Cartesian product is nonempty, then that’s completely fine without extra axioms. See for example https://mathoverflow.net/q/32538
E.g. in type theory, one term of type `Nonempty(A) → Nonempty(B) → Nonempty(A × B)` (supposing that `Nonempty` is defined as the [bracket type](https://ncatlab.org/nlab/show/bracket+type)) would just be `λ [a] ↦ λ [b] ↦ [(a, b)]`.
The two statements imply each other, they are logically equivalent:
https://en.wikipedia.org/wiki/Product_topology#Axiom_of_choi...
>One of many ways to express the axiom of choice is to say that it is equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.
> A human cannot describe said element, by definition.
That example doesn't work. Some numbers are describable but not computable, Chaitin's constant being the famous example: https://en.wikipedia.org/wiki/Chaitin%27s_constant
> Note that it's not necessarily simple to pick an element from a set. For instance, how would one pick an element from the set of uncomputable numbers?
In ZF without choice, you can pick an element from any non-empty set, so it actually is simple to pick an element from a set. Choice is only needed when you have an infinite number of sets to pick elements from.
> but you need that you can take a Cartesian product and turn it into a set of its elements as well
Huh? In your model, what is a Cartesian product? How can it have elements without being a set?
Well, you’d need some model of index, for one. And I’m not sure how you’d construct that with uncountably many elements. Even ignoring that, a set containing n elements is different from a set containing n sets of one element each.
Not saying your formulation is wrong, just that there’s a fair amount of non-obvious work to get to the classic formulation.
Isn't that equivalent (or, ok, similar) to saying that we can decide undecidable mathematical truths?
As far as I understand there's no such thing “undecidable” in absolute, Gödel incompleteness theorem is about being undecidable under a certain set of axioms.
The axiom of choice allows you to make infinitely many arbitrary choices.
You don't need the axiom of choice to make finitely many arbitrary choices. Let's say you have a pile of indistinguishable socks in front of you. You want to pick two of them. Well -- assuming that there are at least two of them to pick -- you can pick one, and then you can pick one from what remains. If something exists, you can pick one of it, that's permitted by the laws of logic; and if you need to do that multiple times, well, obviously you can just do it multiple times. But if you need to do it infinitely many times, well, the laws of logic aren't enough to support that.
You also don't need the axiom of choice if the choices aren't arbitrary, but rather are given by some rule you can specify. There's a famous analogy used by Russell to illustrate this. Suppose you have set in front of you an infinite array of pairs of socks, and you want to pick one sock from each pair. Then you need the axiom of choice to do that. But suppose, instead, it were an infinite array of pairs of shoes. Then you don't need the axiom of choice! Because you can say, I will always pick the left one. That's a rule according to which the choice is made, so you don't need the axiom of choice. You only need the axiom of choice when the choices have some arbitrary element to them, where there isn't a rule you can specify that gets things down to just a single possibility. (Isn't the choice of left over right making an arbitrary choice? In a sense, yeah, but it's only making a single arbitrary choice!)
(The axiom that lets you do this, btw, is the axiom of separation. Or, perhaps in rare instances, the axiom of replacement, but the axiom of replacement is generally irrelevant in normal mathematics.)
So that's what the axiom of choice does. Without it, you can only make finitely many arbitrary choices, or infinitely many specified choices. If you need to make infinitely many choices, but you don't have a rule to do it by, you need axiom of choice.
[Edit: Given the article, I should note that I'm describing the role of the axiom of choice in ordinary mathematics, rather than its role in constructive mathematics. I know little about the latter.]
Bertrand Russell coined an analogy: for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i.e. set) of shoes; this makes it possible to define a choice function directly. For an infinite collection of pairs of socks (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no obvious way to make a function that forms a set out of selecting one sock from each pair without invoking the axiom of choice.
(From Wikipedia but I’ve always found it good)
Somehow the existing answers don't satisfy me, so here's my attempt. The essence of it is really simple.
The axiom is an obviously true statement: if you have a bag of beans, you can somehow take one bean out of it, without specifying, how do you choose the exact bean. Obvious, right? And that's really it, informally this is the axiom of choice: we are stating that we can somehow always do that, even if there are infinitely many beans and infinitely many bags, and the result of your work may be a collection of infinitely many beans.
Now, what's the "problem"? If you look closer, what I've just said is equivalent to saying we can well-order[0] any set of elements, which must make you uncomfortable: you may be ok with the idea that in principle you can order infinitely many particles of sand (after all, there are just ℕ of them), but how the fuck do you order water (assuming it's like ℝ — there are no molecules and you can divide every drop infinitely many times)?
This is both why we have it — ℝ seems like a useful concept so far; and the source of all notorious "paradoxes" related to it — if you can somehow order water, you may as well be able to reorder details of a sphere in a way to construct 2 spheres of the same size.
The single most best definition I know is what is on the wiki[0]:
> A choice function (also called selector or selection) is a function f, defined on a collection X of nonempty sets, such that for every set A in X, f(A) is an element of A. With this concept, the axiom can be stated:
> Axiom—For any set X of nonempty sets, there exists a choice function f that is defined on X and maps each set of X to an element of that set.
I like this definition because IMO it is simple, close to the name of the axiom, and you might want to use it in this form, that is, having a set of sets, and taking a choice function on them.
To understand its importance and the controversies around it, you'll need some examples and counterexamples how truthness and provability and knowability (regarding structures, numbers, metamathematics) interact; also what are the views of the majority of working mathematicians and people in other fields using mathematics.
[0] : https://en.wikipedia.org/wiki/Axiom_of_choice#Statement
Tangential, but a choice function is one of the ur-examples of Dependent Type Theory (DTT). In standard ZFC the choice function on X would have the type signature
f: X -> UX (union X).
f: (A:X) -> A.
Often it's easy to construct a family of sets representing something of interest. For example, we like to define integration initially as a finite process of breaking the integrand's domain into pieces, computing their area, and summing.
To compute the contribution of some piece indexed i, we measure the size of its domain, call it the area Ai, and then evaluate the integrand, f, at some point xi within that domain, then the contribution is Ai * f(xi).
Summing all of these across i produces a finite approximation of the integral. Then we take a limit on this process, breaking the domain into larger and larger families of sets with smaller and smaller areas. At the limit, we have the integral.
This process seems intuitive, but it contains an application of the axiom of choice---in the limit, we have an infinite number of subsets of our domain and we still have to pick a representative xi for each one to evaluate the integrand at.
It's quite obvious how to pick an arbitrary representative from each set in a finite family of sets: you just go through one-by-one picking an element.
But this argument breaks down for an infinite family. Going one-by-one will never complete. We need to be able to select these representative xis "all at once". And the Axiom of Choice asserts that this is possible.
(Note: I'm being fast-and-loose, but the nature of the argument is correct. This doesn't prove integration demands AoC or anything like that, just shows how this one sketch of an argument would. Specifically, integration normally avoids AoC because we can constructively specify our choice function - for example, picking the lexicographically smallest point within each axis-aligned rectangular cell. Generalize to something like Monte Carlo integration, however...)
Not like 5, but High-school Geometry.
If you remember Geometry, there are two ways to prove something:
- By making it (constructing)
- By contradiction (reductio ad absurdum)
During the late 1800s to early 1900s, when math was becoming more formalized, a group of mathematicians had issues with the second method.
From their point of view if you can’t show how to make it, then you’ve not proven that it exists.
Now it turns out that indirect proofs like contradiction requires the law of excluded middle: If something isn’t true, then it must be false (or vice versa).
It turns out that AoC is needed/implied, for the law of excluded middle; hence the objection to AoC; and enables these non-constructive proofs.
https://en.m.wikipedia.org/wiki/Law_of_excluded_middle
Another AoC proof: Prove that an irrational number to a irrational power can be rational.
sqrt(2)^sqrt(2) : If rational, then done.
Else (sqrt(2)^sqrt(2))^sqrt(2) = 2.
QED (and non-constructive).
This set of slides, originally devised for the Chaos Communication Congress, might be helpful: https://www.speicherleck.de/iblech/stuff/ac-38c3.pdf
- Precise statement of the axiom
- Overview of its consequences
- A counterexample (in an alternative universe)
- Consistency of the axiom
- Gödel's sandbox for containing the axiom
Yes. Here’s a great ELI5 intro:
Have you ever seen statements such as "for every epsilon there is a delta such that the following ... holds"? The axiom of choice implies that in those cases the delta can be supplied by some function of epsilon. It can't be proven that such a function exists in ordinary ZF (even if you can prove that statement with epsilon and delta).
The Cartesian product of nonempty sets is nonempty.
This is obvious!, you might say — obviously we can just pick one element from each set and be done with it. But the statement that we can pick an element from each set is the axiom of choice.
Note that it's not necessarily simple to pick an element from a set. For instance, how would one pick an element from the set of uncomputable numbers? A human cannot describe said element, by definition. The axiom of choice says it's possible anyway.