# Variations of rigidity111The work was carried out in the framework of the
State Contract of the Sobolev Institute of Mathematics, Project No.
FWNF-2022-0012.

S.V. Sudoplatov

###### Abstract

We study possibilities for semantic and syntactic rigidity, i.e., the rigidity
with respect to automorphism group and with respect to definable closure.
Variations of rigidity and their degrees are studied in general case, for
special languages and for some natural operations with structures.

Key words: definable closure, semantic rigidity, syntactic rigidity, degree of
rigidity.

##  1 Introduction

We continue to study variations of algebraic closures [1] considering and
describing semantic and syntactic possibilities for definable closures.

In Section 2, we introduce variations and degrees for semantic and syntactic
rigidity of structures, describe properties, possibilities, and dynamics for
these characteristics, in general and for theories of unary predicates. In
Section 3, indexes of rigidity are introduced and their possibilities are
described. In Sections 4 and 5, possibilities for degrees of rigidity and for
indexes of rigidity are described for disjoint unions of structures and for
compositions of structures are studied.

We use the standard model-theoretic terminology [2, 3, 4, 5, 6], notions and
notations in [1].

##  2 Variations of rigidity and their characteristics

Definition. For a set $A$ in a structure $\mathcal{M}$, $\mathcal{M}$ is
called semantically $A$-rigid or automorphically $A$-rigid if any
$A$-automorphism $f\in{\rm Aut}(\mathcal{M})$ is identical. The structure
$\mathcal{M}$ is called syntactically $A$-rigid if $M={\rm dcl}(A)$.

A structure $\mathcal{M}$ is called $\forall$-semantically /
$\forall$-syntactically $n$-rigid (respectively, $\exists$-semantically /
$\exists$-syntactically $n$-rigid), for $n\in\omega$, if $\mathcal{M}$ is
semantically / syntactically $A$-rigid for any (some) $A\subseteq M$ with
$|A|=n$.

Clearly, as above, syntactical $A$-rigidity and $n$-rigidity imply semantical
ones, and vice versa for finite structures, but not vice versa for some
infinite ones. Besides, if $\mathcal{M}$ is $Q$-semantically /
$Q$-syntactically $n$-rigid, where $Q\in\\{\forall,\exists\\}$, then
$\mathcal{M}$ is $Q$-semantically / $Q$-syntactically $m$-rigid for any $m\geq
n$.

The least $n$ such that $\mathcal{M}$ is $Q$-semantically / $Q$-syntactically
$n$-rigid, where $Q\in\\{\forall,\exists\\}$, is called the $Q$-semantical /
$Q$-syntactical degree of rigidity, it is denoted by ${\rm
deg}^{Q\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})$ and ${\rm
deg}^{Q\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$, respectively. Here if a
set $A$ produces the value of $Q$-semantical / $Q$-syntactical degree then we
say that $A$ witnesses that degree. If such $n$ does not exists we put ${\rm
deg}^{Q\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})=\infty$ and ${\rm
deg}^{Q\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=\infty$, respectively.

Notice that all these characteristics have the upper bound $|M|-1$ if the
structure $\mathcal{M}$ is finite. Moreover, if $M\setminus{\rm
dcl}(\emptyset)$ is finite then the cardinality $|M\setminus{\rm
dcl}(\emptyset)|-1$ is the upper bound for both ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})$ and ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$.

We have the following obvious characterizations for finite values of degrees:

###### Proposition 2.1

$1.$ ${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})=0$ iff
${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})=0$, and iff
the structure $\mathcal{M}$ is semantically rigid.

$2.$ ${\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=0$ iff
${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=0$, and iff
the structure $\mathcal{M}$ is syntactically rigid.

$3.$ ${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})=n\in\omega$ iff for any set $A\subseteq M$ with $|A|\geq n$
there is minimal $B\subseteq A$, under inclusion, such that $|B|=n$ and any
automorphism $f\in{\rm Aut}(\mathcal{M})$ fixing $B$ pointwise fixes all
elements in $\mathcal{M}$, too, and there are no sets of cardinalities
$n^{\prime}<n$ with that property. Here $B\subseteq A$ can be taken arbitrary
with $|B|=n$.

$4.$ ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})=n\in\omega$ iff for some set $A\subseteq M$ with $|A|\geq n$
there is minimal $B\subseteq A$, under inclusion, such that $|B|=n$ and any
automorphism $f\in{\rm Aut}(\mathcal{M})$ fixing $B$ pointwise fixes all
elements in $\mathcal{M}$, too, and there are no sets of cardinalities
$n^{\prime}<n$ with that property.

$5.$ ${\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})=n\in\omega$ iff for any set $A\subseteq M$ with $|A|\geq n$
there is minimal $B\subseteq A$, under inclusion, such that $|B|=n$ and
$M={\rm dcl}(B)$, and there are no sets of cardinalities $n^{\prime}<n$ with
that property. Here $B\subseteq A$ can be taken arbitrary with $|B|=n$.

$6.$ ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})=n\in\omega$ iff for some set $A\subseteq M$ with $|A|\geq n$
there is minimal $B\subseteq A$, under inclusion, such that $|B|=n$ and
$M={\rm dcl}(B)$, and there are no sets of cardinalities $n^{\prime}<n$ with
that property.

By the definition, we have the following monotonicity property: if
$\mathcal{M}$ is semantically / syntactically $A$-rigid and $A\subseteq
A^{\prime}\subseteq M$ then $\mathcal{M}$ is semantically / syntactically
$A^{\prime}$-rigid.

Using the definition and the monotonicity property, for any structure
$\mathcal{M}$ the following inequalities hold:

${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})\leq{\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}),$ (1)

the equality in (1) means that either there are no finite sets $A$ with
identical $A$-automorphisms only, or minimal finite sets $A$ with identical
$A$-automorphisms only have unbounded cardinalities, or all finite $A\subseteq
M$ of some fixed cardinality $n$ satisfy $M={\rm dcl}(A)$ and some $A$ with
$|A|=n$ does not have proper subsets $A^{\prime}$ such that there are
identical $A^{\prime}$-automorphisms only;

${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})\leq{\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}),$ (2)

the equality in (2) means that either there are no finite sets $A$ with
identical $A$-automorphisms only, or there is finite $A\subseteq M$ such that
$M={\rm dcl}(A)$, and there are no sets $A^{\prime}$ with less cardinalities
such that there are identical $A^{\prime}$-automorphisms only;

${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})\leq{\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}),$ (3)

the equality in (3) means that either there are no finite sets $A$ with
identical $A$-automorphisms only, or there is finite $A\subseteq M$ with
identical $A$-automorphism only and each finite $A^{\prime}\subseteq M$ with
$|A^{\prime}|\geq|A|$ has a minimal restriction $A^{\prime\prime}$, under
inclusion, with $|A^{\prime\prime}|=|A|$ and with identical
$A^{\prime\prime}$-automorphism only;

${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})\leq{\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}).$ (4)

the equality in (4) means that either there are no finite sets $A$ with ${\rm
dcl}(A)=M$, or there is finite $A\subseteq M$ with ${\rm dcl}(A)=M$ and each
finite $A^{\prime}\subseteq M$ with $|A^{\prime}|\geq|A|$ has a minimal
restriction $A^{\prime\prime}$, under inclusion, with $|A^{\prime\prime}|=|A|$
and with ${\rm dcl}(A^{\prime\prime})=M$.

###### Example 2.2

The structure $\mathcal{M}=\langle\omega,\leq\rangle$ is both semantically and
syntactically rigid, therefore ${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})={\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})={\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})=0$. We observe the same effect for arbitrary structures in
which each element is marked by a constant.

###### Example 2.3

If $\mathcal{M}$ has the empty language then

${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=|M|-1$

if $\mathcal{M}$ is finite, and and these values equal $\infty$ if
$\mathcal{M}$ is infinite.

###### Example 2.4

If $\mathcal{V}$ is a vector space over a field $F$ then we have the following
criterion for the semantic/syntactic rigidity: ${\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{V})=0$ iff ${\rm
dim}(\mathcal{V})\leq 1$ and $|F|=2$ for ${\rm dim}(\mathcal{V})=1$. If
$\mathcal{V}$ is not rigid then ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{V})={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{V})={\rm dim}(\mathcal{V})$ for finite ${\rm dim}(\mathcal{V})$,
and ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{V})=\infty$, otherwise.
Besides, ${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{V})=\infty$ if ${\rm
dim}(\mathcal{V})$ is infinite, or ${\rm dim}(\mathcal{V})\geq 1$ and $F$ is
infinite. Finally for ${\rm dim}(\mathcal{V})=n\in\omega\setminus\\{0\\}$ and
$|F|=m\in\omega\setminus\\{0\\}$ with $(n,m)\neq(1,2)$, we have ${\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{V})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{V})=(n-1)m+1$, since we
obtain the rigidity taking all vectors in a $(n-1)$-dimensional subspace
$\mathcal{V}^{\prime}$, with $(n-1)m$ elements, and a vector in
$\mathcal{V}\setminus\mathcal{V}^{\prime}$.

###### Example 2.5

Let $\mathcal{M}$ be a structure of disjoint infinite unary predicates
$P_{i}$, $i\in I$, expanded by constants for all elements in
$\bigcup\limits_{i\in I}P_{i}$. Since $\mathcal{M}$ is both semantically and
syntactically rigid we have ${\rm deg}^{Q\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})={\rm deg}^{Q\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=0$
for $Q\in\\{\forall,\exists\\}$. At the same time extending $n$ predicates
$P_{i}$ by new elements $a_{i}$ we obtain $\mathcal{N}\succ\mathcal{M}$ with
${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N})={\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N})=0$, ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{N})=n$, ${\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{N})=\infty$. Moreover,
if infinitely many $P_{i}$ are extended by new elements $a_{i}$ then the
correspondent elementary extension $\mathcal{N}^{\prime}$ of $\mathcal{M}$ has
the following characteristics: ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{N}^{\prime})=0$, ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{N}^{\prime})=n$ and ${\rm deg}^{\forall\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{N}^{\prime})={\rm deg}^{\forall\mbox{\rm-}{\rm
synt}}_{\rm rig}(\mathcal{N}^{\prime})=\infty$. Besides, if some extended
$P_{i}$ are again extended by $m$ new elements in total then an appropriate
elementary extension $\mathcal{N}_{m,n}$ has the following characteristics:
${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N}_{m,n})=m$,
${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{N}_{m,n})=m+n$,
${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N}_{m,n})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{N}_{m,n})=\infty$
including the possibility ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{N}_{\mu,n})={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{N}_{\mu,n})={\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{N}_{\mu,n})={\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{N}_{\mu,n})=\infty$ if $\mu\geq\omega$ new elements are added.

Thus by Example 2.5 the difference between ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})$ and ${\rm deg}^{\exists\mbox{\rm-}{\rm
synt}}_{\rm rig}(\mathcal{M})$ can be arbitrary large. In view of Proposition
2.1 and inequality 2 we obtain the following theorem on distributions for
these characteristics:

###### Theorem 2.6

$1.$ The pairs $\left({\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}),{\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})\right)$ belong to the set ${\rm
DEG}^{\rm\exists\mbox{\rm-}{\rm sem},\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}=\\{(\mu,\nu)\mid\mu,\nu\in\omega\cup\\{\infty\\},\mu\leq\nu\\}$.

