format: text

text:
# Testing statistical bounds on entanglement using quantum chaos

## Abstract

Previous results indicate that while chaos can lead to substantial entropy production, thereby maximizing dynamical entanglement, this still falls short of maximality. Random Matrix Theory (RMT) modeling of composite quantum systems, investigated recently, entails an universal distribution of the eigenvalues of the reduced density matrices. We demonstrate that these distributions are realized in quantized chaotic systems by using a model of two coupled and kicked tops. We derive an explicit statistical universal bound on entanglement, that is also valid for the case of unequal dimensionality of the Hilbert spaces involved, and show that this describes well the bounds observed using composite quantized chaotic systems such as coupled tops.

Recently, entanglement has been discussed extensively due to its crucial role in quantum computation and quantum information theory . Since a quantum computer is a many particle system, entanglement is inevitable and even desirable. Entanglement is important both at the hardware and software levels of a quantum computer, as the efficiency of all proposed quantum algorithms are based on it, hence its characterization as a quantum resource. The many particle nature of a quantum computer brings another phenomenon to the fore, that is chaos. Some studies have enquired whether chaos will help or hinder in the operation of a quantum computer . At a more basic level several studies have explored the connections between quantum entanglement and classical chaos , two phenomena that are prima facie uniquely quantum and classical respectively.

Such a connection between entanglement and chaos has been previously studied with the example of an $`N`$-atom Jaynes-Cummings model . It was found that the entanglement rate is considerably enhanced if the initial wave packet was placed in a chaotic region. In another work of similar kind, the authors have related such rates to classical Lyapunov exponents with the help of a coupled kicked top model . Recently, one of us studied entanglement in coupled standard maps  and found that entanglement increased with coupling strength, but after a certain magnitude of coupling strength corresponding to the emergence of complete classical chaos, the entanglement saturated. The saturation value depended on the Hilbert space dimensions and was less than its maximum possible value. This result implies that though there exists a maximum kinematical limit for entanglement, dynamically it is not possible to create it by using generic Hamiltonian evolutions on unentangled states. It should be emphasized that such bounds are statistical and are more unlikely to be violated the larger the Hilbert space dimension.

Recent related work  calculates the mean entanglement of pure states for the case $`M=N`$ by using a RMT model that allows specification of the joint probability distribution of the eigenvalues of the reduced density matrices (RDM). Below we calculate the entanglement from a eigenvalue distribution that is valid for large $`M`$ and $`N`$. We show that this distribution describes well those obtained from a coupled kicked top model. There is also some early work that calculates the subsystem entropy for random pure states . Apart from RMT simulations, we deal with an actual quantum mechanical system and relate these results to the presence of classical chaos, thus our results show in what context results such as in  can be expected to be universal.

The previous studies on entanglement, in the context of chaos, were based on pure states of bipartite systems, where the von Neumann entropy of the RDM is a natural measure of quantum entanglement. We will also initially consider pure states and point out in the end that as a simple corollary we can estimate the entanglement of formation of any density matrix as well. Suppose that the state space of a bipartite quantum system is $`=_1_2`$, where $`\text{dim}_1=N\text{dim}_2=M`$, and $`\text{dim}=d=NM`$. If $`\rho =_ip_i|\varphi _i\varphi _i|`$ is an ensemble representation of an arbitrary state in $``$, the entanglement of formation is found by minimizing $`_ip_iE(|\varphi _i)`$ over all possible ensemble realizations. Here $`E`$ is the von Neumann entropy of the RDM of the state $`|\varphi _i`$ belonging to the ensemble, i.e., its entanglement. For pure states $`|\psi `$ there is only one unique term in the ensemble representation and the entanglement of formation is simply the von Neumann entropy of the RDM.

The two RDMs of the bipartite state $`|\psi `$ are $`\rho _1=\text{Tr}_2(|\psi \psi |)`$ and $`\rho _2=\text{Tr}_1(|\psi \psi |)`$. The Schmidt decomposition of $`|\psi `$ is the optimal representation in terms of a product basis and is given by

$$|\psi =\underset{i=1}{\overset{N}{}}\sqrt{\lambda _i}|\varphi _i^{(1)}|\varphi _i^{(2)},$$
(1)
where $`0<\lambda _i1`$ are the (nonzero) eigenvalues of either RDMs and the vectors are the corresponding eigenvectors. The von Neumann entropy $`S_V`$ is the entanglement $`E(|\psi )`$ given by

$$S_V=\text{Tr}_l(\rho _l\mathrm{ln}\rho _l)=\underset{i=1}{\overset{N}{}}\lambda _i\mathrm{ln}(\lambda _i),;l=1,2.$$
(2)
Under an arbitrary unitary evolution $`\rho `$ or $`|\psi `$ evolves into states with changed entanglement. Quantum chaotic evolutions eventually create large entanglement which fluctuates around the value $`\mathrm{ln}(\gamma N)`$. The factor $`\gamma `$ depends only on the ratio $`M/N`$ and tends to unity (maximal entanglement) as $`M\mathrm{}`$. Such evolutions lead to universal properties of the RDMs, which is also shared by the RDMs of stationary states. This follows from the universal near normal distributions of the complete pure state components in any generic bases. The distribution of the eigenvalues of RDMs $`\{\lambda _i\}`$ also follows from RMT results for correlation matrices recently used in the analysis of data from financial time series . Many important universal spectral fluctuation properties of quantum chaotic systems have been modeled and explained by RMT. We extend this success to the RDMs of composite systems and consequently a description of quantum entanglement in strongly interacting systems.

As the Hilbert space dimension and chaos have roles in this bound for entanglement, coupled large spins are attractive models. A coupled kicked tops model has already been used in this context , we generalize it here to include the case of unequal spins and symmetry breaking terms. The Hamiltonian of the coupled top system used is :

$`H(t)`$ $`=`$ $`{\displaystyle \frac{\pi }{2}}J_{y_1}+{\displaystyle \frac{k}{2j_1}}(J_{z_1}+\alpha _1)^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\delta (tn)`$ (3)
$`+`$ $`{\displaystyle \frac{\pi }{2}}J_{y_2}+{\displaystyle \frac{k}{2j_2}}(J_{z_2}+\alpha _2)^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\delta (tn)`$ (4)
$`+`$ $`{\displaystyle \frac{ϵ}{\sqrt{j_1j_2}}}J_{z_1}J_{z_2}{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\delta (tn).`$ (5)
The $`J_{y_r}`$ terms describe free precession of each top and the remaining terms are due to periodic $`\delta `$-function kicks. The first two such terms are torsion about $`z`$axis and the final term describes the spin-spin coupling. When either of the constants, $`\alpha _1`$ or $`\alpha _2`$, is not zero the parity symmetry $`RH(t)R^1=H(t)`$, where $`R=\mathrm{exp}(i\pi J_{y_1})\mathrm{exp}(i\pi J_{y_2})`$, is broken. The dimensionality of the Hilbert spaces are $`N=2j_1+1`$ and $`M=2j_2+1`$. The unitary time evolution operator corresponding to this Hamiltonian is given by :

