How Many Choice Functions Exist for Finite and Infinite Sets?

  • Thread starter Thread starter honestrosewater
  • Start date Start date
  • Tags Tags
    Choice Functions
Click For Summary
For a finite set X with n elements, the number of choice functions from the power set of X minus the empty set to X is given by the product of binomial coefficients. The discussion raises the complexity of choice functions when X is infinite, noting that the existence of choice functions can be contingent on the acceptance of the axiom of choice. If the axiom is denied, it is possible to have zero choice functions. However, if at least one choice function exists for a set S with cardinality a, then there must be at least a choice functions. The concept of a choice function is defined as a function that selects an element from each non-empty subset of S.
honestrosewater
Gold Member
Messages
2,133
Reaction score
6
If |X| = n > 0, there are 1C1nC12C1nC2...nC1nCn many choice functions from (power set of X minus empty set) P(X)\{{}} to X?
Just curious. I'm jumping ahead a bit, but that makes sense to me. Is it correct? Is it much more difficult to understand when X is infinite?
 
Physics news on Phys.org
Sounds right.

Infinite sets make things more interesting! For instance, there might be 0 choice functions, if you deny the axiom of choice! Though, if there's at least one choice function on a set S, and S has an element with cardinality a, then there must be at least a choice functions.

By a "choice function on S", I mean a function f:S --> US such that f(x) is in x. Or, equivalently, an element in the cartesian product of all the elements of S.
 

Thread 'Two interesting number theory tricks'

First trick I learned this one a long time ago and have used it to entertain and amuse young kids. Ask your friend to write down a three-digit number without showing it to you. Then ask him or her to rearrange the digits to form a new three-digit number. After that, write whichever is the larger number above the other number, and then subtract the smaller from the larger, making sure that you don't see any of the numbers. Then ask the young "victim" to tell you any two of the digits of the...
View full post »

Similar threads

Undergrad The set of nonzero values of pmf is at most countable
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Countability of binary Strings
  • · Replies 18 ·
Replies
18
Views
3K
Undergrad Thinking about equality of infinite sets
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Question about about halting problem and this particular function
  • · Replies 54 ·
2
Replies
54
Views
6K
The axiom of choice one a finite family of sets.
  • · Replies 5 ·
Replies
5
Views
2K
Axiom of Choice: finite sets to infinite sets
  • · Replies 11 ·
Replies
11
Views
6K
Undergrad Probability: why can we use the Dirac delta function for a conditional pdf?
  • · Replies 12 ·
Replies
12
Views
5K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
4K
Busy Beaver Function: Range of BB Sets
  • · Replies 16 ·
Replies
16
Views
2K
Countably Infinite Set, Axiom of Choice
  • · Replies 2 ·
Replies
2
Views
3K