$2.$ For each pair $(\mu,\nu)\in{\rm DEG}^{\rm\exists\mbox{\rm-}{\rm
sem},\exists\mbox{\rm-}{\rm synt}}_{\rm rig}$ there exists a structure
$\mathcal{M}_{\mu,\nu}$ such that

${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}_{\mu,\nu})=\mu,\,{\rm deg}^{\exists\mbox{\rm-}{\rm
synt}}_{\rm rig}(\mathcal{M}_{\mu,\nu})=\nu.$

Example 2.5 shows that values in ${\rm DEG}^{\rm\exists\mbox{\rm-}{\rm
sem},\exists\mbox{\rm-}{\rm synt}}_{\rm rig}$ in Theorem 2.6 are covered by
structures in countable languages $\Sigma_{1}$ of unary predicates. Now we
describe possibilities for the pairs $\left({\rm deg}^{\forall\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M}),{\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})\right)$ in these languages $\Sigma_{1}$.

###### Proposition 2.7

For any structure $\mathcal{M}$ in a language $\Sigma_{1}$ of unary predicates
the pair

$\left({\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}),{\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})\right)$

has one of the following possibilities:

$1)$ $(0,0)$, if $\mathcal{M}$ is both semantically and syntactically rigid;

$2)$ $(n,n)$, if $\mathcal{M}$ is finite with $n+1$ elements and it is not
semantically rigid that is not syntactically rigid;

$3)$ $(0,\infty)$, if $\mathcal{M}$ is infinite, semantically rigid but not
syntactically rigid;

$4)$ $(\infty,\infty)$, if $\mathcal{M}$ is infinite and both not semantically
rigid and not syntactically rigid.

Proof. If $\mathcal{M}$ is syntactically rigid then we have $\left({\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}),{\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})\right)=(0,0)$ by
the inequality (1). Now we assume that $\mathcal{M}$ is not syntactically
rigid and consider the following cases.

Case 1: $\mathcal{M}$ is semantically rigid, i.e., ${\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})=0$. In such a case
$\mathcal{M}$ is infinite since finite structures have isolated $1$-types only
and there are complete $1$-types over empty set with at least two realizations
that contradicts the semantic rigidity for the language $\Sigma_{1}$. Again
using the unary language $\Sigma_{1}$ and the arguments of [7, Section 8.1]
that all $1$-types, over empty set, are forced by formulae of quantifier free
diagrams and formulae describing estimations for cardinalities of their
solutions, with independent actions of automorphisms in distinct sets of
realizations of $1$-types. Thus each $1$-type has at most one realization in
$\mathcal{M}$. Since $\mathcal{M}$ is not syntactically rigid, $\mathcal{M}$
realizes at least one nonisolated $1$-type $p(x)$ by some unique element $a$.
Now for any $n\in\omega$ we can take $n$ realizations of other $1$-types
forming a set $A$ such that $a\notin{\rm dcl}(A)$. It implies ${\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=\infty$.

Case 2: $\mathcal{M}$ is not semantically rigid and $|M|=n+1\in\omega$. In
such a case $\mathcal{M}$ has a complete $1$-type $p(x)$ with at least two
realizations $a$ and $b$. Since there is an
$(M\setminus\\{a,b\\})$-automorphism $f$ with $f(a)=b$, we obtain ${\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})=n$ implying ${\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=n$ by the
inequality (1) and the syntactic rigidity of $\mathcal{M}$ over each
$n$-element set.

Case 3: $\mathcal{M}$ is not semantically rigid and it is infinite. In such a
case $\mathcal{M}$ has a complete $1$-type $p(x)$ with at least two
realizations $a$ and $b$ and such that realizations of other $1$-types allow
to form arbitrarily large finite set $A$ such that some $A$-automorphism
transforms $a$ in $b$. It means that ${\rm deg}^{\forall\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})=\infty$ implying ${\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})=\infty$ by the
inequality (1). $\Box$

Combining arguments for Theorems 2.6 and 2.7 we obtain the following
possibilities for tetrads ${\rm
deg}_{4}(\mathcal{M})\rightleftharpoons\left({\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M}),{\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}),{\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}),{\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})\right)$ in a language of unary predicates:

###### Corollary 2.8

For any structure $\mathcal{M}$ in a language $\Sigma_{1}$ of unary predicates
the tetrad ${\rm deg}_{4}(\mathcal{M})$ has one of the following
possibilities:

$1)$ $(0,0,0,0)$, if $\mathcal{M}$ is both semantically and syntactically
rigid;

$2)$ $(m,m,n,n)$, if $\mathcal{M}$ is finite with $n+1$ elements and it is not
semantically rigid that is not syntactically rigid with some minimal
$m$-elements set $A\subset M$, $1\leq m\leq n$, producing ${\rm dcl}(A)=M$;

$3)$ $(0,\nu,0,\infty)$, if $\mathcal{M}$ is infinite, semantically rigid but
not syntactically rigid, with $1\leq\nu\leq\infty$;

$4)$ $(\mu,\nu,\infty,\infty)$, if $\mathcal{M}$ is infinite and both not
semantically rigid and not syntactically rigid, with
$1\leq\mu\leq\nu\leq\infty$.

###### Example 2.9

Let $\mathcal{M}$ be a finitely generated algebra by a set $X$. Then by the
definition we have ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})\leq|X|$ which implies ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})\leq|X|$ by the inequality (2). Here, if
additionally the generating set $X$ admits substitutions by any $Y\subseteq M$
with $|Y|=|X|$ and these substitutions preserve the generating property then
we have ${\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})\leq|X|$ which implies ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})\leq|X|$ by the inequality (1). For instance, if
$\mathcal{M}$ is a directed graph forming a finite cycle of positive length
then ${\rm deg}_{4}(\mathcal{M})=(1,1,1,1)$.

Since algebras, with constants and unary operations, can define arbitrary
configurations of unary predicates, possibilities for characteristics ${\rm
deg}_{4}(\mathcal{M})$ in Corollary 2.8 can be realized in the class of
algebras, too.

###### Example 2.10

Let ${\rm pm}={\rm pm}(G_{1},G_{2},\mathcal{P})$ be a connected polygonometry
of a group pair $(G_{1},G_{2})$ on an exact pseudoplane $\mathcal{P}$, and
$\mathcal{M}=\mathcal{M}({\rm pm})$ be a ternary structure for ${\rm pm}$ [8].
Since all points $a$ in $\mathcal{M}$ are connected by automorphisms we have
${\rm acl}(\\{a\\})=\\{a\\}$. At the same time any two distinct points $a,b\in
M({\rm pm})$ (laying in a common line) define all points in $\mathcal{M}$ by
line and angle parameters of broken lines. It implies $M({\rm pm})={\rm
dcl}(\\{a,b\\})$. If line and angle parameters of shortest broken lines
connecting arbitrary distinct points $a$ and $b$ are defined uniquely then
$M({\rm pm})={\rm dcl}(\\{a,b\\})$ for these points, too. Hence, in such a
case, ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})={\rm
deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})\leq 2$. Moreover,
these degree values equal $1$ iff ${\rm pm}$ consists of unique line and with
at least two points, i.e., $|G_{1}|>1$ and $|G_{2}|=1$. Finally, for a
polygonometry ${\rm pm}$, the degrees equal $0$ iff ${\rm pm}$ consists of
unique point.

If parameters of broken lines do not define these broken lines by endpoints
then finite cardinalities of points in these lines can be unbounded. Indeed,
taking opposite vertices $a$ and $b$ in an $n$-cube [8, 9] or in its
polygonometry ${\rm pm}$ we obtain $n$ adjacent vertices $c_{1},\ldots,c_{n}$
for $a$ and these vertices are connected by $\\{a,b\\}$-automorphisms.
Moreover, in such a case, ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})=n+1$ witnessed, for instance, by the set
$A=\\{a,b,c_{1},\ldots,c_{n-1}\\}$.

The value ${\rm deg}_{4}(\mathcal{M}_{2})=(2,2,2,2)$ for
$\mathcal{M}_{2}=\mathcal{M}({\rm pm})$ can be increased till ${\rm
deg}_{4}(\mathcal{M}_{n})=(n,n,n,n)$, $n\geq 3$, generalizing group
trigonometries in the following way. We construct a $(n+1)$-dimensional space
consisting of points and $n$-dimensional hyperplanes. We introduce an
incidence $n$-ary relation $I_{n}$ for $n$ distinct points to lay on a common
hyperplane. Now fixing a hyperplane $H$ and $n-1$ pairwise distinct points
$a_{1},\ldots,a_{n-1}\in H$ we define an exact transitive action of a group
$G_{1}$ on $H\setminus\\{a_{1},\ldots,a_{n-1}\\}$, i.e., on $H$ with respect
to $a_{1},\ldots,a_{n-1}$, such that this action is transformed for any
pairwise distinct points $a^{\prime}_{1},\ldots,a^{\prime}_{n-1}\in H$. Since
each $H$ can be defined by its $n-1$ distinct points with actions, we can fix
$a_{1},\ldots,a_{n-1}$ and move $a_{n}\in
H\setminus\\{a_{1},\ldots,a_{n-1}\\}$ into points $a^{\prime}_{n}$ in other
hyperplanes $H^{\prime}$ containing $a_{1},\ldots,a_{n-1}$. Collecting these
movements we define an action of a group $G_{2}$ on that bundle of hyperplanes
containing $a_{1},\ldots,a_{n-1}$. Then we spread actions of $G_{1}$ and
$G_{2}$ for any hyperplanes and bundles of hyperplanes, respectively, such
that all pairwise distinct $a_{1},\ldots,a_{n-1}$ and
$a^{\prime}_{1},\ldots,a^{\prime}_{n-1}$ are connected by automorphisms with
respect to these actions.

For instance, taking the set $P$ of planes in $\mathbb{R}^{3}$, a plane
$\pi\in P$ and distinct points $a_{1},a_{2}\in P$ the action of $G_{1}$ can be
defined as $\mathbb{R}\times A$ with the side group $\mathbb{R}$ and angle
group $A$ defining both the directed distance $d\in\mathbb{R}$ from $a_{1}$ to
a point $a_{3}\in\pi$ and the angle value $\alpha$ from the side
$a_{1}\hat{\,}a_{2}$ to the side $a_{1}\hat{\,}a_{3}$. And $G_{2}$ is the
rotation group for the planes in $P$ around the lines $l(a_{1},a_{2})$.

Now we extend the language $\\{I_{n}\\}$ by $(n+1)$-ary predicates
$Q_{g_{1}}$, $g_{1}\in G_{1}$, such that first $(n-1)$-coordinates
$\overline{a}$ in $\langle\overline{a},b,c\rangle\in Q_{g_{1}}$ are exhausted
by $a_{1},\ldots,a_{n-1}$ and $c=bg_{1}$ with respect to
$a_{1},\ldots,a_{n-1}$. Simultaneously we define predicates $R_{g_{2}}$,
$g_{2}\in G_{2}$, of arities $n+1$ such that each $R_{g_{2}}$ realizes a
rotation of a hyperplane with respect to $a_{1},\ldots,a_{n-1}$ by the element
$g_{2}$. We obtain a structure $\mathcal{M}_{n}$ whose values ${\rm
deg}^{Q\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}_{n})$ and ${\rm
deg}^{Q\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}_{n})$, for
$Q\in\\{\forall,\exists\\}$ equal $n$.

