# The Choice Function

1. Sep 25, 2006

### Oxymoron

Does the choice function let me choose exactly one element from a set? The set which I am choosing from must be the domain of the choice function, correct?

Also, if I have a finite set, say something like $X = \{a,b,c\}$ where a, b, c are distinct non-empty sets, then can I construct a choice function for this set? Could this choice function simply say: "Pick one element of X, then pick another, then pick the third."?

Since there are only finite choices, well three actually, then does this mean that I do not have to appeal to the Axiom of Choice?

Could I say that I have defined a choice function without resorting to the axiom of choice?

What if my set is infinite, say the set of all integers? Must I then appeal to the Axiom of choice to define an explicit choice function?

What if my set is infinite, but it is well-ordered? Could I cheat and define a choice function without appealing to the Axiom of Choice?

Basically I want to know when and how to define Choice functions on sets without having to use the Axiom of Choice. Thanks for any help.

2. Sep 25, 2006

### AKG

If you have a finite set, you do not need the choice axiom. If your set is infinite, then it depends. If your set is well-ordered, I don't think that says anything special. On the other hand, if every set in your set is well-ordered, then you don't need the choice axiom, because you can define a function that picks the least element of each set.

3. Sep 25, 2006

### Oxymoron

You're right it doesn't...

Now this is interesting! I read somewhere that the set of integers, $\mathbb{Z}$ is a set of sets, is it not? For example, the integers 0, 1 and 2, etc.. are sets:

$$0 = \emptyset = \{\}$$

$$1 =\{ 0 \} = \{\{\}\}$$

$$2 = 1 \cup \{1\} = \{0\}\cup\{1\} = \{0,1\} = \{\emptyset,\{0\}\} = \{\emptyset,\{\}\}$$

So this means that the integers is a set in which every subset is well-ordered isn't it?

Last edited: Sep 25, 2006
4. Sep 25, 2006

### matt grime

You're confusing the integers with the natural numbers. One is well ordered (every non-empty set has a minimal element) and the other is not.

5. Sep 25, 2006

### Oxymoron

You're right. I simply assumed that the same construction worked for the integers. What fails?

6. Sep 25, 2006

### matt grime

The point about the natural number construction is that you're creating a set of cardinality n to represent n, so how're you going to make a set with cardinality -1? Why would you want to? Anyway, since integers are ordered pairs of natural numbers, I'm sure you could if you felt like it, however they'll never be naturally well ordered, and if you want to well order them you'll need to use the axiom of choice.

Note, there is a mistake in your set construction. You have equated {} with the empty set, so strictly speaking you've written 2={0,{}}={),0}={0}=1. 2 is { {{}},{{{}}}} or { {0} ,{{0}}} or {1,{1}}.

Last edited: Sep 25, 2006
7. Sep 25, 2006

### Oxymoron

For me to be able to define a Choice Function on $\mathbb{Z}$ I need the set to well-ordered non-empty (thus allowing me to pick a least element as AKG said). Now, we were ok with $\mathbb{N}$ because every subset of $\mathbb{N}$, i.e. the natural numbers, are well-ordered subsets themselves. But for the integers - which are ordered pairs of well-ordered subsets, surely I can still pick a least element? Or maybe I cant.

If I consider the reals, $\mathbb{R}$ then I would easily assume that I cannot define a choice function without appealling to the Axiom of Choice for one reason: $\mathbb{R}$ is dense - hence I can always find smaller and smaller numbers.

And if I consider the ordinal number $\omega$ then I should be able to pick a least element - zero, and then choose its successor, and then choose its successor, and so on.

Last edited: Sep 25, 2006
8. Sep 25, 2006

### CRGreathouse