$$U_T=(U_1U_2)U_{12}^ϵ=[(U_1^fU_1^k)(U_2^fU_2^k)]U_{12}^ϵ,$$
(6)
where the different terms are given by

$`U_i^f`$ $``$ $`\mathrm{exp}\left({\displaystyle \frac{i\pi }{2}}J_{y_i}\right),U_i^k\mathrm{exp}\left({\displaystyle \frac{ik}{2j_i}}(J_{z_i}+\alpha _i)^2\right),`$ (7)
$`U_{12}^ϵ`$ $``$ $`\mathrm{exp}\left({\displaystyle \frac{iϵ}{\sqrt{j_1j_2}}}J_{z_1}J_{z_2}\right)`$ (8)
and $`i=1,2`$. There exists an antiunitary generalized time reversal symmetry, $`[\mathrm{exp}(i\pi J_{x_1})\mathrm{exp}(i\pi J_{y_1}/2)][\mathrm{exp}(i\pi J_{x_2})\mathrm{exp}(i\pi J_{y_2}/2)]K`$ where $`K`$ is complex conjugation operator, from which we can expect the applicability of results concerning the Gaussian orthogonal ensemble (GOE). We note that for the parameter values considered in this Letter, the nearest neighbor spacing distribution (NNSD) of the eigenangles of $`U_T`$ is Wigner distributed, which is typical of quantized chaotic systems with time reversal symmetry. Entanglement production of time evolving states under $`U_T`$ have been studied for two different initial states. (1) The initial state is a product of directed angular momentum states as given in Ref. , placed in the chaotic sea of phase space. This is a completely unentangled state. (2) The initial state is maximally entangled and is given by:

$$m_1,m_2|\psi (0)=\frac{1}{N}\delta _{m_1m_2}.$$
(9)
These initial states are evolved under $`U_T`$, and the results are displayed in Fig. 1. Here the coupling strength is very large compared to the value taken in , as our goal is to study entanglement saturation and strong coupling will help us achieve entanglement saturation within a short time. In the first case, initially both the von Neumann entropy and the linearized entropy ($`S_R=1\text{Tr}_1(\rho _1^2)`$), are zero, but with time evolution both entropies start

increasing and get saturated, apart from small fluctuations, at values less than their maximum possible values.

For the von Neumann entropy the saturation value is $`\mathrm{ln}(0.6N)`$ and for the linear entropy it is approximately $`12/N`$, where $`N`$ is the dimension of each subsystems. This is the dynamical bound for entanglement of a system consists of two equal dimensional subsystems, while the maximum kinematical limits are $`\mathrm{ln}N`$ and $`11/N`$ respectively. The saturation value of von Neumann entropy of this time evolved state is same as that obtained for stationary states of completely chaotic coupled standard maps . In the second case, the initial state is maximally entangled and time evolution forces this state to partially disentangle till the entropy reaches the above mentioned values.

This study shows that the saturation of entanglement is a universal phenomenon, it depends only on the Hilbert space dimensions, and not on dynamical characteristics of the system, apart from the presence of complete chaos. The effect of dimension on entanglement saturation has been studied by keeping the dimension of the first subsystem constant at $`N`$ and increasing the dimension $`M`$ of the second subspace from $`M=N`$ to some large value. Thus we may think of the second spin as tending towards a complex bath with a quasi-continuous spectrum. It is observed that the entanglement saturation increases with $`M`$ and finally gets saturated at the maximum possible

kinematical limit, as shown in Fig. 2. For example the von Neumann entropy starting from $`\mathrm{ln}(0.6N)`$ increases asymptotically to $`\mathrm{ln}N`$, while the linear entropy starting from $`12/N`$ tends to $`11/N`$.

We can develop a complete analytical understanding of these limits via RMT modeling. A typical stationary state of a quantum chaotic system shares properties of the eigenvectors of random matrices. Let us assume that some product basis has been used to write components $`a_{nm}`$ of any state, which is real for stationary states of time reversal symmetric systems. Writing $`a_{nm}`$ as the rectangular $`N\times M`$ matrix $`A`$, the $`M`$ dimensional RDM is $`A^TA`$ while the other RDM is the $`N`$ dimensional $`AA^T`$. The assumptions of quantum chaos, we have just seen, imply that $`A`$ can be taken to have random independent entries, a member of the Laguerre ensemble. The RDMs then have the structure of correlation matrices , from where we directly use results for the density of states. Such matrices have also been studied since the early days of RMT as they have a non-negative spectrum . The distribution of the eigenvalues of such matrices is known and thus this is the distribution of the eigenvalues of RDMs. The density of the eigenvalues of the RDM $`\rho _1`$ is given by

$`f(\lambda )`$ $`=`$ $`{\displaystyle \frac{NQ}{2\pi }}{\displaystyle \frac{\sqrt{(\lambda _{max}\lambda )(\lambda \lambda _{min})}}{\lambda }}`$ (10)
$`\lambda _{min}^{max}`$ $`=`$ $`{\displaystyle \frac{1}{N}}\left(1+{\displaystyle \frac{1}{Q}}\pm {\displaystyle \frac{2}{\sqrt{Q}}}\right),`$ (11)
where $`\lambda [\lambda _{min},\lambda _{max}]`$, $`Q=M/N`$ and $`Nf(\lambda )d\lambda `$ is the number of eigenvalues within $`\lambda `$ to $`\lambda +d\lambda `$. This has been derived under the assumption that both $`M`$ and $`N`$ are large. Note that this predicts a range of eigenvalues for the RDMs that are of the order of $`1/N`$. For $`Q1`$, the eigenvalues of the RDMs are bounded away from the origin, while for $`Q=1`$ there is a divergence at the origin. All of these predictions are seen to be borne out in numerical work with coupled tops.

Fig. 3 shows how well the above formula fits the eigenvalue distribution of actual reduced density matrices. This figure also shows that the probability of getting an eigenvalue outside the range $`[\lambda _{min},\lambda _{max}]`$ is indeed very small. The sum in $`S_V`$ can be replaced by an integral over the density $`f(\lambda )`$:

$$S_V_{\lambda _{min}}^{\lambda _{max}}f(\lambda )\lambda \mathrm{ln}\lambda d\lambda \mathrm{ln}(\gamma N)$$
(12)
The integral in $`\gamma `$ can be evaluated to a generalized hypergeometric function and the final result is :

