����������� ������ 58 (2006), 111–117

UDK 515.122.4

���������� ������ ��� research paper

CONTINUOUS REPRESENTATION OF INTERVAL ORDERS BY MEANS OF DECREASING SCALES

Gianni Bosi

Abstract. We characterize the representability of an interval order on a topological space through a pair of continuous real-valued functions which in addition represent two total preorders associated to the given interval order. Such a continuous representation is obtained by using the notion of a decreasing scale.

1. Introduction

Interval orders are reflexive and total binary relations which are not transitive in general. Such a model may be viewed as the simplest one fulfilling these requirements, in the sense that interval orders may be fully represented by a pair of real-valued functions. The real representability of interval orders was first deeply studied by Fishburn (see e.g. Fishburn [18,19], and then considered by other authors (see e.g. Bridges [9–11], Bridges and Mehta [13], and Oloriz et al. [22]).

Some authors were concerned with the existence of a (semi)continuous representation of an interval order on a topological space (see e.g. Bridges [12], Candeal et al. [15], Chateauneuf [16], Bosi [3], Bosi and Isler [4], and Bosi et al. [5]). In particular, Chateauneuf [16] provided a characterization of the existence of a pair of continuous real-valued functions representing an interval order on a connected topological space. A characterization of the existence of a continuous representation of an interval order on a topological space has been recently obtained by Bosi et al. [6] by using a suitable notion of order separability, called i.o.separability.

In this paper we provide a characterization of the existence of a pair (U, V) of continuous real-valued functions representing an interval order ≾ on a topological space (X, τ) (in the sense that, for all x, y ∈ X, x ≾ y if and only if U(x) ≤ V (y)). The functions U and V may be chosen so that they represent two total preorders associated to the interval order ≾. In order to obtain such a characterization, we use the notion of a decreasing scale which was first introduced by Burgess and Fitzpatrick [14], and then considered by other authors (see e.g. Herden [20], Alcantud et al. [1], Bosi and Mehta [7] and Bosi and Zuanon [8]).

AMS Subject Classification: 06A06; 91B16.

Keywords and phrases: Interval order; continuous numerical representation; decreasing scale.

2. Notation and preliminaries

An interval order ≾ on an arbitrary nonempty set X is a binary relation on X which is reflexive and in addition verifies the following condition for all x, y, z, w ∈ X:

(x ≾ z) and (y ≾ w) ⇒ (x ≾ w) or (y ≾ z).

The strict part of a given interval order ≾ will be denoted by ≺ (i.e., for all x, y ∈ X, x ≺ y if and only if not(y ≾ x)). An interval order ≾ on a set X is necessarily total, in the sense that, for any two elements x, y ∈ X, either x ≾ y or y ≾ x (see Oloriz et al. [22]).

If ≾ is an interval order on a set X, then we may consider the binary relations ≾^{∗} and ≾^{∗∗} on X defined as follows:

x ≾^{∗} y ⇔ (z ≾ x ⇒ z ≾ y for every z ∈ X) (x, y ∈ X)
x ≾^{∗∗} y ⇔ (y ≾ z ⇒ x ≾ z for every z ∈ X) (x, y ∈ X)

Fishburn [19] proved that the binary relations ≾^{∗} and ≾^{∗∗} associated to any interval order ≾ on a set X are total preorders on X (i.e., they are reflexive, transitive and total). It is clear that, for any two elements x, y ∈ X, if either x ≾^{∗} y or x ≾^{∗∗} y, then we have that x ≾ y.

Obviously every total preorder ≾ on a set X is an interval order on X. In this case, we have that ≾=≾^{∗}=≾^{∗∗}. The importance of interval orders in economics lies on the fact that they are not transitive in general.

A total preorder ≾ on a set X is representable by means of a real-valued function U on X if, for all x, y ∈ X:

x ≾ y ⇔ U(x) ≤ U(y).

We also say that U is a utility function for the total preorder ≾ on the set X.

An interval order ≾ on a set X is said to be representable through a pair (U, V) of real-valued functions on X if, for all x, y ∈ X:

x ≾ y ⇔ U(x) ≤ V (y).

If ≾ is an interval order on a set X, then a subset G of X is said to be ≾-decreasing if, for all x, y ∈ X, x ≾ y and y ∈ G imply x ∈ G.

An interval order ≾ on a topological space (X, τ) is said to be upper (lower) semicontinuous if L_{≺}(x) = {y ∈ X : y ≺ x} (U_{≺}(x) = {y ∈ X : x ≺ y}) is a τ-open subset of X for every x ∈ X. If ≾ is both upper and lower semicontinuous, then it is said to be continuous .

3. Continuous representability

We present a characterization of the existence of a pair of continuous realvalued functions representing an interval order on a topological space, where the two functions are utilities for two total preorders naturally associated with the given interval order.

Theorem 3.1. The following conditions are equivalent for an interval order ≾ on a topological space (X, τ):

i) The interval order ≾ is representable through a pair of continuous real-valued functions (U, V) with values in [0, 1], where U is a representation for the total preorder ≾^{∗∗} and V is a representation for the total preorder ≾^{∗};

