Mathematics as Reality: Formal Systems

Before discussing how it might be that reality is mathematics, it would be a good idea to give consideration to what mathematics, itself, really is.  In other words, we need to understand what is meant by a mathematical structure.  The quick answer is that a mathematical structure is a formal system.

Formal systems are an important part of the foundations of mathematics.  So, by a mathematical structure we shall mean some kind of formal system.  But what is a formal system?  We’ll address this question by considering the various “ingredients” that go toward making a formal system.

\fbox{First Ingredient}

The first essential feature of a formal system is a finite set S of symbols.  These symbols form something of an “alphabet” and are sometimes referred to as primitive symbols.  Such symbols are inherently meaningless in the sense that they have no referents outside of themselves.  By way of contrast, the word “moon” refers to the spherical body orbiting our planet:

The word “moon” has meaning, since it has a referent to something existing in the actual world.

The elements of S, however, are abstract entities, mere labels, with no intrinsic meaning.  Sometimes it is tempting to see meaning in certain sets of symbols because of familiarity or various other reasons.  For instance, the symbols +, -, \times, = are immediately interpreted as meaning the familiar concepts of adding, taking away, multiplying and equality respectively.  This is largely a matter of habit and convention, but nothing about the symbols themselves requires them to take on these meanings, or any meaning for that matter.  In another post we’ll consider how meaningless symbols take on a sort of meaning by force, as it were.  This is part of Hofstadter’s thesis, namely that

“…meaning cannot be kept out of formal systems when sufficiently complex isomorphisms arise.  Meaning comes in despite one’s best efforts to keep symbols meaningless!”

For now, what can one do with such meaningless symbols?  That such symbols form an “alphabet” is suggestive.  The essential idea is to create “words”.  By “words” is meant finite strings of these primitive symbols.  The set of finite strings, of course, is countably infinite.  For example, if the set of primitive symbols is \{p,q, !,@\}, then the set of all finite strings would include:

ppqp!,~~~ @p!q!qq!@pppq,~~~ !@!@!@!@!@

Now, creating finite strings of meaningless symbols isn’t all that interesting on its own.  This leads us to our next ingredient.

\fbox{Second Ingredient}

The second ingredient is a grammar or syntax, which governs the way “words” are formed.  In other words, not just any finite string will do.  Based on the grammar or syntax, some strings will be considered well-formed and others not.  This is not unfamiliar.  The same idea exists in natural language.  In English, the word “formed” is well-formed, whereas “sbbkdvkd” is not well-formed.  In logic, the string p\wedge (q\to r) is well-formed, while \to\wedge pp is not.

These legitimate “words” are generally referred to as well-formed formulas (wff’s).  So, syntax provides a set of rules that define how to create wff’s.  It is also generally required that there be a decision procedure that allows one to decide whether a particular string is well-formed or not.  Such a decision procedure can be thought of as some sort of criteria that must be met, which indicates whether or not a particular string has an appropriate form.  As an example, let us return to logic.  The primitive symbols reside in the set

S = V\cup L

where V is an arbitrary set of propositional variables (usually letters) and L is the set of “usual” propositional connectives, along with the “grouping” symbols “(” and “)”.  One can then define wff’s as follows:

(1) Every member of V is a wff (these are called atomic formulas).

(2) If x is a wff, then so is -x (“-” is considered a unary connective).

(3) If x and y are wff’s and \cdot is any binary propositional connective, then x \cdot y is a wff.

Some examples of binary propositional connectives are \leftrightarrow, \to, \wedge, \vee.

From (1)-(3), it is now clear why p\wedge (q\to r) is well-formed, but \to\wedge pp is not.  In fact, given any finite string of symbols s, our decision procedure allows one to determine whether or not s is a wff in a finite amount of time.

Step One: Check if s \in V.

If so, then stop.  If s\notin V, then proceed to step two.

Step Two: Check if s = -v, where v\in V.

If so, then stop.  If not, proceed to step three.

Step Three: Locate all binary connectives in the string and check that each connective component is a wff.  Note that elements of V cannot be concatenated, but must be separated by binary connectives.

Okay, having an “alphabet” and an infinite set of wff’s is great, but still not terribly interesting.  Let’s see what else is needed for a formal system.

\fbox{Ingredient Three}

With the appropriate building materials, we now need a foundation on which to build our formal system.  By “foundation” is meant  a set of axioms.  These axioms are wff’s, which are taken as given, a starting scheme or a choice of “seeds”, if you will, which will grow into our system.  In other words, even though we have an “alphabet” and well-formed formulas, none of them are really in our possession at this point.  Thus, we need an axiom schema, which stands for a countably infinite set of axioms.  Often, one can define these recursively.  There are also systems which can be finitely axiomatized.  One can think of axioms as “true statements” of the system one gets for free.  Let’s consider a well known example of the former type, namely the Peano axioms for the natural numbers \mathbb{N}.  There are several equivalent ways to formulate these axioms, but the following is a common way of presenting them.

