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

 

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