# Quantifier-free descriptions
for quantifier solutions
to interval linear systems of relations111The work is a revised and extended
English translation of the original Russian work Sharaya, I.A. Quantifier-free
descriptions of interval-quantifier linear systems // Trudy Instituta
Matematiki i Mekhaniki UrO RAN (Proceedings of the Institute of Mathematics
and Mechanics, Ural Branch of the Russian Academy of Sciences). – 2014. – Vol.
20, No. 2. – P. 311–323.

Irene A. Sharaya

(Institute of Computational Technologies SB RAS
and Novosibirsk State University,
Novosibirsk, Russia)

###### Abstract

We study systems of relations of the form $Ax\,\sigma\,b$, where $\sigma$ is a
vector of binary relations with the components “$=$”, “$\geq$” and “$\leq$”,
and the parameters (elements of the matrix $A$ and right-hand side vector $b$)
can take values from prescribed intervals. What is considered to be the set of
its solutions depends on which logical quantifier is associated with each
interval-valued parameter and what is the order of the quantifier prefixes for
certain parameters. For solution sets that correspond to the quantifier prefix
of a general form, we present equivalent quantifier-free descriptions in the
classical interval arithmetic, in Kaucher complete interval arithmetic and in
the usual real arithmetic.
Keywords: interval linear systems of equations and inequalities, quantifier
elimination, Kaucher interval arithmetic.
Mathematics Subject Classification 2010: 65G40, 03B10, 91A99

##  1 Introduction

###  1.1 Quantifier solutions to interval linear systems

In the classical interval arithmetic $\mathbb{IR}$, an interval is a non-empty
bounded connected closed subset of the real line $\mathbb{R}$. According to
the notation standard [9], we will denote interval objects in bold type ($A$,
$B$, …, $y$, $z$), in contrast to usual point (non-interval) quantities that
are not specifically distinguished.

We consider a system of linear equations and inequalities of the form

$Ax\,\sigma\,b,\qquad A\in\mathbb{R}^{m\times n},\ x\in\mathbb{R}^{n},\
b\in\mathbb{R}^{m},\ \sigma\in\\{=,\geq,\leq\\}^{m},\ \ m,n\in\mathbb{N},$

where $x$ is a vector of unknowns, $\sigma$ is a vector of binary relations,
with the components “$=$”, “$\geq$” and “$\leq$”, and every parameter
$u\in\mathbb{R}$ (which may be an element of the matrix $A$ or of the right-
hand side $b$) can take values within the prescribed eponymous interval $u$
from $\mathbb{IR}$.

As an example of such “mixed” systems, we can consider a $3\times 2$-system

$\left\\{\begin{array}[]{rcl}2x_{1}-3x_{2}&\leq&4,\\\\[2.0pt]
5x_{1}+6x_{2}&=&7,\\\\[2.0pt] -x_{1}+4x_{2}&\geq&5.\end{array}\right.$

With each parameter $u$, we connect either the universal quantifier
“$\forall$” or the existential quantifier “$\exists$” as well as the
corresponding elementary quantifier prefix $(\forall
u\in{\makebox{\boldmath$u$}})$ or $(\exists u\in{\makebox{\boldmath$u$}})$.
Such interval uncertainty of parameters can be specified by the interval
matrix ${\makebox{\boldmath$A$}}\in\mathbb{IR}^{m\times n}$, the quantifier
matrix ${\cal A}$ of the same size as $A$, the interval vector
${\makebox{\boldmath$b$}}\in\mathbb{IR}^{m}$ and the quantifier vector $\beta$
of length $m$. All the elementary quantifier prefixes can be written down in
an arbitrary order, and we denote the resulting prefix of the length $m(n+1)$
as $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$.

Definition 1 For given interval matrix $A$, interval vector $b$, and
quantifier prefix $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)$, the interval-quantifier linear system of relations, or interval-
quantifier linear system in short, will be called the predicate of the form
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\,\sigma\,b)$. A vector $\tilde{x}\in\mathbb{R}^{n}$ is referred
to as solution to the interval-quantifier linear system if the predicate
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\,\sigma\,b)$ takes the value “true” in $\tilde{x}$.

This definition is, in fact, a further refinement of the general ideas
expressed in [20]. Also, the above introduced interval-quantifier linear
systems are a natural generalization of interval linear systems, which have
long been studied in interval analysis. _Interval linear system_ of the form
${\makebox{\boldmath$A$}}x\,\sigma\,{\makebox{\boldmath$b$}}$ is a formal
record, for which we specially stipulate what is considered a solution in each
specific case. Usually, interval linear systems of only equations or of only
inequalities of the same sign are considered, while their solutions are taken
as formal (algebraic) solutions, AE-solutions, strong solutions, weak
solutions, tolerable solutions, controllable solutions (sometimes called
simply “control solutions”), etc. (see [21, 20; 3, chapter 2] and references
in these publications).

In order to agree with the existing terminology in this field, the solutions
to the interval-quantifier linear system
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\,\sigma\,b)$ will also be called the _quantifier_ solutions of
the interval linear system
${\makebox{\boldmath$A$}}x\,\sigma\,{\makebox{\boldmath$b$}}$. Notice that AE-
solutions, strong solutions, weak solutions, tolerable solutions, controllable
solutions to the system
${\makebox{\boldmath$A$}}x\,\sigma\,{\makebox{\boldmath$b$}}$ are subsumed
under the quantifier solutions. In particular, the AE-solutions to interval
linear systems of equations are their quantifier solutions for which the
determining predicate
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\,\sigma\,b)$ has the so-called AE-form, that is, in which all
occurrences of the universal quantifier “$\forall$” precede the occurrences of
the existential quantifier “$\exists$”.

The notation $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\,\sigma\,b)$ defines all possible interval-quantifier linear
systems in parametric form. The parameters of the description are $A$, $b$,
${\cal A}$, $\beta$, $\sigma$ and the order of elementary quantifier prefixes
in $Q$ (since the elementary prefixes with different quantifiers do not always
commute). Imposing additional constraints on the parameters, we obtain
different classes (subsets) of interval-quantifier linear systems. For
example, if we require equality to be the value of each component of the
relation vector $\sigma$, then we obtain a class of interval-quantifier
systems of linear equations.

###  1.2 Transition to quantifier-free descriptions

Interval-quantifier linear systems and their solutions were introduced in the
previous section through a logical predicate of the first order. Predicative
description is close to the formulation of practical problems, but it allows
very limited means of theoretical investigation and is not at all suitable for
calculations. As a consequence, the following problem arises:

Problem For the widest possible subset of interval-quantifier linear systems,
find a convenient quantifier-free description of their solutions in algebraic
systems with sufficiently developed tools for equivalent transformations,
study and computation.

Usually, the solution sets to interval systems of equations and inequalities
are described using real arithmetic in $\mathbb{R}$ [3, chapter 2; 2, pp.
93–95; 15, 5, 22, 16, 10, 11], since it is simple, familiar, has good
properties, and we can apply developed numerical methods in $\mathbb{R}$. For
various subclasses of interval quantifier systems of linear equations, a
number of quantifier-free descriptions have been obtained in interval
arithmetics [1, 14, 21, 20]. Despite poor algebraic properties of the interval
arithmetics (the absence of the distributivity, etc.), these descriptions
turned out to be very useful. For instance, the description of the AE-solution
sets of interval systems of linear equations made it possible to construct a
general theory of these solutions and interval numerical methods for inner and
outer estimation of the AE-solution sets [21, 20].

The features of the quantifier-free descriptions proposed in this paper are as
follows:

  * 1.

They expand the class of the interval-quantifier linear systems for which a
convenient description of solutions can be given in comparison with those
known descriptions where non-negativity of $x$ is not required. (The
nonnegativity requirement on the vector of unknowns can be formulated as an
additional restriction on the parameters $A$, $b$ and $\sigma$. A. Vatolin in
[22] obtained quantifier-free descriptions for solutions of general interval-
quantifier linear systems, but his result is only valid under nonnegativity
condition on the variables, which is quite severe limitation in practice. The
class $Q^{\sigma}$ of interval-quantifier linear systems we discuss in the
present paper has no restrictions on $A$, $b$ and $\sigma$, but it has a
restriction on the order of the elementary quantifier prefixes.)

  * 2.

Quantifier-free descriptions of the solutions are obtained in ordinary real
arithmetic $\mathbb{R}$, classical interval arithmetic $\mathbb{IR}$, and in
Kaucher interval arithmetic $\mathbb{KR}$. This enables us to carry out
investigation of the solution sets and computation with them by both real and
interval methods.

##  2 Necessary facts about interval arithmetics

In this section, we give the necessary information on various interval
arithmetics. The desire to improve the properties of the classical interval
arithmetic $\mathbb{IR}$ led to the appearance of its various extensions. The
most popular of them is _Kaucher interval arithmetic_ $\mathbb{KR}$ developed
by E. Kaucher [8]. E. Gardeñes and A. Trepat [4] and then S. Markov [13]
proposed another similar constructions. All these researchers constructed
extensions of the classical interval arithmetic $\mathbb{IR}$ on the basis of
different principles, which was reflected in the names of the corresponding
algebraic structures: extended interval arithmetic [8], modal interval
arithmetic [4], arithmetic of directed intervals [13]. However, despite the
difference in their construction, all three algebraic systems coincide up to
notation.

