[HD] EECS3342 F26 - 2026-09-29 (Tuesday) - Lecture 6

Overview

Jackie Wang prepares EECS3342 students for the programming test and reviews how power sets characterize all relations between source and target sets. The lecture then develops relational operations—domain, range, inverse, image, restriction, subtraction, and overwriting—and introduces the quantified property that distinguishes functional relations.

Key takeaways

All relations between source set S and target set T are exactly the power set P(S × T); with 3 departure cities and 3 destinations, there are 2^9 = 512 possible relations.
A relational image requires its input set to be a subset of the source set, not necessarily a subset of the relation's domain; missing domain values simply contribute no target values.
Inverse relations swap every ordered pair, which yields dom(R) = ran(R⁻¹) and ran(R) = dom(R⁻¹).
Domain and range restriction retain pairs matching selected values, while subtraction removes them; the lecture's example with {A, B} and {1, 2} demonstrates all four operators concretely.
Overwriting R with T is equivalent to T ∪ (R domain-subtracted by dom(T)), so T replaces every existing mapping whose domain appears in T.
A relation fails to be functional when one domain value appears in two pairs with different target values, as shown by (A,1) and (A,3).

Chapters

0:00 Programming Test Preparation and Practice-Test Strategy

The programming test is approximately one week away and covers material from Lab 1 and Lab 2.
Students receive two practice tests: an unmodified Fall 2024 real test and a simpler practice test previously given to EECS 3424 students.
Jackie Wang recommends saving the Fall 2024 test until students feel fully prepared so its first attempt accurately measures readiness.
A realistic simulation should use the remote lab, the PDF test environment, a strict 50-minute limit, project export, and submission-file selection.

2:45 Test Clarifications, Event-B Materials, and Lab Support

Ambiguous test wording can be clarified during the test, although students should review the Event-B summary document before test day.
The Wednesday lab session is staffed by teaching assistants because Jackie Wang is unavailable due to back-to-back lab tests.
The teaching assistants have taken EECS3342 and received guidance on Lab 1, Lab 2, and the programming-test guide.
The Lab 2 submission deadline is Wednesday at 11:59 p.m.; solution material is planned for Thursday.

3:45 Power Sets as a Foundation for Enumerating Relations

The power set of a set such as {1, 2, 3} contains every subset, including the empty set, one-element subsets, and the original set.
Subset sizes range from 0 through the cardinality of the original set, and combinations can count subsets of each size.
A relation is itself a set of ordered pairs, so the same subset-selection logic used for power sets applies to relations.
For source set S and target set T, the Cartesian product S × T is the maximum possible relation.

6:05 All Relations Between Two Sets and Relation Membership

The notation S ↔ T denotes the set of all possible relations between S and T.
Each member of S ↔ T is a relation, and each relation is a set of ordered pairs, creating two nested set levels.
The all-relations set is equivalent to the power set P(S × T).
A particular relation R is declared between S and T using membership: R ∈ S ↔ T, equivalently R ∈ P(S × T).

9:00 Airline Relations and Counting Their Cardinalities

Departure cities {Toronto, Montreal, Vancouver} and destination cities {Beijing, Seoul, Paris} create a Cartesian product with 3 × 3 = 9 ordered pairs.
An airline route collection is one relation selected from the set of all relations between the departure and destination sets.
The number of possible relations is 2^9 = 512 because every one of the 9 possible routes may be included or excluded.
The number of relations containing exactly two routes is C(9, 2), such as {(Toronto, Beijing), (Montreal, Seoul)}.

16:00 Relational Operators and Formal Set-Comprehension Definitions

Jackie Wang begins the relational-operations section with domain, range, inverse, and image.
The lecture emphasizes reading both the intuitive English explanation and the formal set-comprehension definition for each operator.
Formal definitions are especially useful for understanding how relational operations are represented in Rodin.
Students are advised to study ahead because additional operations and function classifications continue in later lectures.

18:00 Domain, Range, and Inverse of a Relation

