A string over a finite alphabet $A$ can be thought of as a function
$f:\{1,2,...,m\} \rightarrow A$ for some natural number $m$.


A 2-Dim string over $A$ is a function $f$ where
$f:\{1,2,\ldots,m\}\times\{1,2,\ldots,n\} \rightarrow A$ for some natural numbers $m$ and $n$.


If $f$ and $f'$ are 2-Dims (over $A$), with dimensions $(m,n)$ and $(m'n')$ respectively, we say $f\leq f'$ if there is are increasing functions
$D:\{1,2,\ldots,m\}\rightarrow\{1,2,\ldots, m'\}$ and
$E:\{1,2,\ldots,n\}\rightarrow\{1,2,\ldots, n'\}$ such that whenever
$1\leq i\leq m$ and $1\leq j\leq n$, $f(i,j)=f'(D(i),E(j))$.


Is there a proof or disproof of the version of Higman's lemma that states that for every infinite sequence $f\_1,f\_2,\ldots$ of 2-Dims over $A$, there is $1\leq u<v$ such that $f\_u\leq f\_v$?


Edit August 29 2023


1. This same question was posed and solved [here](https://math.stackexchange.com/questions/3502206/higman-s-lemma-for-matrices).
2. I've posted a new attempt at a two-dimensional version of Higman's Lemma
[here](https://mathoverflow.net/questions/453668/a-second-attempt-at-a-two-dimensional-higmans-lemma).



Is there a two-dimensional Higman's lemma?
I think there's a counterexample. Consider rectangles that look something like this:



```
10000000
10000000
11000000
01100000
00110000
...
00000011
00000001
00000001

```

where we increase the size of the "middle" block by one each time. Since only the first and the last column contain three 1's then any embedding would have to map those two columns to one another but then the other connections form a path between them.


This of course is closely related to the antichain of graphs under the induced subgraph relation that you get by taking paths of various lengths and splitting the first and last vertices into independent pairs.