Interval in $\mathbb{KR}$ is just a record of the form $[a,b]$, where
$a,b\in\mathbb{R}$. In $\mathbb{IR}$, the values $a$ and $b$ should
additionally satisfy the requirement $a\leq b$. Intervals are also denoted by
small boldface letters, e. g., ${\makebox{\boldmath$u$}}\in\mathbb{KR}$. If
$u$ and $[a,b]$ denote the same interval, then $a$ is called left (lower)
endpoint of the interval, which is written as
$\underline{{\makebox{\boldmath$u$}}}$, and $b$ is called the right (upper)
endpoint of the interval $u$, which is written as
$\overline{{\makebox{\boldmath$u$}}}$. Therefore,
${\makebox{\boldmath$u$}}\equiv[\underline{{\makebox{\boldmath$u$}}},\overline{{\makebox{\boldmath$u$}}}]$.
The intervals from $\mathbb{IR}$, as was stated in Introduction, can be
considered as subsets of the real axis $\mathbb{R}$:

$[\underline{{\makebox{\boldmath$u$}}},\overline{{\makebox{\boldmath$u$}}}]=\\{\,u\in\mathbb{R}\mid\underline{{\makebox{\boldmath$u$}}}\leq
u\leq\overline{{\makebox{\boldmath$u$}}}\,\\}.$

In this paper, we will mainly use concepts and properties of Kaucher interval
arithmetic, and we present them below.

Two intervals are considered equal if both their left and right endpoints
coincide:

${\makebox{\boldmath$u$}}={\makebox{\boldmath$v$}}\quad\stackrel{{\scriptstyle\mathrm{def}}}{{\Longleftrightarrow}}\quad\left\\{\,\begin{array}[]{l}\underline{{\makebox{\boldmath$u$}}}=\underline{{\makebox{\boldmath$v$}}},\\\\[5.69054pt]
\overline{{\makebox{\boldmath$u$}}}=\overline{{\makebox{\boldmath$v$}}}.\end{array}\right.$

The inclusion relation “$\subseteq$” in $\mathbb{KR}$ continues the inclusion
relation in $\mathbb{IR}$ that considers intervals as sets. So, we have:

${\makebox{\boldmath$u$}}\subseteq{\makebox{\boldmath$v$}}\quad\stackrel{{\scriptstyle\mathrm{def}}}{{\Longleftrightarrow}}\quad\left\\{\,\begin{array}[]{l}\underline{{\makebox{\boldmath$u$}}}\geq\underline{{\makebox{\boldmath$v$}}},\\\\[5.69054pt]
\overline{{\makebox{\boldmath$u$}}}\leq\overline{{\makebox{\boldmath$v$}}}.\end{array}\right.$
(1)

In particular, $[6,3]\subseteq[4,5]$.

The operations of taking the least upper bound (supremum) and greatest lower
bound (infimum) with respect to inclusion are introduced for families of
intervals bounded from above and from below respectively, using the infimum
and supremum in $\mathbb{R}$:

$\displaystyle\bigvee_{i\in I}{\makebox{\boldmath$u$}}_{i}$ $\displaystyle\
:=\ \sup_{i\in I}{}_{\subseteq}{\makebox{\boldmath$u$}}_{i}\
:=\;\Bigl{[}\;\inf_{i\in
I}\underline{{\makebox{\boldmath$u$}}}_{i},\;\sup_{i\in
I}\overline{{\makebox{\boldmath$u$}}}_{i}\;\Bigr{]},$
$\displaystyle\bigwedge_{i\in I}{\makebox{\boldmath$u$}}_{i}$ $\displaystyle\
:=\ \inf_{i\in I}{}_{\subseteq}{\makebox{\boldmath$u$}}_{i}\
:=\;\Bigl{[}\;\sup_{i\in
I}\underline{{\makebox{\boldmath$u$}}}_{i},\;\inf_{i\in
I}\overline{{\makebox{\boldmath$u$}}}_{i}\;\Bigr{]}.$

We need the following unary operations on intervals:

$\displaystyle\operatorname{mid}{\makebox{\boldmath$u$}}$
$\displaystyle:=\check{{\makebox{\boldmath$u$}}}:=(\underline{{\makebox{\boldmath$u$}}}+\overline{{\makebox{\boldmath$u$}}})/2\quad\text{---
the midpoint,}$ $\displaystyle\operatorname{rad}{\makebox{\boldmath$u$}}$
$\displaystyle:=\hat{{\makebox{\boldmath$u$}}}:=(\overline{{\makebox{\boldmath$u$}}}-\underline{{\makebox{\boldmath$u$}}})/2\quad\text{---
the radius,}$ $\displaystyle\operatorname{dual}{\makebox{\boldmath$u$}}$
$\displaystyle:=[\overline{{\makebox{\boldmath$u$}}},\underline{{\makebox{\boldmath$u$}}}]\quad\text{---
\begin{tabular}[t]{l}the dualization, i.\,e., swapping\\\ the endpoints of the
interval,\end{tabular}}$
$\displaystyle\operatorname{pro}{\makebox{\boldmath$u$}}$
$\displaystyle:=\left\\{\,\begin{array}[]{ll}{\makebox{\boldmath$u$}},&\text{
if
}\underline{{\makebox{\boldmath$u$}}}\leq\overline{{\makebox{\boldmath$u$}}},\\\\[4.0pt]
\operatorname{dual}{\makebox{\boldmath$u$}},&\text{ if
}\underline{{\makebox{\boldmath$u$}}}>\overline{{\makebox{\boldmath$u$}}},\end{array}\right.\quad\text{---
\begin{tabular}[t]{l}the proper projection\\\ of the interval.\end{tabular}}$

Notice that the dualization makes sense only in $\mathbb{KR}$.

Arithmetic operations of addition, subtraction, multiplication and division
are determined through the corresponding real operations and taking exact
lower and upper bounds by inclusion so that

${\makebox{\boldmath$u$}}*{\makebox{\boldmath$v$}}\ =\
\bigvee\bigwedge\nolimits^{{\makebox{\boldmath$u$}}}\bigvee\bigwedge\nolimits^{{\makebox{\boldmath$v$}}}(u*v),\qquad\text{
where
}\;\bigvee\bigwedge\nolimits^{{\makebox{\boldmath$u$}}}:=\left\\{\begin{array}[]{ll}\bigvee\limits_{\operatorname{pro}\scalebox{0.75}{${\makebox{\boldmath$u$}}$}},&\mbox{
if
}\;\underline{{\makebox{\boldmath$u$}}}\leq\overline{{\makebox{\boldmath$u$}}},\\\\[14.22636pt]
\bigwedge\limits_{\operatorname{pro}\scalebox{0.75}{${\makebox{\boldmath$u$}}$}},&\mbox{
if
}\;\underline{{\makebox{\boldmath$u$}}}\geq\overline{{\makebox{\boldmath$u$}}},\end{array}\right.$

for each $*\in\\{+,-,\cdot,/\\}$. Naturally, division is determined only for
such intervals $v$ that $0\not\in\operatorname{pro}{\makebox{\boldmath$v$}}$.
The addition and multiplication are commutative. The addition is defined “by
endpoints”:

${\makebox{\boldmath$u$}}+{\makebox{\boldmath$v$}}=[\underline{{\makebox{\boldmath$u$}}}+\underline{{\makebox{\boldmath$v$}}},\overline{{\makebox{\boldmath$u$}}}+\overline{{\makebox{\boldmath$v$}}}].$
(2)

The real numbers $\lambda\in\mathbb{R}$ are identified with intervals of zero
radius $[\lambda,\lambda]$. Multiplication of an interval by the number
$\lambda\in\mathbb{R}$ satisfy the following properties:

$\lambda{\makebox{\boldmath$u$}}\ =\
\left\\{\,\begin{array}[]{ll}[\lambda\underline{{\makebox{\boldmath$u$}}},\lambda\overline{{\makebox{\boldmath$u$}}}],&\text{
for }\;\lambda\geq 0,\\\\[4.0pt]
[\lambda\overline{{\makebox{\boldmath$u$}}},\lambda\underline{{\makebox{\boldmath$u$}}}],&\text{
for }\;\lambda\leq 0;\end{array}\right.$ (3)
$(\operatorname{dual}{\makebox{\boldmath$u$}})\lambda\stackrel{{\scriptstyle\eqref{lu}}}{{=}}\operatorname{dual}({\makebox{\boldmath$u$}}\lambda)\
=\
[\overline{{\makebox{\boldmath$u$}}\lambda},\underline{{\makebox{\boldmath$u$}}\lambda}].$
(4)

The symbol $-{\makebox{\boldmath$u$}}$ means the result of multiplication
$(-1)\cdot{\makebox{\boldmath$u$}}$, not taking the opposite interval for $u$
with respect to the addition.

The matrices and vectors whose elements are intervals are called interval
matrices and interval vectors respectively. We denote by
${\makebox{\boldmath$A$}}_{i:}$ the $i$-th row of the matrix $A$. For interval
vectors and matrices, the endpoints, the relations $=$ and $\subseteq$, the
operations $\operatorname{mid}$, $\operatorname{rad}$, $\operatorname{dual}$,
$\operatorname{pro}$, as well as addition, subtraction and multiplication by
numbers are introduced componentwise. For example,
$(\operatorname{dual}{\makebox{\boldmath$A$}})_{ij}:=\operatorname{dual}({\makebox{\boldmath$A$}}_{ij})$,
$({\makebox{\boldmath$A$}}-{\makebox{\boldmath$B$}})_{ij}:={\makebox{\boldmath$A$}}_{ij}-{\makebox{\boldmath$B$}}_{ij}$,
$(-{\makebox{\boldmath$A$}})_{ij}=-{\makebox{\boldmath$A$}}_{ij}$. The
multiplication rules for interval vectors and matrices are interval extensions
of analogous rules for the non-interval case:

$({\makebox{\boldmath$A$}}{\makebox{\boldmath$B$}})_{ij}:=\sum\limits_{k}{\makebox{\boldmath$A$}}_{ik}{\makebox{\boldmath$B$}}_{kj}.$
(5)

Also, we need the property

$(\operatorname{dual}{\makebox{\boldmath$A$}})x=\operatorname{dual}({\makebox{\boldmath$A$}}x)\quad\text{
for }{\makebox{\boldmath$A$}}\in\mathbb{KR}^{m\times n},\ x\in\mathbb{R}^{n},$
(6)

which can be easily derived from the definition of interval matrix-vector
product (a particular case of (5)) with the use of (2) and (4).

##  3 Results

###  3.1 Quantifier-free descriptions in interval arithmetics

First of all, we are going to develop quantifier-free descriptions in interval
arithmetics for interval-quantifier linear systems and their solutions. We
need the following notation:

  * $Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ will denote a quantifier prefix obtained from $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ by deleting all those elementary prefixes that are not related to the $i$-th row of the system;

  * $Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ will denote a quantifier prefix of the form $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ satisfying the additional condition: for each $i\in\\{1,\ldots,m\\}$ in $Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$, the universal quantifiers (if any) precede the existential quantifiers (if any);

  * $Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ will denote a quantifier prefix of the form $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ with the additional condition: all the universal quantifiers (if any) precede all the existential quantifiers (if there are such quantifiers);

  * ${\makebox{\boldmath$A$}}^{\forall},{\makebox{\boldmath$A$}}^{\exists}\in\mathbb{IR}^{m\times n}$, ${\makebox{\boldmath$b$}}^{\forall},{\makebox{\boldmath$b$}}^{\exists}\in\mathbb{IR}^{m}$, ${\makebox{\boldmath$A$}}^{\mathfrak{c}}\in\mathbb{KR}^{m\times n}$, ${\makebox{\boldmath$b$}}^{\mathfrak{c}}\in\mathbb{KR}^{m}$ will denote interval vectors and matrices defined by the rules

$\begin{array}[]{r@{\ }l@{\hspace{20mm}}r@{\
}l}{\makebox{\boldmath$A$}}^{\forall}_{\\!ij}&:=\begin{cases}{\makebox{\boldmath$A$}}_{ij},&\text{
if }{\cal A}_{ij}=\forall,\\\ \ 0,&\text{ if }{\cal
A}_{ij}=\exists,\end{cases}\hfil\hskip
56.9055pt&{\makebox{\boldmath$A$}}^{\exists}_{\\!ij}&:=\begin{cases}{\makebox{\boldmath$A$}}_{ij},&\text{
if }{\cal A}_{ij}=\exists,\\\ \ 0,&\text{ if }{\cal
A}_{ij}=\forall,\end{cases}\\\\[25.60747pt]
{\makebox{\boldmath$b$}}^{\forall}_{\\!i}&:=\begin{cases}\
{\makebox{\boldmath$b$}}_{i},&\text{ if }\beta_{i}=\forall,\\\ \ 0,&\text{ if
}\beta_{i}=\exists,\end{cases}\hfil\hskip
56.9055pt&{\makebox{\boldmath$b$}}^{\exists}_{\\!i}&:=\begin{cases}\
{\makebox{\boldmath$b$}}_{i},&\text{ if }\beta_{i}=\exists,\\\ \ 0,&\text{ if
}\beta_{i}=\forall,\end{cases}\end{array}$ (7)
${\makebox{\boldmath$A$}}^{\mathfrak{c}}_{ij}:=\begin{cases}{\makebox{\boldmath$A$}}_{ij},&\text{
if }{\cal A}_{ij}=\forall,\\\
\operatorname{dual}{\makebox{\boldmath$A$}}_{ij},&\text{ if }{\cal
A}_{ij}=\exists,\end{cases}\hskip
34.1433pt{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}:=\begin{cases}\operatorname{dual}{\makebox{\boldmath$b$}}_{i},&\text{
if }\beta_{i}=\forall,\\\ {\makebox{\boldmath$b$}}_{i},&\text{ if
}\beta_{i}=\exists.\end{cases}$ (8)

The Gothic letter “$\mathfrak{c}$” as the superscript of $A$ and $b$ in
formula (8) means “characteristic”. Overall, the matrix
${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ and vector
${\makebox{\boldmath$b$}}^{\mathfrak{c}}$ will be called _characteristic
matrix_ and _characteristic vector_ that correspond to the distribution of
interval uncertainty types (A-type or E-type) described by the quantifier
matrix ${\cal A}$ and vector $\beta$ in the system under study [20, 21].

We should write out the property of interval-quantifier linear systems, which
we will repeatedly apply in the sequel: each elementary quantifier prefix from
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ can be
carried to the row of the system in which the parameter of this prefix is
present. This means

$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)\qquad\Longleftrightarrow\qquad\underset{i\in\\{1,\ldots,m\\}}{\scalebox{1.5}{\&}}\
Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(A_{i:}x\,\sigma_{i}\,b_{i}).$ (9)

The substantiation for this property is that the system of relations
$(Ax\,\sigma\,b)$ is, in terms of logic, the conjunction of the relations,
that is,

$\underset{i}{\scalebox{1.5}{\&}}\
\bigl{(}A_{i:}x\,\sigma_{i}\,b_{i}\bigr{)}.$

Additionally, for the conjunction, there hold equivalences

$\displaystyle\forall t\in{\cal S}\ \bigl{(}P_{1}(t)\ \&\ P_{2}\bigr{)}\quad$
$\displaystyle\Longleftrightarrow\quad\bigl{(}\forall t\in{\cal S}\
P_{1}(t)\bigr{)}\ \&\ P_{2},$ $\displaystyle\exists t\in{\cal S}\
\bigl{(}P_{1}(t)\ \&\ P_{2}\bigr{)}\quad$
$\displaystyle\Longleftrightarrow\quad\bigl{(}\exists t\in{\cal S}\
P_{1}(t)\bigr{)}\ \&\ P_{2},$

where  $\cal S$ is the set of values of the variable $t$, $P_{1}$, $P_{2}$ are
formulas, and $P_{2}$ does not depend on $t$.

In view of (9), it is obvious that

$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\,\sigma\,b)\quad\Longleftrightarrow\quad
Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b),$ (10)

i. e., the vector $x$ is a solution to the system
$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\,\sigma\,b)$ if and only if it is a solution to the system
$Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)$. Thus, although the class of systems of the form
$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\,(Ax\,\sigma\,b)$ is wider than the class of systems of the form
$Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\;(Ax\,\sigma\,b)$, the statements proved for the solutions to the
system $Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\;(Ax\,\sigma\,b)$ are trivially generalized into statements for the
solutions to the system
$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\;(Ax\,\sigma\,b)$.

Now let us turn to the interval-quantifier systems of linear equations.
Quantifier-free descriptions for the widest subset of such systems have been
obtained by S.P. Shary. In [18, 19], he first proved that

$\displaystyle Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax=b)\ \ \Longleftrightarrow\ \
{\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\subseteq{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x\
\ \Longleftrightarrow\ \
{\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}.$
(11)

(see also [20]). Equivalence (10) allows us to make the following
generalization of (11).

###### Theorem 1

$\displaystyle
Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax=b)\ \ \Longleftrightarrow\ \
{\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\subseteq{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x\
\ \Longleftrightarrow\ \
{\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}.$
(12)

Theorem 1 for the interval-quantifier system of equations
$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\;(Ax=b)$ gives equivalent quantifier-free inclusion systems in
$\mathbb{IR}$

${\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\;\subseteq\;{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x$

and in $\mathbb{KR}$

${\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}.$

Definition 2 Let us agree to refer to interval quantifier systems of
relations, in which the vector of relations $\sigma$ consists of the same
components, as relationally homogeneous systems.

The results of Theorem 1 is intended for systems of equations, and our
immediate goal is to obtain similar results for relationally homogeneous
systems of inequalities.

###### Theorem 2

$\displaystyle Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\geq b)\ \ $ $\displaystyle\Longleftrightarrow\ \
\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}\quad\Longleftrightarrow\quad\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}},$
(13) $\displaystyle Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\leq b)\ \ $ $\displaystyle\Longleftrightarrow\ \
\overline{{\makebox{\boldmath$A$}}^{\forall}x}+\underline{{\makebox{\boldmath$A$}}^{\exists}x}\leq\underline{{\makebox{\boldmath$b$}}}^{\forall}+\overline{{\makebox{\boldmath$b$}}}^{\exists}\quad\Longleftrightarrow\quad\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}.$
(14)

P r o o f. We carry out the proof only for the chain of equivalences (13). For
(14), the substantiation is completely similar.

1) From (9), it follows that

$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\geq
b)\quad\Longleftrightarrow\quad\underset{i\in\\{1,\ldots,m\\}}{\scalebox{1.5}{\&}}\
Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(A_{i:}x\geq b_{i}).$ (15)

2) Using the fact that

$A_{i:}x\geq
b_{i}\quad\Longleftrightarrow\quad\sum_{j=1}^{n}A_{ij}x_{j}+(-b_{i})\geq 0$

and that, for any continuous functions $h:\mathbb{R}^{2}\to\mathbb{R}$,
$g:\mathbb{R}\to\mathbb{R}$ and an interval
${\makebox{\boldmath$u$}}\in\mathbb{IR}$, there holds

