induagt.dvi


@
Applied General Topology

c© Universidad Politécnica de Valencia

Volume 5, No. 2, 2005

pp. 213-230

Continuous representability of interval orders

J. C. Candeal, E. Induráin, and M. Zudaire1

Abstract. In the framework of the analysis of orderings whose as-
sociated indifference relation is not necessarily transitive, we study the

structure of an interval order, and its representability through a pair of

continuous real-valued functions. Inspired in recent characterizations of

the representability of interval orders, we obtain new results concern-

ing the existence of continuous real-valued representations. Classical

results are also restated in a unified framework.

2000 AMS Classification: 54F05, 06A06.

Keywords: Orderings on a set. Interval orders. Numerical representations
of orderings. Continuous representations of orderings.

1. Introduction

Dealing with different classes of orderings ≺ defined on a nonempty set X,
the concept of an interval order was introduced by Peter C. Fishburn [17] in
contexts of Economic Theory, in order to build models of preferences whose
associated indifference may fail to be transitive. (See also Fishburn [18], or
Bosi and Isler [4]). A very complete and informative study of interval orders
appears in Chapter 6 of Bridges and Mehta [6].

An interval order ≺ defined on a set X is representable if there exists a
pair of real-valued functions u, v : X −→ R such that x ≺ y ⇐⇒ v(x) <
u(y) (x, y ∈ X).

The question of finding a complete characterization of the representability of
interval orders was solved by Fishburn [20] (see also Fishburn [21], Theorem 5
on p. 135). A different characterization was obtained by Doignon et al. [14].
Furthermore, a new alternative solution using only one ordinal condition has
been recently obtained by Olóriz et al. [27]. Some further characterizations
have appeared in Bosi et al. [3].

1A substantial part of this work comes from the Ph. D. of M. Zudaire made under the
advisement of J. C. Candeal and E. Induráin.



214 J. C. Candeal, E. Induráin and M. Zudaire

To deal with numerical representations of interval orders three main tech-
niques have been used in the literature:

i) The first technique (see e.g. Bridges and Mehta [6], pp. 88 and ff.),
associates to each element of the set X where the interval order ≺ has
been defined, two suitable subsets A(x) and B(x) of natural numbers
in a way that x ≺ y ⇐⇒ B(x) ( A(y).

ii) The second technique, used in Bosi and Isler [4], is based on measure
theory. The functions u, v that represent the interval order are related
to the measures of lower and upper contour sets, in some orderings
related to ≺, of the elements of X.

iii) The third technique, introduced in Olóriz et al. [27], is based on the
theory of functional equations. The idea is to construct a bivariate map
F : X × X −→ R such that, for instance, x ≺ y ⇐⇒ F(x, y) > 0.
In the case of an interval order such functions F should also verify a
characteristic functional equation, namely the functional equation of
separability:

F(x, y) + F(y, z) = F(x, z) + F(y, y) (x, y, z ∈ X).

Paying attention to continuity we will be looking for representations (u, v)
of an interval ordered structure (X, ≺) such that u and v are continuous (with
respect to a given topology τ on X and the usual Euclidean topology on R).
In Chateauneuf [11] a characterization of the continuous representability of an
interval order was given for the particular case of a connected topological space
X.

The purpose of the present paper is twofold:

Our first task is to introduce new characterizations of the continuous re-
presentability of an interval order, comparing our results with previous ones
existing in the literature (see Chateauneuf [11], Bridges and Mehta [6]), and
looking for a standard and unified notation.

Our second task is to adapt the main techniques that have been considered
to get numerical representations of interval orders to obtain characterizations
of the continuous representability.

2. Previous concepts

Let X be a nonempty set. In what follows “≺” will denote an asymmetric
binary relation defined on a nonempty set X. Associated to ≺ we will also
consider the binary relations “-” and ”∼”, respectively defined as x - y ⇐⇒
¬(y ≺ x) and x ∼ y ⇐⇒ x - y , y - x. The relation ≺ is usually called strict
preference. The relation - is said to be the weak preference, and ∼ is called
the indifference, associated to ≺. The opposite ordering ≺op of ≺ is defined by
x ≺op y ⇐⇒ y ≺ x. Given x ∈ X, the sets L(x) = {y ∈ X : y ≺ x} and
U(x) = {y ∈ X : x ≺ y} are called, respectively, the lower contour set and
the upper contour set relative to ≺.



Continuous representability of interval orders 215

Definition 2.1. The binary relation ≺ is said to be an interval order if (x ≺
y , a ≺ b) =⇒ either x ≺ b , or else a ≺ y (or both). An interval order
≺ is said to be a semiorder if in addition a ≺ b ≺ c =⇒ a ≺ d or else d ≺
c (a, b, c, d ∈ X).

Observe that because ≺ is asymmetric, if it is an interval order then it must
be transitive. Notice also that ≺ being an interval order, the associated relations
- and ∼ may fail to be transitive. An example is the relation ≺ defined on the
real line R as x ≺ y ⇐⇒ x + 1 < y. However an interval order ≺ is always
pseudotransitive: That is x ≺ y - z ≺ t =⇒ x ≺ t (x, y, z, t ∈ X).

It is straightforward to see that:

For an asymmetric binary relation ≺ on X, pseudotransitivity is equivalent
to the fact of ≺ being an interval order.

Moreover:

An asymmetric binary relation ≺ defined on X is a semiorder if and only
if it satisfies the condition of generalized pseudotransitivity, namely, for every
x, y, z, t ∈ X the following three conditions hold true:

1. x ≺ y - z ≺ t =⇒ x ≺ t,
2. x - y ≺ z ≺ t =⇒ x ≺ t,
3. x ≺ y ≺ z - t =⇒ x ≺ t.

(See Gensemer [24] for details).

