## Monday, March 20, 2006

### 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.

• " x + y =

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

On the first read-through I thought you were using + in your definition of it, then I realized this is a procedure to follow rather than a definition. The test in the first step, which yields y as the result when x=0, is repeated after each successive application of the second step until x=0. Is that the intended meaning?

By  Jim Lippard, at 8:08 PM

• Yes, Jim, that's right.

I forgot that recursive definitions aren't second nature to most people. I'm definitely still in the process of learning to write about math for people who are not mathematicians.

Thanks for the help clarifying that!

By  MarkCC, at 8:19 PM

• Yes, I've been drawn up short by trying to explain mathematical ideas to non-mathematicians. And I've gotten some funny looks from people when I've told them that the maths I like best don't have numbers. So I'm looking forward to seeing what you do with this site.

What are you planning to say about models? And you have an earlier post where you are using graph theory. I think that there would be several interesting ideas about graphs that you could present fairly simply and without much background. Graphs are fun.

By  driftwood, at 9:01 PM

• Driftwood:

Glad your enjoying the site. I'm not quite sure what I'm going to say about models. Something along the lines of what Gunter did in his programming language text, because that's what made it finallyl make sense to me.

And I'm definitely looking forward to doing some fun stuff with graph theory: it's an interesting kind of math that most people aren't familiar with, but which is still concrete enough that it's comprehensible if you use enough examples.

By  MarkCC, at 9:15 PM

• Good

By  driftwood, at 11:08 PM

• markcc - I'm not a professional mathematician but I have a degree in mathematics and I didn't realise what was going on in your definition of addition either ... has to be said, though, when I was at university in the early '80s the computer was in a separate building and ran on punch cards so I'm not used to seeing programme-type ("recursive") definitions.

apart from that, nice clear post!

By  Andi Chapple, at 6:34 AM

• Well, recursive statements as definitions or processes, unlike jim, I'm still fuzzy on them. And like andi, my introduction to computers was back in the day of evil-evil punchcards. The first and third statements make sense, but not how the second relates to them. Can you explain how you are using the term "recursive"? I suspect it has a slightly different flavour in this realm.

Everything else in the post made sense though, and that's a statement from a non-math major. Man, I think it's been nearly four decades since I was introduced to set theory; glad to see it's still there in my head!

andrea

By  andrea, at 8:48 AM

• Well I have a Bachelor's degree in Mathematics and all this was old familiar material to me, however NOT because of my degree, but because of the free elective I took from the Philosophy department 13 years ago.

Phil 401 Set Theory :

By  Anonymous, at 10:24 AM

• And the recursive definition was obvious because when I completed my Math degree, I switched universities and got a Computer Science degree. (Most languages allow recursion, but it is discouraged. However some languages are built entirely on recursion - e.g. LISP)

The recursion should also be familiar to anyone with a Math degree (e.g. Newton's method).

By  Anonymous, at 10:30 AM

• It's not just math that is taught poorly, it's also arithmetic. I discovered that my son was taught addition and subtraction on his fingers badly. He'd get the right answer only one in three times. He'd get off by one answers in both directions. It would be funny if it weren't so sad.

I've started teaching arithmetic to children - starting with addition and subtraction on their fingers. There are techniques that are fast and reliable. Without both features, people are afraid of arithmetic. Further math, and any subject that depends on math, like science, engineering, coping with a checkbook, becomes all but impossible for these people.

I have mentioned it on my blog. No real details though. That's something to do. There is a little on my web site.

By  Stephen, at 3:34 PM

• This comment has been removed by a blog administrator.

By  DJS, at 4:25 PM