Chapter 3 - Math concepts and notation

We saw in the Introduction that, just like sculpting, theoretical modeling requires its own set of dedicated tools. The theoretical modeler’s toolbox includes a.o. mathematical concepts, formal expressions, and notational conventions. One can already get quite far with the basics in set theory, functions and logic. Below we present a brief primer. Readers who have taken introductory classes on these topics can skip this section without loss of continuity. If, however, these materials are new to you, then we recommend carefully studying this chapter before proceeding. A good grasp of the concepts and notation defined here will be necessary for following the examples and exercises in subsequent chapters. In general, developing some fluency in mathematical language is key if one wants to become a theoretical modeler.

⊕
Sets can be visualized as circles.

Set theory

A set is a collection of distinct objects. For example, a set of people $P=\{\text{Ramiro},\text{Brenda},\text{Molly}\}$, animals $A=\{\text{cat},\text{turtle},\text{blue whale}, \text{cuttlefish}\}$ or numbers $N=\{1,5,7,12\}$. Sets are usually denoted by a capital letter and their elements listed between curly brackets. They can also be visualized as circles.

Sets can contain an infinite number of objects, e.g. all positive odd numbers $O=\{1,3,5, 7,\dots\}$.

Set membership

⊕
Set membership.

When we want to write that an object $x$ is (or is not) part of a set $X$, we use set membership notation:

\[5 \in N\\17 \notin N\\\text{Ramiro}\in P\\\text{Saki}\notin P\]

Subset and superset

⊕
Subset relationship. Often, we want to express things like ‘the set of mammals $M$ is part of the set of all animals $A$’. We then use subset notation: $M\subseteq A$ or $M\subset A$. The latter means that $M$ is smaller than $A$.

⊕
Superset relationship. Vice versa, we can express that ‘the set of all things on earth $T$ contains all animals $A$’ using superset notation: $T\supseteq A$ or $T\supset A$. The latter means that $T$ is bigger than $A$.

Intersection, union and difference

Let’s look at what more we can do with two sets. ⊕
Example sets. For example, take the set of your friends and my friends.

\[F_{you}=\{\text{John},\text{Roberto},\text{Holly},\text{Doris},\text{Charlene}\}\] \[F_{me}=\{\text{Vicky},\text{Charlene},\text{Ramiro},\text{Johnnie},\text{Roberto}\}\]

⊕
Set intersection. Who are our common friends? We use set intersection:

\[F_{you}\cap F_{me} = \{\text{Roberto},\text{Charlene}\}\]

Who do we know together? We use set union:

$F_{you}\cup F_{me} = \{\text{John},\text{Roberto},\text{Holly},\text{Doris},\text{Charlene},$ $\text{Vicky},$ $\text{Ramiro},$ $\text{Johnnie}\}$

⊕
Set union.

Who do I know that you do not know? We use set difference:

\[F_{me}\setminus F_{you}=\{\text{Vicky},\text{Ramiro},\text{Johnnie}\}\]

⊕
Set difference.

Set builder

A more advanced way to denote sets, is to define a set using set builder notation. This allows us to define (build) a new set given other set(s). A set builder consists of two parts, a variable and a logical predicate:

\[\{\text{variable}~|~\text{predicate}\}\]

Let’s look at an example and build a set of all mammals from $A$. We explain logical predicates below, for now lets use verbal language:

\[M=\{a~|~a\in A\text{ and }a\text{ is a mammal}\}\]

You can read this as ‘$M$ contains all $a$’s with the property that $a\in A$ and $a$ is a mammal’.

⊕
Set builder.

Cardinal product

Set builder notation is useful to filter objects from a single set, but becomes very potent when building from multiple sets. For example:

\[F=\{(p,a)~|~p\in P\text{ AND }a\in A\}\]

⊕
Cardinal product.

Read this as ‘$F$ contains all pairs of $p$ and $a$ with the property that $p$ is a person and $a$ is an animal’. Pairs are denoted in brackets. You can think of $F$ containing all possible combinations of person-animal pairs. For example, these are all the options you have when trying to guess what the favorite animals are of your friends.

Many other set builders are possible too, but this specific ‘pair builder’ is called the cardinal product of two sets. It is used often enough that it has its own special symbol: $F=P\times A$.

Special sets

Finally, there are some special sets which we often use that have their own symbols:

Empty set $\varnothing=\{\}$
Natural (whole) numbers (with zero) $\mathbb{N}_0=\{0,1,2,3,4,\dots\}$
Natural (whole) numbers (without zero) $\mathbb{N}^*=\{1,2,3,4,\dots\}$
Integer numbers $\mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\}$
Real numbers $\mathbb{R}=\{r~|~-\infty<r<\infty\}$

Tuple