$`\gamma `$ $`=`$ $`{\displaystyle \frac{Q}{Q+1}}\mathrm{exp}\left[{\displaystyle \frac{Q}{2(Q+1)^2}}{}_{3}{}^{}F_{2}^{}\{1,1,{\displaystyle \frac{3}{2}};2,3;{\displaystyle \frac{4Q}{(Q+1)^2}}\}\right]`$ (13)
When the two subsystems are of equal dimension, that is $`Q=1`$, then above expression gives $`\gamma =\mathrm{exp}(0.5)0.6`$ and so the corresponding von Neumann entropy is $`\mathrm{ln}(0.6N)`$. This is also the saturation value obtained in previous numerical work for the stationary states and time evolving states of a coupled standard map , reflecting universality. In another extreme case, when the Hilbert space dimension of the second subsystem is very large compared to that of the first, that is $`Q1`$, then $`\gamma 1`$ and hence the corresponding von Neumann entropy is $`\mathrm{ln}(N)`$. Therefore, the analytical formulation based on RMT is able to explain the saturation behaviour of the von Neumann entropy or quantum entanglement very accurately.

Fig. 2 also compares the Eq. (12) to both RMT simulations and kicked top results. We expect that the deviations of the quantum calculations are due to finite size effects. The presence of parity symmetry results in a somewhat smaller entanglement, as seen in this figure, a fact that needs further study. For time evolving states and stationary states of system without time reversal symmetry the RDMs are complex Hermitian matrices. The entanglement bounds discussed here are also valid for these cases as the entanglement depends only on the density of states of the RDMs. However, spectral fluctuations of the RDMs (such as their NNSD) corresponding to these states can be distinct. Indeed, in the correlation matrix approach to atmospheric data, such a difference has been recently noted .

The linear entropy can also be derived as above, but using direct RMT results, without taking recourse to the distribution above, is also possible in this case. Thus we may write:

$`\text{Tr}\rho ^2`$ $`=`$ $`{\displaystyle \underset{j,k=1}{\overset{N}{}}}{\displaystyle \underset{\alpha ,\beta =1}{\overset{M}{}}}a_{j\alpha }a_{k\alpha }a_{k\beta }a_{j\beta }`$ (15)
Substituting RMT ensemble average values  of $`a_{j\alpha }^2a_{j\beta }^2=a_{j\alpha }^2a_{k\alpha }^2=1/[MN(MN+2)]`$, $`a_{j\alpha }^4=3/[MN(MN+2)]`$ and $`a_{j\alpha }a_{k\alpha }a_{k\beta }a_{j\beta }=0`$, where $`jk`$ and $`\alpha \beta `$ in the above expressions, we find that:

$$S_R=1\text{Tr}\rho _1^2=1\frac{M+N+1}{MN+2}.$$
(16)
When the dimension of the two subsystems are equal, that is $`M=N`$, then in the large $`N`$ limit $`S_R12/N`$. This is the saturation value of the linear entropy approximately obtained in case of time evolving states of coupled kicked tops. Similarly, when the Hilbert space dimension of the second subsystem is very large compared to the dimension of first subsystem, that is $`MN`$, $`S_R11/N`$. This is the maximum possible value of linear entropy.

Finally as an almost trivial corollary we note that the entanglement of formation of a time evolving density matrix is also statistically bounded to $`\mathrm{ln}(\gamma N)`$, as each pure state belonging to an ensemble representation evolves to this entanglement under quantum chaos. To summarize, we have pointed out that the eigenvalue distribution of reduced density matrices of composite quantum chaotic bipartite systems are universal, and shown that there exists a typical value of quantum entanglement that quantum chaos engenders. This value is the maximum we may expect typical unentangled initial states to be able to reach under generic interactions. If we already had maximally entangled states, then chaos can disentangle this state to just such an extent as to coincide with this generic value.

We wish to thank Dr. M. S. Santhanam, Prof. V. K. B. Kota and Prof. V. B. Sheorey for useful discussions. We thank Prof. K. Zyczkowski for informing us of references  and .


text:
# Deductive Nonmonotonic Inference Operations: Antitonic Representations This work was partially supported by the Jean and Helene Alfassa fund for research in Artificial Intelligence

## 1 Introduction

A fundamental intuition of Default Reasoning (understood in the wider sense) is that a reasoner has, at its disposal, a set of facts $`X`$ (a fact is represented by a formula) and a set of defaults $`D`$ (there is no general agreement on the way the defaults ought to be represented). Given those, it draws conclusions (conclusions are formulas, as facts are) by extracting from $`D`$ and $`X`$ some set of assumptions $`A`$ (formulas again), held in the presence of $`X`$, and then accepting as plausible conclusions the set of logical consequences of the set $`XA`$. Some nonmonotonic systems are explicitly presented in this way, most notably the Closed World Assumption of Reiter’s , the system described by Poole in  (at least in its skeptical version when the set of defaults is finite), the system based on Epistemic Entrenchment , and the Rational Closure construction of . Other systems, most notably the Default Logic of  and the Circumscription of  are presented, at first, in ways that do not fit this paradigm, but they could have been presented this way: Default Logic adds to the facts the conclusions of the applicable defaults, and Circumscription adds to the facts what can be deduced from the defaults when abnormalities are minimized. In fact any system may be presented in this way by taking for $`A`$ the set of plausible conclusions from $`X`$.

In such a presentation, it seems very natural to expect that, for any fixed set of defaults $`D`$, the mapping $`𝒮`$ that sends a set of facts $`X`$ to the set of assumptions $`A=𝒮(X)`$ held in the presence of $`X`$, be antitonic (i.e., anti-monotonic, i.e., $`XY`$ implies $`𝒮(Y)𝒮(X)`$). Indeed, this is explicitly the case for the Closed World Assumption. For finite Poole systems, even those without constraints, this is not the case, though. There, given a set $`D`$ of formulas, $`𝒞(X)`$ is defined as $`𝒞n(X,_{B(X)}𝒞n(B))`$, where $`(X)`$ is the set of all subsets of $`D`$ that are consistent with $`X`$ and maximal for this property. The intersection must not be antitonic. Intuitively, antitonicity is a very natural property since $`𝒮(X)`$ is some set of default assumptions that are compatible, or consistent with $`X`$, and the larger $`X`$ is, the less compatible (with $`X`$) formulas there are. Antitonicity seems to be a necessary requirement for $`𝒮`$, at least when $`X`$ has a single extension. The purpose of this paper is to characterize those operations that may be defined by such an antitonic representation. From our characterization, will follow that many nonmonotonic systems that were not originally presented in such a way are amenable to an antitonic presentation. This point will be taken up in the conclusion. In particular finite Poole systems without constraints have an antitonic representation, even though, as explained above, their natural presentation is not antitonic.

In , S. Brass considers a property (IMD, Definition 3.13) that may seem closely related to the antitonicity of $`𝒮`$. In fact, IMD is very different from it. In our notations, IMD may be described as: if $`x𝒞(\mathrm{})`$ and $`XY`$, then if $`x`$ is in $`𝒞(Y)`$ it is also in $`𝒞(X)`$. There does not seem to be much intuitive support for such a property.

We suppose a language $``$ is given, and, with it some consequence operation $`𝒞n`$ in the sense of Tarski. The elements of $``$ will be referred to as formulas. About $`𝒞n`$, we shall assume, as customary in the literature, that $`𝒞n`$ satisfies inclusion, monotonicity, idempotency and compactness. As usual, we write $`𝒞n(X,Y)`$ instead of $`𝒞n(XY)`$, and $`XY`$ for $`Y𝒞n(X)`$. We shall assume that the language $``$ has implication. i.e., for any formulas $`a,b`$, there is a formula $`ab`$ such that, for any $`X`$, $`b𝒞n(X,a)`$ iff $`ab𝒞n(X)`$. Some of our results do not depend on this assumption, or could be proved with weaker assumptions on $``$. We shall use the following lemma from \[3, Lemma A.3\].

###### Lemma 1

1. For any set $`Y`$ and any finite set $`A`$ of formulas, there is a set $`AY`$ of formulas such that, for any set $`X`$ of formulas, $`AY𝒞n(X)`$ iff $`Y𝒞n(X,A)`$. If $`Y`$ is finite, so is $`AY`$.
2. For any $`X,Y,Z`$, $`𝒞n(X,Y)𝒞n(X,Z)=𝒞n(X,𝒞n(Y)𝒞n(Z))`$.
3. For any finite set $`A`$ of formulas and any family $`Y_i,iI`$ of sets of formulas, $`𝒞n(A,_{iI}𝒞n(Y_i))=`$ $`_{iI}𝒞n(A,Y_i)`$.

## 2 Infinitary operations

We consider infinitary operations $`𝒞:2^{}2^{}`$. We shall need to consider a host of properties for such operations. Most of them were considered in . Our terminology is slightly different, since we consider operations that are not always cumulative, or even absorbing. After the definitions, we shall compare those properties of infinitary operations with the corresponding properties of finitary consequence relations described in .

The following have to be understood for arbitrary subsets $`X`$ and $`Y`$ of $``$, and an arbitrary element $`x`$ of $``$. We shall write $`A_fX`$ if $`A`$ is a finite subset of $`X`$.

$`(\mathrm{supraclassicality})`$ $`𝒞n(X)𝒞(X)`$ (1)
$`(\mathrm{left}\mathrm{absorption})`$ $`𝒞n(𝒞(X))=𝒞(X)`$ (2)
$`(\mathrm{right}\mathrm{absorption})`$ $`𝒞n(X)=𝒞n(Y)𝒞(X)=𝒞(Y)`$ (3)
$`(\mathrm{deductivity})`$ $`YX𝒞(X)𝒞n(X,𝒞(Y))`$ (4)
$`(\mathrm{cumulativity})`$ $`Y𝒞n(𝒞(X))𝒞n(𝒞(X,Y))=𝒞n(𝒞(X))`$ (5)
$`(\mathrm{antitonicity})`$ $`XY𝒞(Y)𝒞(X)`$ (6)
$`(\mathrm{compactness})`$ $`x𝒞(X)A_x_fX`$ (7)
$`\mathrm{such}\mathrm{that}Y,\mathrm{if}A_x_fYX,\mathrm{then}x𝒞(Y)`$
$`(\mathrm{supracompactness})`$ $`x𝒞(X)A_x_fX`$ (8)
$`\mathrm{such}\mathrm{that}Y,\mathrm{if}A_x_fY𝒞(X),\mathrm{then}x𝒞(Y)`$
Supraclassicality is a consequence of Reflexivity and Right-Weakening. Left-absorption corresponds to Right-Weakening + And. Right-absorption corresponds to Left-Logical-Equivalence. The central property of this paper, Deductivity, corresponds to the (S) rule. To understand its intuitive appeal, consider the case $`X=Y\{a\}`$ ($`a`$ is an arbitrary formula). Deductivity says that, if $`x𝒞(Y,a)`$, then $`x`$ should already be in $`𝒞n(a,𝒞(Y))`$, i.e., that $`ax`$ should be in $`𝒞(Y)`$. In other words, if $`x`$ is expected to be true on the evidence “$`a`$ and $`Y`$”, then, on the evidence $`Y`$ alone, we should already expect “if $`a`$ then $`x`$”. Cumulativity corresponds to Cut + Cautious Monotonicity.

Right-absorption could have been written as $`𝒞(X)=𝒞(𝒞n(X))`$. We have chosen a formulation that generalizes without change to finitary operations. Cumulativity is also defined in a slightly more convoluted way than usual since we intend to consider cumulative operations that do not satisfy left-absorption. The definition of supracompactness is taken from . Our generalization of compactness is different both from the compactness considered in  and from supracompactnes. It is clear that any supracompact operation is compact (our meaning), and that any compact operation in our sense is compact in Freund’s sense. For monotonic operations our notion of compactness coincides with the usual one. For supraclassical, left-absorbing, cumulative operations, we shall see in Corollary 1 that compact operations are exactly the supracompact operations of Freund. Our first result characterizes those operations that have an antitonic representation of the sort we discussed in the introduction. The gist of our theorem is that, assuming supraclassicality and left-absorption, the existence of an antitonic representation is essentially equivalent to deductivity plus compacity. Since compacity is of concern only for infinitary operations, for finitary operations antitonic representations are equivalent to the (S) rule.

###### Theorem 1

Let $`𝒞`$ be an infinitary operation. The following three properties are equivalent.

1. There is an antitonic operator $`𝒮`$ such that, for any set $`X`$ of formulas, $`𝒞(X)=𝒞n(X,𝒮(X))`$,
2. for any set $`X`$,

$$𝒞(X)=𝒞n(X,\underset{YX}{}𝒞(Y)),$$
(9)
3. $`𝒞`$ is supraclassical, left-absorbing, deductive and compact.

Proof: We show, first, that 1 implies 3. Let $`𝒞(X)=𝒞n(X,𝒮(X))`$, for some antitonic $`𝒮`$. The operation $`𝒞`$ is supraclassical because $`𝒞n`$ satisfies inclusion and monotonicity. It is left-absorbing because $`𝒞n`$ is idempotent. Let us check it is deductive. Suppose $`YX`$. Then $`𝒮(X)𝒮(Y)`$, since $`𝒮`$ is antitonic, and by monotonicity of $`𝒞n`$,

$$𝒞(X)=𝒞n(X,𝒮(X))𝒞n(X,𝒮(Y))𝒞n(X,𝒞n(Y,𝒮(Y)))=𝒞n(X,𝒞(Y)).$$

Let us show it is also compact. Suppose $`x𝒞(X)`$. By the compactness of $`𝒞n`$, there is a finite set $`B_x_fX𝒮(X)`$ such that $`x𝒞n(B_x`$. Let $`A_x\stackrel{\mathrm{def}}{=}B_xX`$. We have $`A_x_fX`$, and, by monotonicity of $`𝒞n`$,

$$𝒞n(B_x)=𝒞n(A_x,B_x𝒮(X))𝒞n(A_x,𝒮(X)),$$

and $`x𝒞n(A_x,𝒮(X))`$. If $`A_x_fYX`$, then $`x𝒞n(Y,𝒮(Y))`$ by monotonicity of $`𝒞n`$ and antitonicity of $`𝒮`$.

We now show that 3 implies 2. Suppose $`𝒞`$ is supraclassical, left-absorbing, deductive and compact. Since, $`_{YX}𝒞(Y)𝒞(X)`$ and $`𝒞`$ is supraclassical and left-absorbing, we see easily that

$$𝒞n(X,\underset{YX}{}𝒞(Y))𝒞(X).$$

Suppose, now, that $`x𝒞(X)`$. Since $`𝒞`$ is compact, there is a finite set $`A_fX`$, such that $`x𝒞(Y)`$, for any $`Y`$, $`A_fYX`$. In other terms, $`x𝒞(A,Y)`$, for any $`YX`$. Since $`𝒞`$ is deductive

$$x\underset{YX}{}𝒞n(A,Y,𝒞(Y))=\underset{YX}{}𝒞n(A,𝒞(Y)).$$

By Lemma 1, part 3,

$$x𝒞n(A,\underset{YX}{}𝒞(Y))𝒞n(X,\underset{YX}{}𝒞(Y)).$$

The fact that 2 implies 1 is obvious since $`𝒮(X)\stackrel{\mathrm{def}}{=}_{YX}𝒞(Y)`$ is antitonic.

It is clear that there are supraclassical, left-absorbing deductive operations that are not compact. Consider for example the operation $`𝒞`$ defined by $`𝒞(X)=𝒞n(X,a)`$ if $`X`$ is infinite and $`𝒞(X)=𝒞n(X)`$ otherwise. The antitonic operator that appears in Equation (9), i.e. $`_{YX}𝒞(Y)`$, is the largest antitonic operator that represents $`𝒞`$, as will be explained now.

###### Lemma 2

If, for some antitonic $`𝒮`$, for any $`X`$, $`𝒞(X)=𝒞n(X,𝒮(X))`$ then, $`𝒮(X)_{YX}𝒞(Y)`$.

Proof: Let $`Y`$ be an arbitrary subset of $`X`$. We have, since $`𝒮`$ is antitonic,

$$𝒮(X)𝒮(Y)𝒞n(Y,𝒮(Y))=𝒞(Y).$$

Our next result extends Theorem 1 to right-absorbing operations. In  the intersection of Equation 10 was called the trace of $`X`$.

###### Theorem 2

Let $`𝒞`$ be an infinitary operation. The following three properties are equivalent.

1. There is an antitonic right-absorbing operator $`𝒮`$ such that, for any set $`X`$ of formulas, $`𝒞(X)=𝒞n(X,𝒮(X))`$,
2. for any set $`X`$,

$$𝒞(X)=𝒞n(X,\underset{XY}{}𝒞(Y)),$$
(10)
3. $`𝒞`$ is supraclassical, left-absorbing, right-absorbing, deductive and compact.

Proof: Let us show, first, that 1 implies 3. This is clear from Theorem 1 and the fact that, if $`𝒮`$ is right-absorbing, so is $`𝒞n(X,𝒮(X))`$. We now show that 3 implies 2. From right-absorption of $`𝒞`$ and Theorem 1, we have

$$𝒞(X)=𝒞(𝒞n(X))=𝒞n(𝒞n(X),\underset{XY}{}𝒞(Y))$$

and we conclude easily. The last leg of the proof is obvious since

$$𝒮(X)\stackrel{\mathrm{def}}{=}\underset{XY}{}𝒞(Y)$$

is antitonic and right-absorbing.

Notice that we do not claim that, for a right-absorbing $`𝒞`$ the intersections appearing in Equations (9) and (10) are equal. The following example will show it need not be the case. Consider the propositional calculus on two variables $`p`$ and $`q`$, and let $`𝒞n`$ be logical consequence. Define $`𝒮(X)`$ as $`𝒞n(p)`$ if $`𝒞n(X)=𝒞n(\mathrm{})`$ and $`\mathrm{}`$ otherwise. The operator $`𝒮`$ is obviously antitonic and right-absorbing. If $`𝒞(X)\stackrel{\mathrm{def}}{=}𝒞n(X,𝒮(X))`$ one sees that $`p`$ is an element of $`𝒞(\mathrm{})`$ and of $`𝒞(p)`$, but not an element of $`𝒞(qp)`$. Therefore $`p_{Y\{p\}}𝒞(Y)`$ but $`p_{pY}𝒞(Y)`$. Similarly, to what we have shown in Lemma 2, the antitonic operation, $`_{XY}𝒞(Y)`$ is the largest right-absorbing antitonic representation of $`𝒞`$.

###### Lemma 3

If $`𝒞(X)=𝒞n(X,𝒮(X))`$ for some antitonic right-absorbing $`𝒮`$, then, $`𝒮(X)_{XY}𝒞(Y)`$

Proof: Let $`Y`$ be an arbitrary subset of $`𝒞n(X)`$. We have, since $`𝒮`$ is right-absorbing and antitonic,

$$𝒮(X)=𝒮(𝒞n(X))𝒮(Y)𝒞n(Y,𝒮(Y))=𝒞(Y).$$

We deal now with cumulative operations. Our first result is important in itself and will be used in the proof of our third characterization result. Notice, first, that any supraclassical, left-absorbing cumulative operation is right-absorbing, since $`𝒞n(X)𝒞(X)`$ implies $`𝒞n(𝒞(X,𝒞n(X))=𝒞n(𝒞(X))`$ and therefore $`𝒞(𝒞n(X))=𝒞(X)`$.

###### Theorem 3

If $`𝒞`$ is supraclassical, left-absorbing, deductive and cumulative, then

$$\underset{Y𝒞n(X)}{}𝒞(Y)=\underset{Y𝒞(X)}{}𝒞(Y).$$
(11)
Proof: Since $`𝒞`$ is supraclassical, the right-hand side is obviously a subset of the left-hand side. We must show that, for any $`Z𝒞(X)`$,

$$\underset{Y𝒞n(X)}{}𝒞(Y)𝒞(Z).$$

But, since $`𝒞n(X)𝒞n(Z)𝒞n(X)`$, $`_{Y𝒞n(X)}𝒞(Y)𝒞(𝒞n(X)𝒞n(Z))`$, and it is enough to show that $`𝒞(𝒞n(X)𝒞n(Z))𝒞(Z)`$. We notice that, since $`𝒞`$ is left-absorbing and supraclassical, $`𝒞n(X)𝒞n(Z)𝒞(X)`$. But $`𝒞`$ is left-absorbing and cumulative and we conclude that $`𝒞(X)=𝒞(X,𝒞n(X)𝒞n(Z))`$ and therefore $`Z𝒞(X,𝒞n(X)𝒞n(Z))`$. But $`𝒞`$ is deductive and

$$𝒞(X,𝒞n(X)𝒞n(Z))𝒞n(X,𝒞n(X)𝒞n(Z),𝒞(𝒞n(X)𝒞n(Z)))$$

and we conclude that $`Z𝒞n(X,𝒞(𝒞n(X)𝒞n(Z)))`$. But, obviously,

$$Z𝒞n(Z,𝒞(𝒞n(X)𝒞n(Z))).$$

By Lemma 1, part 2,

$$𝒞n(X,𝒞(𝒞n(X)𝒞n(Z)))𝒞n(Z,𝒞(𝒞n(X)𝒞n(Z)))$$

$$=𝒞n(XZ,𝒞(𝒞n(X)𝒞n(Z)))=𝒞(𝒞n(X)𝒞n(Z)).$$

The last equality follows from supraclassicality and left-absorption. We conclude that $`Z𝒞(𝒞n(X)𝒞n(Z))`$. By the cumulativity of $`𝒞`$, we have $`𝒞(𝒞n(X)𝒞n(Z))=𝒞(𝒞n(X)𝒞n(Z),Z)`$. But $`𝒞n(𝒞n(X)𝒞n(Z),Z)=𝒞n(Z)`$ and, since $`𝒞`$ is right-absorbing by a remark above, $`𝒞(𝒞n(X)𝒞n(Z))=𝒞(Z)`$.

We may now prove our third characterization theorem.

###### Theorem 4

Let $`𝒞`$ be an infinitary operation. The following three properties are equivalent.

1. There is an antitonic, right-absorbing and cumulative operator $`𝒮`$ such that, for any set $`X`$ of formulas, $`𝒞(X)=𝒞n(X,𝒮(X))`$,
2. for any set $`X`$,

$$𝒞(X)=𝒞n(X,\underset{Y𝒞(X)}{}𝒞(Y)),$$
(12)
3. $`𝒞`$ is supraclassical, left-absorbing, deductive, cumulative and compact.

Proof: Let us show, first, that 1 implies 3. Let $`𝒞`$ be as in 1. By Theorem 2, we only need to show that $`𝒞`$ is cumulative. Suppose, therefore, that we have $`Y𝒞n(𝒞(X))=𝒞n(X,𝒮(X))`$. One of the inclusions we have to prove (the one corresponding to Cut) is a consequence of the deductivity of $`𝒞`$ (using $`XXY`$) and does not require the cumulativity of $`𝒮`$. Indeed $`𝒞(X,Y)𝒞n(X,Y,𝒞(X))`$ by the deductivity of $`𝒞`$. Since both $`X`$ and $`Y`$ are subsets of $`𝒞(X)`$ and $`𝒞`$ is left-absorbing, we conclude that $`𝒞(X,Y)𝒞(X)`$. The converse inclusion will be proved now. Since $`Y𝒞n(X,𝒮(X))`$, for any $`yY`$, there exists a finite $`A_y_fX`$ such that $`y𝒞n(A_y,𝒮(X))`$. We may apply part 1 of Lemma 1, and consider the set $`W\stackrel{\mathrm{def}}{=}\{A_yyyY\}𝒞n(𝒮(X))`$. But $`𝒮`$ is cumulative and therefore, $`𝒞n(𝒮(X))=𝒞n(𝒮(X,W))`$. One easily sees that $`𝒞n(X,W)=𝒞n(X,Y)`$, and, since $`𝒮`$ is right-absorbing, we have $`𝒞n(𝒮(X))=𝒞n(𝒮(X,Y))`$. Therefore

$$𝒞(X)=𝒞n(X,𝒮(X))=𝒞n(X,𝒮(X,Y))𝒞n(X,Y,𝒮(X,Y))=𝒞(X,Y).$$

Let us show now that 3 implies 2. Suppose $`𝒞`$ is supraclassical, left-absorbing, deductive, cumulative and compact. As we noticed above, any supraclassical, left-absorbing and cumulative operation is right-absorbing. We may use Theorem 2 to see that Equation 10 holds, and conclude by Theorem 3. Finally, let us show that 2 implies 1. Suppose $`𝒞`$ satisfies Equation 12. We shall show that $`𝒮(X)\stackrel{\mathrm{def}}{=}_{Y𝒞(X)}𝒞(Y)`$ is antitonic, right-absorbing and cumulative. None of those properties is obvious. One immediately sees that $`𝒞`$ is supraclassical and left-absorbing. One easily sees that $`𝒞`$ is deductive. Indeed, suppose $`YX`$, by supraclassicality we have $`Y𝒞(X)`$ and therefore $`𝒮(X)𝒞(Y)`$. We conclude that $`𝒞(X)=𝒞n(X,𝒮(X))𝒞n(X,𝒞(Y))`$. The crux of the proof is to show that $`𝒞`$ is cumulative. Let $`Z𝒞(X)`$ (remember $`𝒞`$ is left-absorbing). Since $`𝒞`$ is deductive, we have $`𝒞(X,Z)𝒞n(Z,𝒞(X))=𝒞(X)`$. But, in turn, this implies $`𝒮(X)𝒮(X,Z)`$, and

$$𝒞(X)=𝒞n(X,𝒮(X))𝒞n(X,Z,𝒮(X,Z))=𝒞(X,Z).$$

We have shown that $`𝒞`$ is supraclassical, left-absorbing, deductive and cumulative. By Theorem 3, we conclude that $`𝒮(X)=_{XY}𝒞(Y)`$ and we conclude that $`𝒮`$ is antitonic and right-absorbing. The only thing left to prove is that $`𝒮`$ is cumulative. Suppose $`Z𝒞n(𝒮(X))`$. We see that $`Z𝒞(X)`$, and, since $`𝒞`$ is cumulative, we have $`𝒞(X)=𝒞(X,Z)`$. We conclude that $`𝒮(X)=𝒮(X,Z)`$.

The following corollary will make completely clear the relation between compacity and supracompacity.

###### Corollary 1

Let $`𝒞`$ be supraclassical, left-absorbing, deductive and cumulative. It is supracompact iff it is compact.

Proof: The only if part is obvious from the supraclassicality of $`𝒞`$ and the definitions. For the if part, by Theorem 4, Equation 12 holds. Supracompacity follows easily.

## 3 Finitary deductive operations

We shall denote the set of all finite subsets of $`X`$ by $`𝒫_f(X)`$. We shall now consider finitary operations $`:𝒫_f()2^{}`$. The properties of supraclassicality, left-absorption, right-absorption, deductivity, antitonicity and cumulativity for finitary operations are defined exactly as for infinitary operations, after replacing arbitrary sets $`X`$ and $`Y`$ by finite sets $`A`$ and $`B`$. Notice that right-absorption cannot be expressed as $`(A)=(𝒞n(A))`$ since $`𝒞n(A)`$ need not be finite. The best way to study finitary operations is to extend them to infinitary operations and use the representation theorems we have developed in the previous section. We shall see that there is a canonical way to extend finitary operations. But, before we can do that, we must prove one technical result concerning finitary operations. Its proof is the corresponding part of the proof of Theorem 1, after replacing arbitrary sets by finite sets wherever needed.

###### Lemma 4

Let $``$ be a supraclassical, left-absorbing and deductive finitary operation. Then, for any finite $`A_f`$, $`(A)=𝒞n(A,_{BA}(B))`$.

In the next section we shall deal with the question of extending finitary operations.

## 4 Co-compactness

Our notion of compactness is not really satisfying, since it does not seem to be the right generalization of the notion of compactness (for monotonic operations) since any finitary monotonic operation has a unique compact monotonic extension, but compact extensions of nonmonotonic operations are not unique. If we restrict our attention to supraclassical, left-absorbing, deductive and compact operations the new notion we need seems to be the following.

###### Definition 1

An operation $`𝒞`$ is said to be strongly co-compact iff, for any $`X`$ and for any $`x`$, if $`x𝒞(X)`$, then there is a finite $`A_fX`$ such that $`x𝒞(A)`$.

The following is obvious.

###### Lemma 5

If $`𝒮`$ is antitonic, it is strongly co-compact iff $`𝒮(X)=_{A_fX}𝒮(A)`$.

Not all operations represented by antitonic operators are strongly co-compact, as may be seen from the following counter-example. Consider a propositional calculus on an infinite set of propositional variables, and let $`𝒞n`$ be logical consequence. Let $`a`$ a proposition that is not a tautology. Define, for any finite set $`B`$, $`𝒮(B)\stackrel{\mathrm{def}}{=}𝒞n(\{\chi _Ba\})`$, where $`\chi _B`$ is the conjunction of all elements of $`B`$. For infinite $`X`$, $`𝒮(X)\stackrel{\mathrm{def}}{=}_{B_fX}𝒮(B)`$. It is easy to see that $`a𝒞(B)=𝒞n(B,𝒮(B))`$, for any finite set $`B_f`$. Let $`X`$ be any infinite set of propositional variables that do not appear in $`a`$. One may see that $`_{B_fX}𝒮(B)`$ is equal to $`𝒞n(\mathrm{})`$, and therefore $`𝒞(X)=𝒞n(X)`$. We conclude that $`a𝒞(X)`$, even though $`a𝒞(A)`$ for any finite subset $`A`$ of $`X`$. Many operations represented by antitonic operations are strongly co-compact, though.

###### Theorem 5

If $`𝒞(X)=𝒞n(X,𝒮(X))`$ for some antitonic and strongly co-compact $`𝒮`$, and if $`𝒮(\mathrm{})`$ is finite, then $`𝒞`$ is strongly co-compact.

Proof: Since $`𝒮`$ is antitonic and strongly co-compact, we have $`𝒞(X)=𝒞n(X,_{B_fX}𝒮(B))`$. Since, for any $`Y`$, $`𝒮(Y)𝒮(\mathrm{})`$ and this last set is finite, the intersection above is a finite intersection. By Lemma 1, part 2, $`𝒞(X)=_{B_fX}𝒞n(X,𝒮(B))`$. Suppose $`x𝒞(X)`$. There is a finite set $`B_fX`$, such that $`x𝒞n(X,𝒮(B))`$. Clearly, $`x𝒞n(B,𝒮(B))=𝒞(B)`$.

Our next result shows that compactness and strong co-compactness together play the role of a generalization of the notion of compactness.

###### Theorem 6

Let $``$ be a finitary supraclassical, left-absorbing, deductive operation. It has a unique supraclassical, left-absorbing, deductive, compact and strongly co-compact extension.

Proof: Suppose $``$ is a finitary supraclassical, left-absorbing, deductive operation. We shall prove uniqueness of the extension first. Suppose that $`𝒞`$ is an infinitary supraclassical, left-absorbing, deductive, compact and strongly co-compact extension of $``$. By Theorem 1, $`𝒞(X)=𝒞n(X,_{YX}𝒞(Y))`$. But $`𝒞`$ is strongly co-compact, and

$$\underset{YX}{}𝒞(Y)=\underset{B_fX}{}𝒞(B).$$

We conclude that

$$𝒞(X)=𝒞n(X,\underset{B_fX}{}(B)).$$
(13)
But Equation (13) uniquely defines $`𝒞`$ in terms of $``$.

To prove existence, we shall show that Equation (13) provides an extension of $``$ with all the required properties. Lemma 4 shows that it is indeed an extension of $``$. We notice that Equation (13) provides an antitonic representation of $`𝒞`$ and therefore Theorem 1 enables us to conclude that $`𝒞`$ is supraclassical, left-absorbing, deductive and compact. It is left to us to show that $`𝒞`$ is strongly co-compact. But this follows clearly from Equation (13) since $`_{B_fX}(B)𝒞(X)`$.

###### Corollary 2

If $``$ is supraclassical, left-absorbing and deductive, its unique supraclassical, left-absorbing, deductive, compact and strongly co-compact extension is given by $`x𝒞(X)`$ iff there is a finite $`A_x_fX`$ such that $`x(A_x,B)`$ for any finite $`B_fX`$.

Proof: Let $`𝒞^{}`$ be the unique extension of $``$ provided by Equation (13). One easily checks that $`𝒞`$ is also an extension of $``$, and, since $`𝒞^{}`$ is compact, we have $`𝒞^{}(X)𝒞(X)`$. Suppose now that $`x𝒞(X)`$. We have $`x_{B_fX}(A_x,B)`$. Since $``$ is deductive, by Lemma 1 and Equation (13),

$$x\underset{B_fX}{}𝒞n(A_x,B,(B))=\underset{B_fX}{}𝒞n(A_x,(B))=𝒞n(A_x,\underset{B_fX}{}(B))$$

$$𝒞n(X,\underset{B_fX}{}(B))=𝒞^{}(X).$$

## 5 Right-absorbing operations

We shall now deal with extending right-absorbing finitary operations. It turns out that we cannot prove that any supraclassical, left-absorbing, right-absorbing and deductive finitary operation has a supraclassical, left-absorbing, right-absorbing, deductive, compact and strongly co-compact extension. We, therefore, need a weaker notion of co-compactness.

###### Definition 2

An operation $`𝒞`$ is said to be co-compact iff, for any $`X`$ and for any $`x`$, if $`x𝒞(X)`$, then there is a finite set $`A`$, such that $`XA`$ and $`x𝒞(A)`$.

Clearly, any strongly co-compact operation is co-compact. We also have the following, the proof of which is obvious.

###### Lemma 6

If $`𝒞`$ is strongly co-compact, then the operation $`𝒞^{}`$ defined by $`𝒞^{}(X)=𝒞(𝒞n(X))`$ is co-compact.

We may now prove our result concerning right-absorbing operations.

###### Theorem 7

Any supraclassical, left-absorbing, right-absorbing and deductive finitary operation $``$ has a unique extension that is supraclassical, left-absorbing, right-absorbing, deductive, compact and co-compact.

