PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
choice function (Definition)

A choice function on a set $ S$ is a function $ f$ with domain $ S$ such that $ f(x)\in x$ for all $ x\in S$.

A choice function on $ S$ simply picks one element from each member of $ S$. So in order for $ S$ to have a choice function, every member of $ S$ must be a nonempty set. The Axiom of Choice (AC) states that every set of nonempty sets does have a choice function.

Without AC the situation is more complicated, but we can still show that some sets have a choice function. Here are some examples:

  • If $ S$ is a finite set of nonempty sets, then we can construct a choice function on $ S$ by picking one element from each member of $ S$. This requires only finitely many choices, so we don't need to use AC.
  • If every member of $ S$ is a well-ordered nonempty set, then we can pick the least element of each member of $ S$. In this case we may be making infinitely many choices, but we have a rule for making the choices, so AC is not needed. The distinction between “well-ordered” and “well-orderable” is important here: if the members of $ S$ were merely well-orderable, we would first have to choose a well-ordering of each member, and this might require infinitely many arbitrary choices, and therefore AC.
  • If every member of $ S$ is a nonempty set, and the union $ \cup S$ is well-orderable, then we can choose a well-ordering for this union, and this induces a well-ordering on every member of $ S$, so we can now proceed as in the previous example. In this case we were able to well-order every member of $ S$ by making just one choice, so AC wasn't needed. (This example shows that the Well-Ordering Principle, which states that every set is well-orderable, implies AC. The converse is also true, but less trivial -- see the proof.)



"choice function" is owned by yark.
(view preamble)

View style:

See Also: axiom of choice, axiom of countable choice, Hausdorff paradox, proof of Hausdorff paradox, one-to-one function from onto function

Keywords:  choice

Attachments:
one-to-one function from onto function (Definition) by mathcam
Log in to rate this entry.
(view current ratings)

Cross-references: converse, implies, well-ordering principle, induces, union, well-ordering, least element, well-ordered, finite set, function
There are 12 references to this entry.

This is version 8 of choice function, born on 2004-10-25, modified 2005-12-01.
Object id is 6419, canonical name is ChoiceFunction.
Accessed 3202 times total.

Classification:
AMS MSC03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)