Search   Memberlist   Usergroups
 Page 1 of 1 [6 Posts]
Author Message
Peter Webb
science forum Guru Wannabe

Joined: 05 May 2005
Posts: 192

Posted: Fri Jul 21, 2006 3:28 am    Post subject: Choice function over finite sets

I know this is a stupid question, but I can't get my head around it, or find
anything in Google (presumably because I don't know the appropriate search
term).

I am reasonably confident that I can well order finite sets constructed in
ZF. These are basically just sets comprising the characters "{", "}", and
"," and syntactical rules (brackets must be balanced, elements of sets are
seperated by commas, etc). By finite sets, I means sets representable with a
finite number of these three characters.

However, these sets do not bear much resemblance to the sets discussed in
secondary school, which include sets like {Margaret Thatcher, the rules of
hockey, the colour blue}.

I now create a new set theory ZFP, which (for the sake of simplification)
drops the Axiom of infinity, and adds three new Axioms:

Their exists A = {Margaret Thatcher} (and by this I mean the set containing
the actual ex-Prime Minister of Britian of the same name)
Their exists B = {the rules of hockey}
A does not equal B (to make them distiinguishable within ZFP).

Note that I have not numbered these axioms, as the numbering of an axiom is
a conveneince for discussing it, and not part of ZF (and certainly not part
of ZFP). Axioms themselves are not ordered.

Can we well order (finite) sets in ZFP without AC?

This breaks down to establishing an order on "A"and "B", for example A < B <
{} so that A, and B are effectively -2, and -1, or similar.

However, to do this we must choose one of "A"and "B" to be the lowest. How
do we do this without an axiom of finite choice, allowing us to choose an
element of the set {A, B} to be the lowest? I cannot conceive of an explicit
choice function over {{Margaret Thatcher} , {the rules of hockey}}.
Certainly I could define A< B, but this still requires us to choose an A and
B for this definition to work. In the absence of some indicator in the
axioms of the explicit order, I can't see how to do this without just
choosing an order (creating a choice function).

It seems unfortunate and unlikely that adding three Axioms stating the
existence of different two sets {Margaret Thatcher} and {the rules of
hockey} requires the creation of either an explicit order function or an
explicit finite choice Axiom to order. Indeed, even adding a single
additional Axiom would seem to suffice, as the set it defines needs to be
ordered with respect to {}.

This really boils down to the following issue. I am thinking of an element
of {{Margaret Thatcher}, {the rules of hockey}}. You can't ask me a question
(a choice function) which identifies which element I am thinking of without
asking "Is it {Margaret Thatcher} or is it {the rules of hockey}", which
itself requires choice.

Wkipedia doesn't seem to think it is a problem; in
http://en.wikipedia.org/wiki/Axiom_of_choice they state:

"Not every situation requires the axiom of choice. For finite sets X, the
axiom of choice follows from the other axioms of set theory. In that case it
is equivalent to saying that if we have several (a finite number of) boxes,
each containing at least one item, then we can choose exactly one item from
each box. Clearly we can do this: We start at the first box, choose an item;
go to the second box, choose an item; and so on. There are only finitely
many boxes, so eventually our choice procedure comes to an end. "
This seems completely circular to me. How do they "choose" the first box
without a choice function?

Axiom of Finite Choice for us to well order finite sets which are

Adding a countably infinite numer of axioms of the form: There exists {"x"},
there exists {"xx"}, there exists {"xxx"}, ... would also seem to require an
Axiom of Countable choice to allow well ordering.

Am I missing something here, or is this just how it is?
Rupert
science forum Guru

Joined: 18 May 2005
Posts: 372

Posted: Fri Jul 21, 2006 3:53 am    Post subject: Re: Choice function over finite sets

Peter Webb wrote:
 Quote: I know this is a stupid question, but I can't get my head around it, or find anything in Google (presumably because I don't know the appropriate search term). I am reasonably confident that I can well order finite sets constructed in ZF. These are basically just sets comprising the characters "{", "}", and "," and syntactical rules (brackets must be balanced, elements of sets are seperated by commas, etc). By finite sets, I means sets representable with a finite number of these three characters. However, these sets do not bear much resemblance to the sets discussed in secondary school, which include sets like {Margaret Thatcher, the rules of hockey, the colour blue}. I now create a new set theory ZFP, which (for the sake of simplification) drops the Axiom of infinity, and adds three new Axioms: Their exists A = {Margaret Thatcher} (and by this I mean the set containing the actual ex-Prime Minister of Britian of the same name) Their exists B = {the rules of hockey} A does not equal B (to make them distiinguishable within ZFP).