$\displaystyle(\forall u\in{\makebox{\boldmath$u$}})\ (h(u,x)+g(x)\geq
0)\quad$
$\displaystyle\Longleftrightarrow\quad\min_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}\,h(u,x)+g(x)\geq
0,$ $\displaystyle(\exists u\in{\makebox{\boldmath$u$}})\ (h(u,x)+g(x)\geq
0)\quad$
$\displaystyle\Longleftrightarrow\quad\max_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}\,h(u,x)+g(x)\geq
0,$

enables us to get a quantifier-free description for
$Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(A_{i:}x\geq b_{i})$:

$Q_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(A_{i:}x\geq
b_{i})\quad\Longleftrightarrow\quad\sum_{j=1}^{n}\;\underset{A_{ij}\in\scalebox{0.75}{${\makebox{\boldmath$A$}}$}_{ij}}{\operatorname{extr}^{{\cal
A}_{ij}}}(A_{ij}x_{j})+\underset{b_{i}\in\scalebox{0.75}{${\makebox{\boldmath$b$}}$}_{i}}{\operatorname{extr}^{\beta_{i}}}(-b_{i})\,\geq\,0,$
(16)

where “extr” means conditional extremum, such that

$\operatorname{extr}^{\forall}=\min,\qquad\operatorname{extr}^{\exists}=\max.$

3) Thanks to the equalities

$\min_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}(ux)=\underline{{\makebox{\boldmath$u$}}x},\qquad\max_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}(ux)=\overline{{\makebox{\boldmath$u$}}x},\qquad\min_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}(u)=\underline{u},\qquad\max_{u\in\scalebox{0.75}{${\makebox{\boldmath$u$}}$}}(u)=\overline{u},$

which are valid for any interval ${\makebox{\boldmath$u$}}\in\mathbb{IR}$, and
taking into account (2), the sum of the extrema in (16) can be expressed in
terms of the matrices ${\makebox{\boldmath$A$}}^{\forall}$,
${\makebox{\boldmath$A$}}^{\exists}$ and the vectors
${\makebox{\boldmath$b$}}^{\forall}$, ${\makebox{\boldmath$b$}}^{\exists}$
from (7):

$\sum_{j=1}^{n}\,\underset{A_{ij}\in\scalebox{0.75}{${\makebox{\boldmath$A$}}$}_{ij}}{\operatorname{extr}^{{\cal
A}_{ij}}}(A_{ij}x_{j})+\underset{b_{i}\in\scalebox{0.75}{${\makebox{\boldmath$b$}}$}_{i}}{\operatorname{extr}^{\beta_{i}}}(-b_{i})\geq
0\quad\Longleftrightarrow\quad\underline{{\makebox{\boldmath$A$}}_{i:}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}_{i:}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}_{i}^{\forall}+\underline{{\makebox{\boldmath$b$}}}_{i}^{\exists}.$
(17)

4) From (15)–(17), it follows that

$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\geq
b)\quad\Longleftrightarrow\quad\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}.$

5) Let us prove the second equivalence in the chain (13). For the matrix
${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ in (8), we have

$[\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x},\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}]={\makebox{\boldmath$A$}}^{\mathfrak{c}}x\stackrel{{\scriptstyle\scalebox{0.7}{\begin{tabular}[]{c}definitions\\\
of
${\makebox{\boldmath$A$}}^{\mathfrak{c}},{\makebox{\boldmath$A$}}^{\forall},{\makebox{\boldmath$A$}}^{\exists}$\end{tabular}}}}{{=}}{\makebox{\boldmath$A$}}^{\forall}x+(\operatorname{dual}{\makebox{\boldmath$A$}}^{\exists})x\stackrel{{\scriptstyle\scalebox{0.7}{\begin{tabular}[]{c}properties\\\
\eqref{dualAx} and
\eqref{sumend}\end{tabular}}}}{{=}}[\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x},\,\overline{{\makebox{\boldmath$A$}}^{\forall}x}+\underline{{\makebox{\boldmath$A$}}^{\exists}x}],$
(18)

and therefore
$\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}=\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}$.
The definitions of the vectors ${\makebox{\boldmath$b$}}^{\mathfrak{c}}$,
${\makebox{\boldmath$b$}}^{\forall}$, and ${\makebox{\boldmath$b$}}^{\exists}$
give

$[\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}},\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}]={\makebox{\boldmath$b$}}^{\mathfrak{c}}=\operatorname{dual}({\makebox{\boldmath$b$}}^{\forall})+{\makebox{\boldmath$b$}}^{\exists}=[\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists},\underline{{\makebox{\boldmath$b$}}}^{\forall}+\overline{{\makebox{\boldmath$b$}}}^{\exists}],$
(19)

hence
$\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}=\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}$.
Overall, we get

$\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}\quad\Longleftrightarrow\quad\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}.$

The proof of Theorem 2 is complete.

In the interval arithmetics $\mathbb{IR}$ and $\mathbb{KR}$, the relations
“$\geq$” and “$\leq$” are applicable, and they are continuations of the same
relations over $\mathbb{R}$. For vectors, “$\geq$” and “$\leq$” are introduced
componentwise. This allows us to formally refer to the records with
${\makebox{\boldmath$A$}}^{\forall}$, ${\makebox{\boldmath$A$}}^{\exists}$,
${\makebox{\boldmath$b$}}^{\forall}$, ${\makebox{\boldmath$b$}}^{\exists}$ in
(13) and (14) as inequalities in classical interval arithmetic, while the
records with ${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ and
${\makebox{\boldmath$b$}}^{\mathfrak{c}}$ will be called inequalities in the
Kaucher arithmetic. Still, in practice it is more convenient to understand all
inequalities from (13) and (14) as componentwise inequalities in
$\mathbb{R}^{m}$.

From (9) and Theorems 2, the following remarkable fact follows: _the solution
sets of interval-quantifier systems of linear inequalities with arbitrary
$\sigma\in\\{\geq,\leq\\}^{m}$ does not depend on the order of the elementary
quantifier prefixes, that is, all interval-quantifier systems of linear
inequalities with the same $A$, $b$, $\cal{A}$, $\beta$ and $\sigma$ have the
same solution sets_. This property essentially distinguishes interval systems
of inequalities from interval systems of equations.

We give a corollary of Theorems 1 and 2, which establishes the relation
between AE-solution sets of interval systems of linear equations and
quantifier solution sets of interval relationally homogeneous systems of
linear inequalities.

###### Corollary 1

$Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\,(Ax=b)\ \Longleftrightarrow\
Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\,(Ax=b)\ \Longleftrightarrow\
\begin{cases}Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax\geq b),\\\
Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)(Ax\leq
b).\end{cases}$

The proof is given by the following chain of equivalences:

$\begin{cases}Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\geq b)\\\
Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\leq
b)\end{cases}\quad\stackrel{{\scriptstyle\text{Theorem\leavevmode\nobreak\
\ref{SharayaTineq}}}}{{\Longleftrightarrow}}\quad\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}\\\\[3.0pt]
\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}\end{cases}\quad\stackrel{{\scriptstyle\text{definition
of}\;\subseteq}}{{\Longleftrightarrow}}\quad{\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}\\\\[11.38109pt]
\stackrel{{\scriptstyle\text{Theorem\leavevmode\nobreak\
\ref{SharyT=}}}}{{\Longleftrightarrow}}\ \
Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax=b)\ \
\stackrel{{\scriptstyle\eqref{aeAE}}}{{\Longleftrightarrow}}\ \
Q^{AE}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax=b).$

Theorems 1–2 give quantifier-free descriptions for relationally homogeneous
systems. Next, we turn to the consideration of systems with an arbitrary
relationship vector $\sigma$.

Definition 3 We denote by
$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$
a quantifier prefix of the form
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$
satisfying the following condition: if $\sigma_{i}$ is “$=$”, then the
universal quantifiers (if any) precede the existential quantifiers (if any) in
$Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)$.

Definition 4 The _class $Q^{\sigma}$_ within the set of all interval-
quantifier systems of linear relations is a subset consisting of all systems
of the form
$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)$.

The following theorem gives a quantifier-free description of the class
$Q^{\sigma}$ in the interval arithmetics $\mathbb{KR}$ and $\mathbb{IR}$, with
the use of componentwise inequalities from $\overline{\mathbb{R}}^{m}$, where
$\overline{\mathbb{R}}$ denotes the extended real axis, i. e.,
$\overline{\mathbb{R}}=\mathbb{R}\cup\\{-\infty,\infty\\}$.

###### Theorem 3

$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)\ \ \Longleftrightarrow\ \
\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+u,\\\\[4.0pt]
\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+v,\\\
\end{cases}\Longleftrightarrow\ \
\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}+u,\\\\[4.0pt]
\overline{{\makebox{\boldmath$A$}}^{\forall}x}+\underline{{\makebox{\boldmath$A$}}^{\exists}x}\leq\underline{{\makebox{\boldmath$b$}}}^{\forall}+\overline{{\makebox{\boldmath$b$}}}^{\exists}+v,\\\
\end{cases}$ (20)

