News for hackers. Stuff that matters.
Re:What is the Axiom of Choice? by twic on Friday July 16, 2021 @05:13AM (#27854397)
> 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?

Re:What is the Axiom of Choice? by nnamtr on Friday July 16, 2021 @06:08AM (#27854666)
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.

Re:What is the Axiom of Choice? by twic on Friday July 16, 2021 @12:52PM (#27858243)
Okay so if x is {potato, tomato}, what is the tuple for x, and how did you decide that?
Re:What is the Axiom of Choice? by ambulancechaser on Friday July 16, 2021 @04:14PM (#27860725)
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.

Re:What is the Axiom of Choice? by twic on Saturday July 17, 2021 @04:54AM (#27864483)
Yes, that's what nnamtr said in their comment, and it doesn't answer my question.
Re:What is the Axiom of Choice? by siraben on Friday July 16, 2021 @05:37AM (#27854529)
> Is picking an element from a single finite set something you can build using ZF?

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.

[0] https://en.wikipedia.org/wiki/Axiom_of_regularity

Re:What is the Axiom of Choice? by twic on Friday July 16, 2021 @12:48PM (#27858203)
It seems to me that there is a huge difference between "a set X must have an element y" and "given a set X, you can get an element y".

If set theorists do not make that distinction, then that is the answer to my question!

Re:What is the Axiom of Choice? by l33t2328 on Friday July 16, 2021 @01:15PM (#27858561)
What do you mean “you can get”?

Being precise is especially important in math.

Re:What is the Axiom of Choice? by ceh123 on Friday July 16, 2021 @03:59PM (#27860566)
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.

[0] https://en.wikipedia.org/wiki/Existential_instantiation [1] https://math.stackexchange.com/questions/132717/do-we-need-t...

Re:What is the Axiom of Choice? by twic on Saturday July 17, 2021 @05:14AM (#27864543)
Yes! Existential instantiation looks like exactly what I was asking for.

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).

Re:What is the Axiom of Choice? by twic on Saturday July 17, 2021 @04:56AM (#27864488)
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.
Re:What is the Axiom of Choice? by bschne on Friday July 16, 2021 @05:39AM (#27854535)
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.

Am I missing something?

Re:What is the Axiom of Choice? by skissane on Friday July 16, 2021 @05:52PM (#27861661)
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".

Re:What is the Axiom of Choice? by veltas on Friday July 16, 2021 @06:00AM (#27854629)
I think you can already pick an element.

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.

Re:What is the Axiom of Choice? by bschne on Friday July 16, 2021 @06:03AM (#27854644)
Yes but as I read it, the parent comment was not asking about that, but about whether we could even assume we could pick from a single set.
Re:What is the Axiom of Choice? by veltas on Friday July 16, 2021 @06:28AM (#27854760)
You're right, sorry.
Re:What is the Axiom of Choice? by twic on Friday July 16, 2021 @12:47PM (#27858187)
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?

Re:What is the Axiom of Choice? by cevi on Saturday July 17, 2021 @11:00AM (#27866243)
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".

Re:What is the Axiom of Choice? by dandanua on Friday July 16, 2021 @10:25AM (#27856531)
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?
Re:What is the Axiom of Choice? by edflsafoiewq on Friday July 16, 2021 @09:35AM (#27856070)
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.