Surjective and Bijective Functions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 2.8 Free with a free account

Surjective and Bijective Functions

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.8 · lesson 16 of 879 min · free with a free account

← Injective Functions: One-to-One Mappings and Their PropertiesNext lesson: Introduction to Sequences →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Every slot used, nothing left over - and a function you can run backwards.

  • Define a surjective (onto) function
  • Define a bijection as injective and surjective together
  • Prove that an inverse exists exactly for bijections
  • Connect bijections to equal cardinality - and avoid the converse trap

Transcript

Everything said in the video, section by section (1,287 words). Read along, or search it.

Set Theory and Functions

Surjective and Bijective Functions

This last section of chapter two adds a new property of functions, and then combines it with injectivity. We'll define surjective, or onto, functions, and bijections, which are injective and surjective together. We'll prove exactly when a function can be run backwards. And we'll connect bijections to the sizes of sets, while avoiding a tempting trap.

The Opening Problem

A Migration That Can't Lose a Record

A software team is migrating a legacy system's user records into a new database, with a fresh ID scheme. Every one of the old system's one hundred thousand record IDs must map to exactly one new ID. That's just what it means for the remapping to be a function. But leadership has a sharper requirement. The new system has exactly one hundred thousand ID slots, and every single one must end up assigned to a migrated record. An empty slot would mean a record silently vanished during migration. That's exactly the kind of bug a migration can't afford. And once that property and injectivity hold together, the migration gains something for free. Engineers can run it backwards on demand, taking any new ID and recovering which old record produced it. Exactly what an audit or a rollback needs.

Definition 2.8.1

Surjective, or Onto

For a function f from A to B, every output is automatically in the codomain B. That's built into what a function is. What isn't automatic is whether every element of B actually gets used as an output. A function is surjective, or onto, if every element of B has at least one preimage in A. For every b in B, there's at least one a with f of a equal to b. Equivalently, f is surjective exactly when its range equals the whole codomain, rather than merely being a subset of it.

Table 2.8.1

A First Attempt: 4 Records, 5 Slots

Here's a first attempt at the migration, with four old IDs and five new slots, one over-provisioned. One oh one maps to slot two, one oh two to slot five, one oh three to slot one, and one oh four to slot four. Check every slot. Slots one, two, four, and five each have a preimage. But slot three has none. So f is not surjective. A slot was left empty. Notice what this does and doesn't say. The outputs, two, five, one, and four, are all different. So f is perfectly injective. Injectivity says no slot gets hit twice. It says nothing about whether every slot gets hit. A function can have one property without the other. Here, one extra, unused slot is exactly what keeps an otherwise well-behaved function from being surjective.

Table 2.8.2

Corrected: 4 Records, 4 Slots

Now remove the extra slot, so there are exactly four slots for the four old records. Define g. One oh one maps to three, one oh two to one, one oh three to four, and one oh four to two. Check every slot. Slot one comes from one oh two. Slot two from one oh four. Slot three from one oh one. And slot four from one oh three. Every slot has a preimage, in fact exactly one. So g is surjective.

Definition 2.8.2

Bijective: Both at Once

A function is bijective, or a bijection, if it's both injective and surjective. A bijection is also called a one-to-one correspondence. It pairs every element of A with a unique element of B, and every element of B with a unique element of A. Nothing on either side is left unpaired. The corrected migration g is bijective. Its table already confirms it's surjective. And its outputs, three, one, four, and two, are all different, so it's injective too.

Figure 2.8.1

Injective Only, Versus Bijective

This figure draws both functions as arrow diagrams, side by side. On the left, f is injective but not surjective. Slot three receives no arrow. On the right, g is bijective. Every old record has exactly one outgoing arrow, and every slot has exactly one incoming arrow. It's a perfect pairing, with nothing left over on either side.

Table 2.8.3

The 3 Properties Compared

This table compares the three properties. An injective function can still leave some element of B with no preimage. It requires A to be no larger than B. A surjective function can still reach some element of B more than once. It requires A to be at least as large as B. A bijection fails in neither way, and it requires A and B to be exactly the same size. We'll prove the cardinality part carefully at the end of this section.

Definition 2.8.3 and Theorem 2.8.1

When Can a Function Be Reversed?

A one-to-one correspondence invites a question. Can the pairing be read in the opposite direction, as a function from B back to A? An inverse function, f inverse, from B to A, satisfies two identities. f inverse of f of a is a, for every a. And f of f inverse of b is b, for every b. Here's the theorem. A function has an inverse if and only if it's bijective. Suppose f is bijective, and take any b. Since f is surjective, some a maps to b. Since f is injective, that a is unique. So define f inverse of b to be that a. Both identities then hold. Conversely, suppose an inverse exists. If f of a one equals f of a two, apply f inverse to both sides, and you get a one equals a two. So f is injective. And for any b, let a be f inverse of b. Then f of a is b, so b has a preimage. So f is surjective too, and therefore bijective.

Reading Off the Inverse

The Audit Lookup

Reading off g inverse is immediate. Just reverse each pair. g inverse of one is one oh two. g inverse of two is one oh four. g inverse of three is one oh one. And g inverse of four is one oh three. That's precisely the audit lookup the migration team needed. Contrast the first attempt, f. Trying to define f inverse of three, there's nothing to point to, since no record maps to slot three. So f inverse would be undefined there, and it fails to be a function on all of B. That's the theorem failing in practice, because f isn't surjective. A repeated output would break the inverse in the other way. It would stop being well-defined.

Theorem 2.8.2

Bijections Force Equal Size

Recall that the cardinality of a finite set is the count of its distinct elements. A bijection between two finite sets forces those counts to agree. Theorem. If A and B are finite and there's a bijection from A to B, then A and B have the same cardinality. The proof. List A's n elements, a one through a n. Applying f gives a list of n values, all in B. Because f is injective, those n values have no repeats. Because f is surjective, every element of B appears somewhere in the list. A list of n distinct values that includes every element of B is exactly B. So B has n elements, the same as A. That's why the engineers built the new system with exactly one hundred thousand slots. It made a bijection possible in the first place.

The Converse Trap

Equal Size Isn't Enough

But the converse deserves a careful warning. Equal cardinality is a necessary condition for a bijection to exist between two sets. It is not sufficient to make any particular function one. Here's something to think about. With four records and four slots, a junior engineer says whatever migration we write is automatically a bijection. Test that against h, which sends one oh one and one oh two both to slot one, one oh three to two, and one oh four to three. Is h bijective? And what's the difference between equal sizes guaranteeing a bijection could exist, and guaranteeing this particular function is one? To summarize. Surjective means the range is the whole codomain. Bijective means injective and surjective. An inverse exists exactly for bijections, and a bijection forces equal sizes.

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Surjective and Bijective Functions

What does it mean for a function to be surjective (onto)?
A function f:A\to B is surjective if every element of B has at least one preimage in A. In other words, for every b\in B there is some a with f(a)=b. Equivalently, the range equals the whole codomain. If even one element of B is never hit, f is not surjective.
What is a bijection, and how is it different from an injective function?
A bijection is a function that is both injective and surjective, so it pairs each element of A with a unique element of B and vice versa. An injective function only guarantees no output is repeated, and it can still leave elements of B unused. For example, mapping 4 records into 5 slots can be injective but leave one slot empty.
Why does a function have an inverse only if it is a bijection?
A function has an inverse exactly when it is bijective. If f is bijective, surjectivity gives each b some a with f(a)=b, and injectivity makes that a unique, so f^{-1}(b)=a is well defined. Conversely, if f^{-1} exists, then f(a_1)=f(a_2) gives a_1=a_2, so f is injective, and f(f^{-1}(b))=b shows f is surjective.
If two finite sets have the same size, is every function between them a bijection?
No. Equal cardinality is necessary for a bijection to exist, but it does not make every function between the sets a bijection. If a bijection A\to B exists and both are finite, then |A|=|B|. Yet with four records and four slots, a map sending two records to the same slot is not injective, so it is not a bijection.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →