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

[Oxymoron]

So I assume that we all agree that one cannot define a choice function on the set $\mathbb{Z}$ without resorting to the AC because the integers are not naturally well-ordered (even though the integers is a set of ordered pairs of well-ordered subsets).

Question 2. Is $2 = \{\{\{\}\},\,\{\{\{\}\}\}\}$ the same as $2^1$? Because I have seen $2^1$ written in various places as a set of functions. If they are the same thing then is it true that the natural number 2 is a set of functions?

 

[matt grime]

I think AKG would, indeed did, argue differently for the first one. His point was that if you can write down a bijection with N that doesn't involve choice, then you can well order a set without choice. Since the function r--> 2r for r>0 and -2r+1 for r negative does not invoke the axiom of choice at any point it can be used to well order the integers.

I seem to recall there is something weaker than the axiom of choice along the lines of countable choice, anyone else know about that?When you see someone write a^b in this sense they are talking about the set of functions from b to a. Thus 2^1 in this idea is the set of functions from a 1 element set to a 2 element set. There are two of these.

Incidentally, when anyone writes 2, they *never* mean the set { {{}},{{{}}}}. No one thinks of natural numbers like that. The peano axioms are just a way to create a model of the natural numbers out of sets. In particular 2 *is not a set*, 2 is the element of N that is defined to be 1+1.

 

[Oxymoron]

Posted by Matt Grime:

I think AKG would, indeed did, argue differently for the first one. His point was that if you can write down a bijection with N that doesn't involve choice, then you can well order a set without choice. Since the function r--> 2r for r>0 and -2r+1 for r negative does not invoke the axiom of choice at any point it can be used to well order the integers.

So you are saying that

$$f(r)\,:\,r\mapsto\left\{\begin{array}{cc} 2r & \mbox{for }r \geq 0 \\ -2r+1 & \mbox{for } r < 0 \end{array}\right.$$

is an explicit choice function on $\mathbb{Z}$ which does not resort to the Axiom of Choice? If so, does this choice function define a well-ordering of $\mathbb{Z}$?

What about the reals? I don't think it is possible to define an explicit choice function on $\mathbb{R}$ without resorting to the Axiom of Choice. It would seem strange that both being infinite sets, one has a choice function and one does not. What is the difference between R and Z that enables Z to have a choice function and R not to have one?

Posted by Matt Grime:

Incidentally, when anyone writes 2, they *never* mean the set { {{}},{{{}}}}. No one thinks of natural numbers like that.

Well, I don't mean that 2 is that set. I guess I meant to say that the number 2 may be coded as a set in that way.

 

[Oxymoron]

I suppose then that $2^1$ may be coded in a similar fashion? If $2^1$ is a set of exactly 2 functions then it has two elements and it's coding may look like

$$\{\emptyset,\{\emptyset\}\}$$

the two elements of $2^1$ being the 1) the empty set (which corresponds to one of the maps) and 2) the set containing the empty set (which corresponds to the other map).

 

[matt grime]

That isn't how you write a function as set. A function from A to B is a subset of AxB. If you are thinking of 1 and 2 as sets, then a function from 1 to 2 is a subset of 1x2. The space 2^1 is the collection of all subsets of 1x2 that satisfy the definition of function. However, I find this a completely unhelpful way to think about functions.

 

[matt grime]

So you are saying that

