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

3 comments on “MIU-System

  1. Curtis Gross says:

    I tried the exercise. I don’t think it’s possible. I can only double the number of I’s in my statement, and reduce by 3. A power of 2 will never be able to reduce to 0 by subtraction by 3.

    Unless there is some combination of the theorems that I’m not thinking of.

  2. Excellent thoughts Curtis! Anyone else give it a try?

  3. Louis says:

    “They are meaningless.”

    That is possibly false.

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