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

[matt grime]

Obviously not. Algebraic closure and topological closure are completely unrelated concepts.

 

[AKG]

My ordering would not respect the natural ordering, nor would it even respect the well-ordering on Q. It's clear that no well-ordering can.

What? You're proposing a well-order on R that doesn't respect a well-order on Q? If X is a subset of Y, and X is well-ordered, then the restriction of the well-order to Y is of course a well-order.

I thought the closure of Q in R (with the standard topology) was the algebraic numbers \bar{\mathbb{Q}}.

I think matt just addressed this.

 

[sparkster]

You can't just "take the closure of Q". The closure of Q as a subspace of Q is Q. The closure of Q as a subspace of R with the standard topology is R.

I thought I was clear that I was always equipping Q with the subspace topology.

The closure of Q as a subspace of R with a topology which, when restricted to Q, coincides with an order topology on Q induced by some well-order on Q is, well, God knows what.

Right. That's what I meant to say. I'm sorry if I tend to be less than precise. I usually get online at the end of a long day and I suspect it's making my sloppier than usual.

 

[CRGreathouse]

What? You're proposing a well-order on R that doesn't respect a well-order on Q? If X is a subset of Y, and X is well-ordered, then the restriction of the well-order to Y is of course a well-order.I think matt just addressed this.

I was proposing a well-order on R based on a given well-order for Q, where the well-order for R restricted to Q is not the same as the given well-order for Q. Obviously the restriction of my well-order on R to Q is a well order, it's just not the same as the given one (when restricted to Q).

 

[CRGreathouse]

Obviously not. Algebraic closure and topological closure are completely unrelated concepts.

I think matt just addressed this.

I'm amused. I was reading about some particular algebraic closure earlier, and the fact that you were talking about topological closure just didn't occur to me. Heh.

 

[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}<br /> 2r &amp; \mbox{for }r \geq 0 \\<br /> -2r+1 &amp; \mbox{for } r &lt; 0<br /> \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}<br /> 2r &amp; \mbox{for }r \geq 0 \\<br /> -2r+1 &amp; \mbox{for } r &lt; 0<br /> \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 \{\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.