\[\newcommand{\FGrp}{F_{\mathbf{Grp}}} \newcommand{\Sg}{\mathsf{Sg}} \newcommand{\Hom}{\mathsf{Hom}} \newcommand{\hom}{\mathsf{Hom}} \newcommand{\epi}{\mathsf{Epi}} \newcommand{\aut}{\mathsf{Aut}} \newcommand{\mono}{\mathsf{Mono}} \newcommand{\Af}{\langle A, f \rangle} \newcommand{\dom}{\mathsf{dom}}\newcommand{\cod}{\mathsf{cod}} \newcommand{\ran}{\mathsf{ran}} \newcommand{\id}{\mathsf{id}} \newcommand{\Id}{\mathsf{id}} \newcommand{\im}{\mathrm{im}} \newcommand{\Proj}{\mathsf{pr}} \newcommand{\Con}{\mathsf{Con}} \newcommand{\Clo}{\mathsf{Clo}}\newcommand{\Pol}{\mathsf{Pol}} \newcommand{\Op}{\mathsf{Op}} \newcommand{\Th}{\mathsf{Th}} \newcommand{\Mod}{\mathsf{Mod}} \newcommand{\src}{\mathsf{src}} \newcommand{\tar}{\mathsf{tar}} \newcommand{\eval}{\mathsf{eval}} \newcommand{\fork}{\mathsf{fork}}\newcommand{\Type}{\mathsf{Type}} \newcommand{\comp}{\circ} \newcommand{\tick}{\mathsf{tick}} \newcommand{\Time}{\mathsf{Time}}\newcommand{\Tree}{\mathsf{Tree}}\newcommand{\Term}{\mathsf{Term}} \newcommand{\Mod}{\mathsf{Mod}}\newcommand{\Th}{\mathsf{Th}} \newcommand{\inv}{\ ^{-1}}\]

definitions

abelian group

A group is called abelian just in case its binary operation is commutative; in that case we usually let \(0\) (instead of \(e\)) denote the additive identity, we let \(-\) (instead of \(^{-1}\)) denote the additive inverse, and we let \(+\) (instead of \(⋅\)) denote binary addition. Thus, an abelian group is a group \(⟨A, 0, -, +⟩\) such that \(a+b = b+a\) for all \(a, b ∈ A\).

absolutely continuous measure

Let \(μ\) be a positive measure on a σ-algebra \(𝔐\), and let \(λ\) be an arbitrary complex measure on \(𝔐\). 1

If \(∀ E ∈ 𝔐\), \(μ E = 0 \; ⟹ \; λ E = 0\), then we call \(λ\) absolutely continuous with respect to \(μ\), and we write \(λ ≪ μ\).

absolutely continuous function

A real- or complex-valued function \(F\) on \(ℝ\) is called absolutely continuous on the interval \([a,b] ⊆ ℝ\), denoted \(F ∈ AC[a,b]\), if for every \(ε > 0\) there exists \(δ > 0\) such that for each finite set \(\{(a_1, b_1), \dots, (a_N, b_N)\}\) of disjoint intervals in \([a,b]\), we have

\[∑_{i=1}^N (b_i-a_i) < δ \quad ⟹ \quad ∑_{i=1}^N |F(b_i)-F(a_i)| < ε.\]

abstract category

An abstract category is one whose objects are not sets or whose morphisms are not functions defined on sets. Our next example is somewhere in between. The objects are sets, but the morphisms are not necessarily total functions; that is, they may be defined on only a part of the source object.

algebraic lattice

a lattice generated by its compact elements.

accumulation point

See limit point.

additive

Let \(𝔐 = \{M_λ: λ∈ Λ\}\) be a collection of sets and let \(R\) be a ring. An \(R\)-valued function \(s: 𝔐 → R\) defined on the collection \(𝔐\) is called additive if for every subset \(Γ ⊆ Λ\) such that \(\{M_γ : γ ∈ Γ\}\) is a subcollection of pairwise disjoint subsets in \(𝔐\), we have

\[s \bigl( ⋃_{γ∈Γ} M_γ \bigr) = ∑_{γ∈ Γ} s (M_γ).\]

adjoint

Suppose that \(X\) and \(Y\) are normed linear spaces and \(T ∈ 𝔅(X, Y)\) (a bounded linear transformation). The adjoint (or transpose) of \(T\) is denoted by \(T^†: Y^∗ → X^∗\) and defined for each \(f∈ Y^∗\) by \(T^† f = f T\).

It is not hard to show that \(T^† ∈ 𝔅(Y^∗, X^∗)\) and \(\|T^†\| = \|T\|\).

algebra

See algebraic structure.

algebra of functions

Let \(F\) be a field and let \(F^X\) denote the collection of all functions from \(X\) to \(F\). A subset \(𝔄 ⊆ F^X\) of \(F\)-valued functions on \(X\) is called an algebra if it is closed under point-wise product. That is, for all \(f, g ∈ 𝔄\), the function \(h = f ⋅ g\) defined by \(h: x ↦ f(x) ⋅ g(x)\) also belongs to \(𝔄\).

algebra of sets

Let \(X\) be a nonempty set. An algebra of sets on \(X\) is a nonempty collection \(𝔄\) of subsets of \(X\) that is closed under finite unions and complements. (Some authors call this a “field of sets.”)

algebraic structure

An algebraic structure in the signature \(σ = (F, ρ)\) (or, \(σ\)-algebra) is denoted by \(𝔸 = ⟨A, F^𝔸⟩\) and consists of

1. \(A\) := a set, called the carrier (or universe) of the algebra,

2. \(F^𝔸 = \{ f^𝔸 ∣ f ∈ F, \ f^𝔸: (ρ f → A) → A \}\) := a set of operations on \(A\), and

3. a collection of identities satisfied by elements of \(A\) and operations in \(F^𝔸\).

antichain

A subset \(A\) of the preordered set \(X\) is called an antichain if for all \(x, y ∈ A\) we have \(x ≤ y\) implies \(y ≤ x\).

antisymmetric

A binary relation \(R\) on a set \(X\) is called antisymmetric provided \(∀ x, y ∈ X \ (x \mathrel{R} y ∧ y\mathrel{R} x \ → \ x=y)\).

arity

Given a signature \(σ = (F, ρ)\), each operation symbol \(f ∈ F\) is assigned a value \(ρ f\), called the arity of \(f\). (Intuitively, the arity can be thought of as the “number of arguments” that \(f\) takes as “input”.)

associative algebra

If \(𝔸\) is a bilinear algebra with an associative product—\((a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)\) for all \(a, b, c ∈ A\)—then \(𝔸\) is called an associative algebra.

Thus an associative algebra over a field has both a vector space reduct and a ring reduct.

An example of an associative algebra is the space of linear transformations (endomorphisms) of a vector space into itself.

Baire category theorem

No nonempty complete metric space is of the first category.

Banach space

A Banach space is a normed linear space \((X, \|\,⋅\,\|)\) such that \(X\) is complete in the metric defined by its norm. (That is, each Cauchy sequence in \((X, \|\,⋅\,\|)\) converges to a point in \(X\).)

base

Let \((X, τ)\) be a topological space and let \(x ∈ X\). A collection \(ℬ_x\) of neighborhoods of \(x\) is called a base for \(τ\) at \(x\) provided for every neighborhood \(V\) of \(x\), there exists \(B ∈ ℬ_x\) such that \(B ⊆ V\). A collection \(ℬ\) of open sets is called a base for \(τ\) provided it contains a base for \(τ\) at every point of \(X\).

bilinear algebra

Let \(𝔽= ⟨ F, 0, 1, -\, , +, ⋅⟩\) be a field. An algebra \(𝔸 = ⟨ A, 0, -\, , +, ⋅, f_r⟩_{r∈ F}\) is a bilinear algebra over \(𝔽\) provided \(⟨A, 0, -, +, ⋅, f_r⟩_{r ∈ F}\) is a vector space over \(𝔽\) and for all \(a, b, c ∈ A\) and all \(r ∈ F\), we have

\[\begin{split}(a + b) ⋅ c &= (a ⋅ c) + (b ⋅ c)\\ c ⋅ (a + b) &= (c⋅ a) + (c⋅ b)\\ a⋅ f_r(b) &= f_r(a⋅ b) = f_r(a)⋅ b.\end{split}\]

If, in addition, \((a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)\) for all \(a, b, c ∈ A\), then \(𝔸\) is called an associative algebra over \(𝔽\). Thus an associative algebra over a field has both a vector space reduct and a ring reduct. An example of an associative algebra is the space of linear transformations (endomorphisms) of any vector space into itself.

binary operation

An operation \(f\) on a set \(A\) is called binary if the arity of \(f\) is 2. That is, \(f: A × A → A\) (or, in curried form, \(f: A → A → A\)).

Borel function

See Borel measurable function.

Borel measurable function

If \(ℬ(X)\) and \(ℬ(Y)\) are Borel σ-algebras of \(X\) and \(Y\), respectively, then a \((ℬ(X), ℬ(Y))\)-measurable function is called a Borel measurable function (or just Borel function). Equivalently, \(f\) is a Borel function iff \(f^{-1}(B) ∈ ℬ(X)\) for every \(B∈ ℬ(Y)\).

Boolean algebra homomorphism

a lattice homomorphism that also preserves complementation (but every lattice homomorphism between Boolean lattices automatically preserves complementation, so we may characterize the morphisms of this category more simply as the lattice homomorphisms).

We call a function \(φ: ℝ^n → ℝ\) Borel measurable (or a Borel function or just Borel) if it is \((ℬ(ℝ) ⊗ \cdots ⊗ ℬ(ℝ))\)-measurable, where the \(⊗\)-product has \(n\) factors.

Borel measure

A Borel measure is a measure whose domain is a Borel σ-algebra.

Borel set

The members of a Borel σ-algebra are called Borel sets; included among them are the open sets, closed sets, countable intersections of open sets, countable unions of closed sets, and so forth.

Borel σ-algebra

If \(X\) is a metric or topological space, then the σ-algebra generated by the family of open sets in \(X\) is called the Borel σ-algebra on \(X\), which we denote by \(ℬ(X)\).

bounded linear functional

Let \(X\) be a normed linear space over the field \(F\). A bounded linear functional on \(X\) is a bounded linear transformation with codomain \(F\).

We denote by \(𝔅(X,F)\) the collection of all bounded linear functionals on \(X\).

bounded linear transformation

Let \(X\) and \(Y\) be two normed linear spaces. A linear transformation \(T: X → Y\) is called bounded if there exists \(C > 0\) such that

\[\|Tx\| ≤ C \|x\| \; \text{ for all } x ∈ X.\]

We denote the space of all bounded linear transformations from \(X\) to \(Y\) by \(𝔅(X,Y)\).

bounded set

A set \(E\) in a metric space is called bounded if it has finite diameter, \(\mathrm{diam} E < ∞\).

bounded variation

For \(f: [a, b] → ℝ\) define