The construction above admits a generalization for polygonometries ${\rm
pm}(G_{1},G_{2},\mathcal{P})$ of group pairs transforming $(G_{1},G_{2})$ a
pseudoplane $\mathcal{P}$ to a pseudospace $\mathcal{S}$ with hyperplanes $H$
such that $H={\rm dcl}(\\{a_{1},\ldots,a_{n}\\})$ for any pairwise distinct
points $a_{1},\ldots,a_{n}\in H$ and with ${\rm
dcl}(\\{b_{1},\ldots,b_{n-1}\\})=\\{b_{1},\ldots,b_{n-1}\\}$ for any
$b_{1},\ldots,b_{n-1}\in\mathcal{S}$.

Comparing characteristics ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})$ / ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})$ and ${\rm deg}^{\forall\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M})$ / ${\rm deg}^{\forall\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M})$ we observe that the first ones produce cardinalities of
“best”, i.e., minimal sets generating the structure $\mathcal{M}$ and the
second ones give cardinalities of “worst” generating sets. It is natural to
describe possibilities of “intermediate” generating sets. For this aim we
define the degrees of rigidity with respect to a subset $A$ of $M$ as follows:

Definition. For a set $A$ in $\mathcal{M}$ and an expansion $\mathcal{M}_{A}$
of $\mathcal{M}$ by constants in $A$, the least $n$ such that
$\mathcal{M}_{A}$ is $Q$-semantically / $Q$-syntactically $n$-rigid, where
$Q\in\\{\forall,\exists\\}$, is called the $(Q,A)$-semantical /
$(Q,A)$-syntactical degree of rigidity, it is denoted by ${\rm
deg}^{Q\mbox{\rm-}{\rm sem}}_{{\rm rig},A}(\mathcal{M})$ and ${\rm
deg}^{Q\mbox{\rm-}{\rm synt}}_{{\rm rig},A}(\mathcal{M})$, respectively. If
such $n$ does not exists we put ${\rm deg}^{Q\mbox{\rm-}{\rm sem}}_{{\rm
rig},A}(\mathcal{M})=\infty$ and ${\rm deg}^{Q\mbox{\rm-}{\rm synt}}_{{\rm
rig},A}(\mathcal{M})=\infty$, respectively.

Any expansion $\mathcal{M}_{A}$ of $\mathcal{M}$ with ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{A})=0$, for $s\in\\{{\rm
sem},{\rm synt}\\}$, is called a $s$-rigiditization or simply a rigiditization
of $\mathcal{M}$.

We have the following properties for $(Q,A)$-semantical and
$(Q,A)$-syntactical degrees of rigidity:

###### Proposition 2.11

Let $\mathcal{M}$ be a structure, $A\subseteq M$, $Q\in\\{\forall,\exists\\}$,
$s\in\\{{\rm sem},{\rm synt}\\}$. Then the following assertions hold:

$1.$ (Preservation of degrees of rigidity) If $A\subseteq{\rm dcl}(\emptyset)$
then ${\rm deg}^{Q\mbox{\rm-}s}_{\rm rig}(\mathcal{M})={\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},A}(\mathcal{M})$.

$2.$ (Rigiditization) If $A$ contains a witnessing set for the finite value
${\rm deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M})$ then ${\rm
deg}^{\exists\mbox{\rm-}s}_{{\rm rig},A}(\mathcal{M})=0$.

$3.$ (Monotony) If $A\subseteq B\subseteq M$ then ${\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},A}(\mathcal{M})\geq{\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},B}(\mathcal{M})$.

$4.$ (Additivity) If $A$ witnesses the finite value ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M})$ then for any
$A^{\prime}\subseteq A$,

${\rm deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M})={\rm
deg}^{\exists\mbox{\rm-}s}_{{\rm rig},A^{\prime}}(\mathcal{M})+{\rm
deg}^{\exists\mbox{\rm-}s}_{{\rm rig},A\setminus A^{\prime}}(\mathcal{M}).$

$5.$ (Cofinite character) If $A$ is cofinite in $\mathcal{M}$ then ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{{\rm rig},A}(\mathcal{M})$ and ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{{\rm rig},A}(\mathcal{M})$ are natural.

$6.$ (Finite rigiditization) Any cofinite set $A$ in $\mathcal{M}$ has a
minimal finite extension $A^{\prime}$ such that $\mathcal{M}_{A^{\prime}}$ is
semantically / syntactically rigid.

Proof. 1. If $A\subseteq{\rm dcl}(\emptyset)$ then ${\rm
Aut}(\mathcal{M})={\rm Aut}(\mathcal{M}_{A})$ and therefore the equalities
${\rm deg}^{Q\mbox{\rm-}s}_{\rm rig}(\mathcal{M})={\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},A}(\mathcal{M})$ hold for $s={\rm sem}$. For
the case $s={\rm synt}$ the required equalities are satisfied in view of ${\rm
dcl}(B)={\rm dcl}(A\cup B)$ for any $B\subseteq M$.

2\. If $A$ contains a witnessing set for the finite value ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})$ then there exists
identical $A$-automorphism of $\mathcal{M}$ only implying ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{{\rm rig},A}(\mathcal{M})=0$. Similarly if
$A$ contains a witnessing set for the finite value ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$ then ${\rm
dcl}(A)=M$ producing ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{{\rm
rig},A}(\mathcal{M})=0$.

3\. If $A\subseteq B\subseteq M$ then ${\rm Aut}(\mathcal{M}_{B})\leq{\rm
Aut}(\mathcal{M}_{A})$ therefore the inequalities ${\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},A}(\mathcal{M})\geq{\rm
deg}^{Q\mbox{\rm-}s}_{{\rm rig},B}(\mathcal{M})$ hold for $s={\rm sem}$. For
the case $s={\rm synt}$ the required equalities are satisfied in view of ${\rm
dcl}(A\cup C)\subseteq{\rm dcl}(B\cup C)$ for any $C\subseteq M$.

4\. If $A$ witnesses the finite value ${\rm deg}^{\exists\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})$ then we divide $A$ into two disjoint parts $A_{1}$ and
$A_{2}$ and by the definition of ${\rm deg}^{\exists\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})$, both $A_{1}$ and $A_{2}$ are extended till minimal $A$
witnessing the semantic / syntactic rigidity. Thus $A_{1}$ witnesses the value
${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}_{A_{2}})$ and
$A_{2}$ witnesses the value ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}_{A_{1}})$ producing the required equation ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M})={\rm
deg}^{\exists\mbox{\rm-}s}_{{\rm rig},A^{\prime}}(\mathcal{M})+{\rm
deg}^{\exists\mbox{\rm-}s}_{{\rm rig},A\setminus A^{\prime}}(\mathcal{M}).$

5\. If $A$ is cofinite in $\mathcal{M}$ then there are only finitely many
elements, all in $M\setminus A$, witnessing the values ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{{\rm rig},A}(\mathcal{M})$ and ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{{\rm rig},A}(\mathcal{M})$. Thus these
values are natural.

6\. It is immediately implied by Items 2 and 5. $\Box$

In view of Proposition fixing a subset in $\mathcal{M}$ large enough we obtain
its rigiditization. At the same time the following assertion clarifies that
small subsets can produce the rigiditization for structures in bounded
cardinalities only.

###### Proposition 2.12

$1.$ If ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$ is
finite then $|M|\leq{\rm max}\\{\Sigma(\mathcal{M}),\omega\\}$.

$1.$ If $\mathcal{M}$ is homogeneous and ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})$ is finite then $|M|\leq 2^{{\rm
max}\\{\Sigma(\mathcal{M}),\omega\\}}$.

Proof. 1. If ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$
is finite then there is a finite set $A\subseteq M$ witnessing that value,
with $M={\rm dcl}(A)$. This equality is witnessed by at most by ${\rm
max}\\{\Sigma(\mathcal{M}),\omega\\}$ formulae such that each element in
$\mathcal{M}$ is defined by a formula in the language
$\Sigma(\mathcal{M}_{A})$. Since there are ${\rm
max}\\{\Sigma(\mathcal{M}),\omega\\}$ $\Sigma(\mathcal{M}_{A})$-formulae we
obtain at most ${\rm max}\\{\Sigma(\mathcal{M}),\omega\\}$ elements in
$\mathcal{M}$.

2\. If a finite set $A\subseteq M$ witnesses the finite value ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})$ and $\mathcal{M}$
is homogeneous possibilities for $A$-automorphisms fixing elements of
$\mathcal{M}$ are exhausted by single realizations of types in $S^{1}(A)$.
Since there are at most $2^{{\rm max}\\{\Sigma(\mathcal{M}),\omega\\}}$ these
types that value is the required upper bound for the cardinality of
semantically rigid structure $\mathcal{M}_{A}$. $\Box$

Proposition 2.12 immediately implies the following:

###### Corollary 2.13

$1.$ If ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{{\rm rig},A}(\mathcal{M})$
is finite then $|M|\leq{\rm max}\\{\Sigma(\mathcal{M}),|A|,\omega\\}$.

$1.$ If $\mathcal{M}$ is homogeneous and ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{{\rm rig},A}(\mathcal{M})$ is finite then $|M|\leq 2^{{\rm
max}\\{\Sigma(\mathcal{M}),|A|,\omega\\}}$.

##  3 Indexes of rigidity

Definition. For a set $A$ in a structure $\mathcal{M}$ the index of rigidity
of $\mathcal{M}$ over $A$, denoted by ${\rm ind}_{\rm rig}(\mathcal{M}/A)$ is
the supremum of cardinalities for the set of solutions of algebraic types
${\rm tp}(a/A)$ for $a\in M$. We put ${\rm ind}_{\rm rig}(\mathcal{M})={\rm
ind}_{\rm rig}(\mathcal{M}/\emptyset)$. Here we assume that ${\rm ind}_{\rm
rig}(\mathcal{M})=0$ if $\mathcal{M}$ does not have algebraic types ${\rm
tp}(a)$ for $a\in M$.

###### Remark 3.1

By the definition we have ${\rm ind}_{\rm rig}(\mathcal{M}/A)\in\omega+1$.

###### Example 3.2

1\. If $\mathcal{M}$ is a structure of unary predicates $P_{i}$, $i\in I$,
then ${\rm ind}_{\rm rig}(\mathcal{M})=0$ iff there are no finite nonempty
intersections $P^{\delta_{1}}_{i_{1}}\cap\ldots\cap P^{\delta_{k}}_{i_{k}}$,
$\delta_{1},\ldots,\delta_{k}\in\\{0,1\\}$. We have ${\rm ind}_{\rm
rig}(\mathcal{M})=1$ iff ${\rm dcl}(\emptyset)\neq\emptyset$ and there are no
maximal finite intersections $P^{\delta_{1}}_{i_{1}}\cap\ldots\cap
P^{\delta_{k}}_{i_{k}}$ with at least two elements. Besides, ${\rm ind}_{\rm
rig}(\mathcal{M})\in\omega$ iff these finite intersections have bounded
cardinalities, and all natural possibilities $n$ are realized by predicates
with exactly $n$ elements and infinite complements. Otherwise, i.e., for ${\rm
ind}_{\rm rig}(\mathcal{M})=\omega$, these finite intersections have unbounded
cardinalities.

