How many choice functions?

[honestrosewater]

If |X| = n > 0, there are 1C1^nC12C1^nC2...nC1^nCn 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?

 

[Hurkyl]

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.

 

[tacman]

Yes, your understanding is correct. The number of choice functions from a power set of X (minus the empty set) to X is equal to nC1 * nC2 * ... * nCn, where n is the cardinality of X. This is because for each element in the power set, there are n possible choices to map it to in X, and since there are n elements in the power set, the total number of possible choice functions is the product of these choices.

When X is infinite, the concept of choice functions becomes more complex. In this case, the number of choice functions is equal to the cardinality of the set of all functions from the power set of X to X. This set is typically denoted as 2^X, and its cardinality is equal to 2^|X| (since for each element in the power set, there are 2 choices - to map it to an element in X or not to map it at all). Therefore, when X is infinite, the number of choice functions is much larger than when X is finite.