To state these new axioms you would have to extend the language,
introducing constants for Margaret Thatcher and the rules of hockey.
Another issue would be that Margaret Thatcher and the rules of hockey
are distinct objects which have no members, so the axiom of
extensionality would need modification. The usual approach is to
introduce a predicate that says "x is an individual", and restrict the
axiom of extensionality to those objects that are not individuals.

 Quote: Note that I have not numbered these axioms, as the numbering of an axiom is a conveneince for discussing it, and not part of ZF (and certainly not part of ZFP). Axioms themselves are not ordered. Can we well order (finite) sets in ZFP without AC?

Yes, I would think so. It is pretty easy to prove in ZF that finite
sets are well-ordered, by induction on the number of elements. The
axiom of infinity is not necessary for the proof.

 Quote: This breaks down to establishing an order on "A"and "B", for example A < B {} so that A, and B are effectively -2, and -1, or similar.

Oh, did you mean can we well-order the class of finite sets? We can
definitely well-order the class of hereditarily finite sets, but we
wouldn't be able to prove that the class of finite sets can be
well-ordered, because this would easily imply that every set can be
well-ordered.

 Quote: However, to do this we must choose one of "A"and "B" to be the lowest. How do we do this without an axiom of finite choice, allowing us to choose an element of the set {A, B} to be the lowest?

The axiom of choice is provable for finite families of sets.

 Quote: I cannot conceive of an explicit choice function over {{Margaret Thatcher} , {the rules of hockey}}.

{Margaret Thatcher} -> Margaret Thatcher, {the rules of hockey} -> the
rules of hockey.

 Quote: Certainly I could define A< B, but this still requires us to choose an A and B for this definition to work.

Well, if you've got different constant symbols referring to the A and B
this shouldn't be a problem...

 Quote: In the absence of some indicator in the axioms of the explicit order, I can't see how to do this without just choosing an order (creating a choice function).

There are two different possible orders and we can choose either one of
them.

 Quote: It seems unfortunate and unlikely that adding three Axioms stating the existence of different two sets {Margaret Thatcher} and {the rules of hockey} requires the creation of either an explicit order function or an explicit finite choice Axiom to order. Indeed, even adding a single additional Axiom would seem to suffice, as the set it defines needs to be ordered with respect to {}. This really boils down to the following issue. I am thinking of an element of {{Margaret Thatcher}, {the rules of hockey}}. You can't ask me a question (a choice function) which identifies which element I am thinking of without asking "Is it {Margaret Thatcher} or is it {the rules of hockey}", which itself requires choice.

Why does it require choice? Both of those sets can be defined.

 Quote: Wkipedia doesn't seem to think it is a problem; in http://en.wikipedia.org/wiki/Axiom_of_choice they state: "Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. There are only finitely many boxes, so eventually our choice procedure comes to an end. " This seems completely circular to me. How do they "choose" the first box without a choice function?

They're talking a bit loosely here. What you have to do is prove it by
induction on the number of boxes.

 Quote: Does adding a single Axiom adding a single additional set to ZF demand an Axiom of Finite Choice for us to well order finite sets which are constructed using this additional set?

Note that I'm assuming you actually have a constant symbol to refer to
the set. If this isn't what you had in mind then I'd have to ask you to
specify what you had in mind a bit more carefully.

 Quote: Adding a countably infinite numer of axioms of the form: There exists {"x"}, there exists {"xx"}, there exists {"xxx"}, ... would also seem to require an Axiom of Countable choice to allow well ordering. Am I missing something here, or is this just how it is?

I think we need to be a bit more careful about what question you're
asking here. Specify in more detail the extensions of ZF that you're
considering.
Stuart M Newberger
science forum Guru Wannabe

Joined: 03 May 2005
Posts: 129

Posted: Fri Jul 21, 2006 4:01 am    Post subject: Re: Choice function over finite sets

Peter Webb wrote:
 Quote: I know this is a stupid question, but I can't get my head around it, or find anything in Google (presumably because I don't know the appropriate search term). I am reasonably confident that I can well order finite sets constructed in ZF. These are basically just sets comprising the characters "{", "}", and "," and syntactical rules (brackets must be balanced, elements of sets are seperated by commas, etc). By finite sets, I means sets representable with a finite number of these three characters. However, these sets do not bear much resemblance to the sets discussed in secondary school, which include sets like {Margaret Thatcher, the rules of hockey, the colour blue}. I now create a new set theory ZFP, which (for the sake of simplification) drops the Axiom of infinity, and adds three new Axioms: Their exists A = {Margaret Thatcher} (and by this I mean the set containing the actual ex-Prime Minister of Britian of the same name) Their exists B = {the rules of hockey} A does not equal B (to make them distiinguishable within ZFP). Note that I have not numbered these axioms, as the numbering of an axiom is a conveneince for discussing it, and not part of ZF (and certainly not part of ZFP). Axioms themselves are not ordered. Can we well order (finite) sets in ZFP without AC? This breaks down to establishing an order on "A"and "B", for example A < B {} so that A, and B are effectively -2, and -1, or similar. However, to do this we must choose one of "A"and "B" to be the lowest. How do we do this without an axiom of finite choice, allowing us to choose an element of the set {A, B} to be the lowest? I cannot conceive of an explicit choice function over {{Margaret Thatcher} , {the rules of hockey}}. Certainly I could define A< B, but this still requires us to choose an A and B for this definition to work. In the absence of some indicator in the axioms of the explicit order, I can't see how to do this without just choosing an order (creating a choice function). It seems unfortunate and unlikely that adding three Axioms stating the existence of different two sets {Margaret Thatcher} and {the rules of hockey} requires the creation of either an explicit order function or an explicit finite choice Axiom to order. Indeed, even adding a single additional Axiom would seem to suffice, as the set it defines needs to be ordered with respect to {}. This really boils down to the following issue. I am thinking of an element of {{Margaret Thatcher}, {the rules of hockey}}. You can't ask me a question (a choice function) which identifies which element I am thinking of without asking "Is it {Margaret Thatcher} or is it {the rules of hockey}", which itself requires choice. Wkipedia doesn't seem to think it is a problem; in http://en.wikipedia.org/wiki/Axiom_of_choice they state: "Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. There are only finitely many boxes, so eventually our choice procedure comes to an end. " This seems completely circular to me. How do they "choose" the first box without a choice function? Does adding a single Axiom adding a single additional set to ZF demand an Axiom of Finite Choice for us to well order finite sets which are constructed using this additional set? Adding a countably infinite numer of axioms of the form: There exists {"x"}, there exists {"xx"}, there exists {"xxx"}, ... would also seem to require an Axiom of Countable choice to allow well ordering. Am I missing something here, or is this just how it is?

Hi,well if you have a non empty set E ,ie there exists x belonging to
E then the predicate calculus from logic allows you to say choose a
name,say "b" by saying choose b belonging to E.Thus the axiom of
choice for one set is a theorem of logic which is why its never
mentioned .For finite sets ,the existance of a choice function follows
by mathematical induction on the number of elements in your set which
you need and have in ZF when you develop the theory of finite sets
..Well ordering of finite sets is also by induction.When speking of the
language and creating sets with brackets you need to assume
mathematical induction to prove anything as logicians always do when
discussing metamathematical theorems.Regards,smn
Peter Webb
science forum Guru Wannabe

Joined: 05 May 2005
Posts: 192

Posted: Fri Jul 21, 2006 4:20 am    Post subject: Re: Choice function over finite sets

 Quote: I think we need to be a bit more careful about what question you're asking here. Specify in more detail the extensions of ZF that you're considering.

Three new axioms:

Exists A = {a}
Exists B={b}
x element A => x not element B

How are you going to order A and B without a finite choice Axiom (or an
explicit order as an Axiom)?
Rupert
science forum Guru

Joined: 18 May 2005
Posts: 372

Posted: Fri Jul 21, 2006 4:35 am    Post subject: Re: Choice function over finite sets

Peter Webb wrote:
 Quote: I think we need to be a bit more careful about what question you're asking here. Specify in more detail the extensions of ZF that you're considering. Three new axioms: Exists A = {a}

Is a a new constant which you're introducing into the language? Or are
you just saying there exists a singleton A? That can be proved in ZF
anyway.

 Quote: Exists B={b} x element A => x not element B

You could introduce two new constants a and b and introduce a new axiom
saying a!=b. Then the assertions that there are singletons {a} and {b}
could be proved. We can then prove the existence of an ordering of
{A,B} in which A<B, and also of an ordering in which B<A. There is no
problem.

If you don't want to introduce new constants, then all you have to do
is say there exist singletons A and B which are different. That can be
proved in ZF (without the axiom of infinity). Then we can prove in ZF
(without the axiom of infinity) that for all such A and B there exists
an ordering of {A,B} in which A<B and also an ordering in which B<A.
There is no problem.

