March 12, 2025
Everything in math is a set. We write a\in A to indicate a is an element, or member, of A. The set of function from A to B is the set exponential B^A = \{f\colon A\to B\}. A function is a set defined by its graph \{(a,f(a))\mid a\in A\} contained in the cartesion product A\times B. Kazimierz Kuratowski improved Norbert Wiener’s definition of an ordered pair (a,b)\in A\times B as the set \{a,\{a,b\}\}.
Exercise. Show \cap\{a,\{a,b\}\} = \{a\} and \cup\{a,\{a,b\}\} = \{a,b\}.
Hint For any set A, \cap A is the intersection \cap\{x\mid x\in A\}; x belongs to \cap A if and only if x is a member of every element of A. For any set A, \cup A is the union \cup\{x\mid x\in A\}; x belongs to \cup A if and only if x is a member of some element of A.
The intersection identifies the first item of the pair. If the union is a singleton, a set containing only one element, then the second item is equal to the first item, otherwise we remove the first item to identify the second item.
Functions f\colon A\to B and g\colon B\to C can be composed. The composition of f and g is g\circ f\colon A\to C defined by g\circ f(a) = g(f(a)), a\in A. We also write gf for g\circ f.
Exercise. If in additon h\colon C\to D show h(gf) = (hg)f.
Function composition is associative. Every set has an identity function 1_A\colon A\to A defined by 1_A(a) = a, a\in A.
Exercise. If f\colon A\to B show f1_A = f and 1_B f = f.
A function f\colon A\to B is one-to-one, or injective, if f(a) = f(a') implies a = a', a,a'\in A. A function is onto, or surjective, if for every b\in B there exists an a\in A with f(a) = b. A function is a one-to-one correspondence, or bijective, if it is one-to-one and onto. Two finite sets are the same size if they have the same number of elements. Bijections classify possibly infinite sets by cardinality.
We can define one-to-one and onto using only functions.
Exercise. Show f\colon A\to B is one-to-one if and only if fg = fh implies g = h for g,h\colon C\to A.
Hint: fg = fh if and only if f(g(c)) = f(h(c)) for all c\in C.
Exercise. Show f\colon A\to B is one-to-one if and only if it has a left inverse.
Hint: A left inverse is a function f^\dashv\colon B\to A with f^\dashv f = 1_A.
Exercise. Show f\colon A\to B is onto if and only if gf = hf implies g = h for g,h\colon B\to C.
Hint: gf = hf if and only if g(f(a)) = h(f(a)) for all a\in A. For all b\in B there exists a\in A with f(a) = b.
Exercise. Show f\colon A\to B is onto if and only if it has a right inverse.
Hint: A right inverse is a function f^\vdash\colon B\to A with ff^\vdash = 1_B.
Not everything in math is a set. There is an alternate foundation of mathematics called category theory involving objects and arrows having an associative composition and identity arrows for each object. The above exercises show sets and functions are objects and arrows for the category \mathbf{Set}.
We will not give a rigorous definition of what a category is, but we will lean heavily on what Samuel Eilenberg and Saunders Mac Lane invented to unify many proofs from diverse areas of mathematics prior to the mid 20-th century.
It is possible to define an ordered pair using only functions. Define projections \pi_A\colon A\times B\to A by \pi_A(a,b) = a and \pi_B\colon A\times B\to B by \pi_B(a,b) = b.
Exercise. If f\colon C\to A and g\colon C\to B show there exists h\colon C\to A\times B with \pi_A h = f and \pi_B h = g.
Hint: Of course h(c) = (f(c), g(c)), c\in C.
This characterizes the cartesian product A\times B. Let P be any set with functions p_A\colon P\to A, p_B\colon P\to B with the property in the previous exercise, then P is in one-to-one correspondence with A\times B.
Exercise. Show any such P is in one-to-one correspondence with A\times B.
Set product and exponential are connected by currying. Functions from A\times B to C are in one-to-one correspondence with functions from A to functions from B to C. If f\colon A\times B\to C define f,\colon A\to(B\to C) by f,a(b) = f(a,b). If g\colon A\to(B\to C) define g`\colon A\times B\to C by g`(a,b) = ga(b).
Exercise. If f\colon A\times B\to C show (f,)` = f and if g\colon A\to(B\to C) show (g`), = g.
Evaluation of a function is defined by \operatorname{eval}= \operatorname{eval}_A^B\colon A^B\times B\to A with \operatorname{eval}(f,b) = f(a).
Exercise. !!!connect currying and eval!!!
Our theme is to define everything in terms of sets and functions with an eye toward computer implementation. Every programming language allows you to define functions and call them on types belonging to a set. We provide mathematical names that can be translated into any computer language.
There are two ways to think about \boldsymbol{{{R}}}^n, one is as a set of tuples, the other is as a set of functions. These two perspectives are a source of confusion and insight.
An impoverished notion of a vector is that it is a tuple of real numbers {x = (x_1,\ldots,x_n)}. Given a natural number n\in\boldsymbol{{N}}, let {\boldsymbol{{{R}}}^n = \{(x_1,\ldots,x_n)\mid x_i\in\boldsymbol{{{R}}}, 1\le i\le n\} = \prod_{1\le i\le n}\boldsymbol{{{R}}}} be the cartesian product of n\in\boldsymbol{{N}} copies of the real numbers. If bold {\boldsymbol{{n}}} is the set {\{1,\ldots,n\}} then {i\in\boldsymbol{{n}}} is a shorter notation for {1\le i\le n}. We can identify \boldsymbol{{{R}}}^n with \boldsymbol{{{R}}}^{\boldsymbol{{n}}} where the tuple {(x_i)_{i\in\boldsymbol{{n}}}} corresponds to the function \boldsymbol{{x}}\colon\boldsymbol{{n}}\to\boldsymbol{{{R}}} defined by \boldsymbol{{x}}(i) = x_i, i\in\boldsymbol{{n}}.
Exercise. Show \prod_{i\in\boldsymbol{{n}}}\boldsymbol{{{R}}} is in one-to-one correspondence with \boldsymbol{{{R}}}^{\boldsymbol{{n}}}.
Hint: If {\pi_i\colon\prod_{i\in\boldsymbol{{n}}}\boldsymbol{{{R}}}\to\boldsymbol{{{R}}}} are the projections \pi_i(x) = x_i, i\in I define x\mapsto\boldsymbol{{x}} by \boldsymbol{{x}}(i) = \pi_i(x) and show it is bijective.
A more powerful notion is to consider a vector as an element of the vector space of all functions from an index set I to the real numbers, \boldsymbol{{{R}}}^I. The tuple x = (x_i)_{i\in I} in \prod_{i\in I}\boldsymbol{{{R}}} corresponds to a function {\boldsymbol{{x}}\colon I\to\boldsymbol{{{R}}}} in \boldsymbol{{{R}}}^I defined by \boldsymbol{{x}}(i) = x_i, i\in I. In what follows we just write x for \boldsymbol{{x}} and leave it to you to figure out from context if a vector is a tuple or a function.
Exercise. For any set I, show \prod_{i\in I}\boldsymbol{{{R}}} is in one-to-one correspondence with \boldsymbol{{{R}}}^{I}.
Hint: If \pi_i\colon \prod_{i\in I}\boldsymbol{{{R}}}\to\boldsymbol{{{R}}} are the projections defining the product then \boldsymbol{{x}}(i) = \pi_i(x).
I -> (Pi_i R -> R)
Scalar multiplication and vector addition on \boldsymbol{{{R}}}^I are defined pointwise by {(ax)(i) = a(x(i))} and {(x + y)(i) = x(i) + y(i)}, a\in\boldsymbol{{{R}}}, x,y\in\boldsymbol{{{R}}}^I.
For any set I, a,b\in\boldsymbol{{{R}}}, and x, y, z\in\boldsymbol{{{R}}}^I show the following:
Exercise. x + (y + z) = (x + y) + z.
Exercise. x + y = y + x.
Exercise. \boldsymbol{{0}}+ x = x where \boldsymbol{{0}}(i) = 0, i\in I.
Exercise. x + (-x) = \boldsymbol{{0}} where (-x)(i) = -(x(i)), for i\in I.
Exercise. a(bx) = (ab)x.
Exercise. 1x = x.
Exercise. a(x + y) = ax + ay.
Exercise. (a + b)x = ax + bx.
Hint: Use the pointwise definitions and the properties of real numbers.
The exercises are the axioms for an abstract vector space with scalar multiplication {\boldsymbol{{{R}}}\times V\to V} where {(a,x)\mapsto ax = xa} and binary addition {V\times V\to V} where {(x,y)\mapsto x + y}. The first four axioms show vector addition is an abelian (commutative) group. The last two axioms are the distributive laws connecting scalar multiplication and vector addition. Every abstract vector space can be represented by \boldsymbol{{{R}}}^I for some set I, but this is not a trivial result.
Proofs involving only the abstract axioms are considered more elegant.
If x\in\boldsymbol{{{R}}}^I then (0x)(i) = 0(x(i)) = 0 and (1x)(i) = 1(x(i)) = x(i) for all i\in I so 0x = \boldsymbol{{0}} and 1x = x. These hold for any vector space, not just \boldsymbol{{{R}}}^I.
Exercise. (Zero is unique) Show if \boldsymbol{{0}}' + v = v for all v\in V then 0' = 0.
Hint: \boldsymbol{{0}}+ v = v so \boldsymbol{{0}}' + v = \boldsymbol{{0}}+ v. Add -v to both sides.
Exercise. Show 0v = \boldsymbol{{0}} for all v\in V.
Hint: Show 0v + v = v and use the previous exercise.
Exercise. For any vector space V show {v + v = v} implies {v = \boldsymbol{{0}}} for all {v\in V}.
This may seem to be a tedoious way to prove an obvious result, but it is a simple example of the power of mathematics. Unlike other areas of human endeavour, whenever two mathematicians disagree it is possible to get to the bottom of things.
The standard basis of \boldsymbol{{{R}}}^n is {e_i\in\boldsymbol{{{R}}}^n}, {i\in\boldsymbol{{n}}}, where {e_i = (0,\ldots,1,\ldots,0)} with all elements 0 except for a 1 in the i-th position. It is plausible that {x = (x_1,\ldots,x_n) = x_1 e_1 + \cdots + x_n e_n} for {x\in\boldsymbol{{{R}}}^n}, but you should always be wary of definitions involving dots.
More generally, the standard basis of \boldsymbol{{{R}}}^I is {e_i\in\boldsymbol{{{R}}}^I}, {i\in I}, where {e_i(j) = \delta_{ij}} for j\in I, where \delta_{ij} is the Kronecker delta defined by {δ_{ij} = 1} if {i=j} and {δ_{ij} = 0} if {i\not=j}. We write e^I_j to indicate the domain if needed.
Exercise. If I is finite, show x = \sum_{i\in I} x(i)e_i for x\in\boldsymbol{{{R}}}^I.
Hint: Evaluate the putative equality at j\in I.
A vector space homomorphism is a linear operator. A linear operator between vector spaces is a function {T\colon V\to W} that preserves the scalar multiplication and vector addition: T(ax) = aTx and {T(x + y) = Tx + Ty}, {a\in\boldsymbol{{{R}}}}, {x,y\in V}. The collection of all linear operators from V to W is denoted \mathcal{L}(V,W).
Exercise. Show if T\colon V\to W is a function with {T(ax + y) = aTx + y}, {a\in\boldsymbol{{{R}}}}, {x,y\in V} then T is a linear operator.
Hint: Take y = \boldsymbol{{0}} and a = 1.
The collection \mathcal{L}(V,W) can be made into a vector space. Define scalar multiplication by (aT)v = a(Tv) and vector addition by (T + S)v = Tv + Sv, a\in\boldsymbol{{{R}}}, T,S\in\mathcal{L}(V,W). One could check the scalar multiplication and vector addition satisfy the axioms for an abstract vector space but we will show a simple way to establish this once we define matrix.
If T\in\mathcal{L}(\boldsymbol{{{R}}}^I,\boldsymbol{{{R}}}^J) then the image of the i-th standard basis element in \boldsymbol{{{R}}}^I under T can be written Te^I_i = \sum_{j\in J} t_{ij} e^J_j for some scalars t_{ij}\in\boldsymbol{{{R}}} when I and J are finite. The matrix of T is [t_{ij}]_{i\in I, j\in J}.
If S\colon\boldsymbol{{{R}}}^J\to\boldsymbol{{{R}}}^K then U = ST\colon\boldsymbol{{{R}}}^I\to\boldsymbol{{{R}}}^K.
Exercise. Show the matrix of the composition U = ST is {u_{ik} = \sum_{j\in J} s_{ij}t_{jk}}, for i\in I, k\in K.
Matrix multiplication is just composition of linear operators. Define E_{ij}\colon\boldsymbol{{{R}}}^I\to\boldsymbol{{{R}}}^J to be the linear operator with matrix [\delta_{ij}].
Exercise. Show E_{ij}E_{k,l} = \delta_{jk}E__il}.
Werner Heisenberg reinvented matrix multiplication. His interpretation was E_{ij} represented a jump of an electron from orbital level i in a hydrogen atom to orbital level j. He positied E_{ij}E_{kl} was a jump from level i to level l if and only if j = k. Eventually Pascual Jordan pointed this out to him.
This shows linear operators from \boldsymbol{{{R}}}^I to \boldsymbol{{{R}}}^J are in one-to-one correspondence with \boldsymbol{{{R}}}^{I\times J}. Define a function from T\in\mathcal{L}(\boldsymbol{{{R}}}^I,\boldsymbol{{{R}}}^J) to \boldsymbol{{T}}\in\boldsymbol{{{R}}}^{I\times J} by \boldsymbol{{T}}(i,j) = t_{ij} where [t_{ij}] is the matrix of T.
Exercise. Show \mathcal{L}(\boldsymbol{{{R}}}^I,\boldsymbol{{{R}}}^J) is isomorphic to \boldsymbol{{{R}}}^{I\times J}.
Since I\times J is a set, \boldsymbol{{{R}}}^{I\times J} is a vector space. This shows \mathcal{L}(\boldsymbol{{{R}}}^I,\boldsymbol{{{R}}}^J) is a vector space.
The dual of a vector space V is the set of all linear functionals from V to \boldsymbol{{{R}}}, V^* = \mathcal{L}(V,\boldsymbol{{{R}}}). We write the dual pairing \langle v, v^*\rangle = v^*(v) for v\in V, v^*\in V^*.
The standard dual basis of \boldsymbol{{{R}}}^I, e_i^*\colon\boldsymbol{{{R}}}^I\to\boldsymbol{{{R}}} is defined by e_i^*(x) = x(i), i\in I.
Exercise. Show e_i^* is linear for all i\in I.
Exercise. Show \langle e_i, e^*_j\rangle = \delta_{ij}, i,j\in I.
Exercise Show the matrix of T\in\mathcal{L}(\boldsymbol{{{R}}}^I,\boldsymbol{{{R}}}^J) is {t_{ij} = \langle Te_i, e^*j\rangle}, i\in I, j\in J.