Learning Objectives

• Define functions, domains, codomains and ranges formally.
• Distinguish between functions and non-functions (the vertical line test for mappings).
• Translate mathematical functions to Java methods and Function<T,R>.
• Prove that a given rule defines a function.
• Analyze Java methods as functions: identify domain, codomain and range.

Concept Overview

What Is a Function?

A function $f: X \rightarrow Y$ is a rule that assigns to each element $x \in X$ exactly one element $f(x) \in Y$.

Key property: Each input maps to exactly one output. Two things can fail:

1. Some input has no output defined → not a function on that domain.
2. Some input maps to multiple outputs → not a function.

Function Equality

$f = g$ if and only if $\text{dom}(f) = \text{dom}(g)$ and $\forall x \in \text{dom}(f): f(x) = g(x)$.

Functions as Sets of Ordered Pairs

A function $f: X \rightarrow Y$ can be viewed as a set $F \subseteq X \times Y$ (connecting to Module 4) where:

• For every $x \in X$, there exists exactly one $y$ with $(x, y) \in F$.

Composition

If $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, the composition $g \circ f: X \rightarrow Z$ is defined by $(g \circ f)(x) = g(f(x))$.

Why this matters in CS:

• Java methods are functions: parameters form the domain, return type is the codomain.
• Hash functions map keys to buckets: hashCode: Object → int.
• Functional programming uses composition (Function.andThen, Function.compose).
• Understanding domain and range prevents bugs: calling a function outside its domain causes errors.

Formal Notation

Worked Examples

Example 1: Identifying Domain, Codomain and Range

Function: $f: \mathbb{Z} \rightarrow \mathbb{Z}$ defined by $f(n) = 3n$.

• Domain: $\mathbb{Z}$
• Codomain: $\mathbb{Z}$
• Range: $\{3k \mid k \in \mathbb{Z}\} = $ multiples of 3

The range is a proper subset of the codomain ($3 \nmid 1$, so $1$ is not in the range).

Java translation:

// Domain: int (all 32-bit integers)
// Codomain: int
// Range: multiples of 3 (that fit in int)
public static int f(int n) { return 3 * n; }

Example 2: Is This a Function?

Rule: $g: \mathbb{Z} \rightarrow \mathbb{Z}$ defined by "$g(n) = $ a number whose square is $n$."

This is not a function because:

• For $n = 4$: both $2$ and $-2$ satisfy $g(4)^2 = 4$. Multiple outputs.
• For $n = 3$: no integer has square 3. No output.

Example 3: Composition

Let $f(x) = x + 2$ and $g(x) = x^2$. Then:

• $(g \circ f)(x) = g(f(x)) = g(x+2) = (x+2)^2$
• $(f \circ g)(x) = f(g(x)) = f(x^2) = x^2 + 2$

Note: $g \circ f \neq f \circ g$ in general! Composition is not commutative.

Example 4: Function from Module 2 — Remainder

$r_m: \mathbb{Z} \rightarrow \{0, 1, \ldots, m-1\}$ defined by $r_m(n) = n \bmod m$.

• Domain: $\mathbb{Z}$
• Codomain: $\{0, \ldots, m-1\}$
• Range = Codomain (every remainder value is achieved) → surjective (Module 5, Class 3)
• Preimage: $r_m^{-1}(\{k\}) = [k]_m$ (congruence class from Module 2)

Example 5: Hash Function as a Function

// Domain: all possible String values
// Codomain: int (all 32-bit integers)
// Range: a subset of int (not every int is a hash value)
int h = "hello".hashCode();  // h = 99162322

The hash function maps an infinite domain to a finite codomain — by the pigeonhole principle (Module 7 preview), collisions must occur.

Proof Techniques Spotlight

Proving a Rule Is (or Isn't) a Function

To prove $f: X \rightarrow Y$ is a function:

1. Show every $x \in X$ has at least one output (well-defined).
2. Show every $x \in X$ has at most one output (single-valued).

To disprove: Find an $x$ with zero or multiple outputs.

Proving Function Equality

To prove $f = g$ where $f, g: X \rightarrow Y$:

"Let $x \in X$. Then $f(x) = \ldots = g(x)$."

Java Deep Dive

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class FunctionLibrary {

    // --- Representing Functions ---

    /**
     * Represent a finite function as a Map.
     * Domain = keySet, Codomain determined by context, Range = values.
     */
    public static <X, Y> boolean isFunction(Map<X, Y> mapping, Set<X> domain) {
        // Every element of domain must have exactly one image
        for (X x : domain) {
            if (!mapping.containsKey(x)) return false;
        }
        return true;  // Maps give single-valued by construction
    }

    /**
     * Compute the range (image) of a function.
     */
    public static <X, Y> Set<Y> range(Map<X, Y> f) {
        return new HashSet<>(f.values());
    }

    /**
     * Compute the preimage of a value y.
     * f^{-1}({y}) = { x ∈ dom(f) | f(x) = y }
     */
    public static <X, Y> Set<X> preimage(Map<X, Y> f, Y y) {
        Set<X> result = new HashSet<>();
        for (Map.Entry<X, Y> entry : f.entrySet()) {
            if (Objects.equals(entry.getValue(), y)) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    // --- Composition ---

    /**
     * Compose two functions: (g ∘ f)(x) = g(f(x))
     */
    public static <X, Y, Z> Function<X, Z> compose(
            Function<X, Y> f, Function<Y, Z> g) {
        return x -> g.apply(f.apply(x));
    }

    /**
     * Compose finite functions represented as Maps.
     */
    public static <X, Y, Z> Map<X, Z> composeMaps(
            Map<X, Y> f, Map<Y, Z> g) {
        Map<X, Z> result = new HashMap<>();
        for (Map.Entry<X, Y> entry : f.entrySet()) {
            Y intermediate = entry.getValue();
            if (g.containsKey(intermediate)) {
                result.put(entry.getKey(), g.get(intermediate));
            }
        }
        return result;
    }

    // --- Analysis Methods ---

    /**
     * Analyze a Java function over a domain:
     * compute its range and identify the mapping.
     */
    public static <X, Y> Map<X, Y> analyzeFunction(
            Set<X> domain, Function<X, Y> f) {
        Map<X, Y> mapping = new LinkedHashMap<>();
        for (X x : domain) {
            mapping.put(x, f.apply(x));
        }
        return mapping;
    }

    /**
     * Check if two functions agree on a domain.
     * f = g iff ∀x ∈ domain: f(x) = g(x)
     */
    public static <X, Y> boolean functionsEqual(
            Set<X> domain, Function<X, Y> f, Function<X, Y> g) {
        for (X x : domain) {
            if (!Objects.equals(f.apply(x), g.apply(x))) return false;
        }
        return true;
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Function Library ===\n");

        // f(n) = 3n
        Set<Integer> domain = IntStream.rangeClosed(-5, 5).boxed()
                .collect(Collectors.toCollection(TreeSet::new));
        Function<Integer, Integer> f = n -> 3 * n;
        Map<Integer, Integer> fMap = analyzeFunction(domain, f);
        System.out.println("f(n) = 3n on [-5,5]:");
        System.out.println("  Mapping: " + fMap);
        System.out.println("  Range: " + new TreeSet<>(range(fMap)));

        // Composition: g(x) = x + 2, h(x) = x^2
        Function<Integer, Integer> g = x -> x + 2;
        Function<Integer, Integer> h = x -> x * x;
        Function<Integer, Integer> hg = compose(g, h);  // h(g(x)) = (x+2)^2
        Function<Integer, Integer> gh = compose(h, g);  // g(h(x)) = x^2 + 2

        System.out.println("\nComposition (non-commutative):");
        System.out.println("  (h ∘ g)(3) = " + hg.apply(3) + " = (3+2)^2 = 25");
        System.out.println("  (g ∘ h)(3) = " + gh.apply(3) + " = 3^2 + 2 = 11");

        // Remainder function r_m
        int m = 5;
        Function<Integer, Integer> rem = n -> Math.floorMod(n, m);
        Map<Integer, Integer> remMap = analyzeFunction(
                IntStream.rangeClosed(0, 14).boxed().collect(Collectors.toSet()), rem);
        System.out.println("\nr_5(n) = n mod 5:");
        System.out.println("  Mapping: " + new TreeMap<>(remMap));
        System.out.println("  Range: " + new TreeSet<>(range(remMap)));

        // Preimage: which inputs map to 2 under r_5?
        Map<Integer, Integer> extendedRem = analyzeFunction(
                IntStream.rangeClosed(0, 20).boxed().collect(Collectors.toSet()), rem);
        System.out.println("  Preimage of 2: " + new TreeSet<>(preimage(extendedRem, 2)));

        // Function equality
        Function<Integer, Integer> f1 = x -> x * x - 1;
        Function<Integer, Integer> f2 = x -> (x - 1) * (x + 1);
        boolean eq = functionsEqual(domain, f1, f2);
        System.out.println("\nx²-1 = (x-1)(x+1)? " + eq);
    }
}

Historical Context

The modern concept of a function evolved over centuries:

• Euler (1748) defined a function as an "analytic expression."
• Dirichlet (1837) generalized to any rule assigning outputs to inputs.
• Set-theoretic definition (20th century): a function is a set of ordered pairs with unique first components.

In computer science, Alonzo Church's lambda calculus (1930s) formalized computation as function application. This directly influenced functional programming languages (Lisp, Haskell, and Java 8+'s lambda expressions).

Java's Function<T, R> interface (Java 8) made functions first-class citizens, enabling map, filter, compose — all grounded in the mathematical concept.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. For $f: \mathbb{Z} \rightarrow \mathbb{Z}$ with $f(n) = n^2$, what is the range?

A2. Is the rule "$g(x) = \pm\sqrt{x}$" a function from $\mathbb{R}^+ \rightarrow \mathbb{R}$? Why or why not?

A3. Given $f(x) = 2x+1$ and $g(x) = x-3$, compute $(g \circ f)(4)$ and $(f \circ g)(4)$.

Slide Set B: Proof Problems

B1. Prove that $f(n) = 2n + 1$ is a well-defined function from $\mathbb{Z}$ to $\mathbb{Z}$.

B2. Prove: if $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, then composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$.

B3. Prove the range of $f(n) = n \bmod m$ is exactly $\{0, 1, \ldots, m-1\}$.

Slide Set C: Java Coding Problems

C1. Write a method that takes a Function<Integer, Integer> and a domain, and returns the range as a Set<Integer>.

C2. Implement function composition for Map-based finite functions.

C3. Write a method to compute the preimage of a given output value.

Full Problem Set

Discrete Math Problems

DM1. For each rule, determine whether it defines a function from $\mathbb{Z}$ to $\mathbb{Z}$:

(a) $f(n) = n + 3$ (b) $g(n) = n/2$ (c) $h(n) = |n|$ (d) $k(n) = $ "the smallest prime greater than $n$"

DM2. Prove: if $f: X \rightarrow Y$ is a function, then for all $A \subseteq X$: $f(A) \subseteq Y$ (the image of a subset of the domain is a subset of the codomain).

DM3. Let $f: \mathbb{Z} \rightarrow \mathbb{Z}$ with $f(n) = n^2 + 1$. Compute $f(\{-2, -1, 0, 1, 2\})$ and $f^{-1}(\{2\})$.

DM4. Prove: composition of functions is associative.

DM5. Prove or disprove: the range of $f \circ g$ is a subset of the range of $f$.

DM6. Let $f(n) = n \bmod 5$ (from Module 2). Show that the fibers of $f$ (sets $f^{-1}(\{k\})$ for $k = 0,\ldots,4$) form a partition of $\mathbb{Z}$. (Connects to Module 4, Class 3.)

Java Programming Problems

JP1. Represent a function as a Map<Integer, Integer>. Write methods: isFunction(Map, Set domain), getRange(Map), getPreimage(Map, value).

JP2. Implement a method that takes two Function<Integer, Integer> objects and composes them. Test by composing $f(x) = x + 1$ and $g(x) = x * 2$ in both orders.

JP3. Write a method that, given a List<Function<Integer, Integer>>, composes them left-to-right ($f_1 \circ f_2 \circ \cdots \circ f_n$).

JP4. Analyze Java's String.hashCode() as a function: for all 2-character strings from 'a' to 'z', compute the hash and identify collisions (different inputs, same output).

JP5. Write a method that determines whether a given Map<Integer, Integer> is a well-defined function on a given domain and codomain (every domain element maps to an element in the codomain).

Bridge Problems

BR1. The divisor-count function $\tau(n) = |D(n)|$ maps $\mathbb{Z}^+$ to $\mathbb{Z}^+$. Compute $\tau(n)$ for $n = 1, \ldots, 30$. What is the range of $\tau$ restricted to $\{1, \ldots, 30\}$? Which values have the largest preimage?

BR2. Recall from Module 2 that $r_m(n) = n \bmod m$ maps $\mathbb{Z}$ to $\{0, \ldots, m-1\}$. Prove that the fibers of $r_m$ are exactly the congruence classes. Implement in Java: compute fibers for $m = 7$ over $\{0, \ldots, 50\}$ and verify they match partitionByMod from Module 4.

Solutions

Discrete Math Solutions

DM1. (a) Yes — well-defined, single-valued. (b) No — $g(3) = 3/2 \notin \mathbb{Z}$. Not well-defined on $\mathbb{Z}$. (c) Yes — well-defined, single-valued. (d) Yes — by Bertrand's postulate, there exists a prime between $n$ and $2n$; the smallest such prime is unique.

DM2. Let $y \in f(A)$. Then $y = f(a)$ for some $a \in A \subseteq X$. Since $f: X \rightarrow Y$, $f(a) \in Y$. So $y \in Y$. $\blacksquare$

DM3. $f(\{-2,-1,0,1,2\}) = \{5, 2, 1, 2, 5\} = \{1, 2, 5\}$. $f^{-1}(\{2\}) = \{-1, 1\}$ (since $(-1)^2 + 1 = 2$ and $1^2 + 1 = 2$).

DM5. True. Let $y \in \text{range}(f \circ g)$. Then $y = f(g(x))$ for some $x$. Let $z = g(x)$. Then $y = f(z)$, so $y \in \text{range}(f)$. $\blacksquare$

DM6. $f^{-1}(\{k\}) = \{n \in \mathbb{Z} \mid n \bmod 5 = k\} = [k]_5$. By Module 4, Class 3 (Problem A3 of the assignment), the fibers of any function partition the domain. Since every $n \in \mathbb{Z}$ has $n \bmod 5 \in \{0,\ldots,4\}$, the five fibers are non-empty, pairwise disjoint, and cover $\mathbb{Z}$. $\blacksquare$

Java Solutions

JP4.

Set<Integer> hashes = new HashSet<>();
Map<Integer, List<String>> hashToStrings = new HashMap<>();
for (char c1 = 'a'; c1 <= 'z'; c1++) {
    for (char c2 = 'a'; c2 <= 'z'; c2++) {
        String s = "" + c1 + c2;
        int h = s.hashCode();
        hashToStrings.computeIfAbsent(h, k -> new ArrayList<>()).add(s);
        hashes.add(h);
    }
}
System.out.println("Total 2-char strings: " + (26 * 26));
System.out.println("Distinct hash values: " + hashes.size());
// Find collisions
hashToStrings.entrySet().stream()
    .filter(e -> e.getValue().size() > 1)
    .forEach(e -> System.out.println("Collision: hash=" + e.getKey()
            + " strings=" + e.getValue()));

BR1.

Map<Integer, Integer> tau = new TreeMap<>();
for (int n = 1; n <= 30; n++) {
    int count = 0;
    for (int d = 1; d <= n; d++) if (n % d == 0) count++;
    tau.put(n, count);
}
System.out.println("τ(n) for n=1..30: " + tau);
Set<Integer> tauRange = new TreeSet<>(tau.values());
System.out.println("Range of τ: " + tauRange);

// Preimage analysis
Map<Integer, List<Integer>> preimages = new TreeMap<>();
for (var e : tau.entrySet()) {
    preimages.computeIfAbsent(e.getValue(), k -> new ArrayList<>())
            .add(e.getKey());
}
preimages.forEach((k, v) ->
    System.out.println("  τ^{-1}({" + k + "}) = " + v));

Learning Objectives

• Define binary relations on a set as subsets of $A \times A$.
• Identify and prove reflexive, symmetric, transitive and antisymmetric properties.
• Distinguish equivalence relations from partial orders.
• Compute equivalence classes and verify they form partitions.
• Implement relation-checking in Java using sets of pairs and boolean predicates.

Concept Overview

Binary Relations

A binary relation $R$ on a set $A$ is a subset $R \subseteq A \times A$. We write $aRb$ or $(a,b) \in R$ to mean "$a$ is related to $b$."

Properties of Relations

Equivalence Relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It partitions the set into equivalence classes.

Key theorem: The equivalence classes of an equivalence relation form a partition of $A$, and every partition defines an equivalence relation. (Connects to Module 4, Class 3.)

Partial Orders

A relation that is reflexive, antisymmetric and transitive is a partial order.

Examples:

• $\leq$ on $\mathbb{Z}$
• $\subseteq$ on $\mathcal{P}(A)$ (subset ordering)
• $a \mid b$ (divisibility) on $\mathbb{Z}^+$

Why this matters in CS:

• Graphs are relations: an edge $(u,v)$ means $uRv$.
• Equivalence relations model "same group" — union-find, connected components.
• Partial orders model dependencies — topological sort, build systems, task scheduling.
• Comparators in Java implement total orders (a special case of partial orders).

Formal Notation

Worked Examples

Example 1: Congruence Modulo $m$ Is an Equivalence Relation

Relation: $a \equiv b \pmod{m}$ on $\mathbb{Z}$.

Proof.

• Reflexive: $a - a = 0 = m \cdot 0$, so $m \mid (a - a)$. ✓
• Symmetric: If $m \mid (a - b)$, then $a - b = mk$, so $b - a = m(-k)$ and $m \mid (b - a)$. ✓
• Transitive: If $m \mid (a - b)$ and $m \mid (b - c)$, then $a - c = (a - b) + (b - c) = mk + ml = m(k+l)$, so $m \mid (a - c)$. ✓

Since all three hold, $\equiv \pmod{m}$ is an equivalence relation. Its equivalence classes are the congruence classes from Module 2. $\blacksquare$

Example 2: Divisibility on $\mathbb{Z}^+$ Is a Partial Order

Relation: $a \mid b$ on $\mathbb{Z}^+$.

• Reflexive: $a = a \cdot 1$, so $a \mid a$. ✓
• Antisymmetric: If $a \mid b$ and $b \mid a$, then $b = ak$ and $a = bl$, so $a = akl$, giving $kl = 1$. Since $k, l \in \mathbb{Z}^+$, $k = l = 1$, so $a = b$. ✓
• Transitive: (Proved in Module 1, Class 2.) ✓

So divisibility is a partial order on $\mathbb{Z}^+$. $\blacksquare$

Example 3: A Relation That Is NOT an Equivalence Relation

Relation: $R$ on $\mathbb{Z}$ defined by $aRb$ iff $|a - b| \leq 1$.

• Reflexive: $|a - a| = 0 \leq 1$. ✓
• Symmetric: $|a - b| = |b - a|$. ✓
• Transitive: $1R2$ and $2R3$, but $|1 - 3| = 2 > 1$, so $\neg(1R3)$. ✗

Not an equivalence relation (transitivity fails).

Example 4: Equivalence Classes

Relation: Congruence mod 3 on $\{0, 1, \ldots, 8\}$.

$[0]_3 = \{0, 3, 6\}$, $[1]_3 = \{1, 4, 7\}$, $[2]_3 = \{2, 5, 8\}$.

These are pairwise disjoint and their union is $\{0, \ldots, 8\}$ — a partition! (Module 4, Class 3.)

Example 5: Checking Properties Programmatically

Given a finite relation as a set of pairs, we can check each property by iterating:

• Reflexive: For every $a$ in the set, check $(a,a) \in R$.
• Symmetric: For every $(a,b) \in R$, check $(b,a) \in R$.
• Transitive: For every $(a,b) \in R$ and $(b,c) \in R$, check $(a,c) \in R$.

Proof Techniques Spotlight

Proving a Relation Has a Property

Each property requires a universal statement ("for all..."). To prove:

"Let $a, b$ [, $c$] be arbitrary in $A$ with the given conditions. Then..."

Disproving a Property

Find a specific counterexample:

"Consider $a = \ldots$, $b = \ldots$. We have $aRb$ but not $bRa$. So $R$ is not symmetric."

Proving Equivalence Classes Form a Partition

1. Non-empty: Each $[a]$ contains $a$ (by reflexivity).
2. Disjoint or equal: Prove that if $[a] \cap [b] \neq \emptyset$, then $[a] = [b]$.
3. Cover: Every $a \in A$ belongs to $[a]$.

Java Deep Dive

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class RelationLibrary {

    // --- Relation Representation ---

    /**
     * A relation on integers, represented as a set of pairs.
     */
    public static class Relation {
        private final Set<Integer> domain;
        private final Set<List<Integer>> pairs;

        public Relation(Set<Integer> domain, Set<List<Integer>> pairs) {
            this.domain = domain;
            this.pairs = pairs;
        }

        public boolean relates(int a, int b) {
            return pairs.contains(Arrays.asList(a, b));
        }

        // --- Property Checks ---

        public boolean isReflexive() {
            for (int a : domain) {
                if (!relates(a, a)) return false;
            }
            return true;
        }

        public boolean isSymmetric() {
            for (List<Integer> pair : pairs) {
                if (!relates(pair.get(1), pair.get(0))) return false;
            }
            return true;
        }

        public boolean isTransitive() {
            for (List<Integer> ab : pairs) {
                for (List<Integer> bc : pairs) {
                    if (ab.get(1).equals(bc.get(0))) {
                        if (!relates(ab.get(0), bc.get(1))) return false;
                    }
                }
            }
            return true;
        }

        public boolean isAntisymmetric() {
            for (List<Integer> pair : pairs) {
                int a = pair.get(0), b = pair.get(1);
                if (a != b && relates(b, a)) return false;
            }
            return true;
        }

        public boolean isEquivalenceRelation() {
            return isReflexive() && isSymmetric() && isTransitive();
        }

        public boolean isPartialOrder() {
            return isReflexive() && isAntisymmetric() && isTransitive();
        }

        // --- Equivalence Classes ---

        public Set<Integer> equivalenceClass(int a) {
            Set<Integer> cls = new TreeSet<>();
            for (int x : domain) {
                if (relates(x, a)) cls.add(x);
            }
            return cls;
        }

        public Set<Set<Integer>> allEquivalenceClasses() {
            Set<Set<Integer>> classes = new HashSet<>();
            for (int a : domain) {
                classes.add(equivalenceClass(a));
            }
            return classes;
        }

        // --- Transitive Closure ---

        public Relation transitiveClosure() {
            Set<List<Integer>> closed = new HashSet<>(pairs);
            boolean changed = true;
            while (changed) {
                changed = false;
                Set<List<Integer>> toAdd = new HashSet<>();
                for (List<Integer> ab : closed) {
                    for (List<Integer> bc : closed) {
                        if (ab.get(1).equals(bc.get(0))) {
                            List<Integer> ac = Arrays.asList(ab.get(0), bc.get(1));
                            if (!closed.contains(ac)) {
                                toAdd.add(ac);
                                changed = true;
                            }
                        }
                    }
                }
                closed.addAll(toAdd);
            }
            return new Relation(domain, closed);
        }
    }

    // --- Factory Methods ---

    /**
     * Build the congruence relation mod m on domain.
     */
    public static Relation congruenceRelation(Set<Integer> domain, int m) {
        Set<List<Integer>> pairs = new HashSet<>();
        for (int a : domain) {
            for (int b : domain) {
                if (Math.floorMod(a, m) == Math.floorMod(b, m)) {
                    pairs.add(Arrays.asList(a, b));
                }
            }
        }
        return new Relation(domain, pairs);
    }

    /**
     * Build the divisibility relation on domain.
     */
    public static Relation divisibilityRelation(Set<Integer> domain) {
        Set<List<Integer>> pairs = new HashSet<>();
        for (int a : domain) {
            for (int b : domain) {
                if (a != 0 && b % a == 0) {
                    pairs.add(Arrays.asList(a, b));
                }
            }
        }
        return new Relation(domain, pairs);
    }

    /**
     * Build a relation from a predicate.
     */
    public static Relation fromPredicate(Set<Integer> domain,
                                          BiPredicate<Integer, Integer> pred) {
        Set<List<Integer>> pairs = new HashSet<>();
        for (int a : domain) {
            for (int b : domain) {
                if (pred.test(a, b)) pairs.add(Arrays.asList(a, b));
            }
        }
        return new Relation(domain, pairs);
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Relation Library ===\n");

        Set<Integer> domain = IntStream.rangeClosed(0, 8).boxed()
                .collect(Collectors.toSet());

        // Congruence mod 3
        Relation congMod3 = congruenceRelation(domain, 3);
        System.out.println("Congruence mod 3:");
        System.out.println("  Reflexive: " + congMod3.isReflexive());
        System.out.println("  Symmetric: " + congMod3.isSymmetric());
        System.out.println("  Transitive: " + congMod3.isTransitive());
        System.out.println("  Equivalence relation: " + congMod3.isEquivalenceRelation());
        System.out.println("  Classes: " + congMod3.allEquivalenceClasses());

        // Divisibility on {1..12}
        Set<Integer> posDomain = IntStream.rangeClosed(1, 12).boxed()
                .collect(Collectors.toSet());
        Relation divides = divisibilityRelation(posDomain);
        System.out.println("\nDivisibility on {1..12}:");
        System.out.println("  Reflexive: " + divides.isReflexive());
        System.out.println("  Antisymmetric: " + divides.isAntisymmetric());
        System.out.println("  Transitive: " + divides.isTransitive());
        System.out.println("  Partial order: " + divides.isPartialOrder());

        // |a - b| <= 1 (not transitive)
        Relation close = fromPredicate(domain, (a, b) -> Math.abs(a - b) <= 1);
        System.out.println("\n|a-b| <= 1:");
        System.out.println("  Reflexive: " + close.isReflexive());
        System.out.println("  Symmetric: " + close.isSymmetric());
        System.out.println("  Transitive: " + close.isTransitive());
        System.out.println("  Equivalence: " + close.isEquivalenceRelation());

        // Transitive closure
        Relation closedClose = close.transitiveClosure();
        System.out.println("  After transitive closure — Equivalence: "
                + closedClose.isEquivalenceRelation());
    }
}

Historical Context

Giuseppe Peano (1858–1932) and Ernst Schröder (1841–1902) formalized the study of relations in the late 19th century. Schröder developed an algebra of relations that predates modern relational databases.

Equivalence relations became central in abstract algebra through the work of Évariste Galois and later algebraists, who used quotient structures (groups modulo normal subgroups, rings modulo ideals) extensively.

Edgar Codd (1970) based the relational database model on mathematical relations. SQL tables are relations (sets of tuples), and queries are operations on these relations.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. For each relation on $\{1,2,3\}$, determine reflexive/symmetric/transitive: (a) $R = \{(1,1),(2,2),(3,3)\}$ (b) $R = \{(1,2),(2,1)\}$ (c) $R = \{(1,2),(2,3),(1,3)\}$

A2. Is $<$ on $\mathbb{Z}$ a partial order? Why or why not?

A3. Name two equivalence relations you use in everyday life.

Slide Set B: Proof Problems

B1. Prove: "same parity" (both even or both odd) is an equivalence relation on $\mathbb{Z}$.

B2. Prove: if $R$ is an equivalence relation on $A$ and $[a] \cap [b] \neq \emptyset$, then $[a] = [b]$.

B3. Prove: $\subseteq$ is a partial order on $\mathcal{P}(S)$ for any set $S$.

Slide Set C: Java Coding Problems

C1. Implement isReflexive, isSymmetric, isTransitive for a relation given as Set<List<Integer>>.

C2. Compute all equivalence classes of "same remainder mod 4" on $\{0, \ldots, 15\}$.

C3. Implement transitiveClosure and test on a small relation.

Full Problem Set

Discrete Math Problems

DM1. Determine which properties hold for each relation on $\mathbb{Z}$: (a) $aRb$ iff $a + b$ is even (b) $aRb$ iff $a \leq b + 1$ (c) $aRb$ iff $a \mid b$ (on $\mathbb{Z}^+$)

DM2. Prove: "has the same number of divisors" is an equivalence relation on $\mathbb{Z}^+$. What are the equivalence classes of $[1], [2], [6]$?

DM3. Prove that if $R$ is an equivalence relation on a finite set $A$ with $|A| = n$, and there are $k$ equivalence classes of sizes $n_1, \ldots, n_k$, then $n_1 + \cdots + n_k = n$.

DM4. Prove: the intersection of two equivalence relations on $A$ is an equivalence relation.

DM5. Let $R$ be a relation on $A$ that is symmetric and transitive. Is $R$ necessarily reflexive? Prove or give a counterexample.

DM6. Prove: if $(A, \preceq)$ is a partial order and $B \subseteq A$, then $(B, \preceq \cap (B \times B))$ is also a partial order.

Java Programming Problems

JP1. Build the Relation class with isReflexive(), isSymmetric(), isTransitive(), isAntisymmetric(). Test with at least 4 different relations.

JP2. Implement allEquivalenceClasses() for an equivalence relation. Verify the classes form a partition (using Module 4's isPartition).

JP3. Implement transitiveClosure() using Warshall's algorithm. Compare with the iterative approach.

JP4. Model a small directed graph as a relation: Set<List<String>> of edges. Check if the "reachability" relation (transitive closure) is reflexive (every node reaches itself) and transitive (by construction).

JP5. Implement a Comparator<Integer> based on divisibility order. Use it with a list and explain why Collections.sort may fail (partial order, not total).

Bridge Problems

BR1. From Module 1: divisibility $a \mid b$ on $\{1, \ldots, 30\}$ is a partial order. Draw the Hasse diagram (or describe it programmatically). Use a topological sort to produce a linear extension. Verify the extension is a total order.

BR2. From Module 2: congruence mod $m$ is an equivalence relation. From Module 4: equivalence classes partition the set. From Module 5: this is a special case of the general partition theorem. Write a Java program that demonstrates all three perspectives for $m = 5$ on $\{0, \ldots, 24\}$.

Solutions

Discrete Math Solutions

DM1. (a) Reflexive: $a + a = 2a$ is even. ✓ Symmetric: $a + b = b + a$. ✓ Transitive: If $a + b$ even and $b + c$ even, then $(a+b)+(b+c) = a + 2b + c$ is even, so $a + c$ is even. ✓ Equivalence relation.

(b) Reflexive: $a \leq a + 1$. ✓ Symmetric: $1 \leq 2 + 1 = 3$ ✓, but is $2 \leq 1 + 1 = 2$? Yes. Try $1R3$: $1 \leq 4$ ✓. $3R1$: $3 \leq 2$? No. ✗ Not symmetric. Not an equivalence relation.

(c) On $\mathbb{Z}^+$: Reflexive ✓, Antisymmetric ✓, Transitive ✓. Partial order. Not symmetric (e.g., $2 \mid 4$ but $4 \nmid 2$).

DM2. Let $\tau(n)$ = number of divisors. Define $aRb \iff \tau(a) = \tau(b)$.

• Reflexive: $\tau(a) = \tau(a)$. ✓
• Symmetric: $\tau(a) = \tau(b) \implies \tau(b) = \tau(a)$. ✓
• Transitive: $\tau(a) = \tau(b)$ and $\tau(b) = \tau(c)$ $\implies$ $\tau(a) = \tau(c)$. ✓

$[1] = \{1\}$ (only 1 has exactly 1 divisor). $[2] = \{p \mid p \text{ prime}\} = \{2, 3, 5, 7, 11, \ldots\}$. $[6] = \{n \mid \tau(n) = 4\} = \{6, 8, 10, 14, 15, 21, 22, \ldots\}$. $\blacksquare$

DM5. No! Counterexample: $A = \{1, 2\}$, $R = \emptyset$. $R$ is vacuously symmetric and transitive, but not reflexive ($(1,1) \notin R$). Another counterexample: $A = \{1,2,3\}$, $R = \{(1,2),(2,1),(1,1),(2,2)\}$. Symmetric ✓, transitive ✓, but not reflexive ($(3,3) \notin R$). $\blacksquare$

Learning Objectives

• Define injective (one-to-one), surjective (onto) and bijective functions.
• Prove a function is injective by assuming $f(x_1) = f(x_2)$ and showing $x_1 = x_2$.
• Prove a function is surjective by constructing a preimage for each element in the codomain.
• Understand how bijectivity connects to invertibility.
• Prove that composition preserves injectivity and surjectivity.
• Implement injectivity/surjectivity checks in Java using Map representations.

Concept Overview

Injective (One-to-One)

A function $f: A \to B$ is injective if:

Equivalently (contrapositive): $x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$.

Intuition: Every output comes from at most one input. No two different inputs share the same output.

Surjective (Onto)

A function $f: A \to B$ is surjective if:

Intuition: Every element in the codomain $B$ is actually "hit." The range equals the codomain.

Bijective (One-to-One Correspondence)

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

Key theorem: $f: A \to B$ is bijective if and only if $f$ has an inverse function $f^{-1}: B \to A$.

Counting Implications

For finite sets $|A| = m$, $|B| = n$:

• If $f: A \to B$ is injective, then $m \leq n$.
• If $f: A \to B$ is surjective, then $m \geq n$.
• If $f: A \to B$ is bijective, then $m = n$.

This foreshadows the counting arguments of Module 7.

CS Connections

Formal Notation

Worked Examples

Example 1: Proving Injectivity

Claim: $f: \mathbb{Z} \to \mathbb{Z}$ defined by $f(n) = 2n + 3$ is injective.

Proof. Assume $f(x_1) = f(x_2)$:

So $f$ is injective. $\blacksquare$

Example 2: Proving Surjectivity

Claim: $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 3$ is surjective.

Proof. Let $y \in \mathbb{R}$. We need $x$ such that $f(x) = y$:

Check: $f\!\left(\frac{y-3}{2}\right) = 2 \cdot \frac{y-3}{2} + 3 = y$. ✓

Since $\frac{y-3}{2} \in \mathbb{R}$, every $y$ has a preimage. $\blacksquare$

Note: Over $\mathbb{Z}$, $f(n) = 2n + 3$ is NOT surjective (e.g., $y = 4$ has no integer preimage: $n = 1/2$).

Example 3: A Function That Is Neither

$f: \mathbb{Z} \to \mathbb{Z}$ defined by $f(n) = n^2$.

• Not injective: $f(2) = f(-2) = 4$ but $2 \neq -2$.
• Not surjective: no $n$ gives $f(n) = -1$.

Example 4: Composition Preserves Injectivity

Theorem: If $f: A \to B$ and $g: B \to C$ are both injective, then $g \circ f: A \to C$ is injective.

Proof. Assume $(g \circ f)(x_1) = (g \circ f)(x_2)$, i.e., $g(f(x_1)) = g(f(x_2))$.

Since $g$ is injective: $f(x_1) = f(x_2)$.

Since $f$ is injective: $x_1 = x_2$. $\blacksquare$

Example 5: Bijectivity and Inverses

$f: \{0, 1, \ldots, 25\} \to \{0, 1, \ldots, 25\}$ defined by $f(x) = (x + 3) \bmod 26$ (Caesar cipher with shift 3).

• Injective: $f(x_1) = f(x_2) \implies x_1 + 3 \equiv x_2 + 3 \pmod{26} \implies x_1 \equiv x_2 \pmod{26}$. Since $0 \leq x_1, x_2 \leq 25$, $x_1 = x_2$. ✓
• Surjective: For any $y$, take $x = (y - 3) \bmod 26$. Then $f(x) = y$. ✓

So $f$ is bijective with inverse $f^{-1}(y) = (y - 3) \bmod 26$. This connects to Module 2's modular arithmetic.

Proof Techniques Spotlight

The Injection Proof Template

1. Assume $f(x_1) = f(x_2)$.
2. Use the definition of $f$ and algebraic manipulation.
3. Conclude $x_1 = x_2$.

The Surjection Proof Template

1. Let $y$ be an arbitrary element of the codomain.
2. Construct a candidate $x$ (often by "solving" $f(x) = y$).
3. Verify $f(x) = y$.
4. Verify $x$ is in the domain.

Disproof by Counterexample

• Not injective: Find $x_1 \neq x_2$ with $f(x_1) = f(x_2)$.
• Not surjective: Find $y$ in the codomain with no preimage.

Composition Proofs

For composition, chain the property through: use injectivity/surjectivity of the inner function, then the outer function.

Java Deep Dive

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class InjectSurjectLibrary {

    // --- Injectivity / Surjectivity Checks ---

    /**
     * Check if a function (Map) is injective.
     * f is injective iff all values are distinct.
     */
    public static <A, B> boolean isInjective(Map<A, B> f) {
        Set<B> seen = new HashSet<>();
        for (B val : f.values()) {
            if (!seen.add(val)) return false; // duplicate value
        }
        return true;
    }

    /**
     * Check if a function (Map) is surjective with respect to a codomain.
     * f is surjective iff every element of codomain appears as a value.
     */
    public static <A, B> boolean isSurjective(Map<A, B> f, Set<B> codomain) {
        return f.values().containsAll(codomain);
    }

    /**
     * Check if a function (Map) is bijective.
     */
    public static <A, B> boolean isBijective(Map<A, B> f, Set<B> codomain) {
        return isInjective(f) && isSurjective(f, codomain);
    }

    /**
     * Find a collision (two domain elements mapping to same value).
     * Returns null if function is injective.
     */
    public static <A, B> List<A> findCollision(Map<A, B> f) {
        Map<B, A> inverse = new HashMap<>();
        for (Map.Entry<A, B> entry : f.entrySet()) {
            A prev = inverse.put(entry.getValue(), entry.getKey());
            if (prev != null) {
                // Use ArrayList to ensure a mutable, safe list
                List<A> collision = new ArrayList<>();
                collision.add(prev);
                collision.add(entry.getKey());
                return collision;
            }
        }
        return null;
    }

    /**
     * Find elements in codomain with no preimage.
     */
    public static <A, B> Set<B> findMissing(Map<A, B> f, Set<B> codomain) {
        Set<B> range = new HashSet<>(f.values());
        Set<B> missing = new HashSet<>(codomain);
        missing.removeAll(range);
        return missing;
    }

    // --- Inverse ---

    /**
     * Compute the inverse of a bijective function.
     * Throws if not bijective.
     */
    public static <A, B> Map<B, A> inverse(Map<A, B> f, Set<B> codomain) {
        if (!isBijective(f, codomain)) {
            throw new IllegalArgumentException("Function is not bijective");
        }
        Map<B, A> inv = new HashMap<>();
        for (Map.Entry<A, B> entry : f.entrySet()) {
            inv.put(entry.getValue(), entry.getKey());
        }
        return inv;
    }

    // --- Composition with Property Preservation ---

    /**
     * Compose two maps: (g ∘ f)(x) = g(f(x)).
     */
    public static <A, B, C> Map<A, C> compose(Map<A, B> f, Map<B, C> g) {
        Map<A, C> result = new HashMap<>();
        for (Map.Entry<A, B> entry : f.entrySet()) {
            C val = g.get(entry.getValue());
            if (val != null) {
                result.put(entry.getKey(), val);
            }
        }
        return result;
    }

    // --- Fiber / Preimage ---

    /**
     * Compute the preimage (fiber) of a value b.
     */
    public static <A, B> Set<A> fiber(Map<A, B> f, B b) {
        Set<A> result = new HashSet<>();
        for (Map.Entry<A, B> entry : f.entrySet()) {
            if (Objects.equals(entry.getValue(), b)) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    /**
     * Print fiber sizes. A function is:
     * - injective iff max fiber size = 1
     * - surjective iff min fiber size >= 1 (over codomain)
     */
    public static <A, B> void analyzeFibers(Map<A, B> f, Set<B> codomain) {
        System.out.println("Fiber analysis:");
        for (B b : codomain) {
            Set<A> fib = fiber(f, b);
            System.out.println("  f^{-1}({" + b + "}) = " + fib
                    + " (size " + fib.size() + ")");
        }
    }

    // --- Demo: Caesar Cipher ---

    public static Map<Integer, Integer> caesarEncrypt(int shift, int alphabetSize) {
        Map<Integer, Integer> f = new HashMap<>();
        for (int x = 0; x < alphabetSize; x++) {
            f.put(x, Math.floorMod(x + shift, alphabetSize));
        }
        return f;
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Inject/Surject Library ===\n");

        // f(n) = 2n + 3 on {0,...,5} -> Z
        Map<Integer, Integer> f1 = new HashMap<>();
        for (int i = 0; i <= 5; i++) f1.put(i, 2 * i + 3);
        System.out.println("f(n) = 2n+3 on {0..5}: " + f1);
        System.out.println("  Injective: " + isInjective(f1));

        // g(n) = n % 3 on {0,...,5} -> {0,1,2}
        Map<Integer, Integer> g1 = new HashMap<>();
        for (int i = 0; i <= 5; i++) g1.put(i, i % 3);
        Set<Integer> codomainG = Set.of(0, 1, 2);
        System.out.println("\ng(n) = n%3 on {0..5}: " + g1);
        System.out.println("  Injective: " + isInjective(g1));
        System.out.println("  Surjective onto {0,1,2}: " + isSurjective(g1, codomainG));
        List<Integer> collision = findCollision(g1);
        System.out.println("  Collision: " + collision);
        analyzeFibers(g1, codomainG);

        // Caesar cipher
        int n = 26;
        Map<Integer, Integer> caesar = caesarEncrypt(3, n);
        Set<Integer> alphabet = IntStream.range(0, n).boxed()
                .collect(Collectors.toSet());
        System.out.println("\nCaesar(3) on {0..25}:");
        System.out.println("  Bijective: " + isBijective(caesar, alphabet));
        Map<Integer, Integer> inv = inverse(caesar, alphabet);
        System.out.println("  Encrypt(0) = " + caesar.get(0)
                + ", Decrypt(3) = " + inv.get(3));

        // Composition preserves injectivity
        Map<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i <= 5; i++) h.put(i, i * i); // not injective on Z, but on {0..5}?
        System.out.println("\nh(n) = n^2 on {0..5}: " + h);
        System.out.println("  Injective: " + isInjective(h));
        Map<Integer, Integer> composed = compose(f1, h);
        System.out.println("  h ∘ f1 injective: " + isInjective(composed));
    }
}

Historical Context

Georg Cantor (1845–1918) used bijections to compare the sizes of infinite sets, leading to his groundbreaking theorem that $|\mathbb{R}|> |\mathbb{N}|$ (the reals are uncountable). His "diagonal argument" for surjection failure remains one of the most elegant proofs in mathematics.

The classification into injective/surjective/bijective became standard through Bourbaki (1930s–), the pseudonym of a group of French mathematicians who systematized modern mathematics. They also introduced the arrow notation $f: A \to B$.

In cryptography, Claude Shannon (1949) established that a secure cipher must be a bijection on the message space — if encryption is not injective, information is lost; if not surjective, some ciphertexts can never appear.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. For $f: \{1,2,3\} \to \{a,b,c,d\}$ with $f(1) = a, f(2) = b, f(3) = c$: injective? surjective? bijective?

A2. Can a function from a 5-element set to a 3-element set be injective? Surjective? Justify.

A3. If HashMap maps keys to values, is the key→value mapping always injective? Is it always surjective?

A4. True or false: The composition of two surjective functions is surjective.

Slide Set B: Proof Problems

B1. Prove: $f(n) = 3n - 7$ is injective on $\mathbb{Z}$.

B2. Prove or disprove: $f(n) = n \bmod 5$ is surjective from $\mathbb{Z}$ to $\{0,1,2,3,4\}$.

B3. Prove: If $g \circ f$ is surjective, then $g$ is surjective.

B4. Prove: If $g \circ f$ is injective, then $f$ is injective.

Slide Set C: Java Coding Problems

C1. Write isInjective(Map<Integer, Integer> f) and test with $f(n) = n^2$ on $\{-3, \ldots, 3\}$.

C2. Write inverse(Map<A, B> f) that returns the inverse map. Throw an exception if $f$ is not bijective.

C3. Compose two maps and check whether the composition preserves injectivity.

Full Problem Set

Discrete Math Problems

DM1. Let $f: \mathbb{Z} \to \mathbb{Z}$ be $f(n) = 5n + 2$. Prove $f$ is injective. Is $f$ surjective? Prove or disprove.

DM2. Let $f: \mathbb{R} \to \mathbb{R}$ be $f(x) = x^3$. Prove $f$ is bijective. Find $f^{-1}$.

DM3. Let $f: A \to B$ and $g: B \to C$. Prove: if $g \circ f$ is injective, then $f$ is injective.

DM4. Let $f: A \to B$ and $g: B \to C$. Prove: if $g \circ f$ is surjective, then $g$ is surjective.

DM5. Prove: if $f: A \to B$ is a bijection, then $|A| = |B|$ for finite sets.

DM6. Let $f: \{0, \ldots, n-1\} \to \{0, \ldots, n-1\}$ be defined by $f(x) = (ax + b) \bmod n$. Under what conditions on $a$ and $n$ is $f$ a bijection? (Connect to Module 2, units mod $n$.)

Java Programming Problems

JP1. Implement isInjective, isSurjective, isBijective for Map<Integer, Integer> with a given codomain.

JP2. Given a bijective map, compute its inverse. Verify that $f^{-1}(f(x)) = x$ for all $x$ in the domain.

JP3. Build two injective maps $f$ and $g$, compose them, and verify the composition is injective.

JP4. Build a hash function from strings to integers (using hashCode() % tableSize). Find collisions, demonstrating the function is not injective. Compute fibers.

JP5. Implement the Caesar cipher as a bijective map. Encrypt a message, decrypt using the inverse. Extend to an affine cipher $f(x) = (ax + b) \bmod 26$ and compute the inverse using modular inverse from Module 2.

Bridge Problems

BR1. From Module 2: the map $f(x) = ax \bmod n$ is a bijection iff $\gcd(a, n) = 1$. Verify this for $n = 26$ and all values of $a$ from 1 to 25, using your GCD function from Module 1.

BR2. From Module 5 Class 2: an equivalence relation on $A$ partitions $A$ into classes. Define the canonical map $\pi: A \to A/R$ by $\pi(a) = [a]$. Prove $\pi$ is surjective. When is $\pi$ injective?

BR3. From Module 4: the function $\text{powerSet}: \{0, 1, \ldots, n-1\} \to \{0,1\}^n$ that maps a subset to its characteristic function (bit vector) is a bijection from $\mathcal{P}(\{0,\ldots,n-1\})$ to $\{0,1\}^n$. Verify in Java for $n = 4$.

Solutions

Discrete Math Solutions

DM1. Injective: $5x_1 + 2 = 5x_2 + 2 \implies 5x_1 = 5x_2 \implies x_1 = x_2$. ✓

Not surjective over $\mathbb{Z}$: $y = 1$ requires $5n + 2 = 1$, so $n = -1/5 \notin \mathbb{Z}$. $\blacksquare$

DM2. Injective: $x_1^3 = x_2^3 \implies x_1 = x_2$ (cube root is well-defined on $\mathbb{R}$). Surjective: For any $y \in \mathbb{R}$, take $x = y^{1/3}$. Then $f(x) = y$. Inverse: $f^{-1}(y) = y^{1/3}$. $\blacksquare$

DM3. Assume $g \circ f$ is injective. Let $f(x_1) = f(x_2)$. Then $g(f(x_1)) = g(f(x_2))$, i.e., $(g \circ f)(x_1) = (g \circ f)(x_2)$. Since $g \circ f$ is injective, $x_1 = x_2$. So $f$ is injective. $\blacksquare$

DM4. Assume $g \circ f$ is surjective. Let $c \in C$. Then $\exists a \in A: (g \circ f)(a) = c$. So $g(f(a)) = c$. Let $b = f(a) \in B$. Then $g(b) = c$. So for every $c$, $\exists b: g(b) = c$. Thus $g$ is surjective. $\blacksquare$

DM5. If $f$ is bijective: injective $\implies |A| \leq |B|$, surjective $\implies |A| \geq |B|$. Therefore $|A| = |B|$. $\blacksquare$

DM6. $f(x) = (ax + b) \bmod n$ is bijective iff $\gcd(a, n) = 1$. If $\gcd(a, n) = 1$, then $a$ has an inverse $a^{-1}$ mod $n$, and $f^{-1}(y) = a^{-1}(y - b) \bmod n$. If $\gcd(a, n) = d > 1$, then $f(0) = b$ and $f(n/d) = (a \cdot n/d + b) \bmod n = b$ (since $a \cdot n/d$ is a multiple of $n$), so $f$ is not injective. $\blacksquare$

Java Programming Solutions

JP4.

public static void hashCollisionDemo() {
    String[] words = {"cat", "dog", "bat", "tab", "act", "god", "tac"};
    int tableSize = 5;
    Map<String, Integer> hashMap = new HashMap<>();
    for (String w : words) {
        hashMap.put(w, Math.floorMod(w.hashCode(), tableSize));
    }
    System.out.println("Hash map: " + hashMap);
    System.out.println("Injective: " + isInjective(hashMap));
    Set<Integer> codomain = IntStream.range(0, tableSize).boxed()
            .collect(Collectors.toSet());
    analyzeFibers(hashMap, codomain);
}

JP5.

public static void affineCipherDemo() {
    int a = 5, b = 8, n = 26;
    // Verify gcd(a, n) = 1
    // From Module 1: gcd(5, 26) = 1, so a^{-1} mod 26 exists
    // Extended Euclidean: 5 * 21 = 105 = 4*26 + 1, so a^{-1} = 21

    Map<Integer, Integer> encrypt = new HashMap<>();
    for (int x = 0; x < n; x++) {
        encrypt.put(x, Math.floorMod(a * x + b, n));
    }
    Set<Integer> alpha = IntStream.range(0, n).boxed().collect(Collectors.toSet());
    System.out.println("Affine(5,8) bijective: " + isBijective(encrypt, alpha));

    int aInv = 21; // precomputed
    Map<Integer, Integer> decrypt = new HashMap<>();
    for (int y = 0; y < n; y++) {
        decrypt.put(y, Math.floorMod(aInv * (y - b), n));
    }
    // Verify round-trip
    for (int x = 0; x < n; x++) {
        assert decrypt.get(encrypt.get(x)) == x;
    }
    System.out.println("Round-trip verified for all 26 letters.");
}