where ${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ and
${\makebox{\boldmath$b$}}^{\mathfrak{c}}$ are from (8),
${\makebox{\boldmath$A$}}^{\forall}$, ${\makebox{\boldmath$A$}}^{\exists}$,
${\makebox{\boldmath$b$}}^{\forall}$, ${\makebox{\boldmath$b$}}^{\exists}$ are
from (7), while the vectors $u,v\in\overline{\mathbb{R}}^{m}$ are defined as

$u_{i}:=\left\\{\ \begin{array}[]{cl}0,&\text{if $\sigma_{i}$ is ``$=$'' or
``$\geq$''},\\\\[4.0pt] -\infty,&\text{if ``$\sigma_{i}$'' is
``$\leq$''},\end{array}\right.\qquad\ v_{i}:=\left\\{\
\begin{array}[]{cl}0,&\text{if $\sigma_{i}$ is ``$=$'' or
``$\leq$''},\\\\[4.0pt] \infty,&\text{if $\sigma_{i}$ is
``$\geq$''}.\end{array}\right.$

P r o o f (step by step).

1) Due to the fact that each interval parameter (the element of the matrix $A$
or the vector $b$) enters only one row of the system $Ax\,\sigma\,b$, we have
(9) and, in particular,

$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)\quad\Longleftrightarrow\quad\underset{i\in\\{1,\ldots,m\\}}{\scalebox{1.5}{\&}}\
Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (A_{i:}x\,\sigma_{i}\,b_{i}).$ (21)

2) We eliminate quantifier prefixes in the predicate
$Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (A_{i:}x\,\sigma_{i}\,b_{i})$ using Theorems 1 and 2, based on the
specific values of $\sigma_{i}$:

$\displaystyle
Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (A_{i:}x=b_{i})\ $
$\displaystyle\quad\overset{\eqref{Axeqb}}{\Longleftrightarrow}\quad({\makebox{\boldmath$A$}}^{\mathfrak{c}}x)_{i}\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}\quad\,\Longleftrightarrow\quad\bigl{(}\,(\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\,\bigr{)}\
\&\
\bigl{(}\,(\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\,\bigr{)},$
$\displaystyle
Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (A_{i:}x\geq b_{i})\ $
$\displaystyle\quad\overset{\eqref{Axgeqb}}{\Longleftrightarrow}\quad(\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\quad\,\Longleftrightarrow\quad\bigl{(}\,(\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\,\bigr{)}\
\&\
\bigl{(}\,(\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\leq\infty\,\bigr{)},$
$\displaystyle
Q^{\sigma}_{i:}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (A_{i:}x\leq b_{i})\ $
$\displaystyle\quad\overset{\eqref{Axleqb}}{\Longleftrightarrow}\quad(\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\,\quad\Longleftrightarrow\quad\bigl{(}\,(\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\geq-\infty\,\bigr{)}\
\&\
\bigl{(}\,(\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x})_{i}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}_{i}}\,\bigr{)}.$

3) Introducing the vectors $u$ and $v$, we pass to the matrix-vector
inequalities

$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)\quad\Longleftrightarrow\quad\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+u,\\\\[4.0pt]
\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+v.\\\
\end{cases}$

4) The equivalence

$\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+u,\\\\[4.0pt]
\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}+v,\\\
\end{cases}\quad\Longleftrightarrow\quad\begin{cases}\underline{{\makebox{\boldmath$A$}}^{\forall}x}+\overline{{\makebox{\boldmath$A$}}^{\exists}x}\geq\overline{{\makebox{\boldmath$b$}}}^{\forall}+\underline{{\makebox{\boldmath$b$}}}^{\exists}+u,\\\\[4.0pt]
\overline{{\makebox{\boldmath$A$}}^{\forall}x}+\underline{{\makebox{\boldmath$A$}}^{\exists}x}\leq\underline{{\makebox{\boldmath$b$}}}^{\forall}+\overline{{\makebox{\boldmath$b$}}}^{\exists}+v,\\\
\end{cases}$

is obvious in view of (18) and (19). The proof of Theorem 3 is complete.

Convenient quantifier-free representations for the class $Q^{\sigma}$ can be
obtained from Theorem 3, if we introduce the sets of intervals
$\mathbb{K}\overline{\mathbb{R}}=\\{[\underline{z},\overline{z}]\mid\underline{z},\overline{z}\in\overline{\mathbb{R}}\\}$
and
$\mathbb{I}\overline{\mathbb{R}}=\\{[\underline{z},\overline{z}]\mid\underline{z},\overline{z}\in\overline{\mathbb{R}},\
\underline{z}\leq\overline{z}\\}$ and continue relation “$\subseteq$”
according to rule (1). Then

$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)\quad\Longleftrightarrow\quad{\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}+{\makebox{\boldmath$w$}}\quad\Longleftrightarrow\quad{\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\subseteq{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x+{\makebox{\boldmath$w$}},$
(22)

where ${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ and
${\makebox{\boldmath$b$}}^{\mathfrak{c}}$ from (8),
${\makebox{\boldmath$A$}}^{\forall}$, ${\makebox{\boldmath$A$}}^{\exists}$,
${\makebox{\boldmath$b$}}^{\forall}$, ${\makebox{\boldmath$b$}}^{\exists}$
from (7), and the interval vector
${\makebox{\boldmath$w$}}\in\mathbb{I}\overline{\mathbb{R}}^{m}$ is such that

${\makebox{\boldmath$w$}}_{i}:=\left\\{\begin{array}[]{c@{\hspace{3mm}}c}0,\hfil\hskip
8.53581pt&{\text{ if $\sigma_{i}$ is ``$=$''}},\\\\[3.0pt]
{[0,\infty]},\hfil\hskip 8.53581pt&{\text{ if $\sigma_{i}$ is
``$\geq$''}},\\\\[3.0pt] {[-\infty,0]},\hfil\hskip 8.53581pt&{\text{ if
$\sigma_{i}$ is ``$\leq$''}}.\end{array}\right.$

The inclusion

${\makebox{\boldmath$A$}}^{\mathfrak{c}}x\;\subseteq\;{\makebox{\boldmath$b$}}^{\mathfrak{c}}+{\makebox{\boldmath$w$}}$

provides a quantifier-free description of the solution set to the quantifier
interval linear system
$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)$ in any interval arithmetic that extends the Kaucher
arithmetic to the set $\mathbb{K}\overline{\mathbb{R}}$. An example of such an
extension is given in [7]. We agree to denote the arithmetic extension, as
well as its basic set, through $\mathbb{K}\overline{\mathbb{R}}$.

Similarly, the inclusion

${\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\;\subseteq\;{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x+{\makebox{\boldmath$w$}}$

provides a quantifier-free description of the solution set to the system
$Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)$ in interval arithmetic that extends $\mathbb{IR}$ to the set
$\mathbb{I}\overline{\mathbb{R}}$. Examples of the extension of the classical
interval arithmetic to a set of intervals with infinite endpoints are
described in [12]. Let us agree to refer to any such extension as arithmetic
$\mathbb{I}\overline{\mathbb{R}}$. Thus, the relation (22) gives quantifier-
free descriptions of the solution sets to quantifier interval linear systems
of class $Q^{\sigma}$ in the interval arithmetics
$\mathbb{K}\overline{\mathbb{R}}$ and $\mathbb{I}\overline{\mathbb{R}}$.

Comparing the quantifier-free descriptions obtained for the solution sets to
quantifier interval linear systems, we can see that,

on the one hand, the quantifier-free description in $\mathbb{KR}$
($\mathbb{K}\overline{\mathbb{R}}$) is much more remote from the initial data
$A$, $b$, $\cal A$ and $\beta$ due to multilevel notation, and,

on the other hand, the description in $\mathbb{KR}$
($\mathbb{K}\overline{\mathbb{R}}$) is more concise and convenient for
analysis than a similar description in $\mathbb{IR}$
($\mathbb{I}\overline{\mathbb{R}}$).

###  3.2 Quantifier-free descriptions in real arithmetic

In this section, we derive quantifier-free descriptions of the quantifier
solution sets to interval linear systems in the real arithmetic $\mathbb{R}$.
To do that, we will need _Hadamard product_ of matrices (entrywise product),
denoted by the symbol “$\circ$” (see e. g. [6]). Hadamard product is defined
for two matrices of the same dimensions and produces another matrix in which
the $ij$-th element is the product of the $ij$-th elements of the original
matrices:

$(A\circ B)_{ij}=A_{ij}B_{ij}.$

Also, notice that the operation of taking the modulus of a vector is
understood componentwise. If, for instance, $x\in\mathbb{R}^{n}$, then $|x|$
is a nonnegative vector with the components $|x|_{i}=|x_{i}|$.

###### Theorem 4

$\displaystyle
Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax=b)$
$\displaystyle\quad\Longleftrightarrow\quad|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq({\cal
A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\,\hat{{\makebox{\boldmath$b$}}},$
(23) $\displaystyle Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\geq b)$
$\displaystyle\quad\Longleftrightarrow\quad\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\,\leq({\cal
A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\,\hat{{\makebox{\boldmath$b$}}},$
(24) $\displaystyle Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\leq b)$ $\displaystyle\quad\Longleftrightarrow\
\quad\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\,\leq({\cal
A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\,\hat{{\makebox{\boldmath$b$}}},$
(25) $\displaystyle
Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\
(Ax\,\sigma\,b)$
$\displaystyle\quad\Longleftrightarrow\quad\operatorname{abs}^{\sigma}(\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}})\leq({\cal
A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\,\hat{{\makebox{\boldmath$b$}}},$
(26)

where

${\cal A}^{s}_{ij}=\begin{cases}\ \ 1,&\text{ if }{\cal A}_{ij}=\exists,\\\
-1,&\text{ if }{\cal
A}_{ij}=\forall,\end{cases}\qquad\beta^{s}_{i}=\begin{cases}\ \ 1,&\text{ if
}\beta_{i}=\exists,\\\ -1,&\text{ if }\beta_{i}=\forall,\end{cases}$ (27)
$\operatorname{abs}_{i}\\!^{\sigma}(y)=\left\\{\
\begin{array}[]{cc}|y_{i}|,&\text{ if $\sigma_{i}$ is ``$=$''},\\\\[3.0pt]
-y_{i},&\text{ if $\sigma_{i}$ is ``$\geq$''},\\\\[3.0pt] y_{i},&\text{ if
$\sigma_{i}$ is ``$\leq$''}.\end{array}\right.$

P r o o f.

1) The equivalence (23) was proposed and proved by Jiri Rohn at the
international conference INTERVAL’96 (September–October of 1996, Würzburg,
Germany), in a private talk with Sergey Shary and Anatoly Lakeyev. Later, its
reformulation with the use of Hadamard product was proposed by Anatoly Lakeyev
in the work [11]. Below, we present our own proof.

In view of Theorem 1,

$Q^{\forall\exists}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)(Ax=b)\quad\Longleftrightarrow\quad{\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}.$

Then, using the properties of Kaucher arithmetic

$(\forall{\makebox{\boldmath$u$}},{\makebox{\boldmath$v$}}\in\mathbb{KR}^{m})\
\ \bigl{(}{\makebox{\boldmath$u$}}\subseteq{\makebox{\boldmath$v$}}\
\Longleftrightarrow\
|\check{{\makebox{\boldmath$u$}}}-\check{{\makebox{\boldmath$v$}}}|\leq\hat{{\makebox{\boldmath$v$}}}-\hat{{\makebox{\boldmath$u$}}}\bigr{)},$
$\operatorname{mid}({\makebox{\boldmath$A$}}^{\mathfrak{c}}x)=\check{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}x,\qquad\operatorname{rad}({\makebox{\boldmath$A$}}^{\mathfrak{c}}x)=\hat{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}\,|x|,$
(28)

and we get

${\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}\quad\Longleftrightarrow\quad|\check{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}x-\check{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}|\;\leq\;\hat{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}-\hat{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}\,|x|.$

From the definitions of (8) and (27) for
${\makebox{\boldmath$A$}}^{\mathfrak{c}}$,
${\makebox{\boldmath$b$}}^{\mathfrak{c}}$, ${\cal A}^{s}$, and $\beta^{s}$, we
have

$\check{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}=\check{{\makebox{\boldmath$A$}}},\qquad\hat{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}=-{\cal
A}^{s}\circ\hat{{\makebox{\boldmath$A$}}},\qquad\check{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}=\check{{\makebox{\boldmath$b$}}},\qquad\hat{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}=\beta^{s}\circ\hat{{\makebox{\boldmath$b$}}}.$
(29)

2) Let us prove the equivalence (24). According to Theorem 2

$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)(Ax\geq
b)\quad\Longleftrightarrow\quad\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\;\geq\;\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}.$

Drawing on the obvious property of the Kaucher arithmetic

$(\forall{\makebox{\boldmath$u$}},{\makebox{\boldmath$v$}}\in\mathbb{KR}^{m})\
\ \bigl{(}\underline{u}\geq\underline{v}\ \Longleftrightarrow\
\check{{\makebox{\boldmath$v$}}}-\check{{\makebox{\boldmath$u$}}}\leq\hat{{\makebox{\boldmath$v$}}}-\hat{{\makebox{\boldmath$u$}}}\bigr{)},$

which allows us to replace the inequality between the endpoints by the
inequality between centers and radii, and then involving (28), we get

$\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\,\geq\,\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}\quad\Longleftrightarrow\quad\check{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}-\check{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}x\,\leq\,\hat{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}-\hat{{\makebox{\boldmath$A$}}^{\mathfrak{c}}}\,|x|.$

Finally, we use (29).

3) The equivalence (25) is proved similarly to (24).

4) It remains to substantiate the equivalence (26). Just as in the item 1 of
the proof of Theorem 3, we have (21), i. e., the problem splits in rows. We
apply, to each row, one of the equivalences (23), (24) or (25), depending on
the corresponding binary relation, and convolve the resulting system of
inequalities using the operation $\operatorname{abs}^{\sigma}$.

The proof of Theorem 4 is complete.

From the equivalences (23)–(25), one more proof of Corollary 1 becomes
obvious. In addition, it is not difficult to establish the following
connection between relationally homogeneous systems of inequalities of the
opposite signs.

###### Corollary 2

$\displaystyle Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\geq b)\quad\Longleftrightarrow\quad
Q(-{\makebox{\boldmath$A$}},-{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\leq
b),$ (30) $\displaystyle
Q(-{\makebox{\boldmath$A$}},-{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\geq
b)\quad\Longleftrightarrow\quad
Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\leq
b).$ (31)

P r o o f. Based on the properties of intervals

$\operatorname{mid}(-{\makebox{\boldmath$u$}})=-\check{{\makebox{\boldmath$u$}}}\qquad\text{
and
}\qquad\operatorname{rad}(-{\makebox{\boldmath$u$}})=\hat{{\makebox{\boldmath$u$}}},$
(32)

we can show the validity of relation (31):

$\displaystyle Q(-{\makebox{\boldmath$A$}},-{\makebox{\boldmath$b$}},{\cal
A},\beta)\ (Ax\geq b)$ $\displaystyle\
\stackrel{{\scriptstyle\eqref{TRgeq}}}{{\Longleftrightarrow}}\
\operatorname{mid}(-{\makebox{\boldmath$b$}})-\operatorname{mid}(-{\makebox{\boldmath$A$}})x\,\leq\bigl{(}{\cal
A}^{s}\\!\circ\,\operatorname{rad}(-{\makebox{\boldmath$A$}})\bigr{)}|x|+\beta^{s}\\!\circ\,\operatorname{rad}(-{\makebox{\boldmath$b$}}),$
$\displaystyle\
\stackrel{{\scriptstyle\eqref{midrad-}}}{{\Longleftrightarrow}}\ \
-\check{{\makebox{\boldmath$b$}}}+\check{{\makebox{\boldmath$A$}}}x\,\leq({\cal
A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\,\hat{{\makebox{\boldmath$b$}}},$
$\displaystyle\ \stackrel{{\scriptstyle\eqref{TRleq}}}{{\Longleftrightarrow}}\
\ Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)\ (Ax\leq
b).$

Relation (30) is proved similarly.

Corollary 2 means that, if the sign of the inequality and the signs of all
intervals of the parameter values are reversed to the opposite, then the set
of quantifier solutions to the interval system of linear inequalities does not
change. For example, the sets of solutions to the systems $(\forall
A\in{\makebox{\boldmath$A$}})\,(\exists b\in{\makebox{\boldmath$b$}})\,(Ax\geq
b)$ and $(\forall A\in-{\makebox{\boldmath$A$}})\,(\exists
b\in-{\makebox{\boldmath$b$}})\,(Ax\leq b)$ coincide.

###  3.3 Quantifier-free descriptions in $\mathbb{KR}$, $\mathbb{IR}$ and
$\mathbb{R}$
for systems of basic types

So far, considering the interval-quantifier linear systems
$Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal
A},\beta)\,(Ax\,\sigma\,b)$, we tried to obtain results in which there are no
constraints on the parameters $A$, $b$, ${\cal A}$, $\beta$ and $\sigma$, and
the restrictions on the order of the elementary quantifier prefixes in $Q$ are
minimal. In this sense, the most general descriptions were found for the class
$Q^{\sigma}$. In this section, we consider subsets of interval-quantifier
linear systems of class $Q^{\sigma}$, which are distinguished by the
requirement of homogeneity of ${\cal A}$ and the homogeneity of $\beta$.
Elements of all these subsets will be called systems of basic types, and their
solutions will be referred to as _quantifier solutions of basic types_ for
interval linear systems of the form
${\makebox{\boldmath$A$}}x\,\sigma\,{\makebox{\boldmath$b$}}$.

Depending on which quantifiers fill the matrix $\cal{A}$ and the vector
$\beta$, all the interval-quantifier linear systems of the basic types are
divided into 4 subsets, or 4 types. This subdivision is presented in the last
column of Table 1. For solutions to systems of each of the main types, we give
a proper name that continues the one used in [3, 21] for solutions of
relationally homogeneous systems of this type. The names of the solutions are
listed in the first column of Table 1, the values of the elements of the
matrix $\cal{A}$ and components of the vector $\beta$ are listed in the second
and third columns, and the fourth column gives the general form for the
interval-quantifier systems of the corresponding basic type.

T a b l e 1
---
Basic types of quantifier solutions to the interval system
${\makebox{\boldmath$A$}}x\,\sigma\,{\makebox{\boldmath$b$}}$
Name | Values of elements | Interval-quantifier
of solution | of the matrix $\cal{A}$ | of the vector $\beta$ | system of basic type
weak | $\exists$ | $\exists$ | $(\exists A\in{\makebox{\boldmath$A$}})(\exists b\in{\makebox{\boldmath$b$}})\ (Ax\,\sigma\,b)$
tolerable | $\forall$ | $\exists$ | $(\forall A\in{\makebox{\boldmath$A$}})(\exists b\in{\makebox{\boldmath$b$}})\ (Ax\,\sigma\,b)$
controllable | $\exists$ | $\forall$ | $(\forall b\in{\makebox{\boldmath$b$}})(\exists A\in{\makebox{\boldmath$A$}})\ (Ax\,\sigma\,b)$
strong | $\forall$ | $\forall$ | $(\forall A\in{\makebox{\boldmath$A$}})(\forall b\in{\makebox{\boldmath$b$}})\ (Ax\,\sigma\,b)$

Quantifier-free descriptions in $\mathbb{KR}$, $\mathbb{IR}$ and $\mathbb{R}$
for systems of basic types can be obtained as corollaries of the corresponding
descriptions for systems of class $Q^{\sigma}$. Let us explain that for
relationally homogeneous systems using Table 2.

