# The neat embedding problem for algebras other than cylindric algebras and
for infinite dimensions

Robin Hirsch and Tarek Sayed Ahmed

###### Abstract

Hirsch and Hodkinson proved, for $3\leq m<\omega$ and any $k<\omega$, that the
class $S{\mathfrak{Nr}}_{m}{\bf CA}_{m+k+1}$ is strictly contained in
$S{\mathfrak{Nr}}_{m}{\bf CA}_{m+k}$ and if $k\geq 1$ then the former class
cannot be defined by any finite set of first order formulas, within the latter
class. We generalise this result to the following algebras of $m$-ary
relations for which the neat reduct operator ${\mathfrak{Nr}}_{m}$ is
meaningful: polyadic algebra with or without equality and substitution
algebra. We also generalise this result to allow the case where $m$ is an
infinite ordinal, using quasipolyadic algebra in place of polyadic algebra
(with or without equality). 111 Mathematics Subject Classification: 03G15,
03C10. Key words: algebraic logic, cylindric algebras, quasi-polyadic
algebras, substitution algebras, neat reducts, neat embeddings.

Cylindric algebra is an algebraic correspondent of first-order logic with no
constants or functions, more specifically $n$-dimensional cylindric algebra,
${\bf CA}_{n}$, is an algebraic correspondent of first-order logic restricted
to $n$ indexed variables, for finite $n$. An algebra in ${\bf CA}_{n}$ is a
boolean algebra together with a cylindrfier ${\sf c}_{i}$, which acts as a
unary operator and corresponds to existential quantification of the $i$’th
variable, and a diagonal ${\sf d}_{ij}$ element corresponding to the equaltify
of the $i$th and $j$’ variable, for $i,j<n$. For $m<n$, the _neat reduct_
${\mathfrak{Nr}}_{m}{\mathcal{C}}$ of a ${\mathcal{C}}\in{\bf CA}_{n}$ is the
$m$-dimensional cylindric algebra obtained by restricting to those elements
$c\in{\mathcal{C}}$ such that ${\sf c}_{i}c=c$, for $m\leq i<n$ and
restricting to those cylindrifiers and diagonals indexed by $m$. It is not the
case that every algebra in ${\bf CA}_{m}$ is the neat reduct of an algebra in
${\bf CA}_{n}$, nor need it even be a subalgebra of a neat reduct of an
algebra in ${\bf CA}_{n}$. Furthermore, $S{\mathfrak{Nr}}_{m}{\bf
CA}_{m+k+1}\neq S{\mathfrak{Nr}}_{m}{\bf CA}_{m}$, whenever $3\leq m<\omega$
and $k<\omega$ [6]. A consequence of this is that there are $m$ variable
formulas that can be proved with $m+k+1$ variables, but not with $m+k$
variables, in a certain, fairly typical, proof system.

Other algebras may be defined corresponding to restrictions or extensions of
the $n$ variable first order logic described above. Because our focus is on
neat reducts, we will only consider $n$-dimensional algebras where the
cylindrifiers ${\sf c}_{i}$ are included, or at least are definable, within
the set of operators of the algebra. Without that restriction it would not be
possible to define a neat reduct and our algebras would correspond to first
order logic without quantifiers, we do not consider that case here. But we
might choose to drop the diagonals from our signature (corresponding to first
order logic without equality), or we may add permutation operators,
corresponding to permutations of the variables in first order logic. By
generalising the results about neat reducts of $m$ dimensional cylindric
algebras to other $m$ dimensional algebras, such as polyadic algebras with or
without equality, diagonal free cylindric algebras, substitution algebras, one
may deduce that there are $m$ variable formulas provable with $m+k+1$
variables but not with $m+k$ variables in logical proof systems similar to the
one in [7], but with additional inference rules (corresponding to polyadic
equality algebras $({\bf PEA}))$ or fewer weaker inference rules
(corresponding to substitution algebras $({\bf Sc}))$.

## Preliminaries

For cardinals $m,n$ we write ${}^{m}n$ for the cardinal of the set of maps
from $m$ to $n$. If $U$ is an ultrafilter over $\wp(I)$ and if
${\mathcal{A}}_{i}$ is some structure (for $i\in I$) we write either
$\Pi_{i\in I}{\mathcal{A}}_{i}/U$ or $\Pi_{i/U}{\mathcal{A}}_{i}$ for the
ultraproduct of the ${\mathcal{A}}_{i}$ over $U$. Fix some ordinal $n\geq 2$.
For $i,j<n$ the replacement $[i/j]$ is the map that is like the identity on
$n$, except that $i$ is mapped to $j$ and the transposition $[i,j]$ is the
like the identity on $n$, except that $i$ is swapped with $j$. A map
$\tau:n\rightarrow n$ is finitary if the set $\\{i<n:\tau(i)\neq i\\}$ is
finite, so if $n$ is finite then all maps $n\rightarrow n$ are finitary. It is
known, and indeed not hard to show, that any finitary permutation is a product
of transpositions and any finitary non-injective map is a product of
replacements.

The standard reference for all the classes of relations mentioned previously
is [4]. Each class in $\\{{\bf Df}_{n},{\bf Sc}_{n},{\bf CA}_{n},{\bf
PA}_{n},{\bf PEA}_{n},{\bf QPA}_{n},{\bf QPEA}_{n}\\}$ consists of boolean
algebras with extra operators, as shown in figure 1, where ${\sf d}_{ij}$ is a
nullary operator (constant), ${\sf c}_{i},{\sf s}_{\tau},{\sf s}_{[{i}/{j}]}$
and ${\sf s}_{[i,j]}$ are unary operators, for $i,j<n,\;\tau:n\rightarrow n$.
For finite $n$, polyadic algebras are the same as quasi-polyadic algebra and
for the infinite dimensional case we restrict our attention to quasi-polyadic
algebras in ${\bf QPA}_{n},{\bf QPEA}_{n}$. Each class is defined by a finite
axiom schema of equations. Existing in a somewhat scattered form in the
literature, equations defining ${\bf Sc}_{n},{\bf QPA}_{n}$ and ${\bf
QPEA}_{n}$ are given in the appendix, definition 15. For ${\bf CA}_{n}$ we
follow the standard axiomatization given in definition 1.1.1 in [3]. For any
operator $o$ of any of these signatures, we write ${\sf
dim}(o)\;(\subseteq\alpha)$ for the set of dimension ordinals used by $o$,
e.g. ${\sf dim}({\sf c}_{i})=\\{i\\},\;{\sf dim}({\sf
s}_{[{i}/{j}]})=\\{i,j\\}$. An algebra ${\mathcal{A}}$ in ${\bf QPEA}_{n}$ has
operators that can define any operator of ${\bf QPA}_{n},{\bf CA}_{n},\;{\bf
Sc}_{n}$ and ${\bf Df}_{n}$, thus we may obtain the reducts
${\mathfrak{Rd}}_{\bf K}({\mathcal{A}})$ for ${\bf K}\in\\{{\bf QPEA}_{n},{\bf
QPA}_{n},{\bf CA}_{n},{\bf Sc}_{n},{\bf Df}_{n}\\}$ and it turns out that the
reduct always satisfies the equations defining the relevant class so
${\mathfrak{Rd}}_{\bf K}({\mathcal{A}})\in{\bf K}$, similarly from any algebra
${\mathcal{A}}$ in any of the classes ${\bf QPEA}_{n},{\bf QPA}_{n},{\bf
CA}_{n},{\bf Sc}_{n}$ we may obtain the reduct ${\mathfrak{Rd}}_{\bf
Sc}({\mathcal{A}})\in{\bf Sc}_{n}$ [1].

$\begin{array}[]{l|l}\mbox{class}&\mbox{extra operators}\\\ \hline\cr{\bf
Df}_{n}&{\sf c}_{i}:i<n\\\ {\bf Sc}_{n}&{\sf c}_{i},{\sf s}_{[i/j]}:i,j<n\\\
{\bf CA}_{n}&{\sf c}_{i},{\sf d}_{ij}:i,j<n\\\ {\bf PA}_{n}&{\sf c}_{i},{\sf
s}_{\tau}:i<n,\;\tau\in\;^{n}n\\\ {\bf PEA}_{n}&{\sf c}_{i},{\sf d}_{ij},{\sf
s}_{\tau}:i,j<n,\;\tau\in\;^{n}n\\\ {\bf QPA}_{n}&{\sf c}_{i},{\sf
s}_{[i/j]},{\sf s}_{[i,j]}:i,j<n\\\ {\bf QPEA}_{n}&{\sf c}_{i},{\sf
d}_{ij},{\sf s}_{[i/j]},{\sf s}_{[i,j]}:i,j<n\end{array}$ Figure 1: Non-
boolean operators for the classes

Let ${\bf K}\in\\{{\bf QPEA},{\bf QPA},{\bf CA},{\bf Sc},{\bf Df}\\}$, let
${\mathcal{A}}\in{\bf K}_{n}$ and let $2\leq m\leq n$ (possibly infinite
ordinals). The _reduct to $m$ dimensions_
${\mathfrak{Rd}}_{m}({\mathcal{A}})\in{\bf K}_{m}$ is obtained from
${\mathcal{A}}$ by discarding all operators with indices $m\leq i<n$. The
_neat reduct to $m$ dimensions_ is the algebra
${\mathfrak{Nr}}_{m}({\mathcal{A}})\in{\bf K}_{m}$ with base
$\\{a\in{\mathcal{A}}:m\leq i<n\rightarrow{\sf c}_{i}a=a\\}$ where all the
operators are induced from ${\mathcal{A}}$ (see [3, definition 2.6.28] for the
${\bf CA}$ case). More generally, for $\Gamma\subseteq n$ we write
${\mathfrak{Nr}}_{\Gamma}{\cal{A}}$ for the algebra whose base is
$\\{a\in{\mathcal{A}}:i\in n\setminus\Gamma\rightarrow{\sf c}_{i}a=a\\}$ with
all the operators $o$ of ${\mathcal{A}}$ where ${\sf dim}(o)\subseteq\Gamma$.
Let ${\mathcal{A}}\in{\bf K}_{m},\;{\mathcal{B}}\in{\bf K}_{n}$. An injective
homomorphism $f:{\mathcal{A}}\rightarrow{\mathcal{B}}$ is a _neat embedding_
if the range of $f$ is a subalgebra of ${\mathfrak{Nr}}_{m}({\mathcal{B}})$.
The notions of neat reducts and neat embeddings have proved useful in
analyzing the number of variables needed in proofs, as well as for proving
representability results, via the so-called neat embedding theorems [16, 11,
12, 17]. For ${\bf K}$ as above and $\alpha$ an ordinal, let ${\bf
RK}_{\alpha}$ denote the set of representable algebras in ${\bf K}_{\alpha}$.
Then a typical neat embedding theorem, essentially due to Henkin [4], states
that ${\bf RK}_{\alpha}=S{\mathfrak{Nr}}_{\alpha}{\bf
K}_{\alpha+\omega}=\bigcap_{k\in\omega}S{\mathfrak{Nr}}_{\alpha}{\bf
K}_{\alpha+k}$; this is known to hold for all such ${\bf K}$ except for ${\bf
Df}$.

Let $\alpha\leq\beta$ be ordinals and let $\rho:\alpha\rightarrow\beta$ be an
injection. For any $\beta$-dimensional algebra ${\mathcal{B}}$ (substution,
cylindric or quasi-polyadic algebra with or without equality) we define an
$\alpha$-dimensional algebra ${\mathfrak{Rd}}^{\rho}({\mathcal{B}})$, with the
same base and boolean structure as ${\mathcal{B}}$, where the $(ij)$th
diagonal of ${\mathfrak{Rd}}^{\rho}({\mathcal{B}})$ is ${\sf
d}_{\rho(i)\rho(j)}\in{\mathcal{B}}$ (if diagonals are included in the
signature of the algebra), the $i$th cylindrifier is ${\sf c}_{\rho(i)}$, the
$i$ for $j$ replacement operator is the operator ${\sf s}^{\rho(i)}_{\rho(j)}$
of ${\mathcal{A}}$, the $ij$ transposition operator is ${\sf
s}_{\rho(i)\rho(j)}$ (if included in the signature), for $i,j<\alpha$. It is
easy to check, for ${\bf K}\in\\{{\bf Df},{\bf Sc},{\bf CA},{\bf QPA},{\bf
QPEA}\\}$, that if ${\mathcal{B}}\in{\bf K}_{\beta}$ then
${\mathfrak{Rd}}^{\rho}({\mathcal{B}})\in{\bf K}_{\alpha}$. Also, for
${\mathcal{B}}\in{\bf K}_{\beta}$ and $x\in{\mathcal{B}}$, we define
${\mathfrak{Rl}}_{x}({\mathcal{B}})$ by ‘restriction to $x$’, so the base is
the set of elements of ${\mathcal{B}}$ below $x$, where the boolean unit is
$x$, boolean zero and sum are not changed, boolean complementation is relative
to $x$, and the result of applying any non-boolean operator is obtained by
using the operator for ${\mathcal{B}}$ and intersecting with $x$. It is not
always the case that ${\mathfrak{Rl}}_{x}({\mathcal{B}})$ is a ${\bf
K}_{\beta}$ (we can lose commutativity of cylindrifiers).

The main question we address in this paper is whether
$S{\mathfrak{Nr}}_{m}{\bf K}_{n}={\bf K}_{m}$, where $m<n$ are possibly
infinite ordinals and ${\bf K}\in\\{{\bf Df},{\bf Sc},{\bf CA},{\bf QPA},{\bf
QPEA}\\}$ and, if not, whether $S{\mathfrak{Nr}}_{m}{\bf K}_{n}$ may be
defined within ${\bf K}_{m}$ using only finitely many axioms (or finitely many
axiom schemas, when $m$ is infinite). The case ${\bf K}={\bf Df}$ of diagonal
free algebra is easily answered: $S{\mathfrak{Nr}}_{m}{\bf Df}_{n}={\bf
Df}_{m}$, for $3\leq m\leq n$, see [4, theorem 5.1.31]. We show that in all
the other cases, the answers are negative. In order to generalise the results
of [6] to these other classes of algebra, we define an $m$-dimensional
polyadic equality type algebra ${\mathfrak{C}}(m,n,r)$ where $3\leq m\leq
n,\;r<\omega$ (see definition 4 below). These algebras are based on a relation
algebra construction that first appeared in [9] or see [8, section 15.2],
modified here so that the elements become $n$-dimensional rather than two
dimensional. Still, although they are $n$-dimensional, all of their elements
are generated by two dimensional elements. We will then prove the following
theorem.

######  Theorem 1.

  1. I.

${\mathfrak{C}}(m,n,r)\in{\mathfrak{Nr}}_{m}{\bf PEA}_{n}$,

  2. II.

${\mathfrak{Rd}}_{{\bf Sc}}{\mathfrak{C}}(m,n,r)\not\in
S{\mathfrak{Nr}}_{m}{\bf Sc}_{n+1}$,

  3. III.

$\Pi_{r/U}{\mathfrak{C}}(m,n,r)$ is elementarily equivalent to a countable
polyadic equality algebra ${\mathfrak{C}}\in{\mathfrak{Nr}}_{m}{\bf
PEA}_{n+1}$.

The proof of this theorem is the substantial part of this paper. The proofs
are similar to proofs of corresponding results in [9] but modified for the
signatures considered here and with some further modifications. To prove the
first two parts, the algebras we consider will only have elements generated by
two dimensional elements, however for the third part we will also use elements
that are essentially three dimensional (hence we will introduce three
dimensional hypernetworks, for this part only). From this theorem we deduce
the following.

######  Corollary 2.

Let ${\bf K}\in\\{{\bf PEA},{\bf PA},{\bf CA},{\bf Sc}\\}$, let $3\leq
m<n<\omega$. Then $S{\mathfrak{Nr}}_{m}{\bf K}_{n+1}$ is a proper subclass of
$S{\mathfrak{Nr}}_{m}{\bf K}_{n}$ which cannot be defined, within
$S{\mathfrak{Nr}}_{m}{\bf K}_{n}$ by any finite set of first order formulas.

###### Proof.

We remarked earlier that for each choice of ${\bf K}$ and each $n$, the
operators of ${\bf Sc}_{n}$ are definable by the operators of ${\bf K}_{n}$
which are themselves definable by the operators of ${\bf PEA}_{n}$. Hence, it
follows from (I) that ${\mathfrak{Rd}}_{\bf
K}{\mathfrak{C}}(m,n,r)\in{\mathfrak{Nr}}_{m}{\bf K}_{n}$, from (II)
${\mathfrak{Rd}}_{\bf K}{\mathfrak{C}}(m,n,r)\not\in S{\mathfrak{Nr}}_{m}{\bf
K}_{n+1}$, for $r<\omega$ and from (III) ${\mathfrak{Rd}}_{\bf
K}({\mathfrak{C}})\in{\mathfrak{Nr}}_{m}{\bf K}_{n+1}$. Now suppose for
contradiction that $\phi$ is a formula defining $S{\mathfrak{Nr}}_{m}{\bf
K}_{n}$ within $S{\mathfrak{Nr}}_{m}{\bf K}_{n+1}$. Let $U$ be any non-
principal ultrafilter over $\omega$. Since ${\mathfrak{Rd}}_{\bf
K}{\mathfrak{C}}(m,n,r)\in{\mathfrak{Nr}}_{m}{\bf K}_{n}\setminus
S{\mathfrak{Nr}}_{m}{\bf K}_{n+1}$, ${\mathfrak{Rd}}_{\bf
K}({\mathfrak{C}}(m,n,r))\not\models\phi$, for each $r<\omega$. By Łoś’s
theorem, $\Pi_{r/U}\;{\mathfrak{Rd}}_{\bf
K}{\mathfrak{C}}(m,n,r)\models\neg\phi$. By elementary equivalence
${\mathfrak{C}}\models\neg\phi$, contradicting (III). ∎

We will prove (I), (II), (III) below, after we have defined the algebras
${\mathfrak{C}}(m,n,r)$. For some time to come we restrict our attention to
finite ordinals, which we denote by $m,n\ldots,$ etc. Now we define our
algebras:

######  Definition 3.

Define a function $\kappa:\omega\times\omega\rightarrow\omega$ by
$\kappa(x,0)=0$ (all $x<\omega$) and $\kappa(x,y+1)=1+x\times\kappa(x,y))$
(all $x,y<\omega$). For $n,r<\omega$ let

$\psi(n,r)=\kappa((n-1)r,(n-1)r)+1$

and let $\psi(n,J)=\omega$, for any infinite linear order $J$. [All of this is
simply to ensure that $\psi(n,r)$ is sufficiently big compared to $n,r$ for
the proof of non-embedability to work.] For any $n<\omega$ and any linear
order $J$, let

$Bin(n,J)=\\{Id\\}\cup\\{a^{k}(i,j):i<n-1,\;j\in J,\;k<\psi(n,J)\\}$

For $i<n-1,\;j\in J,\;k<\psi(n,J)$ let

$\displaystyle a(i,\\_)$ $\displaystyle=\\{a^{k}(i,j):j\in
J,\;k<\psi(n,J))\\},$ $\displaystyle a(\\_,j)$
$\displaystyle=\\{a^{k}(i,j):i<n-1,\;k<\psi(n,J)\\},$ $\displaystyle a^{k}$
$\displaystyle=\\{a^{k}(i,j):i<n-1,\;j\in J\\},$ $\displaystyle a(i,j)$
$\displaystyle=\\{a^{k}(i,j):k<\psi(n,J)\\},$ $\displaystyle a(\\_,>j)$
$\displaystyle=\bigcup_{j<j^{\prime}\in J}a(\\_,j^{\prime})$ $\displaystyle
a(\\_,\leq j)$ $\displaystyle=\bigcup_{j^{\prime}\leq j\in
J}a(\\_,j^{\prime})\mbox{ and }$ $\displaystyle a$
$\displaystyle=\bigcup_{i<n-1}a(i,\\_).$

Let $3\leq m\leq n<\omega$ and let $J$ be any linear order. Let $F(m,n,J)$ be
the set of all functions $f:m\times m\to Bin(n,J)$ such that for all $x,y,z<m$
we have $f(x,x)=Id,\;f(x,y)=f(y,x)$, and $(f(x,y),f(y,z),f(x,z))\not\in Forb$,
where $Forb$ is the following set of triples

$\begin{array}[]{c}\\{(Id,b,c):b\neq c\in Bin(n,J)\\}\\\ \cup\\\
\\{(a^{k}(i,j),a^{k^{\prime}}(i,j),a^{k^{*}}(i,j^{\prime})):k,k^{\prime},k^{*}<\psi(n,r),\;i<n-1,\;j^{\prime}\leq
j\in J\\}.\end{array}$

For any $f,g\in F(m,n,J)$ and $x<m$ we write $f\equiv_{x}g$ if for all $y,z\in
m\setminus\\{x\\}$ we have $f(y,z)=g(y,z)$, and for $\tau:m\to m$ we write
$(f\tau)$ for the function defined by

$(f\tau)(x,y)=f(\tau(x),\tau(y)).$ (1)

Clearly $(f\tau)\in F(m,n,J)$. For the next couple of sections we will
consider cases where $J$ is a finite linear order, i.e. some finite ordinal
$r<\omega$.

######  Definition 4.

The base of ${\mathfrak{C}}(m,n,r)$ is the power set of $F(m,n,r)$ and the
operators are

  * •

the boolean operators $+,-$ are union and set complement,

  * •

the diagonal ${\sf d}_{xy}=\\{f\in F(m,n,r):f(x,y)=Id\\}$,

  * •

the cylindrifier ${\sf c}_{x}(X)=\\{f\in F(m,n,r):\exists g\in
X\;f\equiv_{x}g\\}$ and

  * •

the polyadic ${\sf s}_{\tau}(X)=\\{f\in F(m,n,r):f\tau\in X\\}$,

for $x,y<m,\;X\subseteq F(m,n,r)$ and $\tau:m\to m$.

Let $x,y<m$ and let $b\in Bin(n,r)$. Define

$b_{x,y}=\\{f\in F(m,n,r):f(x,y)=b\\}\;\;\in{\mathfrak{C}}(m,n,r)$ (2)

Observe, for any $x,y,z<m$ and $\lambda,\mu,\rho\in Bin(n,r)$, that

$(\lambda,\mu,\rho)\in Forb\iff\lambda_{x,y}\cdot\mu_{y,z}\cdot\rho_{x,z}=0,$
(3)

in particular we will use the case $(x,y,z)=(0,1,2)$, later.

######  Lemma 5.

For $3\leq m,\;2\leq n$ and $r<\omega$ the algebra ${\mathfrak{C}}(m,n,r)$
satisfies all of the axioms defining ${\bf PEA}_{m}$ (see definition 15,
noting that for finite $m$, ${\bf PEA}_{m}$ is the same as ${\bf QPEA}_{m}$)
except, perhaps, the commutativity of cylindrifiers ${\sf c}_{x}{\sf
c}_{y}(X)={\sf c}_{y}{\sf c}_{x}(X)$.

###### Proof.

Routine. ∎

######  Lemma 6.

If $3\leq m\leq m^{\prime}$ then
${\mathfrak{C}}(m,n,r)\cong{\mathfrak{Nr}}_{m}{\mathfrak{C}}(m^{\prime},n,r)$.

###### Proof.

The isomorphism maps $X\subseteq F(m,n,r)$ to $\\{f\in
F(m^{\prime},n,r):f{\restriction_{m\times m}}\in X\\}$. ∎

######  Lemma 7.

For $3\leq m\leq n$ and $r<\omega$, ${\mathfrak{C}}(m,n,r)\in{\bf PEA}_{m}$.

###### Proof.

If $r=0$ then $Bin(n,r)=\\{Id\\}$ so ${\mathfrak{C}}(m,n,0)$ is the trivial
algebra hence ${\mathfrak{C}}(m,n,0)\in{\bf PEA}_{m}$. Now assume $r>0$. In
view of lemma 5 we only have to check the commutativity of cylindrifiers:
${\sf c}_{x}{\sf c}_{y}X={\sf c}_{y}{\sf c}_{x}X$, for $x,y<m$. This equation
is trivial if $x=y$ so assume not. By additivity, it suffices to check the
case where $X$ is an atom, $X=\\{f\\}$ for some $f\in F(m,n,r)$, that is we
must show that $g\in{\sf c}_{x}{\sf c}_{y}\\{f\\}\iff g\in{\sf c}_{y}{\sf
c}_{x}\\{f\\}$. Thus given $g\equiv_{xy}f$, it suffices to find $h\in
F(m,n,r)$ such that $f\equiv_{x}h\equiv_{y}g$. If there is $z<m,\;z\neq x,y$
and $f(y,z)=Id$ then the required $h$ is $g[y/z]$, or if $g(z,x)=Id$ the
required $h$ is $f[x/z]$. Suppose there is no such $z$, so for each
$z<m,\;z\neq x,y$ we have $f(y,z),g(x,z)\in a$. Let $h:m\times m\to Bin(n,r)$
be identical to $f$ on pairs not involving $x$, be identical to $g$ on pairs
not involving $y$ (this is well-defined, since $f\equiv_{xy}g$) and let
$h(x,y)=h(y,x)=a^{0}(i,0)$, where $i$ is the least number below $n-1$ such
that it is not the case that there is $z\neq x,y<m$ and $f(y,z),g(x,z)\in
a(i,\\_)$. Since $m\leq n$ and there are only $m-2$ possible values of $z$ in
$m\setminus\\{x,y\\}$ and $n-1$ possible values of $i$, such an $i$ must
exist. This defines $h$, it is now easy to check that $h\in F(m,n,r)$.

∎

We can now prove theorem 1 (I): if $3\leq m\leq n$ and $r<\omega$ then
${\mathfrak{C}}(m,n,r)\cong{\mathfrak{Nr}}_{m}({\mathfrak{C}}(n,n,r))$ by
lemma 6 and ${\mathfrak{C}}(n,n,r)\in{\bf PEA}_{n}$ by lemma 7, so
${\mathfrak{C}}(m,n,r)\in{\mathfrak{Nr}}_{m}{\bf PEA}_{n}$. Next, we prove
theorem 1 (II).

######  Lemma 8.

Let $3\leq m<\omega,\;2\leq n<\omega,\;r<\omega$. ${\mathfrak{Rd}}_{\bf
Sc}{\mathfrak{C}}(m,n,r)\not\in S{\mathfrak{Nr}}_{m}{\bf Sc}_{n+1}$.

###### Proof.

Suppose, for contradiction, that ${\mathcal{X}}\in{\bf Sc}_{n+1}$ and
$\prime:{\mathfrak{Rd}}_{\bf
Sc}{\mathfrak{C}}(m,n,r)\rightarrow{\mathfrak{Nr}}_{m}{\mathcal{X}}$ is an
isomorphism. Let $B\subseteq Bin(n,r)$ and let $i<j<n+1$. Define

$\alpha(B,i,j)=\sum\\{{\sf s}_{[{0}/{i}]}{\sf s}_{[{1}/{j}]}f^{\prime}:f\in
F(m,n,r),\;f(0,1)\in B\\}\;\;\in{\mathcal{X}}$

For $b\in Bin(n,r)$ we may write $\alpha(b,i,j)$ instead of
$\alpha(\\{b\\},i,j)$. (Though we do not need it, it can be checked that
$\alpha(b,i,j)=b_{i,j}^{\prime}$, for $i,j<m$.) By additivity of the
substitutions

$\sum_{b\in Bin(n,r)}\alpha(b,i,j)=1.$ (4)

Further, if $i<j<k<n+1$ and $(u,v,w)\in Forb$ then

$0=\alpha(u,i,j)\cdot\alpha(v,j,k)\cdot\alpha(w,i,k)\;\;(=\delta\mbox{ say}),$
(5)

(if this were not the case then $0\neq{\sf s}_{[{0}/{i}]}{\sf
s}_{[{1}/{j}]}{\sf s}_{[{2}/{k}]}\delta\leq u_{01}\cdot v_{12}\cdot w_{02}$,
contrary to (3)). Let

$\beta^{k}=\alpha(a^{k}(0,0),0,n)\cdot\prod_{i<n}\alpha(Id,0,i)\;\in{\mathcal{X}}.$

Since there is $f\in F(m,n,r)$ with $f(0,1)=a^{k}(0,0)$, letting
$\sigma:n+1\rightarrow n+1$ be the function
$\sigma(1)=n,\;\sigma(i)=0\;(i<n+1,\;i\neq 1$), we have $0\neq{\sf
s}_{\sigma}f^{\prime}\leq\beta^{k}$, and clearly for $k\neq
k^{\prime}<\psi(n,r)$ we have
$\beta^{k}\cdot\beta^{k^{\prime}}\leq\alpha(a^{k}(0,0),0,n)\cdot\alpha(a^{k^{\prime}}(0,0),0,n)=0$.

