Axiom of choice with single-point sets

[Tom1992]

axiom of choice

do you need to invoke the axiom of choice to choose a point from a collection of sets if the sets are single-point sets?

for example, suppose f:A->B is injective. to create a left inverse g:f(A)->A, we need to "choose" a point from the preimage of b for all b in f(A) and send b to this point by g. but because f is injective, the preimage of b is just one point. do we have to use the axiom of choice to create the left inverse g? after all, the new set being created by "choosing" these points from the preimages simply give the set A, which is not a new set.

 

[Tom1992]

ok, what about this easier, less philosophical question regarding the axiom of choice:

define a one-to-one function f:N -> {0,1}x{0,1}x{0,1}x...

my solution:
define f(n) = (x_i), where x_n=1, and all other components are 0. so the axiom of choice is not being used because a formula (pattern) is being used to define f and hence there is no “choosing” from {0,1} involved for every n in N. is this correct?

 

[verty]

I don't know, but is the axiom of choice perhaps required only for uncountable sets? It seems pretty uncontroversial that I could choose 0 or 1...

 

[Tom1992]

I don't know, but is the axiom of choice perhaps required only for uncountable sets?

according to my book, the axiom of choice is used when choosing an element from each non-empty (that is the only condition) set from a collection of sets. in my above two examples, the sets from which i am "choosing" a point are non-empty (though finite). the question is whether i need to use the axiom of choice.

It seems pretty uncontroversial that I could choose 0 or 1...

that is the whole bugaboo about the axiom of choice. it's an axiom that seems so obvious (and any physicist reading this will think this is all hogwash) but nevertheless we must quote it if we are in fact using it. the question is whether i am actually using the axiom of choice in my above two examples or not.

 

[Tom1992]

I don't know, but is the axiom of choice perhaps required only for uncountable sets?

how about this example i made up:

let W be a collection of uncountable, disjoint, well-ordered sets A_i.
define c:W -> union A_i by the rule c(A_i)=smallest element of A_i.

are we using the axiom of choice is constructing this choice function? we are not choosing arbitrarily from each set A_i, but defining specific points from each A_i.

could someone please clarify whether the axiom of choice is being used in the three examples I've given? my answer is "no" to all three examples, because we are not choosing arbitrarily from each set but rather defining the points from each set. am i right? but then on the other hand, by defining points from each set, we are literally "choosing" points. is this just a matter of semantics?

 

[Tom1992]

ok, what about this easier, less philosophical question regarding the axiom of choice:

define a one-to-one function f:N -> {0,1}x{0,1}x{0,1}x...

my solution:
define f(n) = (x_i), where x_n=1, and all other components are 0. so the axiom of choice is not being used because a formula (pattern) is being used to define f and hence there is no “choosing” from {0,1} involved for every n in N. is this correct?

ok, i firmly believe that the axiom of choice is not being used in this example.
an example of a construction of an injective map f using the axiom of choice for this question is the following: choose a point from {0,1}x{0,1}x{0,1}x... and designate f(1) to be this point. now choose a point from {0,1}x{0,1}x{0,1}x... -f(1) and designate f(2) to be this point. continue in this manner, choosing a point from {0,1}x{0,1}x{0,1}x... -f({1,...,n-1}), which is nonempty since {0,1}x{0,1}x{0,1}x... is infinite, and designating f(n) to be this point. the resulting mapping f is injective. the axiom of choice is required in each iteration since f is defined by choosing arbitrary points from a collection of sets.

what about my first and third examples? i firmly believe the answer is no for them as well.

this is the rule: if you are choosing a point arbitrarily from a collection of sets, you are using the axiom of choice. if you are defining a specific (well-defined) rule for choosing a point from a collection of sets, then you are not using the axiom of choice. correct?

 

[Crosson]

this is the rule: if you are choosing a point arbitrarily from a collection of sets, you are using the axiom of choice. if you are defining a specific (well-defined) rule for choosing a point from a collection of sets, then you are not using the axiom of choice. correct?

Pretty much correct, the only time it is necessary to use the axiom of choice is when you want to claim the existence of a set containing exactly one element from each set in an infinite collection, without specifying a specific rule.

Because 'sets' are only what we define them to be, they do not automatically inherit the intuitive properties we think they should have, and so assuming AOC makes mathematical sets' behave more like 'intuitive sets'.

 

[Fredrik]

do you need to invoke the axiom of choice to choose a point from a collection of sets if the sets are single-point sets?

Wouldn't this just be the union of all the sets? I don't know the ZF axioms, but I assume that one of them says that the union of a bunch of sets is a set.