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

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

 

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

 

[Oxymoron]

Posted by AKG:

If your set is well-ordered, I don't think that says anything special.

You're right it doesn't...

Posted by AKG:

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.

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?

 

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

 

[Oxymoron]

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

 

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

 

[Oxymoron]

Posted by Matt Grime:

...Anyway, since integers are ordered pairs of natural numbers...

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.

 

[CRGreathouse]

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?

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

 

[matt grime]

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.

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?

 

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

 

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

 

[CRGreathouse]

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

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

 

[sparkster]

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

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.

 

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

 

[sparkster]

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?

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

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

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?

 

[CRGreathouse]

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

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

I don't understand how AC can be false and every set is still well-orderable.

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.

 

[sparkster]

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

I don't see the distinction.

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.

No, Matt Grime said

...there is a model of ZF in which the axiom of choice is false and every set is well orderable...

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.

 

[CRGreathouse]

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

I don't see the distinction.

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:

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

 

[AKG]

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

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

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

You misunderstood Matt; here's the full quote:

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.

 

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

 

[AKG]

I doubt it. The reals have a countable dense subset but I think it's generally believed that a well-ordering on R requires the axiom of choice.

 

[sparkster]

I doubt it. The reals have a countable dense subset but I think it's generally believed that a well-ordering on R requires the axiom of choice.

Any ordering we put on Q won't respect the natural ordering on R. So we'd screw up the topology on R, that is, if < is a well ordering on Q, then, I think, the closure of (Q, <) != R with the usual ordering. So we'd still have the same set, but not with the same structure.

 

[CRGreathouse]

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

I don't think that follows from the context. Matt was responding to this statement from ex-xian:

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.

Matt's response made it clear he was saying that at least one set (he uses the natural numbers) can be well-ordered:

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?

You may be right that Matt was considering the possibility of ~AC + all sets have well orders; I interpreted it differently ("granting AKG's observation...[stuff]" as counterfactual cosideration a la RAA). Certainly, I agree that well-ordering is equivilant to AC; in fact I think you'll see I said as much at least twice in this thread before this post.

 

[AKG]

Any ordering we put on Q won't respect the natural ordering on R. So we'd screw up the topology on R, that is, if < is a well ordering on Q, then, I think, the closure of (Q, <) != R with the usual ordering. So we'd still have the same set, but not with the same structure.

I can't really make sense of what you're saying here, but I guess you're suggesting something like: if there is some topology on R such that it's restriction to Q is the same as an order topology on Q for some well order of Q and such that cl(Q) = R [where this closure is understood to be w.r.t. this topology on R of which we speak], then this topology that we have on R is, or helps us get, a topology induced by a well-order on R.

 

[CRGreathouse]

I can't really make sense of what you're saying here, but I guess you're suggesting something like: if there is some topology on R such that it's restriction to Q is the same as an order topology on Q for some well order of Q and such that cl(Q) = R [where this closure is understood to be w.r.t. this topology on R of which we speak], then this topology that we have on R is, or helps us get, a topology induced by a well-order on R.

That's about what I got from it. Actually, it might just work -- real numbers can be uniquely defined* as the limit of a countable number of rational numbers, which are themselves countable. Thus any well order on Q induces a well-order on R since Q is dense in R. I imagine this uses AC somewhere, probably in the "unique definition" part. Does this work?

* Right? I'm thinking of this in the sense of the way hyperreals are defined.

 

[CRGreathouse]

By the way, when I say "uniqely defined" above, I mean that there is (I hope?) a sequence of rationals that limit toward x for every x, not that there is only one sequence. I guess an unbound use of the word "unique" is really bad form. Clearly there are many sequences for each real number.

Also, I imgine there are problems with this -- it doesn't quite sit right with me. If you can point them out, so much the better.

 

[matt grime]

I did say *in some model* of ZF+not C where all sets are countable. Why did no one pay attention to those three little words at the beginning? Now, you will have to embed the model in a larger one in order to get the bijections between N and all the sets in the model, but that should not be a problem. The well ordering theorem will not be true in either model.

What I think I'm claiming would be true is that there is model of ZF+not C and a submodel whose inclusion is not 'full' (i.e. there are maps between sets of the submodel in the larger model that do not come from the submodel, here I am borrowing a term from category theory), and in which all the sets in the submodel can be well ordered in the larger model.

The idea is pretty much the same as Skolem's paradox: there is a countable model, but simultaneously no-bijection between N and its power set within the model. In fact it is identical to skolem, really, where the analogy is 'a model where every set is countable but cantor's powerset argument is still true.'

 

[sparkster]

That's about what I got from it. Actually, it might just work -- real numbers can be uniquely defined* as the limit of a countable number of rational numbers, which are themselves countable. Thus any well order on Q induces a well-order on R since Q is dense in R. I imagine this uses AC somewhere, probably in the "unique definition" part. Does this work?

* Right? I'm thinking of this in the sense of the way hyperreals are defined.

I must not have been clear. The standard topology on R has open intervels as a basis, so coincides with the order topology on R. Q is dense in R, so cl(Q)=R. But whatever well-ordering we put on Q will not respect the standard ordering. So if we take the closure of Q, with the topology generated by the well-ordering, it will not be R with the usual ordering. Since the ordering on R will be different, we will get a different topological structure. We will still have R, but not the R as the unique ordered field with the supremum property.

So what I suggested above and you repeated won't put a well-ordering on R. The denseness of Q in R depends on their respective topologies, and, thus, on the standard ordering.

 

[AKG]

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. 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. "Q is dense in R" only makes sense in the standard topology, and maybe in some others. In the discrete topology, Q is not dense in R, and cl(Q) = Q.

 

[CRGreathouse]

I must not have been clear. The standard topology on R has open intervels as a basis, so coincides with the order topology on R. Q is dense in R, so cl(Q)=R. But whatever well-ordering we put on Q will not respect the standard ordering. So if we take the closure of Q, with the topology generated by the well-ordering, it will not be R with the usual ordering. Since the ordering on R will be different, we will get a different topological structure. We will still have R, but not the R as the unique ordered field with the supremum property.

So what I suggested above and you repeated won't put a well-ordering on R. The denseness of Q in R depends on their respective topologies, and, thus, on the standard ordering.

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.

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. 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. "Q is dense in R" only makes sense in the standard topology, and maybe in some others. In the discrete topology, Q is not dense in R, and cl(Q) = Q.

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