Proof of Higman’s Theorem — Theory of Computation

🌱 What We’re Trying to Prove

We want to show:

All strings built from a well-quasi-ordered alphabet are also well-quasi-ordered under embedding.

A well-quasi-order (WQO) is a fancy way of saying:

• No infinite descending chains
• No infinite set of mutually incomparable elements

In everyday words:

You can’t keep making “new” strings forever without eventually repeating a pattern.

Higman’s Theorem formalizes this precise idea.

---

🎒 The Big Intuition Behind the Proof

Imagine you are writing down an infinite sequence of strings:

S1, S2, S3, S4, ...

Each string is made of letters.
Each letter comes from an alphabet that is already “well behaved” (meaning the letters themselves follow a WQO).

The proof strategy is kind of like this:

1. You assume the worst:
   Suppose all the strings are totally unrelated — no string embeds into a later one.
2. You show that this assumption leads to a contradiction.
3. Therefore, your assumption must be wrong, and the theorem must be true.

This is a classic “proof by contradiction” technique, but we will keep it intuitive.

---

🧩 Core Insight of the Proof

Every string can be split into:

• a first letter, and
• the remaining tail.

Example:

String:   b  c  a
Parts:   [b] [c a]

So any string S can be represented as:

S = a · R

Where:

• a is the first symbol
• R is the rest of the string

This simple observation is the heart of the proof.

---

🏗️ The High-Level Structure of the Proof

Let’s walk through it in a friendly way.

---

Step 1: Look at an Infinite List of Strings

Assume we have an infinite sequence:

S1, S2, S3, S4, ...

Let each string be written as:

Si = ai  Ri

Where:

• ai is the first letter
• Ri is the tail of the string

---

Step 2: Use the WQO Property of Letters

Since the alphabet is well-quasi-ordered, the sequence:

a1, a2, a3, ...

cannot be completely chaotic.

So, there must be an infinite non-decreasing subsequence:

ai1  <= ai2  <=  ai3  <= ...

This means:

The first letters eventually fall into a nice pattern where each one is “≥ or equal to” the previous one.

This is the first point where order starts showing up.

---

Step 3: Look at the Tails

Now focus on the tails:

Ri1, Ri2, Ri3, ...

By induction (the proof uses induction on string length),
the tails must also contain an ordered pair:

Rip  ᵢₙᵈᵘᶜₜᶦᵒⁿ ≤  Riq

This means the tail Rip embeds into the tail Riq.

So we now have two things lined up:

• ai_p ≤ ai_q (first letters)
• Rip embeds into Riq (tails)

---

Step 4: Combine the Two Parts

Since:

• The first letter of Sip is ≤ the first letter of Siq, and
• The tail of Sip embeds into the tail of Siq,

We conclude:

Sip  embeds into  Siq

Which contradicts our original assumption:

“No string embeds into any later string.”

Thus, that assumption must be false.

This completes the proof.

---

🎨 Simple Diagram to Visualize the Embedding

Sip:     a      r1    r2    r3
          \       \     \     \
Siq:   A   x   r1   y   r2   z   r3   w

• a ≤ A (first letters compare by alphabet order)
• The smaller pieces r1, r2, r3 appear inside the larger string in the right order
• Extra letters (x, y, z, w) don’t matter
• The structure is preserved

This illustrates exactly what Higman’s Theorem guarantees.

---

🌈 Why This Proof Is Beautiful

The proof is elegant because:

• It takes a complicated statement about infinite sets of strings
• and breaks it into small, understandable pieces
• relying only on the simple idea that a string is a first letter plus a tail
• and that the alphabet itself already has a nice order

Everything builds up naturally.

It’s one of those proofs where the “big” result pops out from something surprisingly small and intuitive.

---

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts