1Variables

What is the sum of all numbers between $1$ and $5$? Let’s simply compute it: $1+2+3+4+5=15$. What is the sum of all numbers between $1$ and $100$? Let’s make the pupils spend an hour to compute it. At least this is what the teacher of Carl Friedrich Gauß intended when he gave this task to his class. Gauß, however, came back with the correct answer $5050$ almost immediately. He had realized that the sum can be written as follows:

As the two numbers above each other always sum up to $101$, and there are $50$ such pairs of numbers, the sum of all numbers is $50\cdot 101=5050$. Gauß later became a famous mathematician. Here, he had cleverly used the fact that in summing up numbers, we can order and group the numbers as we like. The math terminology for this is that addition is commutative and associative. The order $1+2+...+100$ given by the teacher is much less practical than the order and grouping $(1+100)+(2+99)+\cdots + (50+51)$ that Gauß came up with. In fact, reordering and regrouping things in order to simplify computations is the mathematician’s bread and butter.

Mathematicians immensely like the argument of Gauß but at the same time see more behind it. In fact, whether we sum up to $100$, or to some other even number (for example $1000$) doesn’t really matter—the argument is always “the same.” Hence, mathematicians will try to prove a general theorem (a mathematical statement), involving a variable. The answer for the concrete number $100$ (or for $1000$, or for a milllion) can then be derived by plugging the concrete number into the variable. This would look as follows.

We note that $n(n+1)$ is the lazy mathematician’s shortcut for the multiplication $n\cdot (n+1)$, and $/$ stands for division. In an offset formula (such as the following) where we have more vertical space, we would write $n(n+1)/2$ as a fraction

The little box on the right indicates the end of a proof. In some older textbooks (and in math fiction), the end of a proof is sometimes denoted by q.e.d., quod erat demonstrandum, Latin for what was to be shown.

In this theorem and its proof, the symbol $n$ is a (mathematical) variable. It is a placeholder for an actual number, and the theorem tells us what numbers we are allowed to plug in (“Let $n$ be a positive even number.”) For example, when we plug in $100$, the sum is $100\cdot (100+1)/2=5050$, as we already know. For $1000$, we do not need to repeat the proof but simply plug in $1000$ to get that the sum of the numbers between $1$ and $1000$ is $500500$.

The cool feature of a theorem is that it gives the answer for infinitely many numbers, with only one proof; in this case we get the answer for all positive even numbers. But in fact, the numbers between $1$ and $n$ always sum up to $n(n+1)/2$, also for a positive odd number $n$ such as $101$. We invite you to come up with your own argument for this. Even for $n=0$, the theorem works if we use the convention that there are no numbers “between $1$ and $0$”, so the sum is $0$ in this case. This means, we in fact have

There is the related concept of a (mathematical) constant that simply gives a short name to a long number. For example, if we keep talking about the number $299792458$ (the speed of light in $m/s$), we could start with “Let $c=299792458$,” and then simply say $c$ whenever we mean $299792458$.

Variables are not only used in theorems. Mathematicians use them whenever they want to say something about all numbers (or other mathematical objects) of some kind. A typical use case is a sentence such as “We use $\sqrt {x}$ to denote the square root of a nonnegative number $x$.” This tells us what $\sqrt {5}$ means, but also $\sqrt {1.3}$ or $\sqrt {0}$, as the variable $x$ can stand for all these numbers. In fact, in the first reading assignment we have already used variables such as $S_1$ and $S_2$ standing for true‐false statements. Back then, we called them placeholders, but the term variable is more appropriate for (mathematical) grown‐ups.

2Sets

A set is a “bag” of elements, possibly infinitely many. These elements are typically numbers or some other entities. They are in the bag in no particular order, but no element occurs more than once. Sets are written in curly braces, and in between, we just list the elements. For example, the set of even numbers between $1$ and $10$ is $\{ 2,4,6,8,10\}$, and the set of odd numbers between $1$ and $10$ is $\{ 1,3,5,7,9\}$.

We can also write this as $\{ 1,7,5,9,3\}$, as order doesn’t matter. But typically, the elements are displayed as a familiar sequence, just to make it more readable. We could even write $\{ 1,3,3,1,5,7,7,9,9\}$, and this would mean the same thing as $\{ 1,3,5,7,9\}$, since duplicates are simply ignored. If a set has many elements, we use abbreviations. For example, the set of numbers between $1$ and $100$ is typically written as $\{ 1,2,...,100\}$, and the set of odd numbers between $1$ and $100$ as $\{ 1,3,..., 99\}$, or $\{ 1,3,5,..., 99\}$ to make the pattern even clearer. As the dots notation is very practical but not mathematically rigorous, we have to be careful to avoid misunderstandings.

The set of integers between $1$ and $n$ is $\{ 1,2,...,n\}$, so variables can also naturally be used in sets.

