Sets, relations, functions, and equivalence

Prerequisites: Quantifiers and elementary arithmetic.

Learning objectives

• Distinguish a relation from a total function.
• Test injectivity, surjectivity, and equivalence properties.
• Use equivalence classes to define meaningful identities.

Collections and mappings carry different promises

A set records membership without order or duplicate occurrences. The set {a,b,a} is {a,b}. A sequence can preserve both order and repetition, so replacing a sequence with a set changes its meaning. The Cartesian product A x B contains ordered pairs (a,b) with a in A and b in B. A relation from A to B is any subset of that product.

A total function f:A->B is a relation in which each a appears with exactly one output. “Exactly one” combines existence and uniqueness. A lookup that can fail is better modeled as a partial function, or as a total function whose output type explicitly includes a missing result. A database relation allowing multiple records with the same key does not become a function simply because application code expects one record.

Let A={0,1,2,3}, B={0,1}, and f(x)=x mod 2. This function is surjective: every element of B is reached. It is not injective: 0 and 2 share an output. An injective function never maps distinct inputs to the same output. A bijection is both injective and surjective, so its inverse is a function on the entire codomain. Naming the codomain matters: the same mapping into {0,1,2} is no longer surjective.

Equivalence defines sameness for a purpose

A relation on a set is an equivalence relation when it is reflexive, symmetric, and transitive. For integers, define x equivalent to y when x-y is divisible by 3. Every integer differs from itself by zero; reversing a divisible difference preserves divisibility; adding two divisible differences preserves it. These facts establish all three properties. The equivalence classes are the integers with remainders 0, 1, and 2.

Equivalence classes partition the domain: every element belongs to exactly one class. This is useful when several representations should identify one logical object. For example, canonicalizing case in a deliberately case-insensitive identifier system can map equivalent strings to a shared representative. The equivalence must come from a specified policy, not an accidental implementation shortcut.

Relations need not be equivalences. Dependency-before is generally directional, and closeness within a tolerance is usually not transitive. With tolerance one, 0 is close to 1 and 1 is close to 2, but 0 is not close to 2. Treating approximate equality as an equivalence can make grouping depend on insertion order. Write and check the properties your algorithms actually require.

Practice problem

A username table contains (user_id, display_name) pairs. Several people may share a display name, but each user_id should have one display name. Describe which direction defines a function and whether it is necessarily injective. Propose a representation for looking up all users with one display name. Then analyze the relation on integers defined by “the absolute difference is at most two.” Supply a concrete test for each equivalence property and explain why using this relation as equality in a set would be problematic.

Worked solution

The mapping from user_id to display_name is a function if every valid ID has exactly one stored name. It need not be injective because different IDs can share a name. Reversing the pairs does not produce a function to individual IDs, but a mapping from each name to a set of IDs does. The distance relation is reflexive because an integer differs from itself by zero and symmetric because absolute difference ignores direction. It is not transitive: 0 relates to 2 and 2 relates to 4, while 0 does not relate to 4. A set depends on consistent equality classes; this relation can produce conflicting membership and deduplication decisions. Use explicit clustering semantics instead of pretending closeness is identity.

Check your understanding

Changing f:{0,1}->{0,1} with f(x)=x to codomain {0,1,2} changes which property?

• It is no longer a function.
• It is no longer injective.
• It is no longer surjective.

Explanation

Each input still has one distinct output, but codomain element 2 has no preimage.

Which condition is required for a relation A to B to be a total function?

• Every input has exactly one output.
• Every output has exactly one input.
• The sets A and B have equal size.

Explanation

A total function promises existence and uniqueness of output for each input. It need not be bijective.

Primary reading

• Mathematics for Computer Science: MIT OpenCourseWare

Open the study and save your work →