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".

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.
