Defining Choice Functions: When & How Without Using Axiom of Choice

[AKG]

2 = {0,1} = {{},{0}} = {{},{{}}}
2¹ is the set of functions from 1 to 2. A function from 1 to 2 is a set of ordered pairs such that the first element in a pair is an element of 1 and the second is an element of 2, and there are no two distinct pairs that have the same first co-ordinate (this last bit just says that functions are not one-to-many).

There are two functions from 1 to 2. Recall 1 = {0} = {{}}, and 2 is what it says above. One function maps 0 to 0, and the other maps it to 1. So

2¹ = {{(0,0)}, {(0,1)}}

The ordered pair (x,y) is {{x}, {x,y}}, so continuing:

= {{{{0}, {0,0}}}, {{{0}, {0,1}}}}
= {{{{{}},{{}}}},{{{{}},{{},{{}}}}}}
= {{{{{}}}},{{{{}},{{},{{}}}}}}

And the function I gave before defines a well-order on Z, but it is not a choice function. Given a collection C of nonempty sets, a choice function maps each S in C to an element of S. You can regard Z as a collection of sets, but the function isn't supposed to map each integer to an element of itself. If it is a choice function, it's entirely a coincidence. It is just supposed to help define a well-order. A well-order is a binary relation satisfying some certain properties. Given the function I defined, we can now define a relation R by:

xRy iff f(x)<f(y)

You can check that this is a well-ordering.

Don't confuse choice functions with well-orderings.

 

[Oxymoron]

For example. Suppose I choose my favourite non-empty, well-ordered set, X. Then I would not be able to define an explicit choice function for this set. However if I choose my favourite non-empty set, X, such that every element is a well-ordered set, then I would be able to define an explicit choice function because I could let my function choose the least element of each set of X. Is this correct reasoning?

 

[matt grime]

I think I can well order the finite power set of N after all. Given any finite collection of elements of N x={x_1,..,x_n}, just send x to the product p_{x_i} for p_1,p_2,... the distinct primes. I hope I have not implicitly invoked anything untoward here.

 

[Oxymoron]

Posted by AKG:

Don't confuse choice functions with well-orderings.

I knew I was!

Posted by AKG:

And the function I gave before defines a well-order on Z, but it is not a choice function. Given a collection C of nonempty sets, a choice function maps each S in C to an element of S. You can regard Z as a collection of sets, but the function isn't supposed to map each integer to an element of itself. If it is a choice function, it's entirely a coincidence. It is just supposed to help define a well-order. A well-order is a binary relation satisfying some certain properties. Given the function I defined, we can now define a relation R by:

I always doubted that we had actually defined a choice function. I remember reading somewhere that it was impossible to define a choice function for the integers without resorting to the AoC. Somewhere along the way I was caught up in the well-ordering/choice function trap.

 

[AKG]

And no, {0,{}} wouldn't make sense, since it only has one element, 0 (since 0 = {}). In fact, what you have is:

{0,{}}
= {0} [or {{}} if you want, it's the same thing]
= 1, not 2.

So far we have worked out that we can explicitly define a Choice Function on the integers without resorting to the AoC. This does not necessarily mean that the integers are well-ordered does it?

No, you've defined a well-order on Z without invoking the choice axiom. This means that Z is well-orderable. The normal order on Z is not a well-order.

What can we do without the choice axiom? Well, do you know the statement of the choice axiom? It says for all collections C of nonempty sets, there exists a function f such that ... If, given a particular collection C of nonempty sets you can prove there exists a function f such that ..., then you don't need to invoke the axiom of choice. When C is finite, for example, you don't need the choice axiom, because you can prove there exists an f such that ... with the other axioms. In other special cases for C, you again don't need the choice axiom because you can prove there exists an f using just the other axioms. In general, however, you need the AC if you want, for each C, there to be a function f such that ... By the way, the ellipsis just says that 'f is a choice function on C'.

 

[AKG]

For example. Suppose I choose my favourite non-empty, well-ordered set, X. Then I would not be able to define an explicit choice function for this set. However if I choose my favourite non-empty set, X, such that every element is a well-ordered set, then I would be able to define an explicit choice function because I could let my function choose the least element of each set of X. Is this correct reasoning?

At first glance, that looks good. But what is a well-ordered set? It is a set that has a well-order. But in general, a well-ordered set has many well-orders. So for each set you can't first just say "pick the least element" you first have to pick a well-order, then you can choose the least element. But the problem of picking a well-order for each set is tricky in itself. I have to think on how you'd do this.

 

[Oxymoron]

Posted by AKG:

2 = {0,1} = {{},{0}} = {{},{{}}}
21 is the set of functions from 1 to 2. A function from 1 to 2 is a set of ordered pairs such that the first element in a pair is an element of 1 and the second is an element of 2, and there are no two distinct pairs that have the same first co-ordinate (this last bit just says that functions are not one-to-many).

There are two functions from 1 to 2. Recall 1 = {0} = {{}}, and 2 is what it says above. One function maps 0 to 0, and the other maps it to 1. So

21 = {{(0,0)}, {(0,1)}}

The ordered pair (x,y) is {{x}, {x,y}}, so continuing:

= {{{{0}, {0,0}}}, {{{0}, {0,1}}}}
= {{{{{}},{{}}}},{{{{}},{{},{{}}}}}}
= {{{{{}}}},{{{{}},{{},{{}}}}}}

Perfect! That satisfies my curiosity completely and makes perfect sense.

No, you've defined a well-order on Z without invoking the choice axiom. This means that Z is well-orderable. The normal order on Z is not a well-order.

Yeah, that looks right to me. I had a feeling I'd get fooled by the difference between well-ordered and well-orderable.

So I gather that I must not be able to define an explicit choice function on \mathbb{Z} without having to use the AoC? Same for the reals I guess. And the same for any non-empty well-ordered set.

However, I reckon I could define a choice function without the need for the AoC for any non-empty set whose elements are all well-ordered, for the ordinal \omega, and for the set of rationals, \mathbb{Q}. What do you think?

 

[matt grime]

What do you mean by 'define a choice function on Z'? I realize this is a little late, but a choice function is defined on a set of sets. Z is not a set of sets (despite all that has gone before in this discussion).

 

[Oxymoron]

Here is my definition of a Choice Function:

\mbox{For any non-empty set }Y\mbox{ a choice function for }Z\mbox{ is a function }f\,:\,\mathcal{P}(Y)\backslash\{\emptyset\}\rightarrow Z\mbox{ such that }f(A) \in A\mbox{, for every }A\in\mathcal{P}(Y)\backslash\{\emptyset\}

So maybe we were wrong to even consider defining a choice function on the integers since it fails even the most basic of definitions?

EDIT: Fixed...maybe

 

[CRGreathouse]

So I gather that I must not be able to define an explicit choice function on Z without having to use the AoC? Same for the reals I guess. And the same for any non-empty well-ordered set.

No, wherever do you get that idea? It's easy to well-order the integers, as has been shown above. The 'obvious' function that maps positives to their double and intermingles negatives suffices quite well. Any set containing nonempty subsets of the integers can have an element from each set chosen by mapping each element to its value in this function and choosing the lowest resultant value. (In fact, just choose the element with the lowest absolute value, breaking ties in the positive's favor.)

The choice function just picks the value with the lowest image with this function from each set.

However, I reckon I could define a choice function without the need for the AoC for any non-empty set whose elements are all well-ordered, for the ordinal \omega, and for the set of rationals, \mathbb{Q}. What do you think?

Consider this set of well-ordered sets:
{{2, 4, 6, 8, ...}, {3, 6, 9, 12, ...}, {2, 3, 5, 7, 11, ...}}
The choice function works on the set of sets, leting choosing 2 from {2, 4, 6, 8, ...}, 3 from {3, 6, 9, 12, ...}, and 2 from {2, 3, 5, 7, 11, ...}. You can use this choce function ("choose the lowest value from each set") as a choice function for any set of sets if the individual sets can all be uniquely mapped into the natural numbers.

 

[matt grime]

I don't like your definition of choice function. It does not make sense.

f sends elements of P(Y)\0 to Z (this Z is not the integers, just a set) such that

f(A) is an element of A.

Now for f(A) to make sense A must be an element of P(Y). But you say it is in P(Z). Is Y supposed to be Z or something?

 

[AKG]

So I gather that I must not be able to define an explicit choice function on \mathbb{Z} without having to use the AoC? Same for the reals I guess. And the same for any non-empty well-ordered set.