ii) There exist two families {G_{r}^{∗}}_{r∈Q∩]0,1]} and {G_{r}^{∗∗}}_{r∈Q∩]0,1]} of open subsets of (X, τ) with G_{1}^{∗} = G_{1}^{∗∗} = X satisfying the following conditions:

(a) x ≾ y and y ∈ G_{r}^{∗} imply x ∈ G_{r}^{∗∗} for every x, y ∈ X and r ∈ Q∩]0, 1];

(b) G_{r}^{∗} is ≾^{∗}-decreasing and G_{r}^{∗∗} is ≾^{∗∗}-decreasing for every r ∈ Q∩]0, 1];

(c) \overline{G_{r_{1}}^{∗}} ⊆ G_{r_{2}}^{∗} and \overline{G_{r_{1}}^{∗∗}} ⊆ G_{r_{2}}^{∗∗} for every r_{1}, r_{2} ∈ Q∩]0, 1] such that r_{1} < r_{2};

(d) for every x, y ∈ X such that x ≺ y there exist r_{1}, r_{2} ∈ Q∩]0, 1[ such that r_{1} < r_{2}, x ∈ G_{r_{1}}^{∗}, y ∉ G_{r_{2}}^{∗∗}.

Proof. i) ⇒ ii). If (U, V) is a representation of the interval order ≾ with the indicated properties, then just define G_{r}^{∗} = V^{−1}([0, r[), G_{r}^{∗∗} = U^{−1}([0, r[) for every r ∈ Q∩]0, 1[, and G_{1}^{∗} = G_{1}^{∗∗} = X in order to immediately verify that {G_{r}^{∗}}_{r∈Q∩]0,1]} and {G_{r}^{∗∗}}_{r∈Q∩]0,1]} are two families of open subsets of (X, τ) satisfying conditions (a) through (d).

ii) ⇒ i). Assume that the above condition ii) holds. Define two functions U, V : X → [0, 1] as follows:

U(x) = inf{r ∈ Q∩]0, 1] : x ∈ G_{r}^{∗∗}} (x ∈ X),
V (x) = inf{r ∈ Q∩]0, 1] : x ∈ G_{r}^{∗}} (x ∈ X).

We claim that (U, V) is a pair of continuous functions on (X, τ) with values in [0, 1] representing the interval order ≾ where U is a representation for the total preorder ≾^{∗∗} and V is a representation for the total preorder ≾^{∗}.

From the definition of the functions U and V, it is clear that they both take values in [0, 1]. Let us first show that the pair (U, V) represents the interval order ≾. Consider any two elements x, y ∈ X such that x ≾ y, and observe that, for every r ∈ Q∩]0, 1], if y ∈ G_{r}^{∗} then it must be that x ∈ G_{r}^{∗∗} by the above condition (a). Hence it must be that U(x) ≤ V (y) from the definition of U and V. Now consider any two elements x, y ∈ X such that y ≺ x. Then by condition (d), there exist r_{1}, r_{2} ∈ Q∩]0, 1] such that r_{1} < r_{2}, y ∈ G_{r_{1}}^{∗}, x ∉ G_{r_{2}}^{∗∗}. Hence we have that V (y) ≤ r_{1} < r_{2} ≤ U(x), which obviously implies that V (y) < U(x).

