Is there an infinite set of finite strings such that no element is a subsequence of another?
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".
Solution 1:
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.
Solution 2:
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
- $x_i\in\Sigma^\ast$
- $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.