Foundations of Mathematics

Wait What is Math?

You’re not going to find an official definition of mathematics that everyone will agree on, but most people agree that it involves reasoning about quantity, change, structure, chance, causality, and space by both (1) finding abstract patterns and (2) creating models.

Math aims to help us both (1) explain real-world phenomena and (2) discover truths that transcend the physical world. It’s such a well-known human activity that Wikipedia has an article on it! Seriously!

Where does it come from?

No one knows for sure, but there’s a great book on the topic that just might have the answer. If you look at the evolution of life and consciousness you might get some ideas. The earliest life forms may have only survived by bumping into food. Natural selection likely led to sensing abilities enabling organisms to move toward the food. Next, lifeforms capable of making “models of their surroundings” so they could swerve around obstacles and remember where the food was gained an evolutionary advantage.

This may explain how everyone can make models, and hence do Math!

Was it invented or discovered?

This question has been asked millions of times. Seriously.

The answer is probably both!

The question is so popular we can even question the question:

Whatever your take on this question is, Math has proven to be unreasonably effective in the natural sciences.

What are some of its branches?

Math is a big field of study. Here’s how Wikipedia breaks it down (this is just one way, and it’s not going to please everyone):

Branch	Topics
Foundations	Philosophy of Mathematics • Mathematical Logic • Information Theory • Set Theory • Type Theory • Category Theory
Algebra	Abstract • Boolean • Clifford • Commutative • Elementary • Field Theory • Group Theory • Homological • Lie • Linear • Multilinear • Ring Theory • Universal
Analysis	Calculus • Real Analysis • Complex Analysis • Hypercomplex Analysis • Differential Equations • Functional Analysis • Harmonic Analysis • Measure Theory
Discrete	Combinatorics • Discrete Geometry • Graph Theory • Matroid Theory • Order Theory
Geometry	Algebraic • Affine • Analytic • Arithmetic • Complex • Computational • Convex • Differential • Discrete • Euclidean • Finite • Information • Projective
Number Theory	Algebraic • Analytic • Arithmetic • Diophantine Geometry
Topology	General • Algebraic • Differential • Geometric • Homotopy Theory • Knot Theory
Applied	Control theory • Operations Research • Probability • Statistics • Game Theory
Computational	Computer Science • Theory of Computation • Computational Complexity • Numerical Analysis • Optimization • Computer Algebra

Another organization of topics can be found at Quanta Magazine’s Map of Mathematics. There’s also a cool Map of Mathematics video by Dominic Walliman, from which this poster can be found:

Foundations

We want to put math on a solid foundation so we know that we are not talking nonsense.

Here’s part of the Wikipedia article on the foundations of mathematics:

Foundations of mathematics are the logical and mathematical frameworks that allow the development of mathematics without generating self-contradictory theories, and to have reliable concepts of theorems, proofs, algorithms, etc. in particular. This may also include the philosophical study of the relation of this framework with reality.

If we can reduce everything down to a few very basic concepts and rules that people can agree upon, then show how to carefully and systematically derive all of mathematics from them, building things up in a way everyone can agree is valid, we can have confidence that mathematics does what it is supposed to do.

Whether you believe philosophically that this is possible or not doesn’t matter for now. What matters is putting in the effort to build a foundation and learning from the effort. Honestly, some fascinating discoveries and useful inventions have come from past work in foundations.

History of Foundations

What we now understand to be the foundations of mathematics today are relatively recent developments, primarily from the late 19th and early 20th centuries. Prior to this time, most of what mathematicians did was just taken for granted. But the the late 1800s and early 1900s saw a rise in inconsistent and contradictory results, paradoxes, and debates about the nature of mathematical truth, leading to what’s now known as the foundational crisis of mathematics.

Several schools of thought emerged to address the foundational crisis. The three main schools were logicism, which aimed to reduce mathematics to logic; formalism, which sought to establish a consistent set of axioms and rules for mathematics; and intuitionism, which emphasized the mental construction of mathematical objects and rejected non-constructive proofs.

Today, this crisis pretty much considered resolved. The new field of mathematical logic was born from work to resolve the crises, as were modern versions of set theory, type theory, and category theory, which provide rigorous foundations for mathematics; as well as practical theories and fields such as proof theory, model theory, computability theory, and complexity theory, as well as the field of computer science itself.

Why Study Foundations?

Good question! Many mathematicians don’t pursue a deep understanding of the foundations of math because they don’t need it in their daily work. But the field turns out to be really useful for computation, theoretical computer science, formal verification of program correctness (used in computer security), and proving complex theorems with the aid of a computer. In other words, it’s important for computer science, particularly in the study of programming languages.

And actually, there is some mind-blowing stuff here.

What is this page about?

This page is a light and incomplete sketch of topics within the area of the foundations of mathematics, with an eye toward showing that mathematical objects (tuples, sets, functions, numbers, and so on) can be rigorously defined and manipulated according to precise rules. The topics here are chosen because they are useful in theoretical computer science.

This page does not cover the foundational theories themselves, but only provides an introduction to the topics they cover. The actual foundations are covered in our upcoming notes on Set Theory and Type Theory.

A Note About Notation

Mathematical reasoning benefits from concise, symbolic notation. It wasn’t always this way—until the 17th century or so math was mainly done in prose. Today we have some widely accepted notation for mathematical ideas, but there is still a surprising amount of variation. In fact, you are free to choose your own notation, as long as you are consistent.

Foundational Theories

There are many theories within mathematics. But there are three kinds of theories that can be viewed as providing a foundation for (all of) math: set theories, type theories, and category theories.

See the Wikipedia page on Foundations of Mathematics and the SEP article on Philosophy of Mathematics for a history of the subject.

Oversimplifying a bit, here’s a bit about these three theories (or technically, theory families):

	Set Theory	Type Theory	Category Theory
