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

Injective Functions: One-to-One Mappings and Their Properties

Name: 2.7 Injective Functions: One-to-One Mappings and Their Properties — Discrete Mathematics
Uploaded: 2026-09-30T05:42:10+00:00
Duration: 8 min 14 s
Description: Never sending 2 different inputs to the same output

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.7 · lesson 15 of 878 min · free with a free account

← Functions: Definitions and Terminology Next lesson: Surjective and Bijective Functions →

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

Never sending 2 different inputs to the same output.

Define an injective (one-to-one) function
Read injectivity from an arrow diagram
Prove injectivity algebraically - and disprove it with one counterexample
See how restricting the domain can create injectivity

Transcript

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

Set Theory and Functions

Injective Functions

Section two point six defined functions. This section studies functions with a stronger guarantee. They never send two different inputs to the same output. They're called injective, or one-to-one. We'll define them precisely, read the property from an arrow diagram, prove it algebraically, and see how a single counterexample is enough to show it fails.

The Opening Problem

Hash Collisions Are a Certainty

A hash function that indexes database records maps an essentially unlimited set of possible keys, down to a small, fixed set of bucket numbers. Two different keys landing in the same bucket is called a hash collision. It isn't a bug that shows up in one unlucky case. It's a mathematical certainty, whenever the possible keys outnumber the buckets. This course returns to that idea as the Pigeonhole Principle, in section five point three. Designers can't avoid it, so they engineer around it, with collision resolution, more buckets, or hash functions that spread keys evenly. But when a function's domain and codomain happen to be evenly matched, it can aspire to something stronger. Never sending two different inputs to the same output at all.

Definition 2.7.1

Injective, or One-to-One

A function f from A to B is injective, or one-to-one, under one condition. For all a one and a two in A, f of a one equals f of a two, implies a one equals a two. In words, if two inputs produce the same output, they must have been the same input. There's an equivalent form, the contrapositive, from section one point five. If a one and a two are different, then f of a one and f of a two are different. Distinct inputs always produce distinct outputs.

Figure 2.7.1

The Discrete Horizontal-Line Test

A calculus course tests injectivity with the horizontal line test. If some horizontal line crosses a graph more than once, the function isn't injective. For functions between finite sets, arrow diagrams give the exact analogue. A function is injective precisely when no element of the codomain receives more than one incoming arrow. On the left, f is injective. Every codomain element gets at most one arrow. d gets none, and that's fine. Injectivity says nothing about whether every codomain element is used. On the right, g isn't injective. Both one and two point to a, so a receives two arrows.

Checking Every Pair

Confirming f Is Injective

Let's confirm f is injective directly from the definition. A is one, two, three, and B is a, b, c, d, with f of one equals a, f of two equals b, and f of three equals c. Every pair of distinct inputs must be checked. One and two give a and b, which differ. One and three give a and c, which differ. Two and three give b and c, which differ. Every one of the three pairs produces distinct outputs. So f is injective, exactly as the diagram shows. But checking every pair by hand is only possible when the domain is small and finite.

The Algebraic Method

Proving Injectivity

When the domain is infinite, like all the reals or all the integers, injectivity must be shown for every pair at once. That's exactly the direct-proof template from section one point seven. Assume f of a equals f of b, for arbitrary a and b, and use algebra to derive a equals b. Claim. f of x equals three x minus five is injective on the reals. Let a and b be arbitrary real numbers, and assume f of a equals f of b. Then three a minus five equals three b minus five. Add five to both sides, so three a equals three b. Divide both sides by three, so a equals b. f of a equals f of b forces a equals b. That's exactly the definition, so f is injective.

Disproving Injectivity

One Counterexample Is Enough

Disproving injectivity doesn't need a general argument at all. Claim. g of x equals x squared is not injective on the reals. A single counterexample suffices. g of two is four, and g of minus two is also four. But two isn't equal to minus two. So g fails the definition, and isn't injective. The asymmetry is worth stating plainly. Proving a function is injective needs an argument that works for arbitrary a and b. Proving it's not injective needs only one specific pair. A claim about every pair fails the moment one pair breaks it.