A_1: 0 is a natural number.

Here 0 is a constant symbol and is given to us as a natural number.  The next few axioms deal with the relational properties of the symbol “=”, which is interpreted as equality.

A_2: For any natural number x, x = x.

This axiom seems funny, but it says that “=” is a reflexive relation.

A_3: For all natural numbers x and y, if x = y, then y = x.

This means that “=” is a symmetric relation.

A_4: For all natural numbers x, y and z, if x = y and y = z, then x = z.

So, “=” is a transitive relation.  Taken together, axioms A_2A_4 allow us to say that “=” is an equivalence relation and, hence, is why we call it “equality”.

A_5: For all a and b, if a is a natural number and a = b, then b is a natural number.

This axiom means that the natural numbers are closed under equality; we don’t get any weird or unwanted objects in \mathbb{N} via some bizarre equality.

For the last set of axioms, let S : \mathbb{N}\to \mathbb{N} be a function, called the “successor” function.  Our notation, here, is suggestive.  It embodies the following axiom.

A_6: If n is a natural number, then so is S(n).

Since A_1 gives us a starting natural number, we get the natural number S(0), which is defined to be 1, the “successor” of 0.  Applying S again we get the natural number S(S(0)) = S^{2}(0) or S(1), which is defined to be 2, the “successor” of 1.  In general, S^{n}(0) = S(n-1) is taken to be the natural number n, the “successor” of n-1.

A_7: For every natural number n, S(n) \neq 0.

In other words, 0 is not the successor of any natural number.  Thus, 0 is truly the “beginning” of the natural numbers.

A_8: For any natural numbers n and m, if S(n) = S(m), then n = m.

Thus, S is an injective (i.e. one-to-one) function.  Finally, we have

A_9: If M is a set such that (i) 0 is a member of M and (ii) for every natural number n, if n\in M, then S(n)\in M; then M contains every natural number.

This is called the induction axiom.  From these axioms, one can derive all the properties of the natural numbers.

With axioms in hand, things are beginning to get interesting.  But before one can get anywhere with the axioms, one needs a mechanism or a means with which to build off of the axioms.  This leads to the final ingredient of a formal system.

\fbox{Ingredient Four}

The final ingredient necessary for a formal system is a set of inference rules, that is, a set of rules for transforming one string of symbols into another.  These rules can be applied to the given/free wff’s provided by the axioms to obtain new wff’s , which are called theorems.  All wff’s provided by the axioms are theorems.  We might say they are complimentary theorems.  All other theorems are derived from the axioms via the rules of inference.  So, if the axioms are the “seeds”, the inference rules determine what these “seeds” can grow into or what kind of system they can produce.  Now generally, one desires that the inference rules be recursively defined in the sense that there is a decision procedure for determining if some string is a theorem or not as in the case with wff’s.

To prevent this post from getting too long, the next post will explore a toy formal system introduce by Hofstadter called the MIU-system.  This will give us occasion to understand the concepts of this post better, especially the idea of a set of inference rules.

Advertisements

3 comments on “Mathematics as Reality: Formal Systems

  1. scullytr says:

    A lot of equations that fly just out of my comprehension, but I think I understand what you’re getting at: Mathematics is a “Formal System”, which, as I understand it, is an established, documented, and understood process for doing, or (for the purpose of this discussion) understanding something, which (being sort of a formal system in and of itself) contains each of the ingredients mentioned above. Am I correct? That might be an oversimplified definition. 🙂

  2. I think you are getting the right idea. First you get some symbols, then you create an appropriate way of arranging those symbols. Next, you provide yourself with a starting point – i.e. axioms. And finally, you need some rules, which tell you how to get from one string of symbols to another. You then apply these rules to the axioms and see what theorems “pop” out.

    I’ll be going over this again from a slightly different perspective, which is given by Tegmark. The essential idea is that you have a set of symbols which relate to each other in certain ways. That is, they behave according to certain rules. Think of just plain old natural numbers {1,2,3,4,…} along with the operation of addition. These are just symbols, but, here, they behave/interact according to certain rules – e.g. 5+7 = 12 or 3+2 = 2+3.

    Computer languages are another good example.

  3. Also, thank you for commenting and participating with me. That means a lot. It helps make me feel that I am doing something worthwhile.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s