The empty set (a bag containing nothing) is written as $\{ \}$ or $\emptyset$. Elements may also be (text) symbols, such as in $\{ \uparrow ,\downarrow ,\rightarrow ,\leftarrow \}$, or $\{ \text {True}, \text {False}\}$.

Just as for numbers, there are also set variables and set constants, as in “Let $S$ be a set of $n$ numbers,” or “Let $S=\{ 1,3,5,7,9\}$.” Sets are usually denoted with upper‐case letters, sometimes calligraphic letters such as ${\mathcal S}$.

Sets of numbers.So far, when we said “numbers”, we in fact meant natural numbers, the numbers we use for counting. There are infinitely many natural numbers. We could write the set of natural numbers as $\{ 0,1,2,...\}$ (computer scientists typically start counting from $0$ instead of $1$). For the set of all integers (positive or negative), something like $\{ ...,-2,-1,0,1,2,...\}$ would work. But this notation is a bit cumbersome, so it is more common to use standard names for such sets: $\N$ for the set of natural numbers and $\Z$ for the set of integers.

The symbol $\R$ denotes the set of real numbers (the infinite bag containing all numbers that we typically deal with, including integers, decimal numbers such as $0.5, 0.346$, fractions such as $\frac {1}{2},\frac {3}{7}$, square and third roots such as $\sqrt {2}$, $\sqrt [3]{15}$, and other special numbers such as $\pi =3.1415926...$

By $\R _+$, we denote the set of nonnegative real numbers (numbers greater or equal to $0$); $\R _-$ is the set of nonpositive real numbers (numbers smaller or equal to $0$). There are also more exotic numbers, called complex numbers, and in fact, the number of possible kinds of numbers that mathematicians can come up with is infinite. But we will only need $\N ,\Z ,\R$, sometimes $\R _+$ and $\R _-$.

As it is not always clear what we mean when talking about “a number”, we should generally say what kind of number we mean. For example, the Theorem “Kleiner Gauß” can without ambiguity be stated as follows: Let $n$ be a natural number. Then the sum of all natural numbers between $1$ and $n$ is $n(n+1)/2$. But in this case, the extra precision is unnecessary. By “all numbers between 1 and $n$”, even mathematicians mean the natural numbers $1,2,...,n$.

Variables that stand for natural numbers or integers are in most cases called $i,j,k,\ell ,m,n$. Variables that stand for real numbers are often called $x,y,z$.

The mathematician immediately sees a general theorem here: Let $n$ be a natural number. There are $2^n$ sets with elements between $1$ and $n$. In fact, as we already have a symbol $\N$ for the set of natural numbers, we can use it and abbreviate “Let $n$ be a natural number” by “Let $n\in \N$.” Here, the symbol $\in$ stands for “element of”, so that the abbreviation literally says “Let $n$ be an element of $\N$.” The theorem then reads as follows.

3Tuples

A set is an unordered bag of elements. When we care about the order, we use tuples. A tuple is a “list” of elements where elements may also occur more than once. Tuples are written between normal braces. For example $(2,5,2,6,3)$ has five elements and is called a 5‐tuple. Here $2$ comes first on the list, then $5$, then $2$ again, and so on. You can for example imagine that this tuple records the results of rolling a dice five times.

Hence, $(2,5,2,6,3)$ is not the same as $(5,2,2,6,3)$. 2‐tuples are also called pairs, 3‐tuples are triples, and 4‐tuples are quadruples (a term already less common). You occasionally still hear about quintuples, but anyone saying sextuple or septuple is probably a nerd. There are 1‐tuples and even 0‐tuples, written as $()$, but they are rarely needed. The dots notation $(1,2,...,10)$ naturally also applies to tuples, and even $(1,1,...,1)$ makes sense if we also say how many elements the tuple has. There are no infinite tuples; lists with infinitely many elements are called sequences.

Tuples are typically denoted by lower‐case letters (“Let $p=(1,2)$”), sometimes in bold to distinguish them from numbers (“Let $\mathbf {p}=(1,2)$”).

There is a fundamental difference between sets and tuples; even if $\{ 1,2\}$ and $(1,2)$ seem to be the same, they aren’t. In $\{ 1,2\}$, there is no order between $1$ and $2$, while in $(1,2)$, $1$ comes before $2$. This isn’t just mathematical sophistry, it really lets you express different things; for example, if you want to say who competed in the 2018 world chess championship, you would write $\{ \text {Carlsen},\text {Caruana}\}$, but if you want to talk about the outcome, you would write $(\text {Carlsen},\text {Caruana})$.

Here is the mathematical theorem behind the previous exercise, this time with $2$ variables.

A tuple such as $(6,5,6,4,3)$ whose elements are numbers is typically called a vector. In contrast to tuples such as $(\text {Ich}, \text {bin}, \text {ein}, \text {Berliner})$, we can compute with vectors, but we will get to this only in later reading assignments. Vector variables are typically called $u,v,w$.