Philosophy and Approach	Math is about classification of objects by arranging them in sets. Set theory requires logic (generally a classical one) to already exist.	Math is about manipulating objects according to the types they inhabit. Logic emerges from the theory. Usually constructive in nature (though classical type theories do exist).	Math is about structures and the relationships between them, without worrying about internal details.
Key Features	Sets are built up from smaller sets, with rules to avoid paradoxes. Generally, everything is a set, which is both a strength and a weakness.	Terms have types. Types can depend on other types as well as on terms. Propositions are types. Proofs are programs.	Categories have objects and morphisms (arrows or relationships). Functors map between categories. Commutative diagrams are used a lot.
Concepts	Elements, membership, subsets, power sets, tuples, sequences, partitions, relations, equivalence relations, orders, cardinality.	Types, terms, inductive types, sums ($+$), products ($\times$), dependent types ($\Pi$ and $\Sigma$), propositions as types, proofs as programs, equality types, universes.	Objects, morphisms, functors, natural transformations, limits, colimits, adjunctions, monads, categories, monoids, topoi.
Characteristic Notation	$x \in S$ means $x$ is an element of set $S$.	$x : A$ means the term $x$ is of type $A$.	$X \xrightarrow{f} Y$ means $f$ is a morphism from category $X$ to category $Y$.
Applications	Used everywhere—most mathematicians are familiar with much of it.	Computer science, formal verification, proof assistants.	Abstract algebra, topology, geometry, mathematical logic.
Exemplars	Some set theories are: ZF and ZFC, NBG, NF and NFU, MK, KP, CST.	Some type theories are: Simply-Typed $\lambda$ calculus, MLTT, System F, DTT, CoC, HoTT.	Some category theories are: ETCS, Topos Theory, Abelian, Monoidal.

Math and Logic

Math and logic are related, but not the same thing. Mathematicians do quite a lot of logic. If interested, I have more extensive notes that get into logic in more detail, with coverage of non-bivalent, intuitionistic, paraconsistent, fuzzy, non-monotonic, and a bunch of other types of logic. They get into metalogical notions of soundness and completeness, too.

Mathematical Objects

Mathematics is concerned with objects and the relationships between them. Before creating a foundational theory, we should take an inventory of the kinds of things that humans work with in mathematics. Then we can start to think about how all of the objects can be encoded with primitive notions. In no particular order, here’s an incomplete sampling of useful mathematical objects:

Booleans Numbers Tuples Sets Relations Functions Sequences Lists Characters Strings Maps Graphs Vectors Matrices Tensors

Let’s visit the basic ideas behind some of these objects.

Booleans

The boolean objects are $\textsf{true}$ and $\textsf{false}$. They obey several laws, including:

Numbers

Numbers are so useful. We use them to count, measure, order, compare, and so much more.

Some people love numbers. Some numbers have a lot of fascinating properties. Some are interesting philosophically and recreationally. If you like numbers, or even if you think you don’t, browse Robert Munafo’s pages on notable numbers. You’ll probably like it!

Kinds of Numbers

Numbers are classified by how we use them. Here is a small sampling:

Type	Concept	What it tells us
Cardinal Numbers	Quantity	How many discrete items
Ordinal Numbers	Sequence	The position of something in an ordering
Scalar Numbers	Magnitude	How much (continuous quantity) of something there is
Coordinate Numbers	Location	Numbers that represent a position in space
Vector Numbers	Direction and Magnitude	Which way and how far
Nominal Numbers	Identification	A convenient label

Here is another way to classify numbers:

Kind	Symbol	Informal Description
Natural Numbers	$\mathbb{N}$	$\{0, 1, 2, 3, \ldots\}$
Integers	$\mathbb{Z}$	$\{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}$
Rational Numbers	$\mathbb{Q}$	$\{\frac{a}{b} \mid a, b \in \mathbb{Z} \land b \neq 0\}$
Real Numbers	$\mathbb{R}$	(See the Wikipedia article)
Complex Numbers	$\mathbb{C}$	Has 2 real components, written ($a+bi$)
Quaternions	$\mathbb{H}$	Has 4 real components, written ($a+bi+cj+dk$)
Octonions	$\mathbb{O}$	8 real components, with units $e_0 ... e_7$
Sedenions	$\mathbb{S}$	16 real components

There are more! Did you know about algebraic vs. transcendental numbers? This amazing diagram by Keith Enevoldsen shows how they fit in (up to the complex numbers, at least):

We can even slip in a couple more categories, Computable and Describable, which are very useful in computer science theory. Here is where they land in the real numbers hierarchy:

That’s right! There are real numbers that we can describe but not compute. There are real numbers that exist but that we can’t even describe. This makes computer science (and math) interesting. How we know that we have proper containment at each level of this hierarchy is a little beyond the scope of these notes, but something you should research and internalize at some point.

$\Omega$

The number $\Omega$ in the diagram above is Chaitin’s constant, a number we can describe but not compute. It’s not the same $\Omega$ as the mathematically inconsistent, self-contradictory “absolute infinity” from the Vi Hart video later in these notes.

Things get interesting when you go beyond the reals. What isn’t “real” by the way? Imaginary perhaps? Not a good name, as Jade shows:

Perhaps if they got a better name, the video would have had a different title.

Operations

Before we get to foundational definitions of numbers, let’s look at some basic operations we can perform with them (informally, of course).

For natural numbers:

• Addition: $x^{(1)}y = x + y = \underbrace{\:s\: \ldots \:s\:}_{y}\;x$
• Multiplication: $x^{(2)}y = x \times y = \underbrace{\:x + x + \ldots + x\:}_{y}$
• Exponentiation: $x^{(3)}y = x \uparrow y = \underbrace{\:x \times x \times \ldots \times x\:}_{y}$
• Tetration: $x^{(4)}y = x \uparrow\uparrow y = \underbrace{\:x \uparrow x \uparrow \ldots \uparrow x\:}_{y}$ (also called hyper4 or power-tower)
• Pentation: $x^{(5)}y = x \uparrow\uparrow\uparrow y = \underbrace{\:x \uparrow\uparrow x \uparrow\uparrow \ldots \uparrow\uparrow x\:}_{y}$
• And on and on....

Addition, multiplication, and exponentiation work for real numbers too. There are also inverses:

• Subtraction: $x - y$ = the $z$ such that $y + z = x$
• Division: $x \div y$ = the $z$ such that $y \times z = x$
• Logarithm: $\log_y(x)$ = the $z$ such that $y^z = x$
• And there are “inverses” of the operators beyond exponentiation as well

Got all that? Do you have a good sense of these numbers and operations? You should. Being numerically literate, with a good feel for numbers gives you agency in the world, become less likely to be taken advantage of, and helps you become a better citizen. Watch Vi Hart’s piece which should give you a feel for what having feels about numbers entails:

Also important:

• The floor of a real number $x$, denoted $\lfloor x \rfloor$, is the largest integer less than or equal to $x$.
• The ceiling of a real number $x$, denoted $\lceil x \rceil$, is the smallest integer greater than or equal to $x$.

In computer science, integers, rationals, and reals are often compressed into fixed size registers, yielding classes of bounded numbers. You can study these in more depth in the notes on Numbers and Numeric Encoding.

Big Numbers

Robert Munafo has another catalog of numbers, his Large Numbers pages, which you absolutely don’t want to miss. It includes not only large numbers, but the transfinite ordinals.

Seriously, don’t miss it!

Have ten hours to spare? This will take you through large finite numbers only, but in doing so, will give you a sense that thinking that infinity is not a big deal isn’t really accurate. Though easy to describe, it’s so far beyond direct experience. You just can’t.

If you want to become immersed and well-versed in this stuff, start at the Googology Wiki. Have fun!

One small nit

This video seems to suggest that infinity is a number, which isn’t really accurate. Infinity is not a number, but there are numbers that represent infinities in various mathematical contexts.

Infinities

There are not only so many kinds of numbers but there are even many kinds of transfinite numbers. Perhaps you encountered a few of these already in Robert Munafo’s Large Numbers pages. Whether you have or have not, Vsauce gives a careful explanation of cardinals (“how many”) and ordinals (“position of”) that really helps!

Vsauce does not go far enough. Vi Hart takes us much, much further:

So many types of numbers in this video: cardinals in set theory, surreals in game theory, supernaturals in field theory, ordinal spaces in topology, Hilbert spaces in analysis and quantum physics, and more.

Many of the infinities are best understood in the context of set theory. So we’ll defer a proper treatment of cardinals and ordinals to our upcoming notes on Set Theory.

Pairs

A pair, also called an ordered pair, literally an object $(a, b)$ where $a$ is the first element and $b$ is the second element. The order of the elements matters, meaning that the pair $(a, b)$ is only the same as the pair $(b, a)$ when $a = b$.

Pairs are a fundamental building block for more complex structures.

Tuples

A tuple is an object such as $(21,F)$, $(a,a,b,a,b,a,b,b)$, or $(do, re, mi, fa, so, la, ti, do)$. The elements of a tuple are ordered. Given a tuple $t$, you access the $i$th element with the notation $\:t\!\downarrow\!i$.

In both Set Theory and Type Theory, tuples are built from pairs so that the 3-tuple $(a, b, c)$ sugars $(a, (b, c))$, and a the 4-tuple $(a, b, c, d)$ can be represented as $(a, (b, (c, d)))$, and so on.

We can speak of $1$-tuples and $0$-tuples, too. The convention is $a = (a)$ for a $1$-tuple and the $0$-tuple is simply $()$.

Tuples can be concatenated. If $t_1$ is an $m$-tuple and $t_2$ is an $n$-tuple then $t_1 • t_2$ is an $(m+n)$-tuple:

$$(a_1, \ldots, a_m) • (b_1, \ldots, b_n) = (a_1, \ldots, a_m, b_1, \ldots, b_n)$$

We will allow the concatenation operator to work with $0$-tuples and $1$-tuples as well, so $(a,b) • c = (a,b,c)$, $a • b = (a,b)$, and $a • () = a$.

Sets

A set, in practice, is an unordered collection of unique elements. We denote sets by enumerating their elements or using a filtering notation to select certain elements from an existing set. Depending on context, we can sometimes get quite informal and use prose, as long as the precise meaning can be recovered exactly and uniquely.

Crisp and Fuzzy Sets

What does it mean to be a member? It can vary.

• For crisp sets, you’re either in or you’re out. No in-between. This is the most common kind of set.
• For fuzzy sets, membership can be partial. For example, you might be 0.8 in the set of tall people.

These notes will only cover crisp sets.

The fundamental operation on sets is membership ($\in$). But a lot of additional notation exists. The fundamental notions are:

According to Set Theory, the following sets and operators are defined by axioms of the theory:

From those axioms, we can define new concepts and ideas:

AMBIGUOUS NOTATION ALERT

The notation $A^n$ is horribly overloaded! When $A$ is a plain old set, the notation indicates tuple construction. When $A$ is a relation, the notation indicates repeated composition of the relation with itself. When $A$ is an alphabet, the notation indicates the set of strings with a given length. When $A$ is a language, the notation indicates sets of strings made by concatenating strings from $A$ a given number of times.

In each of these cases, the value of $A^n$ is completely different!

Context is crucial to understanding the meaning. Ambiguity is very common in math.

Assuming you already know first-order classical logic, you can use the definitions above to prove some interesting theorems about sets. The following are theorems in any of the major set theories (ZFC, NFU, etc.), with all free variables implicitly universally quantified:

Relations

When we say “5 is less than 8” we are expressing a relation between two numbers. You can probably think of many more, For numbers, there is $\leq$, $\gt$, and $\geq$. For sets, there is $\subseteq$. The relation $=$ is defined for every kind of object, it seems.

Relations are highly intertwined with Set Theory. Relations are actually defined as sets of ordered pairs, i.e., a relation $R$ between sets $A$ and $B$ is a subset of $A \times B$. There are a lot of details here, so we are going to defer a full discussion until our coverage of that topic.

Functions

A function maps an input to an output, such that given any input (called the argument), you get the same output every time you apply the function.

In Type Theory, a function maps every inhabitant of the input type, called the domain to a value in the output type, called the codomain. If a function $f$ has domain $t_1$ and codomain $t_2$, then $f$ inhabits the type $t_1 \to t_2$. To apply or invoke the function $f$ on argument $a$, we write $f\,a$ or $f(a)$. To represent a function explicitly, we write:

$$\lambda x_t. e$$

where $x$ is the argument of the function, $t$ is the type of the argument, and $e$ is the expression that computes the output based on $x$. Usually the output type is inferrable, but if it is not, writing $(\lambda x. e)\!: t_1\to t_2$ is totally fine.

In Set Theory, functions are actually sets, so we write $f \in A \to B$ to denote a function, where the function maps elements from the set $A$ to the set $B$.

The restriction of the domain and codomain to particular sets or particular types is something common in the foundations of mathematics. Allowing functions to operate on anything whatsoever can give you a version of Russell's Paradox, which leads to inconsistencies.

We often give names to functions, for example:

$$ \textsf{plusTwo} =_{\small{\textrm{def}}} \lambda x_{\textsf{Nat}}. \textsf{s}\,\textsf{s}\,n$$ $$ \textsf{isZero} =_{\small{\textrm{def}}} \lambda x_{\textsf{Nat}}. x = 0$$

We can create functions for any operation we like, such as $\textsf{and}$ for logical conjunction, $\textsf{or}$ for logical disjunction, $\textsf{not}$ for logical negation, $\textsf{plus}$ for addition, $\textsf{times}$ for multiplication, and $\textsf{exp}$ for exponentiation, and define different versions of these for different numeric types. Relations can be defined as functions whose codomain is the boolean type (or set):

$\begin{array}{l} \textsf{lt}\!: \textsf{Nat} \rightarrow \textsf{Nat} \rightarrow \textsf{Bool} =_{\small{\textrm{def}}} \\ \quad \lambda x_{\textsf{Nat}}. \lambda y_{\textsf{Nat}}. \exists k_{\textsf{Nat}}.\, k \neq 0 \land x + k = y \end{array}$

And here is something remarkably useful:

$\begin{array}{l} \textsf{cond}\!: \textsf{Bool} \rightarrow t \rightarrow t \rightarrow t =_{\small{\textrm{def}}} \\ \quad \lambda b_{\textsf{Bool}}. \lambda x. \lambda y. \textsf{match}\;b \\ \quad \quad \textsf{when}\;\textsf{true} \rightarrow x \\ \quad \quad \textsf{when}\;\textsf{false} \rightarrow y \end{array}$

Polymorphism

The $\textsf{cond}$ function we defined above is an example of a polymorphic function. It can operate on any type $t$, not just a specific type like $\textsf{Nat}$ or $\textsf{Bool}$. This is powerful. Many programming languages make use of this idea.

The word comes from the Greek words poly meaning many and morph meaning form.

In the foundations of mathematics, we can consider all operations to be functions, and sugar various function calls. Here are some conventional sugarings:

$\begin{array}{lll} \neg b & \text{for} & \textsf{not}\;b \\ a \land b & \text{for} & \textsf{and}\;a\;b \\ a \lor b & \text{for} & \textsf{or}\;a\;b \\ \textsf{if}\;b\;\textsf{then}\;x\;\textsf{else}\;y & \text{for} & \textsf{cond}\;b\;x\;y \\ n + 1 & \text{for} & \textsf{s}\;n \\ m + n & \text{for} & \textsf{plus}\;n\;m \\ m \times n & \text{for} & \textsf{times}\;n\;m \\ m^n & \text{for} & \textsf{exp}\;n\;m \\ n \lt m & \text{for} & \textsf{lt}\;n\;m \\ \textsf{let}\;x = e\;\textsf{in}\;e' & \text{for} & (\lambda x.\,e')\;e \end{array}$

Heck we’ll even write $xy$ for $x \times y$ except when it makes things too confusing.

Overloading

You might notice that some symbols and operators, like $+$, $\times$, and so on will be used across multiple arithmetic types, and perhaps on nonarithmetic types too. While such cases represent fundamentally distinct functions, we’ll happily overload the symbols and rely on context to suss out which specific function is meant.

A few forms make $\lambda$-expressions easier to read. The first is the amazing let-notation that we saw earlier, but did not really dive into. Here it is again, because it is so useful and is used all the time:

• For example: $\;\mathsf{let}\;x=3\;\mathsf{in}\;x+5$ evaluates to $8$
• Because: $\;\mathsf{let}\;x=3\;\mathsf{in}\;x+5$ is the same as $(\lambda x . x+5)(3)$
• In general: $\;\mathsf{let}\;x=e\;\mathsf{in}\;e'$ is the same as $(\lambda x . e')(e)$

Where-notation is a close relative of let-notation:

• For example: $\;x+5\;\mathsf{where}\;x=3$ evaluates to $8$
• Because: $\;x+5\;\mathsf{where}\;x=3$ is the same as $(\lambda x . x+5)(3)$
• In general: $\;e'\;\mathsf{where}\;x=e$ is the same as $(\lambda x . e')(e)$

If-notation:

• $\mathsf{if}\;b\;\mathsf{then}\;x\;\mathsf{else}\;y = \textsf{cond}\;b\;x\;y$

Equivalently:

• $\mathsf{if}\;b\;\mathsf{then}\;x\;\mathsf{else}\;y = \begin{cases} x & b = \textsf{true} \\ y & b = \textsf{false}\end{cases}$

Substitution:

• $f[a \mapsto b] = \lambda x. \mathsf{if}\;x=a\;\mathsf{then}\;b\;\mathsf{else}\;f(x)$

Function iteration:

• $f^0(x) = x$
• $f^1(x) = f(x)$
• $f^2(x) = f(f(x))$
• $f^3(x) = f(f(f(x)))$
• ...
• $f^{n+1}(x) = f(f^n(x))$

AMBIGUOUS NOTATION ALERT

Many mathematicians purposefully blur the distinction between $\sin^2\theta$ and $(\sin \theta)^2$, leaving you, the poor reader, to figure out what they mean by context. It can be very annoying.

It appears that for trigonometric functions, people tend to use the iterative form for the power form, but for other functions the iterative form usually means iteration. Maybe?

Don’t worry too much. It’s all a consequence of the fact that everyone is allowed to invent their own notation. Just remember, all things are contextual.

AMBIGUOUS LANGUAGE ALERT

If $f$ is a function, do not say “the function $f(x)$” unless the function $f$, when applied to $x$, actually yields a function. Also do not say things like “the function $n^2$” because $n^2$ is a number. The function you probably have in mind is $\lambda n. n^2$. That doesn’t stop people from abusing the notation, though.

Mathematics is often about communicating ideas, not about absolute precision. Confusing people is part of the fun of math, it seems. Context matters. When something is ambiguous, ask about it.

Sequences

A sequence is an ordering of elements indexed by natural numbers, and written $\langle a_0, a_1, a_2, \dots, a_{n-1} \rangle$. The length of the sequence is $n$. The common operation is to lookup elements by position. It is common to think of the sequence as a partial function from natural numbers to sequence elements.

Both the set-theoretic and type-theoretic encodings of sequences are fascinating. They will be covered later in the course.

Lists

A list is defined inductively like this:

• The empty list $[\,]$ is a list.
• If $x$ is an element and $y$ is a list, then $(x :: y)$ is a list.