2\. If $\mathcal{M}$ is a structure of an equivalence relation $E$, then ${\rm
ind}_{\rm rig}(\mathcal{M})=0$ iff there are no finite $E$-classes. We have
${\rm ind}_{\rm rig}(\mathcal{M})=1$ iff ${\rm dcl}(\emptyset)\neq\emptyset$
and there are no finite $E$-classes with at least two elements. Besides, ${\rm
ind}_{\rm rig}(\mathcal{M})\in\omega$ iff these $E$-classes have bounded
cardinalities, and all natural possibilities $n$ are realized by infinitely
many $E$-classes with exactly $n$ elements. Otherwise, i.e., for ${\rm
ind}_{\rm rig}(\mathcal{M})=\omega$, these $E$-classes have unbounded
cardinalities.

3\. If $\mathcal{M}=\mathcal{M}({\rm pm})$ for a polygonometry ${\rm pm}$ then
${\rm ind}_{\rm rig}(\mathcal{M})=0$ iff ${\rm pm}$ has infinitely many
points. Otherwise, if ${\rm pm}$ has $n\in\omega$ points then ${\rm ind}_{\rm
rig}(\mathcal{M})=n$.

More generally, we have the following possibilities for a model $\mathcal{M}$
of transitive theory $T$, i.e., of a theory with $|S^{1}(\emptyset)|=1$:

i) ${\rm ind}_{\rm rig}(\mathcal{M})=0$, if $\mathcal{M}$ is infinite;

ii) ${\rm ind}_{\rm rig}(\mathcal{M})=|\mathcal{M}|$, if $\mathcal{M}$ is
finite.

In view of Remark 3.1 the following assertion describes possibilities of
indexes of rigidity:

###### Proposition 3.3

For any $\lambda\in\omega+1$ there is a structure $\mathcal{M}_{\lambda}$ such
that ${\rm ind}_{\rm rig}(\mathcal{M}_{\lambda})=\lambda$.

Proof follows by Example 3.2. $\Box$

##  4 Variations of rigidity for disjoint unions of structures

Definition [10]. The disjoint union
$\bigsqcup\limits_{n\in\omega}\mathcal{M}_{n}$ of pairwise disjoint structures
$\mathcal{M}_{n}$ for pairwise disjoint predicate languages $\Sigma_{n}$,
$n\in\omega$, is the structure of language
$\bigcup\limits_{n\in\omega}\Sigma_{n}\cup\\{P^{(1)}_{n}\mid n\in\omega\\}$
with the universe $\bigsqcup\limits_{n\in\omega}M_{n}$, $P_{n}=M_{n}$, and
interpretations of predicate symbols in $\Sigma_{n}$ coinciding with their
interpretations in $\mathcal{M}_{n}$, $n\in\omega$. The disjoint union of
theories $T_{n}$ for pairwise disjoint languages $\Sigma_{n}$ accordingly,
$n\in\omega$, is the theory

$\bigsqcup\limits_{n\in\omega}T_{n}\rightleftharpoons{\rm
Th}\left(\bigsqcup\limits_{n\in\omega}\mathcal{M}_{n}\right),$

where $\mathcal{M}_{n}\models T_{n}$, $n\in\omega$.

###### Theorem 4.1

For any disjoint predicate structures $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$,
and $s\in\\{{\rm sem},{\rm synt}\\}$ the following conditions hold:

$1.$ ${\rm deg}^{\exists\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})={\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})+{\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})$, in particular, ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})$ is
finite iff ${\rm deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})$ and
${\rm deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})$ are finite.

$2.$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})=0$ iff ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})=0$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})=0$.

$3.$ If ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})>0$ then it is finite iff ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})>0$ is finite and
$\mathcal{M}_{2}$ is finite, or ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{2})>0$ is finite and $\mathcal{M}_{1}$ is finite. Here,

${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})={\rm max}\\{|M_{1}|+{\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2}),|M_{2}|+{\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})\\}.$

Proof. 1. Let $A_{i}\subset M_{i}$ be sets witnessing values ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{i})$, $i=1,2$. By the
definition of $\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$, $A_{1}$ and $A_{2}$ are
disjoint and $A_{1}\cup A_{2}$ witnesses the value ${\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})$.
Thus ${\rm deg}^{\exists\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})={\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})+{\rm
deg}^{\exists\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})$.

2\. If ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})=0$ then the empty set witnesses
that $\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$, $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ are $s$-rigid, i.e., rigid with respect to $s$, implying
${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})=0$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})=0$. Conversely, if ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})=0$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})=0$ then the empty set
witnesses that $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ are $s$-rigid. Now by
the definition of $\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$ we observe that
$\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$ is $s$-rigid, too, implying ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})=0$.

3\. Let ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})>0$ be finite, then by Item 2, ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})>0$ or ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})>0$. Assuming that ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{i})>0$ we can not witness
that value by subsets of $M_{3-i}$, $i=1,2$. Thus $M_{3-i}$ should be finite.
Conversely, let ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})>0$
be finite and $\mathcal{M}_{2}$ be finite, or ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})>0$ be finite and
$\mathcal{M}_{1}$ be finite. Then we can take ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{1})$ elements of $M_{1}$ and
all elements of $M_{2}$ obtaining the $s$-rigidity of
$\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$. Similarly we can take ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}_{2})$ elements of $M_{2}$ and
all elements of $M_{1}$ obtaining the $s$-rigidity of
$\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$, too. Thus, the finite value ${\rm
max}\\{|M_{1}|+{\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{2}),|M_{2}|+{\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1})\\}$ equals ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})$. $\Box$

Theorem 4.1 and Corollary 2.8 immediately imply:

###### Corollary 4.2

For any structures $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ in a language
$\Sigma_{1}$ of unary predicates the tetrad ${\rm
deg}_{4}(\mathcal{M}_{1}\sqcup\mathcal{M}_{2})$ has one of the following
possibilities:

$1)$ $(0,0,0,0)$, if $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ are both
semantically and syntactically rigid;

$2)$ $(m,m,n,n)$, if $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ are finite with
$|M_{1}\,\dot{\cup}\,M_{2}|=n+1$ elements and some $\mathcal{M}_{i}$ is not
semantically rigid that is not syntactically rigid with some minimal
$m_{1}$-elements set $A_{1}\subset M_{1}$ producing ${\rm dcl}(A_{1})=M_{1}$
and some minimal $m_{2}$-elements set $A_{2}\subset M_{2}$ producing ${\rm
dcl}(A_{2})=M_{2}$, where $m=m_{1}+m_{2}\leq n-1$;

$3)$ $(0,\nu,0,\infty)$, if $\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$ is
infinite, $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ are semantically rigid but
some of them is not syntactically rigid, with $1\leq\nu\leq\infty$, $\nu={\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}_{1})+{\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}_{2})$;

$4)$ $(\mu,\nu,\infty,\infty)$, if $\mathcal{M}_{1}\sqcup\mathcal{M}_{2}$ is
infinite, $\mathcal{M}_{1}$ or $\mathcal{M}_{2}$ is not semantically rigid,
$\mathcal{M}_{1}$ or $\mathcal{M}_{2}$ is not syntactically rigid, with
$1\leq\mu\leq\nu\leq\infty$, $\mu={\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}_{1})+{\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}_{2})$, $\nu={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}_{1})+{\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}_{2})$.

###### Theorem 4.3

For any disjoint predicate structures $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$,
and a set $A\subseteq M_{1}\cup M_{2}$,

${\rm ind}_{\rm rig}((\mathcal{M}_{1}\sqcup\mathcal{M}_{2})/A)={\rm
max}\\{{\rm ind}_{\rm rig}(\mathcal{M}_{1}/(M_{1}\cap A)),{\rm ind}_{\rm
rig}(\mathcal{M}_{2})/(M_{2}\cap A)\\}.$

Proof. By the definition of disjoint union types in $S^{1}(A)$ are locally
realized either in $\mathcal{M}_{1}$ or in $\mathcal{M}_{2}$. Moreover, they
are forced by their restrictions to $M_{1}$ or $M_{2}$. So algebraic types
$p(x)\in S^{1}(A)$ are defined in $\mathcal{M}_{1}$ or in $\mathcal{M}_{2}$ by
their restrictions to $M_{1}\cap A$ and to $M_{2}\cap A$. Now we collect
possibilities for cardinalities of sets of realizations of algebraic types in
$S^{1}(M_{1}\cap A)$ and in $S^{1}(M_{2}\cap A)$. We either choose a maximal
natural cardinality obtaining natural $n={\rm ind}_{\rm
rig}((\mathcal{M}_{1}\sqcup\mathcal{M}_{2})/A)$ with $n={\rm max}\\{{\rm
ind}_{\rm rig}(\mathcal{M}_{1}/(M_{1}\cap A)),{\rm ind}_{\rm
rig}(\mathcal{M}_{2})/(M_{2}\cap A)\\}$ or there are no maximal natural
cardinality with both ${\rm ind}_{\rm
rig}((\mathcal{M}_{1}\sqcup\mathcal{M}_{2})/A)=\omega$ and ${\rm max}\\{{\rm
ind}_{\rm rig}(\mathcal{M}_{1}/(M_{1}\cap A)),{\rm ind}_{\rm
rig}(\mathcal{M}_{2})/(M_{2}\cap A)\\}=\omega$. $\Box$

##  5 Variations of rigidity for compositions of structures

Recall the notions of composition for structures and theories.

Definition [11]. Let $\mathcal{M}$ and $\mathcal{N}$ be structures of
relational languages $\Sigma_{\mathcal{M}}$ and $\Sigma_{\mathcal{N}}$
respectively. We define the composition $\mathcal{M}[\mathcal{N}]$ of
$\mathcal{M}$ and $\mathcal{N}$ satisfying the following conditions:

1)
$\Sigma_{\mathcal{M}[\mathcal{N}]}=\Sigma_{\mathcal{M}}\cup\Sigma_{\mathcal{N}}$;

2) $M[N]=M\times N$, where $M[N]$, $M$, $N$ are universes of
$\mathcal{M}[\mathcal{N}]$, $\mathcal{M}$, and $\mathcal{N}$ respectively;

3) if $R\in\Sigma_{\mathcal{M}}\setminus\Sigma_{\mathcal{N}}$, $\mu(R)=n$,
then $((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in R_{\mathcal{M}[\mathcal{N}]}$ if
and only if $(a_{1},\ldots,a_{n})\in R_{\mathcal{M}}$;

4) if $R\in\Sigma_{\mathcal{N}}\setminus\Sigma_{\mathcal{M}}$, $\mu(R)=n$,
then $((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in R_{\mathcal{M}[\mathcal{N}]}$ if
and only if $a_{1}=\ldots=a_{n}$ and $(b_{1},\ldots,b_{n})\in
R_{\mathcal{N}}$;

5) if $R\in\Sigma_{\mathcal{M}}\cap\Sigma_{\mathcal{N}}$, $\mu(R)=n$, then
$((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in R_{\mathcal{M}[\mathcal{N}]}$ if and
only if $(a_{1},\ldots,a_{n})\in R_{\mathcal{M}}$, or $a_{1}=\ldots=a_{n}$ and
$(b_{1},\ldots,b_{n})\in R_{\mathcal{N}}$.

The theory $T={\rm Th}(\mathcal{M}[\mathcal{N}])$ is called the composition
$T_{1}[T_{2}]$ of the theories $T_{1}={\rm Th}(\mathcal{M})$ and $T_{2}={\rm
Th}(\mathcal{N})$.

By the definition, the composition $\mathcal{M}[\mathcal{N}]$ is obtained
replacing each element of $\mathcal{M}$ by a copy of $\mathcal{N}$.

Definition [11]. The composition $\mathcal{M}[\mathcal{N}]$ is called
$E$-definable if $\mathcal{M}[\mathcal{N}]$ has an $\emptyset$-definable
equivalence relation $E$ whose $E$-classes are universes of the copies of
$\mathcal{N}$ forming $\mathcal{M}[\mathcal{N}]$.

###### Remark 5.1

It is shown in [11] that $E$-definable compositions $\mathcal{M}[\mathcal{N}]$
uniquely define theories ${\rm Th}(\mathcal{M}[\mathcal{N}])$ by theories
${\rm Th}(\mathcal{M})$ and ${\rm Th}(\mathcal{N})$ and types of elements in
copies of $\mathcal{N}$ are defined by types in these copies and types for
connections between these copies.

###### Proposition 5.2

For $E$-definable compositions $\mathcal{M}[\mathcal{N}]$ the automorphism
group ${\rm Aut}(\mathcal{M}[\mathcal{N}])$ is isomorphic to the wreath
product of ${\rm Aut}(\mathcal{M})$ and ${\rm Aut}(\mathcal{N})$:

${\rm Aut}(\mathcal{M}[\mathcal{N}])\simeq{\rm Aut}(\mathcal{M})\wr{\rm
Aut}(\mathcal{N}).$

Proof. Since all copies of $\mathcal{N}$ are isomorphic in
$\mathcal{M}[\mathcal{N}]$ and form definable $E$-classes each automorphism
$f\in{\rm Aut}(\mathcal{M}[\mathcal{N}])$ is defined both by the action on the
set of $E$-classes, which corresponds to an automorphism $g\in{\rm
Aut}(\mathcal{M})$, and by the the actions on the $E$-classes, which
corresponds to an automorphism $h$ for copies of $\mathcal{N}$. Therefore $f$
is situated in the one-to-one correspondence with the pair $(g,h)$ producing a
correspondent element of ${\rm Aut}(\mathcal{M})\wr{\rm Aut}(\mathcal{N})$.
$\Box$

In view of Remark 5.1 and Proposition 5.2 we have the following:

###### Theorem 5.3

For any $E$-definable composition $\mathcal{M}[\mathcal{N}]$ the following
conditions hold:

${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}[\mathcal{N}])={\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}),$

if $\mathcal{N}$ is semantically rigid, and

${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=|M|\cdot{\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{N}),$

if $\mathcal{N}$ is not semantically rigid. In particular, ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M}[\mathcal{N}])$ is
finite iff ${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{M})$
and $\mathcal{N}$ are finite, if $\mathcal{N}$ is semantically rigid, and
${\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N})$ and
$\mathcal{M}$ are finite, if $\mathcal{N}$ is not semantically rigid.

Proof. If $\mathcal{N}$ is semantically rigid then it suffices to find
possibilities for automorphisms of $\mathcal{M}$ since in such a case the
semantical rigidity of an inessential expansion of $\mathcal{M}$ implies the
semantical rigidity of correspondent inessential expansion of
$\mathcal{M}[\mathcal{N}]$. Thus, here ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M}[\mathcal{N}])={\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{M})$. If $\mathcal{N}$ is not semantically rigid then
copies of $\mathcal{N}$ in $\mathcal{M}[\mathcal{N}]$ are automorphically
independent, i.e., fixing automorphisms for $\mathcal{M}[\mathcal{N}]$ one
have to fix all automorphisms for these copies. Since the smallest set fixing
automorphisms for $\mathcal{N}$ contains ${\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{N})$, we have at least and minimally at most
$|M|\cdot{\rm deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm rig}(\mathcal{N})$
elements to fix automorphisms for $\mathcal{M}[\mathcal{N}]$ implying ${\rm
deg}^{\exists\mbox{\rm-}{\rm sem}}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=|M|\cdot{\rm deg}^{\exists\mbox{\rm-}{\rm
sem}}_{\rm rig}(\mathcal{N})$. $\Box$

###### Theorem 5.4

For any $E$-definable composition $\mathcal{M}[\mathcal{N}]$ the following
conditions hold:

${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}[\mathcal{N}])={\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}),$

if $N={\rm dcl}(\emptyset)$, and

${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=|M|\cdot{\rm deg}^{\exists\mbox{\rm-}{\rm
synt}}_{\rm rig}(\mathcal{N}),$

if $N\neq{\rm dcl}(\emptyset)$. In particular, ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M}[\mathcal{N}])$ is
finite iff ${\rm deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{M})$
and $\mathcal{N}$ are finite, for $N={\rm dcl}(\emptyset)$, and ${\rm
deg}^{\exists\mbox{\rm-}{\rm synt}}_{\rm rig}(\mathcal{N})$ and $\mathcal{M}$
are finite, for $N\neq{\rm dcl}(\emptyset)$.

Proof repeats the proof of Theorem 5.3 replacing automorphism groups by
definable closures. $\Box$

Proposition 2.1, (1), (2) and Theorems 5.3, 5.4 immediately imply:

###### Corollary 5.5

For any $E$-definable composition $\mathcal{M}[\mathcal{N}]$ and $s\in\\{{\rm
sem},{\rm synt}\\}$ the following conditions are equivalent:

$(1)$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])=0$;

$(2)$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})=0$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$.

###### Theorem 5.6

For any $s\in\\{{\rm sem},{\rm synt}\\}$ and $E$-definable composition
$\mathcal{M}[\mathcal{N}]$ with

${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])>0$

the following conditions are equivalent:

$(1)$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])$ is
finite;

$(2)$ one of the following conditions hold:

i) $\mathcal{M}$ and $\mathcal{N}$ are finite, i.e. $\mathcal{M}[\mathcal{N}]$
is finite;

ii) $\mathcal{M}$ is infinite with ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})=1$ and ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})=0$;

iii) $\mathcal{M}$ is infinite and $\mathcal{N}$ is finite with ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})\in\omega\setminus\\{0,1\\}$
and ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$;

iv) $\mathcal{M}$ is a singleton and $\mathcal{N}$ is infinite with ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})\in\omega\setminus\\{0\\}$.

Here there are the following possibilities:

a) ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])=({\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})-1)\cdot|N|+1$, if the case
i) or iii) is satisfied with ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})=0$;

b) ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=(|M|-1)\cdot|N|+{\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N}),$ if the case i) is
satisfied with ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})>0$;

c) ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])=1,$ if
the case ii) is satisfied;

d) ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])={\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N}),$ if the case iv) is
satisfied.

Proof. At first we notice that ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})>0$ or ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})>0$ in view of Corollary 5.5.

Now by the definition $\mathcal{M}[\mathcal{N}]$ is finite iff $\mathcal{M}$
and $\mathcal{N}$ are finite. In such a case we have the following
possibilities:

$\bullet$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=({\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})-1)\cdot|N|+1$, if ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})=0$, since the rigidity of $\mathcal{M}[\mathcal{N}]$ can be
achieved here taking all elements in ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})-1$ copies of $\mathcal{N}$ with one additional element
witnessing the degree ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})$
defining rigidly all $E$-classes for copies of $\mathcal{N}$ which are rigid
by ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$; it corresponds
the case i) with a);

$\bullet$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}[\mathcal{N}])=(|M|-1)\cdot|N|+{\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N}),$ if ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})>0$, since the rigidity of
$\mathcal{M}[\mathcal{N}]$ can be achieved here taking all elements in
$(|M|-1)$ copies of $\mathcal{N}$ with ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})$ additional elements in the last copy of $\mathcal{N}$; it
corresponds the case i) with b).

$(1)\Rightarrow(2)$. Let ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}[\mathcal{N}])>0$ is finite. We can assume that $\mathcal{M}$
is infinite or $\mathcal{N}$ is infinite. We have the following possibilities:

$\bullet$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})=1$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$, that is any element of
$\mathcal{M}[\mathcal{N}]$ rigidly defines its $E$-class and all $E$-classes,
too, by ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})=1$, such that
all copies of $\mathcal{N}$ in these $E$-classes are rigid by ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$; it corresponds the case
ii) with c);

$\bullet$ ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M})\in\omega\setminus\\{0,1\\}$ and ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})=0$; here we require that
$\mathcal{N}$ is finite, since otherwise we can take arbitrary many elements
in some $E$-classes which do not imply the rigidity in view of ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})\geq 2$; here we have the
case iii) with a).

$\bullet$ $\mathcal{M}$ is a singleton and $\mathcal{N}$ is infinite with
${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})\in\omega\setminus\\{0\\}$, here ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M})=0$,
$\mathcal{M}[\mathcal{N}]\simeq\mathcal{N}$ and therefore ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])={\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{N})$.

If $\mathcal{N}$ is infinite with ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{N})\in\omega\setminus\\{0\\}$ and $|\mathcal{M}|\geq 2$ then we
can not obtain the rigidity for all $E$-classes taking arbitrary many elements
in some $E$-classes that contradicts the condition ${\rm
deg}^{\forall\mbox{\rm-}s}_{\rm rig}(\mathcal{M}[\mathcal{N}])\in\omega$.

$(2)\Rightarrow(1)$. Since each finite structure has finite degrees of
rigidity it suffices to show that ${\rm deg}^{\forall\mbox{\rm-}s}_{\rm
rig}(\mathcal{M}[\mathcal{N}])$ is finite if $\mathcal{M}$ is infinite or
$\mathcal{N}$ is infinite with the conditions ii), iii), iv). We observe that
ii) implies c), iii) implies a), and iv) implies d) confirming a finite value
of that degree. $\Box$

##  6 Conclusion

We studied possibilities for the degrees and indexes of rigidity, both for
semantical and syntactical cases. Links of these characteristics and their
possible values are described. We studied these values and dynamics for
structures in some languages, for some natural operations including disjoint
unions and compositions of structures. A series of examples illustrates
possibilities of these characteristics. It would be interesting to continue
this research describing possible values of degrees and indexes for natural
classes of structures and their theories.

## References

  * [1] Sudoplatov S.V. Algebraic closures and their variations. arXiv:2307.12536 [math.LO], 2023. — 16 p.
  * [2] Shelah S. Classification theory and the number of non-isomorphic models. Amsterdam : North-Holland, 1990. — 705 p.
  * [3] Hodges W. Model theory. Cambridge : Cambridge University Press, 1993\. — 772 p.
  * [4] Pillay A. Geometric Stability Theory. Oxford : Clarendon Press, 1996\. — 361 p.
  * [5] Marker D. Model Theory: An Introduction. New York : Springer-Verlag, 2002. — Graduate texts in Mathematics. — Vol. 217. — 342 p.
  * [6] Tent K., Ziegler M. A Course in Model Theory. Cambridge, Cambridge University Press, 2012. — 248 p.
  * [7] Ershov Yu.L., Palyutin E.A. Mathematical logic. — Moscow : FIZMATLIT, 2011. — 356 p. [in Russian]
  * [8] Sudoplatov S.V. Group Polygonometries. Novosibirsk, NSTU, 2013.
  * [9] Sudoplatov S.V. Models of cubic theories, Bulletin of the Section of Logic, 43:1–2 (2014), 19–34.
  * [10] Woodrow R. E. Theories with a finite number of countable models and a small language. Ph. D. Thesis. — Simon Fraser University, 1976. — 99 p.
  * [11] Emelyanov D.Yu., Kulpeshov B.Sh., Sudoplatov S.V. Algebras of binary formulas for compositions of theories, Algebra and Logic, 59:4 (2020), 295–312.
  * [12] Sudoplatov S.V. Formulas and Properties, Their Links and Characteristics, Mathematics. 2021, Vol. 9, Issue 12. 1391. 16 pp.

Sergey V. Sudoplatov

Sobolev Institute of Mathematics,

Novosibirsk State Technical University,

Novosibirsk, Russia

E-mail<EMAIL_ADDRESS>


# Robust Guidance for Unsupervised Data Selection:
Capturing Perplexing Named Entities
for Domain-Specific Machine Translation

###### Abstract

Employing extensive datasets enables the training of multilingual machine
translation models; however, these models often fail to accurately translate
sentences within specialized domains. Although obtaining and translating
domain-specific data incurs high costs, it is inevitable for high-quality
translations. Hence, finding the most ’effective’ data with an unsupervised
setting becomes a practical strategy for reducing labeling costs. Recent
research indicates that this effective data could be found by selecting
’properly difficult data’ based on its volume. This means the data should not
be excessively challenging or overly simplistic, especially if the amount of
data is limited. However, we found that establishing a criterion for
unsupervised data selection remains challenging, as the ’proper difficulty’
might vary based on the data domain being trained on. We introduce a novel
unsupervised data selection method, ’Capturing Perplexing Named Entities’,
which adopts the maximum inference entropy in translated named entities as a
selection measure. The motivation was that named entities in domain-specific
data are considered the most complex portion of the data and should be
predicted with high confidence. When verified with the ’Korean-English
Parallel Corpus of Specialized Domains,’ our method served as a robust
guidance for unsupervised data selection, in contrast to existing methods.

Keywords: Machine Translation, Data Pruning, Unsupervised Method

Robust Guidance for Unsupervised Data Selection:
Capturing Perplexing Named Entities
for Domain-Specific Machine Translation

Seunghyun Ji12, Hagai Raja Sinulingga2, Darongsae Kwon2
---
1A-ha, 2TelePIX
<EMAIL_ADDRESS>{hagairaja<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

††footnotetext: This work was done in TelePIX, the previous affiliation of the
first author.††footnotetext: The code is available in the following hyperlink
: https://github.com/comchobo/Capturing-Perplexing-Named-Entities

With the advent of large-scale models capable of translating numerous
languages in various directions(Aharoni et al., 2019), the field of machine
translation is entering a new era. For instance, ’No Language Left Behind(NLLB
Team et al., 2022)’, which demonstrated outstanding performance across a range
of languages, was trained on over 40,000 combinations of 200 languages. These
models can be regarded as pre-trained or foundational, as they have acquired
general knowledge for translation. Nevertheless, they might sometimes face
challenges when translating domain-specific data, despite their extensive
training on diverse datasets. To address this, fine-tuning the pre-trained
models with target domain data can enhance their specializationFadaee and Monz
(2018); Zan et al. (2022).

Figure 1: A diagram illustrates our method, which utilizes a pre-trained
multilingual model for machine translation and a named entity recognition
model that has been fine-tuned on the target language. Our method comprises
three steps: 1) capturing named entity tokens in the machine-translated
sentences, 2) calculating the inference entropy of those tokens, and 3) using
the maximum entropy value as a measure for selection.

However, when addressing narrow or specialized domains, the model must
recognize words that relatively rare in general corpora. This presents a
challenge, as rare words often consist of sparse tokens, such as being
composed of single character tokens, making them harder to train. Furthermore,
named entities frequently lack synonyms, complicating to build contextualized
representations. Consequently, acquiring translation data can become costly,
necessitating translators who possess not only domain expertise but also
familiarity with domain-specific terminology.

To reduce costs, one might consider strategically identifying data for
labeling rather than making random selections. Several researchers(Paul et
al., 2021; Feldman and Zhang, 2020; Sorscher et al., 2022) have suggested
various measurement methods aimed at selecting ’effective’ data for training.
Some of those focus on ’Data difficulty,’(Paul et al., 2021; Meding et al.,
2022) identifying data that poses a challenge to a given model. ’Data
forgettability(Toneva et al., 2019)’ or ’Memorization(Feldman and Zhang,
2020)’ could serve as alternative criterion. However, these methods require a
supervised setting for selection, which may be inefficient for machine
translation. For instance, pruning a dataset is unlikely to yield a better
model if the dataset was curated by domain experts (Maillard et al., 2023).

In an unsupervised setting, Sorscher et al. (2022) demonstrated that the
Euclidean distance between a data point’s representation and its cluster
centroid can serve as an effective measure for data selection. This approach
is supported by several concrete theoretical analyses and provides
straightforward guidance for selection. However, it remains uncertain whether
this criterion can be universally applied to parameter-efficient fine-tuning
methods(Houlsby et al., 2019; Hu et al., 2022; Liu et al., 2022), which are
commonly used. We observed that this measurement method might not always align
with training-efficiency, indicating that it may not consistently correlate
with performance improvement, despite using the same pre-trained weights and
dataset size. These findings are detailed in Section 5.2.

We propose a novel method for unsupervised data selection, which we refer to
as ’Capturing Perplexing Named Entities’. Our method identifies data that
should be selected, by assessing the perplexity of named entity tokens
translated by a given pre-trained model, as described in Figure 1. The
motivations behind this approach are as follow:

  * •

Since named entities in domain-specific data are challenging to translate
without recognizing the complex patterns within the domain, they represent one
of the most difficult portions to translate. Therefore, these entities should
be given priority for efficient domain adaptation.

  * •

The entropy score of a vocabulary distribution can indicate the model’s level
of perplexity. Given that synonyms for named entities are unlikely to exist,
the model should not exhibit a high entropy score for named entities.

In several experiments targeting domain-specific ’Korean to English’
translation, our method consistently identified the most training-efficient
data. This indicates that our measurement method has a stronger correlation
with performance improvement compared to existing methods, which can vary
significantly across different data domains. For clarity in our discussion,
’MDS’ will serve as the abbreviation for Measurement method for Data
Selection, and ’Value by MDS’ will denote the specific value it calculates.

## 2\. Related Works

Languages |  Data Examples | Scores
---|---|---
Korean |  메이저리그 자유계약선수(FA) 최대어 투수 중 한 명인 스티븐 스트라스버그가 원 소속팀 워싱턴과 7년 2억4,500만달러에 도장을 찍었다. | COMET
90.92
English |  Steven Strasburg, one of the biggest free agent (FA) pitchers in Major League Baseball, has signed a 7-year, $ 245 million contracts with his original team Washington. | ChrF++
67.94
Translated |  Steven Strasberg, one of the biggest pitchers in the Major League Free Agent (FA) league, signed a seven-year, $ 245 million contract with former team Washington. | BLEU
27.38
Korean |  고메스 부상 이후 에버턴 지휘봉을 잡게된 카를로 안첼로티 감독은 지난주 ”고메스의 회복이 순조롭게 이뤄지고 있다”고 밝혔다. | COMET
90.99
English |  Manager Carlo Ancelotti, who took the helm of Everton after Gomez’s injury, revealed last week that ”Gomez’s recovery is going smoothly.” | ChrF++
64.47
Translated |  Coach Carlo Ancelotti, who took over Everton after Gomes’ injury, said last week, ”Gomes’ recovery is progressing smoothly.” | BLEU
24.86
Table 1: Example pairs with high COMET and ChrF++ scores but low BLEU scores
were selected from sports domain data. The first column represents the source
(Korean), the target (English), and the machine-translated (Korean to English)
result. Words that may cause critical semantic distortions are highlighted in
red. The last column lists the evaluation scores of the machine-translated
sentences, calculated using three different metrics.

### 2.1. Data Selection for Training

Throughout several training cycles, metrics such as forgetting scores(Toneva
et al., 2019), memorization(Feldman and Zhang, 2020), diverse ensembles(Meding
et al., 2022), and normed gradients(Paul et al., 2021) could be used as one of
the measurement methods for data selection (MDS). EL2N, which quantifies the
error magnitude, acts as a training-free MDS. However, these methods require
annotations, limiting their application to supervised settings only. As high-
quality data has been shown to significantly outperform large volumes of low-
quality or synthetic data(Maillard et al., 2023), it is generally recommended
that the data with elaborate annotations should not be pruned.

In an unsupervised setting, one might explore data uniqueness—for example, by
measuring the Euclidean distance between a data representation and its
centroid(Sorscher et al., 2022) (referred to as Selfsup)—as a form of
unsupervised MDS. Measuring uncertainty, which could be estimated by the
entropy of the probability distribution, also might be one of MDS(Brown et
al., 1990; Wu et al., 2021). However, empirical evidence suggests that when
training with small datasets, excessively unique data (indicated by high
values in MDS Selfsup) may impede training(Sorscher et al., 2022). Therefore,
selecting data using the appropriate type of MDS and determining the optimal
value for MDS are crucial. Nonetheless, establishing a standard for this is
challenging, to the best of our knowledge.

In machine translation, reference-free Quality Estimation (QE) methods, which
operate as an unsupervised MDS, are gaining focus. One strategy involves the
intuition of ’seeking perplexing data’ by identifying attention distractions
or uncertainties(Peris and Casacuberta, 2018). More sophisticated reference-
free QE algorithms, which can be implemented using deep models(Rei et al.,
2021), have demonstrated competitive results when compared to their reference-
requiring counterparts(Rei et al., 2020). However, these methods, relying on
sentence embedding models, are often confounded by even slight literal
differences. We have observed and discussed this phenomenon in Section 2.2.

### 2.2. Named entities in Machine Translation

Translating named entities presents a significant challenge in machine
translation(Ugawa et al., 2018), although it is crucial for delivering
accurate information. Incorrect translations of named entities, even with few
errors, can lead to information distortion. For instance, in Table 1, the
human-translated and machine-translated Korean to English-sentences may seem
similar. However, a closer examination reveals differences in the individual’s
name (Steven Strasburg), the league (Major League Baseball), and an adjective
(original). Despite these mistakes causing critical distortions, recent
metrics such as COMET(Rei et al., 2020)111We used
https://huggingface.co/Unbabel/wmt22-comet-da to evaluate using COMET score.
and ChrF++(Popović, 2015) show scores high enough to be interpreted as
satisfactory results. Given that some rare named entities are more common in
domain-specific data, accurately recognizing named entities constitutes a
significant challenge, one that recent metrics fail to adequately capture.

One current approach to translate named entities precisely, integrates a
knowledge base(Zhao et al., 2020) or employs a transliteration model once
tokens are identified as named entities(Sharma et al., 2023). However, these
strategies often rely on specialized algorithms that act as a workaround,
rather than directly boosting the translation model’s performance or
robustness. Multi-task learning has demonstrated improvements in translation
performance when additional annotations for named entities are provided(Xie et
al., 2022). However, this method may incur significantly higher labeling
costs.

## 3\. Existing Methods

We consider the multilingual translation model as a ’pre-trained model’, with
subsequent training on specific data referred to as ’fine-tuning’.

### 3.1. EL2N

Paul et al. (2021) previously used the average error from several minimally
trained models to identify data that could not be easily trained in a few
epochs. This method requires paired data for its computations, hence
categorized as a supervised approach. Intuitively, the EL2N value from a pre-
trained model signifies an average error or incorrect confidence, enabling the
identification of the most problematic data for a given model. If $\bm{Y}$ and
$\bm{\hat{Y}}$ represent the original and translated sentences in the target
language, respectively, EL2N can be described as follows:

EL2N$(\bm{Y},\bm{\hat{Y}})=\frac{1}{L}\sum_{l=1}^{L}\|\bm{y}_{l}-\hat{\bm{y}_{l}}\|$
$L=min(|\bm{Y}|,|\bm{\hat{Y}}|)$

where $\bm{\hat{y}}$ represents the predicted token distribution, and $\bm{y}$
is the actual label. Given that the translated sentence may contain a
different number of tokens from original sentence, we chose the shorter token
length, represented by the cardinality of $\bm{Y}$ and $\bm{\hat{Y}}$.

### 3.2. Entropy

Brown et al. (1990) demonstrated that uncertainty in prediction is
quantifiable by entropy. Various studies have reported performance
improvements by employing entropy to select data for training(Jiao et al.,
2021; Wu et al., 2021). Building on this concept, we considered entropy as an
indicator of the pre-trained model’s perplexity regarding specific sentences,
selecting them as candidates for fine-tuning. The entropy of the vocabulary
distribution is defined as:

$H(\bm{\hat{y}})=\frac{1}{V}\sum_{i\in{}V}-P(\hat{y_{i}})logP(\hat{y_{i}})$

where $V$ is a vocabulary. We adopted averaged entropy as MDS which is as
follows:

$AvgEntropy(\bm{\hat{Y}})=\frac{1}{L}\sum_{l=1}^{L}H(\bm{\hat{y}}_{l})$

where $L$ is a length of the sentence $\bm{\hat{Y}}$.

However, given that the optimal entropy level may differ by token types, such
as adjectives or synonyms, we hypothesized that employing $AvgEntropy$ as an
MDS might lead the model to become either overconfident or overly cautious.

### 3.3. Selfsup

Sorscher et al. (2022) observed that within clustered image representations,
data points distant from their centroids often exhibit unique patterns, which
have high Euclidean distance to the centroid. However, its effectiveness as an
MDS for fine-tuning translation models remains unverified. To adapt this
approach to the language domain, we utilized sentence embeddings for the
source data and applied k-means clustering. If $x_{A}$ represents a sentence
embedding of source language data $x$, clustered around centroid $A$, then the
MDS Selfsup can be described as:

$Selfsup(x_{A})=||x_{A}-A||$

If the sentence embeddings are well-aligned, MDS Selfsup is expected to
capture training-efficient data for fine-tuning. Although recent sentence
embedding models demonstrate decent performance, their accuracy in domain-
specific data remains questionable. Our findings provide support for this
doubt, as illustrated in Table 1, where the COMET score failed to detect
semantic distortion.

### 3.4. Reference-free COMET

Rei et al. (2021) proposed a Reference-free COMET, which was trained to
estimate quality without reference, only with source and translated sentences.
Reference-free COMET was designed to predict quality annotations using a
sentence embedding model. Its output range is 0 to 1, where 1 denotes the best
quality. We expected that Reference-free COMET as an MDS would be inversely
proportional to the training-efficiency since it would detect examples that
the model could not translate well.

## 4\. Proposed Method

Our hypothesis posits that complex patterns possessed by named entities are
essential for fine-tuning. This is particularly true in domain-specific
machine translation, where rare words and expressions occur frequently but are
not present in the general domain. By incorporating these characteristics into
data selection, we measured the maximum entropy while translating named
entities, which are unlikely to have alternative answers. In summary, our
method specifically targets perplexing named entities.

$PerEnts(\bm{\hat{Y}})=max(\\{H(\bm{\hat{y}}_{x})|x\in NE(\bm{\hat{y}})\\})$

where $NE(\bm{\hat{y}})$ represents a set of named entity token indices in the
machine-translated sentence $\bm{\hat{y}}$, predicted by a named entity
recognition model. We will use the abbreviation ’PerEnts,’ to refer to our
method.

## 5\. Experiments

### 5.1. Settings for experiments

Figure 2: Pseudo code for the experiment data preparation. We sorted and split
the data into 4 segments based on each value by MDS. Then, we sampled 2,000
sentences from each segment for fine-tuning.

We attempted to evaluate our method, which is one of the unsupervised MDSs,
with various datasets. We sorted the data based on the values of each MDS and
divided it into four segments to verify that each MDS is proportional to
training-efficiency. If it is proportional and invariant across data domains,
it can be regarded as ’robust guidance’ for unsupervised data selection. We
also conducted multiple data samplings for fine-tuning to precisely assess the
capabilities of MDSs. This process follows the same cycle as described in the
pseudo-code, shown in Figure 2. Note that the highest segment index (3 in our
case) represents data subsets with the highest values according to each MDS.

Data Domain | Train / Test
---|---
Medical | 200k / 25k
Travel | 160k / 20k
Law | 120k / 15k
Sports | 160k / 20k
Table 2: The number of sentences of ’Korean-English Parallel Corpus of
Specialized Domains’ dataset, released with train/test splits.

Models and Datasets As a pre-trained translation model, we used
’NLLB-1.3B(NLLB Team et al.,
2022)222https://huggingface.co/facebook/nllb-200-distilled-1.3B’ multilingual
model. We then employed the ’Korean-English Parallel Corpus of Specialized
Domains(Flitto, 2021) 333This research (paper) used datasets from ’The Open AI
Dataset Project (AI-Hub, S. Korea)’. All data information can be accessed
through ’AI-Hub (www.aihub.or.kr)’.’, published by the National Information
Society Agency of South Korea, as the domain-specific dataset. Given the
scarcity of open datasets in the Korean language available for public
download, we adopted this approach despite its limited access being restricted
to nationals. There are ’Law, Medical, Travel, Sports’ domains, showing each
distribution in Table 2.

Training and Hyperparameters Given the potential variability in domain-
specific translation, such as extremely unique domains or low-resource
environments, we randomly sampled 2,000 sentences from each segment, regarding
the pre-defined seeds. We employed IA3 training(Liu et al., 2022) to simulate
practical fine-tuning environments. For hyperparameters, we set the epoch to
10, and the batch size to 32, and searched for the best learning rate from
three options [1e-2, 2e-2, 3e-2] during each fine-tuning trial. Given that
fine-tuning with a low-resource dataset might result in high variance between
models, we took the average scores of three fine-tuned models, using sampled
data with 3 different seeds.

MDSs | Average Performance
---|---
| BLEU | ChrF++ | COMET
Not fine-tuned | 21.42 | 45.57 | 76.39
Random | 33.71 | 56.90 | 80.71
Supervised method |  |  |
EL2N (Paul et al., 2021) | 34.01 | 57.25 | 80.84
Unsupervised methods |  |  |
Entropy (Jiao et al., 2021) | 33.64 | 57.05 | 80.86
Selfsup (Sorscher et al., 2022)* | 33.85 | 57.11 | 80.81
Reference-Free COMET (Rei et al., 2021)* | 33.88 | 57.22 | 80.92
PerEnts (ours) | 34.09 | 57.19 | 80.82
Table 3: Average test-set performance across 4 domains. We divided the dataset
for each domain into four segments after sorting by each MDS and sampled 2,000
sentences three times from each segment. Given our conjecture that invariance
across data domains is an important characteristic of an unsupervised MDS, we
reported scores fine-tuned with subsets from either the highest (3) or lowest
(0), denoted with an asterisk) segment. The highest scores among the
unsupervised MDSs are highlighted in bold. Figure 3: The scores for each
segment index across the four domains. The best BLEU scores among the segment
indices were marked with a black star. Experimental results demonstrated that
our method consistently identified the most training-efficient data by
selecting the highest segment (3), whereas other methods varied by data
domain.

Implementations of MDSs Since our method requires named entity recognition
model in the target language, which is English in our case, we employed the
’d4data/biomedical-ner-all444https://huggingface.co/d4data/biomedical-ner-all’
fine-tuned model to capture entities in the ’medical’ domain dataset, such as
names of medicines. For datasets in other domains, we used ’RashidNLP/NER-
Deberta555https://huggingface.co/RashidNLP/NER-Deberta’ model, trained with
Few-NERD dataset(Ding et al., 2021), which we conjectured far more
comprehensive than CoNLL-2003 dataset(Tjong Kim Sang and De Meulder, 2003). To
implement MDS Selfsup, we used the monolingual sentence embedding model
’BM-K/KoSimCSE-roberta-multitask666https://huggingface.co/BM-K/KoSimCSE-
roberta-multitask’, which is specialized for the Korean (source) language.
Lastly, ’Unbabel/wmt23-cometkiwi-da-xl’ was employed for Reference-Free
COMET(Rei et al., 2021)777https://huggingface.co/Unbabel/wmt23-cometkiwi-da-
xl.

### 5.2. Main Results

We employed BLEU(Post, 2018), ChrF++(Popović, 2015), and COMET scores(Rei et
al., 2020)888We used https://huggingface.co/Unbabel/wmt22-comet-da to evaluate
using COMET score. for evaluation, as presented in Table 3. The fine-tuned
models were evaluated using pre-split test sets. It is important to note that,
identifying the optimal value for each MDS requires access to every segment
index, necessitating a complete parallel corpus for comparison. To simulate a
practical strategy where access is limited, we reported averaged scores by
selecting either the highest (3) or lowest (0) segment index. For instance,
the domain-average score for EL2N was determined by selecting segment index 3,
while for MDS Selfsup, segment index 0 was chosen.

Our method, referred to by the abbreviation ’PerEnts,’ achieved the highest
BLEU score among the MDSs, even surpassing the supervised method (EL2N).
Although other existing methods outperformed ours for COMET and ChrF++ scores,
we propose that the BLEU score might be the most critical metric for domain-
specific translation due to its ability to capture semantic distortion, as
demonstrated in Table 1.

Additionally, to assess the robustness of the MDSs, we calculated the average
scores across four different domains, as presented in Figure 3. The best
performing segment index, selected by other MDSs, was neither 0 nor 3,
suggesting that these MDSs are sensitive to the data domain. We conjectured
that this observation could complement the assertion by Sorscher et al. (2022)
that ’The best selection strategy depends on the amount of initial data.’ Even
though the same pre-trained weights and the same volume of data were used for
each fine-tuning procedure, the data domain could play an important role as a
factor. Furthermore, our selection of a well-regarded monolingual sentence
embedding model999https://huggingface.co/BM-K/KoSimCSE-roberta-multitask for
implementing MDS Selfsup did not result in decent performance, supporting the
idea that the sentence embedding model could be confounded by slight literal
differences.

### 5.3. Additional Study

MDSs | Averaged Performance
---|---
| BLEU | ChrF++ | COMET
PerEnts | 34.09 | 57.16 | 80.82
*Mean | 33.94 | 57.19 | 80.82
Selfsup | 33.85 | 57.11 | 80.81
*Multilingual | 33.3 | 56.78 | 80.02
Table 4: The results of MDS variants. ’*Mean’ denotes that it averaged entropy
instead of choosing max in our method(PerEnts), and ’Multilingual’ adopted a
multilingual sentence embedding model for ’Selfsup’. Both variants used the
same segment index to achieve the highest average performance.

Since the intuition for each MDS could be implemented in various forms, we
implemented some MDS variants. e.g., adopting average entropy instead of max
for our method. We also employed multilingual sentence embedding model
’sentence-transformers/LaBSE(Feng et al.,
2022)101010https://huggingface.co/sentence-transformers/LaBSE’ for
implementing MDS Selfsup. The results are reported in Table 4. Although there
were less significant degradations, it can be argued that our method’s focus
on finding maximum entropy more effectively captures the ’unlearned parts.’
and it reveals a limitation in the representation ability of multilingual
sentence embedding models.

