How many choice functions?

In summary, for a set X with n elements, there are nC1*nC2*...*nCn choice functions from the power set of X minus the empty set to X. This concept becomes even more interesting when X is infinite, as there may be 0 or an infinite number of choice functions depending on the axiom of choice. However, if there is at least one choice function on a set S with an element of cardinality a, there must be at least a choice functions on S.
  • #1

honestrosewater

Gold Member
2,142
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
  • #2
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.
 
  • #3


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.
 
1.

What is a choice function?

A choice function is a mathematical concept that assigns a single element from a set of options as the "chosen" element. It is often used in decision making and optimization problems.

2.

How many choice functions are there?

The number of choice functions depends on the size of the set of options. For a set with n elements, there are 2^n possible choice functions.

3.

How do you determine the number of choice functions for a given set?

To determine the number of choice functions for a set with n elements, you can use the formula 2^n. For example, a set with 3 elements has 2^3 = 8 possible choice functions.

4.

What is the difference between a single-valued and a multi-valued choice function?

A single-valued choice function only assigns one element as the "chosen" element for a set of options. A multi-valued choice function can assign multiple elements as the "chosen" elements.

5.

Can choice functions be used in real-world applications?

Yes, choice functions have various applications in fields such as economics, computer science, and social sciences. They can be used in decision making, resource allocation, and optimization problems.

Suggested for: How many choice functions?

Replies
7
Views
862
Replies
4
Views
933
Replies
7
Views
1K
Replies
19
Views
2K
Replies
2
Views
775
Replies
41
Views
3K
Replies
5
Views
1K
Back
Top