Proving the Number of Functions from X to Y

  • Thread starter Thread starter adarshtr
  • Start date Start date
  • Tags Tags
    Functions
AI Thread Summary
To prove the number of functions from set X to set Y, where n(X) = p and n(Y) = q, the key is to consider each element of X and its possible images in Y. Each element in X has q choices for its image in Y, leading to a total of q^p combinations when considering all p elements in X. The initial confusion stemmed from misinterpreting the relationship between functions and relations, but recognizing that each element independently contributes to the total count clarifies the result. Therefore, the number of functions from X to Y is indeed q^p. This understanding simplifies the proof significantly.
adarshtr
Messages
4
Reaction score
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
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?
 
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
 
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?
 
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
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top