Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
2.6.4. Part (d): Surjectivity of f
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we'll begin by understanding surjective functions. Can anyone define what a surjective function is?
Is it a function where every element of the codomain has a pre-image in the domain?
Correct! We can remember that surjective functions 'cover' every part of the codomain. Now, what happens if we have a finite set?
If the function is surjective and finite, isn't it also bijective?
Exactly! In finite sets, surjectivity implies bijectivity. Let's note that down: For finite sets, 'SU' implies 'BI' – remember 'SU' for surjective and 'BI' for bijective!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let us explore infinite sets. Can surjectivity imply bijectivity there?
I think I've heard that it doesn’t in infinite cases?
That's right! Here's an example function that illustrates this. If we have a function from {0, 1, 2, …, ∞} to itself defined as f(x) = x - 1 for x > 0, and f(0) = 0, it’s surjective but not injective.
Can you explain what that means?
Sure, it means multiple inputs can give the same output. Hence, it’s not a one-to-one function. 'SURJECTIVE but not INJECTIVE' can be a good phrase to remember!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's discuss equivalence relations now. How does it relate to surjectivity?
Each equivalence relation forms a partition of the original set, right?
Precisely! And if a set A has 30 elements and partitions into 3 subsets of equal size, how do we count ordered pairs in that relation?
I think it's just 10 squared for each subset?
Correct! Since there are 10 elements in each subset, the total ordered pairs will be 3 * 10^2, resulting in 300 total pairs!
Got it! Thanks for connecting that!
Overview
Short Summary
This section focuses on the concept of surjective functions, exploring their characteristics, including conditions under which surjectivity implies bijectivity, particularly in finite and infinite sets.
Medium Summary
The section discusses the definition and characteristics of surjective functions and highlights the distinction between finite and infinite sets regarding bijectivity. A specific counterexample is provided to illustrate that surjectivity alone does not guarantee bijectivity in infinite sets, alongside examples of counting ordered pairs and variations of functions.
Detailed Summary
Detailed Summary
This section covers surjective functions, which are defined as functions where every element in the codomain has at least one pre-image in the domain. A key characteristic discussed is that while a surjective function from a finite set to itself is also bijective, this is not always the case with infinite sets. A specific example demonstrates a surjective function that is not injective, illustrating the concept clearly. Additional insights into equivalence relations, partitions, and the essence of functions from one set to another provide a well-rounded understanding of these mathematical constructs.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountIn question number 6 you are asked to either prove or disprove the following. You are given a function f:A → A and you are given that the function is surjective. Then the question is, is it necessary that the function is a bijective as well.
Detailed Explanation
A surjective function is one where every element in the codomain (set A in this case) has at least one pre-image from the domain. However, the question here asks whether being surjective automatically means that the function is also bijective. A function is bijective if it is both injective (one-to-one) and surjective. Thus, if a function is surjective, it does not necessarily have to be injective, especially if the set A is infinite.
Examples & Analogies
Imagine a group of friends (elements of A) trying to buy drinks from a store. If everyone (surjectivity) buys at least one drink, but some friends buy the same type of drink (not injective), then we don't have a one-to-one mapping of friends to drinks, meaning no distinct drink bought by each friend.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountIt turns out that the statement is true provided your set A is a finite set. Because indeed if the set is a finite set and the function is from the same set to itself and surjective. Then we can show it is a bijective function as well.
Detailed Explanation
For finite sets, if a function from the set to itself is surjective, it must also be injective. This is due to the pigeonhole principle, which states that if you have more items than containers, at least one container must hold more than one item. Therefore, a surjective function in a finite context ensures that every element of the set is covered without any gaps, hence each element must map uniquely which makes it bijective.
Examples & Analogies
Think of a finite set as a basket of eggs where each egg is a distinct item. If you have a limited number of baskets (elements of A) and you ensure that every egg is in a basket (surjective), and you only have as many baskets as there are eggs, then no basket can have more than one egg. Hence every egg has its own basket (bijective).
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountBut the statement need not be true if the set A is an infinite set. So, here is a counterexample. So, imagine the function f given from the set 0 to infinity to the set 0 to infinity.
Detailed Explanation
In this example, consider the function f defined as f(0) = 0 and f(n) = 0 for all natural numbers n > 0. This function is surjective because the only output (codomain) value is 0, which is covered by every input mapping to 0. However, it is not injective, as multiple inputs (like n = 1, n = 2, etc.) map to the same output, causing loss of uniqueness. Therefore, it fails to be bijective.
Examples & Analogies
Imagine a movie theater showing only one movie (the codomain is {movie}). If a gang of friends buys multiple tickets (input elements) but only shows up with one person to watch, they all occupy the same seat (0 as the output). They share the same view (output), making it surjective but not injecting distinct attendance at the show.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Surjectivity:
The property of a function that every element in the codomain has at least one pre-image in the domain.
- Bijectivity:
The property of a function that ensures a one-to-one correspondence between domain and codomain elements.
- Equivalence Relation:
A relation that divides a set into distinct subsets while maintaining the relationship context.
- Ordered Pairs:
A concept used to count relationships in ordered relations.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
Example of a surjective function f: {0, 1, 2, ...} → {0, 1, 2, ...} defined as f(x) = x - 1 for x > 0 and f(0) = 0.
A partition of a set A with 30 elements into 3 subsets, where each subset contributes 10^2 pairs to an equivalence relation.
Memory aids
Imagine a party where every guest must have a dance partner. The partners ensure everyone is paired, showing the essence of surjectivity.
Flash Cards
Glossary
Surjective Function
A function where every element in the codomain has at least one pre-image in the domain.
Bijective Function
A function that is both injective and surjective, meaning each element of the codomain is mapped by exactly one element of the domain.
Infinite Sets
A set that has no end and can be counted indefinitely.
Partition
A division of a set into non-empty, disjoint subsets.
Equivalence Relation
A relation that is reflexive, symmetric, and transitive.