3 - Set theory

Summary

Introduction

Suppose that we are using the notations of mathematical logic, as described in Chapter 2. We have some universe of discourse E, and let us suppose that a predicate R(x) is given. We could look at the objects in E in turn, and check for each object whether or not R(x) is true. If we then selected the collection of objects which made R(x) true, we would have what is known as a set.

Although the predicate calculus allows us to do anything we desire, it has been found over the last century or so that set notation is far more convenient and natural. A predicate in one variable is thought of as expressing a property of objects in the universe of discourse; a set is the collection of all those objects with that property. Conversely, given a collection of objects in the universe of discourse, we can form a predicate which expresses the property of being in that collection. Sets and one place predicates are completely interchangeable.

Example 3.1 A username for an Apostrophe computer consists of a string of six letters and digits. The director of computing services is responsible for informing the Apostrophe which strings are valid usernames. This he does by creating a file of valid usernames. If there are 500 users of the Apostrophe, the file will have 500 lines. The 2,176,782,336 possible usernames have been reduced by a factor of around 4 million.