T a b l e 2
---
Characterization of relationally homogeneous interval-quantifier linear
systems and their main solution types
|  | Type of solution and corresponding quantifier prefix $Q({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$
$Ax\,\sigma\,b$ |  Space of description |  | Basic types of solutions
|  | Quantifier | Weak | Tolerable | Controllable | Strong
|  | $Q^{\sigma}({\makebox{\boldmath$A$}},{\makebox{\boldmath$b$}},{\cal A},\beta)$ | $(\exists A\in{\makebox{\boldmath$A$}})\ (\exists b\in{\makebox{\boldmath$b$}})$ | $(\forall A\in{\makebox{\boldmath$A$}})\ (\exists b\in{\makebox{\boldmath$b$}})$ | $(\forall b\in{\makebox{\boldmath$b$}})\ (\exists A\in{\makebox{\boldmath$A$}})$ | $(\forall A\in{\makebox{\boldmath$A$}})\ (\forall b\in{\makebox{\boldmath$b$}})$
$Ax=b$ | $\mathbb{KR}$ | ${\makebox{\boldmath$A$}}^{\mathfrak{c}}x\subseteq{\makebox{\boldmath$b$}}^{\mathfrak{c}}$ | $(\operatorname{dual}{\makebox{\boldmath$A$}})x\subseteq{\makebox{\boldmath$b$}}$ | ${\makebox{\boldmath$A$}}x\subseteq{\makebox{\boldmath$b$}}$ | $(\operatorname{dual}{\makebox{\boldmath$A$}})x\subseteq\operatorname{dual}{\makebox{\boldmath$b$}}$ | ${\makebox{\boldmath$A$}}x\subseteq\operatorname{dual}{\makebox{\boldmath$b$}}$
| $\mathbb{IR}$ | ${\makebox{\boldmath$A$}}^{\forall}x-{\makebox{\boldmath$b$}}^{\forall}\subseteq{\makebox{\boldmath$b$}}^{\exists}-{\makebox{\boldmath$A$}}^{\exists}x$ | $0\in{\makebox{\boldmath$b$}}-{\makebox{\boldmath$A$}}x$ | ${\makebox{\boldmath$A$}}x\subseteq{\makebox{\boldmath$b$}}$ | ${\makebox{\boldmath$b$}}\subseteq{\makebox{\boldmath$A$}}x$ | ${\makebox{\boldmath$A$}}x-{\makebox{\boldmath$b$}}\subseteq 0$
| $\mathbb{R}$ | $|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq({\cal A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\\!\hat{{\makebox{\boldmath$b$}}}$ | $|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq-\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$ | $|\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}|\leq-\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$
$Ax\geq b$ | $\mathbb{KR}$ | $\underline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\geq\underline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}$ | $\underline{(\operatorname{dual}{\makebox{\boldmath$A$}})x}\geq\underline{{\makebox{\boldmath$b$}}}$ | $\underline{{\makebox{\boldmath$A$}}x}\geq\underline{{\makebox{\boldmath$b$}}}$ | $\underline{(\operatorname{dual}{\makebox{\boldmath$A$}})x}\geq\overline{{\makebox{\boldmath$b$}}}$ | $\underline{{\makebox{\boldmath$A$}}x}\geq\overline{{\makebox{\boldmath$b$}}}$
| $\mathbb{IR}$ | $\overline{{\makebox{\boldmath$A$}}^{\exists}x}+\underline{{\makebox{\boldmath$A$}}^{\forall}x}\geq\underline{{\makebox{\boldmath$b$}}}^{\exists}+\overline{{\makebox{\boldmath$b$}}}^{\forall}$ | $\overline{{\makebox{\boldmath$A$}}x}\geq\underline{{\makebox{\boldmath$b$}}}$ | $\underline{{\makebox{\boldmath$A$}}x}\geq\underline{{\makebox{\boldmath$b$}}}$ | $\overline{{\makebox{\boldmath$A$}}x}\geq\overline{{\makebox{\boldmath$b$}}}$ | $\underline{{\makebox{\boldmath$A$}}x}\geq\overline{{\makebox{\boldmath$b$}}}$
| $\mathbb{R}$ | $\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\leq({\cal A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\\!\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\leq\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\leq-\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\leq\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$b$}}}-\check{{\makebox{\boldmath$A$}}}x\leq-\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$
$Ax\leq b$ | $\mathbb{KR}$ | $\overline{{\makebox{\boldmath$A$}}^{\mathfrak{c}}x}\leq\overline{{\makebox{\boldmath$b$}}^{\mathfrak{c}}}$ | $\overline{(\operatorname{dual}{\makebox{\boldmath$A$}})x}\leq\overline{{\makebox{\boldmath$b$}}}$ | $\overline{{\makebox{\boldmath$A$}}x}\leq\overline{{\makebox{\boldmath$b$}}}$ | $\overline{(\operatorname{dual}{\makebox{\boldmath$A$}})x}\leq\underline{{\makebox{\boldmath$b$}}}$ | $\overline{{\makebox{\boldmath$A$}}x}\leq\underline{{\makebox{\boldmath$b$}}}$
| $\mathbb{IR}$ | $\underline{{\makebox{\boldmath$A$}}^{\exists}x}+\overline{{\makebox{\boldmath$A$}}^{\forall}x}\leq\overline{{\makebox{\boldmath$b$}}}^{\exists}+\underline{{\makebox{\boldmath$b$}}}^{\forall}$ | $\underline{{\makebox{\boldmath$A$}}x}\leq\overline{{\makebox{\boldmath$b$}}}$ | $\overline{{\makebox{\boldmath$A$}}x}\leq\overline{{\makebox{\boldmath$b$}}}$ | $\underline{{\makebox{\boldmath$A$}}x}\leq\underline{{\makebox{\boldmath$b$}}}$ | $\overline{{\makebox{\boldmath$A$}}x}\leq\underline{{\makebox{\boldmath$b$}}}$
| $\mathbb{R}$ | $\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\leq({\cal A}^{s}\\!\circ\\!\hat{{\makebox{\boldmath$A$}}})|x|+\beta^{s}\\!\circ\\!\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\leq\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\leq-\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\leq\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$ | $\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}}\leq-\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}$

In the Table 2, columns 4–7, corresponding to the basic types of quantifier
solutions, are obtained, in row-wise manner, from column 3 corresponding to
quantifier solutions with the prefix $Q^{\sigma}$. It is necessary to use the
definition of (8) of the matrix ${\makebox{\boldmath$A$}}^{\mathfrak{c}}$ and
vector ${\makebox{\boldmath$b$}}^{\mathfrak{c}}$ in the rows corresponding to
the Kaucher arithmetic. In the rows that correspond to the classical interval
arithmetic, we have to use definition (7) of the matrices
${\makebox{\boldmath$A$}}^{\forall}$, ${\makebox{\boldmath$A$}}^{\exists}$ and
the vectors ${\makebox{\boldmath$b$}}^{\forall}$,
${\makebox{\boldmath$b$}}^{\exists}$. Finally, the rows corresponding to real
non-interval arithmetic, the definition (27) of the matrix ${\cal A}^{s}$,
vector $\beta^{s}$ and the definition of the product $\circ$ should be used.

Approximately half of the descriptions of the basic types of quantifier
solutions for interval linear systems, presented in columns 4–7 of Table 2,
have been obtained earlier. The descriptions that were found first, obtained
their own proper names. These are

  * the Oettli-Prager characterization in $\mathbb{R}$ [15] and the Beeck characterization in $\mathbb{IR}$ [1]
for weak solutions of the equation
${\makebox{\boldmath$A$}}x={\makebox{\boldmath$b$}}$,

  * the Gerlach description in $\mathbb{R}$ for weak solutions of the inequality ${\makebox{\boldmath$A$}}x\leq{\makebox{\boldmath$b$}}$ [5].

The quantifier-free descriptions of the set of tolerable solutions to the
equation ${\makebox{\boldmath$A$}}x={\makebox{\boldmath$b$}}$ was obtained in
$\mathbb{R}$ by J. Rohn [16] and in $\mathbb{IR}$ by A. Neumaier [14]. The
description in $\mathbb{R}$ was further investigated by A.V. Lakeyev and S.I.
Noskov in [10], and they also presented, as an evident one, a description, in
$\mathbb{IR}$, for the set of controllable solutions to the equation
${\makebox{\boldmath$A$}}x={\makebox{\boldmath$b$}}$ (see also [17]). The
remaining descriptions for the basic types of quantifier solutions to the
equation ${\makebox{\boldmath$A$}}x={\makebox{\boldmath$b$}}$ in the interval
arithmetics $\mathbb{IR}$ and $\mathbb{KR}$ are also known, for example, as
obvious corollaries of the statement (11), proved by S.P Shary in [18, 19]. In
Theorem 2.25 from the book [3], a quantifier-free description in $\mathbb{R}$
for strong solutions to the interval inequality
${\makebox{\boldmath$A$}}x\leq{\makebox{\boldmath$b$}}$ was presented.

For interval-quantifier systems of basic types in which the relationship
vector $\sigma$ is not homogeneous, quantifier-free descriptions in
$\mathbb{K}\overline{\mathbb{R}}$ can be obtained from (22) and (8). The
descriptions in $\mathbb{I}\overline{\mathbb{R}}$ can be derived from (22) and
(7), and the descriptions in $\mathbb{R}$ follows from (26) and (27). Below,
we give these descriptions only in $\mathbb{I}\overline{\mathbb{R}}$ and
$\mathbb{R}$ (in $\mathbb{K}\overline{\mathbb{R}}$, they are less expressive
and differ from the descriptions in $\mathbb{I}\overline{\mathbb{R}}$ by
obvious arithmetic transformations, in the same way as the descriptions in
$\mathbb{KR}$ and $\mathbb{IR}$ differ from each other in Table 2):

