Chapter 1 Sets and Mappings

Sorting blocks by color, dividing food into what we like and what we do not—classification is one of the ways we make sense of the world. Everyday operations such as “these things go together” and “those go somewhere else” offer an intuitive starting point for approaching the language of sets.

Between everyday classification and rigorous set notation lies one more step: stating these familiar operations precisely, in definitions that anyone can check word by word.

Yet humans spent two thousand years computing before turning back to write these familiar operations down in rigorous symbols.

Why such a long detour? Because computation ran into a crisis.

The central task of ancient mathematics was to compute particular cases: how large this field is, how much tax is owed, how long this hypotenuse is. The Nine Chapters on the Mathematical Art works this way, the Babylonian clay tablets work this way, and so do the Egyptian papyri. Greek geometry took a step further—Euclid proved properties of all triangles, not of one particular triangle—but it still relied on geometric intuition, and wherever a boundary blurred it let the picture do the talking.

In the nineteenth century the boundaries of intuition began to collapse. In 1872 Weierstrass constructed a function that is continuous everywhere and differentiable nowhere. Geometric intuition says such an object should not exist at all, and yet it can be proved from the rigorous definitions that it is continuous everywhere and differentiable at no point. Pictures could no longer be trusted. Mathematicians realized that a feeling for individual objects was no longer enough: they had to say precisely which class of things was under discussion, and then reason rigorously about that entire class.

Dedekind conceived the idea of the Dedekind cut in 1858 and published it in 1872, using it to redefine the real numbers—not by producing a formula to compute with, but by defining each real number as a partition of the set of rational numbers. This showed another way to build a number system: characterizing numbers through sets and their properties, rather than only supplying a computational procedure. Cantor followed close behind. In the 1870s he built set theory, giving this way of describing objects a general language: sets, and the mappings between them.

This is the historical turning point at which mathematics moved from computing particular cases to discussing the properties of an entire class of objects.

In the middle of the twentieth century, a group of French mathematicians pushed that turn to its extreme.

In 1935 a number of young French mathematicians, writing under the pen name “Nicolas Bourbaki,” began an enormously ambitious series of books, the Éléments de mathématique. The title pays homage to Euclid’s Elementa, but it carries a deliberate provocation. In Euclid’s day mathematics was a collection of many disciplines, so French normally writes the plural mathématiques; Bourbaki insisted on the singular mathématique—a declaration that mathematics is one subject, with a single foundation, and that the foundation is set theory. The name belongs to no real person but to a collective whose members included André Weil, Henri Cartan, and Jean Dieudonné, among the finest mathematicians of the day. Their goal was single-minded: to rewrite all of modern mathematics from the ground up in the language of set theory, leaving no place that appeals to intuition or leans on a picture.

Bourbaki’s influence was profound and contested. Admirers say the group gave twentieth-century mathematics a unified foundation of language; critics say the books are too abstract, that they expel every trace of geometric intuition, and that reading them feels like reading statutes. Either way, by making formalization the highest standard of mathematics, Bourbaki changed the face of mathematical education and research for good.

The structural viewpoint that Bourbaki emphasized also offers a point of entry for thinking about children’s cognition. The Swiss psychologist Jean Piaget observed that the classifying, ordering, and spatial operations that children gradually develop can be set side by side with the structural viewpoint of modern mathematics.

This comparison gives the chapter a point of departure: sets and mappings, abstract as they look, can be approached through the everyday activities of classifying, ordering, and matching. It suggests that abstract language can connect with everyday cognition; it does not mean that the full concept of a set, or its formal definition, is innate.

The task of this chapter is to build the foundation of that formal language.

Set theory is not an isolated chapter in this book; it is the bedrock language of the whole book. “A vector space is a set equipped with two operations satisfying eight axioms”—this sentence speaks about all vector spaces, not about one concrete example. Once a theorem has been proved from it, that theorem applies at once to $\mathbb{R}^n$ , to polynomial spaces, to function spaces, and to matrix spaces, with no need to redo the work for each example. This is something computation cannot do, and it is what the language of sets does most naturally.

Chapter Structure and Learning Objectives¶

§1.1 establishes the precise definition of a set, along with subsets, power sets, and the set operations (union, intersection, complement, and the Cartesian product). Simple as these operations look, they are the precondition for describing every later notion of “space” and “structure” precisely.

§1.2 introduces the notion of a mapping, generalizing the traditional idea of a “function” from correspondences between numbers to correspondences between arbitrary sets. The section unfolds in three layers. §1.2.1 supplies the basic vocabulary: mapping, domain, codomain, range, and composition. §1.2.2 takes up the preimage—the reverse analysis of a mapping: given an output, which inputs produce it? §1.2.3 uses that idea to classify mappings as injective, surjective, and bijective, and gives a unified characterization in terms of the size of preimage sets. Linear transformations, matrix multiplication, and the choice of a coordinate system are all, mathematically, special cases of mappings.

§1.3 is the chapter summary; it reviews the theoretical thread and ties it to the chapters that follow. The preimage will reappear in set form again and again—in the solution sets of linear systems in Chapter 6, and in the definition of eigenspaces in Chapter 8. The classification of mappings returns in algebraic dress in Chapter 4, in the rank-nullity theorem for linear mappings.

By the end of this chapter you will possess a set of tools for speaking. Every chapter that follows builds with those tools.

