[HD] EECS3342 F26 - 2026-10-06 (Tuesday) - Lecture 8

Overview

Jackie Wang reviews relations and partial versus total functions, then develops injective, surjective, and bijective properties using formal definitions, arrow diagrams, and finite-set examples. The lecture emphasizes how to test each property independently—functionality, domain coverage, uniqueness of outputs, and target coverage—and applies those checks to model employee locations and decide whether mappings between sets can be bijections.

Key takeaways

A function maps every domain element to at most one target; it is total only when its domain equals the entire source set.
For a function, the relational image of a source value has cardinality 0 or 1: zero means the source is outside the domain, and one means it is in the domain.
Injectivity fails exactly when two distinct source values map to the same target; functionality fails when one source value maps to two distinct targets.
Surjectivity requires the range to cover the entire target set, whereas totality requires the domain to cover the entire source set.
A bijection must be a total, injective, surjective function; consequently, finite source and target sets of different sizes cannot be in bijection.
When modeling employee locations, a partial function avoids assuming that every employee is always present at a company location, while still preventing one employee from having multiple simultaneous locations.

Chapters

0:00 Programming Test Logistics and Function Review

The programming test is scheduled for the next day in the student's enrolled session at room 102 in the LAN building.
Phones must be left at the lab front desk; a physical ID such as a UCard, driver's license, health card, or passport can save time.
A relation is a set of ordered pairs; a partial function satisfies functionality, while a total function also has domain equal to its source set.

2:00 Relational Images Reveal a Function's Domain

For a function R and source value s, the relational image R(s) contains at most one target value, so its cardinality is at most 1.
If |R(s)| = 0, then the image is empty and s is not in the domain; if |R(s)| = 1, then s is in the domain.
An image containing more than one target value would violate the functional property, even though a general relation may allow it.

9:55 Modeling Employee Locations with a Partial Function

A relation from employees to locations is unsuitable if one employee could be assigned to multiple locations at once.
A total function assumes every employee is always assigned a location, an assumption that may fail during vacation, remote work, or absence.
A partial function is the preferred model when some employees may not currently be present at a company location.

18:02 Combining Partiality, Totality, Injectivity, and Surjectivity

Functions have a partial-versus-total dimension: totality requires every source-set element to appear in the domain.
Injectivity concerns the domain-to-range mapping; surjectivity concerns whether the range covers the target set.
A bijection combines totality, injectivity, and surjectivity, so it is inherently a total function.

23:46 Formal Definitions: Functionality Versus Injectivity

Functionality rules out one source value s mapping to two distinct target values t1 and t2.
Injectivity rules out two distinct source values s1 and s2 mapping to the same target value t.
To disprove functionality, find one source with two outputs; to disprove injectivity, find two sources sharing an output.

32:13 Testing Empty, Single-Pair, and Multi-Pair Partial Injections

The empty relation satisfies functionality and injectivity vacuously because no violating pair of mappings exists.
A relation containing just (1, A) is also both functional and injective: one pair cannot establish either kind of violation.
A mapping such as (2, A) and (3, B) is injective because distinct source values have distinct targets.

39:06 Finding Injectivity Violations in Arrow Diagrams

A relation may be functional but not injective: mappings (1, B), (2, B), and (3, C) assign each source at most one target, but sources 1 and 2 share B.
The same test catches (1, B) and (3, B): distinct sources mapping to the same target violate injectivity.
To demonstrate the failure formally, use the shared target in two ordered pairs and show their source values are unequal.

45:09 Why Three Sources Cannot Inject into Two Targets

For source set {1, 2, 3} and target set {A, B}, no total injection exists.
Totality requires mappings for all three sources, while injectivity allows each target to be used by at most one source.
After assigning A and B to two sources, the remaining source must reuse a target, creating an injectivity violation.

50:42 Surjectivity Requires Covering the Entire Target Set

A function is surjective when its range equals the target set, regardless of whether every source-set value is used.
Mappings whose only output is A are not surjective onto {A, B}, because B is missing.
Check functionality and target coverage separately when deciding whether a relation is a partial surjection.

54:12 Checking Total Surjections One Property at a Time

A total surjection must be functional, cover every source value, and cover every target value.
For the lecture's examples with source {1, 2, 3} and target {A, B}, each candidate is checked for functionality, totality, and surjectivity independently.
A candidate can be functional and surjective but not total, or functional and total but not surjective; either failure prevents it from being a total surjection.

58:20 Bijections Require Totality, Injectivity, and Surjectivity

A bijection is a total function that is both injective and surjective—equivalently, a one-to-one correspondence.
No bijection can exist from {1, 2, 3} to {A, B}, since even an injection is impossible.
A mapping such as 1→A, 2→B, 3→C between matching three-element sets satisfies functionality, totality, injectivity, and surjectivity.

1:00:50 Diagnosing Failed Bijections with a Property Table

The four candidate mappings are evaluated by checking total functionality, injectivity, and surjectivity as separate columns.
A mapping that omits source value 1 is not total; one that maps distinct sources to the same target is not injective.
A mapping whose outputs omit a target such as B is not surjective, so it cannot be a bijection.

1:05:54 Arrow-Diagram Exercise on Sets {1, 2, 3, 4} and {A, B, C, D}

All four arrow diagrams are functional because no source value has multiple outgoing arrows.
Diagrams missing source value 4 fail totality; diagrams sending two sources to D fail injectivity.
Only a diagram covering A, B, C, and D is surjective, and only a candidate satisfying every required property is bijective.

1:10:13 Thursday Preview and Test-Tip Wrap-Up

The remaining example on formalizing arrays is deferred to Thursday, before the course moves to a case study.
The class concludes with an invitation to discuss tips for the programming test scheduled for the next day.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.