This means a list is an ordered collection of elements. This shows in the conventional notation: We write ${[x]}$ for $(x\,\textbf{::}\,[\,])$, ${[x,y,z]}$ for $(x\,\textbf{::}\,(y\,\textbf{::}\,(z\,\textbf{::}\,[\,])))$, and so on.

Lists are particularly useful in mathematics and computer science, and appear in nearly every mainstream programming language. Several dozen useful lists operations are known, among them:

• head: Returns the first element of the list (a partial function).
• tail: Returns the list without the first element (a partial function).
• append: Adds an element to the end of the list.
• length: Returns the number of elements in the list.
• map: Applies a function to each element of the list.
• filter: Returns a list of elements that satisfy a predicate.

Characters

A character is a primitive unit of textual information. In practice, we create sets of characters called alphabets.

The most common alphabet in the world today is Unicode. Characters in Unicode have both a code point (a unique natural number identifying the character) and a name, such as U+0041 LATIN CAPITAL LETTER A.

The science of characters is quite vast. You can learn by browsing the resources available through Unicode.org, or, for a computer science approach, see the course notes on Characters and Character Encoding.

Strings

A string is a list of characters. Sets of strings are called languages. We cover strings and languages in much more detail in our notes on Language Theory, where we will encounter a great many operations.

Maps

Sometimes it’s convenient to think of partial functions as maps where the inputs are the keys and the outputs are the values. When we do, we tweak the notation a bit, so that the following partial function, $m \in \textsf{Unicode}^* \rightharpoonup \mathbb{N}$:

$(\lambda s. \bot)[\texttt{a} \mapsto 1][\texttt{b} \mapsto 2][\texttt{c} \mapsto 3]$

is more conveniently shown as:

$\{ \texttt{a}\!: 1, \texttt{b}\!: 2, \texttt{c}\!: 3 \}$

We will consider the latter just syntactic sugar for the former, rather than defining maps as a primitive type. So for this particular map, we have:

Also, because maps are just functions, the substitution notation works for them too. If $m$ is the map above, we can write things like $m[\texttt{d} \mapsto 4]$ for the map just like $m$ with the additional key-value pair mapping $d$ to $4$, and $m[\texttt{b} \mapsto 0]$ for the map like $m$ except $\texttt{b}$ now maps to $0$.

Graphs

Structurally, a graph is a set of vertices and a set of edges connecting pairs of vertices. Behaviorally, a graph comes with associated operations such as finding paths, computing connectivity, and traversing the graph.

Vectors

Structurally, a vector is a tuple that contains numbers. Behaviorally, while a tuple just kind of sits there, a vector comes with associated operations obeying the laws of a vector space such as vector addition and scalar multiplication.

Matrices

Structurally, a matrix is a two-dimensional array of numbers. Behaviorally, a matrix comes with associated operations obeying the laws of matrix algebra such as matrix addition and matrix multiplication.

Tensors

Structurally, a tensor is a multi-dimensional array of numbers. Behaviorally, a tensor comes with associated operations obeying certain laws.

Encodings

In studying mathematical foundations, we need to show how various mathematical objects can be represented using the primitive notions of a foundational theory.

The complete encodings will be shown in our detailed notes on Set Theory and Type Theory. For now, we’ll tease the basic ideas.

The Set Theory Approach

Most set theories reduce everything down to, then build everything up from, sets. A set is a (possibly empty) collection of elements, which are themselves sets, constructed in such a way as to avoid nonsense collections.

Though there are many set theories, they all share some common notation:

• $x \in A$ is defined to mean $x$ is an element of $A$.
• $x \notin A$ sugars $\neg(x \in A)$, and is read “$x$ is not an element of $A$.”
• $A \subseteq B$ sugars $\forall x. x \in A \supset x \in B$, and is read “$A$ is a subset of $B$.”

This idea is to be able to express statements like:

Set theories assume that first-order predicate logic already exists then add axioms to say what sets are and how they behave. Again, this is necessary to make sure we avoid nonsense like “the set of all non-self-containing sets”.

The most popular set theory, ZFC, gives us axioms that say:

• The empty collection $\varnothing$ is a set.
• The collection $\{ \varnothing, \{\varnothing, \{\varnothing\}\}, \{ \varnothing, \{\varnothing, \{\varnothing\}\} \}, \{ \varnothing, \{\varnothing, \{\varnothing\}\}, \{ \varnothing, \{\varnothing, \{\varnothing\}\} \} \}, \ldots \}$ is a set.
• Given any two sets, the collection containing all and only those two sets is a set.
• Given a set of sets, the collection containing all and only the elements of those sets is a set.
• For any set, the collection containing all and only its subsets is a set.
• Given any set, a new set can be formed from the image of the set under a mapping.
• If two sets have exactly the same elements, they are equal.
• Every non-empty set contains an element that is disjoint from it.
• For any set of pairwise disjoint, non-empty sets, there exists a set that has exactly one element in common with each member of the set.

These axioms prevent Russell’s Paradox.

There is a lot of notation in Set Theory, so more sugar will be warranted. We’ll be using:

$\begin{array}{lcl} \forall x \in A. P & \textrm{to sugar} & \forall x.\, x \in A \supset P \\ \exists x \in A. P & \textrm{to sugar} & \exists x.\, x \in A \land P \\ \forall x\,y \in A. P & \textrm{to sugar} & \forall x. \forall y.\, x \in A \land y \in A \supset P \\ \exists x\,y \in A. P & \textrm{to sugar} & \exists x. \exists y.\, x \in A \land y \in A \land P \\ \end{array}$

Now we know what sets are. To have Set Theory as a foundation for mathematics, we need to be able to encode every mathematical object as a set. But how? Here are some encodings people have invented:

Object	Encoding in Set Theory
Natural Numbers	$0 = \varnothing$ $1 = \{0\} = \{\varnothing\}$ $2 = \{0, 1\} = \{\varnothing,\{\varnothing\}\}$ $3 = \{0,1,2\} = \{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}$ $4 = \{0,1,2,3\}$ ... $n = \{0,1,2,\ldots,n-1\}$ ...
Booleans	$\textsf{false} = 0$ $\textsf{true} = 1$
Ordered Pairs	$(a, b) = \{\{a\}, \{a, b\}\}$
Tuples	Ordered pairs that “nest” to the right
Relations	Sets of ordered pairs
Functions	Relations in which each left element is unique
Sequences	Functions from $\{0, 1, \ldots, n\}$ to some set, representing an ordered list of elements
Lists	Nested pairs in which the innermost pair has the form $(x, \varnothing)$
Characters	Natural numbers (interpreted as code points)
Strings	Lists of characters
Integers	Sets of all pairs of natural numbers $(a, b)$ with the same difference $a - b$
Rational Numbers	Sets of all pairs of integers $(a, b)$ with $b \neq 0$ with the same quotient $\frac{a}{b}$
Real Numbers	Sets of rational numbers with no lower bound, no greatest element, and for any rational number in the set, contains all rational numbers less than that value

Other Set Theories

ZFC is just one of many set theories. They all resolve the paradoxes arising from being too loose with what is and is not a set, particularly Russell’s Paradox, in different ways. Some theories make self-containing sets impossible to write. NF allows such sets but gets around the root problem with stratification. NBG distinguishes sets and classes.

Some set theories allow for the existence of items that are not sets, but that can be members of sets. They’re called urelements. ZFC explicitly rejects these because the foundations are easier without them, and they don’t really add any expressive power.

The Type Theory Approach

Type Theory doesn’t go as deep into making all objects one kind of thing, but does something much more convenient. It allows you to bring into existence whatever objects you need, as long as you give them each a type and construct them carefully. You do this by defining rules that exhaustively specify the inhabitants of a type.

Our first type:

$$ \dfrac{}{\textsf{true}\!: \textsf{Bool}} \quad\quad\quad \dfrac{}{\textsf{false}\!: \textsf{Bool}} $$

This states that the type $\textsf{Bool}$ is inhabited by exactly two values, $\textsf{true}$ and $\textsf{false}$. No more, no less. We have created two things. And a type.

Now here is the type of natural numbers:

$$ \dfrac{}{0\!: \textsf{Nat}} \quad\quad\quad \dfrac{n\!: \textsf{Nat}}{\textsf{s}\,n\!: \textsf{Nat}} $$

This says “(1) $0$ is a natural number, (2) For any natural number $n$, $\mathsf{s\,}n$ is a natural number, and (3) nothing else is a natural number.” So the type of natural numbers is inhabited by $0$, $\mathsf{s\,}0$, $\mathsf{s\,s\,}0$, $\mathsf{s\,s\,s\,}0$, $\mathsf{s\,s\,s\,s\,}0$, and so on. We’ll write these as $0$, $1$, $2$, $3$, $4$, and so on. These abbreviations should be familiar to you.

Now for the integers:

$$ \dfrac{n\!: \textsf{Nat}}{\textsf{pos}\,n\!: \textsf{Int}} \quad\quad\quad \dfrac{n\!: \textsf{Nat}}{\textsf{neg}\,(\textsf{s}\,n)\!: \textsf{Int}} $$

So the type of integers is inhabited by $\mathsf{pos\,}0$, $\mathsf{neg}\,(\mathsf{s}\,0)$, $\mathsf{pos}\,(\mathsf{s}\,0)$, $\mathsf{neg}\,(\mathsf{s\,s}\,0)$, $\mathsf{pos}\,(\mathsf{s\,s}\,0)$, $\mathsf{neg}\,(\mathsf{s\,s\,s}\,0)$, and so on. We’ll abbreviate these as $0$, $-1$, $1$, $-2$, $2$, $-3$, and so on. But what, then, is the type of $3$? We need to figure it out from context, or we can write $3_{\textsf{Nat}}$ or $3_{\textsf{Int}}$ to be explicit.

Here are the rationals:

$$ \dfrac{n\!: \textsf{Int} \quad d\!: \textsf{Nat}}{\textsf{rat}\,n\,(\textsf{s}\,d)\!: \textsf{Rat}} $$

So one-third is $\textsf{rat}\,1\,3$, which we can abbreviate as $\frac{1}{3}$. Make sure to study the rule carefully to see how a “zero in the denominator” is avoided.

We can build lots of numeric types that are useful in programming languages, for example $\textsf{Int8}$, $\textsf{Int16}$, $\textsf{Int32}$, $\textsf{Int64}$, $\textsf{Int128}$, $\textsf{UInt8}$, $\textsf{UInt16}$, $\textsf{UInt32}$, $\textsf{UInt64}$, $\textsf{UInt128}$, $\textsf{Float16}$, $\textsf{Float32}$, $\textsf{Float64}$, $\textsf{Float128}$, $\textsf{Complex64}$, $\textsf{Complex128}$, and so on. Some might require a lot of rules, but they can be defined in principle.

We can make up more types for ourselves. Here is one for primary colors:

$$ \dfrac{}{\textsf{red}\!: \textsf{PrimaryColor}} \quad\quad\quad \dfrac{}{\textsf{green}\!: \textsf{PrimaryColor}} \quad\quad\quad \dfrac{}{\textsf{blue}\!: \textsf{PrimaryColor}} $$

You can define the type $\textsf{Unicode}$ whose inhabitants are, you guessed it, the characters of Unicode. That’d be a lot of rules! But it is indeed definable, as there are a finite number of such characters.

Now here is a type for some simple two-dimensional shapes:

$$ \dfrac{r\!: \textsf{Float64}}{\textsf{circle}\,r\!: \textsf{Shape}} \quad\quad\quad \dfrac{w\!: \textsf{Float64}\quad h\!: \textsf{Float64}}{\textsf{rectangle}\,w\,h\!: \textsf{Shape}} \quad\quad\quad \dfrac{a\!: \textsf{Float64}\quad b\!: \textsf{Float64} \quad c\!: \textsf{Float64}}{\textsf{triangle}\,a\,b\,c\!: \textsf{Shape}} $$

The idea is that $\mathsf{circle}\,5.0$ is a circle with radius 5. Here are ordered pairs:

Objects can have rather complex structure, if you define the types recursively. Here’s the type “list of elements of type $t$” which we will write $t^*$:

$$ \dfrac{}{[\,]\!: t^*} \quad\quad\quad \dfrac{x\!: t \quad y\!: t^*}{(x :: y)\!: t^*} $$

We will write ${[x]}$ for $(x\,\textbf{::}\,[\,])$, ${[x,y,z]}$ for $(x\,\textbf{::}\,(y\,\textbf{::}\,(z\,\textbf{::}\,[\,])))$, and so on. For an empty list, we would need to rely on context to infer its type, or be explicit by writing, for example, $[\,]_\textsf{Int*}$.

