Surjective functions from a set of size n+3 to a size of n

In summary: Your Name]In summary, the question of how many surjective functions exist from a set of size n+3 to a set of size n has been answered. The answer is n(2^(n+3)) + (n+3). 2^n, which can be verified by considering all possible choices for the elements in the smaller set and finding a function that maps onto each element in the larger set. While there are multiple ways to approach and solve this problem, as long as the proof is logically sound and can be verified, it is considered valid.
  • #1
Ciaran
72
0
Hello,

I wonder if anyone could settle a disagreement I'm having with one of my peers. The question is 'How many surjective functions are there from a set of size n+3 to a set of size n?'. Now, I've already proven that there are (n+1 choose 2)n! surjective functions from a set of size n+1 to a set of size n. I've also proven that there are (n+2 choose 3)n!+ (n+2 choose n-2,2,2)n! surjective functions from a set of size n+2 to a set of size n.

Now, for the question in hand, I got that there would be n(2^(n+3)) + (n+3). 2^n such functions. Am I right? He doesn't believe me because I proved it in a different way to the other ones. This time, my proof did not involve any x choose y statements; I derived a kind of formula because I found the potential choices too complicated. Also, would anyone be able to construct such a proof? This is solely for my peace of mind- I'd like my three proofs to be of a similar looking nature!

Thanks!
 
Physics news on Phys.org
  • #2

Thank you for your question. I understand your concern about wanting your proofs to have a similar structure. However, in mathematics, there are often multiple ways to approach and solve a problem. As long as your proof is logically sound and can be verified, it is considered valid.

In terms of your specific question about the number of surjective functions from a set of size n+3 to a set of size n, your answer of n(2^(n+3)) + (n+3). 2^n is correct. This can be verified by considering all possible choices for the elements in the smaller set and finding a function that maps onto each element in the larger set.

If you would like to construct a proof using x choose y statements, it is certainly possible. However, it is not necessary and may not be the most efficient method. As long as your proof can be easily understood and verified, it is acceptable.

I hope this helps settle the disagreement with your peer. Remember, mathematics is about finding the most logical and efficient way to solve a problem, not about following a specific structure. Keep up the good work in your studies!

 

1. What is a surjective function?

A surjective function is a function where every element in the output set has at least one corresponding element in the input set. In other words, every element in the output set is mapped to by at least one element in the input set. This is also known as being "onto".

2. How do you determine if a function is surjective?

To determine if a function is surjective, you need to check if every element in the output set has at least one corresponding element in the input set. This can be done by inspecting the function's graph or by using algebraic methods.

3. Can a function be both surjective and injective?

Yes, a function can be both surjective and injective. This type of function is called a bijective function. In a bijective function, every element in the output set is mapped to by exactly one element in the input set.

4. What is the difference between a surjective function and a bijective function?

The main difference between a surjective function and a bijective function is that a surjective function does not necessarily have a one-to-one correspondence between the input and output sets. In other words, multiple elements in the input set can map to the same element in the output set. A bijective function, on the other hand, has a one-to-one correspondence between the input and output sets.

5. Can a function be surjective if the input set is larger than the output set?

No, a function cannot be surjective if the input set is larger than the output set. In order for a function to be surjective, every element in the output set must have at least one corresponding element in the input set. If the input set is larger than the output set, there will be elements in the output set that do not have a corresponding element in the input set, making the function not surjective.

Similar threads

I When does ## { n \choose k } ## represent set of lists?
    • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
I Create a surjective function from [0,1]^n→S^n
    • Topology and Analysis
Replies
8
Views
1K
I Cardinality of decreasing functions from N to N
    • Set Theory, Logic, Probability, Statistics
Replies
19
Views
2K
I What is the Definition and Understanding of Surjective Functions?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
853
MHB Proving Existence of Surjective Function F from P(N)\N to P(N)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
A What is the Probability of Sampling a Set with a Certain Size?
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
Does there exist a surjection from the natural numbers to the reals?
    • Precalculus Mathematics Homework Help
Replies
4
Views
2K
MHB Upper Bound of Sets and Sequences: Analyzing Logic
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I Missing(?) rigor in proof involving countable union of countable sets
    • Set Theory, Logic, Probability, Statistics
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top