1 - Definitions and notations

Summary

This chapter is designed to be read in sequence, not merely referred back to. There are even exercises in it to encourage the reader.

Things in boldface are usually being defined. Things in italic are being emphasised. Some exercises will be collected at the end of each chapter, but there are many exercises to be found in the body of the text. The intention is that they will all have been inserted at the precise stage in the exposition when they become doable.

I shall use lambda notation for functions. λx.F(x) is the function that, when given x, returns F(x). Thus λx.x² applied to 2 evaluates to 4. I shall also adhere to the universal practice of writing ‘λxy.(…)’ for ‘λx.(λy.(…))’. Granted, most people would write things like ‘y = F(x)’ and ‘y = x₂’, relying on an implicit convention that, where ‘x’ and ‘y’ are the only two variables are used, then y is the output (“ordinate”) and x is the input (“abcissa”). This convention, and others like it, have served us quite well, but in the information technology age, when one increasingly wants machines to do a lot of the formula manipulations that used to be done by humans, it turns out that lambda notation and notations related to it are more useful.As it happens, there will not be much use of lambda notation in this text, and I mention it at this stage to make a cultural point as much as anything.