Let us now prove that V is a representation for the total preorder ≾^{∗}. From the first part of condition (b) we have that G_{r}^{∗} is a ≾^{∗} decreasing subset of X for every r ∈ Q∩]0, 1]. Hence if x, y are any two elements of X such that x ≾^{∗} y, then it must be that V (x) ≤ V (y) from the definition of V. Now consider any two elements x, y ∈ X such that y ≺^{∗} x. Hence there exists another element z ∈ X such that y ≺ z ≾ x. So, by condition (d), there exist r_{1}, r_{2} ∈ Q∩]0, 1] such that r_{1} < r_{2}, y ∈ G_{r_{1}}^{∗}, z ∉ G_{r_{2}}^{∗∗}. By condition (a), we have that x ∉ G_{r_{2}}^{∗} since z ≾ x. Finally, we may guarantee the existence of r_{1}, r_{2} ∈ Q∩]0, 1] such that r_{1} < r_{2}, y ∈ G_{r_{1}}^{∗}, x ∉ G_{r_{2}}^{∗}. Hence from the definition of V, we have that V (y) ≤ r_{1} < r_{2} ≤ V (x) which obviously implies that V (y) < V (x).

Analogously it may be shown that U is a representation for the total preorder ≾^{∗∗}.

To conclude the proof, let us show that U and V are both continuous functions by condition (c). We only prove that U is continuous. Then analogous arguments will show that also V is continuous. Let us first prove that U is upper semicontinuous. Consider any x ∈ X, and α ∈ R∩]0, 1] such that U(x) < α. Then from the definition of U, there exists r ∈ Q∩]0, 1] such that U(x) ≤ r < α, x ∈ G_{r}^{∗∗}. Observe that U(z) ≥ α (z ∈ X) implies that U(z) > r which in turn implies that z ∉ G_{r}^{∗∗}. Hence G_{r}^{∗∗} is an open subset of X containing x such that U(z) < α for every z ∈ G_{r}^{∗∗}. In order to show that U is lower semicontinuous, let us first prove that

U(x) = inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} for every x ∈ X.

Since G_{r}^{∗∗} ⊆ \overline{G_{r}^{∗∗}} for every r ∈ Q∩]0, 1], it is clear that, for every x ∈ X,

inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} ≤ inf\{r ∈ Q∩]0, 1] : x ∈ G_{r}\}.

Now assume that there exists x ∈ X with

inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} < inf\{r ∈ Q∩]0, 1] : x ∈ G_{r}^{∗∗}\}.

Consider r_{1}, r_{2} ∈ Q∩]0, 1] such that

inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} < r_{1} < r_{2} < inf\{r ∈ Q∩]0, 1] : x ∈ G_{r}^{∗∗}\}.

Then we have that x ∈ \overline{G_{r_{1}}^{∗∗}}, x ∉ G_{r_{2}}^{∗∗}, and this is contradictory, since \overline{G_{r_{1}}^{∗∗}} ⊆ G_{r_{2}}^{∗∗}. So it must be that, for every x ∈ X,

inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} = inf\{r ∈ Q∩]0, 1] : x ∈ G_{r}^{∗∗}\}.

Now consider any x ∈ X, and any α ∈ R∩]0, 1] such that α < U(x). Further let r_{1}, r_{2} ∈ Q∩]0, 1] be such that α < r_{1} < r_{2} < U(x). Then we have that x ∉ \overline{G_{r_{1}}^{∗∗}} because otherwise x ∈ \overline{G_{r_{1}}^{∗∗}} implies that x ∈ G_{r_{2}}^{∗∗} and this contradicts the fact that U(x) > r_{2}. Observe that U(z) ≤ α (z ∈ X) implies that U(z) < r_{1} which in turn implies that z ∈ \overline{G_{r_{1}}^{∗∗}} since U(x) = inf\{r ∈ Q∩]0, 1] : x ∈ \overline{G_{r}^{∗∗}}\} for every x ∈ X. Hence X \ \overline{G_{r_{1}}^{∗∗}} is an open subset of X containing x such that α < U(z) for every z ∈ X \ \overline{G_{r_{1}}^{∗∗}}. This consideration completes the proof.

Remark 3.2. The family {G_{r}^{∗}}_{r∈Q∩]0,1]} is a ≾^{∗}-decreasing scale according to the definition introduced by Burgess and Fitzpatrick [14].

As an application of the previous characterization, in the following proposition we present a generalization of the Theorem in Chateauneuf [16]. Chateauneuf showed that a strongly separable interval order ≾ on a connected topological space (X, τ) is representable through a pair of continuous real-valued functions (U, V), where U is a representation for the total preorder ≾^{∗∗} and V is a representation for the total preorder ≾^{∗}, provided that the total preorders ≾^{∗} and ≾^{∗∗} are both continuous.

We recall that an interval order ≾ on a set X is said to be strongly separable if there exists a countable set D ⊆ X such that, for every x, y ∈ X with x ≺ y, there exists d_{1}, d_{2} ∈ D with x ≺ d_{1} ≾ d_{2} ≺ y. D is said to be an order dense subset of X (see Chateauneuf [16]).

Observe that, in contrast to the Chateauneuf Representation Theorem, ours does not need any connectedness assumption on the topological space. The following proposition was already proved by Bosi [3] by using the proof of the existence of a continuous utility function provided by Jaffray [21].

Proposition 3.3. Let ≾ be a strongly separable interval order on a topological space (X, τ), and assume that the total preorders ≾^{∗} and ≾^{∗∗} are both continuous. Then the interval order ≾ is representable through a pair of continuous real-valued functions (U, V) with values in [0, 1], where U is a representation for the total preorder ≾^{∗∗} and V is a representation for the total preorder ≾^{∗}.

Proof. Let ≾ be a strongly separable interval order on a topological space (X, τ), and assume that the associated total preorders ≾^{∗} and ≾^{∗∗} are both continuous. Then from the Proposition in Chateauneuf [16], we have that ≾ is continuous. Further strong separability of ≾ implies order separability of ≾^{∗} and ≾^{∗∗}. In particular, if D is an order dense subset of X, then for all x, y ∈ X with x ≺^{∗∗} y there exists d ∈ D with x ≺^{∗∗} d ≺^{∗∗} y. Without loss of generality, we may assume that (D, ≾^{∗∗}) is actually a totally ordered set (or a chain) without extreme points. Therefore by using considerations in Birkhoff [2] and following a construction analogous to Construction 3.3 in Alcantud et al. [1], we may conclude that there exists an order-preserving function f: (D, ≾^{∗∗}) → (Q∩]0, 1[, ≤). Further we may assume that the mapping f is onto.

For reader’s convenience we recall that any countable chain (C, ⪯) is order isomorphic with a subchain of (Q, ≤) (see Theorem 22 on page 200 in Birkhoff [2]) and in particular order isomorphic with (Q, ≤) if (C, ⪯) is dense in itself and has neither a minimal nor a maximal element (see Theorem 23 on page 200 in Birkhoff [2]). Therefore we may conclude that any countable chain (C, ⪯) with the above properties is also order isomorphic with (Q∩]0, 1[, ≤).

Let us now go back to our case and consider an order-preserving function f: (D, ≾^{∗∗}) → (Q∩]0, 1[, ≤) which is also onto. If f^{−1}(r) = d (r ∈ Q∩]0, 1[), then define

G_{r}^{∗} = L_{≺}(d), G_{r}^{∗∗} = L_{≺^{∗∗}}(d) (r ∈ Q∩]0, 1[),

and set G_{1}^{∗} = G_{1}^{∗∗} = X. We claim that {G_{r}^{∗}}_{r∈Q∩]0,1]} and {G_{r}^{∗∗}}_{r∈Q∩]0,1]} are two families of subsets of X satisfying condition ii) of Theorem 3.1. It is clear that G_{r}^{∗} is open and ≾^{∗}-decreasing, and G_{r}^{∗∗} is open and ≾^{∗∗}-decreasing for every r ∈ Q∩]0, 1], so that condition (b) holds. In order to show that condition (a) is verified, just observe that, for every d ∈ D, if x ≾ y and y ≺ d, then x ≺^{∗∗} d. In order to prove that condition (c) holds, observe that for all d_{1}, d_{2} ∈ D such that d_{1} ≺^{∗∗} d_{2} there exists z ∈ X such that d_{1} ≾ z ≺ d_{2}, and therefore we have that

L_{≺}(d_{1}) ⊆ \overline{L_{≺}(d_{1})} ⊆ L_{≾^{∗}}(z) ⊆ L_{≺}(d_{2}),
L_{≺^{∗∗}}(d_{1}) ⊆ \overline{L_{≺^{∗∗}}(d_{1})} ⊆ L_{≾^{∗∗}}(d_{1}) ⊆ L_{≺^{∗∗}}(d_{2}),

where L_{≾^{∗}}(z) = {w ∈ X : w ≾^{∗} z} and L_{≾^{∗∗}}(d_{1}) = {w ∈ X : w ≾^{∗∗} d_{1}} are closed subsets of X. Finally, condition (d) of Theorem 3.1 holds, since strong separability of the interval order ≾ implies that for all x, y ∈ X such that x ≺ y there exist d_{1}, d_{2} ∈ D such that x ≺ d_{1} ≺^{∗∗} d_{2} ≺^{∗∗} y, and therefore x ∈ L_{≺}(d_{1}) and y ∉ L_{≺^{∗∗}}(d_{2}). This consideration completes the proof.

Acknowledgments. I wish to thank an anonymous referee for many helpful suggestions.

REFERENCES

[1] J.C.R. Alcantud, G. Bosi, M.J. Campión, J.C. Candeal, E. Induráin and C. Rodríguez-Palmero, Continuous utility functions through scales, (2006), submitted.

[2] G. Birkhoff, Lattice Theory, American Mathematical Society, Providence, 1967.

[3] G. Bosi, Continuous representations of interval orders based on induced preorders, Riv. Mat. Sci. economiche e sociali, XVIII, I (1995), 75–82.

[4] G. Bosi and R. Isler, Representing preferences with nontransitive indifference by a single real-valued function, J. Math. Economics 24 (1995), 621–631.

[5] G. Bosi, J.C. Candeal, E. Induráin, E. Oloriz and M. Zudaire, Numerical representations of interval orders, Order 18 (2001), 171–190.

[6] G. Bosi, J.C. Candeal and E. Induráin, Natural topologies for interval-ordered structures and the continuous representation problem, (2005), preprint.

[7] G. Bosi and G. B. Mehta, Existence of a semicontinuous or continuous utility function: a unified approach and an elementary proof, J. Math. Economics 38 (2002), 311–328.

[8] G. Bosi and M. Zuanon, Continuous representability of homothetic preorders by means of sublinear order-preserving functions, Math. Soc. Sci. 45 (2003), 333–341.

[9] D.S. Bridges, A numerical representation of preferences with intransitive indifference, J. Math. Economics 11 (1983), 25–42.

[10] D.S. Bridges, Numerical representation of intransitive preferences on a countable set, J. Economic Theory 30 (1983), 213–217.

[11] D.S. Bridges, Representing interval orders by a single real-valued function, J. Economic Theory 36 (1985), 149–155.

[12] D.S. Bridges, Numerical representation of interval orders on a topological space, J. Economic Theory 38 (1986), 160–166.

[13] D.S. Bridges and G.B. Mehta, Representations of Preference Orderings, Springer-Verlag, Berlin, 1995.

[14] D.C.J. Burgess and M. Fitzpatrick, On separation axioms for certain types of ordered topological space, Math. Proc. Cam. Phil. Soc. 82 (1977), 59–65.

[15] J.C. Candeal, E. Induráin and M. Zudaire, Continuous representability of interval orders, Applied General Topology 5 (2004), 213–230.

[16] A. Chateauneuf, Continuous representation of a preference relation on a connected topological space, J. Math. Economics 16 (1987), 139–146.

[17] G. Debreu, Continuity properties of Paretian utility, Int. Economic Review 5 (1964), 285– [18] P.C. Fishburn, Intransitive indifference with unequal indifference intervals, J. Math. Psy-

chology 7 (1970), 144–149.

[19] P.C. Fishburn, Interval Orders and Interval Graphs, Wiley, New York, 1985.

[20] G. Herden, On the existence of utility functions, Math. Soc. Sciences 17 (1989), 297–313.

[21] J.Y. Jaffray, Existence of a continuous utility function: an elementary proof, Econometrica 43 (1975), 981–983.

[22] E. Oloriz, J.C. Candeal and E. Induráin, Representability of interval orders, J. Economic Theory 78 (1998), 219-227.

(received 14.02.2005, in revised form 05.09.2005)

Dipartimento di Matematica Applicata “Bruno de Finetti”, Università di Trieste, Piazzale Europa 1, 34127 Trieste, Italy

E-mail: giannibo@econ.units.it