## 6\. Limitations

We attempted to verify our method under various situations and data domains.
However, it’s important to note that our experiments were conducted with a
single translation direction and a single data size (2k). We acknowledge that
testing on multiple translation directions and diverse amounts of datasets
could potentially provide a more comprehensive validation of MDSs, including
our method. Additionally, the impact of utilizing named entities may vary by
language, e.g., languages that use uppercase letters. Although we recognize
the importance of diverse environments and theoretical analysis, limited
experiments were done based on a strategic decision to verify generalizability
for practical usage. We believe that these limitations could be interesting
topics for future research, exploring which measurement method can generally
affect the performances of fine-tuned models.

## 7\. Conclusion

To identify the most training-efficient data for annotating in domain-specific
machine translation, we explored various measurement methods that could serve
as a benchmark for selection, collectively referred to as ’MDS.’ We recognized
named entities as ’complex patterns’ requiring highly confident prediction. As
a result, we introduced ’Capturing Perplexing Named Entity’ as one of the
MDSs. This approach has seen effective as a guidance for selecting training
data, even in unsupervised settings. Despite the common challenge of
identifying effective data for annotation in deep learning—a challenge that we
could not directly address in terms of the relationship between memorizable
patterns and generalizability due to a lack of theoretical analysis—we hope
our findings will pave the way for more in-depth research in the future.

## 8\. Bibliographical References

##

  * Agrawal et al. (2022) Sweta Agrawal, Chunting Zhou, Mike Lewis, Luke Zettlemoyer, and Marjan Ghazvininejad. 2022.  In-context examples selection for machine translation.
  * Aharoni et al. (2019) Roee Aharoni, Melvin Johnson, and Orhan Firat. 2019.  Massively multilingual neural machine translation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3874–3884, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Ahia et al. (2021) Orevaoghene Ahia, Julia Kreutzer, and Sara Hooker. 2021.  The low-resource double bind: An empirical study of pruning for low-resource machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 3316–3333, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Bansal et al. (2022) Yamini Bansal, Behrooz Ghorbani, Ankush Garg, Biao Zhang, Colin Cherry, Behnam Neyshabur, and Orhan Firat. 2022.  Data scaling laws in nmt: The effect of noise and architecture.  In _International Conference on Machine Learning_ , pages 1466–1482. PMLR.
  * Brown et al. (1990) Peter F Brown, John Cocke, Stephen A Della Pietra, Vincent J Della Pietra, Frederick Jelinek, John Lafferty, Robert L Mercer, and Paul S Roossin. 1990.  A statistical approach to machine translation.  _Computational linguistics_ , 16(2):79–85.
  * Ding et al. (2021) Ning Ding, Guangwei Xu, Yulin Chen, Xiaobin Wang, Xu Han, Pengjun Xie, Haitao Zheng, and Zhiyuan Liu. 2021.  Few-NERD: A few-shot named entity recognition dataset.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3198–3213, Online. Association for Computational Linguistics.
  * Fadaee and Monz (2018) Marzieh Fadaee and Christof Monz. 2018.  Back-translation sampling by targeting difficult words in neural machine translation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 436–446, Brussels, Belgium. Association for Computational Linguistics.
  * Feldman and Zhang (2020) Vitaly Feldman and Chiyuan Zhang. 2020.  What neural networks memorize and why: Discovering the long tail via influence estimation.  _Advances in Neural Information Processing Systems_ , 33:2881–2891.
  * Feng et al. (2022) Fangxiaoyu Feng, Yinfei Yang, Daniel Cer, Naveen Arivazhagan, and Wei Wang. 2022\.  Language-agnostic BERT sentence embedding.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 878–891, Dublin, Ireland. Association for Computational Linguistics.
  * Haviv et al. (2022) Adi Haviv, Ido Cohen, Jacob Gidron, Roei Schuster, Yoav Goldberg, and Mor Geva. 2022\.  Understanding transformer memorization recall through idioms.  _arXiv preprint arXiv:2210.03588_.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019.  Parameter-efficient transfer learning for nlp.  In _International Conference on Machine Learning_ , pages 2790–2799. PMLR.
  * Hu et al. (2022) Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022.  LoRA: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_.
  * Jiao et al. (2021) Wenxiang Jiao, Xing Wang, Zhaopeng Tu, Shuming Shi, Michael R Lyu, and Irwin King. 2021.  Self-training sampling with monolingual data uncertainty for neural machine translation.  _arXiv preprint arXiv:2106.00941_.
  * Joos (1936) Martin Joos. 1936.  _Language_ , 12(3):196–210.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium. Association for Computational Linguistics.
  * Liu et al. (2022) Haokun Liu, Derek Tam, Mohammed Muqeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. 2022.  Few-shot parameter-efficient fine-tuning is better and cheaper than in-context learning.  _Advances in Neural Information Processing Systems_ , 35:1950–1965.
  * Maillard et al. (2023) Jean Maillard, Cynthia Gao, Elahe Kalbassi, Kaushik Ram Sadagopan, Vedanuj Goswami, Philipp Koehn, Angela Fan, and Francisco Guzman. 2023.  Small data, big impact: Leveraging minimal data for effective machine translation.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2740–2756, Toronto, Canada. Association for Computational Linguistics.
  * Meding et al. (2022) Kristof Meding, Luca M. Schulze Buschoff, Robert Geirhos, and Felix A. Wichmann. 2022.  Trivial or impossible — dichotomous data difficulty masks model differences (on imagenet and beyond).  In _International Conference on Learning Representations_.
  * Mota et al. (2022) Pedro Mota, Vera Cabarrao, and Eduardo Farah. 2022.  Fast-paced improvements to named entity handling for neural machine translation.  In _Proceedings of the 23rd Annual Conference of the European Association for Machine Translation_ , pages 141–149, Ghent, Belgium. European Association for Machine Translation.
  * Nguyen et al. (2020) Xuan-Phi Nguyen, Shafiq Joty, Kui Wu, and Ai Ti Aw. 2020.  Data diversification: A simple strategy for neural machine translation.  _Advances in Neural Information Processing Systems_ , 33:10018–10029.
  * NLLB Team et al. (2022) NLLB Team, Marta R. Costa-jussà, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, Anna Sun, Skyler Wang, Guillaume Wenzek, Al Youngblood, Bapi Akula, Loic Barrault, Gabriel Mejia-Gonzalez, Prangthip Hansanti, John Hoffman, Semarley Jarrett, Kaushik Ram Sadagopan, Dirk Rowe, Shannon Spruit, Chau Tran, Pierre Andrews, Necip Fazil Ayan, Shruti Bhosale, Sergey Edunov, Angela Fan, Cynthia Gao, Vedanuj Goswami, Francisco Guzmán, Philipp Koehn, Alexandre Mourachko, Christophe Ropers, Safiyyah Saleem, Holger Schwenk, and Jeff Wang. 2022.  No language left behind: Scaling human-centered machine translation.
  * Paul et al. (2021) Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. 2021.  Deep learning on a data diet: Finding important examples early in training.  In _Advances in Neural Information Processing Systems_.
  * Peris and Casacuberta (2018) Álvaro Peris and Francisco Casacuberta. 2018.  Active learning for interactive neural machine translation of data streams.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning_ , pages 151–160, Brussels, Belgium. Association for Computational Linguistics.
  * Popović (2015) Maja Popović. 2015.  chrF: character n-gram F-score for automatic MT evaluation.  In _Proceedings of the Tenth Workshop on Statistical Machine Translation_ , pages 392–395, Lisbon, Portugal. Association for Computational Linguistics.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting bleu scores.  _WMT 2018_ , page 186.
  * Rahaman et al. (2019) Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. 2019.  On the spectral bias of neural networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5301–5310. PMLR.
  * Raunak et al. (2021) Vikas Raunak, Arul Menezes, and Marcin Junczys-Dowmunt. 2021.  The curious case of hallucinations in neural machine translation.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1172–1183, Online. Association for Computational Linguistics.
  * Rei et al. (2021) Ricardo Rei, Ana C Farinha, Chrysoula Zerva, Daan van Stigt, Craig Stewart, Pedro Ramos, Taisiya Glushkova, André F. T. Martins, and Alon Lavie. 2021\.  Are references really needed? unbabel-IST 2021 submission for the metrics shared task.  In _Proceedings of the Sixth Conference on Machine Translation_ , pages 1030–1040, Online. Association for Computational Linguistics.
  * Rei et al. (2020) Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020.  COMET: A neural framework for MT evaluation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2685–2702, Online. Association for Computational Linguistics.
  * Sharma et al. (2023) Radhika Sharma, Pragya Katyayan, and Nisheeth Joshi. 2023.  Improving the quality of neural machine translation through proper translation of name entities.  In _2023 6th International Conference on Information Systems and Computer Networks (ISCON)_ , pages 1–4.
  * Sorscher et al. (2022) Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S. Morcos. 2022.  Beyond neural scaling laws: beating power law scaling via data pruning.  In _Advances in Neural Information Processing Systems_.
  * Soto et al. (2020) Xabier Soto, Dimitar Shterionov, Alberto Poncelas, and Andy Way. 2020.  Selecting backtranslated data from multiple sources for improved neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3898–3908, Online. Association for Computational Linguistics.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Toneva et al. (2019) Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. 2019.  An empirical study of example forgetting during deep neural network learning.  In _International Conference on Learning Representations_.
  * Ugawa et al. (2018) Arata Ugawa, Akihiro Tamura, Takashi Ninomiya, Hiroya Takamura, and Manabu Okumura. 2018.  Neural machine translation incorporating named entity.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3240–3250, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Wu et al. (2021) Minghao Wu, Yitong Li, Meng Zhang, Liangyou Li, Gholamreza Haffari, and Qun Liu. 2021.  Uncertainty-aware balancing for multilingual and multi-domain neural machine translation training.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7291–7305.
  * Xie et al. (2022) Shufang Xie, Yingce Xia, Lijun Wu, Yiqing Huang, Yang Fan, and Tao Qin. 2022.  End-to-end entity-aware neural machine translation.  _Machine Learning_ , pages 1–23.
  * Zan et al. (2022) Changtong Zan, Keqin Peng, Liang Ding, Baopu Qiu, Boan Liu, Shwai He, Qingyu Lu, Zheng Zhang, Chuang Liu, Weifeng Liu, et al. 2022.  Vega-mt: The jd explore academy translation system for wmt22.
  * Zhang et al. (2017) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. 2017\.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_.
  * Zhao et al. (2020) Yang Zhao, Lu Xiang, Junnan Zhu, Jiajun Zhang, Yu Zhou, and Chengqing Zong. 2020\.  Knowledge graph enhanced neural machine translation via multi-task learning on sub-entity granularity.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 4495–4505.
  * Zhou et al. (2020) Yikai Zhou, Baosong Yang, Derek F. Wong, Yu Wan, and Lidia S. Chao. 2020.  Uncertainty-aware curriculum learning for neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6934–6944, Online. Association for Computational Linguistics.

## 9\. Language Resource References

##

  * Flitto (2021) Flitto. 2021.  _Korean-English Parallel Corpus of Specialized Domains_.  AI Hub.