15
$\begingroup$

Of course, this is meant to be over a finite alphabet. My intuition is that this doesn't exist over any such alphabet, so that's what I'd want to know how to prove.

I'm also interested in questions like "can such a set be computably enumerable" and "can such a set be computable".

$\endgroup$
8
  • 2
    $\begingroup$ Do the strings need to be finite? Can you provide a few examples. $\endgroup$
    – Sonal_sqrt
    Dec 14, 2019 at 15:50
  • 3
    $\begingroup$ Do you actually mean "subsequence" or did you mean to say "substring?" For example, "aa" is a subsequence of "aba", but not a substring. $\endgroup$
    – saulspatz
    Dec 14, 2019 at 15:50
  • 3
    $\begingroup$ For "substring" as opposed to "subsequence", $abc$, $aabbcc$, $aaabbbccc$, $\ldots$ satisfy the conditions. $\endgroup$
    – Calvin Lin
    Dec 14, 2019 at 15:53
  • 3
    $\begingroup$ @CalvinLin: Even simpler: $aba,abba,abbba,\ldots$ $\endgroup$
    – TonyK
    Dec 14, 2019 at 15:54
  • 1
    $\begingroup$ @saulspatz yes I mean "subsequence", for "substring" there is already this question $\endgroup$
    – acupoftea
    Dec 14, 2019 at 15:57

2 Answers 2

9
$\begingroup$

Your intuition is correct. Quoting Wikipedia on Higman's lemma:

Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if $w_1,w_2,\dots$ is an infinite sequence of words over some fixed finite alphabet, then there exist indices $i\lt j$ such that $w_i$ can be obtained from $w_j$ by deleting some (possibly none) symbols. More generally this remains true when the alphabet is not necessarily finite, but is itself well-quasi-ordered, and the subsequence relation allows the replacement of symbols by earlier symbols in the well-quasi-ordering of labels. This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952.

$\endgroup$
3
  • $\begingroup$ For future people finding this question, do you know where a simple proof in English is available? Searching for it in English, I only found research articles that prove stronger versions than necessary for this question, and I couldn't understand them. I found a very short, elementary and simple proof here, but it's in Polish. I guess I could just translate it but I hope it (or a similar version) exists somewhere $\endgroup$
    – acupoftea
    Dec 16, 2019 at 7:35
  • $\begingroup$ Once we know that no infinite sequence exists, do we know whether arbitrary long sequences exist? $\endgroup$
    – M. Winter
    Dec 18, 2019 at 10:21
  • 1
    $\begingroup$ @M.Winter If the alphabet contains two different symbols, then for each $n$ there are $2^n$ different strings of length $n$, and of course none is a subsequence of another. $\endgroup$
    – bof
    Dec 18, 2019 at 10:28
3
$\begingroup$

This answer is translated (with small modifications) from here.

$\Sigma$ is a finite alphabet.
$\Sigma^\ast$ is the set of finite strings over $\Sigma$ (Kleene star).
$x\preceq y$ means that $x$ is a subsequence of $y$.

We'll prove that there is no infinite set $S \subseteq \Sigma^\ast$ such that no element of it is a subsequence of another (Higman's lemma).

Assume the thesis is false. Then there is an infinite sequence $x_1, x_2,\ldots$ such that

  1. $x_i\in\Sigma^\ast$
  2. $i<j \implies \textit{not} (x_i \preceq x_j) $ (notice that $x_i \succ x_j$ is possible)

From infinite sequences meeting the criteria 1-2 take one that's minimal in the sense that $|x_1|$ is minimal and with $|x_1|$ fixed $|x_2|$ is minimal, etc.

Take an infinite subsequence $x_{i_1}, x_{i_2},\ldots $ where the first letter of each element is $a$ (constant for all elements). Remove the first letter from each of those elements, getting the sequence $x_{i_1}', x_{i_2}',\ldots $. Then, the infinite sequence $$x_1, x_2, \ldots, x_{i_1-1}, x_{i_1}', x_{i_2}', x_{i_3}', \ldots$$ meets the criteria 1-2 and is "smaller" than $x_1, x_2, \ldots$, a contradiction.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .