5 ms·

> 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 i

by twic 5y ago

> 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?

siraben 5y ago
> 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 https://en.wikipedia.org/wiki/Axiom_of_regularity
- twic 5y ago
  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!
  - l33t2328 5y ago
    What do you mean “you can get”? Being precise is especially important in math.
    - ceh123 5y ago
      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 https://en.wikipedia.org/wiki/Existential_instantiation [1] https://math.stackexchange.com/questions/132717/do-we-need-the-axiom-of-choice-for-finite-sets https://math.stackexchange.com/questions/132717/do-we-need-t...
      - twic 5y ago
        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 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 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).
    - twic 5y ago
      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.
bschne 5y ago
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?
- veltas 5y ago
  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.
  - bschne 5y ago
    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.
    - veltas 5y ago
      You're right, sorry.
- dandanua 5y ago
  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?
- twic 5y ago
  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?
nnamtr 5y ago
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.
- twic 5y ago
  Okay so if x is {potato, tomato}, what is the tuple for x, and how did you decide that?
  - ambulancechaser 5y ago
    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.
    - twic 5y ago
      Yes, that's what nnamtr said in their comment, and it doesn't answer my question.
deleted 5y ago
[deleted]
edflsafoiewq 5y ago
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.

by twic 5y ago

siraben 5y ago

> 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 https://en.wikipedia.org/wiki/Axiom_of_regularity

twic 5y ago
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!
- l33t2328 5y ago
  What do you mean “you can get”? Being precise is especially important in math.
  - ceh123 5y ago
    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 https://en.wikipedia.org/wiki/Existential_instantiation [1] https://math.stackexchange.com/questions/132717/do-we-need-the-axiom-of-choice-for-finite-sets https://math.stackexchange.com/questions/132717/do-we-need-t...
    - twic 5y ago
      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 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 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).
  - twic 5y ago
    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.

bschne 5y ago

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?

veltas 5y ago
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.
- bschne 5y ago
  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.
  - veltas 5y ago
    You're right, sorry.
dandanua 5y ago
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?
twic 5y ago
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?

nnamtr 5y ago

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.

twic 5y ago
Okay so if x is {potato, tomato}, what is the tuple for x, and how did you decide that?
- ambulancechaser 5y ago
  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.
  - twic 5y ago
    Yes, that's what nnamtr said in their comment, and it doesn't answer my question.

deleted 5y ago

[deleted]

edflsafoiewq 5y ago

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.