An interval order ≺ defined on X is said to be representable if there exist
two real-valued functions u, v : X −→ R such that x ≺ y ⇐⇒ v(x) <
u(y) (x, y ∈ X). Since ≺ is asymmetric, this is equivalent to associate to
each element x ∈ X a real-interval (that eventually may collapse to a single
point), Ix = [u(x), v(x)]. Thus x ≺ y if and only if Ix is located on the left
of Iy, and Ix does not meet Iy. This kind of “interval-representation” gave
raise to the nomenclature of interval order. However not every interval order
is representable (see e.g. Bosi et al. [3] for details).

A semiorder ≺ defined on X is said to be representable if there exist a
real-valued function u : X −→ R and a non-negative real number α (called
threshold) such that x ≺ y ⇐⇒ u(x) + α < u(y). Observe that this is a
particular case of representation of an interval order, in which v(x) can be
defined as u(x) + α (x ∈ X). Observe also that this is equivalent to associate
to each element x ∈ X a real-interval Ix = [u(x), u(x) + α]. In this case, all the
intervals have the same length α. Obviously all them will collapse to a single
point if and only if α = 0. (See Fishburn [20], Gensemer [22, 23, 24, 25] or
Candeal et al. [10] for more details).



216 J. C. Candeal, E. Induráin and M. Zudaire

Following Fishburn [17, 19] we shall associate to an interval order ≺ two
new binary relations, respectively denoted by ≺∗ and ≺∗∗ and defined by x ≺∗

y ⇐⇒ x ≺ z - y for some z ∈ X (x, y ∈ X), and, similarly, x ≺∗∗

y ⇐⇒ x - z ≺ y for some z ∈ X (x, y ∈ X). Define the relation
x -∗ y ⇐⇒ ¬(y ≺∗ x) and x -∗∗ y ⇐⇒ ¬(y ≺∗∗ x) (x, y ∈ X). Then it is
straightforward to see that x -∗ y ⇐⇒ (y ≺ z =⇒ x ≺ z (z ∈ X)) and
similarly x -∗∗ y ⇐⇒ (z ≺ x =⇒ z ≺ y (z ∈ X)). Observe also that
in terms of contour sets, it follows that x -∗ y ⇐⇒ U(y) ⊆ U(x) and also
x -∗∗ y ⇐⇒ L(x) ⊆ L(y) (x, y ∈ X).

A preorder - defined on a nonempty set X is a reflexive and transitive
binary relation defined on X. If it is also complete (i.e., either x - y or else
y - x for every x, y ∈ X), - is said to be a total preorder. A total preorder
- is said to be representable if there exists a real-valued function, usually
called utility function, u : X −→ R such that x - y ⇐⇒ u(x) ≤ u(y). If
x ≺ y ⇐⇒ ¬(y - x) and x ∼ y ⇐⇒ x - y - x (x, y ∈ X), then
a representable total preorder clearly corresponds to a representation of the
weak preference - associated to a semiorder ≺ for the special case in which the
threshold α equals zero. An antisymmetric total preorder - on a set X (i.e.
x - y - x =⇒ x = y (x, y ∈ X)) is said to be a total order.

Let - be a total preorder on a set X, and let x ≺ y (x, y ∈ X). We say that
the pair (x, y) defines a jump if there is no z ∈ X such that x ≺ z ≺ y. A
subset Y ⊆ X is said to be cofinal if for every x ∈ X there exists y ∈ Y such
that x ≺ y. Similarly Y is said to be coinitial if for every x ∈ X there exists
y ∈ Y such that y ≺ x. An element z ∈ X is said to be minimal (respectively:
maximal ) with respect to - if z - x (respectively: x - z) for every x ∈ X.
Consider now the quotient space X/ ∼ of X through the equivalence relation
∼. The ordering - is compatible with this quotient, so that X/ ∼ becomes a
totally ordered set. The total preorder - is said to be Dedekind complete if in
X/ ∼ every subset C ⊆ X/ ∼ that is bounded above with respect to ≺ has a
supremum (i.e.: smallest upper bound) sup C in X/ ∼.

When dealing with a total order - defined on X we can endow X with the
order topology whose subbasis is defined by the lower and upper contour sets
relative to ≺.

It can be proved that:

Lemma 2.2.

i) (see Gillman and Jerison [26] p. 3 , Birkhoff [2], p. 200, or else Can-
deal and Induráin [9]) :
Every total preorder - has a Dedekind complete extension without
jumps that has neither minimal nor maximal elements.
This extension is essentially unique.



Continuous representability of interval orders 217

ii) (see e.g. Birkhoff [2], p. 243) :
The order topology relative to a total order - on a set X is connected
if and only if - is Dedekind complete and has no jumps.

Remark 2.3. The extension corresponding to Lemma 2.2 (i) may produce a
set X̄ that is much bigger than the given set X. Notice that if we start with a
single X = {x}, with the trivial total ordering, then we arrive to an extension
that is isotonic to the real line R.

Coming back to the study of interval orders and semiorders, it is well-known
(see e.g. Proposition 2.1 in Bridges [5]) that:

Lemma 2.4. Let ≺ be an asymmetric binary relation defined on a nonempty
set X. Then the following statements are equivalent:

i) ≺ is an interval order,
ii) -∗ is a total preorder,
iii) -∗∗ is a total preorder.

In addition, - is transitive if and only if - , -∗, and -∗∗ coincide.

In what concerns semiorders among interval orders, suppose that an interval
order ≺ has been defined on a set X, and define the following new binary
relation, introduced in Fishburn [18]: x ≺0 y ⇐⇒ x ≺∗ y or else x ≺∗∗

y (x, y ∈ X). In Bosi and Isler [4] it is proved the following fact:

Lemma 2.5. The interval order ≺ is actually a semiorder if and only if ≺0 is
asymmetric.

A key concept, used in Olóriz et al. [27] to get a characterization of the repre-
sentability of interval orders, is that of interval order separability (henceforward
i.o.-separability). An interval order ≺ on a set X is said to be i.o.-separable if
there exists a countable subset D ⊆ X such that for every x, y ∈ X with x ≺ y
there exists an element d in D such that x ≺ d -∗∗ y.

The nub result on the representability of interval orders is in order now:

Lemma 2.6 (Olóriz et al. [27]). Let X be a nonempty set endowed with an
interval order ≺. Then, the following statements are equivalent:

i) ≺ is i.o.-separable,
ii) there exists a bivariate map F : X × X −→ R such that x - y ⇐⇒

F(x, y) ≥ 0 and F(x, y)+F(y, z) = F(x, z)+F(y, y) for every x, y, z ∈
X,

iii) ≺ is representable.

3. Continuous representations of interval orders

Let X be a nonempty set endowed with an interval order ≺ and a topology
τ. Now we consider the possibility of finding a representation (u, v) for ≺ such
that both u and v are continuous when considering on X the given topology
τ and on the real line R the usual Euclidean topology. To do so, we need to
introduce some previous concepts and results.



218 J. C. Candeal, E. Induráin and M. Zudaire

Definition 3.1. Let (X, τ) be a topological space endowed with an interval
order ≺ . We say that ≺ is τ-continuous if for each a ∈ X the upper and lower
contour sets L(a) and U(a) are τ-open sets.

Let ≺ be an interval-order, and ≺∗ and ≺∗∗ its associated relations as defined
in section 2. The τ-continuity of ≺∗ (respectively: ≺∗∗) is defined similarly,
now considering lower and upper contours relative to ≺∗ (respectively: ≺∗∗).

Definition 3.2. Let (X, τ) a topological space endowed with an interval order
≺ . The topology τ is said to be natural for the interval order ≺ if ≺, ≺∗ and
≺∗∗ are all τ-continuous.

Observe that a topology τ is natural for the interval order ≺ if and only if
it is finer than the topology θ, a subbasis of which is given by the family:

{U(a) : a ∈ X} ∪ {L(b) : b ∈ X}
⋃

{U≺∗(c) : c ∈ X} ∪ {L≺∗(d) : d ∈ X}
⋃

{U≺∗∗(e) : e ∈ X} ∪ {L≺∗∗(f) : f ∈ X}.

The existence of continuous representations for an interval order will lean,
of course, on the continuity of ≺, ≺∗, ≺∗∗ with respect to the given topology
τ. Also, it will lean on some ordinal condition of separability or density.

Definition 3.3. Let X be a nonempty set endowed with an interval order ≺ .
We say that ≺ is
i) strongly separable if there exists a countable subset D ⊆ X such that for
every x, y ∈ X with x ≺ y, there exist a, b ∈ D such that x ≺ a - b ≺ y,
ii) full if for every x, y ∈ X with x ≺ y, there exist a, b ∈ X such that x ≺ a -
b ≺ y.

(It is obvious that strongly separable implies full).

The main well-known result on the continuous representability of an interval
order ≺ on a topological space (X, τ) was introduced in Chateauneuf [11] for
the case in which (X, τ) is a connected topological space.

Theorem 3.4 (Chateauneuf [11]). An interval order ≺ defined on a connected
topological space (X, τ) admits a representation (u, v) with u and v continuous
if and only if ≺ is strongly separable and in addition ≺∗ and ≺∗∗ are both τ-
continuous. Moreover, in that case there is also a continuous representation
(U, V ) such that U is a representation for the total preorder -∗∗ and V is a
representation for the total preorder -∗.

We can now improve Chateauneuf’s theorem with more equivalences, having
in mind the concept of i.o.-separability, that is weaker than strong separability.

Theorem 3.5. Let ≺ be an interval order defined on a connected topological
space (X, τ). The following conditions are equivalent:



Continuous representability of interval orders 219

i) (X, ≺) has a continuous representation,
ii) ≺ is strongly separable and τ is a natural topology,
iii) (X, ≺) has a representation (u, v) such that u and v are τ-upper semi-

continuous, and ≺∗, ≺∗∗ are τ-continuous,
iv) (X, ≺) has a representation (u, v) such that u and v are τ-lower semi-

continuous, and ≺∗, ≺∗∗ are τ-continuous,
v) ≺ is strongly separable and ≺∗, ≺∗∗ are τ-continuous,
vi) ≺ is i.o.-separable and full, and ≺∗, ≺∗∗ are τ-continuous,
vii) the topology θ is separable (i.e: there exists a countable subset that

meets every nonempty θ-open set) and coarser than τ,
viii) ≺ is i.o-separable and τ is a natural topology,
ix) ≺ is i.o.-separable, and ≺∗, ≺∗∗ are τ-continuous
x) (X, ≺) has a continuous representation (u, v) such that u is a represen-

tation for ≺∗∗ and v is a representation for ≺∗,
xi) there exists a bivariate map F : X × X −→ R that is continuous with

respect to the product (τ × τ) topology on X × X and the Euclidean
topology on R such that x - y ⇐⇒ F(x, y) ≥ 0 and F(x, y)+F(y, z) =
F(x, z) + F(y, y) for every x, y, z ∈ X,

xii) the topology θ is second countable (i.e.: there exists a countable basis
for such topology) and coarser than τ.

Proof. The proof will follow the scheme :

i) ⇐⇒ ii), i) ⇐⇒ iii), i) ⇐⇒ iv), ii) =⇒ v) =⇒ i), v) ⇐⇒ vi),
vi) ⇐⇒ viii), viii) ⇐⇒ ix), viii) =⇒ x) =⇒ i), i) ⇐⇒ xi),
vii) ⇐⇒ ii), xii) =⇒ vii) and finally i) =⇒ xii).

i) =⇒ ii)
See Proposition 6.2.3, Lemma 6.5.1 and Lemma 6.5.3 in Bridges and Mehta
[6].

ii) =⇒ i)
See Theorem 6.5.5 in Bridges and Mehta [6].

i) =⇒ iii)
It is obvious that (X, ≺) has a representation (u, v) such that u and v are τ-
upper semicontinuous. The τ-continuity of ≺∗, ≺∗∗ follows from Lemma 6.5.1
in Bridges and Mehta [6].