$\displaystyle(\exists A\in{\makebox{\boldmath$A$}})(\exists
b\in{\makebox{\boldmath$b$}})\ $ $\displaystyle(Ax\,\sigma\,b)\ \
\Longleftrightarrow$ $\displaystyle
0\in{\makebox{\boldmath$b$}}-{\makebox{\boldmath$A$}}x+{\makebox{\boldmath$w$}}$
$\displaystyle\Longleftrightarrow\ \
\operatorname{abs}^{\sigma}(\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}})\leq\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}};$
$\displaystyle(\forall A\in{\makebox{\boldmath$A$}})(\exists
b\in{\makebox{\boldmath$b$}})\ $ $\displaystyle(Ax\,\sigma\,b)\ \
\Longleftrightarrow$
$\displaystyle{\makebox{\boldmath$A$}}x\subseteq{\makebox{\boldmath$b$}}+{\makebox{\boldmath$w$}}$
$\displaystyle\Longleftrightarrow\ \
\operatorname{abs}^{\sigma}(\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}})\leq-\hat{{\makebox{\boldmath$A$}}}|x|+\hat{{\makebox{\boldmath$b$}}};$
$\displaystyle(\forall b\in{\makebox{\boldmath$b$}})(\exists
A\in{\makebox{\boldmath$A$}})\ $ $\displaystyle(Ax\,\sigma\,b)\ \
\Longleftrightarrow$
$\displaystyle{\makebox{\boldmath$b$}}\subseteq{\makebox{\boldmath$A$}}x+{\makebox{\boldmath$w$}}$
$\displaystyle\Longleftrightarrow\ \
\operatorname{abs}^{\sigma}(\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}})\leq\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}};$
$\displaystyle(\forall A\in{\makebox{\boldmath$A$}})(\forall
b\in{\makebox{\boldmath$b$}})\ $ $\displaystyle(Ax\,\sigma\,b)\ \
\Longleftrightarrow$
$\displaystyle{\makebox{\boldmath$A$}}x-{\makebox{\boldmath$b$}}\subseteq{\makebox{\boldmath$w$}}$
$\displaystyle\Longleftrightarrow\ \
\operatorname{abs}^{\sigma}(\check{{\makebox{\boldmath$A$}}}x-\check{{\makebox{\boldmath$b$}}})\leq-\hat{{\makebox{\boldmath$A$}}}|x|-\hat{{\makebox{\boldmath$b$}}}.$

##  4 Conclusion

The main results of the paper are presented in Theorems 2–4 (equivalence (23)
was previously known) and in Corollary 1.

Among the statements that have no restrictions on the parameters $A$, $b$,
${\cal A}$, $\beta$ and $\sigma$, those that give quantifier-free descriptions
of interval-quantifier linear systems of class $Q^{\sigma}$ have the greatest
generality. These are the relation (20), which provides a transition to
$\mathbb{KR}$ and $\mathbb{IR}$, the relation (22) for the transition to
$\mathbb{K}\overline{\mathbb{R}}$ and $\mathbb{I}\overline{\mathbb{R}}$, and
equivalence (26) that allows us to go into $\mathbb{R}$.

The usefulness of quantifier-free descriptions from (20), (22) and (26) is
that they give us the possibility

  * •

to study all interval-quantifier linear systems of class $Q^{\sigma}$
simultaneously and in a uniform way, and to derive results for their
subclasses (in particular, for interval-quantifier systems of basic types) as
consequences of the general result;

  * •

to design such solution methods for problems related to interval-quantifier
linear systems that are suitable for all systems of class $Q^{\sigma}$ (an
example is the author’s software package for visualization of quantifier
solution sets to interval linear systems, available at
http://www.nsc.ru/interval/sharaya).

Quantifier-free descriptions, in interval arithmetic, for various classes of
interval-quantifier linear systems and for their solutions, both previously
known (for example, relation (11)) and those obtained in this paper in the
form of relations (12)–(14), (20), (22), allow us

  * •

to investigate interval-quantifier linear systems by interval methods, i. e.,
to reveal the properties of their solution sets, the relationships between
systems with various conditions on the parameters $A$, $b$, ${\cal A}$,
$\beta$, $\sigma$ and the order of the quantifier prefixes (an example is the
proof of Corollary 1);

  * •

to construct interval (that is, essentially using interval arithmetic)
solution methods for problems in which the formulation involves interval-
quantifier linear systems (examples of such methods for systems of equations
can be found in [21], while for inequalities and systems of class $Q^{\sigma}$
constructing such methods is a matter of the future).

## References

  * [1] Beeck, H. Charakterisierung der Lösungsmenge von Intervallgleichungssystemen // ZAMM. – 1973. – Bd. 53, No. 12. – S. T181–T182.
  * [2] Eremin, I.I. Contradictory Models of Optimal Planning. – Moscow: Nauka Publishers, 1988. (in Russian)
  * [3] Fiedler, M., Nedoma, J., Ramik, J., Rohn, J., and Zimmermann, K. Linear optimization problems with inexact data. – New York: Springer Science+Business Media, 2006.
  * [4] Gardeñes, E., Trepat, A. Fundamentals of SIGLA, an interval computing system over the completed set of intervals // Computing. – 1980. – Vol. 24. – P. 161–179.
  * [5] Gerlach, W. Zur Lösung linearer Ungleichungssysteme bei Störung der rechten Seite und der Koeffizientenmatrix // Mathematische Operationsforschung und Statistik, Series Optimization. – 1981. – Bd. 12. – S. 41–43.
  * [6] Horn, R.A., Johnson, C.R. Matrix analysis. – Cambridge: Cambridge University Press, 2012.
  * [7] Kaucher, E. Über metrische und algebraische Eigenschaften einiger beim numerischen Rechnen auftretender Räume: Dr. Naturwissen Dissertation. – Karlsruhe: Universität Karlsruhe, 1973. – 271 S.
  * [8] Kaucher, E. Interval analysis in the extended interval space $\mathbb{IR}$ // Fundamentals of numerical computation (Computer-oriented numerical analysis) / Alefeld G., Grigorieff R.D., eds. – Wien: Springer, 1980. P. 33–49. – (Computing. Suppl. 2).
  * [9] Kearfott, A., Nakao, M., Neumaier, A., Rump, S., Shary, S., and van Hentenryck, P. Standardized notation in interval analysis // Computational Technologies. – 2010. – Vol. 15, No. 1. – P. 7–13. (available at http://www.ict.nsc.ru/jct/getfile.php?id=1345)
  * [10] Lakeev, A.V., Noskov, S.I. On the solution set of a linear equation with the right-hand side and operator given by intervals // Siberian Mathematical Journal. – 1994. – Vol. 35, Issue 5. – P. 957–966.
  * [11] Lakeyev, A.V. Computational complexity of estimation of generalized solution sets for interval linear systems // Computational Technologies. – 2003. – Vol. 8, No. 1. P. 12–23. (available at http://www.ict.nsc.ru/jct/content/t8n1/Lakeev.pdf)
  * [12] Markov, S.M. Extended interval arithmetic involving infinite intervals // Mathematica Balkanica. New Series. – 1992. – Vol. 6, No. 3. – P. 269–304.
  * [13] Markov, S.M. On directed interval arithmetic and its applications // Journal of Universal Computer Science. – 1995. – Vol. 1, No. 7. – P. 514–526.
  * [14] Neumaier, A. Tolerance analysis with interval arithmetic // Freiburger Intervall-Berichte. – 1986. – No. 86/9. – S. 5–19. (available at http://www.nsc.ru/interval/Library/Thematic/ILSystems/InteTolerAn.pdf
  * [15] Oettli, W., Prager, W. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides // Numerische Mathematik. – 1964. Vol. 6. – P. 405–409.
  * [16] Rohn, J. Inner solutions of linear interval systems // Interval Mathematics 1985. – Berlin, Heidelberg: Springer-Verlag, 1986. P. 157–158. – (Lecture Notes in Computer Science. Vol. 212.)
  * [17] Shary, S.P. On controlled solution set of interval algebraic systems // Interval Computations. – 1992. – No. 4 (6). – P. 66–75.
  * [18] Shary, S.P. Algebraic solutions to interval linear equations and their applications // Numerical Methods and Error Bounds. – Berlin: Akademie Verlag, 1996. (Mathematical Research, Vol. 89). – P. 224–233. (available at http://www.nsc.ru/interval/shary/Papers/Herz.pdf)
  * [19] Shary, S.P. Outer estimation of generalized solution sets to interval linear systems // Reliable Computing. – 1999. – Vol. 5, No. 3. – P. 323–335. (available at http://www.nsc.ru/interval/shary/Papers/GOuter.pdf)
  * [20] Shary, S.P. A new technique in systems analysis under interval uncertainty and ambiguity // Reliable Computing. – 2002. – Vol. 8, No. 5. – P. 321–418. (available at http://www.nsc.ru/interval/shary/Papers/ANewTech.pdf)
  * [21] Shary, S.P. Finite-Dimensional Interval Analysis. – Novosibirsk: XYZ Publishers, 2017. (in Russian)
(available at http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf)

  * [22] Vatolin, A.A. On the problems of linear programming with interval coefficients // USSR Computational Mathematics and Mathematical Physics. – 1984. – Vol. 24, Issue 6. – P. 18–23.