Proving the Number of Functions from X to Y

  • Thread starter adarshtr
  • Start date
  • Tags
    Functions
In summary, the number of functions from set X to set Y, where n(X)=p and n(Y)=q, is q^p. To prove this, consider an element of X and the number of choices for its image in Y. The maximum number of elements in the function is p*q, and all other functions are subsets of this. The total number of subsets of this relation is 2^mn, but for it to be a function, all elements of X must be included in the ordered pairs. Using combinations, it is difficult to reach the result of q^p. Instead, it is easier to see that the number of choices for an element's image is q, and the total number of chances is q*q
  • #1
adarshtr
4
0
n(X)=p and n(Y)=q then the no. of function from X-> Y is q^p , how do u prove this ?
 
Physics news on Phys.org
  • #2
Show your work so far and we can be of more help. As a hint, consider an element of X; how many choices are there for its image?
 
  • #3
Ok , Here is what I've tried to do ,

the the function with max. no. of elements from these 2 sets should be a many-one on-to function right ? The no. of elements in that set(function) should be p*q(if the no of elements in 1st set is p and 2nd is q) , and i think that all other functions from these 2 sets should be subsets of this.

Considering this as a relation (and not a function) the no. subsets should be 2^mn . but for this relation to be a function there should be all the elements of set X in the ordered pairs which are the elements of the relation .

But using this logic and using cobinations I can't seem to get to the result q^p
 
  • #4
You might find it easier to start with my previous suggestion: Take an element of X; how many choices are there for its image in Y?
 
  • #5
Oh , didn't realize that this was this simple :( , so the no. chances of images for an element is q ,so the total no. of chances is q*q*q...*q p times . Thanks for the help
 

FAQ: Proving the Number of Functions from X to Y

1. What does "No. of functions from X to Y" mean?

"No. of functions from X to Y" refers to the number of possible ways to map elements from a set X to a set Y. In other words, it represents the total number of functions that can be defined from X to Y.

2. How is the number of functions from X to Y calculated?

The number of functions from X to Y can be calculated using the formula: |Y|^|X|, where |X| represents the cardinality (number of elements) of set X and |Y| represents the cardinality of set Y. This formula is based on the concept of Cartesian product, where for each element in X, there are |Y| possible choices for its mapping in Y.

3. Can there be a different number of functions from X to Y for different sets X and Y?

Yes, the number of functions from X to Y can vary depending on the cardinalities of sets X and Y. For example, if X has 3 elements and Y has 2 elements, there will be 8 possible functions from X to Y. However, if X has 2 elements and Y has 3 elements, there will be only 4 possible functions from X to Y.

4. What is the maximum number of functions from X to Y?

The maximum number of functions from X to Y is infinite if both sets X and Y are infinite. This is because for each element in X, there are infinite possible choices for its mapping in Y. However, if both sets are finite, the maximum number of functions is equal to |Y|^|X|.

5. Can the number of functions from X to Y be zero?

Yes, the number of functions from X to Y can be zero if set Y is empty, as there will be no possible mappings from X to Y. However, if both sets are non-empty, the minimum number of functions is 1, as each element in X must have at least one mapping in Y.

Similar threads

I Understanding extinction probability in simple GWP
Replies
1
Views
509
I Is this conditional expectation identity true?
Replies
1
Views
741
  • Poll
A How to change the support of a probability density function?
Replies
4
Views
2K
I Proof request for best linear predictor
Replies
1
Views
650
I How to obtain moment bound from the importance sampling identity?
Replies
1
Views
1K
MHB Converting Numbers Between Different Bases: Is It Possible to Use Only n Digits?
Replies
9
Views
1K
A Proving Lim F(x,y) is the Distribution Function for X
Replies
1
Views
1K
I Expected number of random variables that must be observed
Replies
3
Views
1K
A Covariance of Posterior Predictive Distribution
Replies
1
Views
1K
Chernoff Bounds using importance sampling identity
Replies
0
Views
1K

Hot Threads

Recent Insights

Back
Top