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.
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?
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.
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".
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.
> * 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?