I’m going to be completely selfish for a few posts here. As I have said I have a fascination with Godel and his incompleteness theorem. I have read a few books in the past on the topic and while I get glimpses of understanding about the theorem, after a few days I seem to have lost all lucidity around what the theorem ultimately means. It just leaks through like sand through my hands.So I am basically going to take some time and make some condensed notes on this site so I can always come back and brush up. And hopefully avoid constantly returning to some of the tomes on the subject.
The first concept I want to lay out is that of a formal system. Through Godel, Escher, and Bach (GEB) I understood the mechanics of what Hofstadter was doing but not the meaning he was clearly trying to get across. Rebecca Goldstein has done that in the course of a few pages. Wonderful. What is a formal system?
Let’s take a step back. Mathematicians want to do math. And when they do math they want their math to be ‘true’. And by true I mean absolutely true. So one needs a starting point to develop theorems. One can approach the problem by creating a set of basic truths (axioms). With these axioms we can apply rules of inference that are perfect laws of ‘truth inheritance’ (if what goes in is true, then what comes out is true). Good God what does that mean? Let’s take an example. Euclid deduced there were 5 axioms (The Elements) for geometry. From these 5 axioms, one can apply rules of inference to create new truths (theorems; e.g., the sum of all angles in a triangle = 180°). It’s not important for now what these axioms are. What's important is the approach. Create axioms (hopefully as few as possible) and then build math theorems from them through inference.
You’ll notice we have a problem. If we never proved the axioms how do we know they are true? Good question. For a while people overlooked this problem because the axioms seemed so self-evident that they didn’t need proving. However 3 mathematicians simultaneously noticed that if you change an axiom (e.g., ‘parallel lines never intersect’ to ‘parallel lines intersect twice’) you create an entirely new and self-consistent geometry. In this case you move from planar geometry (flat land) to spherical geometry. 2 parallel lines on a sphere (circles) can intersect twice - think of 2 sets of longitudinal lines intersecting at both poles. And in fact if you put a triangle on a sphere the sum of the angles do not add up to 180°. Okay so that didn’t work out so well.
Let’s try formal systems. Actually Hilbert (he's the one above) is the one who tried. I’ll be damned if I understood what these were before. Ignore mathematics for a second. Take chess. There are rules about the pieces – how they can move on the board. At any given time on a chessboard the layout of the pieces (assuming no one cheated) constitute a valid chess piece arrangement. Nothing fancy here. Just some rules that we apply to things to create patterns on a board. In essence, these rules about chess are a formal system.
Now imagine if these patterns related to something in the real world. Say for example how 32 pebbles would arrange themselves onto a chess board if they were dropped. Every single time you dropped 32 pebbles they would always fall on board in a manner that could be created by the rules of moving chess pieces. This obviously isn’t the case but just imagine it was. Then from these chess rules (the formal system) we have created a ‘math’ of how pebbles fall onto boards. We interpret the chess pieces that have followed the formal system to represent a theorem of how the pebbles could fall onto a chess board. By definition if you violated a rule (moved a bishop off his color) we would know that 32 pebbles could never fall into that pattern.
Back to math. Formal systems are nothing more than a set of rules. Instructions. There are an infinite number of formal systems. These rules could apply to a bunch of squiggles or chess pieces on a chessboard. Let’s say there are 2 kinds of squiggles. And let's say there are 2 rules. 1) When two of the same squiggles, moving left to right, are next to each other I can add a P to the end of them. 2) I can start out with any combination of squiggles. So by rule 2 I can have
ҰҐҐҐҐ
or
ҐҐҐҰҰҰҐ
These are 2 ‘well-formed’ things in my formal system. Applying my first rule I can make 2 new well-formed things.
ҰҐҐPҐҐP
and
ҐҐPҐҰҰPҰҐ
So what? Well the ‘what’ is there is nothing ‘untrue’ about what I’ve done. I’ve simply made some symbols and I can apply rules to them. By definition there is nothing untrue, nothing ‘axiomatic’ about what I’ve done. There's nothing untrue about the positions of the chess pieces on the board. Now there are things in my system that would be untrue (e.g., ҐP is not a valid thing since I don’t have 2 squiggly symbols behind the P). So there’s no leap of faith in believing what I’ve done above is ‘true’ as long as I don’t break any of my rules.
The ‘aha’ comes from going back to our chessboard. Hilbert was smart enough to realize that these well-formed strings (if you pick your rules carefully) can actually be theorems about math. You just need to interpret the symbols as meaning something mathematical. In fact Hilbert showed that you could create a formal system using rules and squiggles and if you interpreted the squiggles and symbols in a particular way to mean arithmetic operators and numbers, it mimicked true arithmetic (e.g., manipulation of natural numbers). One could then use this formal system to create new things and these things would be true theorems about arithmetic. With nothing more than a bunch of rules and squiggles you can make theorems about arithmetic. That is the beauty of a formal system. It gets around your axiomatic problem of a theorem being true. It is true by nature.
While Hilbert was doing this Godel was working with him. And he was about to throw a wrench into formal systems...
No comments:
Post a Comment