iii) =⇒ i)
By Proposition 6.2.3 in Bridges and Mehta [6], ≺ is continuous. Moreover,
it is i.o.-separable by Lemma 4, since it is representable. The proof of Theo-
rem 6.5.5 in Bridges and Mehta [6] gives now a construction of a continuous
representation for the interval order ≺.



220 J. C. Candeal, E. Induráin and M. Zudaire

i) =⇒ iv) =⇒ i)
This is analogous to i) =⇒ iii) =⇒ i). Notice also that an interval order
is representable if and only if the opposite interval order ≺op is representable.
If (u, v) is a representation for ≺, then (−v, −u) is a representation for ≺op.
Finally, a map f : X −→ R is lower-semicontinuous if and only if −f is upper-
semicontinuous.

ii) =⇒ v)
This is obvious.

v) =⇒ i)
See the proof of Theorem 6.5.5 in Bridges and Mehta [6].

v) =⇒ vi) =⇒ v)
It follows from the equivalence, proved in Bosi et al. [3], that states that
strongly separable is the same as i.o.-separable plus full.

vi) =⇒ viii)
Notice that vi) ⇐⇒ v) ⇐⇒ ii) and obviously ii) =⇒ viii).

viii) =⇒ vi)
This is obvious.

viii) =⇒ ix)
This is immediate.

ix) =⇒ viii)
Following the proof of Theorem 6.5.5 in Bridges and Mehta [6] we first obtain
a representation (u, v) for ≺ such that u and v are τ-upper semicontinuous.
Now Proposition 6.2.3 in Bridges and Mehta [6] proves that ≺ is continuous.

viii) =⇒ x)
The proof of Theorem 6.5.5 in Bridges and Mehta [6] furnishes not only a
continuous representation (u, v) for ≺. It also states that u is a continuous
representation for ≺∗∗ and v is a continuous representation for ≺∗.

x) =⇒ i)
This is obvious.

i) =⇒ xi)
Let (u, v) be a continuous representation for ≺, and let F : X × X −→ R
be defined as follows: F(x, y) = v(y) − u(x) (x, y ∈ X). F is continuous
because u and v are. A final checking shows that x - y ⇐⇒ F(x, y) ≥ 0 and
F(x, y) + F(y, z) = F(x, z) + F(y, y) for every x, y, z ∈ X.



Continuous representability of interval orders 221

xi) =⇒ i)
Suppose F is given in the conditions of xi). Following Lemma 1 in Olóriz
et al. [27], fix an element x0 ∈ X and call u(x) = −F(x, x0) ; v(y) =
F(y, y) + u(y) (x, y ∈ X). It is straightforward to see now that (u, v) is a
continuous representation for ≺.

vii) =⇒ ii)
Because θ is coarser than τ, we have that τ is a natural topology and ≺ is θ-
connected. The connectedness and separability of θ imply, following the proof
of Corollary 6.5.6 in Bridges and Mehta [6], that ≺ is strongly separable. Thus
we arrive to ii).

ii) =⇒ vii)
Since τ is a natural topology, it is, by definition, finer than the topology θ.
Moreover, the τ-connectedness of X implies the connectedness of X in any
topology coarser than τ. Also, ≺ is by hypothesis strongly separable. There-
fore, as shown in Bosi et al. [3], the following conditions are equivalent:

1. ≺ is strongly separable.
2. There exists a countable subset D ⊆ X such that for every x, y ∈ X

with x ≺ y there exists d ∈ D such that x ≺∗ d ≺ y,
3. There exists a countable subset D ⊆ X such that for every x, y ∈ X

with x ≺ y there exists d ∈ D such that x ≺ d ≺∗∗ y.

Let us prove now that θ is separable: To do so, we consider the subbasis

{U(a) : a ∈ X} ∪ {L(b) : b ∈ X}
⋃

{U≺∗(c) : c ∈ X} ∪ {L≺∗(d) : d ∈ X}
⋃

{U≺∗∗(e) : e ∈ X} ∪ {L≺∗∗(f) : f ∈ X}

for such topology θ so that our task consists in proving the existence of a
countable subset C ⊆ X meeting any nonempty basic θ-open set. A basis for
θ appears as the collection of all finite intersections of elements in a subbasis.
Also, since condition ii) is equivalent to condition x), it follows that the interval
order ≺ and the total preorders -∗ and -∗∗ are representable. In particular,
their corresponding order topologies are separable. (See Candeal and Induráin
[7] for the case of a total preorder, and Bosi et al. [3] for the case of an interval
order). Consequently, it is enough to check the following possibilities:

Case 1. U≺(a) ∩ U≺∗(b):
If there exists z ∈ U≺(a) ∩ U≺∗(b), then a ≺ z and b ≺

∗ z. Take a
countable subset D ⊆ X corresponding to the strong separability of ≺. Take
also a countable subset R ⊆ X corresponding to the Cantor separability of the
preorder ≺∗, that is, being x, y ∈ X with x ≺∗ y, there exists r ∈ R such
that x ≺∗ r ≺∗ y. (The existence of such R follows from the connectedness of
the order topology of the representable preorder ≺∗. For more details, consult



222 J. C. Candeal, E. Induráin and M. Zudaire

Candeal and Induráin [7].) The family {U≺(d) ∩ U≺∗(r) : d ∈ D , r ∈ R} is
obviously countable. For any nonempty set S of this family, we choose s ∈ S.
This new set of elements, say C, is also countable. Now consider d ∈ D with
a ≺∗ d ≺ z and r ∈ R such that b ≺∗ r ≺∗ z. It follows that z ∈ U≺(d)∩U≺∗(r).
Take s ∈ C ∩ U≺(d) ∩ U≺∗ (r). It follows easily that s ∈ U≺(a) ∩ U≺∗(b) and we
are done.

Case 2. U≺(a) ∩ U≺∗∗(b):
Since U≺∗∗(x) =

⋃
{η∈X, x-η} U≺(η), this case follows from the separa-

bility of the order topology corresponding to ≺, a subbasis for which is the
collection {U(a) : a ∈ X} ∪ {L(b) : b ∈ X}.

