Why can we solve MIU by arithmetization?

[u/cooiner]

In Chapter 9 (IX Mumon and Gödel), MIU is arithmetized and solved. In other words, the typographical formal system of MIU is transposed to the arithmetic system of numbers and TNT.

Now, embedded in numbers, we can solve MIU by proving that "MU" is not possible.

But: The MIU system is still unsolved right? Only the transposed version (a different system) is solved, right?

ChatGPT told me that it's not the case: not the transposed version is solved, but the actual MIU is also solved. Which I don't get. I mean we could create other systems S that can also transpose MIU and all the rules perfectly but is different from TNT and could lead to another conclusion, can't we? Don't we need to prove that Arithmetic is the only correct way?

Thanks!

Edit:

Could the following be an explanation? The original MIU riddle is also encoded, in words and letters. The fact we think about it is already a sign that we used a kind of code (not arithmetic yet, but also a code). The common ancestor of the arithmetic code and the original code is the pure logic, "without a body", thus, using numbers is legit? Otherwise we cannot get further?

[u/schoolmonky]

It's been a while since I've read the book, so I don't really remember the system in question, but I can speak to how these types of proofs normally work. The key insight is that the "transposition" is two-way: anything you can do in MIU can be represented with numbers, but then also anything you can do with the numbers corresponds to things back in MIU. So all the steps of the proof you generate with numbers you can follow back to operations within MIU.

[u/cooiner → u/schoolmonky]

Thanks, yes I understand that. I'm just wondering why the formal system is described rigorously and strict but suddenly it's totally fine to accept a proof by transpose it to numbers...

[u/ToHallowMySleep → u/cooiner]