Imagine what the type $\textsf{Unicode}^*$ is. Got it? That’s right! We’ll use the abbreviation $\textsf{String}$ for this type. This makes programmers happy.

Here is a type for “binary trees of type $t$”:

There’s a type called $\textsf{Void}$ that has no inhabitants. So there are no constructors.

Just as in Set Theory, there are rules we have to follow to make sure we are not constructing nonsense types. We’ll cover this in detail in our notes on Type Theory.

When defining functions over types like $\textsf{Shape}$, we pattern match on the constructors of the type. This ensures that our function handles all possible cases and adheres to the type system.

$\begin{array}{l} \textsf{area}\!:\textsf{Shape} \rightarrow \textsf{Float64} \\ \textsf{area}\;(\textsf{Circle}\;r) = \pi r^2 \\ \textsf{area}\;(\textsf{Rectangle}\;w\;h) = wh \\ \textsf{area}\;(\textsf{Triangle}\;a\;b\;c) = \textsf{let}\;s = \frac{a + b + c}{2} \;\textsf{in}\; \sqrt{s(s-a)(s-b)(s-c)} \\ \end{array}$

$\begin{array}{l} \textsf{perimeter}\!:\textsf{Shape} \rightarrow \textsf{Float64} \\ \textsf{perimeter}\;(\textsf{Circle}\;r) = 2 \pi r \\ \textsf{perimeter}\;(\textsf{Rectangle}\;w\;h) = 2 (w + h) \\ \textsf{perimeter}\;(\textsf{Triangle}\;a\;b\;c) = a + b + c \\ \end{array}$

We will see many more examples in our notes on Type Theory.

Math and Computation

Much of mathematics is aided by the use of computers. Computers speed up time, allowing us to think previously unthinkable thoughts. Computers make science and mathematics qualitatively different. Computers augment and amplify human thought. In math, complex proofs can be found or checked by automated proof assistants. Generally, these proof assistants are based on Type Theory, not Set Theory, for various reasons (many taken from these slides by Sergey Goncharov):

• In Type Theory, functions are primitive. They are not just special kinds of sets of pairs. Functions compute things, and thus feel dynamic. Why look at them like static relations?
• Set Theory purports to be simpler, in that it has fewer basic notions, as in everything is a set. But this really isn’t the case, as the axioms of Set Theory are really complex and few people know them all. The axioms are arguably arbitrary and don’t help much in finding proofs. Set Theory is just too theoretical.
• Set Theory’s “everything is a set” approach is actually too simple. We want to distinguish tuples and functions and relations and numbers. Mathematicians naturally think in terms of different types of objects. Why treat them all as sets? This leads to silliness like $2 \in 3$ and $\pi \cap \mathbb{R}$.
• In Set Theory, logic and objects come first, then we use sets to group the objects. In type theory, types come first, then we construct objects to inhabit the types, and logic emerges. Thus Type Theory does not decouple logic from the objects it defines the way Set Theory does.
• Most type theories are constructive! There’s no excluded middle, for one thing. To prove existentials, you have to supply a witness. To prove disjunctions, you have to show one of the disjuncts. Computation feels constructive. In contrast, most set theories are classical.
• Set Theory’s underlying logic has debatable principles such as the Excluded Middle, the Axiom of Choice, and Impredicativity, which get in the way of automation.

Hello? Category Theory?

Yes, we made a decision to focus on Set Theory and Type Theory only. Two theories are enough to get you started on the foundational aspects of mathematics. Category Theory is important, but it can be explored after gaining a solid understanding of Set Theory and Type Theory.

Math and Logic

Remember how we started with the observation that Logic is a prerequisite for Set Theory, but Logic emerges from Type Theory? Perhaps this means Type Theory is more fundamental? Maybe. But it does indicate something: there must be a deep connection between Logic and Type Theory.

We won’t cover it all right now, but will leave you with something to think about. Here is the type inference rule that tells us the type of the output of a function application:

That looks like Modus Ponens in logic. Is that a coincidence or an interesting correspondence?

And the inference rule for inferring the type of a pair is:

Can’t you just feel logical conjunction here?

This is just a small part of the Curry-Howard correspondence, which we’ll see when we cover Type Theory in depth.

Beyond Foundations

This page is focused on foundations. But there’s much more to math that is useful in computer science. You might want to check out:

• Counting principles (pigeonhole, addition, multiplication)
• Permutations
• Combinations
• Recurrence Relations
• Algebraic Structures
• Linear Algebra
• Geometry
• Topology
• Analysis
• Probability, for which you really need to see the amazing Seeing Theory: A Visual Introduction to Probability and Statistics
• Optimization
• Graph Theory
• Number Theory

Does Math Describe the World?

Did you watch the Vsauce video above? Kind of cool how Michael says we can do math that isn’t science and just invent things that we declare to be true, like transfinite infinities, and yeah, as long as we don’t have contradictions, let’s go. The first two frames of the famous XKCD Every Major’s Terrible has fun with this idea:

Sometimes our inventions do give us good models. Cohl Furey explains it in two minutes:

Intrigued? Watch her entire Division Algebras And the Standard Model playlist. Or checkout this article on her work.

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What are some things that are reasoned about within mathematics?
   Quantity, structure, change, chance, causality, and space.
2. Mathematic reasoning involves finding abstract ________________ and constructing ________________ of real and imaginary phenomena.
   patterns, models.
3. Was math invented or discovered?
   Probably both.
4. What are some of the main branches within mathematics?
   Foundations, algebra, analysis, discrete, geometry, number theory, topology, applied mathematics, and computational mathematics.
5. What are three theories that claim to be able to formalize “all of mathematics”?
   Set Theory;
   Type Theory;
   Category Theory.
6. What are the characteristic notations of set, type, and category theory?
   $x \in A$
   $x : A$
   $X \xrightarrow{f} Y$
7. What is perhaps the main difference between set theory and type theory?
   In set theory, everything is a set. In type theory, types come first, and objects are constructed to inhabit the types.
8. What are some of the foundational mathematical objects?
   Booleans, numbers, tuples, characters, strings, sequences, relations, functions, sets, vectors, matrices, tensors, maps, graphs.
9. What does the expression $A \subseteq B$ sugar?
   It is syntactic sugar for $\forall x (x \in A \rightarrow x \in B)$.
