Mathematics for Game Developers

Part 0: Fundamentals

Last time I made the great mistake of leaping straight in at numbers, forgetting some of the important background.  So today, instead of the integers I promised, I’m going to cover sets.

Sets are ubiquitous in mathematics.  Many definitions are of the form ”a whatsit is a set of doodads with this additional structure”, and as we glimpsed last time, they can also be used as the basic atoms out of which everything is built.

Definition

Fortunately, they are simple things, as long as we keep the discussion fairly informal.  A set can be regarded as a collection of things.  A set is a thing, so sets can contain other sets.

Given a particular set and a particular thing, the thing is either a member of the set or it is not.  The symbol .

But as Bertrand Russell was preparing his book Principles of Mathematics for publication (in around 1902, I believe), he discovered a problem with this definition.  There is nothing stopping us defining a set which contains all sets that do not contain themselves.  If this set is a member of itself, then it is not a member of itself.  And if it is a member of itself, then it isn’t.

This paradox was a serious problem.  Russell delayed publication by a year while he tried to find a way around it, eventually deciding to publish anyway with a warning, and his work on a theory of types (a not particularly satisfactory attempt at a solution) as an appendix.

By the mid-1920s, work by a number of mathematicians (most significantly Zermelo and Fraenkel) finally produced a solid foundation.  The Zermelo-Fraenkel axioms, as they are known, are rather technical, and require more background than I have the time or patience to provide here.  But the basic idea is relatively simple: start with the empty set, and then repeatedly build new sets out of the ones you already have.  At each step, you can only use sets that had been built in previous steps, so you can never have sets that contain themselves, and Russell’s Paradox is avoided.

I intend these posts to stay relatively informal, so naive set theory, as it is called, should be good enough for us.

And next time… probably no integers, sorry.  I have to introduce you to relations first.