In sets elements are unordered and no element can exist twice. However, there are occasions where the ordering of the elements is relevant and when the same element can exist multiple times. For example, a text is a sequence of characters where ordering is quite important and characters can occur multiple times. To express these sequences or lists we use the mathematical notation of tuples. An $n$-tuple is a sequence of $n\geq0$ elements. The sequence is most commonly expressed between parentheses $()$, but sometimes you will encounter other types of brackets such as $\{\}$, $[]$ and $\langle\rangle$ derived from variations on the tuple such as arrays or vectors. In this book, we will use $\langle\rangle$ to express regular (ordered) tuples, i.e., sequences or lists. We use parentheses $()$ to express unordered tuples (e.g., in graph theory).

Specific elements in a tuple $\langle e_1,e_2,\dots,e_n\rangle$ can be referred to by their label $e$ and index $_i$. Depending on the type of the elements, you can use these in expressions (see below for functions and logic expressions). Here are some example tuples:

A travel route to the south of France: $r=\langle\text{Nijmegen},\text{Liège},\text{Metz},$ $\text{Nancy},\text{Dijon},\text{Lyon},\text{Marseille}\rangle$. We can refer to the $3^\text{th}$ waypoint with $r_3$ which is Metz.

A preference list: $p=\langle\text{chocolate},\text{hiking},\text{sauna},\text{math}\rangle$. This person likes chocolate more than math.

Functions

To define functions we go back to set theory. Functions are relations that map all objects from one set (the domain) to exactly one object from another set (the codomain). We define functions with the following notation, here $f$ is the name of the function:

\[f:D \rightarrow C\text{ with }f(d)=c\]

Let’s make this more concrete:

\[like: P \rightarrow \mathbb{Z}\]

You can read this as ‘$like$ is a function that maps persons $p\in P$ to an integer’.

⊕
Function.

We sometimes omit the exact specification of the function when it is clear what it would be. For example, here it could be a list of numbers representing how much you (dis)like the person, based on your social interactions with that person.

Advanced functions

We can also give functions more complex domains by using set theory. What would a function that captures how much two persons like each other look like?

\[like_2:P\times P\rightarrow \mathbb{Z}\]

The cardinal product $P\times P$ denotes all pairs of persons and $like_2$ maps pairs to an integer.

⊕
Advanced function.

Sum and product

We can now define summation and product. These functions iterate over members in a set and return a summary value.

Summation $\sum$ takes all $x$’s from $X$, applies $f(x)$ to each and adds all values:

\[\sum_{x\in X}f(x)=f(x_1)+f(x_2)+f(x_3)+\dots\]

Product takes $\prod$ all $x$’s from $X$, applies $f(x)$ to each and multiplies all values:

\[\prod_{x\in X}f(x)=f(x_1)f(x_2)f(x_3)\dots\]

Logic

Logical predicates can be thought of as a special type of function that returns a Boolean value true ($\text{true}$ or $\top$) or false ($\text{false}$ or $\bot$). Predicates can be thought of as asking or claiming whether or not a statement is true or false.

For example, is $x$ bigger than $2$? Is $a$ a mammal and small? Is Emily your friend? Or, $x$ is bigger than $2$, $a$ is a mammal and small, and Emily is my friend.

Let’s introduce some formal notation to express these statements:

number comparisons are familiar to most $<$, $\leq$, $>$, $\geq$, $=$, and $\neq$
conjunctions (logical $\text{AND}$) $p\wedge q$ is $\top$ if and only if both $p=\top$ and $q=\top$
disjunctions (logical $\text{OR}$) $p\vee q$ is $\top$ if $p=\top$ or if $q=\top$
set membership can also be used as a predicate $a\in A$ is $\top$ if $a$ is a member of set $A$

Universal quantifier (for all)

Sometimes we want to say something about all objects in a set. We can use quantifier predicates to do this. For example, are all animals in the set mammals? We use the universal quantifier:

\[\forall_{a\in A}\text{mammal}(a)\]

You can read this as `does it hold for all objects $a$ in $A$ that $a$ is a mammal?’ We implicitly introduced a function $\text{mammal}:A\rightarrow\{\top,\bot\}$ with $\text{mammal}(a)=\top$ if $a$ is a mammal or $\bot$ otherwise.

Existential quantifier (exists)

Another type of question we can ask is, for example, is there someone I know that I like? We use the existential quantifier:

\[\exists_{p\in F_{me}}\left[\text{like}(p)>0\right]\]

Which we can read as `does there exist a person $p$ in the set of my friends $F_{me}$ for which I like them $\text{like}(p)>0$?’

Graph theory