More Examples

The Same Shape, Different Answers

Claim. h of n equals two n plus one is injective on the integers. Assume h of a equals h of b. Then two a plus one equals two b plus one. Subtract one, so two a equals two b. Divide by two, so a equals b. It's injective. Not every function of this shape behaves the same way. Let k of n be n mod five, the remainder when n is divided by five. k of zero is zero, and k of five is also zero. But zero isn't five. So k isn't injective. And this is exactly the hash-collision phenomenon from the opening. k folds infinitely many integers onto only five possible outputs, zero through four. Collisions like this are unavoidable.

Domain Restriction

Repairing the Squaring Function

Whether a function is injective can depend on its domain, not only its formula. The squaring function failed on all the reals, because it collapses each pair of opposites, x and minus x, onto one output. Restrict the domain to the non-negative numbers, zero to infinity, and no such pair can appear. Claim. On that restricted domain, x squared is injective. Let a and b be non-negative, and assume a squared equals b squared. Rearrange and factor. a squared minus b squared equals a minus b, times a plus b, which is zero. A product is zero only if one factor is zero. If a minus b is zero, then a equals b directly. If a plus b is zero, then since both are non-negative, the only way is a and b both zero. Again, a equals b. In every case a equals b, so x squared is injective on the non-negative numbers.

Table 2.7.1

Every Function in This Section

This table collects all five functions from this section. Three x minus five on the reals is injective, by algebra. x squared on the reals isn't, because g of two equals g of minus two. x squared on the non-negative numbers is injective, by the factoring argument. Two n plus one on the integers is injective, by algebra. And n mod five isn't, because k of zero equals k of five. Every yes came from a general argument. Every no came from a single counterexample.

Takeaways

Distinct In, Distinct Out

To summarize. A function is injective if f of a one equals f of a two, always forces a one equals a two. Equivalently, distinct inputs give distinct outputs. In an arrow diagram, no codomain element may receive more than one arrow. Proving injectivity needs a general argument. Disproving it needs a single counterexample. And whether a function is injective can depend on its stated domain. Hash functions show the real stakes. A collision is exactly a failure of injectivity, unavoidable once the domain outgrows the codomain. Here's something to think about. Is there another way to restrict the domain, other than the non-negative numbers, that makes x squared injective? Is there a single largest domain on which it's injective, or could two different largest domains work equally well?

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 UniversitySigned partner

University of the PeopleSigned partner

Charter Oak State CollegeSigned partner

Strayer UniversitySigned partner

Columbia Southern UniversitySigned partner

Indiana TechSigned partner

Penn StateWorks with NCCRS

Southern New Hampshire UniversityWorks with NCCRS

SUNYWorks 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 Injective Functions: One-to-One Mappings and Their Properties

What does it mean for a function to be injective (one-to-one)?

A function f: A \to B is injective if f(a_1) = f(a_2) implies a_1 = a_2 for all a_1, a_2 \in A. In other words, two inputs that give the same output must be the same input. The contrapositive says the same thing: different inputs always give different outputs.

How can you tell from an arrow diagram whether a function is one-to-one?

A function is injective exactly when no element of the codomain receives more than one incoming arrow. If two inputs both point to the same output, the function fails. An element of the codomain with no arrow at all is fine, because injectivity does not require every output to be used.

How do you prove that f(x) = 3x - 5 is injective, and how do you show a function is not?

To prove injectivity, assume f(a) = f(b) for arbitrary a, b and derive a = b. Here 3a - 5 = 3b - 5 gives 3a = 3b, so a = b. To disprove it, one counterexample is enough: x^2 is not injective on the reals because 2 \neq -2 but both square to 4.

Can restricting the domain make a function injective?

Yes, injectivity depends on the domain as well as the formula. The function x^2 fails on all reals because x and -x give the same output. On [0,\infty) it is injective: if a^2 = b^2, then (a-b)(a+b)=0, and since a, b \ge 0, either factor being zero forces a = b.

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 syllabus Every course with PRO →

Discrete Mathematics
4 credits · NCCRSEnroll →