june-12

These lecture notes were generated by Claude inside a Cowork environment with knowledge of the syllabus and course materials, and generated from the audio transcript of the lecture. The lecture notes are not a transcript, and skip some parts while adding small details with sources/clarifications. These notes have been checked by me to be correct. I have added and edited the file for correctness and alignment with necessary material. All right-margin aside notes are additional to the course, and are not part of the learning objectives.

Lecture 11 — June 12, 2026

Administrative

• Midterm (Saturday, June 13, 9–11 AM): closed book; no calculators or electronic devices. Bring your UToronto ID card — booklets are matched to students via QR codes.
• Midterm format: 12 multiple-choice questions (reflection-style) + 3 long-answer questions, approximately 30 minutes per part. One proof question is difficult; the other two are feasible.
• Proof-writing advice: do not jump straight into writing. Spend roughly half the time reading, understanding, and exploring the question first. Most complete proof solutions are only 2–3 lines when written efficiently — but writing those lines requires having fully digested the problem. Think: What does it say? What am I trying to show? Can I work through a small example first?
• Injectivity and surjectivity: these are not required for the midterm. If they appeared in last week’s tutorial, you were not expected to know them yet. They are today’s topic. However, if you do know them (or anything else beyond the first five weeks), you are welcome to use your knowledge — the midterm does not penalise broader background.
• Piazza live Q&A: active during the midterm day.
• Tuesday (June 16) follows the Friday schedule — lecture takes place as usual.

---

1. Sets and maps

All of the linear algebra we have built — vector spaces, bases, linear transformations — lives, at its foundation, on top of sets. A vector space is, before it is anything else, a set whose elements we happen to call vectors. We have already discussed what it means to belong to a set, to be a subset, and how sets can be combined (union, intersection, Cartesian product). What we have not yet discussed is how to talk about correspondences between sets.

Definition (Map)

A map (or function) from a set to a set is an assignment: for each element , a unique element .

The set is called the domain of ; the set is called the codomain of .

The domain and codomain are part of the data of a map — they are not an afterthought. Two maps that perform the same rule but have different domains or codomains are different maps. For instance, the rule can define:

• a map , or
• a map .

These are genuinely different functions. Every element in the domain must have something assigned to it; there is no room for the assignment to fail.

Example: the domain must accommodate the rule. The rule does not define a map from to , because the input has no assigned output. The correct domain is : then is a perfectly good map.

A function as a subset

There is a clean formal definition: a map is a subset such that for every there is exactly one with . The set is the graph of . This ties the abstract definition to a picture you already know: the graph of a function in the plane passes the vertical-line test — every vertical line meets it in exactly one point. Subsets of that do not satisfy this condition (no entry, or two entries in some column) are called relations. We will not need relations, but they arise naturally in more general mathematics.

The student-number example. Let denote the set of students in the room and the set of all 10-digit sequences (we allow leading zeros — at least one student’s UToronto ID begins with one). The student-number assignment defines a map:

This is well-defined: every student has a student number, and the assignment is unambiguous.

Imagine writing out the Cartesian product as a giant table — rows indexed by students, columns indexed by 10-digit sequences. Placing a checkmark in position means “student has number .” The map corresponds to a placement of checkmarks such that every row has exactly one checkmark: each student is assigned exactly one number, and no student is without one. This is exactly the definition of a function.

Now two natural questions arise about this assignment: could two students share the same number? And does every possible 10-digit sequence appear as some student’s number?

---

2. Injectivity, surjectivity, bijectivity

Definition

A map is injective if

Equivalently: distinct inputs always produce distinct outputs; no two elements of get “glued” into a single element of .

Definition

A map is surjective if

Equivalently: every element of the codomain is actually achieved as an output; “covers” the entirety of .

Definition

A map is bijective if it is both injective and surjective.

The student-number assignment revisited. The map is injective — student numbers are designed precisely so that no two students share one. It is not surjective — most 10-digit sequences have never been assigned to anyone. In the table picture: every row has exactly one checkmark (the function condition), and no two rows share a column (injectivity). But many columns have no checkmark at all (not surjective).

Etymology

Injective comes from the Latin injectus (put inside). An injective map places the domain inside the codomain without collapsing anything: each input lands at its own distinct address.

Surjective comes from the French sur (on, over). A surjective map covers over the entirety of the codomain: nothing is left out.

The word bijective is a portmanteau of both. Some textbooks instead use one-to-one for injective and onto for surjective; the lecture avoids “one-to-one” because in common usage it is ambiguous — some authors use it to mean injective, others to mean bijective.

