Computability Theory

A1 Mathspeak

The purpose of this appendix is to give a quick summary of everyday mathematical

terminology.

First of all, a set is a collection of things (called its members or elements), the

collection being regarded as a single object. We write “x ∈ S” to say that x is a member

of S; we write “x /∈ S” to say that it is not.

For example, there is the set S whose members are the prime numbers between

0 and 10. This set has four elements, the numbers 2, 3, 5, and 7. We can name this set

conveniently by listing the members within braces (curly brackets):

S = {2, 3, 5, 7}

An important part of the set concept is that what a set is depends solely on what

its members are, and not on how we might choose to name them. We might choose to

name the elements in a ...