$$f(r)\,:\,r\mapsto\left\{\begin{array}{cc} 2r & \mbox{for }r \geq 0 \\ -2r+1 & \mbox{for } r < 0 \end{array}\right.$$

is an explicit choice function on $\mathbb{Z}$ which does not resort to the Axiom of Choice? If so, does this choice function define a well-ordering of $\mathbb{Z}$?

I certainly haven't made any appeal to the axiom of choice. The point is that the integers (less 0, cos that is just annoying), now I come to think about it, are isomorphic to

{1,-1}xN with the lexicographic ordering.

I send r to ( r/|r|, |r|) (see why I got rid of 0?)

and I can do that because I have a rule that specifies what to do without making infinitely many compatible choices.

What about the reals? I don't think it is possible to define an explicit choice function on $\mathbb{R}$ without resorting to the Axiom of Choice. It would seem strange that both being infinite sets, one has a choice function and one does not.

Again, the naturals are an infinite set and have a well ordering on them.

Mind you this all goes beyond my limited understanding of the axiom of choice and its usage.

 

[matt grime]

I would add to AKG's point, that any countable set is well-orderable, but picking that well-order might invoke the countable axiom of choice. The one for the integers does not invoke the countable axiom of choice, I believe, since it is an explicit rule. i.e. it says send r to 2r if r>0 and r to -2r+1 other wise. It doesn't say, send 1 to something, then send 2 to something else, then... The set of finite power sets of N is countable, but I can't see anyway to well order it off the top of my head without invoking the countable axiom of chioce. You give me an element in the finite power set and I can't say what natural number if would map to under any bijection with N, I just know such a bijection exists.

 

[Oxymoron]

Posted by Matt Grime:

That isn't how you write a function as set. A function from A to B is a subset of AxB. If you are thinking of 1 and 2 as sets, then a function from 1 to 2 is a subset of 1x2. The space 2^1 is the collection of all subsets of 1x2 that satisfy the definition of function. However, I find this a completely unhelpful way to think about functions.

Why can't I encode the set of functions $2^1$ as a set by listing it's elements inside braces { } where each element is written only using {, } and $\emptyset$?

The elements of $2^1$ are functions right?

There are two of these because there are only two possible distinct functions from a 1-element set into a 2-element set: A function which maps

$$f_1(a)\,:\,a \mapsto b_1\quad\quad\mbox{for some }a\in\,1$$

and

$$f_2(a)\,:\,a \mapsto b_2\quad\quad\mbox{for some }a\in\,1$$

Now the challenge becomes to list (or encode) these two elements in bracket notation and empty sets. Just as we did for the natural numbers. Is this possible or impossible?

 

[matt grime]

It is perfectly possible, trivially possible in fact. Though why you would choose to do it is a mystery. The point of Peano for the naturals is that the successor operation corresponds to addition, not *just* that there are sets of cardinality n for all n.

 

[Oxymoron]

Posted by Matt Grime:

Though why you would choose to do it is a mystery.

Why, for fun of course!

Posted by Matt Grime:

It is perfectly possible, trivially possible in fact.

Really! Any idea how to do it then? Remember all you are allowed to use are {, } and $\emptyset$ symbols. Basically I want to see if I can do it for the set of functions just as I did for the set of natural numbers. I originally thought that it would look something like this: $\{\emptyset,\{\emptyset\}\}$, but apparently this was wrong. So I am not really sure what it should look like?

 

[matt grime]

Just do it: you're free to 'encode' things however you want in your idea so just arbitrarily assign symbols made up of { } 0 and , as your heart desires.

 

[Oxymoron]

Posted by Matt Grime:

Just do it: you're free to 'encode' things however you want in your idea so just arbitrarily assign symbols made up of { } 0 and , as your heart desires.

This isn't sarcasm is it? $2^1$ has only two elements, no? So it will have to be of the form

$$\{\{...\},\{...\}\}$$

So would [itex]\{\emptyset,\{\}\}[/tex] make sense?

 

[Oxymoron]

I should probably get back on topic.

Im trying to work out what I can do without resorting to the Axiom of Choice. I figured that by defining a choice function on a set then I am doing just a good a job as I would be if the Axiom of Choice held.

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 though does it?

Wikipedia says that a choice function can be defined on a set if
1] The set is a finite set of non-empty sets (such as $X = \{a,b,c\}$ such that a,b,c, are non-empty).
2] Every element of the set is well-ordered.
3] Every element of the set is non-empty and the union $\bigcup X$ is well-orderable.

 

[matt grime]

This isn't sarcasm is it?

No, but would it matter? You claim to want to do for functions between two sets what Peano does for naturals. However, functions between sets do not have of the extra structure of addition of elements as the naturals do so it is trivial to encode this information arbitrarily in whatever langauage you wish, in particular one made up of {}0 and ,.

 

[matt grime]

I should probably get back on topic.
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?

Since we have apparently showed there to be a choice function by well ordering the integers without, seemingly, the axiom of choice I fail to understand what you're asking.

 

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