10. What does a tuple look like?
    $(a, b, c)$
11. What is $(10, 20, 30)\downarrow 1$?
    $20$
12. What is $(2, 8, 3) \bullet (5, 1)$?
    $(2, 8, 3, 5, 1)$
13. How do sets differ from tuples?
    Sets are unordered and do not contain duplicates.
14. What is the difference between a crisp set and a fuzzy set?
    A crisp set is a set where an element is either in the set or not. A fuzzy set is a set where an element can be partially in the set.
15. How do we denote that $x$ is a member of the set $A$?
    $x \in A$
16. Why isn’t $\{ x \mid x \not\in x \}$ considered a set?
    Considering it a set ruins everything because if it were a set, assuming it was a member of itself would imply it was not and assuming it was not a member of itself would imply that it was.
17. How is set subtraction $A \setminus B$ defined?
    $\{x \in A \mid x \notin B\}$
18. What is the difference between $A-B$ and $A \setminus B$?
    Nothing, they are the same.
19. What is the difference between $A \setminus B$ and $A \vartriangle B$?
    The first is the set of all elements in $A$ but not in $B$. The second, the symmetric difference, is the set of elements that are in exactly one of $A$ or $B$.
20. What is $\mathcal{P}(\{a,b,c\})$?
    $\{\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \}$
21. What is $\{1,2\}^*$ (assuming this set is not an alphabet or language)?
    $\{(), (1), (2), (1,1), (1,2), (2,1), (2,2), (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), \ldots \}$
22. What is $\{1, 2\}^0$?
    $\{ () \}$
23. Given a relation $R$ defined as a subset of $A \times B$, what are $A$ and $B$ called?
    The domain and codomain of $R$.
24. How do we denote the type of a function from $A$ to $B$?
    $A \rightarrow B$
25. How do we denote the set of all functions from $A$ to $B$?
    $A \rightarrow B$
26. How do we represent the set $\{ (x, y) \mid x \in \mathbb{N} \land y \in \mathbb{N} \land x > y \}$ as a function in Type Theory?
    $\lambda (x, y)_{\small \mathsf{nat \times nat}}. x > y$
27. How do you write let $x = 8$ in $2^x - 1$ without the “let”?
    $(\lambda x. 2^x - 1)(8)$
28. How do you write $(\lambda x. x + 3)(5)$ in where-notation?
    $x + 3\;\textsf{where}\;x = 5$
29. Suppose $f = \lambda x. x^2$ and $g = \lambda x. x + 3$. What are $f \circ g$ and $g \circ f$?
    $f \circ g = \lambda x. (x + 3)^2$
    $g \circ f = \lambda x. x^2+3$
30. Suppose $f = \lambda x. 5x + 2$ and $g = f[1 \mapsto 2]$. What are $g(8)$ and $g(1)$?
    $g(8) = 42$
    $g(1) = 2$
31. How do you write the function that maps "x" to 21, "y" to 8, "z" to 55, and every other input to 0, in both lambda notation and as a map?
    $(\lambda x. 0)[21/\texttt{"x"}][8/\texttt{"y"}][55/\texttt{"z"}]$
    $\{ \texttt{"x"}\!: 21, \texttt{"y"}\!: 8, \texttt{"z"}\!: 55 \}$
32. Let $f = \lambda x. 3x + 5$. What are $f^{-1}$, $f^0$, $f^1$, and $f^2$?
    $f^{-1} = \lambda x. \frac{x-5}{3}$
    $f^0 = \lambda x. x$
    $f^1 = \lambda x. 3x + 5$
    $f^2 = \lambda x. 9x + 20$.
33. If A was the alphabet $\{a, b, c\}$, what is $A^2$?
    $A^2$ is the set of all 2-letter words that can be formed from $A$, i.e., $\{aa, ab, ac, ba, bb, bc, ca, cb, cc\}$.
34. How to we write the partial function mapping the vowels of the English alphabet to their 1-based position in the alphabet in map-notation?
    $\{ \texttt{a}\!: 1, \texttt{e}\!: 5, \texttt{i}\!: 9, \texttt{o}\!: 15, \texttt{u}\!: 21 \}$
35. What kind of number is this: $3 + 8i - 5j + k$?
    A quaternion.
36. What kind of a number is $2 - 5e_0 * 8e_6$?
    An octonion.
37. What do we call $\uparrow$, $\uparrow\uparrow$, and $\uparrow\uparrow\uparrow$?
    Exponentiation, tetration, pentation.
38. How do you conventionally write $5 \uparrow\uparrow 3$?
    $5^{5^5}$
39. Perform “one-step” in the simplification of $8 \uparrow\uparrow\uparrow 5$. That is, write the expression in terms of the $\uparrow\uparrow$ operator alone.
    $8 \uparrow\uparrow\uparrow 5 = 8 \uparrow\uparrow (8 \uparrow\uparrow (8 \uparrow\uparrow (8 \uparrow\uparrow 8)))$
40. What are the ”inverses” of addition, multiplication, and exponentiation?
    Subtraction, division, logarithm.
41. What is $\log_2 1024$ and why?
    $10$, because $2^{10} = 1024$
42. What is $\log_{2} 0.125$ and why?
    $-3$, because $2^{-3} = \frac{1}{2^3} = \frac{1}{8} = 0.125$
43. What is cardinal number?
    A number that tells you how many of something there is.
44. ________________ is more fundamental than counting.
    Matching
45. What are the cardinalities of $\varnothing$, $\{a, b, c\}$, and $\mathbb{Z}$?
    0, 3, $\aleph_0$
46. How are ordinal numbers different from cardinal numbers?
    Ordinal numbers describe the position of an element in a sequence, while cardinal numbers describe the size of a set.
47. Who is the guy that made that freaking amazing set of web pages on big numbers?
    Robert P. Munafo
48. What is a trotillion?
    $10^{(3 \times 10^{(3 \times 10^{900})} + 3)}$
49. Distinguish scalars, vectors, matrices, and tensors.
    Scalars are single numbers. Vectors are ordered lists of numbers. Matrices are two-dimensional arrays of numbers. Tensors are generalizations of scalars, vectors, and matrices to higher dimensions.
50. (From the Cohl Furey video) What branches of physics do the complex numbers and the quaternions, respectively, play a central role in?
    Quantum mechanics; Special relativity.

Summary