You're still getting confused. You don't want a choice function on Z, you want a well-order on Z.

However, I reckon I could define a choice function without the need for the AoC for any non-empty set whose elements are all well-ordered, for the ordinal \omega, and for the set of rationals, \mathbb{Q}. What do you think?

No, this means you are still confused on the difference between "well ordered" and "well orderable". What do you think "well ordered" means, and how does it differ from "well orderable"? Try to give precise definitions.

 

[CRGreathouse]

I don't like your definition of choice function. It does not make sense.

f sends elements of P(Y)\0 to Z (this Z is not the integers, just a set) such that

f(A) is an element of A.

Now for f(A) to make sense A must be an element of P(Y). But you say it is in P(Z). Is Y supposed to be Z or something?

That's not my definition of choice function, it's my example of a way to build a choice function. If you have a map from a set X to the natural numbers, then any set of subsets of X has a choice function based on that map.

Essentially, it's translating between a well-ordering and a choice function. Actualy, I suppose it even works the other way for sets of countable sets: use the choice function to pick an element out of each set in your set and call these your 'least elements' in each set. Construct a set of sets equal to the sets in the old set of sets without the chosen elements and recurse, putting the new elements 'less than' all remaining elements and 'greater than' all elements already chosen.

In short: a well-order on a set defines a choice function on sets of subsets of that set, and for countable sets at least the converse holds.

 

[AKG]

WOT -> AC
-----------

