Mathematics For Computer Scientists

by Thorsten Altenkirch

Mathematics for Computer Scientists (G51MCS)
1 Types and sets
What is a set? Wikipedia 1
says
Informally, a set is just a collection of objects considered as a whole.
And what is a type? Wikipedia offers different definitions for different subject
areas, but if we look up datatype in Computer Science we
In computer science, a datatype (often simply type) is a name or
label for a set of values and some operations which can be performed
on that set of values.
Here the meaning of type refers back to the meaning of sets, but it is hard
to see a substantial difference. We may conclude that what is called a set in
Mathematics is called a type in Computer Science.
Here, we will adopt the computer science terminology and use the term type.
But remember to translate this to set when talking to a Mathematician.
There is a good reason for this I am going to use the type system of
the programming language Haskell to illustrate many important constructions
on types and to implement mathematical constructions on a computer. Please
note that this course is not an introduction to Haskell, this is done in the 2nd
semester in G51FUN. If you want to find out more about Haskell now, I refer
to Graham Hutton’s excellent, forthcoming book, whose first seven chapters are
available from his web page 2
. The book is going to be published soon and is
the course text for G51FUN. Another good source for information about Haskell
is the Haskell home page 3
While we are going to use Haskell to illustrate mathematical concepts, Haskell is
also a very useful language for lots of other things, from designing user interfaces
to controlling robots.
1.1 Examples of types
I am sure there are some types you already know since primary school. E.g. the
type Nat of natural numbers, which are the numbers we use for counting. In
Computer Science we include the 0 to allow for the case that there is nothing
to count. We can start enumerating the elements of Nat
Nat =
We follow the mathematical tradition to use curly brackets when enumerating
the elements of a type. Clearly, this is not a precise definition because we
have used . . . to indicate that we can go on forever. We will fix this later.
Most Mathematics books will use N for Nat but in Computer Science we prefer using names made up from several letters (because we can type them in on the keyboard) while the mathematicians like single letters but use different
alphabets (that’s the reason that they use so many Greek symbols).
We write 2 ∈ Nat to express that 2 is an element of Nat, we may also say
that 2 has type Nat.
4 If you have a bank account or a credit card you will also know the type of
integers, Int which extends Nat by negative numbers - in Maths one writes Z.
Using the suggestive . . . again we write
Int =
Other types of numbers are the rational numbers Rat (Q) which is the type of fractions (e.g. 2 / 3 ∈ Rat), the type of real numbers Real (R) (e.g.2 ∈ Real and π ∈ Real) and the type of complex numbers Compl (C)
(e.g. √−1 ∈ Compl). 5 While the latter two (Real,Compl) are a central
topic in Mathematics they are less essential in Theoretical Computer Science,
but relevant in many application areas.
We say a type is finite, if we can enumerate it without using “. . . ”. An impor-
tant finite type is the type Bool of booleans or truth
Bool =
We can define new finite types by using a collection of names, different from each other (these are called constructors).

103 pages, Kindle Edition

Published June 8, 2022