Let $S_{0}=\\{\beta^{k}:k<\psi(n,r)\\}$. We will prove by induction over $t$
that if $t\leq(n-1)r$ there is a set $S_{t}$ with
$|S_{t}|>\kappa((n-1)r,(n-1)r-t)$ and functions
$I_{t}:\\{0,\ldots,n-1\\}\to\\{0,\ldots,n-2\\},\;J_{t}:\\{0,\ldots,n-1\\}\to\\{0,\ldots,r-1\\}$,
such that for all $\beta,\beta^{\prime}\in S_{t}$

  1. 1.

if $l<n$ then $\beta\leq\alpha(a(I_{t}(l),J_{t}(l)),l,n)$,

  2. 2.

there is $k<\psi(n,r)$ unique to $\beta\in S_{t}$ such that
$\beta\leq\alpha(a^{k},0,n)$,

  3. 3.

${\sf c}_{n}\beta={\sf c}_{n}\beta^{\prime}$,

To see that the case $t=0$ holds: let $I_{0}(i)=0,\;J_{0}(i)=0$ (all $i<n$).

Given functions $I_{t},J_{t}$ as above and $i<n-1$ let the _index of $i$ with
respect to $I_{t},J_{t}$_ be

$ind(i,I_{t},J_{t})=max(\\{J_{t}(l):l<n-1,\;I_{t}(l)=i\\}\cup\\{-1\\}).$

Define the _rank_ $\rho(I_{t},J_{t})=\sum_{i<n-1}ind(i,I_{t},J_{t})$. Observe
that $ind(0,I_{0},J_{0})=0$ and $ind(i,I_{0},J_{0})=-1$ for $0<i<n-1$, so
$\rho(I_{0},J_{0})=0+(n-2)\times(-1)=2-n$. We also assume, inductively,

  1. 1.

$\rho(I_{t},J_{t})\geq 2-n+t$.

We have seen that this last inductive condition also holds for $t=0$.

Let $0\leq t<(n-1)r$ and assume these properties hold. Since $|{\sf
dom}(I_{t})|=n$ and $|{\sf rng}(I_{t})|\leq n-1$ there must be $u<v<n$ with
$I_{t}(u)=I_{t}(v)$. Pick such a pair $(u,v)$ and let $l=u$ if $J_{t}(u)\leq
J_{t}(v)$, else let $l=v$. Note, by choice of $l$, that if
$I^{\prime},J^{\prime}$ are functions identical to $I,J$, respectively, except
perhaps on $l$, then $\rho(I^{\prime},J^{\prime})\geq\rho(I,J)$.

Since $t<(n-1)r$ we have
$|S_{t}|>\kappa((n-1)r,(n-1)r-t)\geq\kappa((n-1)r,1)=1$. Fix some
$\beta_{0}\in S_{t}$. For each $\beta\in S_{t}\setminus\\{\beta_{0}\\}$, since
${\sf c}_{n}\beta={\sf c}_{n}\beta_{0}$, we have ${\sf c}_{n}{\sf c}_{l}{\sf
s}_{[{n}/{l}]}{\sf c}_{l}(\beta)={\sf c}_{n}{\sf c}_{l}(\beta_{0})$, hence
${\sf c}_{l}\beta_{0}\;\cdot\;{\sf s}_{[{n}/{l}]}{\sf c}_{l}\beta\neq 0$. By
(4), there is $b\in Bin(n,r)$ such that

$\delta={\sf c}_{l}\beta_{0}\;\cdot\;{\sf s}_{[{n}/{l}]}{\sf
c}_{l}\beta\;\cdot\;\alpha(b,l,n)\neq 0.$

We know that
$\beta_{0}\leq\alpha(a^{k_{0}}(0,0),0,n),\;\beta\leq\alpha(a^{k}(0,0),0,n)$
for some $k_{0}\neq k<\psi(n,r)$, so
$\delta\leq\alpha(a^{k_{0}}(0,0),0,l)\cdot\alpha(a^{k}(0,0)(0,n))\cdot\alpha(b,l,n)$.
By (5), $(a^{k_{0}}(0,0),a^{k}(0,0),b)\not\in Forb$ and we cannot have $b=Id$.
Hence $b=a^{k^{\prime}}(i,j)$ for some $i<n-1,\;j<r,\;k^{\prime}<\psi(n,r)$.
For $i<n,\;j<r$ let

$S(i,j)=\\{{\sf c}_{l}\beta_{0}\;\cdot\;{\sf s}_{[{n}/{l}]}{\sf
c}_{l}\beta\cdot\alpha(a^{k}(i,j),l,n):k<\psi(n,r),\;\beta\in
S_{t}\setminus\\{\beta_{0}\\}\\}\setminus\\{0\\}.$

By cardinalities, there is a fixed $i_{0}<n-1$ and $j_{0}<r$ such that
$|S(i_{0},j_{0})|\geq\frac{|S_{t}|-1}{(n-1)r}>\frac{\kappa((n-1)r,(n-1)r-t)-1}{(n-1)r}=\kappa((n-1)r,(n-1)r-(t+1))$.
Let $S_{t+1}=S(i_{0},j_{0})$, let $I_{t+1}$ be identical to $I_{t}$ except
that $l\mapsto i_{0}$ and let $J_{t+1}$ be identical to $J_{t}$ except that
$l\mapsto j_{0}$. If $i_{0}\not\in{\sf rng}(I_{t})$ then
$Ind(i_{0},I_{t+1},J_{t+1})=j_{0}\geq 0>-1=Ind(i_{0},I_{t},J_{t})$, otherwise
for any $p<n+1$ if $I_{t}(p)=i_{0}$ then $j_{0}>J_{t}(p)$, by (5) applied to
$(p,l,n)$, so $j_{0}=Ind(i_{0},I_{t+1},J_{t+1})>Ind(i_{0},I_{t},J_{t})$.
Either way, $\rho(I_{t+1},J_{t+1})>\rho(I_{t},J_{t})$. Hence
$S_{t+1},I_{t+1},J_{t+1}$ satisfies induction hypothesis 3. The other
induction hypotheses are straightforward.

By induction, the properties hold for all $t\leq(n-1)r$. Letting $t=(n-1)r$,
we have a set $S_{(n-1)r}$ of size strictly greater than
$\kappa((n-1)r,(n-1)r-(n-1)r)=\kappa((n-1)r,0)=0$, i.e. non-empty, and there
are functions $I_{t},J_{t}$ of rank at least $(2-n)+((n-1)r)=(n-1)(r-1)+1$, an
impossibility since for each $i<n-1$ the maximum index $i$ can have is $r-1$,
hence the maximum possible rank is $(n-1)(r-1)$. We conclude that
${\mathfrak{Rd}}_{\bf Sc}{\mathfrak{C}}(m,n,r)\not\in S{\mathfrak{Nr}}_{m}{\bf
Sc}_{n+1}$. ∎

We now concentrate on proving (III), that $\Pi_{r/U}\;{\mathfrak{C}}(m,n,r)\in
S{\mathfrak{Nr}}_{m}{\bf PEA}_{n+1}$, for any non-principal ultrafilter $U$. A
standard ultraproduct argument shows that
$\Pi_{r/U}\;{\mathfrak{C}}(m,n,r)\cong{\mathfrak{C}}(m,n,\Pi_{r/U}\;r)$ so we
have to prove that ${\mathfrak{C}}(m,n,J)\in S{\mathfrak{Nr}}_{m}{\bf
PEA}_{n+1}$, where $J=\Pi_{r/U}\;r$. Note that $J$ is a linear order
containing an infinite ascending chain. First we define a game.

######  Definition 9.

Let $m,n<\omega$, let $J$ be a linear order and let $\Lambda=(n+1)^{3}$. An
_$m$ -hypernetwork_ $h=(f,g)$ consists of some $f\in F(m,n,J)$ and a ternary
function $g:\;^{3}m\rightarrow\Lambda$ such that for all
$x,y,z,x^{\prime},y^{\prime},z^{\prime}<m$, if
$f(x,x^{\prime})=f(y,y^{\prime})=f(z,z^{\prime})=Id$ then
$g(x,y,z)=g(x^{\prime},y^{\prime},z^{\prime})$. For $X\subseteq m$ we say that
$h=(f,g)$ is _strict over $X$_ if $x\neq y\in X\Rightarrow f(x,y)\neq Id$. If
$m^{\prime}\leq m$ and $h=(f,g)$ is an $m$-hypernetwork then
$h{\restriction_{m^{\prime}}}$ denotes the $m^{\prime}$-hypernetwork obtained
from $h$ by restriction to $m^{\prime}$.
We define a game $G=G(m,n,J)$ as follows. A _play_ of $G$ is a sequence
$h_{0},h_{1},\ldots,h_{t},\;\;(t<\omega)$ of $(n+1)$-hypernetworks. In round
$t<\omega$ of the game, $\forall$ plays either an $m$-dimensional move
$\theta$ by choosing any $m$-hypernetwork $\theta$ or an amalgamation move
$(u,v,\sigma,\tau,x,y)$ where $u,v<t,\;\sigma,\tau:n+1\rightarrow
n+1,\;x,y<n+1$ and $h_{u}\sigma\equiv_{xy}h_{v}\tau$. In response to an
$m$-dimensional move $\theta$, $\exists$ must play a (n+1)-hypernetwork
$h_{t}$ such that $h_{t}{\restriction_{m}}=\theta$. In response to an
amalgamation move $(u,v,\sigma,\tau,x,y)$, $\exists$ must play a
$(n+1)$-hypernetwork $h_{t}$ such that
$h_{u}\sigma\equiv_{x}h_{t}\equiv_{y}h_{v}\tau$. If she fails to provide such
a response to either kind of move then she loses the play in that round. If
$\exists$ does not lose in any of the $\omega$ rounds of $G$ then she wins the
play.

######  Lemma 10.

Let $3\leq m<n<\omega$ and let $J$ be a linear order containing an infinite
ascending sequence. $\exists$ has a winning strategy in $G(m,n,J)$.

###### Proof.

Let $k_{0}<k_{1}<k_{2}\ldots\;\;\in J$ be an infinite ascending sequence, let
$K=\\{k_{0},k_{1},\ldots\\}\subseteq J$. We describe $\exists$’s strategy.
Consider round $t$ of a play of the game. Suppose, inductively, that $\exists$
has successfully implemented her strategy in all previous rounds $s<t$, the
play so far is $h_{0},h_{1},\ldots h_{t-1}$. Suppose $\forall$ plays an
$m$-dimensional move $\theta$. Let $\sigma:(n+1)\rightarrow m$ be the function
defined by

$\sigma(i)=\left\\{\begin{array}[]{ll}i&(i<m)\\\ 0&(m\leq
i<n+1)\end{array}\right.$

$\exists$ plays the hypernetwork $\theta\sigma$. Observe that if
$X\subseteq(n+1)$ and $|X|>m$ then $\theta\sigma$ is not strict over $X$.

Now suppose $\forall$ plays an amalgamation move $(u,v,\sigma,\tau,x,y)$ where
$h_{u}\sigma\equiv_{xy}h_{v}\tau$. To avoid trivialities assume $x\neq y$.
$\exists$ is required to find $h_{t}=(f_{t},g_{t})$ such that
$h_{u}\sigma\equiv_{x}h_{t}\equiv_{y}h_{v}\tau$. These equivalences uniquely
determine the value of $f_{t}$ on any pair from $n+1$ except $(x,y)$ and
$(y,x)$ and they determine the value of $g_{t}$ on any triple from $n+1$
except those involving both $x$ and $y$. If there is $w<t$ and
$\rho:n+1\rightarrow n+1$ such that
$h_{u}\sigma\equiv_{x}h_{w}\rho\equiv_{y}h_{v}\tau$ then $\exists$ lets
$h_{t}=h_{w}\rho$ (if there is more than one possible solution, then any will
do). Since such a move by $\forall$ is clearly superflous we will assume
henceforth that $\forall$ never makes such a move. Furthermore, we will assume
that if $\forall$ plays the amalgamation move $(u,v,\sigma,\tau,x,y)$ then
there is no $u^{\prime}<u$ and $\sigma^{\prime}:n+1\rightarrow n+1$ such that
$h_{u}\sigma\equiv_{x}h_{u^{\prime}}\sigma^{\prime}$ (if such a $u^{\prime}<u$
and $\sigma^{\prime}$ existed then $\forall$ could instead play
$(u^{\prime},v,\sigma^{\prime},\tau,x,y)$) and there is no $v^{\prime}<v$ and
$\tau^{\prime}:n+1\rightarrow n+1$ such that
$h_{v}\tau\equiv_{y}h_{v^{\prime}}\tau^{\prime}$.

Now, although we have not yet entirely defined $f_{t}$, for each
$x^{\prime},y^{\prime}<n+1$ we already know whether
$f_{t}(x^{\prime},y^{\prime})=Id$ or not (we cannot have $f_{t}(x,y)=Id$, by
our assumption about $\forall$-moves). For any
$x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}<n+1$ we write
$(x_{1},y_{1},z_{1})\sim(x_{2},y_{2},z_{2})$ iff
$f_{t}(x_{1},x_{2})=f_{t}(y_{1},y_{2})=f_{t}(z_{1},z_{2})=Id$.

First $\exists$ defines $g_{t}:^{3}\\!\\!(n+1)\rightarrow\Lambda$ by defining
$g_{t}$ on all triples involving both $x$ and $y$ in such a way that if
$\overline{x}$ is any triple involving $x$ and $y$ and if $\overline{y}$ is
any triple of elements of $(n+1)$ then
$g_{t}(\overline{x})=g_{t}(\overline{y})\iff(\overline{x}\sim\overline{y})$.
Since $\sim$ is clearly an equivalence relation and since $\Lambda=(n+1)^{3}$,
the range of $g_{t}$ is large enough to allow this.

Secondly, $\exists$ defines $f_{t}\in F(n+1,n,J)$ by letting
$f_{t}(x,y)=a^{0}(i,k)$ where

  * •

$k\in K$ is greater than each element of the finite set $\\{k^{\prime}\in
K:\exists s<t,\;x^{\prime},y^{\prime}<n+1\;f_{u}(x^{\prime},y^{\prime})\in
a(\\_,k^{\prime})\\}$, least possible subject to that.

  * •

$i<n-1$ is least such that there is no $w<n+1$ and $j\in J\setminus K$ with
$f_{u}\sigma(y,w),f_{v}\tau(w,x)\in a(i,j)$.

We will prove that the strategy may be implemented, in particular the $i<n-1$
required in the second part may always be found. To prove our claim, suppose
for contradiction that there are $w_{0},w_{1},\ldots,w_{n-2}<n+1$ such that
for each $i<n-1$ there is $j\in J\setminus K$ and
$f_{u}\sigma(y,w_{i}),(f_{v}\tau)(w_{i},x)\in a(i,j)$. Observe that $f_{u}$ is
strict over $\\{\sigma(y),\sigma(w_{i}):i<n-1\\}$, so $f_{u}$ was itself
played in response to an amalgamation move, say
$(u^{\prime},v^{\prime},\sigma^{\prime},\tau^{\prime},x^{\prime},y^{\prime})$.
By our assumption that there is no $u^{*}<u$ and $\sigma^{*}$ such that
$f_{u}\sigma\equiv_{x}f_{u^{*}}\sigma^{*}$, we see that
$\\{\sigma(y^{\prime}),\sigma(x^{\prime})\\}\subseteq\\{y,w_{0},w_{1},\ldots,w_{n-2}\\}$.
Inductively, $\exists$ chose $f_{u}(\sigma(y^{\prime}),\sigma(x^{\prime}))\in
a(\\_,k^{\prime})$ for some $k^{\prime}\in K$, hence
$\\{\sigma(y^{\prime}),\sigma(x^{\prime})\\}\subseteq\\{w_{0},\ldots,w_{n-2}\\}$.
Similarly, $f_{v}$ was played in response to an amalgamation move
$(u^{*},v^{*},\sigma^{*},\tau^{*},x^{*},y^{*}),\;f_{v}(\tau(y^{*}),\tau(x^{*}))\in
a(\\_,k^{*})$ (some $k^{*}\in K$) and
$\\{\tau(y^{*}),\tau(x^{*})\\}\subseteq\\{w_{0},\ldots,w_{n-2}\\}$. By
uniqueness of $k^{\prime}$ and $k^{*}$ we deduce that $k^{\prime}=k^{*},\;u=v$
and
$\\{\sigma(y^{\prime}),\sigma(x^{\prime})\\}=\\{\tau(y^{*}),\tau(x^{*})\\}$.
When $\exists$ played $f_{u}$ she ensured that for each $w_{h}\;(h<n-1)$ the
label $g_{u}(\sigma(y^{\prime}),\sigma(x^{\prime}),\sigma(w_{h}))$ is unique
but it is equal to $g_{v}(\tau(y^{\prime}),\tau(x^{\prime}),\tau(w_{h}))$
(since $g_{u}\sigma\equiv_{xy}g_{v}\tau$), hence $\sigma(w_{h})=\tau(w_{h})$.
But then, define $\rho:(n+1)\rightarrow(n+1)$ by $\rho(v)=\sigma(v)$, for
$v\in(n+1)\setminus\\{x\\}$, and $\rho(x)=\tau(x)$. Then
$h_{u}\sigma\equiv_{x}h_{u}\rho\equiv_{y}h_{v}\sigma$, contrary to our
assumption. This proves the claim and proves that $\exists$’s strategy can
always be implemented.

By choice of $i,k$ it is clear that $f_{t}$ avoids all forbidden triples so
indeed $f_{t}\in F(n+1,n,J)$. ∎

######  Lemma 11.

Let $3\leq m<n<\omega$ and let $J$ be a countable linear order containing an
infinite ascending sequence. Then
${\mathfrak{C}}(m,n,J)\in{\mathfrak{Nr}}_{m}{\bf PEA}_{n+1}$.

###### Proof.

Consider a play of $G(m,n,J)$ in which $\exists$ plays her winning strategy
and $\forall$ plays all possible $m$-dimensional moves and all possible
amalgamation moves. Since $J$ is countable, this can be scheduled. Let $H$ be
the set of all hypernetworks occuring in the play. As in definition 4, the
power set $\wp(H)$ is the base of a ${\bf PEA}_{n+1}$-type algebra
${\mathfrak{C}}$, where ${\sf d}_{ij=}\\{(f,g)\in H:f(i,j)=Id\\},\;{\sf
c}_{i}(X)=\\{h\in H:\exists h^{\prime}\in X,\;h^{\prime}\equiv_{i}h\\}$ and
$s_{\tau}(X)=\\{h\in H:h\tau\in X\\}$, for
$i,j<n+1,\;\tau:(n+1)\rightarrow(n+1)$. As with lemma 5 it is easy to see that
${\mathfrak{C}}$ satisfies all the ${\bf PEA}_{n+1}$ axioms other than
commutativity of cylindrifiers, and since $H$ is closed under amalgamation,
commutativity holds too, so ${\mathfrak{C}}\in{\bf PEA}_{n+1}$. The map
$\lambda:{\mathfrak{C}}(m,n,J)\rightarrow{\mathfrak{Nr}}_{m}{\mathfrak{C}}$
defined by $\iota(f)=\\{(f^{\prime},g^{\prime})\in
H:f^{\prime}{\restriction_{m}}=f\\}$ is easily shown to be an isomorphism. ∎

Since $\Pi_{r/U}{\mathfrak{C}}(m,n,r)\cong{\mathfrak{C}}(m,n,\Pi_{r/U}r)$ and
$\Pi_{r/U}r$ contains an infinite ascending sequence, this proves theorem
1(III) and completes the proof of theorem 1.

## Infinite dimensional case

Now we prove the infinite dimensional case, by lifting the dimensions for the
finite case to the transfinite; a trick due to Monk. Our proof has the same
structure as the finite dimensional case, but naturally we need an infinite
dimensional quasi- polyadic equality algebra. Let $\alpha$ be an infinite
ordinal. For each finite subset $\Gamma\subseteq\alpha$ let

$\rho_{\Gamma}\mbox{ be the unique order preserving bijection from
}|\Gamma|\mbox{ onto }\Gamma.$

Let $I=\\{\Gamma:\Gamma\subseteq\alpha,|\Gamma|<\omega\\}$. For each
$\Gamma\in I$, let $M_{\Gamma}=\\{\Delta\in I:\Gamma\subseteq\Delta\\}$, and
let $F$ be an ultrafilter on $I$ such that $\forall\Gamma\in I,\;M_{\Gamma}\in
F$ (such an ultrafilter exists because $M_{\Gamma_{1}}\cap
M_{\Gamma_{2}}=M_{\Gamma_{1}\cup\Gamma_{2}}$). Let $r<\omega$, $1\leq
k<\omega$, and let ${{\mathfrak{C}}}_{\Gamma}^{r}$ be an algebra similar to
${\bf QPEA}_{\alpha}$ such that

${\mathfrak{Rd}}^{\rho_{\Gamma}}{{\mathfrak{C}}}_{\Gamma}^{r}={{\mathfrak{C}}}(|\Gamma|,|\Gamma|+k,r).$

Let

${\mathfrak{B}}^{r}=\prod_{\Gamma/F}{\mathfrak{C}}_{\Gamma}^{r}.$

######  Theorem 12.

Let $U$ be any non-principal ultraproduct over $\omega$.

  1. 1.

${\mathfrak{B}}^{r}\in S{\mathfrak{Nr}}_{\alpha}{\bf QPEA}_{\alpha+k}$,

  2. 2.

${\mathfrak{Rd}}_{\bf Sc}{\mathfrak{B}}^{r}\not\in
S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+k+1}$ and

  3. 3.

$\Pi_{r/U}{\mathfrak{B}}^{r}\in S{\mathfrak{Nr}}_{\alpha}{\bf
QPEA}_{\alpha+k+1}$.

But first a lemma.

######  Lemma 13.

Let $\alpha$ be an infinite ordinal, let $X$ be any finite subset of $\alpha$,
let $I=\\{\Gamma:X\subseteq\Gamma\subseteq\alpha,\;|\Gamma|<\omega\\}$. For
each $\Gamma\in I$ let $M_{\Gamma}=\\{\Delta\in I:\Delta\supseteq\Gamma\\}$
and let $F$ be any ultrafilter over $I$ such that for all $\Gamma\in I$ we
have $M_{\Gamma}\in F.$ Let ${\mathcal{A}}_{\Gamma},{\mathcal{B}}_{\Gamma}$ be
${\bf QPEA}_{\alpha}$-type algebras. If for each $\Gamma\in I$ we have
${\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{A}}_{\Gamma}={\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{B}}_{\Gamma}$
then
$\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}=\Pi_{\Gamma/F}{\mathcal{B}}_{\Gamma}$.

Furthermore, if ${\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{A}}_{\Gamma}\in{\bf
QPEA}_{|\Gamma|}$, for each $\Gamma\in I$ then
$\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}\in{\bf QPEA}_{\alpha}$.

###### Proof.

Standard proof, by Łoś’ theorem. For the first part, note that the base of
$\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}$ is identical to the base of
$\Pi_{\Gamma/F}{\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{A}}_{\rho}$ which is
identical to the base of $\Pi_{\Gamma/F}{\mathcal{B}}_{\Gamma}$, by the
assumption in the first part of the lemma. Each operator $o$ of ${\bf
QPEA}_{\alpha}$ is the same for both ultraproducts because $\\{\Gamma\in
I:{\sf dim}(o)\subseteq{\sf rng}(\rho_{\Gamma})\\}\in F$.

For the second part, it suffices to prove that each of the defining axioms for
${\bf QPEA}_{\alpha}$ holds for $\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}$. Let
$\sigma=\tau$ be one of the defining equations for ${\bf QPEA}_{\alpha}$, the
number of dimension variables involved is certainly finite, indeed it can be
at most four (see definition 15.8). Take any $i,j,k,l\in\alpha$, we must prove
that
$\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}\models\sigma(i,j,k,l)=\tau(i,j,k,l)$. If
$i,j,k,l\in{\sf rng}(\rho_{\Gamma})$, say
$i=\rho_{\Gamma}(i_{0}),\;j=\rho_{\Gamma}(j_{0}),\;k=\rho_{\Gamma}(k_{0}),\;l=\rho_{\Gamma}(l_{0})$,
then
${\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{A}}_{\Gamma}\models\sigma(i_{0},j_{0},k_{0},l_{0})=\tau(i_{0},j_{0},k_{0},l_{0})$,
since ${\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathcal{A}}_{\Gamma}\in{\bf
QPEA}_{|\Gamma|}$, so
${\mathcal{A}}_{\Gamma}\models\sigma(i,j,k,l)=\tau(i,j,k,l)$. Hence
$\\{\Gamma\in
I:{\mathcal{A}}_{\Gamma}\models\sigma(i,j,k,l)=\tau(i,j,k,l)\\}\supseteq\\{\Gamma\in
I:i,j,k,l\in{\sf rng}(\rho_{\Gamma}\\}\in F$, hence
$\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}\models\sigma(i,j,k,l)=\tau(i,j,k,l)$.
Thus $\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}\in{\bf QPEA}_{\alpha}$. ∎

###### Proof of theorem 12.

For the first part, for each $\Gamma\in I$ we know that
${\mathfrak{C}}(|\Gamma|+k,|\Gamma|+k,r)\in{\bf QPEA}_{|\Gamma|+k}$ and
${\mathfrak{Nr}}_{|\Gamma|}{\mathfrak{C}}(|\Gamma|+k,|\Gamma|+k,r)\cong{\mathfrak{C}}(|\Gamma|,|\Gamma|+k,r)$
(by lemmas 6 and 7). Let $\sigma_{\Gamma}$ be the one to one function
$(|\Gamma|+k)\rightarrow(\alpha+k)$ where
$\rho_{\Gamma}\subseteq\sigma_{\Gamma}$ and
$\sigma_{\Gamma}(|\Gamma|+i)=\alpha+i$ for each $i<k$. Let
${\mathcal{A}}_{\Gamma}$ be an algebra similar to a ${\bf QPEA}_{\alpha+k}$
such that
${\mathfrak{Rd}}^{\sigma_{\Gamma}}{\mathcal{A}}_{\Gamma}={\mathfrak{C}}(|\Gamma|+k,|\Gamma|+k,r)$.
By the second part of lemma 13, with $\alpha+k$ in place of $\alpha$,
$m\cup\\{\alpha+i:i<k\\}$ in place of $X$,
$\\{\Gamma\subseteq\alpha+k:|\Gamma|<\omega,\;X\subseteq\Gamma\\}$ in place of
$I$, and with $\sigma_{\Gamma}$ in place of $\rho_{\Gamma}$, we know that
$\Pi_{\Gamma/F}{\cal{A}}_{\Gamma}\in{\bf QPEA}_{\alpha+k}$.

We prove that
${\mathfrak{B}}^{r}\subseteq{\mathfrak{Nr}}_{\alpha}\Pi_{\Gamma/F}{\mathcal{A}}_{\Gamma}$.
Recall that ${\mathfrak{B}}^{r}=\Pi_{\Gamma/F}{\mathfrak{C}}^{r}_{\Gamma}$ and
note that $C^{r}_{\Gamma}\subseteq A_{\Gamma}$ (the base of
${\mathfrak{C}}^{r}_{\Gamma}$ is ${\mathfrak{C}}(|\Gamma|,|\Gamma|+k,r)$, the
base of ${\mathcal{A}}_{\Gamma}$ is
${\mathfrak{C}}(|\Gamma|+k,|\Gamma|+k,r)$). So, for each $\Gamma\in I$,