Case 3. U≺∗(a) ∩ U≺∗∗(b):
If there exists z ∈ U∗≺(a) ∩ U≺∗∗(b), then a ≺

∗ z and b ≺∗∗ z. Take
a countable subset R ⊆ X corresponding to the Cantor separability of the
preorder ≺∗. Take also a countable subset S ⊆ X corresponding to the Cantor
separability of the preorder ≺∗∗. The family {U≺∗(r)∩U≺∗∗ (s) : r ∈ R , s ∈ S}
is obviously countable. For any nonempty set P of this family, we choose
p ∈ P . This new set of elements, say C, is also countable. Now consider
r ∈ R with a ≺∗ r ≺∗ z and s ∈ S such that b ≺∗∗ s ≺∗∗ z. It is plain that
z ∈ U≺∗(r) ∩ U≺∗∗(s). Take c ∈ C ∩ U≺∗(r) ∩ U≺∗∗(s). It follows easily that
c ∈ U≺∗(a) ∩ U≺∗∗(b) and we are done.

Case 4. L≺(a) ∩ L≺∗(b):
Since L≺∗(x) =

⋃
{ξ∈X, ξ-x} L≺(ξ), this case follows from the separabil-

ity of the order topology corresponding to ≺.

Case 5. L≺(a) ∩ L≺∗∗(b):
This case is analogous to Case 1. Actually, if there exists z ∈ L≺(a) ∩

L≺∗∗(b), then z ≺ a and z ≺
∗∗ b. Take a countable subset D ⊆ X corre-

sponding to the strong separability of ≺. Take also a countable subset R ⊆ X
corresponding to the Cantor separability of the preorder ≺∗∗, that is, being
x, y ∈ X with x ≺∗∗ y, there exists r ∈ R such that x ≺∗∗ r ≺∗∗ y. The
family {L≺(d) ∩ L≺∗∗(r) : d ∈ D , r ∈ R} is obviously countable. For
any nonempty set S of this family, we choose s ∈ S. This new set of ele-
ments, say C, is also countable. Now consider d ∈ D with z ≺ d ≺∗∗ a and
r ∈ R such that z ≺∗∗ r ≺∗∗ b. It follows that z ∈ L≺(d) ∩ L≺∗∗(r). Take
s ∈ C ∩ L≺(d) ∩ L≺∗∗(r). It follows easily that s ∈ L≺(a) ∩ L≺∗∗(b) and we are
done.

Case 6. L≺∗(a) ∩ L≺∗∗(b):
This case is analogous to Case 3.

Case 7. U≺(a) ∩ L≺∗(b):



Continuous representability of interval orders 223

Since L≺∗(x) =
⋃

{ξ∈X, ξ-x} L≺(ξ), this case follows from the separabil-

ity of the order topology corresponding to ≺.

Case 8. U≺(a) ∩ L≺∗∗(b):
If there exists z ∈ U≺(a) ∩ L≺∗∗(b), then a ≺ z and z ≺

∗∗ b. Take a
countable subset D ⊆ X corresponding to the strong separability of ≺. Take
also a countable subset R ⊆ X corresponding to the Cantor separability of the
preorder ≺∗∗. The family {U≺(d) ∩ L≺∗∗(r) : d ∈ D , r ∈ R} is obviously
countable. For any nonempty set S of this family, we choose s ∈ S. This new
set of elements, say C, is also countable. Now consider d ∈ D with a ≺∗ d ≺ z
and r ∈ R such that z ≺∗∗ r ≺∗∗ b. It follows that z ∈ U≺(d) ∩ L≺∗∗(r). Take
s ∈ C ∩ U≺(d) ∩ L≺∗∗(r). It follows easily that s ∈ U≺(a) ∩ L≺∗∗(b).

Case 9. U≺∗(a) ∩ L≺∗∗(b):
If there exists z ∈ U≺∗(a) ∩ L≺∗∗(b), then a ≺

∗ z and z ≺∗∗ b. Take
a countable subset D ⊆ X corresponding to the Cantor separability of the
preorder ≺∗. Take also a countable subset R ⊆ X corresponding to the Cantor
separability of the preorder ≺∗∗. The family {U≺∗(d) ∩ L≺∗∗(r) : d ∈ D , r ∈
R} is obviously countable. For any nonempty set S of this family, we choose
s ∈ S. This new set of elements, say C, is also countable. Now consider
d ∈ D with a ≺∗ d ≺∗ z and r ∈ R such that z ≺∗∗ r ≺∗∗ b. It follows that
z ∈ U≺∗(d) ∩ L≺∗∗(r). Take s ∈ C ∩ U≺∗(d) ∩ L≺∗∗(r). It follows easily that
s ∈ U≺∗(a) ∩ L≺∗∗(b).

Case 10. L≺(a) ∩ U≺∗(b):
This case is analogous to Case 8.

Case 11. L≺(a) ∩ U≺∗∗(b):
This case is analogous to Case 7.

Case 12. L≺∗(a) ∩ U≺∗∗(b):
Since U≺∗∗(x) =

⋃
{η∈X, x-η} U≺(η) and L≺∗(x) =

⋃
{ξ∈X, ξ-x} L≺(ξ),

this case follows from the separability of the order topology corresponding to
≺.

The union of the countable subsets used along the cases considered above is
of course countable and meets any nonempty basic θ-open set. Therefore θ is
separable.

xii) =⇒ vii)
Just notice that a second countable topology is always separable. (For aspects
concerning General Topology, consult Dugundji [15]).
i) =⇒ xii)



224 J. C. Candeal, E. Induráin and M. Zudaire

The topologies θ1, θ2 and θ3 whose respective subbasis are

Σ1 = {U(a) : a ∈ X} ∪ {L(b) : b ∈ X}

Σ2 = {U≺∗(c) : c ∈ X} ∪ {L≺∗(d) : d ∈ X}

Σ3 = {U≺∗∗(e) : e ∈ X} ∪ {L≺∗∗(f) : f ∈ X}