For a relation from alphabet symbols to integers, the domain collects all first components of ordered pairs without repetition.
The range collects all second components and is a subset of the target set; it need not equal the entire target.
The inverse relation swaps every ordered pair, turning pairs such as (A, 1) into (1, A).
The algebraic identities dom(R) = ran(R⁻¹) and ran(R) = dom(R⁻¹) follow directly from exchanging pair components.

25:00 Relational Image: Selecting Target Values from Domain Inputs

The relational image R[S] returns all target values paired with elements of an input set S.
For R[S] to be well-defined, S must be a subset of the source set, not necessarily a subset of dom(R).
If S = {A, B}, the image combines every target associated with A or B, such as {1, 2, 4, 5}.
The image is always a subset of ran(R), and an input element with no associated pair contributes nothing.

34:00 Image Edge Cases and Inverse-Relation Inputs

R[{G}] is well-defined when G belongs to the alphabet source, but it evaluates to the empty set if G has no related pair.
R[{A, H}] can be computed as R[{A}] ∪ R[{H}], producing {1, 4} when H has no associated target.
R[{1, 2}] is not well-defined for the original relation because numeric values are not elements of the alphabet source.
R⁻¹[{1, 2}] is well-defined because 1 and 2 belong to the inverse relation's source, and it returns the corresponding original-domain values such as {A, B, D, E}.

40:00 Four Restriction and Subtraction Operators

The four operators combine two dimensions: domain versus range, and restriction versus subtraction.
Domain restriction and domain subtraction use a set of source values; range restriction and range subtraction use a set of target values.
Each operator returns a new relation rather than a domain or range set.
The direction of the triangular operator indicates whether filtering applies to the left-side domain or right-side range.

43:00 Formal Definition of Domain Restriction

For domain restriction R restricted to S, the result contains every pair (d, r) in R whose first component d belongs to S.
Set comprehension makes the result explicitly a set of ordered pairs and therefore another relation.
The domain value d must be both part of a pair in R and a member of the restricting source subset S.
This definition provides the template for deriving the analogous range and subtraction operations.

48:00 Computing Domain and Range Restrictions and Subtractions

With S = {A, B} and T = {1, 2}, domain restriction keeps pairs beginning with A or B: (A,1), (B,2), (A,4), and (B,5).
Domain subtraction removes all pairs whose first component is A or B, leaving (C,3), (C,6), (D,1), (E,2), and (F,3).
Range restriction keeps pairs whose second component is 1 or 2: (A,1), (B,2), (D,1), and (E,2).
Range subtraction removes those same target values and leaves (C,3), (A,4), (B,5), (C,6), and (F,3).

54:00 Overwriting a Relation with Another Relation

Unlike restriction and subtraction, overwriting takes another relation as its input rather than merely a set of domain or range values.
The result keeps every pair from the overriding relation T and retains only pairs from R whose domain values are absent from dom(T).
The formal definition separates into a union: T ∪ (R domain-subtracted by dom(T)).
For T = {(A,3), (C,4)}, dom(T) = {A, C}; removing A- and C-starting pairs from R leaves pairs such as (B,2), (B,5), (D,1), (E,2), and (F,3) to union with T.

1:07:00 Transition from Relational Operations to Functions

The lecture shifts from manipulating arbitrary relations to classifying relations, beginning with functions.
Upcoming classifications include partial versus total functions and injective, surjective, and bijective functions.
The functional property is expressed with universal quantification over a source value s and target values t1 and t2.
The quantified variables must represent valid source and target elements, while the implication tests whether two pairs sharing s force t1 and t2 to be equal.

1:12:00 Counterexample Witness for a Nonfunctional Relation

The relation R = {(A,1), (B,2), (A,3)} is not functional because the same domain value A maps to two different target values.
The pair witnesses (A,1) and (A,3) make the antecedent of the functional implication true.
The required conclusion 1 = 3 is false, so the implication evaluates to true implies false, which is false.
Identifying two pairs with one shared first component and unequal second components is the standard witness for disproving that a relation is a function.

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.