Yves Coudi Ère
email: yves.coudiere@univ-nantes.fr

Florence Hubert
email: florence.hubert@cmi.univ-mrs.fr

A 3D DISCRETE DUALITY FINITE VOLUME METHOD FOR NONLINEAR ELLIPTIC EQUATIONS *

Keywords: Finite-volume methods, Error estimates, Leray-Lions operators. AMS subject classifications. 35J65, 65N15, 74S10

Discrete Duality Finite Volume (DDFV) schemes have recently been developed in 2D to approximate nonlinear diffusion problems on general meshes. In this paper, a 3D extension of these schemes is proposed. The construction of this extension is detailed and its main properties are proved: a priori bounds, well-posedness and error estimates. The practical implementation of this scheme is easy. Numerical experiments are presented to illustrate its good behavior.

Introduction.

1.1. Nonlinear elliptic equations. In this paper, we are interested in the study of a finite volume approximation of solutions to the nonlinear diffusion problem:

div (ϕ(z, ∇u(z))) = f (z), in Ω, u = g, on ∂Ω, (

where Ω is a bounded polyhedral domain in R 3 . Consider p ≥ 2 and p ′ = p p-1 . The flux ϕ : Ω × R 3 → R 3 in equation (1.1) is supposed to be a Caratheodory function which is strictly monotonic with respect to ξ ∈ R 3 : (ϕ(z, ξ)ϕ(z, η)) • (ξη) > 0, for all ξ = η, for a.e. z ∈ Ω .

(

We also assume that there exist c These assumptions ensure that u →div(ϕ( • , ∇u)) is a Leray-Lions operator, and in particular (see [START_REF] Leray | Quelques résultats de visik sur les problèmes elliptiques non linéaires par les méthodes de minty-browder[END_REF]) the mapping G ∈ (L p (Ω)) 3 → ϕ(•, G(•)) ∈ (L p ′ (Ω)) 3 is continuous.

(1.5) Furthermore, Leray and Lions [START_REF] Leray | Quelques résultats de visik sur les problèmes elliptiques non linéaires par les méthodes de minty-browder[END_REF] proved that Theorem 1.1. Under assumptions (1.2), (1.3) and (1.4), for any source term f ∈ W -1,p ′ (Ω) and boundary data g ∈ W 1-1/p,p (∂Ω), the problem (1.1) has a unique solution u ∈ W 1,p (Ω).

For sake of simplicity, the numerical method is described in details in the more regular context f ∈ L p ′ (Ω) and g continuous on ∂Ω. The possible extension to the general case g ∈ W 1-1/p,p ′ (Ω) and f ∈ W -1,p ′ (Ω) is briefly explained in section 5. The computation of the final error estimates requires the additional regularity u ∈ W 2,p (Ω). In view of the Sobolev's injections on Ω in dimension d = 3 (see [START_REF] Adams | Sobolev spaces[END_REF]), since p ≥ 2 > d/2 (and then 1 p -1 d < 1 d ), the following continuous embeddings hold true

W 2,p (Ω) ⊂ W 1,q (Ω) ⊂ C 0 ( Ω) if 1 p - 1 d < 1 q < 1 d . (1.6)
In this case, the boundary data is supposed to be g = γ 0 (ḡ) where ḡ is in W 2,p (Ω) ⊂ C 0 ( Ω).

The scheme could still be analyzed in the general case, and its numerical properties be essentially preserved, although their proofs require much technical work, see for instance [START_REF] Andreianov | Discrete duality finite volume schemes for Leray-Lions type elliptic problems on general 2D-meshes[END_REF].

1.2. The discrete duality finite volume approaches in 3D. Given a finite volume mesh, the 2D DDFV method relies on the diamond formula [START_REF] Coudière | Convergence rate of a finite volume scheme for a two dimensional convection-diffusion problem[END_REF] to compute gradients of the unknown u from finite differences in two independent directions, involving values of u at the centers and at the vertices of the control volumes (see [START_REF] Hermeline | A finite volume method for the approximation of diffusion operators on distorted meshes[END_REF][START_REF] Domelevo | A finite volume method for the Laplace equation on almost arbitrary two-dimensional grids[END_REF][START_REF] Andreianov | Discrete duality finite volume schemes for Leray-Lions type elliptic problems on general 2D-meshes[END_REF]). Hence, the DDFV strategy consists in building two finite volume meshes, namely the cell-centered given mesh and a vertex centered one. In 2D, there is a geometric duality relationship such that the interfaces between control volumes of each of these two meshes can be gathered by pairs. These pairs of edges define the so-called diamond cells, on which the gradient vectors are computed. The diamond cells are quadrilateral as shown on figure 1.1(a).

Considering 3D extensions, three different methods have been proposed up to now in the linear case ϕ(z, ξ) = K(z)ξ (K(z) a symmetric uniformly elliptic matrix). In these proposals, the additional mesh of control volumes is built around the vertices of the primal mesh (figures 1.1(c) and 1.1(d)) and the diamond cells are as shown on figure 1.1(b). The gradient is approximated by finite differences on the diamond cells and the scheme is obtained by integrating eq. (1.1) on both the primal and dual control volumes. In [START_REF] Coudière | A 2d/3d discrete duality finite volume scheme. application to ecg simulation[END_REF][START_REF] Pierre | Modélisation et simulation de l'activité électrique du coeur dans le thorax, analyse numérique et méthodes de volumes finis[END_REF][START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF][START_REF] Hermeline | A finite volume method for approximating 3d diffusion operators on general meshes[END_REF], each diamond cell is composed of a pair of pyramids having [START_REF] Coudière | A 2d/3d discrete duality finite volume scheme. application to ecg simulation[END_REF][START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF].

x l x k x a x b • • (a) 2D situation. x k x l • • x a x b x c (b) 3D diamond from
x a (c) 3D node control volume from [START_REF] Coudière | A 2d/3d discrete duality finite volume scheme. application to ecg simulation[END_REF][START_REF] Pierre | Modélisation et simulation de l'activité électrique du coeur dans le thorax, analyse numérique et méthodes de volumes finis[END_REF].

x a (d) 3D node control volume from [START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF][START_REF] Hermeline | A finite volume method for approximating 3d diffusion operators on general meshes[END_REF]. as base an interface of the primal mesh and vertices the two neighboring centers (see figure 1.1(b)). In [START_REF] Coudière | A 2d/3d discrete duality finite volume scheme. application to ecg simulation[END_REF][START_REF] Pierre | Modélisation et simulation de l'activité électrique du coeur dans le thorax, analyse numérique et méthodes de volumes finis[END_REF] a 3D gradient is built from the vertex values of each diamond cell under the condition that the interfaces of the primal mesh are either triangles or quadrangles. This includes locally refined meshes. The construction in [START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF][START_REF] Hermeline | A finite volume method for approximating 3d diffusion operators on general meshes[END_REF] allows more general meshes. The construction of the dual control volumes is specific to each method. Extension to discontinuous permeability has been proposed in [START_REF] Hermeline | A finite volume method for approximating 3d diffusion operators on general meshes[END_REF].

Unlike in the 2D version, the primal and the dual meshes play a different role: in [START_REF] Pierre | Modélisation et simulation de l'activité électrique du coeur dans le thorax, analyse numérique et méthodes de volumes finis[END_REF] the domain Ω is recovered twice by the dual mesh and in [START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF] the orthogonality condition means that the dual mesh is the Voronoïmesh associated to the vertices of the primal mesh. In reference [START_REF] Hermeline | Approximation of 2-d and 3-d diffusion operators with variable full tensor coefficients on arbitrary meshes[END_REF], diamond cells are constructed in a different way:

x d x k x l • • x a x b x f x e Figure 1.2. View of a diamond cell.
choosing a point in each face of the mesh, the diamond cell is made of two tetrahedral cells that have a common triangular base with vertices the endpoints of one edge of the face and the center of the face; and the two neighboring centers as additional vertices, see figure 1.2. Two auxiliary unknowns, at the centers of the face and of the edge, are introduced to reconstruct the 3D gradient. With this two additional points, the diamond cell now has 6 vertices, defining 3 independent directions: between the two new points, between the two neighboring centers and between the two endpoints of the edge. It can be constructed a gradient from the 3 finite differences in these directions. But it remains the auxiliary unknowns to eliminate. F. Hermeline suggests several possibilities to eliminate them. The derived schemes are in general non symmetric.

Their convergence seems to be difficult to prove. In any case, three finite differences in independent directions are needed to construct a 3D gradient. The diamond mesh constructed in [START_REF] Hermeline | Approximation of 2-d and 3-d diffusion operators with variable full tensor coefficients on arbitrary meshes[END_REF] gives naturally these three independent directions. According to our method, the additional unknowns are computed by integrating the equation on a third family of control volumes associated to the new unknowns at the faces and at the edges of the primal mesh. Like in the 2D case, the three meshes play a symmetric role, resulting in a scheme that is unexpectedly simple to implement. Hence, our innovative scheme is based on a three meshes finite volume formulation. The diamond cells have 6 vertices organized in 3 pairs, defining 3 independent directions in R 3 . The approximate gradient is easily obtained by the 3 corresponding finite differences. The scheme is naturally symmetric. It is derived as a natural generalization of the 2D method, and could eventually be generalized to higher dimensions. Assembling the matrix consists in gathering some local 3 × 3 anisotropic Gram matrices (section 5.2).

This paper specifies the construction of this 3D DDFV scheme for a nonlinear elliptic equation, states and proves the main properties of this scheme, including some error estimates, and finally presents several numerical results in the linear case.

1.3. Outline. The meshes involved in the construction of the scheme are described in section 2. Some discrete divergence div T and gradient ∇ T operators are defined in section 3, that are proved to verify a discrete duality property similar to the Green formula in section 4. The approximation scheme for the nonlinear elliptic equation (1.1) stated in section 5 reads

-div T (ϕ D (∇ T u T )) = f T
where T is the set of the three finite volume meshes and D is the set of the diamond cells. The discrete divergence operator maps functions piecewise constant on the diamond cells in D to functions piecewise constant on the control volumes in T , while the discrete gradient maps functions piecewise constant on the control volumes to functions piecewise constant on the diamond cells. The main properties of our scheme, well-posedness, a priori estimates and some error estimates, are inherited from the discrete duality property and assumptions (1.2), (1.3) and (1.4) exposed in section 6. The numerical experiments are presented in section 7.

2. Construction of the meshes. Consider a usual finite volume mesh M called the primary mesh. We construct two additional finite volume meshes, with control volumes respectively around the vertices and the faces and edges of the primary mesh. They are denoted by N and FE. The diamond cells d are defined in order to contain one part of each of the interfaces between control volumes of the three meshes, so that three finite differences are available inside d to construct the discrete gradient of u.

The mesh T is the triple (M, N , FE) of meshes on Ω, defined below (see figure 2.2). We refer as c ∈ T for any of the volumes in M ∪ N ∪ FE.

2.1. The primary mesh. The mesh M is a set of open disjoint polyhedral control volumes k ⊂ Ω such that ∪k = Ω. The interfaces k ∩ l of these control volumes 1 are denoted by f = k∩l as well as the remaining boundary faces f = ∂k∩∂Ω. They are all supposed to be polygonal. The vertices of theses faces f are denoted by x a and called the vertices of M, while the edges of these faces are called the edges of M and denoted by e.

We associate to each cell k a point x k ∈ k, to each face f a point x f ∈ f and finally to each edge e a point x e ∈ e. They are for example the isobarycenters of k, f, e.

For each boundary face f ⊂ ∂Ω, we introduce a degenerate boundary control volume k reduced to the face F , with center x k = x f . The set of these degenerated boundary control volume is denoted by ∂M.

Definition 2.1. We define the relation ≺ between respectively the vertices and edges, edges and faces, faces and control volumes as "belongs to the boundary to". In other words

x a ≺ x e ≺ x f ≺ x k means x a ⊂ ∂e, e ⊂ ∂f, f ⊂ ∂k.
This relation is useful to describe, for instance, the subset of the edges that are connected to a given node x a (e.g. {x e : x a ≺ x e }), or the subset of the edges that are boundaries of a face f (e.g. {x e : x e ≺ x f }), etc.

2.2. The diamond cells. Consider an edge e of a face f: x e ≺ x f . The edge e has two endpoints denoted by x a and x b and two neighbouring control volumes in M ∪ ∂M denoted by k and l. Using the relation ≺, they are defined by

x a x b ≺ x e ≺ x f ≺ x k x l .
1 when they have a non zero d -1 dimensional measure Each of the pairs (e, f) with x e ≺ x f defines a diamond cell that is the polyhedra with vertices x a , x b , x e , x f , x k , x l . More specifically, it is denoted by d(e, f) or simply d and given by

d = d(e, f) = hull(x a , x f , x b , x k ) ∪ hull(x a , x f , x b , x l )
where hull(•) denotes the convex hull of a set of points. The set of diamond cells is called the diamond mesh and denoted by D. We associate to each diamond cell a point x d ∈ d called the "center" of d and defined as the midpoint between x e and x f :

x d = 1 2 (x e + x f ).
With the center x d of d(e, f), the diamond cell can be seen as a collection of eight tetrahedra sharing x d as a common vertex, with three more vertices chosen within the pairs (x a , x b ), (x e , x f ) and (x k , x l ) which we denote by

d = hull x d , x a x b , x e x f , x k x l .
(2.1)

Remark: If x f ∈ ∂Ω then the diamond cell d degenerates into only four tetrahedra, because x f = x l , namely d = hull x d , x a x b , x e x f , x k .
The four remaining tetrahedra degenerate into the four triangles

hull x d , x a x b , x e x f
that are subsets of ∂Ω.

The six vertices x k , x l , x a , x b and x e , x f of the diamond cell d(e, f) are supposed to be ordered in such a way that

∆ ef := det(x b -x a , x f -x e , x l -x k ) > 0.
With this orientation the measure of d is

|d| = 1 6 ∆ ef .
2.3. The node mesh. A control volume denoted by a is associated to each vertex x a of the mesh. It can be defined as follows by gathering the four tetrahedra that share x a as a common vertex within each diamond cell d for which x a is a vertex: consider first the set

d a = {d(e, f) ∈ D, with x a ≺ x e ≺ x f };
The node cell a is

a = ∪ d(e,f)∈da hull x d , x a , x e x f , x k x l . (2.2)
This definition is valid for both the interior and boundary vertices x a . The set of the node cells associated to the interior vertices x a ∈ Ω is denoted by N and the set of the node cells associated to the boundary vertices x a ∈ ∂Ω is denoted by ∂N : 2.4. The face+edge mesh. A control volume is associated to each center x f of the faces f and to each center x e of the edges e. For sake of simplicity and because we shall no more need to refer to the face or the edge directly, we can securely use the same notations, e and f, to denote the control volumes associated to x e and x f : from now on, e and f denote control volumes.

N = {a, x a ∈ Ω}, ∂N = {a, x a ∈ ∂Ω}.
They are defined like the node cells a: consider first the sets

d e = {d(e, f) ∈ D, with x e ≺ x f }, d f = {d(e, f) ∈ D, with x e ≺ x f }
of the diamond cells that share x e or x f as a vertex; the face and edge cells e and f are defined by

e = ∪ d(e,f)∈de hull x d , x a x b , x e , x k x l , f = ∪ d(e,f)∈df hull x d , x a x b , x f , x k x l . (2.3)
This definition is valid for both the interior and boundary edges and faces. It is defined FE and ∂FE as

FE = {e, x e ∈ Ω} ∪ {f, x f ∈ Ω}, ∂FE = {e, x e ∈ ∂Ω} ∪ {f, x f ∈ ∂Ω}.
For sake of clarity in the exposition, the set FE is split into E and F, respectively the edge cells, associated to the x e , and the face cells, associated to the x f . k Using the same notation, it can be defined the sets

d k = {d(e, f) ∈ D, with x e ≺ x k }
and then the control volumes k of the primary mesh M are simply

k = ∪ d(e,f)∈dk hull x d , x a x b , x e x f , x k . (2.4)
2.5. Interfaces within the three meshes.

The DDFV scheme is based on three finite volume formulations on the meshes M, N and FE. The interfaces between pairs of control volumes of these three meshes are described in terms of triangles inside each diamond cell d.

x d x k x l • • x a x b x f
x e (a) Interface Skl.

x d x k x l • • x a x b x f x e (b) Interface Sab. x d x k x l • • x a x b x f x e (c) Interface Sef.
S kl (d) := k ∩ l ∩ d = hull x d , x a x b , x e x f , (2.5
)

N kl = Skl n kl ds = 1 2 (x b -x a ) × (x f -x e ), (2.6)
S ab (d) := ā ∩ b ∩ d = hull x d , x e x f , x k x l , (2.7
)

N ab = Sab n ab ds = 1 2 (x f -x e ) × (x l -x k ), (2.8)
S ef (d) := ē ∩ f ∩ d = hull x d , x k x l , x a x b , (2.9
)

N ef = Sef n e,f ds = 1 2 (x l -x k ) × (x b -x a ), (2.10)
where n kl stands for the unit normal to S kl (d) oriented from k to l, n ab stands for the unit normal to S ab (d) oriented from a to b and n e,f stands for the unit normal to S ef (d) oriented from e to f. Furthermore, note that

N kl • (x l -x k ) = N ab • (x b -x a ) = N ef • (x f -x e ) = 1 2 ∆ ef = 3|d|. (2.

11)

Proof. A straightforward computation shows that the interfaces between pairs of control volumes are indeed made of triangles, and their average normal can be expressed using simple vector products, so that eq. (2.11) is obvious.

Finally, the boundaries of the interior control volumes k ∈ M, a ∈ N , e, f ∈ FE can be expressed in terms of the S kl (d), S ef (d), S ab (d):

∂k = ∪ d∈dk S kl (d) , ∂a = ∪ d∈da S ab (d),
(2.12)

∂e = ∪ d∈de S ef (d), ∂f = ∪ d∈df S ef (d). ( 2

.13)

Remark: In the case a ∈ ∂N or e or f ∈ ∂FE, it is important to note that the boundary ∂a, ∂e or ∂f is not easily described in such a way. Anyway they are not needed since only Dirichlet boundary conditions are used: the scheme writes only on interior control volumes.

2.6. Regularity of the meshes. Given a diamond cell d ∈ D, let

ν kl = N kl |N kl | , ν ab = N ab |N ab | , ν ef = N ef |N ef | (2.14)
denote the unit normals (see eqs. (2.6)-(2.10)) and

G d =   ν kl • ν kl ν kl • ν ab ν kl • ν ef ν ab • ν kl ν ab • ν ab ν ab • ν ef ν ef • ν kl ν ef • ν ab ν ef • ν ef   (2.15)
denote the Gram matrix associated to (ν kl , ν ab , ν ef ). Definition 2.3. The size h of the mesh T is the maximum diameter of the diamond cells,

h d = sup x,y∈d |x -y|, h = max d∈D h d .
(2.16)

It is assumed that each diamond cell d contains an open ball B d of diameter R d such that d is star-shaped with respect to B d , that is {tx + (1 -t)y, t ∈ (0, 1)} ⊂ d for any x ∈ B d and y ∈ d.
The constant of regularity of the mesh is any number c r (T ) > 0 such that

∀d ∈ D, 1 λ m (d) ≤ c r (T ), |d| |d i | ≤ c r (T ), h d R d ≤ c r (T ) (2.17)
where λ m (d) is the smallest eigenvalue of G d , (d i ) i=1...8 are the 8 tetrahedra that compose d (see eq. (2.1)).

3. The discrete spaces and operators.

3.1. The discrete spaces. Consider the data (u M , u N , u F E ) of three functions piecewise constant respectively on the k ∈ M, a ∈ N and e/f ∈ FE:

u M = k∈M u k χ k , u N = A∈N u a χ A , u F E = f∈F u f χ f + e∈E uχ e .
The sets of functions piecewise constant on the K ∈ M, a ∈ N and e/f ∈ FE are respectively denoted by X M , X N and X F E . They are finite dimensional subspaces of any L q (Ω) (q ≥ 1). The finite volume unknown is an element of the space X = X M × X N × X F E . It is denoted by

u T = (u M , u N , u F E ) = ((u k ) k∈M , (u a ) a∈N , (u e ) e∈E , (u f ) f∈F ) .

It is supplemented with boundary values

δu T = ((u k ) xk∈∂M , (u a ) xa∈∂Ω , (u e ) xe∈∂Ω , (u f ) xf∈∂Ω )
that define a linear space ∂X. These boundary values δu T are actually determined by a suitable projection of the boundary data g (see eq. ( 5.3) below).

The space X is supplied with the natural inner product

(u T , v T ) X = 1 3 Ω u M v M + Ω u N v N + Ω u F E v F E = 1 3 k∈M u k v k |k| + a∈N u a v a |a| + e∈E u e v e |e| + f∈F u f v f |f| . (3.1)
For this norm, the inequality of Hölder reads:

(u T , v T ) X ≤ 1 3 u M L p ′ v M L p + u N L p ′ v N L p + u F E L p ′ v F E L p ≤ u T L p ′ v T L p (3.2)
with the notation

u T L p = 1 3 u M p L p + u N p L p + u F E p L p 1/p . (3.3)
A linear space of vector fields will be associated to the finite volumes gradient. It is the space Q of functions piecewise constant on the d ∈ D with value in R 3 :

ξ D ∈ Q ⇔ ξ D = d∈D ξ d χ d , ∀d ∈ D, ξ d ∈ R 3 .
These functions are (L q (Ω)) 3 for any q ≥ 1 and like for elements u T ∈ X, an element ξ D ∈ Q may also be denoted by the sequence of its degrees of freedom:

ξ D = (ξ d ) d∈D .
The space Q is endowed with the natural inner product

(ξ D , η D ) Q = Ω ξ D • η D = d∈D ξ d • η d |d|.
(3.4)

3.2. The discrete gradient. The discrete gradient is defined for (u

T , δu T ) ∈ X × ∂X. It is a vector field in Q, denoted by ∇ T δu u T = (∇ d δu u T ) d∈D where ∀d ∈ D, ∇ d δu u T = 1 3|d| ((u l -u k )N kl + (u b -u a )N ab + (u f -u e )N ef ) . (3.5)
The mapping (u T , δu T ) ∈ X × δX → ∇ T δu u T ∈ Q is linear with respect to (u T , δu T ) and we shall need a "homogeneous" gradient, denoted by ∇ T 0 : u T ∈ X → ∇ T 0 u T ∈ Q defined by eq. (3.5) with δu T = 0 δX . It is a linear mapping from X onto Q.

Lemma 3.1 (Properties of the discrete gradient). By construction, for each diamond cell d ∈ D, 1. the vector ∇ d δu u T is the unique vector of R 3 such that

∇ d δu u T •(x l -x k ) = u l -u k , ∇ d δu u T •(x b -x a ) = u b -u a , ∇ d δu u T •(x f -x e ) = u f -u e , 2. if u(x) = u 0 + p • x is an affine function and u k = u(x k ), u l = u(x l ), u e = u(x e ), u f = u(x f ), u a = u(x a ), u b = u(x b ), then ∇ d δu u T = ∇u = p in R 3 .
Proof. The first point is a consequence of the relation (2.11) and the second point is a consequence of the first one.

3.3. The discrete divergence. The discrete divergence is defined for a vector field ξ D ∈ Q. It is an element of X denoted by div T ξ D = (div M ξ D , div N ξ D , div F E ξ D ) ∈ X where div M ξ D = (div k ξ D ) k∈M , div N ξ D = (div a ξ D ) a∈N , div F E ξ D = (div e ξ D ) e∈E , (div f ξ D ) f∈F .
For any control volume denoted in general by c = k, a, e, f ∈ T , the discrete divergence is the finite volume one:

|c| div c ξ D = ∂c ξ D (x) • n c (x)dσ(x), (3.6)
where n c is the unit normal to ∂c outward of c. Because of lemma 2.2 and equalities (2.12) and (2.13), these discrete divergences read

|k| div k ξ D = d∈dk ξ d • N kl , |a| div a ξ D = d∈da ξ d • N ab , (3.7
)

|e| div e ξ D = d∈de ξ d • N ef , |f| div f ξ D = d∈df ξ d • (-N ef ) . (3.8)
4. Properties of the Discrete operators.

4.1. The discrete duality relationship. We first state a discrete version of the Green formula in the spaces W 1,p ′ (Ω) and W 1,p 0 (Ω):

div q, u L p ′ ,L p + q, ∇u (L p ′ ) 3 ,(L p ) 3 = 0, ∀u ∈ W 1,p 0 (Ω), ∀q ∈ W 1,p ′ (Ω) 3 .
Theorem 4.1 (Discrete duality identity). For any u T ∈ X and ξ D ∈ Q, the homogeneous gradient ∇ T 0 u T and divergence div T ξ D verify the discrete duality relation

div T ξ D , u T X + ξ D , ∇ T 0 u T Q = 0.
Proof. From the eqs. (3.7) and (3.8) of the divergence and (3.1) of the inner product in X, it is computed:

div T ξ D , u T X = 1 3 k∈M d∈dk ξ d • N kl u k + a∈N d∈da ξ d • N ab u a + f∈F d∈df ξ d • (-N ef )u f + e∈E d∈de ξ d • N ef u e = - 1 3 d∈D ξ d • (N kl (u l -u k ) + N ab (u b -u a ) + N ef (u f -u e )) = - d∈D |d|ξ d • ∇ d u T = -ξ D , ∇ T u T Q ,
using also eqs. (3.5) and (3.4) for the discrete gradient and the inner product in Q, and with the homogeneous Dirichlet condition δu T = 0 δX .

4.2.

The inequality of Poincaré. The discrete spaces X × δX and X (or X × {0}) can be interpreted as discrete counterparts of W 1,p (Ω) and W 1,p 0 (Ω) respectively. For homogeneous Dirichlet boundary data, that is using ∇ T 0 in X, it is expected that ∇ T 0 u T = 0 ⇒ u T = 0 and that a discrete inequality of Poincaré holds. Theorem 4.2 (Inequality of Poincaré). There exists a constant C > 0 depending on c r (T ) such that

∀u T ∈ X, u T L p ≤ C ∇ T 0 u T L p .
Proof. The proof makes use of the notations from eqs. (2.14) and (2.15) for the unit normals inside a diamond d, the associated Gram matrix and its smallest eigenvalue λ m (d). For sake of simplicity, consider the notations

a kl = (u l -u k ) |N kl | 3|d| , a ab = (u b -u a ) |N ab | 3|d| , a ef = (u f -u e ) |N ef | 3|d| .
The expression of the discrete gradient now reads ∇ d δu u T = a kl ν kl + a ab ν ab + a ef ν ef and then

∇ d 0 u T 2 = a T G d a ≥ λ m (d) 3 i=1 |a i | 2 ,
where a = (a kl , a ab , a ef ). As a consequence,

|a i | 2 ≤ 1/λ m (d) ∇ d 0 u T 2
, and then

∇ d 0 u T p ≥ λ m (d) p/2 3 |u l -u k | p |N kl | p 3 p |d| p + |u b -u a | p |N ab | p 3 p |d| p + |u f -u e | p |N ef | p 3 p |d| p .
It remains to prove that there exists a constant C > 0 depending on the regularity of the meshes c r (T ) and on Ω such that

Ω |u M (x)| p dx ≤ C d∈D |u l -u k | p |N kl | p 3 p |d| p |d|,
and similarly for the two other finite differences in the above inequality. The usual VF4 computation from [START_REF] Eymard | Handbook of Numerical Analysis[END_REF] yields such a result (see also [START_REF] Andreianov | Convergence of finite volume approximations for a nonlinear elliptic-parabolic problem : a "continuous approach[END_REF] for the L p case).

5. The finite volume scheme.

∀d ∈ D, ∀ξ ∈ R 3 , ϕ d (ξ) = 1 |d| d ϕ(z, ξ) dz. (5.2)
The flux ϕ(•, ∇u(•)) is approximated by the vector field in Q defined by

ϕ D (∇ T δu u T ) = (ϕ d (∇ d δu u T )) d∈D ∈ Q,
where δu T = p T g ∈ ∂X is given by a pointwise projection of the data g on the x k , x a , x e and x f on ∂Ω, ∀g ∈ C 0 (∂Ω), p T g = (g(x k ), g(x a ), g(x e ), g(x f )) xk∈∂M,xa∈∂N ,xe,xf∈∂F E (5.3) and ∇ T δu u T has been defined in section 3.2. With this approximation of the flux and the discrete divergence described in section 3.3, eq. (5.1) reads

-div T ϕ D (∇ T δu u T ) = π T f, δu T = p T g (5.4)
where the projection

π T f = {(f k ) k∈M , (f a ) a∈N , (f e , f f ) e∈E,f∈F } ∈ X is the piecewise constant projection defined by average values, ∀k ∈ M, f k = 1 |k| k f (x)dx, ∀a ∈ N , f a = 1 |a| a f (x)dx, (5.5) ∀e ∈ E, f e = 1 |e| e f (x)dx, ∀f ∈ F, f f = 1 |f| f f (x)dx. (5.6)
For any fixed values δu T ∈ ∂X, eq. (5.4) is a non linear system of N M + N N + N F E equations with N M + N N + N F E unknowns, where N M , N N and N F E are the number of cells, interior vertices and interior faces plus edges of the primal mesh T .

Remark: in the general case, g ∈ W 1-1/p,p ′ (∂Ω) and f ∈ W -1,p ′ (Ω), only the projections π T for the right-hand side f and p T for the boundary data g has to be modified. For instance f k = f, χ k is a natural choice to define π T and the g k,a,... would be some average values of g on the boundary.

5.2.

A word on practical implementation. Note that the implementation of such a scheme does not require the construction of the node mesh N and the face and edges mesh FE explicitly. If the primal mesh is given with the format a ≺ e ≺ f ≺ k that is a control volume is defined by its faces, a face by its edges and an edge by its vertices, then a diamond cell is easily constructed by referencing its six vertices x a , x b , x k , x l , x e , x f . This is a usual structure for simplicial meshes (i.e. tetrahedra in 3D) of Ω.

The expression of the scheme requires to compute the values N kl , N ab , N ef and the measures of the eight tetrahedral cells that compose the diamond cell (see eq. (2.1)). The system of equations involved in the resolution of the scheme can be easily implemented by iterating through the diamond cell structure.

For instance, in the linear case, ϕ(z, ∇u(z)) = K(x)∇u(x) where K(x) is a uniformly elliptic symmetric matrix, the flux in the diamond cell d is K d ∇ d δu u T and eq. ( 5.4) is a symmetric and positive definite linear system of equations. Its coefficients are computed by assembling the local contributions of all the diamond cells d. The elementary matrix in d is

K d =   K d N kl • N kl K d N kl • N ab K d N kl • N ef K d N ab • N kl K d N ab • N ab K d N ab • N ef K d N ef • N kl K d N ef • N ab K d N ef • N ef   with K d = 1 |d| d K(x)dx.
The right hand side in eq. ( 5.4) is split similarly in elementary contributions on the eight tetrahedra that compose the diamond cells d thanks to (2.2), (2.3) and (2.4).

6. Analysis of the scheme. In this section, the nonlinear system of equations (5.4) is proved to be well-posed, uniform a priori estimates are found on its solutions and finally error estimates are given. The discrete solution u T will be compared to the pointwise projection of the exact solution u, defined as in eq. ( 5.3) by ∀u ∈ W 2,p (Ω), p T u = (u(x k ), u(x a ), u(x e ), u(x f )) k∈M,a∈N ,e∈E,f∈F .

(

The comparison u Tp T u will be studied in the L p norm as defined by eq. (3.3) and in the discrete W 1,p semi norm, defined by

|u T | W 1,p (Ω),T = ∇ T 0 u T L p (Ω) . (6.2)
6.1. The discrete problem and a priori estimate. First, the discrete problem is proved to be well-posed and the discrete solution u T to be bounded in the discrete W 1,p norm. Theorem 6.1 (Well-posedness of Eqs. (5.4)). Assume that the flux ϕ satisfies assumptions (1.2), (1.3) and (1.4). For any function f ∈ L p ′ (Ω), any boundary data g = γ 0 (ḡ) with ḡ ∈ W 2,p (Ω) and any mesh T on Ω, the finite volume scheme (5.4) admits a unique solution u T ∈ X and there exists a constant C > 0 depending only on p, (c i ) i=1,2 and c r (T ), such that

Ω |∇ T δu u T | p ≤ C f p ′ L p ′ + b 1 L 1 + b 2 p ′ L p ′ + ḡ p W 2,p (Ω) . (6.3)
Proof. The mapping a T : (u T , δu T ) ∈ X ×δX →div T (ϕ D (∇ T δu u T ))-π T f ∈ X is continuous and coercitive: its continuity follows from eq. (1.5) and its coercitivity is a consequence of theorems 4.1 and 4.2 and of assumption (1.3).

For any piecewise constant function v T ∈ X and piecewise constant boundary data δu T ∈ δX, note that

∇ T δu u T -∇ T δu v T = ∇ T 0 (u T -v T ) so that a T (u T , δu T ), u T -v T X = -div T (ϕ D (∇ T δu u T )) -π T f, u T -v T X = Ω ϕ(z, ∇ T δu u T (z)) • ∇ T 0 (u T (z) -v T (z))dz -(π T f, u T -v T ) X = Ω ϕ(z, ∇ T δu u T (z)) • ∇ T δu u T (z)dz - Ω ϕ(z, ∇ T δu u T (z)) • ∇ T δu v T (z)dz -(π T f, u T -v T ) X .
Assumptions (1.3) and (1.4) are used to bound the first two terms of the above righthand side:

Ω ϕ(z, ∇ T δu u T (z)) • ∇ T δu u T (z)dz ≥ c 1 ∇ T δu u T p L p -b 1 L 1 and Ω ϕ(z, ∇ T δu u T (z)) • ∇ T δu v T (z)dz ≤ Ω c 2 |∇ T δu v T | p-1 + b 2 |∇ T δu v T | ≤ c 2 ∇ T δu u T p-1 L p ∇ T δu v T L p + b 2 L p ′ ∇ T δu v T L p .
With some inequalities of Young, we get, for any α, β > 0,

a T (u T , δu T ), u T -v T X ≥ c 1 - c 2 β p ′ p ′ ∇ T δu u T p L p -b 1 L 1 + 1 p ′ b 2 p ′ L p ′ + 1 α p ′ p ′ π T f p ′ L p ′ - c 2 β p p + 1 p ∇ T δu v T p L p - α p p u T -v T p L p . The inequality of Poincaré (theorem 4.2) is used to bound u T -v T p L p : u T -v T p L p ≤ C ∇ T 0 (u T -v T ) p L p ≤ C ∇ T δu u T p L p + C ∇ T δu v T p L p . At last, we can choose β > 0 such that c 1 -c2 β p ′ p ′ = 1 2 c 1 and then α > 0 such that 1 2 c 1 -Cα p p = 1 4 c 1 (C is still the Poincarï¿ 1 2 constant) and get, because π T f L p ′ ≤ f L p ′ , a T (u T , δu T ), u T -v T X + b 1 L 1 + 1 p ′ b 2 p ′ L p ′ + 1 α p ′ p ′ f p ′ L p ′ + c 2 β p p + 1 p + Cα p p ∇ T δu v T p L p ≥ 1 4 c 1 ∇ T δu u T p L p . (6.4)
Consider ḡ ∈ W 2,p (Ω) such that the boundary data is g = γ 0 (ḡ). Substituting v T = p T ḡ ∈ X and δu T = p T g ∈ δX as defined by eqs. (6.1) and (5.3), lemma 6.8 can be applied and results in

∇ T δu v T L p ≤ C ḡ W 2,p (Ω) .
The existence of a solution to the scheme (5.4) is then a consequence of the Brouwer fixed point theorem, and estimate (6.3) is a direct consequence of inequality (6.4).

The uniqueness of the solution is finally due to the monotonicity of the map a T . Indeed, theorem 4.1 and assumption (1.2) yield, for any u T , v T ∈ X such that u T = v T (with the same boundary data δu T ),

a T (u T ) -a T (v T ), u T -v T X = -div T (ϕ D (∇ T δu u T )) + div T (ϕ D (∇ T δu v T )), u T -v T X = Ω ϕ(z, ∇ T δu u T ) -ϕ(z, ∇ T δu v T ) • (∇ T 0 (u T -v T ))dz = Ω ϕ(z, ∇ T δu u T ) -ϕ(z, ∇ T δu v T ) • (∇ T δu u T -∇ T δu v T )dz > 0.
Remark: In the case where the flux ϕ derives from a convex potential Φ:

ϕ(z, ξ) = ∇ ξ Φ(z, ξ) ∀ξ ∈ R 2
, for a.e. z ∈ Ω, and Φ(z, 0) = 0 for a.e. z ∈ Ω the solution u T of the scheme (5.4) is also the unique minimizer of the discrete energy J T associated to the scheme by

J T (u T ) = Ω Φ(z, ∇ T u T ) -Ω u T π T f .

Assumptions and technical lemmas.

The scheme is well-posed, and the discrete solution might be proved to converge under assumptions (1.2), (1.3) and (1.4) only, following the 2D case [START_REF] Andreianov | Discrete duality finite volume schemes for Leray-Lions type elliptic problems on general 2D-meshes[END_REF] or another 3D approach [START_REF] Andreianov | A gradient reconstruction formula for finitevolume schemes and discrete duality[END_REF]. Anyway, in order to compute some error estimates, the following additional assumptions on ϕ are needed : there exists constants c 3 , c 4 , c 5 > 0, b 3 ∈ L For p = 2, inequality (6.6) degenerates and the assumptions becomes b 3 ∈ L ∞ (Ω). Lemma 6.2 (Regularity of the flux). Under assumptions (6.5)-(6.7) on ϕ and given a function u ∈ W 2,p (Ω), the mapping G : z → ϕ(z, ∇v(z)) is well defined in (W 1,p ′ (Ω)) 3 . Furthermore, the mapping v → G is such that

∇G L p ′ (Ω) ≤ C v W 2,p (Ω) (6.8)
with C > 0 that depends only on the (b i ) i=3,4 and (c i ) i=3,4,5 .

Proof. The proof is straightforward. Definition 6.3 (Errors of consistency). Suppose that the solution u of the continuous problem (1.1) is in W 2,p (Ω). Consider its pointwise projection (p T u, p T g) ∈ X × δX defined by eqs (6.1) and (5.

(u) = (R d (u)) d∈D ∈ Q where ∀d ∈ D, R d (u) = ψ d (∇u) -ϕ d (∇ T p g p T u). It is split as R T (u) = R 1 T (u) + R 2 T (u) with R j T (u) = (R j d (u)) d∈D and ∀d ∈ D, R 1 d (u) = ψ d (∇u) -ϕ d (∇u)
involves differences between surface and volume integrals and

∀d ∈ D, R 2 d (u) = ϕ d (∇u) -ϕ d (∇ T p g p T u)
is related to the error of consistency on the gradient.

The next lemma are technical multidimensional results used to bound the errors term R 1 d and R 2 d , similar to the usual finite element estimates, see for instance [START_REF] Brenner | The Mathematical Theory of Finite Element Methods[END_REF]. Lemma 6. [START_REF] Andreianov | Convergence of finite volume approximations for a nonlinear elliptic-parabolic problem : a "continuous approach[END_REF].

Let H = {x, (x -x 0 ) • n = 0} (x 0 ∈ R d and n ∈ R d ) be a hyperplane in R d and σ ⊂ H be an bounded polygon in H. Consider x 1 and x 2 in R d \H such that (x 1 -x 0 ) • n < 0 < (x 2 -x 0 ) • n and let K i (i = 1,
2) be the pyramid with basis σ and vertex x i , namely K i = {tx i + (1t)y, y ∈ σ, t ∈ (0, 1)}. Finally consider the set K = K 1 ∪ K 2 . For any q ≥ 1 and any function v ∈ W 1,q (K),

1 |K i | Ki v(x)dx - 1 |σ| σ v(y)dσ(y) ≤ h i d|K i | 1/q ∇v L q (Ki) (i = 1, 2), 1 |K 1 | K1 v(x)dx - 1 |K 2 | K2 v(x)dx ≤ 1 d max i=1,2 h i |K i | |K| 1-1/q ∇v L q (K) ,
where

h i = diam(K i ) = max{|x -y|, x, y ∈ K}.
Proof. The first inequality is a variant of the result proved in [START_REF] Droniou | A mixed finite volume scheme for anisotropic diffusion problems on any grid[END_REF] (lemma 6.3) while the second is an easy consequence of the former one. Lemma 6.5. Consider an open bounded subset K in R d and suppose that there exists an open ball B of center x K ∈ K and of radius R > 0 such that K is star-shaped with respect to B. For any q ≥ 1 and for any function v ∈ W 1,q (K),

v -v B L q (K) ≤ d d -1 1/q h 2 K R ∇v L q (K)
where

h K = sup{|x -y|, x, y ∈ K} is the diameter of K and v B = 1 |B| B v(x)dx is the average value of v on B.
Proof. The proof is an adaptation of the proof of lemma 7.1 in [START_REF] Droniou | Error estimates for the convergence of a finite volume discretization of convectiondiffusion equations[END_REF]. Lemma 6.6 (Error of consistency due to the projections).

If u ∈ W 2,p (Ω) then R 1 T (u) L p ′ (Ω) ≤ 2c r (T ) 2 h ∇G L p ′ (Ω) ≤ 2Cc r (T ) 2 h u W 2,p (Ω) ,
where the constant C > 0 and the function G are taken from lemma 6.2.

Proof. The difference R 1 d (u) involves differences between surface and volume averages of the flux:

R 1 d (u) • ν kl = 1 |N kl | Skl ϕ(z, ∇u(z)) • n kl dz - 1 |d| d ϕ(z, ∇u(z)) • ν kl dz , R 1 d (u) • ν ab = 1 |N ab | Sab ϕ(z, ∇u(z)) • n ab dz - 1 |d| d ϕ(z, ∇u(z)) • ν ab dz , R 1 d (u) • ν ef = 1 |N ef | Sef ϕ(z, ∇u(z)) • n ef dz - 1 |d| d ϕ(z, ∇u(z)) • ν ef dz .
Remark that each of the interfaces S kl , S ab and S ef is composed of four triangles (eqs. (2.5), (2.7) and (2.9) from lemma 2.2), while d is a collection of 8 tetrahedra with theses faces as bases and, respectively, (x k , x l ), (x a , x b ) and (x e , x f ) as vertices.

For sake of simplicity, let S denote any of these interfaces, S i denote the four triangles (i = 1 . . . 4), x 1 , x 2 denote the two corresponding vertices and n(x) = 4 i=1 n i χ Si (x) denote the unit normal to S from x 1 towards x 2 . The diamond cell is composed of the 8 tetrahedra

d k i = hull(S i , x k ) (i = 1, . . . 4 and k = 1, 2). The cor- responding integral normal is N = S n(x)dσ(x) = 4 i=1 |S i |n i and the unit normal is ν = 4 i=1
|Si| |S| n i . At last, consider the function G(z) = ϕ(z, ∇u(z)) as defined in lemme 6.2. Each of the 3 errors from above now reads

R 1 d (u) • ν = 4 i=1 |S i | |S| n i • 1 |S i | Si G(z)dz - 1 |d| d G(z)dz = 4 j=1 4 i=1 k=1,2 |d k j | |d| |S i | |S| n i • 1 |S i | Si G(z)dz - 1 |d k j | d k j G(z)dz and it remains to bound 1 |Si| Si G(z)dz -1 |d k j | d k j G(z)dz for any i = 1 . . . 4, j = 1 .
. . 4 and k = 1, 2. Since the d k j form a tetrahedrisation of d the following bound is a consequence of lemma 6.4 with q = 1 and d = 3 :

1 |S i | Si G(z)dz - 1 |d k j | d k j G(z)dz ≤ 1 |S i | Si G(z)dz - 1 |d k i | d k i G(z)dz + 1 |d k i | d k i G(z)dz - 1 |d k j | d k j G(z)dz ≤ h i,k 3|d k i | d k i |∇G(z)|dz + 1 3 max j=1,...4 h j,k |d k j | d k |∇G(z)|dz ≤ 2 3 max j=1,...4 h j,k |d k j | d k |∇G(z)|dz where d k = ∪ 4 j=1 d k j and h j,k = diam(d k j ). Finally, since d k ⊂ d, R 1 d (u) • ν ≤ 2 3 max k=1,2 max j=1,...4 h j,k |d k j | d |∇G(z)|dz 4 j=1 4 i=1 k=1,2 |d k j | |d| |S i | |S| ≤ 2 3 max k=1,2 max j=1,...4 h j,k |d k j | |d| 1/p ∇G L p ′ (d) ≤ 2c r (T ) 3 h|d| -1/p ′ ∇G L p ′ (d) because c r (T )|d k j | ≥ |d| and h j,k ≤ h d ≤ h. The vector R 1 d (u) can be expressed in the basis (ν kl , ν ab , ν ef ) as R 1 d (u) = R 1 kl (u)ν kl + R 1 ab (u)ν ab + R 1 ef (u)ν ef and its norm verifies R 1 d (u) 2 = R 1 d (u) T G d R 1 d (u) ≤ λ M (d) (R 1 kl (u)) 2 + (R 1 ab (u)) 2 + (R 1 ef (u)) 2 .
The three errors of consistency evaluated above are R 1 d (u) • ν kl , ... given by

  R 1 d • ν kl R 1 d • ν ab R 1 d • ν ef   = G d   R 1 kl R 1 ab R 1 ef   . Because G d -1 2 ≤ 1 λm(d) , it is derived the estimate R 1 d (u) 2 ≤ λ M (d) λ m (d) 2 R 1 d (u) • ν kl 2 + R 1 d (u) • ν ab 2 + R 1 d (u) • ν ef 2 .
Here, λ M (d) is the largest eigenvalue of the Gram matrix G d as defined by eq. (2.15), while λ m (d) is its smallest one. Note that λ M (d) ≤ G d 1 ≤ 3 and c r (T )λ m (d) ≥ 1, so that the bound on the local error of consistency reads

R 1 d (u) ≤ 3c r (T ) 2c r (T ) 3 h|d| -1/p ′ ∇G L p ′ (d) = 2c r (T ) 2 h|d| -1/p ′ ∇G L p ′ (d)
and the proof is completed by an easy summation over the diamond cell d in D.

Lemma 6.7 (Error of consistency on the flux). There exists a constant C > 0 depending on the mesh regularity constant c r (T ), on c 4 and p, q, such that, if u ∈ W 2,p (Ω),

R 2 T (u) L p ′ (Ω) ≤ Ch b 3 L p/(p-2) (Ω) + u p-2 W 2,p (Ω) u W 2,p (Ω)
with g = γ(u) as a boundary data.

Proof. Using (6.6), the computation of R 2 T (u) reads for p = 2:

Ω |R 2 T (u)| p ′ = d∈D |d| 1 |d| d ϕ(z, ∇u(z)) -ϕ(z, ∇ d p g p T u(z)) dz p ′ ≤ d∈D d ϕ(z, ∇u(z)) -ϕ(z, ∇ d p g p T u(z))dz p ′ ≤ d∈D d c 4 b 3 + |∇u| p-2 + |∇ d p g p T u| p-2 p ′ |∇u -∇ d p g p T u| p ′ dz ≤ Ω c 4 b 3 + |∇u| p-2 + |∇ T p g p T u| p-2 p/(p-2) dz 1-p ′ /p Ω |∇u -∇ T p g p T u| p dz p ′ /p because p ′ /(1 -p ′ /p) = 1/(1 -2/p) = p/(p -2)
. This inequality finally reads

R 2 T (u) L p ′ (Ω) ≤ c 1-2/p 4 b 3 +|∇u| p-2 +|∇ T p g p T u| p-2 L p/(p-2) ∇u-∇ T p g p T u L p (Ω) ≤ c 1-2/p 4 b 3 L p/(p-2) (Ω) + ∇u p-2 L p (Ω) + ∇ T p g p T u p-2 L p (Ω) ∇u -∇ T p g p T u L p (Ω) .
For p = 2, we simply have

Ω |R 2 T (u)| 2 ≤ d∈D d ϕ(z, ∇u(z)) -ϕ(z, ∇ d p g p T u(z))dz 2 ≤ b 3 L ∞ (Ω) ∇u -∇ d p g p T u 2 L 2 (Ω) .
The final estimate results from lemma 6.8 below. Lemma 6.8 (Estimates on the projection). There exists a constant C(p) > 0 that depends only on p such that, for any function u ∈ W 2,p (Ω), ∇u -∇ T p g p T u L p (Ω) ≤ C(p)c r (T ) 3(1+1/p) h u W 2,p (Ω) , (6.12)

∇ T p g p T u L p (Ω) ≤ 1 + C(p)c r (T ) 3(1+1/p) diam(Ω) u W 2,p (Ω) (6.13)
with g = γ(u). The value of C(p) is specified in eq. (6.15). Proof. By density, it is sufficient to prove the estimate (6.12) for functions u ∈ C 2 ( Ω). In that case, for any d ∈ D, consider the ball B d inside d of radius R d > 0 and such that d is star-shaped with respect to B d (definition 2.3). It is written

∇u -∇ T p g p T u L p (Ω) = d∈D E d 1/p with E d = d ∇u(z) -∇ d p g p T u p dz. Let ∇u B = 1
|B| B ∇u(z)dz denote the average of ∇u on the ball B. The estimate is split as

E d ≤ 2 p-1 d |∇u(z) -∇u B | p dz + ∇u B -∇ d p g p T u p |d| . (6.14)
The first term is bounded because of the result from lemma 6.5,

d |∇u(z) -∇u B | p dz ≤ 3 2 h d R d p h p d d |∇u(z)| p dz.
To bound the second term, note that, for any c = k, l, a, b, e, f,

∀z ∈ B, u(x c ) = u(z) + ∇u(z) • (x c -z) + E c (z), with E c (z) = 1 0 H(u)(z + t(x c -z))(x c -z) • (x c -z)(1 -t)dt
(where H(u) denotes the Hessian matrix of u). From the consistency property stated in lemma 3.1 and because g = γ 0 (u),

∇ d p g p T u = ∇u(z) + 1 3|d| (E l (z) -E k (z))N kl + (E b (z) -E a (z))N ab + (E f (z) -E e (z))N ef .
As a consequence,

∇ d p g p T u -∇u B = 1 3|d| ((E l -E k )N kl + (E b -E a )N ab + (E f -E e )N ef ) with E c = 1 |B| B E c (z)
|E c | ≤ h 2 d |B| H(u) L p (d) 1 0 s d(1-1/p) |B| 1-1/p sds s d = h 2 d |B| -1/p H(u) L p (d) 1 0 s 1-d/p ds = 1 2 -d/p h 2 d |B| -1/p H(u) L p (d) .
Here, 2d/p > 0 because d = 3 and p ≥ 2, which is also used to prove the Sobolev's embeddings stated in (1.6). The final estimate of the second term of eq. (6.14) is For functions u in W 2,p (Ω), the inequality (6.13) is derived directly from the previous one using the triangular inequality. Lemma 6.9. Given q such that 1 p -1 3 < 1 q < 1 3 like in (1.6), for any u ∈ W 2,p (Ω),

∇u B -∇ d p g p T u ≤ 1 3|d| 2 2 -3/p h 2 d |B| -1/p H(u) L p (d) (|N kl | + |N ab | + |N ef |) ≤ 1 3|d| 2 2 -3/p h 2 d |B| -1/p H(u) L p (d) 3
E d ≤ 2 p-1 3 2 h d R d p h p d + 1 (2 -3/p) p h 4p d |d| p |d| |B| u p W 2,p (
u -p T u L p (Ω) ≤ |Ω| 1/p-1/q (1 -3p/q) 1/p h ∇u L q (Ω) ≤ Ch u W 2,p (Ω) (6.16)
where C > 0 is constant that depends only on Ω and p.

Proof. Recall that p T u = (u(x k ), u(x a ), u(x e ), u(x f )) k∈M,a∈N ,e∈E,f∈F is a triple of piecewise constant functions, namely u M , u N and u F E and according to the notation (3.3),

u -p T u L p (Ω) = 1 3 Ω |u -u M | p + Ω |u -u N | p + Ω |u -u F E | p 1/p
. (6.17)

For each of these 3 piecewise constant functions, the error is split into integrals on the 8 tetrahedra that form a diamond, namely the (d i ) i=1...8 as defined by eq. (2.1). Hence, it is sufficient to estimate some integrals of the form di |u(z)u(x c )| p dz for

any c = k, l, a, b, e, f. If u is a function in C 2 ( Ω), then u(z) -u(x c ) = 1 0 ∇u(tz + (1 -t)x c ) • (z -x c )dt and di |u(z) -u(x c )| p dz ≤ di 1 0 |∇u(tz + (1 -t)x c )| p h p d dtdz ≤ h p d 1 0 dt t 3 di(t) |∇u(x)| p dx ≤ h p d 1 0 dt t 3 di |∇u(x)| q dx p/q |d i (t)| 1-p/q where d i (t) = {tz + (1 -t)x c , z ∈ d i } ⊂ d i because d i is convex. Now |d i (t)| = t 3 |d i | and then di |u(z) -u(x c )| p dz ≤ h p d |d i | 1-p/q ∇u p L q (di) 1 0 t -3p/q dt = 1 1 -3p/q h p d |d i | 1-p/q ∇u p L q (di) .
Each of the 3 integrals in eq. ( 6.17) is bounded by h p 1-3p/q ∇u p L q (Ω) |Ω| 1-p/q so that, using the Sobolev's embedding W 2,p (Ω) ⊂ W 1,q (Ω), the inequalities (6.16) hold.

6.3. Main result and proof. Our main result is the following. Theorem 6.10 (Error estimates). Assume that the flux ϕ satisfies assumptions (1.2), (1.3), (1.4) on the one hand and assumptions (6.5), (6.6) and (6.7) on the other hand. Consider f ∈ L p ′ (Ω) and assume that the solution u to (1.1) belongs to W 2,p (Ω).

For any mesh T on Ω there exists a constant C > 0 depending on the norm u W 2,p , the regularity parameter c r (T ), the data Ω, f, g, (b i ) 1≤i≤5 and (c i ) 1≤i≤4 , such that

u -u M L p + u -u N L p + u -u F E L p + ∇u -∇ T δu u T L p ≤ C u W 2,p (
Ω) h 1/(p-1) (6.18) where u T = (u M , u N , u F E ) ∈ X and δu T = p T g (eq. (5.3)) are the solutions to eq. (5.4).

Proof. With the discrete fluxes from definition 6.3, the exact solution verifies the system of equations

-div T (ψ T (∇u)) = π T f, (6.19)
that is the continuous counterpart of the scheme (5.4). Comparing equation (6.19) on the exact solution u and (5.4) on the approximation u T , it is obvious that

-div T (ψ T (∇u)) + div T (ϕ D (∇ T δu u T )) = 0
and equivalently

-div T ϕ D (∇ T δu u T ) -ϕ D (∇ T p g p T u) = -div T (R T (u)) , where R T (u) = ψ T (∇u) -ϕ D (∇ T δu p T u) ∈ Q is given in definition 6.
3. Since we take δu T = p T g, using the discrete duality identity (theorem 4.1), the error equation reads

ϕ D (∇ T δu u T ) -ϕ D (∇ T δu p T u), ∇ T δu u T -∇ T δu p T u Q = R T (u), ∇ T δu u T -∇ T δu p T u Q . (6.20)
Under assumption (6.5), the error equation (6.20) proves that

c 3 Ω ∇ T 0 (u T -p T u) p ≤ Ω R T (u) • ∇ T 0 (u T -p T u),
and then, using the inequality of Hölder, (c 3 )

p ′ Ω ∇ T 0 (u T -p T u) p ≤ Ω |R T (u)| p ′ ≤ R 1 T (u) L p ′ (Ω) + R 2 T (u) L p ′ (Ω) p ′ .
And from lemma 6.6 and 6.7, there exists a constant C > 0 that depends on c r (T ) and on the (b i ), the (c i ) and p such that

∇ T 0 (u T -p T u) L p (Ω) ≤ C u W 2,p (Ω) h 1/(p-1)
since p ′ /p = 1/(p -1). The proof is easily completed using lemma 6.8 to get the estimate on ∇u -∇ T p g u T L p (Ω) and theorem 4.2 and lemma 6.9 to get the estimate on up T u L p (Ω) , because 1/(p -1) ≤ 1 (so that h ≤ h 1/(p-1) for h ≤ 1).

7. Numerical tests. We exhibit the efficiency of this 3D DDFV scheme on the linear anisotropic problem ϕ(x, ξ) = K(x)ξ. For all the tests, the source term f and the boundary data g are built in such a way that the solution of (1.1) is a given function u. The accuracy of the scheme is investigated in the L 2 and discrete H 1 norms (from eq. ( 6.2)). The maximum principle is also examined.

The tests are carried out on four families of meshes as illustrated on figure 7.1: some standard cubic and tetrahedrical meshes ( Test 2: it is the test proposed in [START_REF] Brezzi | Mimetic finite differences for elliptic problems[END_REF] where the permeability is strongly heterogeneous and anisotropic and the exact solution is sharp. The data are We observe in tables 7.3-7.6 an order of convergence closed to 2 in L 2 -norm and order 1 convergence in the discrete H 1 norm. This super-convergence is classically observed for finite volume schemes, but it remains an open problem for general meshes, even for 2D-DDFV.

As the exact solution lies for test 1 in [0, 12] and for test 2, 3, 4 in [-1, 1], we observe in table 7.7 that the positivity of the scheme is fulfilled, and that the maximum principle is only achieved asymptotically. In the highly anisotropic and heterogeneous tests 3 and 4, we observe in table 7.8 that neither the positivity, neither the maximum principle hold, as it was already the case for the 2D DDFV schemes and for all the linear schemes (see [START_REF] Herbin | Benchmark on discretization schemes for anisotropic diffusion problems on general grids for anisotropic heterogeneous diffusion problems[END_REF][START_REF] Boyer | Benchmark on anisotropic problems, the ddfv discrete duality finite volumes and m-ddfv schemes[END_REF]). Only nonlinear schemes can ensure the maximum principle in such severe situations ([21, 24, 20, 13]

1 , c 2 >

 12 0, b 1 ∈ L 1 (Ω), b 2 ∈ L p ′ (Ω) such that ϕ(z, ξ) • ξ ≥ c 1 |ξ| pb 1 (z), for all ξ ∈ R 3 , a.e. z ∈ Ω, (1.3) |ϕ(z, ξ)| ≤ c 2 |ξ| p-1 + b 2 (z), for all ξ ∈ R 3 , a.e. z ∈ Ω.(1.4)

Figure 1 . 1 .

 11 Figure 1.1. Various schemes.

  Primary mesh M and a node cell associated to xa.

  Primary mesh M and a face cell associated to xf.

  Primary mesh M and an edge cell associated to xe.

Figure 2 . 1 .

 21 Figure 2.1. 3D views of the 3 meshes for a Cartesian grid.

Figure 2 . 2 .Lemma 2 . 2 .

 2222 Figure 2.2. Interfaces in a diamond cell. Lemma 2.2. For any diamond cell d with vertices x k , x l , x a , x b , x e , x f , we can define (see fig: 1.2 or fig: 2.2)

5. 1 .

 1 Formulation of the scheme. The Discrete Duality Finite Volume scheme is obtained by integrating equation (1.1) on all the control volumes of the three meshes, k ∈ M, a ∈ N , e ∈ E and f ∈ F [16, 10, 3]: the exact solution u verifies for all c ∈ T (ie c = k, a, e, f): -∂c ϕ(s, ∇u(s)) • n c ds = c f (x)dx. (5.1) For any diamond cell d ∈ D, consider the spatial approximation ϕ d : R 3 → R 3 of the flux ϕ defined by

p p- 2

 2 (Ω) and a function b 4 ∈ L p ′ (Ω) such that for all (ξ, η) ∈ R 3 × R 3 and almost every z ∈ Ω,(ϕ(z, ξ)ϕ(z, η)) • (ξη) ≥ c 3 |ξ -η| p ,(6.5)|ϕ(z, ξ)ϕ(z, η)| ≤ c 4 b 3 (z) + |ξ| p-2 + |η| p-2 |ξ -η|,(6.6)and for all ξ ∈ R 3 and almost every z ∈ Ω, ∂ϕ ∂z (z, ξ) ≤ c 5 b 4 (z) + |ξ| p-1 . (6.7)

  3). The approximate flux associated to the projection (p T u, p T g) is exactly ϕ D (∇ T p g p T u) ∈ Q while there are two discrete flux functions associated to the function u, namely the piecewise constant projection of ϕ(x, ∇u(x)) onto the diamond cells, denoted by ϕ D (∇u) = (ϕ d (∇u)) d∈D ∈ Q with ϕ d (∇u) = 1 |d| d ϕ(x, ∇u(x))dx and the function ψ T (∇u) = (ψ d (∇u)) d∈D ∈ Q where the vectors ψ d (∇u) ∈ R 3 are defined uniquely for any diamond cell d ∈ D by the three equationsψ d (∇u) • N kl = F d kl := Skl ϕ(z, ∇u(z)) • n kl dz,(6.9)ψ d (∇u) • N ab = F d ab := Sab ϕ(z, ∇u(z)) • n ab dz,(6.10)ψ d (∇u) • N ef = F d ef := Sef ϕ(z, ∇u(z)) • n ef dz(6.11)(i.e. the numbers F d • are the exact fluxes through the 3 interfaces inside the diamond cell d). The total error of consistency is R T

2 dB 1 0

 21 dz. The estimate of E c is carried out as usual, with the change of variable s = 1t and because |zx c | ≤ h d , and then with the change of variablex = sz + (1s)x c : |E c | ≤ h |B| |H(u)(sz + (1s)x c )| sdsdz ≤ d = 3 is the dimension and B(s) = {sz + (1s)x c , z ∈ B} ⊂ dbecause d is star-shaped with respect to B. Due to the inequality of Hölder, B(s) |H(u)(x)| dx ≤ H(u) L p (d) |B(s)| 1-1/p with |B(s)| = s d |B| and it finally reads

.

  d) and the conclusion holds because h d ≤ c r (T )R d Specifically, E d ≤ C(p) p c r (T ) 3(p+1) h p d u p W 2,p (d) where the constant C(p) > 0 depends only on p: C(p) p = 2 p-1

  figures 7.1(a) and 7.1(b)), a distorted family of meshes proposed in [7] (figure 7.1(c)) and checkerboard-like meshes (figure 7.1(d)) that present a great amount of non conformal faces.

  (a) Mesh 1: Cubes. (b) Mesh 2: Tetrahedra. (c) Mesh 3: Prismes. (d) Mesh 4: Checkerboards.

Figure 7 . 1 .

 71 Figure 7.1. The different meshes. Meshes 2 were generated with TetGen [25], meshes 3 are courtesy of K. Lipnikov and Meshes 4 were generated with PELICANS [19].

  Nb un Nb cv Nb un Nb cv Nb un Nb cv Nb

Test 1 :

 1 in this first test, the exact solution is quadratic and there is a mild anisotropy. The data are , u(x, y, z) = 16(x(1x) + y(1y) + z(1z)).

  y, z) = x 3 y 2 z + x sin(2πxz) sin(2πxy) sin(2πz).Tests 3 and 4: they are built from a rotating and heterogeneous anisotropic permeability with a harmonic solution. The data are , y, z) = sin(2πx) sin(2πy) sin(2πz) and the values of K 1 , K

Table 7 . 1

 71 Number of primary control volumes and number of unknowns.

  2 , K 3 for tests 3 and 4 are given in table 7.2.

		K 1	K 2	K 3
	Test 3	1	0.1	1
	Test 4	1	0.001 10

Table 7 .

 7 2 K 1 and K 2 for tests 3 and 4.

Table 7 . 3

 73 ). Relative L 2 and H 1 errors and rate of convergence for test 1.

			Mesh 1			Mesh 4
	#	• 2	Rate	• H1	Rate	• 2	Rate	• H1	Rate
	1	0.18e+00	-	0.12e+01	-	0.78e+00	-	0.28e+01	-
	2	0.37e-01	2.02 0.49e+00 1.10	0.22e+00 1.62 0.15e+01 0.80
	3	0.24e-01	1.91 0.39e+00 0.96	0.57e-01	1.82 0.77e+00 0.90
	4	0.15e-01	2.10 0.30e+00 1.09	0.14e-01	1.91 0.39e+00 0.95
	5	0.95e-02	1.87 0.25e+00 0.93	-	-	-	-

The authors were partially supported by l'Agence Nationale de la Recherche under grant ANR VFSitCom, BLAN08 2 311650


Dov M Gabbay
email: dov.gabbay@kcl.ac.uk@www.dcs.kcl.ac.uk

Karl Schlechta
email: karl.schlechta@web.de

Critical analysis of the Carmo-Jones system of Contrary-to-Duty obligations *

This paper offers a technical analysis of the contrary to duty system proposed in Carmo-Jones. We offer analysis/simplification/repair of their system and compare it with our own related system.

Introduction

The present paper was inspired by the important paper [START_REF] Carmo | Deontic logic and contrary-to-duties[END_REF] of J.Carmo and A.Jones on contrary-to-duties. In that paper Carmo and Jones present a logical system designed to solve many of the current puzzles of contrary-to-duties. They propose a system with the unary connective O(B) and the binary connective O(B/A) and using these connectives give a detailed case analysis of several contrary-to-duty paradoxes. Gabbay, in his paper [START_REF] Gabbay | Reactive Kripke models and contrary to duty obligations[END_REF] proposed a reactive Kripke semantics approach to contrary-to-duties and made use of the Carmo and Jones paper to draw upon examples and analysis. Gabbay promised in his paper an analysis of the Carmo-Jones approach and a comparison with his own paper. Meanwhile Gabbay and Schlechta developed the reactive and hierarchical approach to conditionals [START_REF] Gabbay | A theory of hierarchical consequence and conditionals[END_REF] as well as a general road map paper for preferential semantics [START_REF] Gabbay | Roadmap for preferential logics[END_REF] and armed with this new arsenal of methods (Carmo-Jones paper was written 10 years ago), we believe we can give a preferential analysis of the Carmo-Jones paper.

Our comments are strictly mathematical. Our own philosophical approach is outlined in [START_REF] Gabbay | A semantics for obligations[END_REF].

The Carmo-Jones system

To model a contrary to duty set of sentences given in a natural language, which avoids paradoxes, we need a logic L and a translation from natural language into L. The translation must be such that whenever the original natural language set is coherent and consistent in our common sense reading of it, its natural formal translation in L is consistent in L (otherwise we get what is referred to as a paradox, relative to L). One such logic L is dyadic modal logic. We have a binary modal operator O(B/A) reading B is obligatory relative to a given A, i.e., we have multiple unary modalities O A dependent on A. Thus we have t |= O(B/A) iff for all s such that tR(A)s holds we have that s |= B.

It stands to reason that condition (5-b) below holds for R(A), namely tR(A)s implies that s is in A (i.e., s |= A), We note that any correct logic L needs axioms for combining formulas of the form O(B/A) with O(¬B/(A ∧ C)). Bearing all of the above in mind, let us examine the Carmo-Jones system. To fix our notation etc, the following is the Carmo-Jones system, regarded formally as a logical system with axioms and semantics as proposed by Carmo-Jones. (We take the liberty to change notation slightly, and will sometimes call the system CJ system.) Alphabet: classical propositional logic, with 5 additional modal operators: 2 a with dual 3 a -the actually necessary/possible (5) ob : P(W ) → P(P(W )) -the "morally good" sets such that for X, Y, Z ⊆ W (5-a) ∅ ∈ ob(X)

(5-b) if Y ∩ X = Z ∩ X, then Y ∈ ob(X) ⇔ Z ∈ ob(X) (5-c) if Y, Z ∈ ob(X), then Y ∩ Z ∈ ob(X) (5-d) if Y ⊆ X ⊆ Z, Y ∈ ob(X), then (Z -X) ∪ Y ∈ ob(Z)
Remark: This results in a form of the Ross paradox: Let X := M ( water plants), Y := M ( water plants and post letter), then (Z -X) ∪ Y is the set of models where the plants are watered and the letter is posted (so far ok), or the plants are not watered. So either do both, or don't water the plants -which does not seem a good obligation. Validity in w is defined (for fixed M) inductively as follows (M (φ) is the set of points where φ holds):

w |= p :⇔ w ∈ V (p) the usual conditions for classical connectives w |= 2 a φ :⇔ av(w) ⊆ M (φ) w |= 2 p φ :⇔ pv(w) ⊆ M (φ) w |= O(φ/ψ) :⇔ M (φ) ∩ M (ψ) = ∅ and ∀X(X ⊆ M (ψ), X ∩ M (φ) = ∅ ⇒ M (φ) ∈ ob(X)) w |= O a φ :⇔ M (φ) ∈ ob(av(w)) and av(w) ∩ M (¬φ) = ∅ w |= O p φ :⇔ M (φ) ∈ ob(pv(w)) and pv(w) ∩ M (¬φ) = ∅ Axiomatics (A) 2 a and 2 p (1) 2 p is a normal modal operator of type KT (2) 2 a is a normal modal operator of type KD (3) 2 p φ → 2 a φ (B) Characterisation of O(./.) (4) ¬O(⊥/ψ) (5) O(φ/ψ) ∧ O(φ ′ /ψ) → O(φ ∧ φ ′ /ψ) (6) O(φ/ψ) → O(φ/φ ∧ ψ) (SA1) (7) If ⊢ ψ ↔ ψ ′ , then ⊢ O(φ/ψ) ↔ O(φ/ψ ′ ) (8) If ⊢ ψ → (φ ↔ φ ′ ), then ⊢ O(φ/ψ) ↔ O(φ ′ /ψ) (C) Relationship between O(./.) and 2 p (9) 3 p O(φ/ψ) → 2 p O(φ/ψ) (10) 3 p (ψ ∧ ψ ′ ∧ φ) ∧ O(φ/ψ) → O(φ/ψ ∧ ψ ′ ) (SA2) (D) Characterization of O a and O p (11) O a φ ∧ O a ψ → O a (φ ∧ ψ) O p φ ∧ O p ψ → O p (φ ∧ ψ) (E) Relationships between O a (O p ) and 2 a (2 p ) (12) 2 a φ → (¬O a φ ∧ ¬O a ¬φ) 2 p φ → (¬O p φ ∧ ¬O p ¬φ) (13) 2 a (φ ↔ ψ) → (O a φ ↔ O a ψ) 2 p (φ ↔ ψ) → (O p φ ↔ O p ψ) (F) Relationships between O(./.), O a (O p ) and 2 a (2 p ) (14) O(φ/ψ) ∧ 2 a ψ ∧ 3 a φ ∧ 3 a ¬φ → O a φ O(φ/ψ) ∧ 2 p ψ ∧ 3 p φ ∧ 3 p ¬φ → O p φ (15) O(φ/ψ) ∧ 3 a (φ ∧ ψ) ∧ 3 a (ψ ∧ ¬φ) → O a (ψ → φ) O(φ/ψ) ∧ 3 p (φ ∧ ψ) ∧ 3 p (ψ ∧ ¬φ) → O p (ψ → φ)

General comments

Methodological discussion

We believe that Carmo and Jones important insight was that to solve contrary-to-duty and other Deontic paradoxes we need a wider family of operators capable of describing a wider context surrounding the problematic paradoxes. We agree with this view wholeheartedly. Gabbay's papers [START_REF] Gabbay | Reactive Kripke models and contrary to duty obligations[END_REF] and [START_REF] Gabbay | Reactive Kripke models and contrary to duty obligations[END_REF] use reactive semantics to create such a context and the present paper will use hierarchical modality to create essentially the same context. See [START_REF] Gabbay | Reactive Kripke models and contrary to duty obligations[END_REF], Example 3.1. Also note that [START_REF] Gabbay | Reactive Kripke models and contrary to duty obligations[END_REF] contains the following text (in the current January 2010 draft of the paper the text is on page 47): "We can now also understand better the approach of Carmo and Jones. Using our terminology, they were implicitly using the cut approach by translating into a richer language with more operators, including some dyadic ones." It would be useful to describe the methodology we use.

Viewed formally, we have here a logical system CJ proposed by Carmo-Jones and a proposed semantics M(CJ) for it, intended to be applied to the contrary-to-duties application area CTD. We want to study it and compare it with our own methodology, and technically simplify/assist/repair/support its formal details. We would like to provide preferential semantics for the Carmo Jones system. How can we do it? Let us list the methodological parameters involved.

2.1.2

The semantics proposed must be compatible with the intended application.

This means that the spirit of the semantics must correspond to the application. We explain by an example. Consider modal logic S4 and assume we are trying to apply it to the analysis of the tenses of natural language.

The phrase " A is true from now on" can be modelled by 2A.

The phrase "John is reading now" i.e. the progressive tense can also be modelled as 2( John is reading). Both examples give rise to modal S4. However the Kripke accessibility relation for S4 is the semantics suitable for the "from now on" linguistic construction, while the McKinsey-Tarski open intervals semantics for S4 is more suitable for the analysis of the progressive. (Sentences A are assigned intervals W (A) and 2A is read as the topological interior of W (A).) Carmo-Jones indeed offer an analysis of the compatibility of their system in Section 6 of their paper. We will examine that.

Soundness and completeness

We ask whether the system is sound and complete for the semantics. (Carmo and Jones claimed only soundness.) If not, what axioms do we need to add to the system or what changes do we propose to the system to obtain correspondence? We will find that CJ is not complete for the proposed semantics.

Discrepancies inside the CJ system

A closer look at semantics and proof theory reveals a certain asymmetry in the treatment of unary vs. binary obligations, and elsewhere:

3 Our proposal for a modified CJ system

The following is the proposed modified CJ system.

Our system in a preferential framework

Take any system for finite ranked structures.

• A ranked structure is defined in Definition 5.4 (page 9) and Definition 5.7 (page 12).

• Logical conditions are defined in Definition 5.3 (page 8).

• Take now a characterisation, see Proposition 5 (page 13).

• For definiteness, we choose (µ∅), (µ =), (µ ⊆).

• We still have to add the accessibility relation R, which chooses subsets -this is trivial, as everything is definable.

Our system in a modal framework

The language of obligations has usually the flavour of modal languages, whereas the language describing preferential structures is usually different in decisive aspects.

If we accept that the description of obligations is suitably given by ranked structures, then we have ready characterizations available.

So our task will be to adapt them to fit reasonably well into a modal logic framework. We discuss this now.

We will suppose that we have an entry point u into the structure, from which all models are visible through relation R, with modal operators 2 and 3. R is supposed to be transitive. The first hurdle is to express minimality in modal terms. Boutilier and Lamarre have shown how to do it, see [START_REF] Boutilier | Conditional Logics of Normality as Modal Systems[END_REF] and [START_REF] Lamarre | S4 as the conditional logic of nonmonotonicity[END_REF].

(It was criticized in [START_REF] Makinson | Five faces of minimality[END_REF], but this criticism does not concern our approach as we use different relations for accessibility and minimization.)

We introduce a new modal operator working with the minimality relation, say we call the (irreflexive) relation R ′ , and the corresponding operators 2 ′ and 3 ′ . Being a minimal model of α can now be expressed by

m |= α ∧ ¬3 ′ α. So α ∼ | β reads: u |= 2((α ∧ ¬3 ′ α) → β) -everywhere, if m is a minimal model of α, then β holds.
(RatM ) e.g. is translated to

u |= 2 (φ ∧ ¬3 ′ φ) → ψ ∧ 3 φ ∧ ¬3 ′ φ ∧ ψ ′ → 2 (φ ∧ ψ ′ ∧ ¬3 ′ (φ ∧ ψ ′ )) → ψ .
The second hurdle is to handle subsets defined by accessibility from a given model m. In above example, all was done from u, with formulas. But we also have to make sure that we can handle expressions like "in all best models among those accessible from m φ holds". The set of all those accessible models corresponds to some φ m , and then we have to choose the best among them. In particular, we have to make sure that the axioms of our system hold not only for the models of some formulas seen from u, but also when those formulas are defined by the set of models accessible from some model m.

Let R(m) := {n : mRn}, and µ(X) be the minimal models of X.

Suppose we want to say now:

If mRm ′ (so R(m ′ ) ⊆ R(m) by transitivity), and R(m ′ ) ∩ µ(R(m)) = ∅, then µ(R(m ′ )) = R(m ′ ) ∩ µ(R(m))
. How can we express this with modal formulas? If we write m |= 2φ, then we know that φ holds everywhere in R(m), but φ might not be precise enough to describe R(m), e.g. φ might be TRUE.

We introduce an auxiliary modal relation R -with operators 2 -and 3 -s.t. mR -m ′ iff not(mRm ′ ). (If R is not reflexive, R -will not be either, and we change the definition accordingly. -Our notation differs from the one of Boutilier, we chose it as we do not know how to create his symbols.)

We can now characterize R(m) by φ m : m |= 2φ m ∧ ¬3 -φ m -everywhere φ m holds, and at no point we cannot reach from m, φ m holds. We can now express that φ holds in the minimal models of R(m) by

m |= (2φ m ∧ ¬3 -φ m ) ∧ 2((φ m ∧ ¬3 ′ φ m ) → φ).
Finally, we can express e.g.

(AN D) α ∼ | φ, α ∼ | φ ′ ⇒ α ∼ | φ ∧ φ ′
in the case where α is defined by some R(m) as follows:

u |= 2 (2φ m ∧ ¬3 -φ m ) ∧ 2((φ m ∧ ¬3 ′ φ m ) → φ) ∧ 2((φ m ∧ ¬3 ′ φ m ) → φ ′ ) → 2((φ m ∧ ¬3 ′ φ m ) → φ ∧ φ ′ ) .
(3) It presents a descriptive semantics.

(4) It puts the operators in the object language and uses a modal logic language, as usual in the field.

• The article on A-ranked semantics, [GS08d]:

(1) It contains a relatively exhaustive semantics for the ideal cases in contrary-to-duty obligations.

-The A-ranked semantics allows us to express that a whole hierarchy of obligations (if . . . . possible, then . . . .; if not, but . . . ., then . . . .; . . . .) is satisfied, i.e. the agent "does his best". This hierarchy is directly built into the semantics, which is a multi-layered, semi-ranked structure, which can also be re-used in other contexts. -The article contains a sound and complete characterization of the semantics with full proofs.

-The language is that of usual nonmonotonic logics, i.e. rules are given in the meta-language.

(2) Paradoxa like the Ross paradox are not treated at all, we only treat the ideal case, and not individual obligations.

(3) The additional accessibility relation is added without changing the overall language to a modal flavour.

• The article on the semantics of obligations, [GS08g]:

(1) In this article, present a discussion of elementary properties a notion of derivation of obligations should have.

(2) There, we are not at all concerned about more complicated situations, involving accessibility etc.

(3) We also see rankedness somewhat sceptically there.

• The present article [START_REF]Unary obligations are dependent on accessibility relations av and pv, binary ones are not[END_REF] We work with a ranked structure describing ideal situations as usual.

(2) We fully integrate the underlying logic for the ideal cases in a modal framework, using an idea by Boutelier and Lamarre, and extending it with a complementary relation to precisely characterize the successor sets.

Definitions and proofs

Definition 5.1

(1) We use P to denote the power set operator, Π{X i : i ∈ I} := {g : g : I → {X i : i ∈ I}, ∀i ∈ I.g(i) ∈ X i } is the general cartesian product, card(X) shall denote the cardinality of X, and V the set-theoretic universe we work in -the class of all sets. Given a set of pairs X , and a set X, we denote by X ↾ X := { x, i ∈ X : x ∈ X}. When the context is clear, we will sometime simply write X for X ↾ X. (The intended use is for preferential structures, where x will be a point (intention: a classical propositional model), and i an index, permitting copies of logically identical points.)

(2) A ⊆ B will denote that A is a subset of B or equal to B, and A ⊂ B that A is a proper subset of B, likewise for A ⊇ B and

A ⊃ B.
Given some fixed set U we work in, and X ⊆ U, then C(X) := U -X .

(3) If Y ⊆ P(X) for some X, we say that Y satisfies (∩) iff it is closed under finite intersections, ( ) iff it is closed under arbitrary intersections, (∪) iff it is closed under finite unions, ( ) iff it is closed under arbitrary unions, (C) iff it is closed under complementation, (-) iff it is closed under set difference.

(4) We will sometimes write A = B C for:

A = B, or A = C, or A = B ∪ C.
We make ample and tacit use of the Axiom of Choice.

Definition 5.2

(1) We work here in a classical propositional language L, a theory T will be an arbitrary set of formulas. Formulas will often be named φ, ψ, etc., theories T, S, etc. v(L) will be the set of propositional variables of L.

F (L) will be the set of formulas of L. M L will be the set of (classical) models for L, M (T ) or M T is the set of models of T, likewise M (φ) for a formula φ.

(2) D L := {M (T ) : T a theory in L}, the set of def inable model sets. Note that, in classical propositional logic, ∅, M L ∈ D L , D L contains singletons, is closed under arbitrary intersections and finite unions.

An operation f : Y → P(M L ) for Y ⊆ P(M L ) is called def inability preserving , (dp) or (µdp) in short, iff for all X ∈ D L ∩Y f (X) ∈ D L .

We will also use (µdp) for binary functions f : Y × Y → P(M L ) -as needed for theory revision -with the obvious meaning.

(3) ⊢ will be classical derivability, and T := {φ : T ⊢ φ}, the closure of T under ⊢ .

(4) Con(.) will stand for classical consistency, so Con(φ) will mean that φ is classical consistent, likewise for Con(T ). Con(T, T ′ ) will stand for Con(T ∪ T ′ ), etc.

(5) Given a consequence relation ∼ | , we define

T := {φ : T ∼ | φ}.
(There is no fear of confusion with T , as it just is not useful to close twice under classical logic.)

(6) T ∨ T ′ := {φ ∨ φ ′ : φ ∈ T, φ ′ ∈ T ′ }. (7) If X ⊆ M L , then T h(X) := {φ : X |= φ}, likewise for T h(m) , m ∈ M L .
(|= will usually be classical validity.)

Definition 5.3
We introduce here formally a list of properties of set functions on the algebraic side, and their corresponding logical rules on the other side. Putting them in parallel facilitates orientation, especially when considering representation problems. We show, wherever adequate, in parallel the formula version in the left column, the theory version in the middle column, and the semantical or algebraic counterpart in the right column. The algebraic counterpart gives conditions for a function f : Y → P(U ), where U is some set, and Y ⊆ P(U ).

The development in two directions, vertically with often increasing strength, horizontally connecting proof theory with semantics motivates the presentation in a table. The table is split in two, as one table would be too big to print. The first table contains the basic rules, the second one those about cumulativity and rationality.

Precise connections between the columns are given in Proposition 5.2 (page 9). When the formula version is not commonly used, we omit it, as we normally work only with the theory version.

A and B in the right hand side column stand for M (φ) for some formula φ, whereas X, Y stand for M (T ) for some theory T .

• (P R) is also called inf inite conditionalization We choose this name for its central role for preferential structures (P R) or (µP R).

• The system of rules (AN D) (OR) (LLE) (RW ) (SC) (CP ) (CM ) (CU M ) is also called system P (for preferential). Adding (RatM ) gives the system R (for rationality or rankedness). Roughly: Smooth preferential structures generate logics satisfying system P , while ranked structures generate logics satisfying system R.

• A logic satisfying (REF ), (ResM ), and (CU T ) is called a consequence relation.

• (LLE) and(CCL) will hold automatically, whenever we work with model sets.

• (AN D) is obviously closely related to filters, and corresponds to closure under finite intersections. (RW ) corresponds to upward closure of filters. More precisely, validity of both depend on the definition, and the direction we consider. Given f and (µ ⊆), f (X) ⊆ X generates a principal filter:

{X ′ ⊆ X : f (X) ⊆ X ′ }, with the definition: If X = M (T ), then T ∼ | φ iff f (X) ⊆ M (φ).
Validity of (AN D) and (RW ) are then trivial.

Conversely, we can define for X = M (T )

X := {X ′ ⊆ X : ∃φ(X ′ = X ∩ M (φ) and T ∼ | φ)}.
(AN D) then makes X closed under finite intersections, and (RW ) makes X upward closed. This is in the infinite case usually not yet a filter, as not all subsets of X need to be definable this way. In this case, we complete X by adding all X ′′ such that there is X ′ ⊆ X ′′ ⊆ X, X ′ ∈ X . Alternatively, we can define

X := {X ′ ⊆ X : {X ∩ M (φ) : T ∼ | φ} ⊆ X ′ }.
• (SC) corresponds to the choice of a subset.

• (CP ) is somewhat delicate, as it presupposes that the chosen model set is non-empty. This might fail in the presence of ever better choices, without ideal ones; the problem is addressed by the limit versions.

• (P R) is an infinitary version of one half of the deduction theorem: Let T stand for φ, T ′ for ψ, and

φ ∧ ψ ∼ | σ, so φ ∼ | ψ → σ, but (ψ → σ) ∧ ψ ⊢ σ.
Table 1: Basic logical and semantic laws

Basics (AN D) (AN D) Closure under φ ∼ | ψ, φ ∼ | ψ ′ ⇒ T ∼ | ψ, T ∼ | ψ ′ ⇒ finite φ ∼ | ψ ∧ ψ ′ T ∼ | ψ ∧ ψ ′ intersection (OR) (OR) (µOR) φ ∼ | ψ, φ ′ ∼ | ψ ⇒ T ∩ T ′ ⊆ T ∨ T ′ f (X ∪ Y ) ⊆ f (X) ∪ f (Y ) φ ∨ φ ′ ∼ | ψ (wOR) (wOR) (µwOR) φ ∼ | ψ, φ ′ ⊢ ψ ⇒ T ∩ T ′ ⊆ T ∨ T ′ f (X ∪ Y ) ⊆ f (X) ∪ Y φ ∨ φ ′ ∼ | ψ (disjOR) (disjOR) (µdisjOR) φ ⊢ ¬φ ′ , φ ∼ | ψ, ¬Con(T ∪ T ′ ) ⇒ X ∩ Y = ∅ ⇒ φ ′ ∼ | ψ ⇒ φ ∨ φ ′ ∼ | ψ T ∩ T ′ ⊆ T ∨ T ′ f (X ∪ Y ) ⊆ f (X) ∪ f (Y ) (LLE) (LLE) Left Logical Equivalence ⊢ φ ↔ φ ′ , φ ∼ | ψ ⇒ T = T ′ ⇒ T = T ′ trivially true φ ′ ∼ | ψ (RW ) Right Weakening (RW ) upward closure φ ∼ | ψ, ⊢ ψ → ψ ′ ⇒ T ∼ | ψ, ⊢ ψ → ψ ′ ⇒ φ ∼ | ψ ′ T ∼ | ψ ′ (CCL) Classical Closure (CCL) T is classically trivially true closed (SC) Supraclassicality (SC) (µ ⊆) φ ⊢ ψ ⇒ φ ∼ | ψ T ⊆ T f (X) ⊆ X (REF ) Reflexivity T ∪ {α} ∼ | α (CP ) (CP ) (µ∅) Consistency Preservation φ ∼ | ⊥ ⇒ φ ⊢ ⊥ T ∼ | ⊥ ⇒ T ⊢ ⊥ f (X) = ∅ ⇒ X = ∅ (µ∅f in) X = ∅ ⇒ f (X) = ∅ for finite X (P R) (µP R) φ ∧ φ ′ ⊆ φ ∪ {φ ′ } T ∪ T ′ ⊆ T ∪ T ′ X ⊆ Y ⇒ f (Y ) ∩ X ⊆ f (X) (µP R ′ ) f (X) ∩ Y ⊆ f (X ∩ Y ) (CUT ) (CUT ) (µCUT ) T ∼ | α; T ∪ {α} ∼ | β ⇒ T ⊆ T ′ ⊆ T ⇒ f (X) ⊆ Y ⊆ X ⇒ T ∼ | β T ′ ⊆ T f (X) ⊆ f (Y )
• (CU M ) (whose more interesting half in our context is (CM )) may best be seen as normal use of lemmas: We have worked hard and found some lemmas. Now we can take a rest, and come back again with our new lemmas. Adding them to the axioms will neither add new theorems, nor prevent old ones to hold. (This is, of course, a meta-level argument concerning an object level rule. But also object level rules should -at least generally -have an intuitive justification, which will then come from a meta-level argument.)

Fact 5.1

The following table is to be read as follows: If the left hand side holds for some function f : Y → P(U ), and the auxiliary properties noted in the middle also hold for f or Y, then the right hand side will hold, too -and conversely. "sing." will stand for: "Y contains singletons" Proposition 5.2

The following table "Logical and algebraic rules" is to be read as follows: If f satisfies a property in the right hand side, then -provided the additional properties noted in the middle for ⇐ hold, too -∼ | will satisfy the property in the left hand side. If "T = φ" is noted in the table, this means that, if one of the theories (the one named the same way in Definition 5.3 (page 8)) is equivalent to a formula, we do not need (µdp).

Definition 5.4

(µCM) φ ∼ | ψ, φ ∼ | ψ ′ ⇒ T ⊆ T ′ ⊆ T ⇒ f (X) ⊆ Y ⊆ X ⇒ φ ∧ ψ ∼ | ψ ′ T ⊆ T ′ f (Y ) ⊆ f (X) or (ResM) (µResM) Restricted Monotony f (X) ⊆ A ∩ B ⇒ T ∼ | α, β ⇒ T ∪ {α} ∼ | β f (X ∩ A) ⊆ B (CUM) Cumulativity (CUM) (µCUM) φ ∼ | ψ ⇒ T ⊆ T ′ ⊆ T ⇒ f (X) ⊆ Y ⊆ X ⇒ (φ ∼ | ψ ′ ⇔ φ ∧ ψ ∼ | ψ ′ ) T = T ′ f (Y ) = f (X) (⊆⊇) (µ ⊆⊇) T ⊆ T ′ , T ′ ⊆ T ⇒ f (X) ⊆ Y, f (Y ) ⊆ X ⇒ T ′ = T f (X) = f (Y ) Rationality (RatM) Rational Monotony (RatM) (µRatM) φ ∼ | ψ, φ ∼ | ¬ψ ′ ⇒ Con(T ∪ T ′ ), T ⊢ T ′ ⇒ X ⊆ Y, X ∩ f (Y ) = ∅ ⇒ φ ∧ ψ ′ ∼ | ψ T ⊇ T ′ ∪ T f (X) ⊆ f (Y ) ∩ X (RatM =) (µ =) Con(T ∪ T ′ ), T ⊢ T ′ ⇒ X ⊆ Y, X ∩ f (Y ) = ∅ ⇒ T = T ′ ∪ T f (X) = f (Y ) ∩ X (Log = ′ ) (µ = ′ ) Con(T ′ ∪ T ) ⇒ f (Y ) ∩ X = ∅ ⇒ T ∪ T ′ = T ′ ∪ T f (Y ∩ X) = f (Y ) ∩ X (Log ) (µ ) T ∨ T ′ is one of f (X ∪ Y ) is one of T , or T ′ , or T ∩ T ′ f (X), f (Y ) or f (X) ∪ f (Y ) (by (CCL)) (Log∪) (µ∪) Con(T ′ ∪ T ), ¬Con(T ′ ∪ T ) f (Y ) ∩ (X -f (X)) = ∅ ⇒ ⇒ ¬Con(T ∨ T ′ ∪ T ′ ) f (X ∪ Y ) ∩ Y = ∅ (Log∪ ′ ) (µ∪ ′ ) Con(T ′ ∪ T ), ¬Con(T ′ ∪ T ) f (Y ) ∩ (X -f (X)) = ∅ ⇒ ⇒ T ∨ T ′ = T f (X ∪ Y ) = f (X) (µ ∈) a ∈ X -f (X) ⇒ ∃b ∈ X.a ∈ f ({a, b})
Fix U = ∅, and consider arbitrary X. Note that this X has not necessarily anything to do with U, or U below. Thus, the functions µ M below are in principle functions from V to V -where V is the set theoretical universe we work in. Note that we work here often with copies of elements (or models). In other areas of logic, most authors work with valuation functions. Both definitions -copies or valuation functions -are equivalent, a copy x, i can be seen as a state x, i with valuation x. In the beginning of research on preferential structures, the notion of copies was widely used, whereas e.g., [KLM90] used that of valuation functions. There is perhaps a weak justification of the former terminology. In modal logic, even if two states have the same valid classical formulas, they might still be distinguishable by their valid modal formulas. But this depends on the fact that modality is in the object language. In most work on preferential stuctures, the consequence relation is outside the object language, so different states with same valuation are in a stronger sense copies of each other.

(1) P ref erential models or structures.

(1.1) The version without copies:

A pair M := U, ≺ with U an arbitrary set, and ≺ an arbitrary binary relation on U is called a pref erential model or structure.

(1.2) The version with copies :

A pair M := U, ≺ with U an arbitrary set of pairs, and ≺ an arbitrary binary relation on U is called a pref erential model or structure. If x, i ∈ U, then x is intended to be an element of U, and i the index of the copy. We sometimes also need copies of the relation ≺ . We will then replace ≺ by one or several arrows α attacking nonminimal elements, e.g., x ≺ y will be written α : x → y , x, i ≺ y, i will be written α : x, i → y, i , and finally we might have α, k : x → y and α, k : x, i → y, i , etc.

(2) M inimal elements, the functions µ M

(2.1) The version without copies: Let M := U, ≺ , and define

µ M (X) := {x ∈ X : x ∈ U ∧ ¬∃x ′ ∈ X ∩ U.x ′ ≺ x}. µ M (X) is called the set of minimal elements of X (in M).
Thus, µ M (X) is the set of elements such that there is no smaller one in X. (2.2) The version with copies:

Let M := U, ≺ be as above. Define

µ M (X) := {x ∈ X : ∃ x, i ∈ U.¬∃ x ′ , i ′ ∈ U(x ′ ∈ X ∧ x ′ , i ′ ′ ≺ x, i )}.
Thus, µ M (X) is the projection on the first coordinate of the set of elements such that there is no smaller one in X. Again, by abuse of language, we say that µ M (X) is the set of minimal elements of X in the structure. If the context is clear, we will also write just µ.

We sometimes say that x, i " kills" or " minimizes" y, j if x, i ≺ y, j . By abuse of language we also say a set X kills or minimizes a set Y if for all y, j ∈ U, y ∈ Y there is x, i ∈ U, x ∈ X s.t. x, i ≺ y, j .

Table 3: Interdependencies of algebraic rules .

Basics (1.1) (µP R) ⇒ (∩) + (µ ⊆) (µP R ′ ) (1.2) ⇐ (2.1) (µP R) ⇒ (µ ⊆) (µOR) (2.2) ⇐ (µ ⊆) + (-) (2.3) ⇒ (µ ⊆) (µwOR) (2.4) ⇐ (µ ⊆) + (-) (3) (µP R) ⇒ (µCUT ) (4) (µ ⊆) + (µ ⊆⊇) + (µCUM) ⇒ (µP R) +(µRatM) + (∩) Cumulativity (5.1) (µCM) ⇒ (∩) + (µ ⊆) (µResM) (5.2) ⇐ (infin.) (6) (µCM) + (µCUT ) ⇔ (µCUM) (7) (µ ⊆) + (µ ⊆⊇) ⇒ (µCUM) (8) (µ ⊆) + (µCUM) + (∩) ⇒ (µ ⊆⊇) (9) (µ ⊆) + (µCUM) ⇒ (µ ⊆⊇) Rationality (10) (µRatM) + (µP R) ⇒ (µ =) (11) (µ =) ⇒ (µP R) + (µRatM) (12.1) (µ =) ⇒ (∩) + (µ ⊆) (µ = ′ ) (12.2) ⇐ (13) (µ ⊆) + (µ =) ⇒ (∪) (µ∪) (14) (µ ⊆) + (µ∅) + (µ =) ⇒ (∪) (µ ), (µ∪ ′ ), (µCUM) (15) (µ ⊆) + (µ ) ⇒ (-) of Y (µ =) (16) (µ ) + (µ ∈) + (µP R)+ ⇒ (∪) + sing. (µ =) (µ ⊆) (17) (µCUM) + (µ =) ⇒ (∪) + sing. (µ ∈) (18) (µCUM) + (µ =) + (µ ⊆) ⇒ (∪) (µ ) (19) (µP R) + (µCUM) + (µ )
⇒ sufficient, (µ =). e.g., true in DL (20)

(µ ⊆) + (µP R) + (µ =) ⇒ (µ ) (21) (µ ⊆) + (µP R) + (µ ) ⇒ (without (-)) (µ =) (22) (µ ⊆) + (µP R) + (µ )+ ⇒ (µ ∈) (µ =) + (µ∪)
(thus not representable by ranked structures)

+ (µCU M ) ⇐ smooth ⇒ (µdp) (LLE) + (RW )+ (SC) + (P R)+ (CU M ) ⇒ (∪) ⇐ (∪) ⇒ without (µdp) (µ ⊆) + (µP R) + (µCU M ) ⇐ smooth+transitive ⇒ (µdp) (LLE) + (RW )+ (SC) + (P R)+ (CU M ) ⇒ (∪) ⇐ (∪)
⇒ without (µdp) ⇔ without (µdp)

using "small" exception sets any "normal" characterization of any size let B := {x ∈ Z: there is some x, i ∈ X , s.t. for no x, j ∈ X x, j ≺ x, i },

(µ ⊆) + (µ =) + (µP R)+ ⇐ ranked, ≥ 1 copy (µ = ′ ) + (µ ) + (µ∪)+ (µ∪ ′ ) + (µ ∈) + (µRatM ) (µ ⊆) + (µ =) + (µP R)+ ⇒ ranked (µ∪) + (µ ∈) (µ ⊆) + (µ =) + (µ∅) ⇔, (
let C := {x ∈ Z: there is no x, i ∈ X }.
Let c i : i < κ be an enumeration of C. We introduce for each such c i ω many copies c i , n : n < ω into X ′ , put all c i , n above all elements in X , and order the c i , n by c i , n ≺ ′ c i ′ , n ′ :⇔ (i = i ′ and n > n ′ ) or i > i ′ . Thus, all c i , n are comparable.

If a ∈ A, then there are infinitely many copies of a in X , as X was cycle-free, we put them all into X ′ . If b ∈ B, we choose exactly one such minimal element b, m (i.e., there is no b, n ≺ b, m ) into X ′ , and omit all other elements. (For definiteness, assume in all applications m = 0.) For all elements from A and B, we take the restriction of the order ≺ of X . This is the new structure Z ′ .

Obviously, adding the c i , n does not introduce cycles, irreflexivity and rankedness are preserved. Moreover, any substructure of a cycle-free, irreflexive, ranked structure also has these properties, so Z ′ is 1 -∞ over Z, ranked and free of cycles. We show that Z and Z ′ are equivalent. Let then X ⊆ Z, we have to prove µ

(X) = µ ′ (X) (µ := µ Z , µ ′ := µ Z ′ ). Let z ∈ X -µ(X). If z ∈ C or z ∈ A, then z ∈ µ ′ (X). If z ∈ B, let
z, m be the chosen element. As z ∈ µ(X), there is x ∈ X s.t. some x, j ≺ z, m . x cannot be in C. If x ∈ A, then also x, j ≺ ′ z, m . If x ∈ B, then there is some x, k also in X ′ . x, j ≺ x, k is impossible. If x, k ≺ x, j , then z, m ≻ x, k by transitivity. If x, k ⊥ x, j , then also z, m ≻ x, k by rankedness. In any case, z, m ≻ ′ x, k , and thus z ∈ µ ′ (X).

Let z ∈ Xµ ′ (X). If z ∈ C or z ∈ A, then z ∈ µ(X). Let z ∈ B, and some x, j ≺ ′ z, m . x cannot be in C, as they were sorted on top, so x, j exists in X too and x, j ≺ z, m . But if any other z, i is also minimal in Z among the z, k , then by rankedness also x, j ≺ z, i , as z, i ⊥ z, m , so z ∈ µ(X). 2

We give a generalized abstract nonsense result, taken from [START_REF] Lehmann | Distance Semantics for Belief Revision[END_REF], which must be part of the folklore:

Lemma 5.8 Given a set X and a binary relation R on X, there exists a total preorder (i.e., a total, reflexive, transitive relation) S on X that extends R such that ∀x, y ∈ X(xSy, ySx ⇒ xR * y) where R * is the reflexive and transitive closure of R. < represents µ and is Y-smooth: Let a ∈ Aµ(A). By (µ∅), ∃b ∈ µ(A), so bRa, but (by above argument) not aRb, so bSa, but not aSb, so b < a, so a ∈ Aµ < (A), and, as b will then be < -minimal (see the next sentence), < is Y-smooth. Let a ∈ µ(A), then for all a ′ ∈ A aRa', so aSa', so there is no a ′ ∈ A a ′ < a, so a ∈ µ < (A). 2

Proof

2 p

 2 with dual 3 p -the potentially necessary/possible O(./.) a dyadic deontic operator O a (.) monadic deontic operator: actual obligations O p (.) monadic deontic operator: potenial obligations Semantics: A model M = W, av, pv, ob, V where (1) W = ∅ (2) V an assignment function (3) av : W → P(W ) (the actually accessible worlds) such that (3-a) av(w) = ∅ (4) pv : W → P(W ) (the potentially accessible worlds) such that (4-a) av(w) ⊆ pv(w) (4-b) w ∈ pv(w)

  Let a logic ∼ | satisfy (LLE) and (CCL), and define a function f : D L → D L by f (M (T )) := M (T ). Then f is well defined, satisfies (µdp), and T = T h(f (M (T ))). If ∼ | satisfies a rule in the left hand side, then -provided the additional properties noted in the middle for ⇒ hold, too -f will satisfy the property in the right hand side. Conversely, if f : Y → P(M L ) is a function, with D L ⊆ Y, and we define a logic ∼ | by T := T h(f (M (T ))), then ∼ | satisfies (LLE) and (CCL). If f satisfies (µdp), then f (M (T )) = M (T ).

  ) + (µ =) + (µ∅f in)+ ⇔, (∪), singletons ranked, smooth, (µ ∈) ≥ 1 copy + (µ∅f in) (µ ⊆) + (µP R) + (µ )+ ⇔, (∪), singletons ranked ⇒ without (µdp) (RatM ), (RatM =), (µ∪) + (µ ∈)

  Define x ≡ y iff xR * y and yR * x. The relation ≡ is an equivalence relation. Let [x] be the equivalence class of x under ≡ . Define [x] [y] iff xR * y. The definition of does not depend on the representatives x and y chosen. The relation on equivalence classes is a partial order. Let ≤ be any total order on these equivalence classes that extends . Define xSy iff [x] ≤ [y]. The relation S is total (since ≤ is total) and transitive (since ≤ is transitive) and is therefore a total preorder. It extends R by the definition of and the fact that ≤ extends . Suppose now xSy and ySx. We have [x] ≤ [y] and [y] ≤ [x] and therefore [x] = [y] by antisymmetry. Therefore x ≡ y and xR * y. 2Proposition 5.9 Let Y ⊆ P(U ) be closed under finite unions. Then (µ ⊆), (µ∅), (µ =) characterize ranked structures for which for all X ∈ Y X = ∅ ⇒ µ < (X) = ∅ hold, i.e., (µ ⊆), (µ∅), (µ =) hold in such structures for µ < , and if they hold for some µ, we can find a ranked relation < on U s.t. µ = µ < . Moreover, the structure can be choosen Y-smooth.ProofCompleteness: Note that by Fact 5.1 (page 9) (3) + (4) (µ ), (µ∪), (µ∪ ′ ) hold.Define aRb iff ∃A ∈ Y(a ∈ µ(A), b ∈ A) or a = b. R is reflexive and transitive: Suppose aRb, bRc, let a ∈ µ(A), b ∈ A, b ∈ µ(B), c ∈ B. We show a ∈ µ(A ∪ B). By (µ ) a ∈ µ(A ∪ B) or b ∈ µ(A ∪ B). Suppose b ∈ µ(A ∪ B), then µ(A ∪ B) ∩ A = ∅, so by (µ =) µ(A ∪ B) ∩ A = µ(A), so a ∈ µ(A ∪ B). Moreover, a ∈ µ(A), b ∈ Aµ(A) ⇒ ¬(bRa) : Suppose there is B s.t. b ∈ µ(B), a ∈ B. Then by (µ∪) µ(A ∪ B) ∩ B = ∅, and by (µ∪ ′ ) µ(A ∪ B) = µ(A), but a ∈ µ(A) ∩ B, contradiction. Let by Lemma 5.8 (page 14) S be a total, transitive, reflexive relation on U which extends R s.t. xSy, ySx ⇒ xRy (recall that R is transitive and reflexive). Define a < b iff aSb, but not bSa. If a⊥b (i.e., neither a < b nor b < a), then, by totality of S, aSb and bSa. < is ranked: If c < a⊥b, then by transitivity of S cSb, but if bSc, then again by transitivity of S aSc. Similarly for c > a⊥b.

Table 2 :

 2 Cumulativity and Rationality

		Cumulativity
	(CM) Cautious Monotony	(CM)

Table 4 :

 4 Logical and algebraic rules

			Basics
	(1.1) (1.2)	(OR)	⇒ ⇐	(µOR)
	(2.1) (disjOR) (2.2)	⇒ ⇐	(µdisjOR)
	(3.1)	(wOR)	⇒	(µwOR)
	(3.2)		⇐
	(4.1) (4.2)	(SC)	⇒ ⇐	(µ ⊆)
	(5.1)	(CP )	⇒	(µ∅)
	(5.2)		⇐
	(6.1)	(P R)	⇒	(µP R)
	(6.2)		⇐ (µdp) + (µ ⊆)
	(6.3) (6.4) (6.5)	(P R)	⇐ -(µdp) ⇐ (µ ⊆) T ′ = φ ⇐ T ′ = φ	(µP R ′ )
	(7.1)	(CUT )	⇒	(µCUT )
	(7.2)		⇐
			Cumulativity
	(8.1)	(CM)	⇒	(µCM)
	(8.2)		⇐
	(9.1) (ResM) (9.2)	⇒ ⇐	(µResM)
	(10.1)	(⊆⊇)	⇒	(µ ⊆⊇)
	(10.2)		⇐
	(11.1) (CUM) (11.2)	⇒ ⇐	(µCUM)
			Rationality
	(12.1) (RatM) (12.2)	⇒ ⇐ (µdp)	(µRatM)
	(12.3) (12.4)		⇐ -(µdp) ⇐
			T = φ
	(13.1) (RatM =)	⇒	(µ =)
	(13.2) (13.3)		⇐ (µdp) ⇐ -(µdp)
	(13.4)		⇐
	(14.1) (Log = ′ )	T = φ ⇒	(µ = ′ )
	(14.2)		⇐ (µdp)
	(14.3) (14.4)		⇐ -(µdp) ⇐ T = φ
	(15.1) (Log ) (15.2)	⇒ ⇐	(µ )
	(16.1) (Log∪) ⇒ (µ ⊆) + (µ =)	(µ∪)
	(16.2) (16.3) (17.1) (Log∪ ′ ) ⇒ (µ ⊆) + (µ =) ⇐ (µdp) ⇐ -(µdp) (17.2) ⇐ (µdp)	(µ∪ ′ )
	(17.3)		⇐ -(µdp)

Table 5 :

 5 Preferential representation

	Logic	(LLE) + (RW )+	(SC) + (P R)		any "normal"	characterization	of any size	(LLE) + (RW )+	(SC) + (P R)		using "small"	exception sets
		⇒ (µdp)	⇐	⇒ without (µdp)	⇔ without (µdp)			⇒ (µdp)	⇐	⇒ without (µdp)	⇔ without (µdp)
	Pref.Structure	general						transitive
		⇐	⇒					⇐	⇒
	µ-function	(µ ⊆) + (µP R)						(µ ⊆) + (µP R)			(µ ⊆) + (µP R)

Acknowledgements

We thank A.Herzig, Toulouse, and L.v.d.Torre, Luxembourg, for very helpful discussions.

Simplifications of the CJ system

We make now some simplifications which will help us to understand the CJ system. [START_REF]Unary obligations are dependent on accessibility relations av and pv, binary ones are not[END_REF] We assume the language is finite, thus we will not have any problems with non-definable model sets -see e.g. [START_REF] Gabbay | Roadmap for preferential logics[END_REF] for an illustration of what can happen otherwise. [START_REF]3 Incompleteness of the CJ system Example 2[END_REF] We assume that ob(X) ⊆ P(X). This is justified by the following fact, which follows immediately from the system of CJ, condition 5-b): Fact 2.1 If A ∈ ob(X), A ⊆ X, B ⊆ W -X, then A ∪ B ∈ ob(X). Conversely, if A ∈ ob(X), then A ∩ X ∈ ob(X).

Thus, what is outside X, does not matter, and we can concentrate on the inside of X. (Of course, the validity condition has then to be modified, M (B) ∈ ob(X) will be replaced by: There is X ′ ∈ ob(X), X ′ = M (B) ∩ X.

By 5-c), ob is closed under finite intersection, by overall finiteness, there is thus a smallest (by (⊆)) A ∈ ob(X). We call this µ(X). Thus, µ(X) ⊆ X, which is condition (µ ⊆). (If the language is not finite, we would have to work with the limit version. As we work with formulas only, this would not present a fundamental problem, see [START_REF] Schlechta | Coherent Systems[END_REF].)

We thus have that µ satisfies (µ ⊆) and (µP R), and we know that this suffices for a representation by preferential structures -see e.g. [START_REF] Schlechta | Some results on classical preferential models[END_REF] and Section 5 (page 7). Thus, the basic choice function ob is preferential for unary O. Note that (µ ⊆) [START_REF] Gabbay | Roadmap for preferential logics[END_REF] and Section 5 (page 7).

When we look now at the truth conditions for O a and O i , we see that we first go to the accessible worlds -av(w) or pv(w) -and check whether µ(av(w)) ⊆ M (A) respectively µ(pv(w)) ⊆ M (A) (and whether ¬A is possible). Thus, in preferential terms, whether av(w) ∼ | A, but av(w) ⊢ A.

The case of O(B/A) is a bit more complicated and is partly dissociated from O a and O i .

We said already above that O(B/A) is independent from av and pv, and from w.

Second, and more importantly, the condition for O(B/A) implies a converse of (µOR) or (µP R) :

(1) Setting X := M (A), we have µ(M (A)) ⊆ M (B),

(2) as all sets are definable, we can choose B s.

We thus have -if O(B/A) holds -together with (µP R) that (µ =) holds, i.e.

By 5-a) µ(X) = ∅, so (µ∅) holds, too, and by [START_REF] Schlechta | Coherent Systems[END_REF], see also [START_REF] Gabbay | Roadmap for preferential logics[END_REF] and Section 5 (page 7), we know that such µ can be represented by a ranked smooth structure where all elements occur in one copy only. Thus, the basic choice function ob is ranked for binary O(B/A).

Suggested modifications of the CJ system

(1) We assume finiteness (see above)

(2) We work with the smallest element of ob(X) (see above)

(3) We use only one accessibility relation (or operation) a. This is justified, as we are mainly interested in formal properties here.

(4) We make both O and O(./.) dependent on a. So validity of O(./.) depends on w, too. This eliminates one discrepancy between O and O(./.).

(5) We allow both O and O(./.) to be trivial. We could argue here philosophically, e.g.: if you are unable to kill your grandmother, should you then not any longer be obliged not to kill her? (No laws for jail inmates?) But we do this rather by laziness, to simplify the basic machinery. This eliminates a second discrepancy.

(6) We take rankedness as a basic condition for ob, so it does not depend any more on validity of some O(./.).

We can now describe the basic ingredients of our suggested system:

(1) We take a finite ranked structure, together with -for simplicity -one additional relation of accessibility.

(2) Binary and unary obligations will be represented the same way, i.e. the "best" situations will have lowest rank.

(3) To correspond to the usual way of speaking in deontic logic, we translate this into a modal language, using techniques invented by Boutelier et al.

(

This results in the following system.

M is also called injective or 1-copy , iff there is always at most one copy x, i for each x. Note that the existence of copies corresponds to a non-injective labelling function -as is often used in nonclassical logic, e.g., modal logic.

We say that M is transitive, irref lexive, etc., iff ≺ is. Note that µ(X) might well be empty, even if X is not.

Definition 5.5

We define the consequence relation of a preferential structure for a given propositional language L.

(1) (1.1) If m is a classical model of a language L, we say by abuse of language m, i |= φ iff m |= φ, and if X is a set of such pairs, that

2) If M is a preferential structure, and X is a set of L-models for a classical propositional language L, or a set of pairs m, i , where the m are such models, we call M a classical pref erential structure or model.

(2) V alidity in a preferential structure, or the semantical consequence relation defined by such a structure: Let M be as above.

We define:

(3) M will be called def inability preserving iff for all

As µ M is defined on D L , but need by no means always result in some new definable set, this is (and reveals itself as a quite strong) additional property.

Definition 5. [START_REF] |= O | B/A) implies ⊢ A → B. 7. is trivial[END_REF] Let Y ⊆ P(U ). (In applications to logic, Y will be D L .)

A preferential structure M is called Y-smooth iff for every X ∈ Y every element x ∈ X is either minimal in X or above an element, which is minimal in X. More precisely:

(1) The version without copies: If x ∈ X ∈ Y, then either x ∈ µ(X) or there is x ′ ∈ µ(X).x ′ ≺ x.

(2) The version with copies: If x ∈ X ∈ Y, and x, i ∈ U, then either there is no

(Writing down all details here again might make it easier to read applications of the definition later on.)

When considering the models of a language L, M will be called smooth iff it is D L -smooth ; D L is the default. Obviously, the richer the set Y is, the stronger the condition Y-smoothness will be.

Fact 5. [START_REF]Binary obligations postulate additional properties of the basic choice function ob[END_REF] Let ≺ be an irreflexive, binary relation on X, then the following two conditions are equivalent:

(1) There is Ω and an irreflexive, total, binary relation ≺ ′ on Ω and a function f

(2) Let x, y, z ∈ X and x⊥y wrt. ≺ (i.e., neither x ≺ y nor y ≺ x), then z ≺ x ⇒ z ≺ y and x ≺ z ⇒ y ≺ z.

Definition 5.7

We call an irreflexive, binary relation ≺ on X, which satisfies (1) (equivalently (2)) of Fact 5.3 (page 12) , ranked . By abuse of language, we also call a preferential structure X, ≺ ranked, iff ≺ is.

Fact 5.4

If ≺ on X is ranked, and free of cycles, then ≺ is transitive.

Proof

Let x ≺ y ≺ z. If x⊥z, then y ≻ z, resulting in a cycle of length 2. If z ≺ x, then we have a cycle of length 3. So x ≺ z. 2

Remark 5.5 Note that (µ = ′ ) is very close to (RatM ) : (RatM ) says:

depends how many B there are, if f (A) is some such B, the fit is perfect). (µ∪) and (µ∪ ′ ) : All minimal copies of elements in f (Y ) have the same rank. If some y ∈ f (Y ) has all its minimal copies killed by an element x ∈ X, by rankedness, x kills the rest, (µ ∈) : If f ({a}) = ∅, we are done. Take the minimal copies of a in {a}, they are all killed by one element in X.