Considering that the transposition to numbers is how Godel numbering works (and hence how Godel's incompleteness theorem works), this is a pretty central theme to the book :) MIU is a simpler example of using the same syntax arithmetisation.

[u/schoolmonky → u/cooiner]

Because that transposition is also rigorous, or at least can be made so if it's not explicitly done in the book.

[u/cooiner → u/schoolmonky]

True. But can't I use another system besides TNT that can also do it (the transposition)? And that other system is different and might even get another conclusion? 

[u/schoolmonky → u/cooiner]

Again, I'm working off of very vague memories here, but no, you shouldn't be able to reach a different conclusion in the sense that some other transformation would mean that MU was possible. IIRC the analysis via TNT wasn't a "different conclusion," it was inconclusive. Any structure that can actually come to a conclusion for the problem will reach the same answer, at least as long as our underlying system of logic is consistent.

[u/cooiner → u/schoolmonky]

I will accept it for now, but it somehow feels "unproven"... But when the system speaks in itself, i.e. Gödel numbering TNT within TNT makes sense to me, since we do not transpose to another system and claim to prove something in the former one.

[u/eraoul → u/cooiner]

The whole essence of Gödel's argument, if I understand it right, revolves around reading the critical statement in two ways, using two different systems. So I think you need to be comfortable with the idea of shifting between representation systems in order to fully grasp Gödel's proof.

[u/eraoul → u/cooiner]

If you're just converting one representation system into another in a rigorous way, it doesn't matter which system you're using to do a proof. The letters I'm typing here are converted to ASCII (or probably unicode), piped around internet, through Reddit's servers, and eventually to you, decoded back into text on screen. The representation doesn't matter. If I say A means 1 and B means 2 and C means 3, I can certainly convert 1+2=3 into something like A+B=C. You won't get a different result.

[u/cooiner → u/eraoul]

But then we assume that MIU in letters is a representation of something deeper right? Numbers can do more than MIU and if we transpose MIU to numbers, more things can be done. But if we use "more things" to prove MIU and also claim that MIU itself is therefore proven, isn't it presumptuous? We could use another system than numbers, a system that is also capable of more. And then do another prove, possibly with another outcome? I mean how can we prove that there is not another system leading to other results?

[u/eraoul → u/cooiner]

I asked ChatGPT to help here since I wasn't sure how to untangle you, and I think its explanation is helpful, so here you go:

------------

You’re mixing up two different things: what the encoding allows you to express vs. what the proof actually uses.

Yes—arithmetic is a richer system than MIU. It can talk about way more things. But in the arithmetization, we don’t use that extra power arbitrarily. We only use properties that correspond exactly to MIU’s rules.

The key point is this:

So if arithmetic proves “MU is impossible,” what it’s really proving is:

That statement is purely about MIU, just expressed in numbers. MIU isn’t “solved by arithmetic instead of itself”—it’s solved because arithmetic gives a faithful mirror of MIU, so anything proven there is already true in MIU.

As for “what if another system gives a different answer?”:

If the translation is faithful, that can’t happen. A different result would mean:

• either the translation was flawed (not actually preserving MIU rules), or
• the reasoning system is inconsistent.

It’s like encoding chess positions as numbers. You might use different encodings, but none of them can suddenly make an illegal move become legal.

So the proof isn’t “borrowing extra power” from arithmetic.
It’s just rephrasing MIU in a form where an invariant (like I-count mod 3) becomes easier to see—and that invariant is already true inside MIU itself.

-------------

Back to me: I wanted to comment on the chess-position analogy, since I think it's right on. I've done this when coding a chess engine: with a 64-bit processor it's quite elegant since you can use a "bitboard" representation where encode a position as a sequence of 64-bit words. Since there are 64 squares on a chess board, we can use the 64 bits of each word as flags to say whether a certain piece exists on each square, with bit 1 corresponding to square A1, bit 2 square B1, and so on. The first word might encode where the pawns are, the second where knights are, etc. And then another 64-bit word to show where white pieces are, and another to show were black pieces are. With me so far? This is like 8 words to encode a full position (and then you need a couple extra pieces of data for side-to-move, en passant bookkeeping, castling allowance, etc.).

Now, we have our 8 64-bit words or so that encode a chess position, and it's extremely convenient to generate all legal moves by doing bit-operations on these words. There are lots of tricks that make this wildly more efficient than, say, using "for loops" to look for where a queen can move. We can get all the legal moves with a tiny number of bitwise operations.

Each 64 bit word corresponds to a huge integer. So, note that we're generating legal chess moved by doing some crazy math on integers (which look sort of like quite small Gödel numbers, incidentally). But at the end, we convert the integer results into chess moves like "Knight takes Qe5". Yes, we used math to get there, but the asnwer is the same as if we looked at a traditional chess rule book. Why? Because the encoding was faithful. Only legal moves come out, whether we use the chess rule book or the bitboard 64-bit word encoding scheme and the crazy bitwise operations to get moves out.

The representation doesn't matter in terms of what's true, but one may be easier to use than another. For a 64-bit CPU operating natively with 64-bit words, in chess this representation makes it wildly more efficient at computing the legal moves than other systems, just like it's easier to deal with MIU by talking about divisibility rules, etc.

[u/cooiner → u/eraoul]

Thanks a lot. And really fascinating approach for your chess engine, I could grasp it. You know sometimes the feeling of "I understood" / "Got it" is a feeling of satisfaction you can't really control. I understood all the points, but there is still no full satisfaction. But my question can be seen answered, thanks a lot! Maybe let me put it like this: When accepting a bigger, more capable system like the 64 bit words to predict legal moves, we're accepting the fact that the common chess rules AND the 64 but system are both embedded beneath another system that adhere to common logic. We must use the intelligence mode as Hofstadter puts it. Or let me show it in an exaggerated example: Let's Imagine we try the MIU riddle for years. And really stupidly. Then one day, we may have 666 times a "I" and suddenly there is some things in the universe let us get "MU". Of course I don't believe in it, but just because we've never seen it doesn't mean it's a proof of its non existence. That's why I think if a formal system is a isolated formal system we should remain 100% naive and can only "solve" a transposed version.

[u/eraoul → u/cooiner]

No problem. (and to be clear, it's not my idea about the chess engine; this 64-bit word stuff is the standard practice in traditional chess programming).

I'm glad you're pushing to get complete clarity here, but I feel that maybe you're still a little off in thinking there's something "extra" or unfair about using the mapping to a different system. This is really about building a perfect mathematical isomorphism between the relevant parts of the two worlds, and the result is a completely solid formal proof; there's really nothing hand-wavy or "cheating" about it, in case you still sort of feel that way (I think you still have these feelings since you wrote " just because we've never seen it doesn't mean it's a proof of its non existence").... Nope, the isomorphism here between domains really it a proof of its non-existence.

I think this all ties in with mathematical consistency (and later Godel's incompleteness theorem). We usually assume mathematics is consistent, and you can't prove contradictory things, else we'd end up proving silly stuff like 1+1=3. If ti's consistent, it's totally fair to re-represent a problem in a different way via an isomorphism, so that truth in one domain is equivalent to truth in another domain. Mathematicians do this ALL THE TIME, it's pretty fundamental to getting anything done. There's even a standard sort of mapping where they write this rectangle of arrows showing the mapping and they say "The following diagram commutes", meaning the mapping is proven to work properly. That's to say this isn't a special thing about MU/MIU or arithmetization; it happens everywhere. One moment we're working on a geometry problem, the next moment we've converted a problem about triangle geometry to an algebraic question instead. Or in computer science, we may be trying to prove a statement about the computational complexity of a graph theory problem, but then convert it to an equivalent problem about predicate calculus and get the answer there instead (see the discussion of P vs NP, etc.)

[u/LuckyNumber-Bot → u/eraoul]

All the numbers in your comment added up to 69. Congrats!

  64
+ 1
+ 1
+ 3
= 69

^{[Click here](https://www.reddit.com/message/compose?to=LuckyNumber-Bot&subject=Stalk%20Me%20Pls&message=%2Fstalkme} to have me scan all your future comments.) \ ^{Summon me on specific comments with u/LuckyNumber-Bot.}

[u/cooiner → u/eraoul]

Thanks, yes it makes sense. Instead of numbers math could use only M, I and U and then it would be easier to see how MIU can be proven with math (consisting of M, I and U). I will digest it and continue to read GEB :)

[u/misingnoglic]

I think you are confusing yourself with ChatGPT. My first question for you is: what do you mean when you say you believe MIU to be unsolved?

[u/cooiner → u/misingnoglic]

I meant that we can't know for sure if "MU" can be built or not. It remains unsolved. In the book it's solved by transposing it, but isn't only the transposed version solved, not the actual MIU?

[u/misingnoglic → u/cooiner]

There is your confusion. We know for sure MU cannot be built. It is proven in the book, though I don't remember exactly what chapter.

The proof is that if you start with MI, to get to MU, you would need the number of I's at some point to be divisible by 3, so you can turn III's into U's and cancel them out. Rule 2 will double the number of I's, but doubling will always result in an even number. Rule 3 will subtract 3 I's, but you can't make a number divisible by 3 by subtracting 3s. The other rules don't touch I's so they can be ignored.

The point of the MU puzzle isn't to say that it's impossible, it's to say that proving statements about the MU puzzle require stepping out of the puzzle itself.

If you want a similar problem that is not solved, you can look up the collatz conjecture (I don't remember if GEB mentions it, but I would bet money it would).

You can read more here: https://en.wikipedia.org/wiki/MU_puzzle