A note on the definition of injectivity. The condition is a one-way implication. The reverse, , is not an extra condition — it is already guaranteed by the definition of a map (a map must assign the same output to the same input). Injectivity only adds the converse direction.

---

3. Example:

This single example, examined through three versions, illustrates all three properties and how they respond to changes in domain and codomain.

Version 1: .

• Not injective: , yet . Two distinct inputs produce the same output — they have been glued together. Think of the domain as a folded ruler: the fold maps and onto the same point.
• Not surjective: there is no with . The negative reals are never covered.

Version 2: (restrict the codomain to non-negative reals).

• Still not injective: — the domain is unchanged, so the glueing persists.
• Now surjective: every has as a preimage. By declaring the codomain to be exactly , we have removed the elements that had no preimage.

Version 3: (restrict the domain to non-negative reals as well).

• Now injective: if and , then . By forbidding negative inputs, we have eliminated the only way two distinct inputs could share an output.
• Still surjective: every still has in the domain.

Version 3 is therefore bijective.

Intuition: folding and covering

Injectivity is about whether any two elements got folded onto the same output. Surjectivity is about whether every output has at least one element folded onto it. The two restrictions above fix exactly one problem each: restricting the codomain removes uncovered outputs; restricting the domain removes the double-fold.

---

4. Inverse maps

The power of bijectivity is that it enables an inverse. Informally: if takes to , the inverse takes back to .

Definition (Inverse map)

Let be a map. A map is an inverse of if

where and denote the identity maps (the map that sends every element to itself). When an inverse exists, it is unique and is denoted .

Warning on notation. is not . The notation looks like a reciprocal because resembles , but there is no arithmetic division here — is a map, not a number.

Why bijectivity is necessary.

• If is not surjective: some has no preimage, so has nowhere meaningful to go. The condition fails at .
• If is not injective: some has two or more preimages . The inverse must pick one of them — but either choice breaks the condition for the other.

In other words: an inverse requires every output to have a unique preimage — exactly what bijectivity guarantees.

Example. The bijection , , has the inverse . Indeed, for , and for .

The domain restriction is not an arbitrary choice — it is forced by the requirement of bijectivity. Without it, the inverse would have to send to both and , and a map cannot have two outputs for one input.

Multi-valued functions

In complex analysis, removing unwanted preimages is not always possible. The complex logarithm has infinitely many values for every nonzero (they differ by multiples of ). One is forced to work with multi-valued functions — objects that fall outside the framework of maps as defined here. We will actually see why, later in this course, when complex numbers enter through the theory of eigenvalues.

---

5. Linear isomorphisms — first look

All of the above applies to any sets, with no algebraic structure required. Linear algebra enters when we ask the same questions about maps that preserve the vector-space structure.

A linear transformation is, at its foundation, a map of sets — and the questions of injectivity and surjectivity make perfect sense for it.

• is injective if . Equivalently: no nonzero vector is sent to , i.e., . Nothing gets “killed.”
• is surjective if every is the image of some , i.e., . The entire codomain is covered.
• A bijective linear transformation is called a linear isomorphism.

Examples.

• Rotation in : bijective. Every vector has a unique preimage under a rotation (rotate back by the same angle), and every vector is reachable. Rotations are invertible — and the inverse is the reverse rotation.
• Projection onto a hyperplane: not injective. Any two vectors that differ only by a component perpendicular to the hyperplane are sent to the same projected vector. For instance, if we project onto the -plane, then and both map to .

The connection to what we have already built. We now have all the tools to characterise injectivity and surjectivity for linear maps via the rank and nullity:

• is injective .
• is surjective .

The rank-nullity theorem (, Lecture 10 §4) makes these conditions interact: for a map with , injectivity and surjectivity are actually equivalent. This will be developed in Tuesday’s lecture.

---

Textbook references

Topic	Axler	Hefferon	Treil
Maps between sets	Ch. 1, 1.18–1.19	Ch. 1, §I.1	Ch. 1, §1
Injective, surjective, bijective	Ch. 3, 3.15–3.18	Ch. 3, §IV.1	Ch. 3, §3
Inverse maps	Ch. 3, 3.20–3.21	Ch. 3, §IV.3	Ch. 3, §3
Injectivity/surjectivity via kernel and image	Ch. 3, 3.16, 3.19	Ch. 3, §IV.2	Ch. 3, §3