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:

You assume the worst:
Suppose all the strings are totally unrelated — no string embeds into a later one.
You show that this assumption leads to a contradiction.
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.