Skip to main content
added information
Source Link

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.
  2. I've posted a new attempt at a two-dimensional version of Higman's Lemma here.

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$?

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.
  2. I've posted a new attempt at a two-dimensional version of Higman's Lemma here.
A typo in the title is corrected.
Link
user64494
  • 3.5k
  • 14
  • 22

Is there a two-dimensional Higman's Lemmalemma?

Source Link

Is there a two-dimensional Higman's Lemma?

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$?