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

Back to top 


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 exPrime 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 wellordered, 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 wellorder the class of finite sets? We can
definitely wellorder the class of hereditarily finite sets, but we
wouldn't be able to prove that the class of finite sets can be
wellordered, because this would easily imply that every set can be
wellordered.
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. 

Back to top 


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 exPrime 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 

Back to top 


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

Back to top 


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


Back to top 


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
news:1153456507.851150.302870@b28g2000cwb.googlegroups.com...
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 wellordered. 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. 

Back to top 


Google


Back to top 



The time now is Tue Jul 17, 2018 3:03 pm  All times are GMT

