MIU-System

Previously, we explored the nature of formal systems in a more technical manner.  In this post I hope to illustrate the concepts and features of formal systems via a toy formal system called the MIU-system.  Douglas Hofstadter introduces this system in his book Gödel, Escher, Bach: An Eternal Golden Braid.  Let’s see how it works.

In case you haven’t already guessed, the finite set of (meaningless) symbols in this case is S = \{M, I, U\}.  Why these symbols?  Well, it doesn’t matter.  They are meaningless.  But if you hate them, you are more than welcome to swap them out with your favorites.

With this “alphabet” one can make all sorts of finite strings (a countably infinite amount).  For example,

IUUUMMIUIUM, ~~ MMMMI, ~~ UMMMM

The syntax of this system is very easy.  All strings made up of symbols from \{M,I,U\} are legitimate.  So, the examples I gave above are actually wff’s.  But remember, we don’t currently “possess” any wff’s.  What we need is a set of axioms.

This particular system is an example of one that is finitely axiomatized.  In fact, it has but one axiom.

Axiom: MI

This means that the only wff in our possession to work with is the string MI.  Okay, but what can we do with it?  This is where we need a set of inference rules.  There are four.

(1) If you possess a string ending in I, you can add a U to the end.

Here is a good place to point out, as Hofstadter does, that in any string order matters!  One must always be careful not to assume that certain relational properties hold that aren’t given by the inference rules.  For instance, one cannot assume that symbols are interchangeable – i.e. commutative.  MI is not the same as IM; MIU cannot be swapped out with MUI.  They are different strings.

(2) Let x be any string.  Then if you possess a string of the form Mx, you also possess Mxx.

For example, suppose we had the string MIUU  Then, in this case x = IUU and hence we would get the string MIUUIUU.

(3)  If III occurs anywhere within a string in your possession, you may replace III with U.

For instance, suppose we have the string MIUIII.  Then we also get the string MIUU.

(4)  If UU occurs anywhere within a string in your possession, you may drop it.

So, if we had the string MIIUU, then we would also have MII.

With these four inference rules and the axiom string MI, we can proceed to produce theorems for our MIU-system.  Note that because we have MI we can immediately apply (1) to get MIU as part of our collection.  We can alternatively apply (2) to MI to get MII.

One thing you will quickly notice is that all theorems of the MIU-system begin with M.  However, it is not the case that every string beginning with M is a theorem.

Here is an exercise:  Given MI, can you produce MU?  If so, show how.  If not, explain why not.  (I’ll post a solution at some point)

In the next post I’ll talk a little about a decision procedure for the MIU-system and then we’ll move on to other matters.

Advertisements

A Philosophical Interlude

Before playing with any toy formal systems, I would like to take a moment to express another philosophical motivation for adopting Tegmark’s proposal.  For a long time I have been bothered by the apparent distinction between actuality and possibility.  In other words, what does it mean for something to be actual as opposed to merely possible?  I have always felt that to make a substantial distinction between actuality and possibility, one is forced to invent strange modes of existence, one for some “diminished” level of existence or bizarre non-existing existence, and one for a “distinguished” level of existence or “real” existence.  I cannot help feeling that this is quite artificial.  In the set of all possible worlds, why should there be a distinguished member?

From our perspective, of course, this seems intuitive.  We experience some things as “actual” and other things we recognize as possible, but they do not obtain in our world.  In other words, some things could be, but are not.  Yet, to draw a strong distinction seems a mistake akin to thinking that the Earth is the center of the universe because it appears that way from our perspective.  In reality, there is no preferred point in space and, by analogy, it seems reasonable that there is no preferred possible world either.

Being a form of modal realism, this is the thesis of the MUH.  All possible worlds exist on equal footing.  They are all of the same kind as our world.  Ironically, looking at matters this way gives coherent meaning to the terms “actual” and “possible”, but instead of inventing convoluted or mysterious modes of existence, these become relative terms.  The term “actual” simply refers to the world in which we find ourselves and “possible” refers to any other world.  Of course, in any other world, its inhabitants, if it has any, will consider their world to be actual and ours to be possible.  Another way of saying this is that actuality is indexical.  Again, one can use relativity as an analogy.  Each system has its own “preferred” (with respect to itself) reference frame from which it judges everything else.  Objectively speaking, however, no reference frame is preferred over another.  Or think of how each person deems his/her location as ‘here’.  There is no objective ‘here’, it depends on the observer.

This brilliant solution is just one of the many recommendations the MUH enjoys!

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.

Mathematics as Reality (Introduction)

One of the most interesting and provocative ideas to emerge from the intersection of mathematics, philosophy, and physics is the proposal, by MIT cosmologist Max Tegmark, that our universe is a mathematical structure.  Everyone knows that mathematics is indispensable for understanding our universe, but the Mathematical Universe Hypothesis (MUH) says something rather more remarkable.  Two of the most salient questions in all of philosophy are:

(1) Why is there something rather than nothing?

(2) Why is mathematics so effective in describing reality as we know it?

The profundity of these questions is quickly made manifest upon the slightest reflection.  MUH is an ambitious, albeit ingenious, solution to the inherent problems raised in these two questions.  It postulates that reality is mathematics in a very real and well-defined sense; more specifically, physical existence equals mathematical existence. One might describe such a view as a form of radical Platonism or, equally, a mathematical version of modal realism.  In fact, these are the very descriptions employed by Tegmark himself.  As such, MUH answers (1) because it entails that there really is no such thing as an ontological nullity or universal negation.  Something necessarily exists, namely all possible mathematical structures, which Tegmark refers to as the Mathematical Ensemble or Level IV Multiverse.  It also answers (2) by making it trivial.  Certainly, if reality is mathematics, then science is merely the endeavor of uncovering how our particular mathematical system operates or behaves.

Now, as a mathematician, this suggestion resonates with me and isn’t so hard to imagine being the case.  For most people, however, MUH probably sounds outlandish at best, if not incoherent!  After all, what could it possibly mean for reality to be mathematics?  You mean, the chair I’m sitting on is no different than the equations I write down when doing my math homework?

I grant that, at first sight, the idea seems a bit absurd; but  the fog begins to lift, I think, upon a reflection of what mathematics really is.  It is my hope to explore, and clarify, this most fascinating idea in a series of posts.  Included in this investigation will be an incorporation of Douglas Hofstadter’s ideas espoused in his landmark work, Gödel, Escher, Bach: an Eternal Golden Braid, which, I believe, specifically fleshes out Tegmark’s notion of a Self-Aware Sub-Structure (SAS).  On Tegmark’s (and presumably Hofstadter’s) view, a human would be an example of a SAS.  Hofstadter, however, uses the terminology “strange loops” or “tangled hierarchies”.

These posts are primarily for my own benefit, to engage these ideas and to deepen my understanding.  But for anyone who might be reading this blog, I hope that what I write is both interesting and enlightening.  Of course, if I totally botch something or if clarification is needed or if there are other ideas that would be interesting to fit in, please feel free to contribute and participate in the comments.  Happy reading.