1.1 Foundations of Set Theory¶

We begin with the most basic notions, laying a solid mathematical foundation for the central theories of linear algebra: vector spaces, linear transformations, and everything built on them.

1.1.1 Definition and Representation of Sets¶

A set may be presented in either of the following ways:

Roster notation: list all of the elements directly, as in $A = \{1, 2, 3, 4, 5\}$
Set-builder notation: describe the set by a property or logical condition that its elements satisfy, as in $B = \{x | x \text{ is a positive even number less than } 10\}$

Logical and Set-Theoretic Symbols Used in This Book

So that a first encounter with a formal definition does not bring you to a halt, we fix here a few symbols that run through the entire book:

$\{x \mid P(x)\}$ : the set of all $x$ for which the statement $P(x)$ holds (the vertical bar $\mid$ is read “such that”).
$\forall$ : “for all”; $\exists$ : “there exists”. For example, $\forall x \in A,\ \exists y \in B$ is read “for every $x$ in $A$ there exists some $y$ in $B$ ”.
$\Rightarrow$ : “implies” (if ... then ...); $\Leftrightarrow$ : “if and only if” (implication in both directions).
$|S|$ : the cardinality of the set $S$ , that is, its number of elements (for a finite set, simply a count).

Example 1 (Number Systems)

The natural numbers $\mathbb{N}$ : $\{0, 1, 2, 3, ...\}$ or $\{1, 2, 3, ...\}$ (depending on the convention adopted)
The integers $\mathbb{Z}$ : $\{..., -2, -1, 0, 1, 2, ...\}$
The finite field $\mathbb{F}_p$ : $\{0,1,2,...,p-1\}$ , where $p$ is a prime number and both addition and multiplication are carried out “modulo $p$ ” (for instance, in $\mathbb{F}_5$ we have $3+4=2$ ); the rigorous definition of a field appears in a later chapter.
The rational numbers $\mathbb{Q}$ : $\{p/q | p, q \in \mathbb{Z}, q \neq 0\}$
The real numbers $\mathbb{R}$ : all rational numbers together with all irrational numbers
The complex numbers $\mathbb{C}$ : $\{a + bi | a, b \in \mathbb{R}, i^2 = -1\}$

1.1.2 Relations and Operations Between Sets¶

The most common way to prove that two sets are equal is double inclusion: prove $A \subseteq B$ and $B \subseteq A$ separately, and once both hold we have $A = B$ . To prove a single inclusion $A \subseteq B$ , the standard template is one sentence long—take an arbitrary $x \in A$ and derive $x \in B$ . The example below demonstrates that template in its most basic setting.

Example 2 (Sets Defined by Their Relation to Others)

The universal set $U$ : within a particular discussion, the set containing every element under consideration
A singleton: a set containing exactly one element, such as $\{a\}$
The empty set $\emptyset$ , also written $\{\}$ , contains no elements at all, and it is a subset of every set.

Why is the empty set a subset of every set? The claim conflicts with intuition (if it contains nothing, how can it be “contained in” anything?), but reading Definition 2 word for word dissolves the difficulty: to refute $\emptyset \subseteq A$ we would have to find an element of $\emptyset$ that does not belong to $A$ ; since $\emptyset$ has no elements to find, no refutation is possible, and the statement stands. Reasoning of this kind—“true because no counterexample can be found”—is called vacuous truth, and it is our first demonstration of the formal spirit of reasoning strictly from the definition.

Definition 5 (Cartesian Product)

The Cartesian product (direct product) $A \times B$ of sets $A$ and $B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$ .

Intuition. Picture the Cartesian product as a grid whose columns are indexed by the elements of $A$ and whose rows are indexed by the elements of $B$ ; each intersection in the grid is one ordered pair. For example, if $A = \{1, 2\}$ and $B = \{x, y\}$ , then $A \times B = \{(1,x), (1,y), (2,x), (2,y)\}$ .

Generalization to the $n$ -fold product. The two-set definition above generalizes step by step. Given $n$ sets $A_0, A_1, \ldots, A_{n-1}$ , their direct product

A_0 \times A_1 \times \cdots \times A_{n-1} = \{(a_0, a_1, \ldots, a_{n-1}) \mid a_i \in A_i,\ i = 0, 1, \ldots, n-1\}

(2)

is the set of all ordered $n$ -tuples. In particular, taking every $A_i$ to be the set of real numbers $\mathbb{R}$ gives the $n$ -dimensional coordinate space

\mathbb{R}^n = \underbrace{\mathbb{R} \times \cdots \times \mathbb{R}}_{n \text{ copies}}.

(3)

This is exactly the concrete support for the statement in Chapter 2 that a vector space “is first of all a set.”

Example 4 (Venn Diagrams)

Set operations can be displayed directly by means of a Venn diagram. A union appears as the whole of the two circles, and an intersection as the region where they overlap.

The two figures below present the idea in a counting setting: draw one circle for “students majoring in a given subject” and another for “students who have a given programming skill,” so that the overlap is the number of people meeting both conditions. The inclusion-exclusion principle can be read straight off the diagram: the number of elements in the union of two sets equals the sum of their individual counts, minus the intersection, which would otherwise be counted twice,

|A \cup B| = |A| + |B| - |A \cap B|.

(4)

The intersection must be subtracted once because it has been counted once inside $|A|$ and once inside $|B|$ .

# This code block is not shown in the printed book; only the figure is displayed

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np

np.set_printoptions(precision=4, suppress=True, linewidth=100)

# Fonts: the English edition needs no CJK font, so nothing is downloaded when _lang == 'en';
# the Chinese editions use this same block to fetch Noto Sans TC/SC where no CJK font is installed
import os, urllib.request
import matplotlib.font_manager as fm
_lang = 'en'
_cjk = ['Microsoft JhengHei', 'PingFang TC', 'Noto Sans CJK TC', 'Noto Sans TC']
_have = {f.name for f in fm.fontManager.ttflist}
if _lang != 'en' and not _have & set(_cjk):
    _font = os.path.join(os.path.expanduser('~'), '.cache', 'fonts', 'NotoSansTC.ttf')
    try:
        if not os.path.exists(_font):
            os.makedirs(os.path.dirname(_font), exist_ok=True)
            urllib.request.urlretrieve('https://github.com/google/fonts/raw/main/ofl/notosanstc/NotoSansTC%5Bwght%5D.ttf', _font + '.part')
            os.replace(_font + '.part', _font)
        fm.fontManager.addfont(_font)
        _have.add('Noto Sans TC')
    except OSError as err:
        print('Could not download the CJK font; Chinese text in figures may not display:', err)
plt.rcParams['font.family'] = [f for f in _cjk if f in _have] + ['DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False

# --- Color palette (Accent Mix) ---
C_BG   = "#F8F8F8"   # canvas background
C_GRID = "#D6D6D6"   # gridlines
C_AXIS = "#000000"   # text
C_V1   = "#57068C"   # set A (violet)
C_V2   = "#006385"   # set B (deep blue)
C_T1   = "#2AD2C9"   # set C (teal)
C_WARN = "#FF5D47"   # universal-set label (orange)
C_AUX  = "#AB82C5"   # bounding box (light violet)

# --- Visual hierarchy helpers ---
def print_header(title):
    print("=" * 60)
    print(f"  {title}")
    print("=" * 60)

def print_step(step, desc):
    print(f"\n▶ Step {step}: {desc}")
    print("-" * 40)

def compare_print(label, actual, expected_desc):
    print(f"\n[{label}]")
    print(f"  Computed value: {actual}")
    print(f"  Expected value: {expected_desc}")

# ============================================================
print_header("Example 1.1 | Venn Diagrams for Set Operations")
# ============================================================

# --- Step 0: define the plotting helper ---
def draw_venn_with_box(data, labels, title="Venn diagram with bounding box"):
    """
    Draw a Venn diagram with a bounding box (two or three sets).

    Two-set format:   data = {'A_only', 'B_only', 'AB', 'outside'}
    Three-set format: data = {'A_only', 'B_only', 'C_only',
                              'AB_only', 'AC_only', 'BC_only', 'ABC', 'outside'}
    """
    fig, ax = plt.subplots(1, 1, figsize=(10, 8))
    fig.patch.set_facecolor(C_BG)
    ax.set_facecolor(C_BG)

    # bounding box for the universal set
    outer_box = patches.Rectangle(
        (-2, -1.5), 4, 3,
        linewidth=3, edgecolor=C_AXIS,
        facecolor=C_AUX, alpha=0.12
    )
    ax.add_patch(outer_box)

    if len(labels) == 2:
        # draw the two-set Venn diagram (circles A and B)
        circle_styles = [
            ((-0.3, 0), C_V1, 0.45),
            (( 0.3, 0), C_V2, 0.45),
        ]
        for center, color, alpha in circle_styles:
            ax.add_patch(patches.Circle(
                center, 0.6, alpha=alpha,
                facecolor=color, edgecolor=color, linewidth=2
            ))

        # fill in the count for each region
        ax.text(-0.6, 0, str(data.get('A_only', 0)),
                fontsize=14, ha='center', va='center', color='white', fontweight='bold')
        ax.text( 0.6, 0, str(data.get('B_only', 0)),
                fontsize=14, ha='center', va='center', color='white', fontweight='bold')
        ax.text( 0.0, 0, str(data.get('AB', 0)),
                fontsize=14, ha='center', va='center', color=C_AXIS, fontweight='bold')
        ax.text(-1.5, 1, str(data.get('outside', 0)),
                fontsize=12, ha='center', va='center',
                bbox=dict(boxstyle="round,pad=0.3", facecolor='white', edgecolor=C_AUX))

        ax.text(-1.1, 0.8, labels[0], fontsize=16, color=C_V1, fontweight='bold')
        ax.text( 0.7, 0.8, labels[1], fontsize=16, color=C_V2, fontweight='bold')

    elif len(labels) == 3:
        # draw the three-set Venn diagram (circles A, B and C)
        circle_styles = [
            ((-0.2, 0.3), C_V1, 0.40),
            (( 0.2, 0.3), C_V2, 0.40),
            (( 0.0,-0.3), C_T1, 0.40),
        ]
        label_colors = [C_V1, C_V2, C_T1]

        for center, color, alpha in circle_styles:
            ax.add_patch(patches.Circle(
                center, 0.5, alpha=alpha,
                facecolor=color, edgecolor=color, linewidth=2
            ))

        # fill in the count for each region
        positions = {
            'A_only':  (-0.45,  0.50),
            'B_only':  ( 0.45,  0.50),
            'C_only':  ( 0.00, -0.70),
            'AB_only': ( 0.00,  0.60),
            'AC_only': (-0.30,  0.00),
            'BC_only': ( 0.30,  0.00),
            'ABC':     ( 0.00,  0.10),
            'outside': (-1.50,  1.00),
        }
        for region, pos in positions.items():
            kw = dict(fontsize=12, ha='center', va='center',
                      color=C_AXIS, fontweight='bold')
            if region == 'outside':
                kw['bbox'] = dict(boxstyle="round,pad=0.3",
                                  facecolor='white', edgecolor=C_AUX)
            ax.text(pos[0], pos[1], str(data.get(region, 0)), **kw)

        label_positions = [(-0.8, 0.8), (0.5, 0.8), (-0.1, -1.0)]
        for pos, color, label in zip(label_positions, label_colors, labels):
            ax.text(pos[0], pos[1], label, fontsize=16,
                    color=color, fontweight='bold')

    total = sum(data.values())
    ax.text(0, -1.2, rf"Number of elements in the universal set $|U|$ = {total}",
            fontsize=14, ha='center', va='center',
            bbox=dict(boxstyle="round,pad=0.5",
                      facecolor=C_WARN, alpha=0.25, edgecolor=C_WARN))

    ax.set_xlim(-2.2, 2.2)
    ax.set_ylim(-1.7, 1.7)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_title(title, fontsize=16, pad=20, color=C_AXIS)
    plt.tight_layout()
    return fig, ax


# --- Step 1: two-set Venn diagram (Mathematics ∪ Physics) ---
print_step(1, "Draw the two-set Venn diagram: Mathematics ∪ Physics")

data_2 = {
    'A_only':  25,   # in A only
    'B_only':  20,   # in B only
    'AB':      15,   # in A ∩ B
    'outside': 10,   # in the universal set but not in A ∪ B
}
compare_print(
    "|A ∪ B|",
    data_2['A_only'] + data_2['B_only'] + data_2['AB'],
    "|A| + |B| − |A ∩ B| = 40 + 35 − 15 = 60 (inclusion-exclusion principle)"
)
fig1, _ = draw_venn_with_box(data_2, ['Mathematics', 'Physics'], "Distribution of Student Majors")
plt.show()

# --- Step 2: three-set Venn diagram (Python ∩ R ∩ SQL skills) ---
print_step(2, "Draw the three-set Venn diagram: distribution of Python, R and SQL skills")

data_3 = {
    'A_only':  20,
    'B_only':  15,
    'C_only':  18,
    'AB_only':  8,
    'AC_only':  6,
    'BC_only':  5,
    'ABC':      3,
    'outside': 12,
}
compare_print(
    "|A ∪ B ∪ C|",
    sum(v for k, v in data_3.items() if k != 'outside'),
    "|A|+|B|+|C|−|AB|−|AC|−|BC|+|ABC| = (20+8+6+3)+(15+8+5+3)+(18+6+5+3)−11−9−8+3 = 75 (inclusion-exclusion principle)"
)
fig2, _ = draw_venn_with_box(data_3, ['Python', 'R', 'SQL'], "Distribution of Programming Skills")
plt.show()

print("\n✓ Done. Edit the numbers in the data dictionaries to update the region counts.")

§1.1 Summary

This section answered a fundamental question: how can we describe “a collection of objects,” and the relationships among such collections, in precise language?

The three key properties of a set—definiteness, distinctness, unorderedness—look simple, yet they are exactly the apparatus needed to remove the vagueness of intuition. When Dedekind defined the real numbers as partitions of the set of rational numbers, it was these three properties that allowed “describing an object” to take the place of “computing an object.” On that basis, subsets and power sets supply the language of whole and part, while the Cartesian product $A \times B$ gathers all possible pairings of two sets into a single new set—the direct prototype of the ordered-pair structure underlying “domain × codomain” later on. The four operations of union, intersection, complement, and set difference endow sets with algebraic manipulability, which is what makes “discussing the properties of an entire class of objects” a workable mathematical activity.

Once we understand what a set is, and how sets are contained in one another and combined, the next natural question is this: what kinds of correspondence can be set up between two sets? That is precisely the central question that the theory of mappings in §1.2 sets out to answer.

1.2. Foundations of Mappings¶

Linear algebra begins with multivariable linear functions, that is, with linear mappings. Elementary as this class of functions is, it lays the groundwork for understanding far more intricate mathematical ideas. As you go further, you will find that other kinds of functions also have their place in linear algebra.

1.2.1. Definition and Basic Notions of a Mapping¶

A function may be written as $f: X \rightarrow Y$ , $y = f(x)$ , where $x \in X$ and $y \in Y$ .

Definition 8 (Domain, Codomain, Image, Image of a Set, Range)

Domain: the set $X$ in a mapping $f: X \rightarrow Y$
Codomain: the set $Y$ in a mapping $f: X \rightarrow Y$
Image of an element: for $x \in X$ , the element $f(x) \in Y$ is called the image of $x$ .
Image of a set: for a subset $A \subseteq X$ , the image of $A$ under $f$ is $f[A] = \{f(x) | x \in A\}$ (also written $f(A)$ )
Range (that is, the image of $f$ ): $f[X] = \operatorname{Im}f = \{y \in Y | \exists x \in X, y = f(x)\}$ , the set of the images of all elements of $X$ . The range is in general a subset of the codomain, $f[X] \subseteq Y$ , and the two need not coincide—this is exactly the distinction emphasized in The Difference Between the Image and the Codomain below.

Example 7 (Deciding Whether Two Mappings Are Equal)

Consider the following three mappings:

$f_0: \mathbb{R} \rightarrow \mathbb{R}$ , $f_0(x) = x^2$
$f_1: \mathbb{R} \rightarrow \mathbb{R}$ , $f_1(x) = (-x)^2$
$f_2: [0,+\infty) \rightarrow \mathbb{R}$ , $f_2(x) = x^2$

Analysis.

$f_0 = f_1$ , because they have the same domain and the same codomain, and for every $x \in \mathbb{R}$ we have $f_0(x) = x^2 = (-x)^2 = f_1(x)$
$f_0 \neq f_2$ : although the rule of correspondence is the same (squaring in both cases), the domains differ, since $f_0$ may be applied to negative numbers while $f_2$ may be applied only to nonnegative ones

Forming a composite mapping may be understood as “apply $f$ first, then apply $g$ .”

Example 8 (Associativity of Composition)

Let:

$f: \mathbb{R} \rightarrow \mathbb{R}$ , $f(x) = x + 1$
$g: \mathbb{R} \rightarrow \mathbb{R}$ , $g(x) = 2x$
$h: \mathbb{R} \rightarrow \mathbb{R}$ , $h(x) = x^2$

Verifying associativity:

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

Hence $(h \circ g) \circ f = h \circ (g \circ f)$ .

With the same $f$ and $g$ as in this example, we can also compare $g(f(x))=2x+2$ with $f(g(x))=2x+1$ ; hence $g\circ f\neq f\circ g$ .

1.2.2 The Preimage¶

Property 2 (Properties of Images and Preimages)

For a mapping $f: X \rightarrow Y$ and subsets $A_0, A_1 \subseteq X$ , $B_0, B_1 \subseteq Y$ :

$A_0 \subseteq A_1 \Rightarrow f[A_0] \subseteq f[A_1]$
$B_0 \subseteq B_1 \Rightarrow f^{-1}[B_0] \subseteq f^{-1}[B_1]$
$f[A_0 \cup A_1] = f[A_0] \cup f[A_1]$
$f[A_0 \cap A_1] \subseteq f[A_0] \cap f[A_1]$ (note: equality need not hold)
$f^{-1}[B_0 \cup B_1] = f^{-1}[B_0] \cup f^{-1}[B_1]$
$f^{-1}[B_0 \cap B_1] = f^{-1}[B_0] \cap f^{-1}[B_1]$

1.2.3 Types of Mappings¶

Characteristic features of a bijection:

every element of the domain is mapped to a unique element of the range
every element of the range has exactly one preimage

Example 12 (A Bijection and Its Inverse Function)

The function $f(x) = 2x + 3$ (from $\mathbb{R}$ to $\mathbb{R}$ ) is bijective:

it is injective: if $2x_0 + 3 = 2x_1 + 3$ , then $x_0 = x_1$
it is surjective: for any $y \in \mathbb{R}$ there exists $x = f^{-1}(y) = \frac{y-3}{2} \in \mathbb{R}$ with $f(x) = y$
from the preimage point of view: for any $y \in \mathbb{R}$ , the preimage $f^{-1}[\{y\}] = \{\frac{y-3}{2}\}$ contains exactly one element

It is easy to check that $f^{-1}(f(x)) = f^{-1}(2x+3) = \frac{(2x+3)-3}{2} = x$ and $f(f^{-1}(y)) = f(\frac{y-3}{2}) = 2\cdot\frac{y-3}{2}+3 = y-3+3 = y$

A Unified Theory of Preimages and Types of Mappings¶

We have now understood the types of mappings from two angles, the traditional definitions and the preimage characterizations. In fact these two formulations reveal a deeper unity in the theory of mappings:

Exercise 7 (Classifying Mappings by the Preimage Method)

Use the preimage characterizations to classify the following mappings:

$f: \mathbb{R} \rightarrow \mathbb{R}^+$ , $f(x) = e^x$
$g: \mathbb{R} \rightarrow \mathbb{R}$ , $g(x) = x^3 - x$
$h: [0,2\pi) \rightarrow [-1,1]$ , $h(x) = \sin x$

For each function, analyze the structure of its preimages $f^{-1}[\{y\}]$ .

Hint (part 2). Begin by observing that $g(-1) = g(0) = g(1) = 0$ . A single image $y = 0$ turns out to have three preimages, that is, $|g^{-1}[\{0\}]| = 3 > 1$ , which refutes injectivity outright—there is no need to solve the general cubic equation.

The geometric tests in the table below apply only to real-valued functions of a real variable.

Type of mapping	Traditional defining feature	Preimage characterization	Geometric test	Example
General mapping	each $x$ corresponds to a unique $y$	preimages may be empty or large	any graph of a function	$f: \mathbb{R} \to \mathbb{R},\ f(x) = x^2$
Injective	$f(x_0) = f(x_1) \Rightarrow x_0 = x_1$	$\operatorname{card}(f^{-1}[\{y\}]) \leq 1$	a horizontal line meets it at most once	$f: \mathbb{R} \to \mathbb{R},\ f(x) = 2x+1$
Surjective	every $y \in Y$ has a preimage	$f^{-1}[\{y\}] \neq \emptyset$	covers the whole codomain	$f: \mathbb{R} \to \mathbb{R},\ f(x) = x^3$
Bijective	both injective and surjective	$\operatorname{card}(f^{-1}[\{y\}]) = 1$	for a real-valued function of a real variable, each horizontal line at a height $y\in Y$ meets the graph exactly once	$f: \mathbb{R} \to (0,\infty),\ f(x) = e^x$

# This code block is not shown in the printed book; only the figure is displayed

import numpy as np
import plotly.graph_objects as go

np.set_printoptions(precision=4, suppress=True, linewidth=100)

# --- Color palette (Accent Mix) ---
C_BG   = "#F8F8F8"   # canvas background
C_GRID = "#D6D6D6"   # gridlines (used by plotly)
C_V1   = "#57068C"   # violet (spare)
C_V2   = "#006385"   # domain nodes (deep blue)
C_T1   = "#2AD2C9"   # mapping arrows (teal)
C_WARN = "#FF5D47"   # codomain nodes (orange)
C_AUX  = "#AB82C5"   # dropdown background (light violet)
C_AREA = "rgba(87, 6, 140, 0.08)"   # set-boundary fill (transparent violet)

# --- Visual hierarchy helpers ---
def print_header(title):
    print("=" * 60)
    print(f"  {title}")
    print("=" * 60)

def print_step(step, desc):
    print(f"\n▶ Step {step}: {desc}")
    print("-" * 40)

def compare_print(label, actual, expected_desc):
    print(f"\n[{label}]")
    print(f"  Computed value: {actual}")
    print(f"  Expected value: {expected_desc}")

# ============================================================
print_header("Example 1.2 | Interactive Figure of Mapping Types")
# ============================================================

# --- Step 0: define the data for each type of mapping ---
print_step(0, "Define five types of mapping (domain X, codomain Y, rule f)")

FUNCTION_TYPES = {
    "Injective": {
        "domain":   [1, 2, 3, 4],
        "codomain": ['a', 'b', 'c', 'd', 'e'],
        "mapping":  {1: 'a', 2: 'b', 3: 'c', 4: 'd'},
        "desc": "One-to-one: distinct x are sent to distinct f(x), and some codomain elements are never hit",
    },
    "Surjective": {
        "domain":   [1, 2, 3, 4, 5],
        "codomain": ['a', 'b', 'c', 'd'],
        "mapping":  {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'a'},
        "desc": "Onto: every codomain element has a preimage; many-to-one is allowed",
    },
    "Bijective": {
        "domain":   [1, 2, 3, 4],
        "codomain": ['a', 'b', 'c', 'd'],
        "mapping":  {1: 'a', 2: 'b', 3: 'c', 4: 'd'},
        "desc": "One-to-one correspondence: injective and surjective, so the inverse mapping f⁻¹ exists",
    },
    "General mapping": {
        "domain":   [1, 2, 3, 4],
        "codomain": ['a', 'b', 'c', 'd', 'e'],
        "mapping":  {1: 'a', 2: 'a', 3: 'b', 4: 'c'},
        "desc": "Many-to-one and not onto: images repeat, and some codomain elements have no preimage",
    },
    "Constant mapping": {
        "domain":   [1, 2, 3, 4],
        "codomain": ['a', 'b', 'c'],
        "mapping":  {1: 'b', 2: 'b', 3: 'b', 4: 'b'},
        "desc": "Many-to-one in the extreme: every element is sent to the same image",
    },
}

# --- Step 1: classify the mapping by the size of the preimages f⁻¹[{y}] ---
print_step(1, "Classify the mapping by the size of the preimages f⁻¹[{y}]")

def analyze_mapping(domain, codomain, mapping):
    """
    Characterize the mapping by the size of the preimages f⁻¹[{y}]:
      injective   ⟺  |f⁻¹[{y}]| ≤ 1 for all y ∈ Y
      surjective  ⟺  f⁻¹[{y}] ≠ ∅ for all y ∈ Y
      bijective   ⟺  |f⁻¹[{y}]| = 1 for all y ∈ Y
    """
    preimage = {y: [] for y in codomain}
    for x, y in mapping.items():
        preimage[y].append(x)

    sizes         = [len(preimage[y]) for y in codomain]
    is_injective  = all(s <= 1 for s in sizes)
    is_surjective = all(s >= 1 for s in sizes)

    return {
        "is_injective":  is_injective,
        "is_surjective": is_surjective,
        "is_bijective":  is_injective and is_surjective,
        "preimage":      preimage,
        "empty_preimage": [y for y in codomain if len(preimage[y]) == 0],
        "multi_preimage": [y for y in codomain if len(preimage[y]) > 1],
    }

for name, fdata in FUNCTION_TYPES.items():
    result = analyze_mapping(fdata["domain"], fdata["codomain"], fdata["mapping"])
    print(f"\n  {name}")
    print(f"    {fdata['desc']}")
    compare_print(
        "Mapping properties",
        f"injective={result['is_injective']}, surjective={result['is_surjective']}, bijective={result['is_bijective']}",
        "Determined by the size of the preimages (see property pro-preimage-characterization)"
    )
    if result["empty_preimage"]:
        print(f"    elements with no preimage (surjectivity fails): {result['empty_preimage']}")
    if result["multi_preimage"]:
        print(f"    elements hit more than once (injectivity fails): {result['multi_preimage']}")

# --- Step 2: build the interactive Plotly figure ---
print_step(2, "Build an interactive figure that switches between mapping types (Plotly)")

def _add_mapping_traces(fig, fdata, visible):
    """Add the domain, the codomain and the mapping arrows for one type of mapping."""
    domain_elems   = fdata["domain"]
    codomain_elems = fdata["codomain"]
    mapping        = fdata["mapping"]
    desc           = fdata["desc"]

    dy = np.linspace(1, len(domain_elems),   len(domain_elems))
    cy = np.linspace(1, len(codomain_elems), len(codomain_elems))

    # domain nodes (C_V2 deep blue)
    fig.add_trace(go.Scatter(
        x=[1] * len(domain_elems), y=dy,
        mode='markers+text',
        marker=dict(size=30, color=C_V2, line=dict(width=2, color=C_V1)),
        text=[str(e) for e in domain_elems],
        textposition="middle left",
        textfont=dict(size=16, color='white', family='Arial Black'),
        name='Domain X',
        hovertemplate="x = %{text}<br>" + desc + "<extra></extra>",
        visible=visible,
    ))

    # codomain nodes (C_WARN orange)
    fig.add_trace(go.Scatter(
        x=[5] * len(codomain_elems), y=cy,
        mode='markers+text',
        marker=dict(size=30, color=C_WARN, line=dict(width=2, color="#C0392B")),
        text=[str(e) for e in codomain_elems],
        textposition="middle right",
        textfont=dict(size=16, color='white', family='Arial Black'),
        name='Codomain Y',
        hovertemplate="y = %{text}<br>" + desc + "<extra></extra>",
        visible=visible,
    ))

    # mapping arrows (C_T1 teal)
    for x_elem, y_elem in mapping.items():
        xi = domain_elems.index(x_elem)
        yi = codomain_elems.index(y_elem)
        sx, sy = 1.25, dy[xi]
        ex, ey = 4.75, cy[yi]
        fig.add_trace(go.Scatter(
            x=[sx, ex], y=[sy, ey],
            mode='lines',
            line=dict(color=C_T1, width=3),
            hovertemplate=f"f({x_elem}) = {y_elem}<extra></extra>",
            showlegend=False, visible=visible,
        ))

def build_interactive_figure():
    fig = go.Figure()
    names        = list(FUNCTION_TYPES.keys())
    trace_counts = []

    for i, (name, fdata) in enumerate(FUNCTION_TYPES.items()):
        n_before = len(fig.data)
        _add_mapping_traces(fig, fdata, visible=(i == 0))
        trace_counts.append(len(fig.data) - n_before)

    # dropdown menu
    buttons = []
    for i, name in enumerate(names):
        vis   = [False] * len(fig.data)
        start = sum(trace_counts[:i])
        for j in range(trace_counts[i]):
            vis[start + j] = True
        buttons.append(dict(
            label=name,
            method="update",
            args=[{"visible": vis}, {"title": f"Type of mapping: {name}"}],
        ))

    # set boundaries (C_V2 domain, C_WARN codomain)
    for x0, x1, color in [(0.3, 1.7, C_V2), (4.3, 5.7, C_WARN)]:
        fig.add_shape(type="rect", x0=x0, y0=0.5, x1=x1, y1=5.5,
                      line=dict(color=color, width=3),
                      fillcolor=C_AREA)

    fig.add_annotation(x=1, y=6, text="Domain X", showarrow=False,
                       font=dict(size=18, color=C_V2, family="Arial Black"))
    fig.add_annotation(x=5, y=6, text="Codomain Y", showarrow=False,
                       font=dict(size=18, color=C_WARN, family="Arial Black"))

    fig.update_layout(
        title="Type of mapping: Injective",
        updatemenus=[dict(
            buttons=buttons, direction="down",
            showactive=True, x=0.02, xanchor="left", y=0.98, yanchor="top",
            bgcolor=C_AUX, bordercolor=C_V1, borderwidth=2,
        )],
        xaxis=dict(range=[0, 6], showgrid=False, showticklabels=False, zeroline=False),
        yaxis=dict(range=[0, 7], showgrid=False, showticklabels=False, zeroline=False),
        showlegend=False, width=800, height=600,
        plot_bgcolor=C_BG, paper_bgcolor=C_BG,
        margin=dict(t=100, b=50, l=50, r=50),
    )
    return fig

# --- Step 3: show the interactive figure ---
print_step(3, "Show the interactive figure (use the dropdown at the top left to switch types)")
fig = build_interactive_figure()
fig.show()

print("\n✓ Done. The dropdown switches between: Injective, Surjective, Bijective, General mapping, Constant mapping.")

§1.2 Summary

This section answered a question that runs through the whole book: how should the “correspondence” between two sets be defined precisely, and what structurally different types does such a correspondence come in?

The core constraint on a mapping—each element of the domain has one and only one image—looks like a technical detail, but it rules out the ambiguous situation of “one input with several outputs,” and so makes “computing” a well-defined operation. The associativity of composition $g \circ f$ is the set-theoretic root of the associativity of matrix multiplication: in §3, composition of linear mappings corresponds exactly to multiplication of matrices. The importance of the preimage $f^{-1}[B]$ lies in its being meaningful for every mapping, with no requirement that $f$ be invertible—which lets us describe the solution structure of linear systems uniformly in §6 by saying “the solution set is a certain preimage,” and lets us define eigenspaces as particular preimages in §8.

The threefold classification of mappings—injective, surjective, bijective—receives a unified characterization through the size of preimage sets (at most one, nonempty, exactly one), revealing the essential difference between a mapping that “compresses information,” one that “fails to cover the whole codomain,” and one that “establishes a one-to-one correspondence.” These three notions reappear in algebraic guise in §4: injectivity corresponds to a kernel containing only the zero vector, surjectivity to an image equal to the codomain, and bijectivity to invertibility of the linear mapping—and there the language of sets and the language of algebra converge into one.

1.3 Chapter Summary¶

Review of the Theoretical Thread¶

This chapter set out from a historical turning point: the nineteenth-century crisis in mathematics forced mathematicians to give up their reliance on geometric intuition and to seek a language capable of describing “an entire class of objects” precisely. Weierstrass’s pathological function and Dedekind’s cuts pointed jointly to the same answer—set theory.

§1.1 established the vocabulary of that language. The three properties of a set (definiteness, distinctness, unorderedness) are not fussy stipulations but the minimum required for “a class of objects” to be referred to unambiguously. The subset relation introduces the logic of whole and part; the power set gathers “all possible substructures” into a mathematical object in its own right. The Cartesian product $A \times B$ is the most crucial construction of all: it makes the pairing relation between two sets concrete as a set of ordered pairs, laying the structural groundwork for describing “correspondence” in the next step. Union, intersection, complement, and set difference constitute the algebra of sets, allowing us to manipulate and combine these objects—and it is exactly this capacity for manipulation that makes every later notion of “space” amenable to rigorous treatment.

§1.2 introduced mappings on top of the language of sets, answering the question of what structural connections can be established between two sets. Distinguishing the domain, codomain, image, and range of a mapping removes the confusion between “which values a function is allowed to take” and “which values it actually takes”; the associativity of composition then reveals the algebraic structure of the operation of composing mappings. The introduction of the preimage is especially profound: $f^{-1}[B]$ is defined without requiring $f$ to be invertible, so that the question “given an output, what were the inputs?” can be posed in complete generality. Finally, taking the size of preimage sets as a unifying viewpoint, the three classes of mappings—injective ( $|f^{-1}[\{y\}]| \leq 1$ ), surjective ( $f^{-1}[\{y\}] \neq \emptyset$ ), and bijective ( $|f^{-1}[\{y\}]| = 1$ )—acquire an internally consistent characterization rather than three unrelated definitions.

Connections to Other Chapters¶

This is the first chapter of the book, and it supplies the common linguistic foundation for everything that follows. The most direct bridges appear in §2 on vectors and §3 on linear transformations: a vector space is first of all a set, equipped with two operations satisfying particular axioms; a linear transformation is first of all a mapping between sets, together with the requirement that it preserve linear structure. Without the precise definition of “set” given in §1.1, the sentence “a vector space is a set” would be a metaphor rather than a mathematical statement.

The classification of mappings from §1.2 reappears in algebraic guise in §4: a linear mapping is injective exactly when its kernel contains only the zero vector, surjective exactly when its image equals the codomain, and bijective exactly when it is invertible—and the essence of the rank-nullity theorem is precisely an algebraic characterization of these three classes of mappings in finite-dimensional spaces. The notion of a preimage then takes bodily form in §6 as the structure of the solutions of a linear system: the solution set of the equation $\mathbf{A}\mathbf{x} = \mathbf{b}$ is exactly the preimage of $\{\mathbf{b}\}$ under the mapping $\mathbf{x} \mapsto \mathbf{A}\mathbf{x}$ . In §8, the definition of an eigenspace—the set of all vectors satisfying $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$ —is likewise a special case of a preimage. The influence of the language of sets runs through the entire book.

The Role of This Chapter in the Book¶

The problem this chapter solves is that of supplying the whole book with an unambiguous way of speaking. It introduces no content belonging to “linear algebra” as such, and yet it is what makes every later statement of linear algebra possible. “A vector space is a set equipped with two operations satisfying eight axioms”—once every word of that sentence has a precise meaning, the theorems proved from it apply simultaneously to $\mathbb{R}^n$ , to polynomial spaces, to function spaces, and to matrix spaces, with no need to redo the derivation for each kind of object. This kind of once-and-for-all general argument is exactly where “discussing an entire class of objects” outstrips “computing individual examples.”

This chapter also opens a deeper question that runs through the whole book. At the level of sets, injectivity, surjectivity, and bijectivity characterize the preservation and the loss of information; at the level of linear algebra, the same question will be made concrete through algebraic quantities such as rank, kernel, and invertibility. A reader who carries a set-theoretic eye into the following chapters will recognize familiar structures inside every new definition: a subspace is a subset of a vector space, linear dependence is a constraint on linear-combination relations among sets, and an eigenspace is an algebraic instance of a preimage. Formal language is not an ornament on mathematics; it is the infrastructure that allows abstract reasoning to be transmitted precisely.