It is easy to prove in ZF (without the axiom of infinity) that all
finite sets can be well-ordered. One does it by induction on the number
of elements.

 Quote: How are you going to order A and B without a finite choice Axiom (or an explicit order as an Axiom)?
Peter Webb
science forum Guru Wannabe

Joined: 05 May 2005
Posts: 192

Posted: Fri Jul 21, 2006 1:44 pm    Post subject: Re: Choice function over finite sets

"Rupert" <rupertmccallum@yahoo.com> wrote in message
 Quote: Peter Webb wrote: I think we need to be a bit more careful about what question you're asking here. Specify in more detail the extensions of ZF that you're considering. Three new axioms: Exists A = {a} Is a a new constant which you're introducing into the language? Or are you just saying there exists a singleton A? That can be proved in ZF anyway. Exists B={b} x element A => x not element B You could introduce two new constants a and b and introduce a new axiom saying a!=b. Then the assertions that there are singletons {a} and {b} could be proved.

That effectively exactly what I have done (I considered sets {a} and {b},
rather than constants a and b)

 Quote: It is easy to prove in ZF (without the axiom of infinity) that all finite sets can be well-ordered. One does it by induction on the number of elements.

This part I have trouble with. How do you choose the element corresponding
to n+1 ?

 Quote: How are you going to order A and B without a finite choice Axiom (or an explicit order as an Axiom)?

Let me get a little more specific.

I can easily provide an explicit choice function for a finite set of Natural
numbers, say choose the smallest of the set. If I think of a finite set of
numbers, you can always choose one in this manner. You have an explicit
choice function.

Now I give you ZFP, which is
ZFP = ZF + exists {a} + exists {b}

Now a and b are just symbols of course, for things like a specific
rhinoserous in the Adelaide zoo, through to things like the rules of hockey.

Lets say I know what a and b really are. Now, ask me for one of these in a
way that allows me to identify which one you want (a choice function). I
pick a=Chaitans number (the actual number), and b="My mental image of the
best way from the city to the airport". How do you make me choose between
these? On the basis of the minimum number of English language characters in
my description? I'm not sure how I would describe fully my route to the
airport, and if the listener doesn't know what set theory is, then the
description of Chaitans constant may take a little longer.

OK, but can't I just say is it a or b ? After all, a and b are defined to
exist as Axioms. Similar problem occurs.

The problem is best shown by considering two slightly different Axiom sets:

Here is a structure I will call ZFP'

Axioms 1 to 8: the same as ZF.
Axiom 9: Exists {a}
Axiom 10: Exists {b}

I can give you a finite choice function for this set. Scan down the Axioms
in order until you find an existence definition of the form "Exists
{symbol}" We find this on the ninth Axiom, Exists {a}. So you have what you
need for a choice function - you can say "Is it {a}"

Here is ZFP, as I construct it.

Axioms 1 to 8: the same as ZF.
Exists {a}
Exists {b}

The only difference is the two new Axioms are not numbered. Indeed, I don't
believe any of the Axioms in ZF are actually numbered; its just a notational
convenience. Now, you want to ask me a question of the form Exists{symbol}.
How are you going to choose which one is Axiom 9? Just choose one and make
it Axiom 9? How?

The problem completely goes away if the axioms are numbered, because
choosing one which is Exists {a} is simply finding the lowest Axiom number
in which it appears. But this is by explicitly encoding an order on {a} and
{b} in the Axioms. The Axioms of ZF are not actually numbered canonically;
the numbers are as I said before are a notational convenience in every
context I have seen them. Nor are my two new Axioms Exists{a} and Exists{b}.
Unless we have an Axiom of Finite choice, I cannot see how to choose between
them.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [6 Posts]
 The time now is Sat Apr 20, 2019 2:43 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Generating function for Mathieu functions cosmicstring@gmail.com Math 1 Fri Jul 21, 2006 8:39 am Adding 2 sets of roll/pitch/yaw Dan111 Math 1 Thu Jul 20, 2006 9:33 pm Finite fields and Splitting fields vedmundson@hotmail.com Math 8 Thu Jul 20, 2006 6:35 pm Function from Taylor series? Nathan Urban Research 1 Thu Jul 20, 2006 12:48 am Function not in L_1 {[0,1]}, but satisfies ...? atkrunner@hotmail.com Math 12 Thu Jul 20, 2006 12:46 am