Assume the Well-Ordering Theorem is true, that is, that every set is well-orderable. Let C be any collection of sets. By the union axiom, Union(C) exists, and by our assumption, it has a well-order. Define a choice function which takes a set c in C to the least element in Union(C) which is also an element of c [i.e. the least element of c when regarded as a subset of Union(C)]. There you go, the choice function exists. (Adapted from Folland's, "Real Analysis: Modern Techniques and Their Applications").

Note in the above we only have to instantiate one well-order. Although the assumption about well-orderings says that each set is well-orderable, we need to instantiate a well-order to define a choice function. And we cannot instantiate more than finitely many well-orders, because that would require an infinite number of lines, and thus wouldn't constitute a proof.

 

[Oxymoron]

I read somewhere that it is possible to construct a choice function for the set of rationals \mathbb{Q} without resorting to the axiom of choice. Since one can identify every rational number with an ordered pair of integers (m,n). Then you could imagine the rationals as a collection of points on the plane - with each rational number being a point

(-2,2) (-1,2) (0,2) (1,2) (2,2)
(-2,1) (-1,1) (0,1) (1,1) (2,1)
(-2,0) (-1,0) (0,0) (1,0) (2,0)
(-2,-1)(-1,-1)(0,-1)(1,-1)(2,-1)
(-2,-2)(-1,-2)(0,-2)(1,-2)(2,-2)

Each point on the plane given as above represents a rational number. Then a choice function would simply start at (0,0) and spiral outward, visiting all points.

(-2,2)<--(-1,2)<--(0,2)<--(1,2)<------(2,2)
...\/........../\
(-2,1)...(-1,1)<-----(0,1)<-----(1,1)...(2,1)
...\/...\/....../\.../\
(-2,0)...(-1,0)...(0,0) ----->(1,0)...(2,0)
...\/...\/........./\
(-2,-1)...(-1,-1)---->(0,-1)---->(1,-1)--->(2,-1)
...\/............
(-2,-2)--->(-1,-2)--->(0,-2)--->(1,-2)--->(2,-2)...etc

Therefore for every non-empty subset of \mathbb{Q} (ie. for every rational number n/m) we assign via our construction the number that will be reached first by spiralling out and therefore this defines a Choice Function.

 

[Oxymoron]

...and in the case of the reals we know for a fact that they are well-orderable if we assume the Axiom of Choice. But the axiom of choice is equivalent to the existence of a choice function. Therefore the reals are well-orderable if for any set of non-empty sets there exists a choice function f defined on the sets.

So does this mean that the reals are well-orderable if there exists a choice function defined on the reals?

I thought for a moment that since there is a one-to-one correspondence between the reals and the power set of the naturals then to well-order the reals all I have to do is well-order the naturals. But unfortunately there is no explicit way of well-ordering the power set of the naturals either!

Posted by AKG:

You're still getting confused. You don't want a choice function on Z, you want a well-order on Z.

Actually, I do want do define explicitly a choice function on Z without resorting to the axiom of choice. I want to do the same thing for Q and for R. I do not want to imply the existence of a choice function from the well-ordering of these three sets, I want to well-order these sets using the explicit choice function I defined in the first place (if the choice function exists at all - if it doesn't then I don't care if I can well-order the sets). By the way, I do not claim that this is at all possible.

 

[AKG]

No, you really are getting confused. The thing you described in post 65 is not a choice function, it is (on its way to becoming) a well-order. It doesn't really even make sense to talk about defining a choice function on Z, or Q, or R.

 

[Oxymoron]

Posted by AKG:

No, you really are getting confused.

This is a distinct possibility.

Posted by AKG:

The thing you described in post 65 is not a choice function, it is (on its way to becoming) a well-order. It doesn't really even make sense to talk about defining a choice function on Z, or Q, or R.

I think I am going to forget about my whole plan. It seems that from everyone's posts that I am wasting my time trying define an explicit choice function for Z, Q, and R without using the Axiom of Choice. I honestly thought it may be possible to do this (especially for Q), but obviously not.

At least I now know that it is possible for finite sets and for any non-empty set whose elements are all well-ordered sets.

 

[CRGreathouse]

I think I am going to forget about my whole plan. It seems that from everyone's posts that I am wasting my time trying define an explicit choice function for Z, Q, and R without using the Axiom of Choice. I honestly thought it may be possible to do this (especially for Q), but obviously not.

I think most of the problem is with terminology. What you call a choice function is closer to what most people call a well-ordering. Certainly a function of the sort you describe can be constructed for Z and Q without AC. I have trouble imagining such a function on R (without AC), but there's no reason you shouldn't try. It mgiht help you understand the problem better.

In the future, you may wsh to sidestep this entire terminological argument by saying you want to find an injective function onto N rather than a choice function.

 

[AKG]

It is easily possible to define a well-order on Z or Q without the axiom of choice. I can't think of how to define a well-order on R without the axiom of choice. But defining a choice function on Z, Q, or R doesn't even make sense! It's not that you're wasting your time trying to do something difficult, it's that you're not even making sense. Suppose G and H are groups, and think of something totally different from a group, maybe a polynomial p(x). A sensible question is: "can you define a homomorphism f : G -> H?" A nonsensical question is: "can you define a homomorphism f : p(x) -> H?" You trying to define a choice function on Z makes as much sense as trying to define a homomorphism from a polynomial to a group.

You can define a well-order on Z, we've already done it in this thread. You can easily define a well-order on Q too - if it hasn't already been done in this thread, then your post #65 is pretty much right. But it does not make sense to define a choice function on Z or Q. And it's not just a minor terminological difference. "Choice function" has a very specific definition, and "well-order" does too, and they are very different things. The fact that you seem to be using "choice function" to refer to "well-order" is something you really need to correct.

 

[Hurkyl]

A function f with domain S is a choice function for S if and only if f(s) \in s for all s in S.

 

[Oxymoron]

The Axiom of Choice is equivalent to the statement that every non-empty set has a choice function. [Is this correct?]

If so, then for some sets a choice function can be defined without using the Axiom of Choice. [Is this correct?]

If so, the I may define an explicit choice function for that set.

 

[Hurkyl]

The Axiom of Choice is equivalent to the statement that every non-empty set has a choice function.

No; the AoC is the statement that every set of nonempty sets has a choice function.

Just to make it explicit, the mistakes you made were:
(1) The AoC applies to the empty set. (It's choice function is the empty function)

(2) If S contains the empty set, it cannot possibly have a choice function (you cannot possibly have f(\emptyset) \in \emptyset). The AoC applies to all sets that do not contain the empty set.

If so, the I may define an explicit choice function for that set.

If you can explicitly define a choice function, then you can explicitly define a choice function.

An example of an explicitly defined choice function is the following choice function for the set S = {{a}, {b, c}}:

f({a}) := a
f({b, c}) := c

or, as a set-of-ordered-pairs:

f := { ({a}, a), ({b, c}, c) }

 

[CRGreathouse]

If so, the I may define an explicit choice function for that set.

If you have to use AC, then you don't have an explicit choice function, you just know that some choice function exists.