Proof: Let $`𝒞`$ be the unique supraclassical, left-absorbing, deductive, compact and strongly co-compact extension of $``$ defined by Equation (13). Consider $`𝒞^{}`$ defined by $`𝒞^{}(X)=𝒞(𝒞n(X))`$. The operation $`𝒞^{}`$ is easily seen to be supraclassical, left-absorbing, right-absorbing, deductive and compact. By Lemma 6, it is also co-compact. By Corollary 2, $`x𝒞^{}(X)`$ iff there is a finite $`A_x_f𝒞n(X)`$ such that $`x(A_x,B)`$ for any finite $`B_f𝒞n(X)`$. This shows immediately that $`𝒞^{}`$ is an extension of $``$. We have proved existence.

For uniqueness notice that, if $`𝒞`$ has the properties required, we have $`𝒞(X)=𝒞n(X,_{XY}𝒞(Y))`$, by Theorem 2. But, if $`𝒞`$ is a co-compact extension of $``$, $`_{XY}𝒞(Y)=_{B_f𝒞n(X)}𝒞(B)`$.

The extension of Theorem 7 is characterized in the following way.

###### Corollary 3

If $``$ is supraclassical, left-absorbing, right-absorbing and deductive, its unique supraclassical, left-absorbing, right-absorbing, deductive, compact and co-compact extension is given by $`x𝒞(X)`$ iff there is a finite $`A_x_fX`$ such that $`x(A_x,B)`$ for any finite $`B_f𝒞n(X)`$.

Proof: In the proof of Theorem 7 we have seen this extension is $`𝒞(𝒞n(X))`$ for the extension $`𝒞`$ that is described in Corollary 2. Therefore $`x𝒞(X)`$ iff there is a finite $`A_x_f𝒞n(X)`$ such that $`x(A_x,B)`$ for any finite $`B_f𝒞n(X)`$. But if $`A_x_f𝒞n(X)`$, there is a finite $`A_x^{}_fX`$ such that $`A_x^{}A_x`$, and therefore $`(A_x^{},B)=(A_x^{},A_x,B)`$ by right-absorption.

Corollary 3 shows that the unique extension of $``$ is the operation denoted $`𝒞_{}`$ in  (the only case considered there was the case of a cumulative $``$). Our next result deals with cumulative operations.

###### Theorem 8

The unique supraclassical, left-absorbing, right-absorbing, deductive, compact and co-compact extension $`𝒞`$ of a supraclassical, left-absorbing, right-absorbing, deductive and cumulative finitary operation $``$ is cumulative.

Proof: We have seen in the proof of Theorem 7 that this unique extension is defined by $`𝒞(X)=𝒞n(X,_{XB}(B))`$. By the first leg of Theorem 4, all we have to show is that $`𝒮(X)\stackrel{\mathrm{def}}{=}_{XB}(B)`$ is cumulative. We immediately see that $`𝒮`$ is antitonic. Since $``$ is left-absorbing, so is $`𝒮`$. Suppose, then, that $`Y𝒮(X)`$. We must show that $`𝒮(X)=𝒮(X,Y)`$. By antitonicity of $`𝒮`$, we immediately see that $`𝒮(X,Y)𝒮(X)`$. We shall show that $`𝒮(X)𝒮(X,Y)`$. Let $`A`$ be an arbitrary finite set such that $`X,YA`$, we shall show that $`𝒮(X)(A)`$. Since $`X,YA`$, for any $`aA`$, there is a finite $`Y_a_fY`$, such that $`XY_aa`$. In fact, $`Y_aa`$ is a singleton. Let $`B\stackrel{\mathrm{def}}{=}_{aA}Y_aa`$. The set $`B`$ is finite. Notice that $`AB`$ and $`B,YA`$. There is therefore a finite subset $`C`$ of $`Y`$ such that $`B,CA`$. We see that $`𝒞n(B,C)=𝒞n(A,C)`$. Since $`XB`$, we have, by the definition of $`𝒮`$, $`𝒮(X)(B)`$. It will be enough to prove that $`(B)=(A)`$. But, indeed, $`C_fY𝒮(X)(B)`$ and by the cumulativity of $``$, $`(B)=(B,C)`$. By right-absorption $`(B,C)=(A,C)`$. We conclude that $`A_f(B)`$, and, by cumulativity of $``$, $`(B)=(B,A)`$, but $`𝒞n(B,A)=𝒞n(A)`$, and we conclude that $`(B)=(A)`$.

Theorem 8 represents an improvement on Theorem 7.9 of , in which the language $``$ was assumed to have a disjunction. There, it was shown that, under the additional assumption that the language $``$ has a disjunction, the “canonical” extension of a supraclassical, left-absorbing, right-absorbing, deductive and cumulative finitary operation $``$ is the $`𝒞_{}`$ described in Corollary 3, and is supraclassical, left-absorbing, right-absorbing, deductive and cumulative. This operation $`𝒞_{}`$ is, trivially, compact and co-compact.

## 6 Conclusion, open problems and acknowledgments

In our introduction we mentioned a number of nonmonotonic systems. We may now try to tell which ones have antitonic representations. As mentioned in the introduction, the Closed World Assumption of  is explicitly presented by an antitonic representation. Minker’s  Generalized Closed world Assumption, on the contrary, does not have any such representation since the inference operation it defines does not satisfy Deductivity. Indeed from the assumptions $`\{p,pq\}`$, GCWA will conclude $`\neg q`$, but from $`pq`$ it will not conclude $`p\neg q`$. Notice that, equivalently, GCWA does not satisfy Or since it will conclude $`\neg q`$ from $`p`$ and conclude $`\neg p`$ from $`q`$, but will not conclude $`\neg p\neg q`$ from $`pq`$.

Default Logic  is a bit more problematic to study since it does not explicitly defines an inference operation. If we take the reasonable, skeptical approach to this definition, we see that, even when only normal defaults are considered, it lacks an antitonic representation, since its inference operation is not deductive (or does not satisfy Or). The example given above for GCWA translates immediately in normal default logic. It is all the more remarkable that, if we restrict ourselves to finite sets of normal defaults without prerequisites, the skeptical inference operation defined is deductive and admits an antitonic representation. Indeed, normal defaults without prerequisites are equivalent to Poole systems without constraints. In , Theorems 7.17 and previous theorems, it was shown that, if the language $``$ has a contradiction (i.e. if any inconsistent set has a finite subset that is inconsistent), the inference operation defined by any finite Poole system without constraints satisfies the conditions of Theorem 4, part 3. For Circumscription, since the inference operation defined by Circumscription may be defined by some preferential model, it is clearly supraclassical, right-absorbing, left-absorbing and deductive. When the so-called well-foundedness assumption is satisfied, it is also cumulative. If the language is logically finite, it is also, obviously, compact and therefore has an antitonic representation by Theorem 4. We do not know yet whether it is compact even when the language is infinite. It follows from  Section 5.8 that, when the knowledge base is admissible, rational closure has an antitonic representation.

We want to thank Michael Freund for helping us to show that cumulative compact operations are supracompact and David Makinson, Michael Freund and three anonymous referees for their remarks on a draft of this paper.