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

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