There are cases where we want to express the existence of a relationship between two elements in a set. For example, who is friends with who, which two ingredients go well together, the distance between two cities or how often words co-occur in text. Here, we consider relationships that are Boolean (e.g., you are friends or not) or numeric (e.g., distances). Graph theory allows us to express in abstract the set of elements $V$ called vertices and their relationships $E$ called edges which together make up a graph $G=(V,E)$. The set of edges is a subset of the cardinal product of the vertices $E\subseteq V\times V$. If there is a relationship between two vertices $e\in V$ and $v\in V$, then $(u,v)\in E$.

Depending on their structure, graphs can be classified into different types. In this book, we use only a few types of graphs, but see Further Reading if you are interested in diving deeper.

Simple graph

The first graph type is called a simple graph. A simple graph has no edges between a vertex and itself $\forall_{v\in V}(v,v)\notin E$, i.e., it has no self-loops. A simple graph also has at most one edge between any two vertices, i.e. it has no multi-edges.Multi-edges cannot be represented by a set of edges alone, since a set cannot contain multiple copies of the same edge. All graphs in the examples above are simple graphs. In this book, we assume a graph is simple unless otherwise noted.

Connected graph

Not all vertices in a graph need to have an edge, in fact none need to. A graph where for some vertices there exists no path between them is called a forest, because it is a collection of connected graphs. In a connected graph, there always exists a path between any pair of vertices. Graphs B, C, and D in the examples above are connected graphs, graph A is a forest.

In formal notation Graph A is $V=\{\text{John},$ $\text{Doris},$ $\text{Roberto},$ $\text{Ramiro},$ $\text{Charlene},$ $\text{Holly}\}$ and $E=\{(\text{John},\text{Doris}),$ $(\text{Doris},\text{Roberto}),$ $(\text{Ramiro},\text{Charlene}),$ $(\text{Ramiro},\text{Holly}),$ $(\text{Charlene},\text{Holly})\}$.

Weighted graph

Graphs who’s relationships between vertices is a number, are called weighted graphs. Here, in addition to the graph $G=(V,E)$ a weight function is supplied $w:V\times V\rightarrow \mathbb{Z}$. Often, weighted graphs are fully connected but some edges may have a neutral weight such as $0$. Graph B in the examples above is a weighted graphs. If vertex relationships are Boolean, then the graph is unweighted. Graphs A, C and D are unweighted graphs.

Graph B is written up analogously to graph A but we add the weight function $w(\text{Amsterdam},\text{Groningen})=180$, $w(\text{Amsterdam},\text{The Hague})=164$, etc.

(Un)directed graph

Graphs where edges have no direction are called undirected graphs. Here, the pairs of vertices $(u,v)\in E$ are unordered. This means that $(u,v)=(v,u)$. Of course, directed graphs also exist. Here, the pair is ordered and edges have directionality. Graphs A, B and D in the examples above are undirected graphs, graph C is a directed graph.

Graph C is written as graph A, but the order of edges matter. So $(\text{Clouds},\text{Rain})\in E$ but $(\text{Rain},\text{Clouds})\notin E$.

Tree

The final graph type we condider here is more a type of graph with specific properties, namely a tree. Trees are graphs without cycles, which means there is exactly one path (a sequence of edges) between any two vertices. Another way of thinking of acyclic graphs is that there is no way to ‘walk back’ to a vertex along a different ‘route’. Graph D in the examples above is a tree. Trees can be also be directed, in which case they are called polytrees.

Graph D is again written as graph A. Nothing special is needed to denote a tree, since it follows from the graph’s structure that it is a tree. Sometimes, if you want to be very clear, you can write graph/tree $T=(V,E)$ to denote a tree.

Graph properties

Graphs have many formal properties but for the purposes of this book, only a few basic properties are important.

⊕
Vertex degree. Vertex $A$ has degree 4, vertex $B$ has indegree 3, and vertex $C$ has outdegree 2. The first is the degree of a vertex. This is the number of connections that a vertex $v$ has, formally $deg(v)=\left|\{u=v \wedge w=v|(u,w) \in E\}\right|$. If a graph is directed, then we split degree into indegree (the number of edges toward the vertex) and outdegree (the number of edges away from the vertex). For weighted graphs, we ignore the weight.

The maximum number of possible edges in an undirected graph is $\frac{|V|(|V|-1)}{2}$. The first vertex in the graph can have unqiue edges with $|V|-1$ vertices, the second with $|V|-2$ vertices, the third with $|V|-3$ vertices, etc., until the $(|V|-1)^\text{th}$ vertex which can only have a unique edge with $1$ vertex: $(|V|-1) + (|V|-2) + (|V|-3) + \dots + 3 + 2 + 1=\frac{|V|(|V|-1)}{2}$.

The number of possible edges in a directed graph can be derived from the number of possible edges in an undirected graph. In a directed graph can be two edges between any two vertices, doubling the number of possible edges: $2\frac{|V|(|V|-1)}{2}=|V|(|V|-1)$.