(You're constructing the natural numbers, not the integers.)

Yes, the natural numbers in your construction is a set of sets that are well-ordered by cardinality. You can use this to pick the least element from each of the nonempty sets (0 is not nonempty in your construction). In particular, this will choose the empty set from each positive integer.

9. Sep 25, 2006

### matt grime

I tihnk there are at least two misapprehensions here:

1. density doesn't mean that
2. I can pick smaller and smaller integers too: -2 is smaller than -1.

And in any case, whatever you mean here surely applies to the positive rational numbers, and they are also equivalence classes of pairs of natural numbers. So at least one part of your intuition fails you.

The integers are not naturally well ordered. How are you going to pick out anything at all? Note that they are more than just ordered pairs of naturals, this involves a choice too: they are really equivalence classes of ordered pairs, so -1 corresponds to each of the ordered pairs (0,1), (1,2),(2,3) and so on. Of course there is a way to pick an ordered pair that represents each integer without invoking the axiom of choice - make it minimal in the first component. Thus we can without the AoC choose

(0,r) to represent -r, and

(r,0) to represent r.

but the point is given some colletction of integers how am I going to use this to well order them without a choice?

10. Sep 25, 2006

### AKG

You can define a well-order on Z without the axiom of choice. For example, 0, 1, -1, 2, -2, 3, -3, ... That is, you can come up with a formula in the language of set theory $\phi(x,y)$ which holds iff xRy for some well-order R on Z. The natural order on Z is of course not a well-order.

Any countable set can be well-ordered without the choice axiom. By definition, X is countable iff there exists a bijection f : X to N. Take $\phi(x,y)$ to be f(x)<f(y) and show that this gives a well-order.

Anyways, you were almost right in your calculation of 2, but the last equality was wrong:

$$2 = \{\emptyset,\, \{0\}\} = \{\emptyset,\, \{\emptyset\}\} \neq \{\emptyset,\, \{\}\}$$

and you meant to talk about the naturals, not the integers, as others have pointed out.

Also, I don't know what you mean by dense, but you would probably call the rationals dense, right? Well you can well-order them without the choice axiom, since they are countable.

11. Sep 25, 2006

### sparkster

I think by "smaller and smaller" he meant that given x and y, you can always a z in between, a z' in between x and z, and so on, so that you get smaller and smaller numbers in between.

Also (and I think this has been implied, but not said explicitly), you can well-order any set, as a consequence of the axiom of choice as the two concepts are equivalent, but the ordering won't necessarily be "natural", ie, like the usual ordering we put on $\mathbb{Z}$
or $\mathbb{R}$. And how one would actually construct an ordering on R, I have no idea.

12. Sep 25, 2006

### CRGreathouse

I agree, but I think the question is about what can be done without AC.

13. Sep 25, 2006

### sparkster

Yeah, but when one starts talking about well-orderings, they've already invoked the axiom of choice, whether it's mentioned by name or not.

14. Sep 25, 2006

### matt grime

No, they have not. Sets can be and indeed are well ordered without any invocation of the axiom of choice. Or are you denying that the natural numbers are definable without the axiom of choice?

Indeed, granting AKG's observation is well-orderable without the axiom of choice there is a model of ZF in which the axiom of choice is false and every set is well orderable, perhaps at the expense of passing to a slightly larger model. Perhaps. I'd need to think about that (it is an instance of Skolem's paradox).

Last edited: Sep 25, 2006
15. Sep 25, 2006

### sparkster

Then in what sense are the two equivalent? Only for uncountable sets?

I don't understand how AC can be false and every set is still well-orderable. What happens to all the other things that are equivalent to these statements? Tychonoff, Zorn's lemma, vector space and bases, etc?

Would you use a weaker version of the AC? Maybe the countable axiom of choice? Then maybe you can order, say, $\mathbb{R}$ by ordering the rationals and making an argument about $\mathbb{Q} \subset \mathbb{R}$ is dense?

Last edited: Sep 25, 2006
16. Sep 25, 2006

### CRGreathouse

AC is equivilent to the proposition that all sets can be well-ordered, not that any set has a well-order.

The claims are that $\mathbb{N}$ is well-ordered and $\mathbb{Z}$ has a well-order, not that all sets can be well ordered. As above, this is true iff AC.

17. Sep 25, 2006

### sparkster

I don't see the distinction.

No, Matt Grime said
So I hope you can see where I'm confused. It's always fun to come to this forum. It keeps me from thinking that I actually know some math.

18. Sep 25, 2006

### CRGreathouse

First proposition:
$$\forall S\exists W(S)$$

Second proposition:
$$\exists S\exists W(S)$$

where W(S) denotes a well-ordering of S. The first proposition requires that every set, including, say, $\mathbb{R}$ can be well-ordered; the second just says that some set can be well-ordered. $\mathbb{Z}$ can be well-ordered without AC, even if most sets can't be.

You misunderstood Matt; here's the full quote:

Last edited: Sep 25, 2006
19. Sep 25, 2006

### AKG

No, that's not right. "any" is interpreted as "all", not "some". If I say "f(x) is real for any x" I don't mean that f(x) is real for some x, I mean that f(x) is real for all x. This is not a mathematical issue, it's a matter of interpreting natural language quantifiers as formal language quantifiers, but the standard interpretation is "any" means "all". Of course, it's different if I say, for example, "is there any x such that f(x) is real?" but the statement "any set is well-orderable" is the same as "all sets are well-orderable".
No, he understood Matt, and I believe he's correct in questioning Matt's statement. Matt said, "... there is a model of ZF in which the axiom of choice is false and every set is well orderable.... Perhaps." There is no model of ZF in which the choice axiom is false but every set is well orderable. According to wikipedia:

"It turned out though, that the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with the Zermelo-Fraenkel axioms is sufficient to prove the other."

where:

"The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered."

This tells us two things:

$$\mathcal{Z}\mathcal{F} \cup \{AC\} \vdash WOT$$

$$\mathcal{Z}\mathcal{F} \cup \{WOT\} \vdash AC$$

By the deduction theorem, we get:

$$\mathcal{Z}\mathcal{F} \vdash AC \rightarrow WOT$$

$$\mathcal{Z}\mathcal{F} \vdash WOT \rightarrow AC$$

By logic, we get:

$$\mathcal{Z}\mathcal{F} \vdash WOT \leftrightarrow AC$$

By soundness:

$$\mathcal{Z}\mathcal{F} \models WOT \leftrightarrow AC$$

So every model of ZF models the equivalence (AC iff WOT), i.e. there is no model of ZF in which the equivalence (AC iff WOT) doesn't hold.

20. Sep 25, 2006

### sparkster

Well, I had a reply, but AKG made my points better than I did. But I still wonder if, assuming AC if false, whether it's possible to well order any set as long as it has a countable dense subset. I don't have a proof, but the idea is that we well order the set everywhere, except on a set of measure zero. Would denseness imply that the well-ordering holds for all elements in the set?

Last edited: Sep 25, 2006