$\displaystyle{\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathfrak{C}}_{\Gamma}^{r}$
$\displaystyle={\mathfrak{C}}((|\Gamma|,|\Gamma|+k,r)$
$\displaystyle\cong{\mathfrak{Nr}}_{|\Gamma|}{\mathfrak{C}}(|\Gamma|+k,|\Gamma|+k,r)$
$\displaystyle={\mathfrak{Nr}}_{|\Gamma|}{\mathfrak{Rd}}^{\sigma_{\Gamma}}{\cal{A}}_{\Gamma}$
$\displaystyle={\mathfrak{Rd}}^{\sigma_{\Gamma}}{\mathfrak{Nr}}_{\Gamma}{\cal{A}}_{\Gamma}$
$\displaystyle={\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathfrak{Nr}}_{\Gamma}{\cal{A}}_{\Gamma}$

By the first part of lemma 13 we deduce that
$\Pi_{\Gamma/F}{\mathfrak{C}}^{r}_{\Gamma}\cong\Pi_{\Gamma/F}{\mathfrak{Nr}}_{\Gamma}{\cal{A}}_{\Gamma}\subseteq{\mathfrak{Nr}}_{\alpha}\Pi_{\Gamma/F}{\cal{A}}_{\Gamma}$,
proving (1).

Now we prove (2), ${\mathfrak{Rd}}_{\bf
Sc}{\mathfrak{B}}^{r}\not\in{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+k+1}$.
For this assume, seeking a contradiction, that ${\mathfrak{Rd}}_{{\bf
Sc}}{\mathfrak{B}}^{r}\in S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+k+1}$,
i.e. ${\mathfrak{Rd}}_{\bf
Sc}{\mathfrak{B}}^{r}\subseteq{\mathfrak{Nr}}_{\alpha}{\mathfrak{C}}$, where
${\mathfrak{C}}\in{\bf Sc}_{\alpha+k+1}$. Let $3\leq m<\omega$ and
$\lambda:m+k+1\rightarrow\alpha+k+1$ be the function defined by $\lambda(i)=i$
for $i<m$ and $\lambda(m+i)=\alpha+i$ for $i<k+1$. Then
${\mathfrak{Rd}}^{\lambda}({\mathfrak{C}})\in{\bf Sc}_{m+k+1}$ and
${\mathfrak{Rd}}_{m}{\mathfrak{Rd}}_{{\bf
Sc}}{\mathfrak{B}}^{r}\subseteq{\mathfrak{Nr}}_{m}{\mathfrak{Rd}}^{\lambda}({\mathfrak{C}})$.
Let ${\cal{A}}={\mathfrak{Rd}}_{m}{\mathfrak{Rd}}_{\bf Sc}{\mathfrak{B}}^{r}$.
We have just shown that

${\cal{A}}\in S{\mathfrak{Nr}}_{m}{\bf Sc}_{m+k+1}.$ (6)

For $n>m$, let

$x_{n}=\\{f\in F(n,n+k,r):m\leq j<n\to\exists i<m\;f(i,j)=Id\\}.$

Then $x_{n}\in{\mathfrak{C}}(n,n+k,r)$ and ${\sf c}_{i}x_{n}\cdot{\sf
c}_{j}x_{n}=x_{n}$ for distinct $i,j<m$. Furthermore

${I_{n}:{\mathfrak{C}}}(m,m+k,r)\cong{\mathfrak{Rl}}_{x_{n}}{\mathfrak{Rd}}_{m}{{\mathfrak{C}}}(n,n+k,r).$

via

$I_{n}(S)=\\{f\in F(n,n+k,r):f\upharpoonright m\times m\in S,\forall j(m\leq
j<n\to\exists i<m\;f(i,j)=Id)\\}.$

So for each $\Gamma\in I$, $I_{|\Gamma|}$ is an isomorphism

${{\mathfrak{C}}}(m,m+k,r)\cong{\mathfrak{Rl}}_{x_{|\Gamma|}}{\mathfrak{Rd}}_{m}{{\mathfrak{C}}}(|\Gamma|,|\Gamma|+k,r).$

Let $x=(x_{|\Gamma|}:\Gamma\in I)/F\;(\in{\mathfrak{B}}^{r})$ and let
$\iota(b)=(I_{|\Gamma|}b:\Gamma\in I)/F$ for $b\in{\mathfrak{C}}(m,m+k,r)$.
Then $\iota$ is an isomorphism from ${\mathcal{{\mathfrak{Rd}}}}_{{\bf
Sc}}C(m,m+k,r)$ into ${\mathfrak{Rd}}_{{\bf
Sc}}{\mathfrak{Rl}}_{x}{\mathfrak{Rd}}_{m}{\mathfrak{B}}^{r}={\mathfrak{Rl}}_{x}{\mathfrak{Rd}}_{m}{\mathfrak{Rd}}_{{\bf
Sc}}{\mathfrak{B}}^{r}={\mathfrak{Rl}}_{x}{\cal{A}}$. Now ${\cal{A}}\in
S{\mathfrak{Nr}}_{m}{\bf Sc}_{m+k+1}$, by (6), and ${\sf c}_{i}x\cdot{\sf
c}_{j}x=x\leq{\sf s}_{[j/i]}x,$ so that ${\sf s}_{[j/i]}x\cdot{\sf
s}_{[i/j]}x=x$ for any distinct $i,j<m$.

We will now prove that

${\mathfrak{Rl}}_{x}{\cal{A}}\in S{\mathfrak{Nr}}_{m}{\bf Sc}_{m+k+1}.$ (7)

This will yield a contradiction, because it follows from this that
${\mathfrak{Rd}}_{\bf
Sc}{\mathfrak{C}}(m,m+k,r)\subseteq{\mathfrak{Rl}}_{x}{\cal{A}}\in
S{\mathfrak{Nr}}_{m}{\bf Sc}_{m+k+1}$, contrary to theorem 1(II).

The proof of this is similar to the proof of [3, theorem 2.6.38]. Let $n=k+1.$
We know that ${\cal{A}}\in S{\mathfrak{Nr}}_{m}{\bf Sc}_{m+n}$, so let
${\cal{A}}\subseteq{\mathfrak{Nr}}_{m}{\mathfrak{C}}$, where
${\mathfrak{C}}\in{\bf Sc}_{m+n}$. Let $b=x\cdot\prod_{i<n}{\sf
s}_{[0/{m+i}]}x$; then $b\in{\mathfrak{C}}.$ We proceed by induction on $n$ to
show that
${\mathfrak{Rl}}_{x}{\cal{A}}\subseteq{\mathfrak{Nr}}_{m}{\mathfrak{Rl}}_{b}{\mathfrak{C}}$
and simultaneously that ${\sf s}_{[k/l]}b\cdot{\sf s}_{[l/k]}b=b$ for all
$k,l<m+n$. The latter condition will guarantee that
${\mathfrak{Rl}}_{b}{\mathfrak{C}}\in{\bf Sc}_{m+n}$. Indeed, commutativity of
cylindrifiers follows from the fact for any $d\in C$, and distinct $k,l<m+n$,
we have ${\sf c}_{l}({\sf c}_{k}d\cdot b)\cdot b\leq{\sf c}_{l}({\sf
c}_{k}d\cdot b)$. For the base of the induction, assume that $n=1$. Then for
any $k,l<m$, $k\neq l,$ we have

${\sf s}_{[k/m]}x={\sf s}_{[k/m]}({\sf s}_{[k/l]}x\cdot{\sf s}_{[l/k]}x)={\sf
s}_{[k/l]}x\cdot{\sf s}_{[k/m]}{\sf s}_{[l/k]}x.$

By $x\leq{\sf s}_{[k/l]}x$, we get

$x\cdot{\sf s}_{[k/m]}x=x\cdot{\sf s}_{[k/m]}{\sf s}_{[l/k]}x=x\cdot{\sf
s}_{[k/m]}{\sf s}_{[l/m]}x.$

And similarly,

$x\cdot{\sf s}_{[l/m]}x=x\cdot{\sf s}_{[l/m]}{\sf s}_{[k/m]}x=x\cdot{\sf
s}_{[k/m]}{\sf s}_{[l/m]}x.$

Therefore $x\cdot{\sf s}_{[k/m]}x=x\cdot{\sf s}_{[l/m]}x$ for all $k,l<m$, and
so it readily follows that for any non-empty finite $\Gamma\subseteq m,$ we
have (*)

$b=x\cdot\prod_{i\in\Gamma}{\sf s}_{[i/m]}x.$

Now consider $k,l<m$. Then:

$\begin{split}{\sf s}_{[l/k]}b\cdot{\sf s}_{[k/l]}b&={\sf
s}_{[l/k]}(x\cdot{\sf s}_{[k/m]}x)\cdot{\sf s}_{[l/k]}(x\cdot{\sf
s}_{[l/m]}x)\\\ &={\sf s}_{[l/k]}x\cdot{\sf s}_{[k/m]}x\cdot{\sf
s}_{[l/k]}x\cdot{\sf s}_{[l/m]}x\\\ &=x\cdot{\sf s}_{[k/m]}x\cdot{\sf
s}_{[l/m]}x=b.\\\ \end{split}$

And similarly,

${\sf s}_{[k/m]}b\cdot{\sf s}_{[m/k]}b=b.$

We have proved that ${\sf s}_{[k/l]}b\cdot{\sf s}_{[l/k]}b=b$ for all $k,l\leq
m$. Now ${\mathfrak{Rl}}_{x}{\cal{A}}$ can be embedded into
${\mathfrak{Nr}}_{m}{\mathfrak{Rl}}_{b}{\mathfrak{C}}$ via

$f(a)=a\cdot{\sf s}_{[0/m]}x.$

Indeed, for any $a\in{\mathfrak{Rl}}_{x}{\cal{A}}$, we have $f(a)\leq b$. That
$f$ preserves the boolean operations is obvious. We show that $f$ is one to
one. Assume that $f(c)=f(d)$, then $c\cdot{\sf s}_{[0/m]}x=d\cdot{\sf
s}_{[0/m]}x.$ Applying ${\sf c}_{m}$ to both sides of the equation, we get
that $c\cdot{\sf c}_{m}{\sf s}_{[0/m]}x=d\cdot{\sf c}_{m}{\sf s}_{[0/m]}x$.
Hence

$c=c\cdot{\sf c}_{0}x=d\cdot{\sf c}_{0}x=d.$

We show that $f$ is a neat embedding. Let
${\cal{A}}^{\prime}={\mathfrak{Rl}}_{x}{\cal{A}}$ and
${\mathfrak{B}}^{\prime}={\mathfrak{Rl}}_{b}{\mathfrak{B}}$. Let
$a\in{\cal{A}}^{\prime}$. Then we have

$\begin{split}{\sf c}_{m}^{{\mathfrak{B}}^{\prime}}f(a)&={\sf
c}_{m}^{{\mathfrak{B}}^{\prime}}(a\cdot{\sf s}_{[0/{m}]}x)\\\ &={\sf
c}_{m}(a\cdot{\sf s}_{[0/m]}x)\cdot b\\\ &=a\cdot{\sf c}_{m}{\sf
s}_{[0/m]}x\cdot b\\\ &=a\cdot{\sf c}_{0}x\cdot b=f(a).\\\ \end{split}$

To show that $f$ preserves the non-boolean operations, we note that from (*)
we get for any $i,j\in m$, $b={\sf s}_{[i/m]}{\sf s}_{[j/m]}x\cdot b$. This
will be used in our derivations. First we check that $f$ preserves
cylindrifiers. For $a\in{\cal{A}}^{\prime}$ and $j<m$, we have

$\begin{split}f({\sf c}_{j}^{{\cal{A}}^{\prime}}a)&=f({\sf c}_{j}a\cdot x)\\\
&={\sf c}_{j}a\cdot x\cdot{\sf s}_{[0/m]}a\\\ &={\sf c}_{j}a\cdot b\\\ &={\sf
c}_{j}a\cdot{\sf s}_{[j/m]}x\cdot b\\\ &={\sf c}_{j}(a\cdot{\sf
s}_{[j/m]}x)\cdot b\\\ &={\sf c}_{j}f(a)\cdot b\\\ &={\sf
c}_{j}^{{\mathfrak{B}}^{\prime}}f(a).\\\ \end{split}$

Next we show that $f$ preserves substitutions corresponding to replacements.
For $a\in{\cal{A}}^{\prime}$ and distinct $i,j\in m$, we have

$\begin{split}f({\sf s}_{[j/i]}^{{\cal{A}}^{\prime}}a)&=f({\sf
s}_{[j/i]}a\cdot x)\\\ &={\sf s}_{[j/i]}a\cdot x\cdot{\sf s}_{[0/m]}x\\\
&={\sf s}_{[j/i]}a\cdot b\\\ &={\sf s}_{[j/i]}a\cdot{\sf s}_{[i/m]}{\sf
s}_{[j/m]}x\cdot b\\\ &={\sf s}_{[j/i]}a\cdot{\sf s}_{[j/i]}{\sf
s}_{[i/m]}{\sf s}_{[j/m]}x\cdot b\\\ &={\sf s}_{[j/i]}(a\cdot{\sf
s}_{[i/m]}{\sf s}_{[j/m]}x)\cdot b\\\ &={\sf s}_{[j/i]}(a\cdot{\sf
s}_{[i/m]}{\sf s}_{[j/m]}x\cdot b)\cdot b\\\ &={\sf s}_{[j/i]}(a\cdot{\sf
s}_{[0/m]}x\cdot b)\cdot b\\\ &={\sf s}_{[j/i]}(a\cdot{\sf s}_{[0/m]}x)\cdot
b\\\ &={\sf s}_{[i/j]}f(a)\cdot b\\\ &={\sf
s}_{[i/j]}^{{\mathfrak{B}}^{\prime}}f(a).\\\ \end{split}$

Now assume that $n\geq 2$. Let

$b^{\prime}=x\cdot\prod_{i<n-1}{\sf s}_{[0/m+i]}x.$

We have
${\cal{A}}\subseteq{\mathfrak{Nr}}_{m}{\mathfrak{Nr}}_{m+n-1}{\mathfrak{C}}.$
By the induction hypothesis, we get (**)

${\mathfrak{Rl}}_{a}{\cal{A}}\subseteq{\mathfrak{Nr}}_{m}{\mathfrak{Rl}}_{b^{\prime}}{\mathfrak{Nr}}_{m+n-1}{\mathfrak{C}},$

and

${\sf s}_{[k/l]}b^{\prime}\cdot{\sf s}_{[l/k]}b^{\prime}=b^{\prime},$

for all $k,l<m+n-1$. But

$b^{\prime}\cdot{\sf s}_{[0/m+n-1]}b^{\prime}=b^{\prime}\cdot{\sf
s}_{[0/m+n-1]}x\cdot\prod_{i<n-1}{\sf s}_{[0/m+i]}x,$

and so

$b=b^{\prime}\cdot{\sf s}_{[0/m+n-1]}b^{\prime}.$

It follows that

${\mathfrak{Rl}}_{b^{\prime}}{\mathfrak{Nr}}_{m+n-1}{\mathfrak{C}}\subseteq{\mathfrak{Nr}}_{m+n-1}{\mathfrak{Rl}}_{b}{\mathfrak{C}},$

and we are done by (**).

Thus we have proved (7), contradicting theorem 1(II). Hence
${\mathfrak{Rd}}_{\bf Sc}{\mathfrak{B}}^{r}\not\in{\mathfrak{Nr}}_{\alpha}{\bf
Sc}_{\alpha+k+1}$, as required.