\[F(x) = \sup ∑_{i=1}^N |f(t_i)- f(t_{i-1})| \quad (a ≤ x ≤ b),\]

where the supremum is taken over all \(N\) and over all choices of \(\{t_i\}\) such that \(a = t_0 < t_1 < \cdots < t_N = x\). If \(F(b)< ∞\), then we say \(f\) is of bounded variation on \([a,b]\) and we write \(f∈ BV[a,b]\).

If in addition \(f\) is absolutely continuous on \([a,b]\), then the functions \(F\), \(F+ f\), and \(F - f\) are nondecreasing and absolutely continuous on \([a,b]\). (See [Rud87] 7.19.)

Cartesian product

See product.

Cauchy sequence

A sequence \(\{x_n\}\) in a metric space \((X, d)\) is called a Cauchy sequence if for all \(\epsilon >0\) there exists \(N>0\) such that \(d(x_m, x_n) < \epsilon\) for all \(n, m \geq N\).

canonical normal form

See the ncatlab page on normal forms.

category of categories

has categories as objects and functors as morphisms.

Choice

is short for the Axiom of Choice.

characteristic function

The characteristic function \(χ_A\) of a subset \(A ⊆ X\) is the function \(χ_A: X → \{0,1\}\) that is 1 if and only if \(x ∈ A\); that is, \(χ_A(x) = 0\) if \(x ∉ A\) and \(χ_A(x) = 1\) if \(x ∈ A\).

chain

Let \(⟨ X, ≤ ⟩\) be a preordered set and \(C ⊆ X\). We call \(C\) a chain of \(⟨ X, ≤ ⟩\) if for all \(x, y ∈ C\) either \(x ≤ y\) or \(y ≤ x\) holds.

clone

An operational clone (or just clone) on a nonempty set \(A\) is a set of operations on \(A\) that contains all projection operations and is closed under general composition.

closed

If \(𝖢\) is a closure operator on \(X\), then a subset \(A ⊆ X\) is called closed with respect to \(𝖢\) (or \(𝖢\)-closed) provided \(𝖢(A) ⊆ A\) (equivalently, \(𝖢(A) = A\)).

Here’s an important example. Let \(σ = (F, ρ)\) be a signature and \(X\) a set. Define for each \(A ⊆ X\) the set \(𝖢(A) = \{f\, b ∣ f ∈ F, \, b: ρ f → A\}\). Then \(𝖢\) is a closure operator on \(X\) and a subset \(A ⊆ X\) is said to be “closed under the operations in \(F\)” provided \(A\) is \(𝖢\)-closed.

closed ball

Let \((X, d)\) be a metric space. If \(x ∈ X\) and \(r > 0\) are fixed, then the set denoted and defined by \(B̄ (x; r) = \{y ∈ X ∣ d(x,y) ≤ r\}\) is called the closed ball with center \(x\) and radius \(r\).

closed set

A subset of a metric or topological space is closed if its complement is open. (Hence the empty set and the whole universe are closed, finite unions of closed sets are closed, and arbitrary intersections of closed sets are closed.)

closure

If \(X\) is a metric or topological space then the closure of a subset \(E ⊆ X\) is denoted by \(Ē\) and defined to be the smallest \(closed\) subset of \(X\) containing \(E\).

The closure \(Ē\) exists since the collection \(Ω\) of all closed subsets of \(X\) which contain \(E\) is not empty (since \(X ∈ Ω\)), so define \(Ē\) to be the intersection of all members of \(Ω\).

Here is an alternative, equivalent definition. The closure of \(E\) is the intersection of all closed sets containing \(E\).

closure operator

Let \(X\) be a set and let \(𝒫(X)\) denote the collection of all subsets of \(X\). A closure operator on \(X\) is a set function \(𝖢: 𝒫 (X) → 𝒫 (X)\) satisfying the following conditions, for all \(A, B ∈ 𝒫 (X)\),

1. \(A ⊆ 𝖢(A)\),

2. \(𝖢 ∘ 𝖢 = 𝖢\),

3. \(A ⊆ B ⟹ 𝖢(A) ⊆ 𝖢(B)\).

cocomplete

See cocomplete poset.

cocomplete poset

A poset in which all joins exist is called cocomplete.

codomain

If \(f : A → B\) is a function or relation from \(A\) to \(B\), then \(B\) is called the codomain of \(f\), denoted by \(\cod f\).

cofinite topology

If \(X\) is an infinite set, then \(\{V ∈ X ∣ V = ∅ \text{ or } V^c \text{ is finite}\}\) is a topology on \(X\), called the cofinite topology.

commutative diagram

A commutative diagram is a diagram with the following property: for all objects \(C\) and \(D\), all paths from \(C\) to \(D\) yield the same morphism.

commutative group

See abelian group.

compact element

an element \(x\) of a lattice \(L\) is called compact provided for all \(Y ⊆ L\), if \(x ≤ ⋁ Y\), then there exists a finite subset \(F ⊆ Y\) such that \(x ≤ ⋁ F\).

compact set

If \((X,d)\) is a metric space, then a subset \(E ⊆ X\) that satisfies any one (hence all) of the conditions in the Compactness theorem is called compact.

Probably the condition that is most commonly used to define a compact subset is the Heine-Borel property, which is stated simply as follows: a set is compact iff every open covering reduces to a finite subcover.

If \((X,τ)\) is a topological space then a set \(A ⊆ X\) is called compact if every open covering \(\{V_i ∣ i ∈ I\} ⊆ τ\) of \(A\) has a finite subcover. That is,

\[A ⊆ ⋃_{i∈ I} V_i \quad \text{ implies } \quad A ⊆ ⋃_{j=1}^n V_{i_j}\]

for some finite subcollection \(\{V_{i_j} ∣ j = 1, \dots, n\} ⊆ \{V_i ∣ i∈ I\}\).

complete

A poset in which all meets exist is called complete.

complete lattice

a poset whose universe is closed under arbitrary meets and joins.

complete lattice homomorphism

A complete lattice homomorphism is a function \(f: X → Y\) that preserves complete meets and joins.

complete measure

A measure \(μ\) on a measurable space \((X, 𝔐)\) is called complete if all subsets of sets of measure 0 are measurable (and have measure 0). 2

complete measure space

If \(μ\) is a complete measure on the measurable space \((X, 𝔐)\), then \((X, 𝔐, μ)\) is called a complete measure space.

complete metric space

A metric space \((X, d)\) is called complete if \(X\) is complete; that is, each Cauchy sequence in \(X\) converges to a point of \(X\).

complete poset

A poset in which all meets exist is called complete.

complete set

A subset \(C\) of a (metric or topological) space \(X\) is called complete if every Cauchy sequence in \(C\) converges to a point in \(C\).

complex measure

A complex measure on a measurable space \((X, 𝔐)\) is a map \(ν: 𝔐 → ℂ\) such that \(ν ∅ = 0\), and \(ν\) is countably additive over \(𝔐\), which means that

(59)\[ν(⋃_j A_j) = ∑_j ν(A_j)\]

whenever \(\{A_j\}\) is a collection of disjoint sets in \(𝔐\).

Moreover, the sum on the right-hand side of (59) converges absolutely.

Notice, we do not allow a complex measure to take on infinite values. Thus, a positive measure is a complex measure only if it is finite.

component

If \(α : F ⇒ G\) is a natural transformation, then the component of α at \(A\) is the morphism \(α_A : FA → GA\).

composition of operations

If \(f: (n → A) → A\) is an \(n\)-ary operation on the set \(A\), and if \(g: ∏_{(i:n)} ((k_i → A) → A)\) is an \(n\)-tuple of operations, then we define the composition of \(f\) with \(g\), using the eval and fork operations, as follows:

\[f [g] := f\, (\mathbf{eval} \, \mathbf{fork}\, g): ∏_{(i:n)}(k_i → A) → A.\]

Indeed,

\[\mathbf{eval} \, \mathbf{fork} \, g: ∏_{(i:n)}(k_i → A) → (n → A)\]

is the function that maps each \(a: ∏_{(i:n)}(k_i → A)\) to \(∏_{(i:n)}\mathbf{eval} \,(g \, i, a\, i) = g ∘ a\), where for each \((i:n)\) \((g ∘ a)(i) = (g i)(a i): A\).

Thus, if \(a: ∏_{(i:n)}(k_i → A)\), then \((\mathbf{eval} \, \mathbf{fork} \, g) (a)\) has type \(n → A\), which is the domain type of \(f\). Therefore, \(f \, (\mathbf{eval} \, \mathbf{fork}\, g)\, (a)\) has type \(A\).

concentrated

If there is a set \(A ∈ 𝔐\) such that for all \(E ∈ 𝔐\) we have \(λ E = λ (A ∩ E)\), then we say that \(λ\) is concentrated on \(A\).

concrete category

A concrete category is one whose objects are sets and whose morphisms are functions defined on these sets (possibly satisfying some other special properties).

conjugate exponents

If \(p\) and \(q\) are positive real numbers such that \(p+q = pq\) (equivalently, \((1/p) + (1/q) = 1\)), then we call \(p\) and \(q\) a pair of conjugate exponents.

It’s clear that conjugate exponents satisfy \(1 < p, q < ∞\) and that as \(p → 1\), \(q → ∞\) and vice-versa. Thus, \((1, ∞)\) is also regarded as a pair of conjugate exponents.

consecutive functions

If \(f : A → B\) and \(g : B → C\), then \(\cod f = \dom g\) and we say that \(f\) and \(g\) are consecutive functions.

continuous function

Let \((X, τ_1)\) and \((Y, τ_2)\) be topological spaces. A function \(f: X → Y\) is called continuous if \(f^{-1}(S) ∈ τ_1\) for every \(S ∈ τ_2\).

Let \((X, |\;\;|_1)\) and \((Y, |\;\;|_2)\) be metric spaces. A function \(f : X \to Y\) is called continuous at the point \(x_0 ∈ X\) if for all \(ε >0\) there exists \(δ > 0\) such that

\[|x - x_0|_1 < δ \, ⟹ \, |f(x) -f(x_0)|_2 < ε.\]

A function \(f : X → Y\) is called continuous in \(E ⊆ X\) if it is continuous at every point of \(E\).

contravariant powerset functor

The contravariant powerset functor is a functor \(P^{\mathrm{op}}: \mathbf{Set} → \mathbf{Set}\) such that for each morphism \(g: B → A\) the morphism \(P^{\mathrm{op}}g: 𝒫(A) → 𝒫(B)\) is given by \(P^{\mathrm{op}} g (S) = \{b ∈ B : g(b) ∈ S\}\) for each \(S ⊆ A\).

coproduct

Given two objects \(A\) and \(B\) a coproduct (or sum) of \(A\) and \(B\) is denoted by \(A+B\) and defined to be an object with morphisms \(ι_1 : A → A + B\) and \(ι_2 : B → A + B\) such that for every object \(X\) and all morphisms \(u : A → Y\) and \(v : B → Y\) there exists a unique morphism \([u,v] : A+B → Y\) such that \([u,v] ∘ ι_1 = u\) and \([u,v] ∘ ι_2 = v\).

