Process

Starting the puzzle, I’m quite sure that I’ll be able to solve it in a flash. We just discussed a system called “natural deduction” in uni, which I could probably just throw at this puzzle and hope it falls over.

So let’s bring the rules given in the book into the form we learned in uni:

Alphabet

$$ \{\text{M},\text{I},\text{U}\} $$

Inference Rules

$$ \begin{gather*} \begin{prooftree} \AxiomC{} \RightLabel{MI} \UnaryInfC{$\Gamma\vdash\text{MI}$} \end{prooftree} \\[1em] \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{I}$} \RightLabel{R1} \UnaryInfC{$\Gamma\vdash x\text{IU}$} \end{prooftree} \qquad \begin{prooftree} \AxiomC{$\Gamma\vdash \text{M}x$} \RightLabel{R2} \UnaryInfC{$\Gamma\vdash \text{M}xx$} \end{prooftree} \\[1em] \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{III}y$} \RightLabel{R3} \UnaryInfC{$\Gamma\vdash x\text{U}y$} \end{prooftree} \qquad \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{UU}y$} \RightLabel{R4} \UnaryInfC{$\Gamma\vdash xy$} \end{prooftree} \end{gather*} $$

and then set off trying to build a derivation tree for $\vdash\text{MU}$.

Some trying and failing ensues …

Maybe I can simply use R2 over and over again, until I have a number of “I”’s that is divisible by three. Then I could simply add a “U” to the end of the string, turn the last three “I”’s into a “U”, remove the two resulting “U”’s and then simply rinse and repeat until I would be left with “MU”.

But wait … No power of two can be divisible by three … That follows from the uniqueness of the prime factorisation …

So not that then. Maybe the key is using R2 again after having removed the “I”’s, doubling the resulting number …

Oh man, this is more complicated than I’d imagined …

Wait! Maybe it’s just simply not possible?

It follows a attempt at proving “MU” underivable in a system without R3 — with the prospect of then extrapolating that to the whole system. It fails.

Hmm, okay, so R3 has to be the key in this somehow. Maybe we can get it by some repetition of: double the “I”’s using R2; remove 6 “I”’s using R3 and R4; repeat. So looking at the number of “I”’s, that would be a finite sequence of $({}\cdot 2);({}-6)$ operations. Is it even possible to get zero “I”’s from that?

We can try a modulo-test by looking at everything in modulo 3. We’d need:

$$ \begin{align*} &0 \stackrel{!}{\equiv}_3 ((((1 \cdot 2) - 6 ) \cdot 2 ) - 6 ) \dots \\ \dot\implies &0 \stackrel{!}{\equiv}_3 ((((1 \cdot 2) - 0 ) \cdot 2 ) - 0 ) \dots \end{align*} $$

Ooooh waait, I think I see …

My Solution

The MU-puzzle is unsolvable, i.e. in the natural deduction system presented above, MU is not derivable.

Proof: Assume — towards a contradiction — that such a derivation is possible. Let us now examine the change in the number of “I”’s in a string that the application of each rule will produce:

• MI: The amount of “I”’s remains the same.
• R1: The amount of “I”’s remains the same.
• R2: The amount of “I”’s is doubled.
• R3: The amount of “I”’s is reduced by 3.
• R4: The amount of “I”’s remains the same.

Any derivation must start at “MI”, which contains exactly 1 “I”. And “MU” contains 0 “I”’s, so our derivation must start with 1 “I” and then, by some sequence of rule applications, arrive at 0 “I”’s. Hence, by the “I” manipulations presented above, we must be able to start at 1 and then, by some sequence of applications of $({}\cdot 2)$ and $({}-3)$, arrive at 0.

By $3\equiv_30$ and by modular arithmetic, we must therefore have:

$$ 0\stackrel{!}{\equiv}_31\cdot2\cdot2\cdot2\cdot2\cdots $$

This is equivalent to saying that the right-hand term above must be divisible by three. But by the uniqueness of the prime factorisation, a power of two can never be divisible by three.

We’ve arrived at a contradiction, hence no such derivation can exist.

The Author’s Solution

Not yet stated where I am in the book …

Comments

As also stated by the author, it might be interesting to think about whether or not there is a decision procedure for the MU system, i.e. whether or not the language of derivable theorems of the MU systems is recursive.

Maybe we can somehow show that all strings which are not modulo-3-congruent to 0 are indeed derivable? Or maybe even directly how?

I’ll leave this one for the future, I think …

Important

Loose end …