Building Math

Some of the things that I find myself saying in comments, or that I'd like to be able to talk about require understanding something about basic mathematics that most people are not taught. I think the way that we teach math is a damn shame, but that's the way things are, at least for now. But it does take a lot of the fun out of it.

Say the word mathematics to most people, and what they think of first is numbers. But numbers aren't the only thing in math - in fact, you can do all sorts of interesting math without numbers.

What math is really about is creating structured systems with formal rules describing what is and is not a valid statement in the system, and for determining what is and is not true in that system.

As I mentioned in some earlier posts, Godel blew a gaping hole in mathematics. But for most purposes, that's OK. We understand the limits that Godel puts on us, and most of the time, we can avoid the problems of self-reference that trigger Godel's incompleteness results.

The reason that numbers are what people think of in mathematics is because that's where it all began. First people thought of numbers, because they needed to be able to count things; and then they started to think about what they meant. The whole edifice of mathematics and logic grew out of there. What we're usually taught in school is mathematics constructed from a combination of number theory and set theory.

For today, I'm going to take basic set theory, and show you how we can build a very simple version of mathematics. What I'll do for today is show you how using sets - and nothing but sets - how we can build numbers, with addition and subtraction operators. To keep things simple, I'll also just stick to the natural numbers - we can construct the other kinds of numbers given nothing but the naturals. (How we do that is a topic for another day - but for now, just remember that we do this with computers - computers only really understand integers, but they can encode other things using sets of integers - ratios, decimals, even irrational numbers.)

So let's start off by recalling what a set is. A set is a construct which can
enumerate some collection of values. What those values are, we'll leave for a few moments. But given a set, we can ask what values it contains. If it's a finite set, we can see the full list of all values. Also, given a set, we can provide a value, and check if the set contains that value. This is called a membership test.

Also, given two sets, we can compute two basic sets from the combination: union, and intersection. The members of the union of sets A and B contain all of the values that are members of either A OR B. The members of the intersection of A and B are all of the values that are in A AND B.

Ok. Now, here's where it gets tricky. There's nothing but sets so far. So the only things that exist are the empty set, the set containing the empty set, and sets built up that way.

To get numbers, we use set wrapping. We use the empty set as zero (and I'll write it as zero as well). One is the set containing the empty set, or { 0 }. Two is the set containing the set containing the empty set, or { { 0 } }.

To get any number at all, we'll define an increment function, and we'll define decrement as the inverse of increment. (We'll talk about what functions are, later.)


inc(x)= {x}
dec(inc(x)) = x


Now we've got numbers. Addition is simple:

x + y =

• if x = 0 then y
  
• otherwise dec(x) + inc(y)
  

Now, we can start thinking about sets of numbers. That's easy - just sets containing our encoding of values.

So, how can we do functions? Well, a function is an infinite set of pairs: the first element of the pair is from the domain of the function, and the second is from the range. So, for instance, the increment function I mentioned up above is an infinite set of pairs:


{ (0,1), (1,2), (2,3), ... (x,x+1)... }


So to represent functions, all we need to do is represent pairs.

Pairs are easy: they're sets with two values. The only catch is that because sets are intrinsically unordered, we need some way of distinuishing the first element of the pair (the index) from the second element of the pair (the value).

So: we divide the numbers into two sets. All even numbers we still treat as numbers, but we treat them as (n/2). All odd numbers are position labels, and we treat them as labeling position (n-1)/2.

So, a pair is just a set of two numbers, one even, one odd. The ordered pair (1,2) would be set-represented as { 3 4 }, or { { { { 0 } } } { { { { 0 } } } } }.

So now we have numbers, pairs, and functions. We can actually do arbitrary tuples with as many values as we want, which lets us do multi-parameter functions. So in fact, we have everything we need to do all of the math that can be done with the conventional math of natural numbers, but it's done in terms of nothing but sets - absolutely nothing but sets.

You can "build" mathematics this way from almost anything. I've seen full mathematical constructions from computing machines, functions (lamba calculus), category theory, bag theory, pure logic, communicating machines (pi calculus), and more.

There is one very big catch to this, and that's called the model. Essentially, the model is a construct in logic that shows that there is a way of making sense out of this. A model, roughly speaking, is one of two things: a set of logic rules that show how the rules of your math can map onto something real; or a set of transformation rules that convert any meaningful statement in your mathematics into a statement in another form of mathematics with a model.

Models are tricky things. It took me a frightfully long time to really understand what they were about, and why people cared about them. I'll do a post (or more likely a couple) about models at some point; but for now, the short version of why you need a model is:

You can define a mathematical system that looks perfectly reasonable, but accidentally contains an error that allows it be totally inconsistent - that is, that makes every statement true: not just good statements, like 3+2=5, but all statements: 1 = 0, A implies -A, 3 + 2 = 27, etc. The model is the grounding that shows that your system is as complete and consistent as a formal system can be.