Higman’s Theorem — Theory of Computation

by

🌱 what is the idea behind the theorem?

Higman’s Theorem is about sequences (think: strings made from alphabets) and how they can be compared using embedding.

“Embedding” here simply means:

You can transform one string into another by inserting extra characters while keeping the original order.

For example:

  • "abc" can be embedded into "aXbYZc",
    because we can match a → a, b → b, c → c in the same order.

But:

  • "abc" cannot be embedded into "acb"
    because order is broken.

This “order-respecting match” is the heart of Higman’s Theorem.

⭐ So what does Higman’s Theorem actually say?

Here’s the friendly version:

If you have an alphabet where you can compare symbols in a well-behaved, ordered way, then any endless list of strings built from that alphabet must contain two strings where the earlier one embeds into the later one.

In short:

  • No matter how many strings you make,
  • You can’t keep avoiding this “embedding relationship.”

This means the set of all strings over a “well-ordered” alphabet forms a well-quasi-ordering under embedding.

🤔 Why does this matter?

Because it gives us a powerful tool:

👉 It prevents infinite disorder.

You cannot create an infinite list of strings that is:

  • always getting “more complicated,”
  • forever avoiding comparison,
  • and never allowing an earlier one to embed into a later one.

This makes Higman’s Theorem extremely important in:

  • Termination proofs
  • Program analysis
  • Formal language theory
  • Understanding infinite structures

Whenever you need to prove something does not go on forever, Higman’s Theorem often steps in like a quiet superhero.

🍎 An Everyday Analogy

Imagine you’re lining up children by height.
But the rule isn’t strict height — it’s:

“A child A can be placed in front of child B if A is shorter than or equal to B.”

If you keep bringing more and more children into the line, Higman’s Theorem is like saying:

“Eventually you’ll find two children such that the earlier one can stand in front of the later one.”

You cannot create a forever-increasing disorder.

Strings behave the same way.

📘 Simplified Diagram

Here is a simple ASCII-style diagram to show embedding:

String 1:    a   b   c
              \   \   \
String 2:     a   X   b   Y   Z   c

Arrows show how each character of the first string appears in order inside the second string.

This is exactly the kind of behavior Higman’s Theorem guarantees will appear in any long sequence of strings.