Proving the Number of Functions from X to Y

  • Context: Undergrad 
  • Thread starter Thread starter adarshtr
  • Start date Start date
  • Tags Tags
    Functions
Click For Summary

Discussion Overview

The discussion revolves around proving the formula for the number of functions from a set X to a set Y, where the number of elements in X is denoted as p and in Y as q. The focus is on understanding the reasoning behind the formula q^p, exploring different approaches to the proof, and addressing challenges faced in deriving this result.

Discussion Character

  • Exploratory, Technical explanation, Homework-related, Mathematical reasoning

Main Points Raised

  • One participant states that if n(X)=p and n(Y)=q, then the number of functions from X to Y is q^p and seeks a proof for this assertion.
  • Another participant suggests starting with an element of X to determine how many choices exist for its image in Y, hinting at a foundational approach to the proof.
  • A participant proposes that the function with the maximum number of elements should be a many-one onto function, suggesting that the number of elements in the function should be p*q, and considers the implications of treating the relation as a function.
  • There is a mention of subsets and combinations, with a participant expressing difficulty in reaching the result q^p using their logic.
  • In a later reply, a participant acknowledges the simplicity of the problem, realizing that each element of X has q choices for its image in Y, leading to a total of q multiplied by itself p times.

Areas of Agreement / Disagreement

The discussion shows a progression of understanding, with some participants agreeing on the basic premise of the number of choices for images, while others express uncertainty in their reasoning. No consensus is reached on a formal proof, and multiple approaches are presented.

Contextual Notes

Participants express limitations in their understanding of the relationship between functions and relations, and the implications of subsets in the context of proving the formula. There are unresolved mathematical steps in the reasoning presented.

Who May Find This Useful

This discussion may be useful for students or individuals interested in combinatorial mathematics, particularly those studying functions and relations in set theory.

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
 

Similar threads

Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad What Are the Axioms of Fuzzy Logic and How Do They Extend Boolean Algebra?
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Is this conditional expectation identity true?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proof request for best linear predictor
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad How to obtain moment bound from the importance sampling identity?
  • · Replies 1 ·
Replies
1
Views
2K
  • Poll Poll
Graduate How to change the support of a probability density function?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Expected number of random variables that must be observed
  • · Replies 3 ·
Replies
3
Views
2K
MHB Converting Numbers Between Different Bases: Is It Possible to Use Only n Digits?
  • · Replies 9 ·
Replies
9
Views
2K
Graduate Proving Lim F(x,y) is the Distribution Function for X
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Question about about halting problem and this particular function
  • · Replies 54 ·
2
Replies
54
Views
7K