(µ ) : Case f (X) = ∅ : If below every copy of y ∈ Y there is a copy of some x ∈ X, then f

. By rankedness, y ≺ x, or y⊥x, y ≺ x is impossible, as y ∈ X, so y⊥x, and

The following table summarizes representation by preferential structures. "singletons" means that the domain must contain all singletons, "1 copy" or "≥ 1 copy" means that the structure may contain only 1 copy for each point, or several, "(µ∅)" etc. for the preferential structure mean that the µ-function of the structure has to satisfy this property. Note that the following table is one (the more difficult) half of a full representation result for preferential structures. It shows equivalence between certain abstract conditions for model choice functions and certain preferential structures. The other halfequivalence between certain logical rules and certain abstract conditions for model choice functions -are summarized in Definition 5.3 (page 8) and shown in Proposition 5.2 (page 9). Definition 5.8 Let Z = X , ≺ be a preferential structure. Call Z 1 -∞ over Z, iff for all x ∈ Z there are exactly one or infinitely many copies of x, i.e., for all x ∈ Z {u ∈ X : u = x, i for some i} has cardinality 1 or ≥ ω.

Lemma 5.7 Let Z = X , ≺ be a preferential structure and f : Y → P(Z) with Y ⊆ P(Z) be represented by Z, i.e., for X ∈ Y f (X) = µ Z (X), and Z be ranked and free of cycles. Then there is a structure Z ′ , 1 -∞ over Z, ranked and free of cycles, which also represents f.

Proof

We construct Z ′ = X ′ , ≺ ′ .

Let A := {x ∈ Z: there is some x, i ∈ X , but for all x, i ∈ X there is x, j ∈ X with x, j ≺ x, i },