are second countable because ≺, -∗ and -∗ are representable. (See Bosi et al.
[3] or Candeal and Induráin [7] for more details). Then the topology θ whose
subbasis is Σ1 ∪ Σ2 ∪ Σ3 is also second countable.

This concludes the proof. �

Remark 3.6.

i) The version of Chateauneuf’s theorem that appears on pp. 106-107
of Bridges and Mehta [6] corresponds to the equivalence i) ⇐⇒ v)
but actually it is proved x) (a condition that is stronger than i) ).
Nothing is said about i.o.-separability, a condition less restrictive than
strong separability, because such concept of interval order separability
appeared later in the literature (in Olóriz et al. [27]).

ii) Several intermediate steps in the proof have appeared in previous works,
usually as necessary lemmata to introduce the main Chateauneuf’s
theorem. So, for instance, Proposition 6.2.3 in Bridges and Mehta
[6] shows that if a structure of interval order (X, ≺) endowed with a
topology τ has a representation (u, v) such that u and v are τ-upper
semicontinuous then ≺ is τ-continuous. Also, Lemma 6.5.1 and Lemma
6.5.3 in the same work state that if (X, ≺) has a continuous represen-
tation and X is connected, then ≺∗, ≺∗∗ are τ-continuous and ≺ is
strongly separable. Moreover, Lemma 6.5.4 in Bridges and Mehta [6]
states that if ≺∗, ≺∗∗ are τ-continuous and ≺ is full, then ≺ is con-
tinuous. Finally, in Bosi et al. [3] it has been proved that strongly
separable is the same as i.o.-separable plus full.

iii) An immediate corollary follows. This is Corollary 6.5.6 in Bridges and
Mehta [6] and can be considered as an extension to the context of
interval orders of the classical result (see Eilenberg [16]) that states
that a continuous total preorder defined on a connected and separable
topological space has a continuous numerical representation by means
of a utility function. In this new context of interval orders, from the
equivalent condition vii) in the statement of Theorem 3.5, it follows
that:

<< An interval order ≺ on a connected and separable topological
space (X, τ) has a continuous representation if and only if τ is a natural
topology (in other words: if and only if ≺, ≺∗ and ≺∗∗ are all τ-
continuous). >>

iv) Some method of proof of Chateauneuf’s theorem, whose main ideas
have been used to state some equivalences of Theorem 3.5 above, re-
minds us the classical Debreu’s open gap lemma (see Debreu [12, 13] or



Continuous representability of interval orders 225

else Bridges and Mehta [6], Ch. 3) that states the possibility of getting
a continuous utility function representing a total preorder, if it is the
case in which a utility function (continuous or not) is available.

In the context of an interval order ≺ on a connected topological
space (X, τ) such that ≺∗ and ≺∗∗ are continuous, a technique to get
a continuous representation (U, V ) starts by taking a utility function
v for the total preorder -∗. This utility function may or may not be
continuous, but using Debreu’s open gap lemma the continuity of v
can be assumed without loss of generality. From v and following the
proof of Chateauneuf’s theorem that appears in Bridges and Mehta
[6], p. 107, we can construct a real-valued function u that is upper
semicontinuous and such that (u, v) represents ≺. From Proposition
6.2.3 in Bridges and Mehta [6] it follows now that ≺ is continuous.
Then Lemma 6.5.3 in Bridges and Mehta [6] states that ≺ is strongly
separable, and finally the proof of Theorem 6.5.5 in Bridges and Mehta
[6] furnishes a continuous representation (U, V ) for ≺. A final glance
to this process tells us that from just a utility funtion for -∗, even
discontinuous, we are able to get a continuous representation (U, V )
for the interval order ≺. This is the kind of ideas underlying in the
classical Debreu’s open gap lemma.

v) The equation F(x, y) + F(y, z) = F(x, z) + F(y, y) is known as the
functional equation of separability because it corresponds to maps F
defined in X × X such that F can be separated as the sum of two func-
tions of only one variable each, that is F(x, y) = G(x)+H(y) ; G, H :
X −→ R. (For more details, consult Aczél and Dhombres [1]).

vi) In Theorem 3.5 connectedness cannot be ruled out, nor even in the
particular case of a total preorder - on a set X on which we consider
the order topology. For instance, it is not difficult to see that the order
topology given by the lexicographic ordering on R×{0, 1} is separable,
but this ordering is not representable.

vii) Similarly to Eilenberg’s theorem, the classical Debreu’s theorem on
second countability (see Debreu [12, 13] or else Ch. 3 in Bridges and
Mehta [6]) states that a continuous total preorder always admit a con-
tinuous utility function that represents it. Looking for an extension
of this result to the context of interval orders, we must observe that
the equivalent condition xii) that appears in the statement of Theorem
3.5 proves such a fact for the particular case of connected topological
spaces. Also, the continuity here is considered with respect to a natural
topology. It is an open question to prove or disprove the existence of
continuous representations for interval orders defined on a nonempty
set X on which we consider either the topology θ, or more generally a
natural topology, for which X is second countable. That is: the task
would consist in proving the equivalence i) ⇐⇒ xii) in Theorem 3.5



226 J. C. Candeal, E. Induráin and M. Zudaire

making no use of connectedness, or else disprove it by an adequate
counterexample.

viii) Some steps in the proof of Theorem 3.5 could be shortened if ≺ is
a semiorder instead of just an interval order. For instance, if X is a
nonempty set endowed with a semiorder ≺, even without assuming con-
nectedness then, it is not difficult to prove that the strong separability
of ≺ carries the topological separability of θ1, the topology on X whose
subbasis is Σ1 = {U(a) : a ∈ X} ∪ {L(b) : b ∈ X}. Indeed, if x, y in X
are such that x ≺ y and U≺(x) ∩ L≺(y) 6= ∅, we have that there exists
z ∈ X such that x ≺ z ≺ y. Let D ⊆ X be a countable subset that
furnishes the strong separability of ≺ . Then there exist d1, d2 ∈ D such
that x ≺ d1 ≺

∗∗ z ≺ d2 ≺
∗∗ y. By definition of ≺∗∗, there exist a, b ∈ X