Now we prove the third part of the theorem, putting the superscript $r$ to
use. Recall that
${\mathfrak{B}}^{r}=\Pi_{\Gamma/F}{\mathfrak{C}}^{r}_{\Gamma}$, where
${\mathfrak{C}}^{r}_{\Gamma}$ has the type of ${\bf QPEA}_{\alpha}$ and
${\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathfrak{C}}^{r}_{\Gamma}={\mathfrak{C}}(|\Gamma|,|\Gamma|+k,r)$.
We know that
$\Pi_{r/U}{\mathfrak{Rd}}^{\rho_{\Gamma}}{\mathfrak{C}}^{r}_{\Gamma}=\Pi_{r/U}{\mathfrak{C}}(|\Gamma|,|\Gamma|+k,r)\subseteq{\mathfrak{Nr}}_{|\Gamma|}{\mathcal{A}}_{\Gamma}$,
for some ${\mathcal{A}}_{\Gamma}\in{\bf QPEA}_{|\Gamma|+k+1}$.

Let $\lambda_{\Gamma}:|\Gamma|+k+1\rightarrow\alpha+k+1$ extend
$\rho_{\Gamma}:|\Gamma|\rightarrow\Gamma\;(\subseteq\alpha)$ and satisfy

$\lambda_{\Gamma}(|\Gamma|+i)=\alpha+i$

for $i<k+1$. Let ${\mathfrak{F}}_{\Gamma}$ be a ${\bf QPEA}_{\alpha+k+1}$ type
algebra such that
${\mathfrak{Rd}}^{\lambda_{\Gamma}}{\mathfrak{F}}_{\Gamma}={\mathcal{A}}_{\Gamma}$.
As before, by the second part of lemma 13,
$\Pi_{\Gamma/F}{\mathfrak{F}}_{\Gamma}\in{\bf QPEA}_{\alpha+k+1}$. And

$\displaystyle\Pi_{r/U}{\mathfrak{B}}^{r}$
$\displaystyle=\Pi_{r/U}\Pi_{\Gamma/F}{\mathfrak{C}}^{r}_{\Gamma}$
$\displaystyle\cong\Pi_{\Gamma/F}\Pi_{r/U}{\mathfrak{C}}^{r}_{\Gamma}$
$\displaystyle\subseteq\Pi_{\Gamma/F}{\mathfrak{Nr}}_{|\Gamma|}{\mathcal{A}}_{\Gamma}$
$\displaystyle=\Pi_{\Gamma/F}{\mathfrak{Nr}}_{|\Gamma|}{\mathfrak{Rd}}^{\lambda_{\Gamma}}{\mathfrak{F}}_{\Gamma}$
$\displaystyle\subseteq{\mathfrak{Nr}}_{\alpha}\Pi_{\Gamma/F}{\mathfrak{F}}_{\Gamma},$

proving the lemma. ∎

######  Corollary 14.

Let $\alpha$ be an infinite ordinal, let $k\in\omega$. Let ${\bf K}$ be any
class between ${\bf Sc}$ and ${\bf QPEA}$. Then $S{\mathfrak{Nr}}_{\alpha}{\bf
K}_{\alpha+k+1}\subset S{\mathfrak{Nr}}_{\alpha}{\bf K}_{\alpha+k}.$
Furthermore, $S{\mathfrak{Nr}}_{\alpha}{\bf K}_{\alpha+k+1}$ is not finite
schema axiomatisable over $S{\mathfrak{Nr}}_{\alpha}{\bf K}_{\alpha+k}$.

The first part of the corollary is credited to Pigozzi in [3], for cylindric
algebras; however it seems that Pigozzi did not publish his proof, and we have
not found a published proof elsewhere. See [4, definition 4.1.4] for the
precise definition of finitely schema axiomatisability and see [4, theorem
4.1.7] to see how non finite schema axiomatisability follows from theorem 12.

We summarize the status of the neat embedding problem in the following two
tables. The first table adresses the case when $3\leq\alpha<\omega$ and the
second table addresses the case when $\alpha\geq\omega.$ The first row in the
first table is proved in [4, theorem 5.1.3], the third row of the first table
is in [9], while the last two rows in the second table are proved in [2,
theorem 3.3], [4, theorem 5.4.17]. The rest is proved in the present paper.

Algebras | Status of the Neat Embedding Problem for $3\leq\alpha<\omega,\;m<\omega$
---|---
${\bf Df}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf Df}_{\beta}={\bf Df}_{\alpha}$ for all $\beta>\alpha.$
${\bf Sc}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+m}$
${\bf CA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf CA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf CA}_{\alpha+m}$
${\bf PA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf PA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf PA}_{\alpha+m}$
${\bf PEA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf PEA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf PEA}_{\alpha+m}$
Algebras | Status of the Neat Embedding Problem for $\alpha\geq\omega,\;m<\omega$
---|---
${\bf Df}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf Df}_{\beta}={\bf Df}_{\alpha}$ for all $\beta>\alpha.$
${\bf Sc}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf Sc}_{\alpha+m}$
${\bf CA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf CA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf CA}_{\alpha+m}$
${\bf QPA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf QPA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf QPA}_{\alpha+m}$
${\bf QPEA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf QPEA}_{\alpha+m+1}$ is n.f.a. over $S{\mathfrak{Nr}}_{\alpha}{\bf QPEA}_{\alpha+m}$
${\bf PA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf PA}_{\beta}={\bf PA}_{\alpha}$ for all $\beta>\alpha$
${\bf PEA}_{\alpha}$ |  $S{\mathfrak{Nr}}_{\alpha}{\bf PA}_{\beta}={\bf PEA}_{\alpha}$ for all $\beta>\alpha$

For $\alpha=0,1$, the problem is trivial. For $\alpha=2,$ we have for ${\bf
K}\in\\{{\bf Df},{\bf Sc},{\bf QPA}\\}$ and $\beta>2$,
$S{\mathfrak{Nr}}_{2}{\bf K}_{\beta}={\bf K}_{2}$. The ${\bf Df}$ case is
trivial, the ${\bf Sc}$ and ${\bf QPA}$ cases follow from [4, theorem 5.4.33]
without much ado. On the other hand, for ${\bf K}\in\\{{\bf CA},{\bf QPEA}\\}$
(where diagonal elements are present) and $\beta>2$, ${\bf
S}{\mathfrak{Nr}}_{2}{\bf K}_{\beta}={\bf RK}_{2}$ with ${\bf RK}_{2}$
denoting representable algebras in ${\bf K}_{2}.$ This follows from [4,
theorems 3.2.65, 5.4.34].

##  Appendix A Appendix

######  Definition 15.

Substitution Algebra, ${\bf Sc}$

[13].

Let $\alpha$ be an ordinal. By a substitution algebra of dimension $\alpha$,
briefly an ${\bf Sc}_{\alpha},$ we mean an algebra

${{\cal{A}}}=(A,+,-,{\sf c}_{i},{\sf s}_{[{i}/{j}]}:i,j<\alpha)$

where $(A,+,-)$ is a boolean algebra, ${\sf c}_{i},{\sf s}_{[{i}/{j}]}$ are
unary operations on ${\cal{A}}$ (for $i,j<\alpha$) satisfying the following
equations for all $i,j,k,l<\alpha$:

  1. 1.

${\sf c}_{i}0=0,\;x\leq{\sf c}_{i}x,\;{\sf c}_{i}(x\cdot{\sf c}_{i}y)={\sf
c}_{i}x\cdot{\sf c}_{i}y$, and ${\sf c}_{i}{\sf c}_{j}x={\sf c}_{j}{\sf
c}_{i}x,$

  2. 2.

${\sf s}_{[{i}/{i}]}x=x,$

  3. 3.

${\sf s}_{[{i}/{j}]}$ are boolean endomorphisms,

  4. 4.

${\sf s}_{[{i}/{j}]}{\sf c}_{i}x={\sf c}_{i}x,$

  5. 5.

${\sf c}_{i}{\sf s}_{[{i}/{j}]}x={\sf s}_{[{i}/{j}]}x$ whenever $i\neq j,$

  6. 6.

${\sf s}_{[{i}/{j}]}{\sf c}_{k}x={\sf c}_{k}{\sf s}_{[{i}/{j}]}x$, whenever
$k\notin\\{i,j\\},$

  7. 7.

${\sf c}_{i}{\sf s}_{[{j}/{i}]}x={\sf c}_{j}{\sf s}_{[{i}/{j}]}x,$

  8. 8.

${\sf s}_{[{j}/{i}]}{\sf s}_{[{i}/{k}]}x={\sf s}_{[{i}/{k}]}{\sf
s}_{[{j}/{i}]}x$, whenever $|\\{i,j,k,l\\}|=4,$

  9. 9.

${\sf s}_{[{l}/{i}]}{\sf s}_{[{j}/{l}]}x={\sf s}_{[{l}/{i}]}{\sf
s}_{[{j}/{i}]}x$.

Quasipolyadic algebra, ${\bf QPA}$

[18].

A quasipolyadic algebra of dimension $\alpha$, briefly a ${\bf QPA}_{\alpha}$,
is an algebra

${\cal{A}}=(A,+,-,{\sf c}_{i},{\sf s}_{[{i}/{j}]},{\sf s}_{[i,j]}:i,j<n)$

where the reduct to ${\bf Sc}_{\alpha}$ is a substitution algebra (it
satisfies (1)–(9) above) and additionally it satisfies the following equations
for all $i,j,k<\alpha$:

  1. 2’

${\sf s}_{[{i}/{i}]}x={\sf s}_{[i,i]}x=x,\text{ and }{\sf s}_{[i,j]}x={\sf
s}_{[j,i]}x,$

  2. 3’

${\sf s}_{[i,j]}$ are boolean endomorphisms

  3. 1.

${\sf s}_{[i,j]}{\sf s}_{[i,j]}x=x$,

  4. 2.

${\sf s}_{[i,j]}{\sf s}_{[i,k]}x={\sf s}_{[j,i]}{\sf s}_{[i,j]}x~{}~{}\text{
if }~{}~{}|\\{i,j,k\\}|=3$,

  5. 3.

${\sf s}_{[i,j]}{\sf s}_{[{j}/{i}]}x={\sf s}_{[{i}/{j}]}x$.

Quasipolyadic equality algebra, ${\bf QPEA}$

[18].

A quasipolyadic equality algebra of dimension $\alpha$, briefly a ${\bf
QPEA}_{\alpha}$ is an algebra

${\mathfrak{B}}=({\cal{A}},{\sf d}_{ij})_{i,j<\alpha}$

where ${\cal{A}}$ is a ${\bf QPA}_{\alpha}$ (i.e. it satisfies all the
equations above), ${\sf d}_{ij}$ is a constant and the following equations
hold, for all $i,j,k<\alpha$:

  1. 1.

${\sf s}_{[{i}/{j}]}{\sf d}_{ij}=1$,

  2. 2.

$x\cdot{\sf d}_{ij}\leq{\sf s}_{[{i}/{j}]}x$.

## References

  * [1] Andréka, H., Givant, S., Mikulas, S. Németi, I., Simon A., Notions of density that imply representability in algebraic logic. Annals of Pure and Applied logic, 91(1998), p. 93 –190.
  * [2] Daigneault, A., and Monk, J.D., Representation Theory for Polyadic algebras. Fund. Math. 52(1963), p.151-176.
  * [3] Henkin,L., Monk,J.D., and Tarski, A., Cylindric Algebras Part I. North Holland, 1971.
  * [4] Henkin,L., Monk,J.D., and Tarski,A., Cylindric Algebras Part II. North Holland, 1985.
  * [5] Hirsch R. Relation algebra reducts of cylindric algebras and complete representations. Journal of Symbolic Logic, 72(2) (2007), p.673-703.
  * [6] Hirsch R., Hodkinson I, Maddux R., Relation algebra reducts of cylindric algebras and an application to proof theory. Journal of Symbolic Logic, 67 (2002), p.197-213.
  * [7] Hirsch, R., Hodkinson, I. and Maddux, R., On provability with finitely many variables. Bulletin of Symbolic Logic, 8(3)(2002), p.329-347.
  * [8] Hirsch R., Hodkinson I., Relation algebras by games. Studies in Logic and the Foundations of Mathematics. Volume 147. (2002)
  * [9] Hirsch R., Hodkinson I., Relation algebras from cylindric algebras, II. Annals of Pure and Applied Logic, 112(2001), p. 267–297.
  * [10] Monk., J.D., Non-finitizability of classes of representable cylindric algebras. Journal of Symbolic Logic, 34 (1969), p.331-343.
  * [11] Németi, I., The Class of Neat Reducts of Cylindric Algebras is Not a Variety But is closed w.r.t. HP. Notre Dame Journal of Formal logic, 24(3) (1983), p 399-409.
  * [12] Németi,I., Algebraisation of quantifier logics, an introductory overview. Math.Inst. Budapest, Preprint, No 13 (1996). A shortened version appeared in Studia Logica, 50(4) (1991), p.465-569.
  * [13] Pinter, C. A simple algebra of first order logic. Notre Dame Journal of Formal Logic, 1(1973), p.361-366.
  * [14] Pinter, C. Cylindric algebras and algebras of substitutions. Transactions of the American Mathematical Society, 175(1973), p.167-179.
  * [15] Sayed Ahmed, T. and Németi I, On neat reducts of algebras of logic. Studia Logica, 62 (2) (2001), p.229-262.
  * [16] Sayed Ahmed, T., and Samir B., A Neat embedding theorem for expansions of cylindric algebras. Logic journal of IGPL, 15 (2007), p. 41-51.
  * [17] Sayed Ahmed, T., Neat reducts and neat embeddings in cylindric algebras In ’Cylindric-like algebras and Algebraic Logic’, Bolyai Society of Mathematical Studies, vol 22, Editors: Andréka H, Ferenzci, M. and Németi. I (2013).
  * [18] Sain, I. Thompson, R. Strictly finite schema axiomatization of quasi-polyadic algebras. In ‘Algebraic Logic’ North Holland, Editors: Andréka H, Monk D,. and Németi. (1990) I. p.539-572.


# Continuous Perception for Classifying Shapes and Weights of Garments for
Robotic Vision Applications

Li Duan1 , Gerardo Aragon-Camarasa1
1School of Computing Science, University of Glasgow, Glasgow, United Kingdom
<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://orcid.org/0000-0002-0388-752X  https://orcid.org/0000-0003-3756-5569

###### Abstract

We present an approach to continuous perception for robotic laundry tasks. Our
assumption is that the visual prediction of a garment’s shapes and weights is
possible via a neural network that learns the dynamic changes of garments from
video sequences. Continuous perception is leveraged during training by
inputting consecutive frames, of which the network learns how a garment
deforms. To evaluate our hypothesis, we captured a dataset of 40K RGB and
depth video sequences while a garment is being manipulated. We also conducted
ablation studies to understand whether the neural network learns the physical
properties of garments. Our findings suggest that a modified AlexNet-LSTM
architecture has the best classification performance for the garment’s shapes
and discretised weights. To further provide evidence for continuous
perception, we evaluated our network on unseen video sequences and computed
the ’Moving Average’ over a sequence of predictions. We found that our network
has a classification accuracy of 48% and 60% for shapes and weights of
garments, respectively.

##  1 INTRODUCTION

Perception and manipulation in robotics are an interactive process which a
robot uses to complete a task [Bohg et al., 2017]. That is, perception informs
manipulation, while manipulation of objects improves the visual understanding
of the object. Interactive perception predicates that a robot understands the
contents of a scene visually, then acts upon it, i.e. manipulation starts
after perception is completed. In this paper, we depart from the idea of
interactive perception and theorise that perception and manipulation run
concurrently while executing a task, i.e. the robot perceives the scene and
updates the manipulation task continuously (i.e. continuous perception). We
demonstrate continuous perception in a deformable object visual task where a
robot needs to understand how objects deform over time to learn its physical
properties and predict the garment’s shape and weight.

Due to their materials’ physical and geometric properties, garments usually
have folds, crumples and holes, which are irregular shaped and configured,
making garments to have a high-dimensional state space. Therefore, when a
robot manipulates a garment, the deformations of the garment is unpredictable
and complex. Due to the high dimensionality of garments and complexity in
scenarios while manipulating garments, previous approaches for predicting
categories and physical properties of garments are not robust to continuous
deformations [Tanaka et al., 2019][Martínez et al., 2019]. Prior research
[Bhat et al., 2003][Tanaka et al., 2019], [Runia et al., 2020] has leveraged
the use of simulated environments to predict how a garment deforms, however,
real-world manipulation scenarios such as grasping, folding and flipping
garments are difficult to be simulated because garments can take an infinite
number of possible configurations in which a simulation engine may fail to
capture. Moreover, simulated environments can not be fully aligned with the
real environment, and a slight perturbation in the real environment will cause
simulations to fail.

Garment configurations (garment state space) have high dimensionality,
therefore motion planning for garments requires a high dimensionality space.
This motion planning space should represent the dynamic characteristics of
garments and the robot’s dynamic capabilities to successfully plan a motion.
In this paper, we argue that it is need to learning physical properties first
to enable robotic manipulation of garments (and other deformable objects).
Garment shapes and weights are two important geometric and physical properties
of garments. In this paper, we therefore learn the physical and geometric
properties of garments from real-world garment samples. For this, garments are
being grasped from the ground and then dropped. This simple manipulation
scenario allows us to train a neural network to perceive dynamic changes from
depth images and learn physical (weights) and geometric (shapes) properties of
garments while being manipulated, see Fig 1.

To investigate the continuous perception of deformable objects, we have
captured a dataset containing video sequences of RGB and depth images. We aim
to predict the physical properties (i.e. weights) and categories of garment
shapes from a video sequence. Therefore, we address the state-of-the-art
limitations by learning dynamic changes as opposed to static representations
of garments [Jiménez and Torras, 2020, Ganapathi et al., 2020]. We use weight
and shape as the experimental variables to support our continuous perception
hypothesis. We must note that we do not address manipulation in this paper
since we aim to understand how to equip a robot best to perceive deformable
objects visually, as serves as a prerequisite for accommodating online
feedback corrections for garment robotic manipulation. Our codes and datasets
are available at: https://github.com/cvas-ug/cp-dynamics

##  2 BACKGROUND

Bhat [Bhat et al., 2003] proposed an approach to learn physical properties of
clothes from videos by minimising a squared distance error (SSD) between the
angle maps of folds and silhouettes of the simulated clothes and the real
clothes. However, their approach observes high variability while predicting
physical properties of clothes such as shear damping, bend damping and linear
drag. Li et al. [Li et al., 2018, Li et al., 2020] has proposed to integrate
particles to simulate simple fabrics and fluids in order to learn rigidness
and moving trajectories of a deformable object using a Visually Grounded
Physics Learner network (VGPL). By leveraging VGPL together with an LSTM, the
authors can predict the rigidness and future shapes of the object. In their
research, they are using particles to learn the dynamic changes of objects. In
contrast, due to the high dimensionality and complexity of garments, particles
are an approximation to the dynamic changes which cannot be fully described
for a robot manipulation task. In Bhat[Bhat et al., 2003]’s work, they study
the physical properties of garments by comparing differences between motion
video frames of real and simulated garments, where they only aim to match the
shapes between real and simulated garments. In our work, we learn the physical
properties of garments through continuously perceiving video frames of grasped
garments, which means we learn deformations of garments rather than shapes of
garments. Deformations of garments encode dynamics characteristics of
garments, which depend on their physical and geometric properties. Therefore,
our network has higher accuracy while predicting physical and geometric
properties of garments (equivalent to shapes and weights of garments) compared
to [Bhat et al., 2003].

To learn elasticity of objects, Senguapa et al. [Sengupta et al., 2020] has
proposed an approach where a robot presses the surface of objects and observes
the object’s shape changes in a simulated and a real environment. They aimed
to find the difference of the simulated and real objects Young’s modules to
estimate the object’s elasticity and estimate forces applied on the object
without any force sensor. Tanake et al. [Tanaka et al., 2019] minimised the
shape difference between real and simulated garments to find their stiffness.
In these two approaches, if there exists a small variation between simulation
and reality or if an unseen object is presented, their approaches require to
simulate novel object models again as the simulation is limited to known
object models.

Compared with previous research that has utilised temporal images to analyse
the physical properties of deformable objects, Davis et al. [Davis et al.,
2015] chose to investigate deformable objects’ physical properties in terms of
their vibration frequencies. That is, they employed a loudspeaker to generate
sonic waves on fabrics to obtain modes of vibration of fabrics and analysed
the characteristics of these modes of vibration to identify the fabrics
materials. The main limitation of this approach is in the use of high-end
sensing equipment which would make it impractical for a robotic application.
In this paper, we employ an off-the-shelf RGBD camera to learn dynamic changes
of garments.

Yang et al. [Yang et al., 2017] has proposed a CNN-LSTM architecture. Their
method consists of training a CNN-LSTM model to learn the stretch stiffness
and bend stiffness of different materials and then apply the trained model to
classify garment material types. However, suppose a garment consists of
multiple materials. In that case, the CNN-LSTM model will not be able to
predict its physical properties because their work focuses on garments with
only one fabric type. Mariolis et al. [Mariolis et al., 2015] devised a
hierarchical convolutional neural network to conduct a similar experiment to
predict the categories of garments and estimate their poses with real and
simulated depth images. Their work has pushed the accuracy of the
classification from 79.3% to 89.38% with respect to the state of the art.
However, the main limitations are that their dataset consists of 13 garments
belonging to three categories. In this paper, we address this limitation by
compiling a dataset of 20 garments belonging to five categories of similar
material types, and we have evaluated our neural network to predict unseen
garments.

Similar to this work, Martinez et al. [Martínez et al., 2019] has proposed a
continuous perception approach to predict the categories of garments by
extracting Locality Constrained Group Sparse representations (LGSR) from depth
images of the garments. However, the authors did not address the need to
understand how garments deform over time continuously as full sequences need
to be processed in order to get a prediction of the garment shape. Continuous
predictions is a prerequisite for accommodating dexterous robotic manipulation
and online feedback corrections to advanced garment robotic manipulation.

##  3 MATERIALS AND METHODS

We hypothesise that continuous perception allows a robot to learn the physical
properties of clothing items implicitly (such as stiffness, bending, etc.) via
a Deep Neural Network (DNN) because a DNN can predict the dynamic changes of
an unseen clothing item above chance. For this, we implemented an artificial
neural network that classifies shapes and weights of unseen garments (Fig. 1
and Section 3.1). Our network consists of a feature extraction network, an
LSTM unit and two classifiers for classifying the shape and weight of
garments. We input three consecutive frame images $(t,t+1,t+2)$ into our
network to predict the shape and weight of the observed garment from a
predicted feature latent space at $t+3$. We propose to use the garment’s
weight as an indicator that the network has captured and can interpret the
physical properties of garments. Specifically, the garment’s weight is a
physical property and is directly proportional to the forces applied to the
garment’s fabric over the influence of gravity.

#### Garment Dataset

To test our hypothesis, we have captured 200 videos of a garment being grasped
from the ground to a random point above the ground around 50 cm and then
dropped from this point. Each garment has been grasped and dropped down ten
times in order to capture its intrinsic dynamic properties. Videos were
captured with an ASUS Xtion Pro, and each video consists of 200 frames (the
sampling rate is 30Hz), resulting in 40K RGB and 40K depth images at a
resolution of 480$\times$680 pixels.

Our dataset features 20 different garments of five garment shape categories:
pants, shirts, sweaters, towels and t-shirts. Each shape category contains
four unique garments. Garments are made of cotton except for sweaters which
are made of acrylic and nylon. To obtain segmentation masks, we use a green
background, and we used a green sweater to remove the influence of our arm. We
then converted RGB images to a $HSV$ colour space and identified an optimal
thresholding value in the $V$ component to segment the green background and
our arm from the garment.

Figure 1: Our network is divided into feature extraction (F), an LSTM unit and
classifier networks. Depth images of a garment with a resolution of $256\times
256$ pixels are passed to the feature extraction network. Three feature latent
spaces, i.e. $C_{t}$, $C_{t}+1$ and $C_{t}+2$ from time-steps $t$, $t+1$ and
$t+2$, respectively, are concatenated and then passed to the LSTM. Each
feature latent space has a tensor size of $15\times 15$ with a channel size of
256. From the LSTM, we obtain a predicted future feature latent space
($C_{t}+3$) which is reshaped back to the original feature space size (i.e.
$[1,256,15,15]$) and input to an average pooling layer. The average pool
output with size of $[1,256,6,6]$ is flattened to $[1,9216]$ and passed to the
fully connected (FC) shape and weight classifiers.

###  3.1 Network Architecture

Our ultimate objective is to learn the dynamic properties of garments as they
are being manipulated. For this, we implemented a neural network comprising a
feature extraction network, a recurrent neural network, and a shape and a
weight classifier networks. Fig. 1 depicts the overall neural network
architecture. We split training this architecture into learning the appearance
of the garment in terms of its shape first, then learning the garments dynamic
properties from visual features using a recurrent neural network (i.e. LSTM).

#### Feature extraction

A feature extraction network is needed to describe the visual properties of
garments (RGB images) or to describe the topology of garments (depth images).
We therefore implemented 3 state of the art network architectures, namely
AlexNet[Krizhevsky et al., 2012],VGG 16[Simonyan and Zisserman, 2014] and
ResNet 18 [He et al., 2016]. In Section 4.2, we evaluate their potential for
extraction features from garments.

#### Shape and weight classifiers

The classifier components in AlexNet, Resnet and VGG-16 networks comprise
fully connected layers that are used to predict a class depending on the
visual task. In these layers, one fully connected layer is followed by a
rectifier and a regulariser, i.e. a ReLu and dropout layers. However, in this
paper, we consider whether the dropout layer will benefit the ability of the
neural network to generalise the classification prediction for garments. The
reason is that the image dataset used to train these networks contain more
than 1000 categories and millions of images [Krizhevsky et al., 2012], while
our dataset is considerable smaller (ref. Section 3). The latter means that
the dropout layers may filter out useful features while using our dataset.
Dropout layers are useful when training large datasets to avoid overfitting.
Therefore, we have experimented with modifying the fully connected networks by
removing the ReLu and dropout layers and observe their impact on the shape and
weight classification tasks. After experimenting with four different network
parameters, we found that the best performing structure comprises three fully
connected layer blocks, each of which only contains a linear layer. The number
of features stays as 9216 without any reduction, then the number reduces to
512 in the second layer, and finally, we reduce to 5 for shape and 3, for
weight as the outputs of the classifications. We do not include these
experiments in this paper as they do not directly test the hypothesis of this
paper but instead demonstrates how to optimise the classification networks for
the shape and weight classifiers in this paper.

#### LSTM Rationale

The ability to learn dynamic changes of garments is linked to perceiving the
object continuously and being able to predict future states. That is, if a
robot can predict future changes of garments, it will be able to update a
manipulation task on-the-fly by perceiving a batch of consecutive images
rather then receiving a single image and acting sequentially. For this, we
have adopted a Long Short-Term Memory (LSTM) network to learn the dynamic
changes of consecutive images. After training (ref. Section 3.2), we examined
the ability to learn garments’ dynamic changes by inputting unseen garments
images into the trained feature extractor to get their encoded feature maps
and input those encoded feature maps into the trained LSTM and evaluate if the
network (Fig. 1) can predict shapes and weights classifications.

###  3.2 Training Strategy

We split training our architecture (Fig. 1) into two parts. First, we let the
network learn the appearance or topology of garments by means of the feature
extraction and classification networks (Sections 3.1 and 3.1). After this, we
then train the LSTM network while freezing the parameters of the feature
extraction and classification networks to learn the dynamic changes of
garments.

We have used pre-trained architectures for AlexNet, Resnet 18 and VGG 16 but
fine-tuned its classifier component. For depth images, we fine-tuned the input
channel size of the first convolutional layer from 3 to 1 (for AlexNet, Resnet
18 and VGG 16). The loss function adopted is Cross-Entropy between the
predicted shape label and the target shape label. After training the feature
extraction networks, we use these networks to extract features of consecutive
images and concatenate features for the LSTM. The LSTM learning task is to
predict the next feature description from the input image sequence, and this
predicted feature description is passed to the trained classifier to obtain a
predicted shape or weight label. The loss function for training the LSTM
consists of the mean square error between the target feature vector and the
predicted feature vector generated by the LSTM, and the Cross-Entropy between
the predicted shape label and the target shape label. The loss function is:

$\mathcal{L}_{total}=\mathcal{L}_{MSE}+1000\times\mathcal{L}_{Cross-Entropy}$
(1)

We have used a ’sum’ mean squared error during training, but we have reported
our results using the average value of the mean squared error of each point in
the feature space. We must note that we multiply the cross-entropy loss by
1000 to balance the influence of the mean squared error and cross-entropy
losses.

##  4 EXPERIMENTS

For a piece of garment, shape is not an indicator of the garment’s physical
properties but the garment’s weight as it is linked to the material’s
properties such as stiffness, damping, to name a few. However, obtaining
ground truth for stiffness, damping, etc. requires the use of specialised
equipment and the goal of this paper is to learn these physical properties
implicitly. That is, we propose to use the garment’s weight as a performance
measure to validate our approach using unseen samples of garments.

To test our hypothesis, we have adopted a leave-one-out cross-validation
approach. That is, in our dataset, there are five shapes of garments: pants,
shirts, sweaters, towels and t-shirts; and for each type, there are four
garments (e.g. shirt-1, shirt-2, shirt-3 and shirt-4). Three of the four
garments (shirt-1, shirt-2 and shirt-3) are used to train the neural network,
and the other (shirt-4) is used to test the neural work (unseen samples). We
must note that each garment has different appearance such as different colour,
dimensions, weights and volumes. For weight classification, we divided our
garments into three categories: light (the garments weighed less than 180g),
medium (the garments weighed between 180g and 300g) and heavy (the garments
weighted more than 300g).

We have used a Thinkpad Carbon 6th Generation (CPU: Intel i7-8550U) equipped
with an Nvidia GTX 970, running Ubuntu 18.04. We used SGD as the optimiser for
training the feature extraction and classification networks, with a learning
rate of $1\text{\times}{10}^{-3}$ and a momentum of 0.9 for $35$ epochs. We
then used Adam for training the LSTM with a learning rate of
$1\text{\times}{10}^{-4}$ and a step learning scheduler with a step size of
$15$ and decay rate of $0.1$ for $35$ epochs. The reason for adopting
different optimisers is that Adam provides a better training result than SGD
for training the LSTM, while SGD observes faster training for the feature
extraction and classifiers. To test our hypothesis, we first experiment on
which image representation (RGB or depth images) is the best to capture
intrinsic dynamic properties of garments. We also examined three different
feature extraction networks to find the best performing network for
classifying shapes and weights of garments (Section 4.1). Finally, we evaluate
the performance of our network on a continuous perception task (Section 4.2).

Table 1: Classification accuracy (in percentages) of unseen garment shapes Feature Extractor | P | SH | SW | TW | TS | Average
---|---|---|---|---|---|---
AlexNet(depth) | 57.0 | 13.0 | 71.0 | 47.0 | 50.0 | 47.6
AlexNet(RGB) | 18.0 | 13.0 | 0.0 | 0.0 | 0.0 | 6.2
VGG16(depth) | 25.0 | 18.0 | 35.0 | 20.0 | 25.0 | 24.6
VGG16(RGB) | 9.0 | 14.0 | 20.0 | 7.0 | 11.0 | 12.2
ResNet18(depth) | 6.0 | 10.0 | 51.0 | 69.0 | 5.0 | 28.2
ResNet18(RGB) | 16.0 | 1.0 | 2.0 | 81.0 | 14.0 | 22.8
Table 2: Classification accuracy of unseen garment weights. Feature Extractor | Light | Medium | Heavy | Average
---|---|---|---|---
AlexNet (depth) | 72.0 | 18.0 | 55.0 | 48.3
AlexNet (RGB) | 82.0 | 14.0 | 7.0 | 34.3
VGG16 (depth) | 40.0 | 48.0 | 31.0 | 39.7
VGG16 (RGB) | 38.0 | 3.0 | 100.0 | 47
ResNet18 (depth) | 51.0 | 6.0 | 47.0 | 34.7
ResNet18 (RGB) | 41.0 | 5.0 | 10.0 | 18.7

###  4.1 Feature Extraction Ablation

We have tested using three different deep convolutional feature extraction
architectures: AlexNet, VGG 16 and ResNet 18. We compared the performance of
shape and weight classification of unseen garments with RGB and depth images.
These feature extractors have been coupled with a classifier without an LSTM;
effectively producing single frame predictions similar to [Sun et al., 2017].

From Table 1, it can be seen that ResNet 18 and VGG 16 overfitted the training
dataset. As a consequence, their classification performance is below or close
to a random prediction, i.e. we have 5 and 3 classes for shape and weight.
AlexNet, however, observes a classification performance above chance for depth
images. By comparing classification performances between RGB and depth images
in Table 1, we observe that depth images (47.6%) outperformed the accuracy of
a network trained on RGB images (7.4%) while using AlexNet. The reason is that
a depth image is a map that reflects the distances between each pixel and the
camera, which can capture the topology of the garment. The latter is similar
to the findings in [Sun et al., 2017, Martínez et al., 2019].

We observe a similar performance while classifying garments’ weights. AlexNet
has a classification performance of $48.3\%$ while using depth images. We must
note that the weights of garments that are labelled as ’medium’ are mistakenly
classified as ’heavy’ or ’light’. Therefore compared to the predictions on
shape, predicting weights is more difficult for our neural network on a single
shot perception paradigm. From these experiments, we, therefore, choose
AlexNet as the feature extraction network for the remainder of the following
experiments.

###  4.2 Continuous Perception

To test our continuous perception hypothesis (Section 3), we have chosen
AlexNet and a window sequence size of 3 to predict the shape and weight of
unseen video sequences from our dataset, i.e. video sequences that have not
been used for training. For this, we accumulate prediction results over the
video sequence and compute the Moving Average (MA) over the evaluated
sequence. That is, MA serves as the decision-making mechanism that determines
the shape and weight classes after observing a garment deform over time rather
than the previous three frames as in previous sections.

This experiment consists of passing 3 consecutive frames to the network to
output a shape and weight class probability for each output in the networks.
We then compute their MA values for each output before sliding into the next
three consecutive frames, e.g. slide from frame $t-2$, $t-1$, $t$ to frame
$t-1$, $t$, $t+1$. After we slide across the video sequence and accumulate MA
values, we calculated an average of the MA values for each class. We chose the
class that observes the maximum MA value as a prediction of the target
category. Our unseen test set contains 50 video sequences. Hence, we got 50
shape and weight predictions and used to calculate the confusion matrices in
Fig. 2 and Fig. 3.

From Fig. 2(left) and Fig. 3(left), it can been seen that an average
prediction accuracy of $48\%$ for shapes and an average prediction of $60\%$
for weights have been obtained for all unseen video sequences. We can observe
in Fig. 2(left) that the shirt has been wrongly classified as a pant in all
its video sequences, but the sweater is labelled correctly in most of its
sequences. Half of the towels have been wrongly recognised as a t-shirt. Also
for weight, the medium-weighted garments are wrongly classified in all their
sequences, where most of them have been categorised as heavy garments, but all
heavy garments are correctly classified. Fig. 2 (right) shows an example of
the MA over a video sequence of a shirt. It can be seen that the network
changes its prediction between being a t-shirt or a pant while the correct
class is a shirt. The reason for this is that the shirts, t-shirts and pants
in our dataset are made of cotton. Therefore, these garments have similar
physical properties, but different shapes and our neural network is not
capable of differentiating between these unseen garments, which suggests that
further manipulations are required to improve the classification prediction.
Fig. 3 (right) has suggested that the network holds a prediction as ’heavy’
over a medium-weight garment. This is because heavy garments are sweaters and
differ from the rest of the garments in terms of its materials. Therefore, our
network can classify heavy garments but has a low-performance accuracy for
shirts and pants.

As opposed to shapes, weights are a more implicit physical property which are
more difficult to be generalised. Nevertheless, the overall performance of the
network ($48\%$ for shapes and $60\%$ for weights) suggests that our
continuous perception hypothesis holds for garments with shapes such as pants,
sweaters, towels, and t-shirts and with weights such as light and heavy,
suggesting that further interactions with garments such as in [Willimon et
al., 2011, Sun et al., 2016] are required to improve the overall
classification performance. We must note that the overall shape classification
performance while validating our network is approximately $90\%$; suggesting
that the network can successfully predict known garment’s shapes based on its
dynamic properties.

Figure 2: Continuous shape prediction (Left: Moving Average Confusion Matrix;
Right: Moving Average over a video sequence) Figure 3: Continuous weight
prediction (Left: Moving Average Confusion Matrix; Right: Moving Average over
a video sequence)

##  5 CONCLUSIONS

From the ablation studies we have conducted, depth images have a better
performance over RGB images because depth captures the garment topology
properties of garments. That is, our network was able to learn dynamic changes
of the garments and make predictions on unseen garments since depth images
have a prediction accuracy of $48\%$ and $60\%$ while classifying shapes and
weights, accordingly. We also show that continuous perception improves
classification accuracy. That is, weight classification, which is an indicator
of garment physical properties, observes an increase in accuracy from 48.3% to
60% under a continous perception paradigm. This means that our network can
learn physical properties from continuous perception. However, we observed an
increase of around 1% (from 47.6% to 48%) while continuously classifying
garment’s shape. The marginal improvement while continuously classifying shape
indicates that further manipulations, such as flattening [Sun et al., 2015]
and unfolding [Doumanoglou et al., 2016] are required to bring a unknown
garment to a state that can be recognised by a robot. That is, the ability to
predict dynamic information of a piece of an unknown garment (or other
deformable objects) facilitates robots’ efficiency to manipulate it by
ensuring how the garment will deform [Jiménez and Torras, 2020, Ganapathi et
al., 2020]. Therefore, an understanding of the dynamics of garments and other
deformable objects can allow robots to accomplish grasping and manipulation
tasks with higher dexterity

From the results, we can also observe that there exist incorrect
classifications of unseen shirts because of their similarity in their
materials. Therefore, we propose to experiment on how to improve prediction
accuracy on garments with similar materials and structures by allowing a robot
to interact with garments as proposed in [Sun et al., 2016]. We also envisage
that it can be possible to learn the dynamic physical properties (stiffness)
of real garments from training a ’physical-similarity network’ (PhysNet)
[Runia et al., 2020] on simulated garment models.

## REFERENCES

  * Bhat et al., 2003 Bhat, K. S., Twigg, C. D., Hodgins, J. K., Khosla, P. K., Popović, Z., and Seitz, S. M. (2003).  Estimating cloth simulation parameters from video.  In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 37–51. Eurographics Association.
  * Bohg et al., 2017 Bohg, J., Hausman, K., Sankaran, B., Brock, O., Kragic, D., Schaal, S., and Sukhatme, G. S. (2017).  Interactive perception: Leveraging action in perception and perception in action.  IEEE Transactions on Robotics, 33(6):1273–1291.
  * Davis et al., 2015 Davis, A., Bouman, K. L., Chen, J. G., Rubinstein, M., Durand, F., and Freeman, W. T. (2015).  Visual vibrometry: Estimating material properties from small motion in video.  In Proceedings of the ieee conference on computer vision and pattern recognition, pages 5335–5343.
  * Doumanoglou et al., 2016 Doumanoglou, A., Stria, J., Peleka, G., Mariolis, I., Petrik, V., Kargakos, A., Wagner, L., Hlaváč, V., Kim, T.-K., and Malassiotis, S. (2016).  Folding clothes autonomously: A complete pipeline.  IEEE Transactions on Robotics, 32(6):1461–1478.
  * Ganapathi et al., 2020 Ganapathi, A., Sundaresan, P., Thananjeyan, B., Balakrishna, A., Seita, D., Grannen, J., Hwang, M., Hoque, R., Gonzalez, J. E., Jamali, N., Yamane, K., Iba, S., and Goldberg, K. (2020).  Learning to smooth and fold real fabric using dense object descriptors trained on synthetic color images.
  * He et al., 2016 He, K., Zhang, X., Ren, S., and Sun, J. (2016).  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778.
  * Jiménez and Torras, 2020 Jiménez, P. and Torras, C. (2020).  Perception of cloth in assistive robotic manipulation tasks.  Natural Computing, pages 1–23.
  * Krizhevsky et al., 2012 Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012).  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105.
  * Li et al., 2020 Li, Y., Lin, T., Yi, K., Bear, D., Yamins, D. L. K., Wu, J., Tenenbaum, J. B., and Torralba, A. (2020).  Visual grounding of learned physical models.
  * Li et al., 2018 Li, Y., Wu, J., Tedrake, R., Tenenbaum, J. B., and Torralba, A. (2018).  Learning particle dynamics for manipulating rigid bodies, deformable objects, and fluids.  arXiv preprint arXiv:1810.01566.
  * Mariolis et al., 2015 Mariolis, I., Peleka, G., Kargakos, A., and Malassiotis, S. (2015).  Pose and category recognition of highly deformable objects using deep learning.  In 2015 International Conference on Advanced Robotics (ICAR), pages 655–662. IEEE.
  * Martínez et al., 2019 Martínez, L., del Solar, J. R., Sun, L., Siebert, J. P., and Aragon-Camarasa, G. (2019).  Continuous perception for deformable objects understanding.  Robotics and Autonomous Systems, 118:220 – 230.
  * Runia et al., 2020 Runia, T. F., Gavrilyuk, K., Snoek, C. G., and Smeulders, A. W. (2020).  Cloth in the wind: A case study of physical measurement through simulation.  arXiv preprint arXiv:2003.05065.
  * Sengupta et al., 2020 Sengupta, A., Lagneau, R., Krupa, A., Marchand, E., and Marchal, M. (2020).  Simultaneous tracking and elasticity parameter estimation of deformable objects.  In IEEE Int. Conf. on Robotics and Automation, ICRA’20.
  * Simonyan and Zisserman, 2014 Simonyan, K. and Zisserman, A. (2014).  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556.
  * Sun et al., 2015 Sun, L., Aragon-Camarasa, G., Rogers, S., and Siebert, J. P. (2015).  Accurate garment surface analysis using an active stereo robot head with application to dual-arm flattening.  In 2015 IEEE international conference on robotics and automation (ICRA), pages 185–192. IEEE.
  * Sun et al., 2017 Sun, L., Aragon-Camarasa, G., Rogers, S., Stolkin, R., and Siebert, J. P. (2017).  Single-shot clothing category recognition in free-configurations with application to autonomous clothes sorting.
  * Sun et al., 2016 Sun, L., Rogers, S., Aragon-Camarasa, G., and Siebert, J. P. (2016).  Recognising the clothing categories from free-configuration using gaussian-process-based interactive perception.  In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 2464–2470.
  * Tanaka et al., 2019 Tanaka, D., Tsuda, S., and Yamazaki, K. (2019).  A learning method of dual-arm manipulation for cloth folding using physics simulator.  In 2019 IEEE International Conference on Mechatronics and Automation (ICMA), pages 756–762. IEEE.
  * Willimon et al., 2011 Willimon, B., Birchfield, S., and Walker, I. (2011).  Classification of clothing using interactive perception.  In 2011 IEEE International Conference on Robotics and Automation, pages 1862–1868.
  * Yang et al., 2017 Yang, S., Liang, J., and Lin, M. C. (2017).  Learning-based cloth material recovery from video.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4383–4393.