countably additive

Let \(𝒮 = \{S_λ: λ∈ Λ\}\) be a collection of sets and let \(R\) be a ring. A function \(s: 𝒮 → R\) is called countably additive if for every countable subset \(Γ ⊆ Λ\) such that \(\{S_γ : γ ∈ Γ\}\) is a collection of pairwise disjoint subsets in \(𝒮\), we have

. math:: s bigl( ⋃_{γ∈Γ} A_γ bigr) = ∑_{γ∈ Γ} s (A_γ).

countably subadditive

Let \(𝒮 = \{S_λ: λ∈ Λ\}\) be a collection of sets and let \(R\) be a ring. A function \(s: 𝒮 → R\) is called countably subadditive if for every countable subset \(Γ ⊆ Λ\) such that \(\{S_γ : γ ∈ Γ\}\) is a collection of subsets in \(𝒮\), we have

covariant powerset functor

The (covariant) powerset functor is a functor \(P : \mathbf{Set} → \mathbf{Set}\) such that for each \(f : A → B\) the morphism \(Pf : PA → PB\) is given by \(Pf(S) = \{f(x) : x ∈ S\}\) for each \(S \subseteq A\).

cover

See covering.

covering

In a metric or topological space \(X\), a covering of a subset \(E ⊆ X\) is a collection of subsets \(\{V_α\}\) of \(X\) such that \(E ⊆ ⋃_α V_α\). If, in addition, each \(V_α\) is an open subset of \(X\), then we call \(\{V_α\}\) an open covering of \(E\).

Curry-Howard correspondence

the correspondence between propositions and types, and proofs and programs; a proposition is identified with the type of its proofs, and a proof is a program of that type.

(See also https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence.)

dense set

A set \(G\) is dense in \(X\) if each \(x ∈ X\) is a limit point of \(G\). Equivalently, the closure of \(G\) contains \(X\) (in symbols, \(X ⊆ Ḡ\).)

discrete topology

If \(X\) is a nonempty set, the powerset \(𝒫(X)\) is a topology on \(X\) and is called the discrete topology.

diameter

The diameter of a set \(E\) in a metric space \((X, d)\) is denoted and defined by \(\mathrm{diam} E = \sup \{d(x, y) : x, y \in E\}\).

directed set

A subset \(D\) of a preorder is called directed if every finite subset of \(D\) has an upper bound in \(D\). That is, if \(F ⊆ D\) and \(F\) is finite, then there exists \(d ∈ D\) such that \(f ≤ d\) for all \(f ∈ F\).

directed-cocomplete preorder

a preorder for which the joins of all directed subsets exist.

directed-cocomplete poset

an antisymmetric directed-cocomplete preorder.

directed graph

A directed graph is a relational structure consisting of a vertex set \(V\) (whose elements are called vertices) and an edge set \(E ⊆ V^2\) (whose elements are called edges).

division ring

A ring in which every non-zero element is a unit is called a division ring.

domain

If \(f : A → B\) is a function or relation from \(A\) to \(B\), then \(A\) is called the domain of \(f\), denoted by \(\dom f\).

dual

If \(X\) is a normed linear space over the field \(F\), then the collection \(𝔅(X,F)\) of bounded linear functionals is called the dual space (or dual) of \(X\).

If \(F\) is complete, then \(𝔅(X,F)\) is complete, hence a Banach space.

endofunctor

A functor that maps a category to itself is called an endofunctor.

endomorphism

A morphism \(f: 𝔸 → 𝔸\) (i.e., \(\src f = \tar f\)) is called an endomorphism.

epimorphism

A morphism \(f: X → Y\) is called an epimorphism if for every object \(Z\) and pair \(g_1, g_2: Y → Z\) of morphisms we have \(g_1 ∘ f = g_2 ∘ f\) implies \(g_1 = g_2\). When \(f: X → Y\) is an epimorphism we often say “\(f\) is epi” and write \(f: X ↠ Y\).

equivalence class

If \(R\) is an equivalence relation on \(A\), then for each \(a ∈ A\), there is an equivalence class containing \(a\), which is denoted and defined by \(a/R = \{b ∈ A ∣ a \mathrel R b\}\).

equivalence relation

An equivalence relation is a symmetric preorder. The collection of all equivalence relations on \(X\) is denoted by \(\mathrm{Eq}(X)\).

equivalent categories

Two categories \(\mathcal C\) and \(\mathcal D\) are called equivalent categories if there are functors \(F : \mathcal C → \mathcal D\) and \(G : \mathcal D → \mathcal C\) together with natural isomorphisms \(ε : FG ≅ \mathrm{id}_{\mathcal D}\), and \(η : \mathrm{id}_{\mathcal C} ≅ GF\). We say that \(F\) is an equivalence with an inverse equivalence \(G\) and denote the equivalence by \(F : \mathcal C ≃ \mathcal D : G\).

essentially surjective on objects

A functor \(F : C → D\) is called essentially surjective on objects if for every object \(D ∈ \mathcal D\), there is some \(A ∈ \mathcal C\) such that \(F A\) is isomorphic to \(D\).

Euclidean norm

For \(𝐱 = (x_1,\dots, x_n) ∈ ℝ^n\) the Euclidean norm of \(𝐱\) is denoted and defined by \(\|𝐱\|_2 = \left(∑_{i=1}^n x_i^2\right)^{1/2}\).

Euclidean space

For \(n∈ ℕ\) the normed linear space \((ℝ^n, \|\,⋅\,\|_2)\), where \(\|\,⋅\,\|_2\) is the Euclidean norm, is called \(n\)-dimensional Euclidean space.

existential image functor

the functor \(∃ f : P(A) → P(B)\) defined by \(∃ f(X) = \{f(x) : x ∈ X\},\) for \(X ∈ P(A)\).

eval

If \(A\) and \(B\) are types, then the eval (or function application) function on \(A\) and \(B\) is denoted by \(\mathbf{eval}: ((A → B) × A) → B\) and defined by \(\mathbf{eval} (f, a) = f\, a\), for all \(f: A → B\) and \(a: A\).

evaluation functor

The evaluation functor is the functor \(Ev : \mathcal C × \mathbf{Set}^{\mathcal C} → \mathbf{Set}\), which takes each pair \((A, F) ∈ \mathcal C_{\mathrm{obj}} × \mathbf{Set}^{{\mathcal C}_{\mathrm{obj}}}\) of objects to the set \(Ev(A, F) = FA\), and takes each pair \((g, μ) ∈ \mathcal C_{\mathrm{obj}} × \mathbf{Set}^{\mathcal C_{\mathrm{mor}}}\) of morphisms to a function on sets, namely, \(Ev(g, μ) = μ_{A'} ∘ F g = F' g ∘ μ_A\), where \(g ∈ \mathcal C(A, A')\) and \(μ : F ⇒ F'\).

evaluation natural transformation

The evaluation natural transformation is denoted by \(eval^A : F_A → \mathrm{id}_{\mathbf{Set}}\) and defined by… (Todo complete definition)

extensional

An extensional definition of a term lists everything that qualifies as something to which that term refers.

(See also function extensionality.)

faithful functor

A functor \(F : \mathcal C → \mathcal D\) is called faithful if for all objects \(A\), \(B\) in \(\mathcal C_{\mathrm{obj}}\), the map \(\mathcal C(A, B) → \mathcal D(F A, F B)\) is injective.

(Note: A faithful functor need not be injective on morphisms.)

field

A field is a commutative division ring.

finite measure

If \((X, 𝔐, μ)\) is a measure space, then \(μ\) is called a finite measure provided \(μ X < ∞\).

finite ordinals

The category \(\mathrm{Ord}_{\mathrm{fin}}\) of finite ordinals (also called the simplex category \(\Delta\)) has \(\underline n = \{0, 1, \dots, n-1\}\) for objects (for each \(n ∈ ℕ\)) and \(f : \underline n → \underline m\) monotone functions for morphisms.

finite set

A set is called finite if it contains only a finite number of elements.

first category

A set \(G\) is of the first category if it is a countable union of nowhere dense sets.

fork

Let \(A\) and \(D\) be types and for each \(a: A\), let \(C_a\) be a type. Then the (dependent) fork function, denoted

\[\mathbf{fork}: ∏_{a:A}(C_a → D) → ∏_{a:A} C_a → ∏_{a:A} (C_a → D) × C_a,\]

is defined as follows: for all \(h: ∏_{a:A}(C_a → D)\) and \(k: ∏_{a:A} C_a\),

\[\mathbf{fork}\, (h)(k): ∏_{a:A}((C_a → D) × C_a),\]

and for each \(a:A\),

\[\mathbf{fork}\, (h)(k)(a) = (h\,a, k\,a): (C_a → D) × C_a.\]

Thus, \(\mathbf{eval} \, \mathbf{fork}\, (h)(k)(a) = (h\, a)(k\, a)\) is of type \(D\).

free algebra

The free algebra in a variety is the initial object in a category whose objects are algebraic structures.

Precisely, if \(𝒱\) is a variety of algebras and if \(X\) is a set, then the free algebra generated by \(X\) is denoted by \(𝔽(X)\) and defined as follows: for every algebra \(𝔸 ∈ 𝒱\) and every function \(f: X → A\), there exists a unique homomorphism \(h: 𝔽(X) → 𝔸\) such that \(∀ x ∈ X, h(x) = f(x)\). We say that \(𝔽(X)\) is “universal”, or “has the universal mapping property”, for \(𝒱\)

free object

See initial object.

free monoid

The free monoid is the initial object in a category of monoids.

function extensionality

the principle that takes two functions \(f : X → Y\) and \(g : X → Y\) to be equal just in case \(f(x) = g(x)\) holds for all \(x : X\); such functions are sometimes called “Leibniz equal.”

functor

A functor \(F : \mathcal C → \mathcal D\) consists of a function \(F_0\) that maps objects of \(\mathcal C\) to objects of \(\mathcal D\) and a function \(F_1\) that maps morphisms of \(\mathcal C\) to morphisms of \(\mathcal D\) such that \(F\) preserves (co)domains of morphisms, identities, and compositions.

functor category

The functor category from \(\mathcal C\) to \(\mathcal D\) has functors \(F : \mathcal C → \mathcal D\) as objects and natural transformations \(α : F ⇒ G\) as morphisms.

Galois connection

See https://en.wikipedia.org/wiki/Galois_connection.

Galois pair

See https://en.wikipedia.org/wiki/Galois_connection.

generalized element

A morphism \(h: X → A\) is sometimes called a generalized element of \(A\). A morphism \(f\) is mono when it is injective on the generalized elements of its domain.

general composition

See composition of operations.

global element

See point.

graph morphism

Let \(𝐆_1 =(V_1, E_1)\) and \(𝐆_2 = (V_2, E_2)\) be graphs. We say that a pair of functions \(f=(f_v,f_e)\) is a graph morphism from \(𝐆_1\) to \(𝐆_2\) provided \(f_v : V_1 → V_2\), \(f_e : E_1 → E_2\), and for any edge \(e = (v_1,v_2) ∈ E_1\) we have that we have \(f_e(e) = (f_v(v_1), f_v(v_2))\).

group

A group is a monoid expanded with a unary operation \(^{-1}\), called multiplicative inverse, which satisfies \(∀ a ∈ A\), \(a ⋅ a^{-1} = a^{-1} ⋅ a = e\).

groupoid

See magma.

Hausdorff space

A topological space \((X, τ)\) is called a Hausdorff space if the topology separates the points of \(X\). In other words, distinct points have some disjoint neighborhoods.

height

If \(w\) is a term, then the height of \(w\) is denoted by \(|w|\) and defined to be the least \(n\) such that \(w ∈ T_n\).

If \(α\) is a type, then we sometimes refer to the height of \(α\), by which we mean the universe level of \(α\)

Heyting algebra

A Heyting algebra \(⟨L, ∧, ∨, ⊥, ⊤, →⟩\) is a bounded lattice with least and greatest elements ⊥ and ⊤, and a binary “implication” → that satisfies \(∀ a, b, c ∈ L, \ (c ∧ a ≤ b \ ⟺ \ c ≤ a → b)\). Logically, this says a → b is the weakest proposition for which the modus ponens rule, \(\{a → b, a\} ⊢ b\), is sound. The class of Heyting algebras forms a variety that is finitely axiomatizable.

Heyting algebra homomorphism

a lattice homomorphism that also preserves Heyting implications; that is, if \(x, x' ∈ X\), then \(f(x → x') = f(x) → f(x')\).

Hilbert space

A normed linear space whose norm arises from an inner product is called a Hilbert space.

hom set

Some authors require that \(\mathcal C(A,B)\) always be a set and call \(\mathcal C(A,B)\) the hom set from \(A\) to \(B\).

homeomorphic

We call a pair \(X, Y\) of topological spaces homeomorphic if there is a homeomorphism between them.

homeomorphism

A continuous function from a topological space \(X\) to a topological space \(Y\) is called a homeomorphism provided it is one-to-one and onto, and has a continuous inverse from \(Y\) to \(X\).

Clearly the inverse of a homeomorphism is a homeomorphism and the composition of homeomorphisms, when defined, is a homeomorphism.

homomorphism

See morphism.

idempotent

An operation \(f: A^n → A\) is called idempotent provided \(f(a, a, \dots, a) = a\) for all \(a ∈ A\). That is, \(f\) maps constant tuples to their constant image value.

In other terms \(f: (ρ f → A) → A\) is idempotent iff for each constant tuple \(a: ρ f → A\), say, \(∀ i<ρ f, \; a\, i = c\), we have \(f\, a = f(c, c, \dots, c) = c\).

impredicative

A self-referencing definition is called impredicative. A definition is said to be impredicative if it invokes (mentions or quantifies over) the set being defined, or (more commonly) another set which contains the thing being defined.

indiscrete topology

If \(X\) is a nonempty set, then \(\{∅, X\}\) is a topology on \(X\), called the trivial (or indiscrete) topology.

inductive set

A subset \(I\) of a preorder \(X\) is called inductive if \(⋁_X D ∈ I\) for every directed subset \(D ⊆ X\) contained in \(I\). That is, if \(D ⊆ I\), and if every finite subset of \(D\) has an upper bound in \(D\), then \(D\) as a least upper bound in \(I\).

∞-norm

Let \((X, 𝔐, μ)\) be a measure space. The \(∞\)-norm relative to \(μ\) is defined for each real- or complex-valued function \(f\) on \(X\) by

\[\|f\|_∞ := \inf \{a∈ ℝ^∗ ∣ μ\{x : |f(x)| > a\} = 0\} = \inf \{a∈ ℝ^∗ ∣ |f(x)| ≤ a \text{ for } μ-\text{a.e. } x∈ X\},\]

where \(ℝ^∗ = ℝ ∪ \{-∞, ∞\}\) and \(\inf ∅ = ∞\).

initial object

An object \(0\) in a category is called the initial object (or free object) if for every object \(A\) in the category there exists a unique morphism \(!_A: 0 → A\).

The free algebra in a variety is a free object in a category whose objects are algebraic structures.

inner product

Let \(X\) be a vector space over the field \(F\). An inner product on \(X\) is a function \(⟨·,·⟩: X × X → F\) satisfying the following conditions:

1. \(⟨⋅,⋅⟩\) is linear in the first variable; i.e., \(⟨α x + βy, z⟩ = α⟨x,z⟩ + β⟨y,z⟩\) for all \(α, β ∈ F\) and \(x, y, z ∈ X\);

2. \(⟨⋅,⋅⟩\) is symmetric; i.e., \(⟨x, y⟩ = ⟨y, x⟩\) for all \(x, y ∈ X\); and

3. \(⟨x, x⟩ ≥ 0\) for each \(x∈ X\) and \(⟨x, x⟩ = 0\) if and only if \(x = 0\).

inner product space

An inner product space is a vector space equipped with an inner product.

integrable

A real- or complex-valued \(μ\)-measurable function \(f\) is called \(μ\)-integrable (or integrable with respect to \(μ\), or just integrable) over \(X\) if \(∫_X |f| \, dμ < ∞\). We let \(L_1(X, μ)\) (or \(L_1(μ)\), or just \(L_1\)) denote the collection of functions that are \(μ\)-integrable over \(X\).

When \(f∈ L_1(X, μ)\) we define the integral of \(f\) over a measurable set \(E ⊆ X\) by \(∫_E f\, dμ = ∫_E f^+\, dμ - ∫_E f^-\, dμ\).

integral

See Lebesgue integral.

interior

If \(X\) is a topological space and \(A ⊆ X\), then the union of all open sets contained in \(A\) is called the interior of \(A\).

intensional

An intensional definition of a term specifies necessary and sufficient conditions that the term satisfies. In the case of nouns, this is equivalent to specifying all the properties that an object must have in order to be something to which the term refers.

isometrically isomorphic

Two Hilbert spaces \(ℋ_1, ℋ_2\) are called isometrically isomorphic if there exists a unitary operator from \(ℋ_1\) onto \(ℋ_2\).

In other words, \(U: ℋ_1 ↠ ℋ_2\) is a surjective isometry from \(ℋ_1\) to \(ℋ_2\).

isometry

Let \((X, \|\,.\,\|_1)\) and \((Y, \|\,.\,\|_2)\) be normed linear spaces. A linear transformation \(T: X → Y\) is called an isometry if it preserves norms, that is, \(\|Tx\|_2 = \|x\|_1\) holds for all \(x∈ X\).

isomorphism

A morphism \(f: A → B\) is called an isomorphism if there exists a morphism \(g: A → B\) such that \(g ∘ f= \mathrm{id}_A\) and \(f ∘ g = \mathrm{id}_B\). We write \(f^{-1}\) to denote \(g\) when it exists.

kernel

By the kernel of a function \(f: A → B\) we mean the binary relation on \(A\) denoted and defined by \(\mathrm{ker} f := \{(a₁, a₂) : f a₁ = f a₂\}\).

Kleene closure

See free monoid.

lambda calculus

See https://en.wikipedia.org/wiki/Lambda_calculus.

lattice

a poset whose universe is closed under all finite meets and joins is called a lattice.

lattice homomorphism

a function \(f: X → Y\) preserving finite meets and joins.

law of the excluded middle

This is an axiom of classical logic asserting that for all propositions P either ¬ P or P holds.

Lebesgue integrable

A function that is integrable with respect to Lebesgue measure is called a Lebesgue integrable function.

Lebesgue integral

Let \((X, 𝔐, μ)\) be a measure space. If \(E ∈ 𝔐\) and \(s: X → [0, ∞)\) is a measurable simple function of the form \(s = ∑_{i=1}^n α_i χ_{A_i}\), where \(α_1, \dots, α_n ∈ ℝ\) are the distinct values of \(s\), then we denote and define the Lebesgue integral of \(s\) over \(E\) as follows:

\[∫_E s\, dμ := ∑_{i=1}^n α_i μ(A_i ∩ E),\]

where we adopt the convention that \(0⋅∞ = 0\) (in case, e.g., \(α_i = 0\) and \(μ(A_i ∩ E) = ∞\) for some \(1≤ i ≤ n\)).

If \(f: X → [0, ∞]\) is a nonnegative extended real-valued measurable function and \(E∈ 𝔐\), then we denote and define the Lebesgue integral of \(f\) over \(E\) with respect to the measure \(μ\) (or, the integral of \(f\)) as follows:

\[∫_E f\, dμ := \sup ∫_E s\, dμ,\]

where the supremum is taken over all simple measurable functions \(s\) such that \(0≤ s ≤ f\).

If \(μ\) is the only measure in context, then we may write \(∫_E f\) in place of \(∫_E f\, dμ\), and \(∫ f\) in place of \(∫_X f\).

Lebesgue measurable function

Let \(E⊆ ℝ\). A function \(f: E → ℝ\) is called Lebesgue measurable provided \(f^{-1}(G)\) is a Lebesgue measurable set for every open set \(G ⊆ ℝ\). Equivalently, \(f\) is Lebesgue measurable iff the set \(f^{-1}((α, ∞))\) is Lebesgue measurable for every \(α ∈ ℝ\).

Lebesgue measurable set

A set that is measurable with respect to Lebesgue measure is called a Lebesgue measurable set; that is, \(E⊆ ℝ\) is Lebesgue measurable iff

\[m^∗ A = m^∗ (A ∩ E) + m^∗(A ∩ E^c)\; \text{ holds for all } A ⊆ R.\]

Lebesgue measure

Let \(ℓ\) be the measure defined on the semiring \(S := \{[a, b) ∣ a, b ∈ ℝ\}\) of bounded intervals by \(ℓ[a, b)= b-a\) for all \(a ≤ b\). Let \(ℓ^∗: 𝒫(ℝ) → [0, ∞]\) be the outer measure generated by \(ℓ\). That is, for \(E⊆ ℝ\),

\[ℓ^∗(E) := \inf \{∑_{n=1}^∞ m(I_n) ∣ \{I_n\} ⊆ S \text{ and } E ⊆ ⋃_{n=1}^∞ I_n\}\]

The measure obtained by restricting \(ℓ^∗\) to the measurable subsets in \(𝒫(ℝ)\) is called Lebesgue measure.

Observe that the \(ℓ^∗\)-measurable subsets in \(𝒫(ℝ)\) are those \(A∈ 𝒫(ℝ)\) satisfying

\[ℓ^∗ E = ℓ^∗(E ∩ A) + ℓ^∗(E ∩ A^c)\; \text{ for all } E ⊆ ℝ.\]

Lebesgue outer measure

See Lebesgue measure

Lebesgue null set

A Lebesgue null set is a set of Lebesgue measure zero.

Leibniz equal

See function extensionality.

left module

See module.

lift (n)

See lifts (v)

lifts (v)

For \(ρ ⊆ α × α\), and \(f: α → β\), we say that \(f\) lifts to a function on the quotient \(α/ρ\) provided the following implication holds for all \(x y: α\): if \(ρ x y\) then \(f x = f y\). The function to which \(f\) lifts is called the lift of \(f\).

limit point

A point \(x\) is called a limit point (or accumulation point) of a set \(A\) in a topological space if \(A ∩ (V \ {x}) ≠ ∅\) for every neighborhood \(V\) of \(x\).

linear functional

Let \(X\) be a vector space over the field \(F\). A linear functional on \(X\) is a linear transformation with codomain \(F\).

linear operator

See linear transformation.

linear space

See vector space.

linear transformation

A linear transformation (or linear operator) is a morphism in the category of vector spaces.

Explicitly, if \(X\) and \(Y\) are vector spaces over the field \(F\), then a linear transformation from \(X\) to \(Y\) is a function \(T: X → Y\) that is “linear” in that it preserves the vector space operations (addition and scalar products); that is,

1. \(∀ x, x' ∈ X\), \(T(x + x') = T\,x + T\,x'\).

2. \(∀ α ∈ F\), \(∀ x ∈ X\), \(T(α x) = α T\,x\).

(These conditions are equivalent to the single condition \(∀ α ∈ F\), \(∀ x, x' ∈ X\), \(T(α x + x') = α T\,x + T\,x'\).)

Lipschitz condition

A function \(f\) satisfies a Lipschitz condition on an interval if there is a constant \(M\) such that \(|f(x) - f(y)| ≤ M|x-y|\) for all \(x\) in the interval.

Lipschitz constant

The number \(M\) in the definition of Lipschitz condition is called the Lipschitz constant.

Lipschitz continuous

A function is called Lipschitz continuous on an interval if it satisfies a Lipschitz condition on that interval.

locally compact

A topological space \((X,τ)\) is called locally compact if every point of \(X\) has a neighborhood whose closure is compact.

locally small category

A category \(\mathcal C\) is locally small if for every pair \(A\), \(B\) of objects in \(\mathcal C\) the collection of morphisms from \(A\) to \(B\) is a set.

logically equivalent

Propositions \(P\) and \(Q\) are logically equivalent provided \(P\) implies \(Q\) and \(Q\) implies \(P\).

lower limit

Let \(\{a_n\}\) be a sequence in \([-∞, ∞]\), and put \(b_k = \inf \{a_k, a_{k+1}, \dots\}\) for \(k∈ ℕ\) and \(β = \sup \{b_0, b_1, b_2, \dots \}\). We call \(β\) the lower limit (or limit inferior) of \(\{a_n\}\), and write \(β = \liminf\limits_{n→ ∞} a_n\). The upper limit, \(\limsup\limits_{n→ \infty} a_n\) is definied similarly.

Observe that

1. \(b_0 ≤ b_1 ≤ b_2 ≤ \cdots ≤ β\) and \(b_k → β\) as \(k→ ∞\);

2. there is a subsequence \(\{a_{n_j}\}\) of \(\{a_n\}\) that converges to \(β\) as \(j→ ∞\) and \(β\) is the smallest number with this property.

3. \(\limsup\limits_{n→∞} a_n = -\liminf\limits_{n→∞} (- a_n)\).

(See also the definition of upper limit and the remarks following that definition.)

magma

An algebra with a single binary operation is called a magma (or groupoid or binar). The operation is usually denoted by \(+\) or \(⋅\), and we write \(a+b\) or \(a ⋅ b\) (or just \(ab\)) for the image of \((a, b)\) under this operation, which we call the sum or product of \(a\) and \(b\), respectively.

measurable function

Let \((X, 𝔐)\) and \((Y, 𝔑)\) be measurable spaces. A function \(f: X → Y\) is called \((𝔐, 𝔑)\)-measurable (or just measurable) if \(f^{-1}(N) ∈ 𝔐\) for every \(N ∈ 𝔑\).

measurable set

If \(𝔐\) is a σ-algebra in \(X\), then the members of \(𝔐\) are called the measurable sets in \(X\).

If \(μ^∗\) is an outer measure on \(X\), a set \(A ⊆ X\) is called \(μ^∗\)-measurable set (or measurable with respect to \(μ^∗\), or just measurable) provided

\[μ^∗ E = μ^∗(E ∩ A) + μ^∗(E ∩ A^c)\; \text{ for all } E ⊆ X.\]

Equivalently, \(A\) is measurable iff

\[μ^∗ E ≥ μ^∗(E ∩ A) + μ^∗(E ∩ A^c)\; \text{ for all } E ⊆ X \text{ such that } μ^∗ E < ∞.\]

measurable space

If \(𝔐\) is a σ-algebra in \(X\), then \((X, 𝔐)\) (or just \(X\)) is called a measurable space.

measure

A (positive) measure is a function \(μ: 𝔐 → [0, ∞]\), defined on a \(σ\)-algebra \(𝔐\), which is countably additive.

measure space

A measure space is a triple \((X, 𝔐, μ)\) where \(X\) is a measurable space, \(𝔐\) is the σ-algebra of measurable sets in \(X\), and \(μ: 𝔐 → [0, ∞]\) is a measure.

metric space

A metric space is a pair \((X, d)\) where \(X\) is a set and \(d: X × X → ℝ\) is a metric (or distance function), that is, a function satisfying the following conditions for all \(x, y, z ∈ X\):

1. \(d(x, y) ≥ 0\)

2. \(d(x,y) = 0\) if and only if \(x = y\)

3. (symmetry) \(d(x, y) = d(y, x)\)

4. (triangle inequality) \(d(x, z) ≤ d(x, y)+d(y, z)\).

module

Let \(R\) be a ring with unit. A left unitary \(R\)-module (or simply \(R\)-module) is an algebra \(⟨M, \{0, -, +\} ∪ \{f_r : r∈ R\}⟩\) with an abelian group reduct \(⟨M, \{0, -, +\}⟩\) and unary operations \(\{f_r : r ∈ R\}\) that satisfy the following: \(∀ r, s ∈ R\), \(∀ x, y ∈ M\),

1. \(f_r(x + y) = f_r(x) + f_r(y)\)

2. \(f_{r+s}(x) = f_r(x) + f_s(x)\)

3. \(f_r(f_s(x)) = f_{rs}(x)\)

4. \(f_1(x) = x\).

monoid

If \(⟨M, ⋅⟩\) is a semigroup and if there exists \(e ∈ M\) that is a multiplicative identity (i.e., \(∀ m ∈ M\), \(e ⋅ m = m = m ⋅ e\)), then \(⟨M, \{e, ⋅\}⟩\) is called a monoid.

monoid homomorphism

Given monoids \(𝐌_1 = (M_1, e_1, ⋆)\) and \(𝐌_2 = (M_2, e_2, ∗)\) we say that a function \(f : M_1 → M_2\) is a monoid homomorphism from \(𝐌_1\) to \(𝐌_2\) provided \(f\) preserves the nullary (identity) and binary operations; that is, \(f(e_1) = e_2\) and \(f (x ⋆ y) = f(x) ∗ f(y)\) for all \(x, y ∈ M_1\).

monomorphism

A morphism \(f: A → B\) is called a monomorphism if for every object \(X\) and every pair \(h, h' : X → A\) of morphisms, \(f ∘ h = f ∘ h'\) implies \(h = h'\). When \(f\) is a monomorphism we often say \(f\) is “mono” and write \(f: A ↣ B\).

monotone function

Given posets \(⟨A, ≤ᴬ⟩\) and \((B, ≤ᴮ)\) we say that a function \(f: A → B\) is monotone from \(⟨A, ≤ᴬ⟩\) to \(⟨B, ≤ᴮ ⟩\) when for any \(x, y ∈ A\) we have that \(x ≤ᴬ y\) implies that \(f(x) ≤ᴮ f(y)\).

(See also monotone increasing function.)

morphism

If \(𝔸 = ⟨A, F^𝔸⟩\) and \(𝔹 = ⟨B, F^𝔹⟩\) are algebraic structures in the signature \(σ = (F, ρ)\), then a morphism (or homomorphism) \(h: 𝔸 → 𝔹\) is a function from \(A\) to \(B\) that preserves (or commutes with) all operations; that is, for all \(f∈ F\), for all \(a_1, \dots, a_{ρ f} ∈ A\),

\[f^𝔹 (h\,a_1, \dots, h\,a_{ρ f}) = h f^𝔸(a_1, \dots, a_{ρ f}).\]

middle linear map

If \(B_r\) and \(_rC\) are modules over a ring \(R\), and \(A\) is an abelian group, then a middle linear map from \(B × C\) to \(A\) is a function \(f: B × C → A\) such that for all \(b, b_1, b_2 ∈ B\) and \(c, c_1, c_2 ∈ C\) and \(r ∈ R\):

\[\begin{split}f(b_1 + b_2, c) &= f(b_1,c) + f(b_2,c)\\ f(b, c_1 + c_2) &= f(b,c_1) + f(b,c_2)\\ f(br, c) &= f(b,rc)\end{split}\]

module

A module \(M\) over a ring \(R\) is…

monotone increasing function

A real- or extended real-valued function \(f\) deifned on \(ℝ\) is called monotone increasing (or monotonically increasing) on the interval \([a,b] ⊆ ℝ\) if \(a≤ x < y ≤ b\) implies \(f(x) ≤ f(y)\).

(See also monotone function.)

multiplicative inverse

Let \(𝔸 = ⟨ A, e, ∘, \dots ⟩\) be an algebra in a signature with a nullary “identity” operation \(e: () → A\) and a binary “multiplication” operation \(∘: A × A → A\). Then the element \(b ∈ A\) is a multiplicative inverse of \(a ∈ A\) provided \(a ∘ b = e = b ∘ a\).

mutually singular

Suppose \(λ_1\) and \(λ_2\) are measures on \(𝔐\) and suppose there exists a pair of disjoint sets \(A\) and \(B\) such that \(λ_1\) is concentrated on \(A\) and \(λ_2\) is concentrated on \(B\). Then we say that \(λ_1\) and \(λ_2\) are mutually singular and we write \(λ_1 ⟂ λ_2\).

natural isomorphism

An isomorphism in a functor category is referred to as a natural isomorphism.

natural transformation

Given functors \(F, G : \mathcal C → \mathcal D\), a natural transformation \(α : F ⇒ G\) is a family \(\{α_A : A ∈ \mathcal C_{\mathrm{obj}}\}\) of morphisms in \(\mathcal D\) indexed by the objects of \(\mathcal C\) such that, for each \(A ∈ \mathcal C_{\mathrm{obj}}\), the map \(\alpha_A\) is a morphism from \(FA\) to \(GA\) satisfying the naturality condition, \(Gf ∘ α_A = α_B ∘ Ff\), for each \(f : A → B\) in \(\mathcal C_{\mathrm{mor}}\). We shall write \(α : F ⇒ G : \mathcal C → \mathcal D\) to indicate that α is a natural transformation from \(F\) to \(G\), where \(F, G : \mathcal C → \mathcal D\).

naturally isomorphic

If there is a natural isomorphism between the functors \(F\) and \(G\), then we call \(F\) and \(G\) naturally isomorphic.

negative part

The negative part of \(f: X → [-∞, ∞]\) is the function that is denoted and defined for each \(x∈ X\) by \(f^-(x) = \max\{-f(x),0\}\).

Observe that \(f\) is measurable if and only if both the positive and negative parts of \(f\) are measurable. Also, \(f^+, f^-: X → [0, ∞]\), \(f = f^+ - f^-\), and \(|f| = f^+ + f^-\).

negligible

A measurable set is called negligible if it has measure 0.

neighborhood

A neighborhood of a point \(p\) in a topological space \(X\) is a set \(A\) in \(X\) whose interior contains \(p\); that is, \(p ∈ A^o\). 3

nonnegative function

A function \(f: X → ℝ\) such that \(f(x) ≥ 0\) for all \(x∈ ℝ\) is called a nonnegative function. We use the shorthand \(f ≥ 0\) to denote that \(f\) is a nonnegative function.

norm

Let \(X\) be a vector space over the field \(F\), and let \(|\,⋅\,|: F → [0,∞)\) be a valuation on \(F\). A norm on \(X\) is a function \(\|\;\|: X → [0, ∞)\) that satisfies the following conditions:

1. \(\|x + y\| ≤ \|x\| + \|y\|\), for all \(x, y ∈ X\);

2. \(\|α x\| = |α| \|x\|\), for all \(x ∈ X\) and \(α ∈ F\);

3. \(\|x\| = 0\) if and only if \(x = 0\).

Thus, a norm is a seminorm satisfying: \(\|x\| = 0\) only if \(x = 0\).

normed linear space

A normed linear space (or normed vector space) is a pair \((X, \|\,⋅\,\|)\) consisting of a vector space \(X\) and a norm \(\|\,⋅\,\|\) defined on \(X\).

normed vector space

See normed linear space.

nowhere dense

A set \(G\) is nowhere dense in \(X\) if the closure of \(G\) contains no nonempty open subsets of \(X\). Equivalently, the interior of the closure of \(G\) is empty (in symbols, \(Ḡ^o = ∅\)).

nullary operation

An operation \(f\) on a set \(A\) is called nullary if the arity of \(f\) is 0; that is, \(f: () → A\); equialently, \(f\) takes no arguments, so is simply a (constant) element of \(A\).

ω-chain

Let \(⟨ X, ≤ ⟩\) be a preordered set. An ω-chain is an enumerable chain; that is, a chain the elements that can be indexed by the natural numbers.

ω-chain cocomplete

A preorder in which joins of all ω-chains exist is called ω-chain cocomplete.

ω-chain cocomplete poset

an antisymmetric ω-chain cocomplete preorder.

open ball

Let \((X, d)\) be a metric space. If \(x ∈ X\) and \(r > 0\) are fixed, then the set denoted and defined by \(B(x, r) = \{y ∈ X ∣ d(x,y) < r\}\) is called the open ball with center \(x\) and radius \(r\).

open covering

See covering.

open mapping

Let \(X\) and \(Y\) be metric or topological spaces. A set function \(T: 𝒫(X) → 𝒫(Y)\) is called an open mapping if \(T(G)\) is open in \(Y\) for every open \(G ⊆ X\).

open set

A subset \(V\) of a metric or topological space is called open if for every \(x ∈ V\) there is an open ball contained in \(V\) that contains \(x\).

For a metric space \((X,d)\) this means that a set \(V\) is open iff for every \(x ∈ V\) there exists \(δ > 0\) such that

\[B(x,δ) := \{y ∈ X ∣ d(x,y) < δ\} ⊆ V\]

For a topological space \((X, τ)\) the open sets are the sets belonging to the topology \(τ\).

operator norm

If \(X\) and \(Y\) are normed linear spaces, then the space \(𝔅(X,Y)\) of bounded linear transformations is a vector space and the function \(T ↦ \|T\|\) defined by

\[\|T\| = \sup \{ \|Tx\| : \|x\| = 1 \}\]

is a norm on \(𝔅(X,Y)\), called the operator norm.

There are other, equivalent ways to express the operator norm; e.g.,

\[\|T\| = \sup \{ \frac{\|Tx\|}{\|x\|} : x ≠ O\} = \inf \{ C : \|Tx\| ≤ C\|x\| \text{ for all } x\}.\]

opposite category

Given a category \(\mathcal C\) the opposite (or dual) category \(\mathcal C^{\mathrm{op}}\) has the same objects as \(\mathcal C\) and whenever \(f: A → B\) is a morphism in \(\mathcal C\) we define \(f : B → A\) to be a morphism in \(\mathcal C^{\mathrm{op}}\).

orthogonal set

Let \((X, ⟨⋅, ⋅⟩)\) be an inner product space. A subset \(Q ⊆ X\) is called orthogonal provided \(⟨ 𝐮, 𝐯 ⟩ = 0\) for all \(𝐮 ≠ 𝐯\) in \(Q\).

orthonormal basis

A maximal orthonormal set in a Hilbert space is known as an orthonormal basis.

orthonormal set

Let \((X, ⟨⋅, ⋅⟩)\) be an inner product space. An orthogonal set \(U ⊆ X\) is called orthonormal provided \(\|u\| = 1\) for all \(𝐮 ∈ U\).

In other terms, a subset \(Q ⊆ X\) is called orthonormal provided for all \(𝐮, 𝐯 ∈ Q\),

\[\begin{split}⟨ 𝐮, 𝐯 ⟩ = \begin{cases} 0,& 𝐮 ≠ 𝐯,\\ 1,& 𝐮 = 𝐯. \end{cases}\end{split}\]

Every inner product space has a maximal orthonormal set.

outer measure

An outer measure on a nonempty set \(X\) is a function \(μ^∗: 𝒫(X) → [0, ∞]\) that satisfies

1. \(μ^∗ ∅ = 0\),

2. \(μ^∗ A ≤ μ^∗ B\) if \(A ⊆ B ⊆ X\),

3. \(μ^∗\bigl(⋃_{i=1}^∞ A_i\bigr) ≤ ∑_{i=1}^∞ μ^∗ A_i\) if \(A_i ⊆ X\) for all \(1 ≤ i ≤ ∞\).

parallel morphisms

Morphisms \(f,g : A → B\) are called parallel morphisms just in case \(\mathrm{src} f = \mathrm{src} g\) and \(\mathrm{tar} f = \mathrm{tar} g\).

partial function

A partial function from \(A\) to \(B\) is a total function on some (potentially proper) subset \(\dom_f\) of \(A\).

partial order

See partial order.

partial ordering

A partial ordering (or “partial order”) is an antisymmetric preorder.

partially ordered set

A partially ordered set (or “poset”) \(⟨X, R⟩\) is a set \(X\) along with a partial ordering \(R\) defined on \(X\).

point

Given a category with an initial object \(\mathbf{1}\) and another object \(A\), the morphisms with domain \(\mathbf{1}\) and codomain \(A\) are called the points or global elements of \(A\).

pointwise limit

Let \(f_n: X → [-∞, ∞]\) for each \(n∈ ℕ\). If the limit \(f(x) = \lim_{n→∞} f_n(x)\) exist at every \(x ∈ X\), then we call \(f: X → ℝ\) the pointwise limit of the sequence \(\{f_n\}\).

poset

A poset \(⟨X, ⊑⟩\) consists of a set \(X\) and an antisymmetric preorder \(⊑\) on \(X\).

positive measure

See measure.

positive part

The positive part of \(f: X → [-∞, ∞]\) is the function that is denoted and defined for each \(x∈ X\) by \(f^+(x) = \max\{f(x),0\}\).

Observe that \(f\) is measurable if and only if both the positive and negative parts of \(f\) are measurable. Also, \(f^+, f^-: X → [0, ∞]\), \(f = f^+ - f^-\), and \(|f| = f^+ + f^-\).

powerset functor

The (covariant) powerset functor is a functor \(P: \mathbf{Set} → \mathbf{Set}\) such that for each morphism \(f: A → B\) the morphism \(P f : 𝒫(A) → 𝒫(B)\) is given by \(P f(S) = \{f(x): x ∈ S\}\) for each \(S ⊆ A\).

power set operator

The powerset operator \(𝒫\) maps a class \(X\) to the class \(𝒫 (X)\) of all subsets of \(X\).

preorder

A preorder on a set \(X\) is a reflexive and transitive subset of \(X × X\).

preserves

See respects.

product

Given two objects \(A\) and \(B\) a product of \(A\) and \(B\) is defined to be an object, \(A × B\), along with morphisms \(π_1: A × B → A\) and \(π_2: A × B → B\) such that for every object \(X\) and all morphisms \(f: X → A\) and \(g: X → B\) there exists a unique morphism \(⟨f,g⟩: X → A × B\) such that \(p_1 ∘ ⟨f,g⟩ = f\) and \(p_2 ∘ ⟨f,g⟩ = g\).

product σ-algebra

Let \((X, 𝔐, μ)\) and \((Y, 𝔑, ν)\) be measure spaces. If we want to make the product \(X × Y\) into a measurable space, we naturally consider the σ-algebra generated by the sets in \(𝔐 × 𝔑 = \{A × B ⊆ X × Y ∣ A ∈ 𝔐, B ∈ 𝔑\}\), and we define \(𝔐 ⊗ 𝔑 := σ(𝔐 × 𝔑)\); that is, \(𝔐 ⊗ 𝔑\) is the σ-algebra generated by \(𝔐 × 𝔑\). 4

product topology

Let \(\{(X_λ, τ_λ)\}_{λ∈ Λ}\) be a collection of topological spaces indexed by a set \(Λ\). The product topology on the Cartesian product \(∏_{λ∈ Λ}X_λ\) is the topology that has a base consisting of sets of the form \(∏_{λ∈Λ}V_λ\), where \(V_λ ∈ τ_λ\) and \(V_λ = X_λ\) for all but finitely many \(λ\).

Equivalently, the product topology is the weakest topology that makes all the projection maps \(π_λ(\mathbf x) = x_λ\) continuous. In other words, if \(Π\) denotes the clone of all projection operations on \(∏_{λ ∈ Λ} X_λ\), then the product topology is the \(Π\)-topology.

projection operation

The \(i\) is denoted by \(π^k_i: (k → A) → A\) and defined for each \(k\)-tuple \(a: k → A\) by \(π^k_i \, a = a\, i\).

projection operator

If \(σ: k → n\) is a \(k\)-tuple of numbers in the set \(n = \{0, 1, \dots, n-1\}\), then we can compose an \(n\)-tuple \(a ∈ ∏_{0≤i<n} A_i\) with \(σ\) yielding \(a ∘ σ ∈ ∏_{0≤i<k} A_{σ\, i}\).

The result is a \(k\)-tuple whose \(i\)-th component is \((a ∘ σ)(i) = a(σ(i))\).

If \(σ\) happens to be one-to-one, then we call the following a projection operator:

\[\Proj\, σ: ∏_{0≤i< n} A_i → ∏_{0≤i<k} A_{σ\, i}; \ \ a ↦ a ∘ σ.\]

That is, for \(a ∈ ∏_{0≤i<n} A_i\) we define \(\Proj\,σ\, a = a ∘ σ\).

proposition extensionality

This axiom asserts that when two propositions imply one another, they are actually equal. This is consistent with set-theoretic interpretations in which any element a:Prop is either empty or the singleton set {*}, for some distinguished element *. The axiom has the effect that equivalent propositions can be substituted for one another in any context.

quotient

If \(R\) is an equivalence relation on \(A\), then the quotient of \(A\) modulo \(R\) is denoted by \(A/R\) and is defined to be the collection \(\{ a/R ∣ a ∈ A \}\) of equivalence classes of \(R\).

Radon-Nikodym derivative

We denote the function \(h\) that appears in the Radon-Nikodym theorem by \(dλ_a/dμ\), which is called the Radon-Nikodym derivative of \(λ_a\) with respect to \(μ\), and we have \(dλ_a = \frac{dλ_a}{dμ} dμ\).

Strictly speaking, \(dλ_a/dμ\) is the equivalence class of functions that are equal to \(h\) (\(μ\)-a.e.).

reduct

Given two algebras \(𝔸\) and \(𝔹\), we say that \(𝔹\) is a reduct of \(𝔸\) if both algebras have the same universe and \(𝔹\) can be obtained from \(𝔸\) by removing operations.

reflexive

A binary relation \(R\) on a set \(X\) is called reflexive provided \(∀ x ∈ X, \ x \mathrel{R} x\).

relation

Given sets \(A\) and \(B\), a relation from \(A\) to \(B\) is a subset of \(A × B\).

relational product

Given relations \(R : A → B\) and \(S : B → C\) we denote and define the relational product (or composition) of \(S\) and \(R\) to be \(S ∘ R = \{(a,c) : (∃ b ∈ B) a \mathrel{R} b ∧ b \mathrel{S} c \}\).

relational structure

A relational structure \(𝔸 = ⟨A, ℛ⟩\) is a set \(A\) together with a collection \(ℛ\) of relations on \(A\).

relative topology

If \((X, τ)\) is a topological space and \(Y ⊆ X\), then \(τ_Y := \{V ∩ Y ∣ V ∈ τ\}\) is a topology on \(Y\), called the relative topology induced by \(τ\).

respects

Given a function \(f: α → α\), we say that \(f\) respects (or preserves) the binary relation \(R ⊆ α × α\), and we write \(f ⊧ R\), just in case \(∀ x, y :α \ (x \mathrel R y \ → \ f x \mathrel R f y)\).

(The symbol ⊧ is produced by typing \models.)

If \(f: (β → α) → α\) is a \(β\)-ary operation on \(α\), we can extend the definition of “\(f\) respects \(R\)” in the obvious way.

First, for every pair \(u : β → α\) and \(v : β → α\) (\(β\)-tuples of \(α\)), we say that \((u, v)\) “belongs to” \(R ⊆ α × α\) provided

\[∀ i: β \ ui \mathrel R vi\]

Then we say \(f: (β → α) → α\) respects (or preserves) the binary relation \(R ⊆ α × α\), and we write \(f ⊧ R\), just in case \(∀ u, v, \ [(∀ i: β, \ u i \mathrel R v i) \ → \ f u \mathrel R f v]\).

retraction

todo: insert definition

retract

todo: insert definition

right module

A right module \(M\) over a ring \(R\) is…

ring

An algebra \(⟨R, \{0, -, +, ⋅\}⟩\) is called a ring just in case the following conditions hold:

1. the reduct \(⟨R, \{0, -,+\}⟩\) is an abelian group,

2. the reduct \(⟨R, ⋅ ⟩\) is a semigroup, and

3. “multiplication” \(⋅\) distributes over “addition” \(+\); that is, \(∀ a, b, c ∈ R\), \(a ⋅ (b+c) = a ⋅ b + a ⋅ c\) and \((a+b)⋅ c = a ⋅ c + b ⋅ c\).

ring of sets

A nonempty collection \(R\) of subsets of a set \(X\) is said to be a ring if \(A, B ∈ R\) implies \(A ∪ B ∈ R\) and \(A-B ∈ R\).

ring with unity

A ring with unity (or unital ring) is an algebra \(⟨R, \{0, 1, -, +, ⋅\}⟩\) with a ring reduct \(⟨R, \{0, -, +, ⋅\}⟩\) and a multiplicative identity \(1 ∈ R\); that is \(∀ r ∈ R\), \(r ⋅ 1 = r = 1 ⋅ r\).

second category

A set \(G\) is of the second category if it is not of the first category.

section

For a set \(E ⊆ X × Y\), the x-section of \(E\) at the point \(t\) is defined as follows:

\[G_t = \{y ∈ ℝ: (x,y) ∈ E \text{ and } x=t\}.\]

self-adjoint

A linear transformation of a Hilbert space \(ℋ\) to itself is called self-adjoint just in case \(∀ x, y ∈ ℋ, ⟨x, Ty⟩ = ⟨Tx, y⟩\).

self-dual

A normed linear space \(X\) is called self-dual provided \(X ≅ X^∗\).

A category \(𝒞\) is called self-dual if \(𝒞^{\mathrm{op}} = 𝒞\).

semigroup

A magma whose binary operation is associative is called a semigroup. That is, a semigroup is a magma \(⟨A, ⋅⟩\) whose binary operation satisfies \(∀ a, b, c ∈ A\), \((a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)\).

seminorm

Let \(X\) be a vector space over the field \(F\). A seminorm on \(X\) is a function \(\|\;\|: X → [0, ∞)\) that satisfies

1. \(\|x + y\| ≤ \|x\| + \|y\|\), for all \(x, y ∈ X\);

2. \(\|α x\| = |α| \|x\|\), for all \(x ∈ X\) and \(α ∈ F\).

semiring of sets

A collection \(S\) of subsets of a nonempty set \(X\) is called a semiring if it satisfies the following properties:

1. \(∅ ∈ S\);

2. \(A, B ∈ S \; ⟹ \; A ∩ B ∈ S\);

3. \(A, B ∈ S \; ⟹ \; ∃ C_1, \dots, C_n ∈ S\), \(A-B = ⋃_{i=1}^n C_i\) and \(∀ i≠j, \,C_i ∩ C_j = ∅\).

separable

An infinite Hilbert space is called separable if it has a countable orthonormal basis.

separates the points

We say that a collection \(S\) of subsets of \(X\) separates the points of \(X\) if for every pair \(p, q\) of distinct points in \(X\) there exist disjoint sets \(S_1, S_2∈ S\) such that \(p ∈ S_1\) and \(q∈ S_2\).

Let \(F\) be a field. We say that a collection \(𝔄⊆ F^X\) of \(F\)-valued functions separates the points of \(X\) if for every pair \(p, q\) of distinct points in \(X\) there exists \(f ∈ 𝔄\) such that \(f(u) ≠ f (v)\).

σ-algebra

A collection \(𝔐\) of subsets of a nonempty set \(X\) is called a σ-algebra if it satisfies the following conditions:

1. \(X ∈ 𝔐\);

2. if \(A ∈ 𝔐\) then \(A^c:= X - A\) of \(A\) also belongs to \(𝔐\).

3. if \(A_n ∈ 𝔐\) for \(n ∈ ℕ\), then \(⋃_{n = 0}^∞ A_n ∈ 𝔐\).

Equivalently, a σ-algebra of sets is an algebra of sets that is closed under countable unions.

(For the algebraic meaning of the term \(σ\)-algebra, see the definition of algebraic structure.)

σ-finite measure

If \((X, 𝔐, μ)\) is a measure space, then \(μ\) is a σ-finite measure provided \(X = ⋃_j E_j\) for some \(E_j ∈ 𝔐\) such that \(μ E_j < ∞\) for all \(1≤ j < ∞\).

signature

a pair \(σ = (F, ρ)\) consisting of a collection \(F\) of operation symbols and an arity function \(ρ : F → β\) that maps each operation symbol to its arity; here, \(β\) denotes the arity type.

signed measure

Let \((X, 𝔐)\) be a measurable space. A signed measure on \((X, 𝔐)\) is a function \(ν: 𝔐 → [-∞, ∞]\) such that

1. \(ν ∅ = 0\);

2. \(ν\) assumes at most one of the values \(±∞\);

3. \(ν\) is countably additive.

The last item means that

(60)\[ν(⋃_j A_j) = ∑_j ν(A_j)\]

whenever \(\{A_j\}\) is a collection of disjoint sets in \(𝔐\).

Moreover, the sum on the right-hand side of (60) converges absolutely if the left-hand side of (60) is finite.

simple function

A complex- or real-valued function \(s\) whose range consists of only finitely many points is called a simple function.

Let \(s\) be a simple function with domain \(X\) and suppose \(α_1, \dots, α_n\) is the set of distinct values of \(s\). If we set \(A_i = \{x\in X : s(x) = \alpha_i\}\), then clearly

(61)\[s = ∑_{i=1}^n α_i χ_{A_i},\]

where \(χ_{A_i}\) is the characteristic function of the set \(A_i\).

The definition of simple function assumes nothing about the sets \(A_i\); thus, a simple function is not necessarily measurable.

Observe also that the function \(s\) in (61) is integrable if and only if each \(A_i\) has finite measure.

simplex category

See finite ordinals.

small category

A category is called small if its collections of objects and morphisms are sets.

source vertex

Given a directed graph \(\mathbf G = (V,E)\) and an edge \(e=(v_1,v_2) ∈ E\), we refer to \(v_1\) as the source vertex of \(e\).

step function

A finite linear combination of characteristic functions of bounded intervals of \(ℝ\) is called a step function.

subadditive

Let \(𝒮 = \{S_λ: λ∈ Λ\}\) be a collection of sets and let \(R\) be a ring. A function \(s: 𝒮 → R\) is called subadditive if for every subset \(Γ ⊆ Λ\) such that \(\{S_γ : γ ∈ Γ\}\) is a collection of subsets in \(𝒮\), we have .. math:: s bigl( ⋃_{γ∈Γ} A_γ bigr) ≤ ∑_{γ∈ Γ} s (A_γ).

subalgebra

Suppose \(𝔸 = ⟨A, F^𝔸⟩\) is an algebra. If \(B ≠ ∅\) is a subuniverse of 𝔸, and if we let \(F^𝔹 = \{ f ↾ B : f ∈ F^𝔸 \}\), then \(𝔹 = ⟨ B, F^𝔹 ⟩\) is an algebra, called a subalgebra of 𝔸.

subdcpo

If \(X\) is a dcpo then the subset \(A ⊆ X\) is a subdcpo of \(X\) if every directed subset \(D ⊆ A\) satisfies \(⋁_X D ∈ A\).

subuniverse

Suppose \(𝔸 = ⟨A, F^𝔸⟩\) is an algebra. If a subset \(B ⊆ A\) is closed under \(F^𝔸\), then we call \(B\) a subuniverse of \(𝔸\).

symmetric

A binary relation \(R\) on a set \(X\) is called symmetric provided \(∀ x, y ∈ X \ (x \mathrel{R} y \ → \ y \mathrel{R} x)\);

target vertex

Given a directed graph \(\mathbf G = (V,E)\) and an edge \(e=(v_1,v_2)\in E\), we refer to \(v_2\) as the target vertex of \(e\).

terminal object

An object \(\mathbf{1}\) is called a terminal (or bound) object if for every object \(A\) in the same category there exists a unique morphism \(⟨\ ⟩_A: A → \mathbf{1}\).

ternary operation

An operation \(f\) on a set \(A\) is called ternary if the arity of \(f\) is 3; that is, \(f: A × A × A → A\) (or, in curried form, \(f: A → A → A → A\)).

topology

A topology \(τ\) on a set \(X\) is a collection of subsets of \(X\) containing \(X\) and the empty set, and is closed under finite intersections and arbitrary unions. That is, \(τ\) satisfies

1. \(∅ ∈ τ\) and \(X ∈ τ\);

2. \(\{V_i ∣ i = 1, \dots, n\} ⊆ τ\) implies \(⋂_{i=1}^n V_i ∈ τ\);

3. \(\{V_α ∣ α ∈ A\} ⊆ τ\) implies \(⋃_{α∈A} V_α ∈ τ\).

topological space

A topological space is a pair \((X, τ)\) where \(X\) is a set and \(τ\) is a topology on \(X\).

total function

Given sets \(A\) and \(B\), a total function \(f\) from \(A\) to \(B\) is what we typically mean by a “function” from \(A\) to \(B\).

total order

A total order relation \(R\) on a set \(X\) is a partial order on \(X\) satisfying \(∀ x, y ∈ X \ (x ≤ y \ ⋁ \ y ≤ x)\).

totally bounded

A set \(E\) in a metric space is called totally bounded if for every \(ε > 0\) \(E\) can be covered with finitely many balls of radius \(ε\).

transitive

A binary relation \(R\) on a set \(X\) is called transitive provided \(∀ x, y, z ∈ X \ (x \mathrel{R} y ∧ y \mathrel{R} z\ → \ x \mathrel{R} z)\).

translation invariance

Let \((X, 𝔐)\) be a measurable space. Assume there is a binary operation defined on \(X\); e.g., addition \(+: X× X → X\). A measure \(μ\) on \((X, 𝔐)\) is called translation invariant provided \(μ(E + x) = μ E\) holds for all \(E ∈ 𝔐\) and all \(x∈ X\), where \(E+x := \{e+x ∣ e∈ E\}\).

triangle inequality

Let \((X, \|\,⋅\,\|)\) be a metric or normed space. The inequality \(\|x + y\| ≤ \|x\| + \|y\|\), which holds for all \(x, y ∈ X\) in a metric or normed space, is called the triangle inequality. Equivalently (setting \(x = a-b\) and \(y = b-c\)), \(\|a - c\| ≤ \|a - b\| + \|b - c\|\).

type theory

Type theory internalizes the interpretation of intuitionistic logic proposed by Brouwer, Heyting, and Kolmogorov—the so-called BHK interpretation. The types in type theory play a similar role to that of sets in set theory but functions definable in type theory are always computable.

(See also ncatlab.org/type+theory.)

unary operation

An operation \(f\) on a set \(A\) is called unary if the arity of \(f\) is 1; that is, \(f: A → A\).

underlying set functor

The underlying set functor of \(𝐌\) is denoted by \(U(𝐌)\), or by \(|𝐌|\); it returns the universe of the structure \(𝐌\), and for each morphism \(f\), \(Uf\) (or \(|f|\)) is \(f\) viewed simply as a function on sets.

uniformly continuous

Let \((X, |\, |_X)\) and \((Y, |\, |_Y)\) be metric spaces. A function \(f : X → Y\) is called uniformly continuous in \(E ⊆ X\) if

\[(∀ ε >0)\, (∃ δ >0)\, (∀ x, x_0 ∈ E) \, (|x - x_0| < δ \, ⟹ \, |f(x) -f(x_0)| < ε).\]

unit

If \(⟨R, \{0, 1, -, +, ⋅\}⟩\) is a unital ring, an element \(r ∈ R\) is called a unit if it has a multiplicative inverse, that is, there exists \(s ∈ R\) with \(r ⋅ s = 1 = s ⋅ r\). (We usually denote such an \(s\) by \(r^{-1}\).)

unital ring

See ring with unity.

unitary operator

A unitary operator (or unitary map) is an isomorphism in the category of Hilbert spaces.

Explicitly, if \(ℋ_1\) and \(ℋ_2\) are Hilbert spaces with inner products \(⟨\,.\,,\,.\,⟩_1\) and \(⟨\,.\,,\,.\,⟩_2\) (reps.), then a unitary operator from \(ℋ_1\) to \(ℋ_2\) is an invertible linear transformation \(U: ℋ_1 → ℋ_2\) that preserves inner products in the following sense:

\[⟨U x, U y⟩_2 = ⟨x, y⟩_1 \; \text{ for all } x, y ∈ ℋ_1.\]

By taking \(y = x\), we have \(\|U x\|_2 = \|x\|_1\).

universal image functor

the functor \(∀ f : P(A) → P(B)\) defined by \(∀ f (X) = \{y ∈ B : f^{-1}(\{y\}) \subseteq X\}\), for \(X ∈ P(A)\).

universal mapping property

Let \(η_A : A → |𝔸^*|\) be the function that maps \(a ∈ A\) to the “one-letter word” \(a ∈ A^*\). The functors \(K (= \ ^∗)\) and \(U (= |\ |)\) are related by the universal mapping property of monoids, which says that for every monoid \(𝐌\) and every function \(f : A → U 𝐌\) there exists a unique morphism \(f̂ : KA → 𝐌\) such that \(f = f̂ ∘ η\).

universal property

The unique morphism property of the initial object in a category is what we refer to as a universal property, and we say that the free object in a category \(𝒞\) is “universal” for the category \(𝒞\).

universe

In type theory, everything has a type—even a type has a type. If α is a type, then α’s type is Type u for some universe u. More accurately, the u here is actually a variable and whatever (natural number) value it takes on will be the universe level of the type α.

In universal algebra, the universe of an algebra is the set on which an algebra is defined; e.g., the universe of the algebra \(𝔸 = ⟨A, F^𝔸⟩\) is \(A\). (N.B. we sometimes use the word carrier to mean universe in this sense, which can be helpful when we wish to avoid confusion with the universe levels in type theory.)

unique morphism property

See universal property.

upper limit

Let \(\{a_n\}\) be a sequence in \([-∞, ∞]\), and put \(b_k = \sup \{a_k, a_{k+1}, \dots\}\) for \(k∈ ℕ\) and \(β = \inf \{b_0, b_1, b_2, \dots \}\). We call \(β\) the upper limit (or limit superior) of \(\{a_n\}\), and write \(β = \limsup\limits_{n→ ∞} a_n\). The lower limit, \(\liminf\limits_{n→ \infty} a_n\) is definied similarly.

Observe that

1. \(b_0 ≥ b_1 ≥ b_2 ≥ \cdots ≥ β\) and \(b_k → β\) as \(k→ ∞\);

2. there is a subsequence \(\{a_{n_j}\}\) of \(\{a_n\}\) that converges to \(β\) as \(j→ ∞\) and \(β\) is the largest number with this property.

3. \(\liminf\limits_{n→∞} a_n = -\limsup\limits_{n→∞} (- a_n)\).

Suppose \(\{f_n\}\) is a sequence of extended real-valued functions on a set \(X\). Then \(\sup\limits_n f_n\) and \(\limsup\limits_{n→∞}f_n\) are the functions that are defined for each \(x∈ X\) by

\[\left(\sup\limits_n f_n\right)(x) = \sup\limits_n (f_n(x)), \quad \left(\limsup\limits_n f_n\right)(x) = \limsup\limits_n (f_n(x)).\]

valuation

The absolute value for real numbers can generalised to an arbitrary field by considering the four fundamental properties of absolute value. Thus, a real-valued function \(ν\) on a field \(F\) is called a valuation if it satisfies the following four axioms:

1. \(ν(a)≥ 0\) (non-negativity);

2. \(ν(a)=0 \; ⟺ \; a= \mathbf 0\) (positive-definiteness);

3. \(ν(ab)=ν(a)ν(b)\) (multiplicativity);

4. \(ν(a+b)≤ ν(a)+v(b)\) (subadditivity).

Here \(\mathbf 0\) denotes the additive identity element of \(F\). It follows from properties 2 and 3 that \(ν(1) = \mathbf 1\), where \(\mathbf 1\) denotes the multiplicative identity element of \(F\). The real and complex absolute values are examples of valuations.

variety

A variety (or equational class) of structures in the language \(L\) is one that can be axiomatized by a set of equations in \(L\).

vector space

If \(F\) is a field, then an \(F\)-module is called a vector space over \(F\).

---

Footnotes

1

The range of a complex measure is a subset of \(ℂ\), while a positive measure takes values in \([0,∞]\). Thus the positive measures do not form a subclass of the complex measures.

2

See Rudin [Rud87] 1.35-6 for a nice discussion of the role played by sets of measure 0. To summarize that discussion, it may happen that there is a set \(N ∈ 𝔐\) of measure 0 that has a subset \(E ⊆ N\) which is not a member of \(𝔐\). Of course, we’d like all subsets of measure 0 to be measurable and have measure 0. It turns out that in such cases we can extend \(𝔐\) to include the offending subsets, assigning such subsets measure 0, and the resulting extension will remain a \(σ\)-algebra. In other words, we can always complete a measure space so that all subsets of negligible sets are measurable and negligible.

3

The use of this term is not quite standardized; some (e.g., Rudin [Rud87]) call any open set containing \(p\) a “neighborhood of \(p\)”.

4

This notation is not completely standard. In [AB98] (page 154) for example, \(𝔐 ⊗ 𝔑\) denotes what we call \(𝔐 × 𝔑\), while \(σ(𝔐 ⊗ 𝔑)\) denotes what we have labeled \(𝔐 ⊗ 𝔑\). At the opposite extreme, Rudin (in [Rud87]) simply takes \(𝔐 × 𝔑\) to be the σ-algebra generated by the sets \(\{A × B ∣ A ∈ 𝔐, B ∈ 𝔑\}\).

---

---

Complex Analysis Exams

Please email comments, suggestions, and corrections to williamdemeo@gmail.com