such that x ≺ d1 - a ≺ z ≺ d2 - b ≺ y. By the generalized pseu-
dotransitivity of the semiorder ≺, where in particular the fact “-≺≺”
implies “≺”, it follows now that x ≺ d1 ≺ d2 - b ≺ y =⇒ x ≺ d1 ≺ y,
so that θ1 is separable.

A remarkable question that we must consider now concerns the existence
of continuous representations for interval orders in the general case (i.e.: not
necessarily connected). In the case of a total preorder, the crucial Debreu’s
open gap theorem provides continuous representations once we have a utility
representation. But, as far as we know, the validity or not of a similar result
for interval orders is still an open problem. Anyways, we can study some cases
different from the connected case.

Definition 3.7. An interval order ≺ on a nonempty set X is said to be dense-
in-itself if for every x, y ∈ X with x ≺ y there exists z ∈ X such that x ≺ z ≺ y.

Proposition 3.8. Let X be a nonempty set endowed with an interval order ≺
and a natural topology τ for which X is connected. Then it holds that either
the interval order ≺ is dense-in-itself or there exist elements x, y, z ∈ X such
that x ≺ y - z - x. In particular, if - is a total preorder, ≺ is dense-in-itself.

Proof. Actually, if x, y ∈ X are such that x ≺ y and there is no z ∈ X
such that y - z - x then it must exist an element a ∈ X with x ≺ a ≺ y
since otherwise the open and nonempty subsets L≺(y) and U≺(x) would give
raise to a disconnection of the set X, in contradiction with the hypothesis of
connectedness.

In the particular case of a total preorder, the situation x ≺ y - z - x would
imply x ≺ x, against the irreflexivity of the binary relation ≺. �

An important fact that we can prove at this point, states that on suitable
topologies, representable interval-orders that are dense-in-itself admit a con-
tinuous representation.



Continuous representability of interval orders 227

Theorem 3.9. A dense-in-itself and representable interval order ≺ defined
on a nonempty set X endowed with a natural topology τ has a continuous
representation.

Proof. It suffices to prove the existence of a continuous representations when
the topology considered on X is θ. Let a, b ∈ X with a ≺∗ b. By definition of
≺∗ there is an element c ∈ X such that a ≺ c - b. Since ≺ is dense-in-itself,
there also exists an element d ∈ X such that a ≺ d ≺ c - b. Thus a ≺ d ≺∗ b
which implies a ≺∗ d ≺∗ b. Therefore ≺∗ is also dense-in-itself. In a completely
analogous way we can prove that ≺∗∗ is dense-in-itself, too. Since ≺ is rep-
resentable, the associated total preorders -∗ and -∗∗ are representable. (See
Bosi et al. [3]). Since ≺∗ is dense-in-itself, standard techniques of construction
of utility functions for total preorders allow us to consider a utility function
v for ≺∗ with the additional property that (0, 1) ∩ Q ⊆ v(X) ⊆ [0, 1], so that
v(X) is dense in [0, 1] with respect to the Euclidean topology on R. (See, e.g.,
Birkhoff [2], p. 200 or else Candeal and Induráin [7, 8, 9]). The proof concludes
as in Bridges and Mehta [6], p.107, proof of the continuity of the representation
in Chateauneuf’s theorem. �

Definition 3.10. An interval order ≺ on a nonempty set X endowed with a
topology τ is said to be τ-locally non-satiated (see, e.g. Bridges and Mehta
[6], pp. 33 and 93) if for every x ∈ X it holds that U≺(x) meets every τ-
neighbourhood of x.

If τ is a natural topology, ≺ is τ-locally non-satiated, and a, b ∈ X are
such that a ≺ b, then since L≺(b) is a neighbourhood of a there must exist an
element c ∈ U≺(a) ∩ L≺(b). In particular, ≺ is dense-in-itself.

Corollary 3.11. A representable and τ-locally non-satiated interval order ≺
defined on a nonempty set X endowed with a natural topology τ has a conti-
nuous representation.

A deep analysis of the proof of Theorem 6.5.5 in Bridges and Mehta [6] tell
us that the key to finally get a continuous representation (U, V ) for an interval
order ≺ defined on a nonempty set X which we shall consider endowed with a
natural topology τ is nothing else but the fact that the associated total preorder
≺∗ is dense-in-itself (dually, it is also true that under the same conditions for
X, when the associated total preorder ≺∗∗ is dense-in-itself, the interval order
≺ admit a continuous representation (U, V ) ). This fact implies important
consequences:

Theorem 3.12. Let X be a nonempty set endowed with an interval order ≺
and a natural topology τ. Then if ≺ is strongly separable it admits a continuous
representation (U, V ).

Proof. By the previous comments, it is enough to prove that ≺∗ is dense-in-
itself. Let x, y ∈ X be such that x ≺∗ y. It follows, by definition of ≺∗,
that there exists an element z ∈ X such that x ≺ z - y. Since ≺ is strongly



228 J. C. Candeal, E. Induráin and M. Zudaire

separable, there exists now an element a ∈ X such that x ≺∗ a ≺ z - y.
Therefore x ≺∗ a ≺∗ y, and we are done. �

Remark 3.13.

i) It is an open problem to prove whether or not Theorem 3.12 remains
valid when the condition of strong separability is substituted for the
weaker one of i.o.-separability.

ii) The converse of Theorem 3.12 is not true: A clear example is the set
of natural numbers N endowed with the usual Euclidean total ordering
and the discrete topology. Considered as a particular case of interval
order, such ordering is i.o.-separable, but not strongly separable. And
it is plain that it admits a continuous representation.

In what concerns the techniques used to obtain continuous representations
of structures of interval order, the first impression is that they are different
from the main techniques used to just get representations (not necessarily con-
tinuous). Let us explain why:

The first technique, based on constructions using the auxiliar sets A(x),
B(x), leans on numerical series. (See e.g. Bridges and Mehta [6], pp. 88 and
ff. , or else Bosi et al. [3]). However, it is well known that functions defined
through series fail to be continuous in a countable set of points (for instance,
if (qn)

∞
n=1 is an enumeration of the set Q of rational numbers, the function

F : R −→ R given by F(x) =
∑

{k∈N : qk≤x}
2−k fails to be continuous at

each rational number). Consequently, the first technique is so good to ob-
tain representations of interval orders, but it is not so good to get continuous
representations.

The third technique, introduced in Olóriz et al. [27] and based on the the-
ory of functional equations presents similar problems than the first technique,
because the typical constructions of the bivariate map F : X × X −→ R that
satisfies x ≺ y ⇐⇒ F(x, y) > 0 and is a solution of the functional equation of
separability F(x, y) + F(y, z) = F(x, z) + F(y, y) (x, y ∈ X), are also based on
suitable numerical series that could lead to the discontinuity of F .

Fortunately, the second technique, based on measure theoretical construc-
tions may lead to a continuous representation, as proved in Bosi and Isler [4].

On the other hand, it is clear that the techniques used to prove Theorem 3.5
above, understood as a generalization of Chateauneuf’s theorem (as proved e.g.
in Bridges and Mehta [6], pp. 106-107) are different from the three techniques,
just cited, used to get representations (continuous or not) of interval-orders.
The key now is obtaining a continuous representation v for ≺∗ (making use
of Debreu’s open gap lemma, eventually) and then use v to get a continuous
representation u for ≺∗∗ in such a way that (u, v) is a continuous representation
for ≺.



Continuous representability of interval orders 229

Acknowledgements. This work has been partially supported by the re-
search project PB98-551 “Estructuras ordenadas y aplicaciones”. Ministerio
de Educación y Cultura. España. (Dec. 1999).

References

[1] J. Aczél and J. Dhombres, Functional equations in several variables, Cambridge Uni-
versity Press. (Cambridge, U.K. 1991).

[2] G. Birkhoff, Lattice theory, (Third edition). American Mathematical Society. (Provi-
dence, RI. 1967).

[3] G. Bosi , J. C. Candeal , E. Induráin, E. Olóriz and M. Zudaire, Numerical representa-
tions of interval orders, Order 18 (2001), 171-190.

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

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

[6] D. S. Bridges and G. B. Mehta, Representations of preference orderings, Springer-Verlag.
(Berlin. 1995).

[7] J. C. Candeal and E. Induráin, Sobre caracterizaciones topológicas de la representa–
bilidad de cadenas mediante funciones de utilidad, Revista Española de Economı́a 7 (2)
(1990), 235-244.

[8] J. C. Candeal and E. Induráin, Utility functions on chains, Journal of Mathematical
Economics 22 (1993), 161-168.

[9] J. C. Candeal and E. Induráin, Lexicographic behaviour of chains, Archiv der Mathe-
matik 72 (1999), 145-152.

[10] J. C. Candeal and E. Induráin, and M. Zudaire, Numerical representability of semi-
orders, Mathematical Social Sciences 43 (2002), 61-77.

[11] A. Chateauneuf, Continuous representation of a preference relation on a connected
topological space, Journal of Mathematical Economics 16 (1987), 139-146.

[12] G. Debreu, Representation of a preference ordering by a numerical function, In Decision
processes, edited by R. Thrall, C. Coombs and R. Davies. John Wiley. (New York. 1954).

[13] G. Debreu, Continuity properties of Paretian utility, International Economic Review 5
(1964), 285-293.

[14] J. P. Doignon, A. Ducamp and J. C. Falmagne, On realizable biorders and the biorder
dimension of a relation, Journal of Mathematical Psychology 28 (1984), 73-109.

[15] J. Dugundji, Topology, Allyn and Bacon. (Boston. 1966).
[16] S. Eilenberg, Ordered topological spaces, American Journal of Mathematics 63 (1941),

39-45.
[17] P. C. Fishburn, Intransitive indifference with unequal indifference intervals, Journal of

Mathematical Psychology 7 (1970), 144-149.
[18] P. C. Fishburn, Intransitive indifference in preference theory: a survey, Operations

Research 18 (2) (1970), 207-228.
[19] P. C. Fishburn, Utility theory for decision-making, Wiley, (New York. 1970).
[20] P. C. Fishburn, Interval representations for interval orders and semiorders, Journal of

Mathematical Psychology 10 (1973), 91-105.
[21] P. C. Fishburn, Interval orders and interval graphs, (Wiley, New York. 1985).
[22] S. H. Gensemer, On numerical representations of semiorders, Discussion Paper n. 5.

Department of Economics. University of Syracuse, (N.Y. 1986).
[23] S. H. Gensemer, On relationships between numerical representations of interval orders

and semiorders, Journal of Economic Theory 43 (1987), 157-169.



230 J. C. Candeal, E. Induráin and M. Zudaire

[24] S. H. Gensemer, Continuous semiorder representations, Journal of Mathematical Eco-
nomics 16 (1987), 275-289.

[25] S. H. Gensemer, On numerical representations of semiorders, Mathematical Social Sci-
ences 15 (3) (1988), 277-286.

[26] L. Gillman and M. Jerison, Rings of continuous functions, Springer-Verlag. (New York.
1960).

[27] E. Olóriz, J. C. Candeal and E. Induráin, Representability of interval orders, Journal of
Economic Theory 78 (1) (1998), 219-227.

Received May 2003

Accepted August 2003

J.C. Candeal (candeal@posta.unizar.es)
Departamento de Análisis Económico, Facultad de Ciencias Económicas y Em-
presariales, c/Doctor Cerrada 1-3, 50005 Zaragoza, Spain

E. Induráin (steiner@si.unavarra.es)
Departamento de Matemática e Informática, Universidad Pública de Navarra,
Campus Arrosad́ıa, Edificio “Las Encinas”, 31006 Pamplona (Navarra), Spain

M. Zudaire (mzudair2@pnte.cfnavarra.es)
Instituto de Educación Secundaria Barañain, (Gobierno de Navarra), Avda.
Central 3, 31010 Barañáin (Navarra), Spain