Representing Interval Orders by Arbitrary Real Intervals

Uwe Lück Department of Philosophy University of Munich^{∗}

January 13, 2004

Abstract

Interval orders are a way to model non-transitive indifference in comparison judgments as well as temporal relations between “events”. While so far only characterizations of their representability by complete precedence vs. intersecting of closed or open (and bounded) real intervals have been known, this paper presents necessary and sufficient conditions for their representability by arbitrary real intervals as well as a new characterization for open representability. Furthermore we, like Fishburn, consider natural restrictions on representations and extend respective results of his. Accordingly, we also deal with semiorders in the sense of Luce. Interrelations of countability (separability, representability) conditions (“directly” in terms of interval orders) reveal two redundancies in Fishburn’s representability conditions and indicate more direct ways to his results. The key to our results is a pair of generalizations of Fishburn’s notion of “singularity”.

Keywords: interval orders, semiorders, linear orders, representation theorems; preferences/comparisons, economics/mathematical psychology/measurement.

Subject Classification (MSC2000) [suggestions]: Primary 06A99 [ordered sets, remaining]; Secondary 06A05 [total order], 91B08 [individual preferences], 91B16 [utility theory], 91B42 [consumer behaviour, demand theory], 91C05 [measurement theory], 91C15 [one- and multidimensional scaling], 91E30 [psychophysics, …], 91E45 [measurement & performance].

∗Seminar für Philosophie, Logik und Wissenschaftstheorie/Philosophie-Department/ Universität München/Geschwister-Scholl-Platz 1/80539 München/Germany; uwe.lueck @lrz.uni-muenchen.de

Contents

1 Introduction and summary. 3

2 First preliminaries. 4 2.1 Binary relations. . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Interval representations and interval orders. . . . . . . . . . . 5 2.3 Visualization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Known and new results. 7 3.1 “Closed” representability as known. . . . . . . . . . . . . . . 7 3.2 Some improvement concerning semiorders. . . . . . . . . . . . 9 3.3 Results on other kinds of representations. . . . . . . . . . . . 10 3.4 Conditions (F1) etc. . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Real homomorphisms, “exact” representations. . . . . . . . . 13 3.6 Representing singularity. . . . . . . . . . . . . . . . . . . . . . 14 3.7 Extending Fishburn’s results on semiorders. . . . . . . . . . . 16 3.8 Empirical significance? . . . . . . . . . . . . . . . . . . . . . . 17 3.9 Where are the proofs? . . . . . . . . . . . . . . . . . . . . . . 18

4 Additional general preliminaries. 18 4.1 Further conventions concerning binary relations. . . . . . . . 18 4.2 Weak orders, their quotients, and representability. . . . . . . 19 4.3 How interval representations handle I, IT, and T I. . . . . . . 20 4.4 Vital features of T, I, IT, and T I. . . . . . . . . . . . . . . . 20 4.5 I*, singularity, and regularity. . . . . . . . . . . . . . . . . . . 21 4.6 Congruency—exemplified. . . . . . . . . . . . . . . . . . . . . 22 4.7 “Neighbourhood”, “jumps”, and regularity. . . . . . . . . . . 25 4.8 Miscellanea on separability. . . . . . . . . . . . . . . . . . . . 25

5 Proofs: “Unbounded”/FP representations. 26

6 Proofs on representability conditions. 27 6.1 Dual conditions in general. . . . . . . . . . . . . . . . . . . . 27 6.2 A preliminary on (F2). . . . . . . . . . . . . . . . . . . . . . . 28 6.3 Condition (E). . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.4 Singular-separability and -countability. . . . . . . . . . . . . . 30 6.5 (F1), above, and below. . . . . . . . . . . . . . . . . . . . . . 31 6.6 “Weakening” Fishburn’s Condition (F2). . . . . . . . . . . . . 32

7 Necessity proofs. 33 8 Sufficiency proofs. 35

8.1 Content and general strategy. . . . . . . . . . . . . . . . . . . 35 8.2 Closed representations: proof of Corollary 3. . . . . . . . . . . 35 8.3 A representing linear order of “cuts”. . . . . . . . . . . . . . . 36 8.4 Two special kinds of cuts and their interrelations. . . . . . . . 37 8.5 Existence of arbitrary real representations. . . . . . . . . . . . 38 8.6 Existence of open real representations. . . . . . . . . . . . . . 42

9 Proofs concerning semiorders. 43

10 Acknowledgements 44

References 44

1 Introduction and summary.

Interval orders model comparison judgments in experimental psychology (perception/evaluation of objects/persons) as well as comparison judgments concerning utilities of alternatives in economic theory—cf. [9, p. 20f.], [16, pp. 19ff.]. In both cases, indifference of judgment may well be non-transitive (in these realms, however, interval orders like to be replaced by the somewhat more special “semiorders”, cf. [13, 16]). “Utility functions” are (in general) not applicable in such situations. Interval orders also have served to model temporal relationships among events in philosophical ontology (see references in [19, 20]) and in computer science. (For further applications see [references in] [16, pp. 19ff.], [9, pp. 19ff.], or [17, p. 255].)^{1} They may be defined to be representable by the relationships of complete precedence and of intersecting between intervals of linear orders.

Which interval orders may, in particular, in this manner be represented by intervals with respect to the linear ‘less than’-relation between real numbers? This question seems to be held important for the applicability of mathematics to the sciences (at least to the ones mentioned above), and, actually, has occupied all non-philosophical published work on “representability” of interval orders. Such a representation may be considered an appropriate variant of a utility function and would, in an extended manner, fit the research programme of “classical” measurement theory (cf. [11]), where everything “empirical” must be tried to be viewed as something made out of the real numbers.^{2}

While the literature so far only has characterized interval orders representable by complete precedence vs. intersecting of closed or open (and bounded) real intervals (usually equivalently considering pairs of functions and involving questions of [semi-]continuity of interval borders with respect to some topology on the alternatives), this paper presents necessary and sufficient conditions for their representability by arbitrary real intervals (disregarding continuity, however). Moreover, a new characterization of representability by open real intervals is offered.

1As further examples archeology and paleontology are listed, where the duration of such “events” may exceed lifetimes.

2Reservations against this research programme—as espoused, e.g., in [14] —are not considered an obstacle to happily presenting here results fitting it.

Some of the countability and “separability” conditions involved in these characterizations of real representability interrelate. These interrelations yield alternative or even shorter proofs of some of Fishburn’s [8, 9, Sec.s 7.5f.] results and add alternative (“logically/practically weaker”) solutions to a characterization problem previously solved by Fishburn and [15].

We shall begin with briefly reporting these results on “closed” real representability known so far that do not consider continuity of interval borders, only preceded by a minimal amount of conventions required in that report, and followed by some improvement concerning real representability of semiorders. We shall then present our characterizations of “arbitrary” and of “open” real representability (starting with a brief report of Fishburn’s [8, 9] contribution and closing with an improvement of his characterization result). The “position” of one of Fishburn’s representability conditions, and two aspects of “minimality” of representations will be discussed briefly. We shall finish presentation of own results by considering extensions of theorems of Fishburn’s [8, 9] concerning semiorders, taking into account those “minimality” notions. We shall briefly wonder about empirical significance of our results. After extending notational machinery and order-theoretical background, we shall proceed by the obvious explanations concerning “unbounded” real representations and “function pair representations”, then by proving the remaining claims, concerning interrelations between representability (separability, countability) conditions first, concerning necessity of characterizing conditions next, and concerning sufficiency finally.

2 First preliminaries.

2.1 Binary relations.

If R ⊆ X × X (R a binary relation on the largest set X mentioned so far), we write x R y for (x, y) ∈ R, by ∼_{R} we denote X × X \ (R ∪ R^{−1}) (the symmetric complement of R),^{3} and ≺ ∼_{R} is R ∪ ∼_{R}. We shall use the latter notation for asymmetric^{4} relations R only. For these, propositional logic obtains that a ≺ ∼_{R} b just means not b R a (≺ ∼_{R} is the “reverse negation” of R).

3By R^{−1} we mean the binary relation defined by x R^{−1} y iff y R x.—Some notations are vague concerning X, but this will not matter.

4R being asymmetric means R ∩ R^{−1} = ∅.

A set Y will be called R-separable if there is some countable subset D ⊆ Y such that for all x, y ∈ Y such that x R y there is d ∈ D such that x ≺ ∼_{R} d ≺ ∼_{R} y.—We shall apply this notion to a class of (in particular: asymmetric) relations only, for which two other definitions of separability notions given in [3, 1.4.3.f.] and used in other work on real representability of binary relations are equivalent.^{5} In this respect, the notion is somewhat “more widely applicable than it seems at first”.

If a statement is logically or set-theoretically equivalent to a statement only involving X and R, replacing R by its converse R^{−1} yields the dual statement. If notions derived from X and R are involved, it will be clear what the dual is, as well. It will also (at any instance) be clear what the dual of a notion is. We shall often deal with pairs of assumptions or notions dual to each other. In such cases, reasonings can be dualized as well, and we shall treat only one version explicitly. Cf. [1, p. 13].

We write RR′ for the composition of any binary relations R, R′.^{6}

2.2 Interval representations and interval orders.

A binary relation L (strictly) linearly orders some set Q—and (Q, L) will then be called a linear order—, if L ∩ (Q × Q) is irreflexive, transitive and trichotomic (connex, “complete”).^{7} A (corresponding) interval (a non-void “convex” subset) is a non-void subset H of Q such that for all x, y ∈ H each situation x L z L y implies z ∈ H. I(Q, L) will denote the set of these intervals.

If R is some binary relation and X some set, some ρ will be said to be an interval representation (IR) of (X, R) in (Q, L) if L linearly orders Q and if ρ is a map X → I(Q, L) such that

x R y  iff  ∀p ∈ ρ(x) ∀q ∈ ρ(y) : p L q.

ρ[A] (the image of A under ρ) may contain only closed and bounded intervals (i.e., they contain their boundary points); ρ will then be called a closed and bounded IR (CBIR) itself.

By [9, Thm. 2.6], an interval order may now be defined to be an ordered pair (X, R) which has a CBIR in some linear order. In fact, from the result cited one can derive that any (X, R) having an IR has a CBIR. Therefore, an interval order can as well be defined by the property of just having some IR.

5In fact, while Fishburn’s [8] uses the definition given above, his [9] uses one of these two other definitions. More precisely: he uses the respective notions—never actually using the term ‘separable’. The difference stems from different definitions of ‘(order-)dense’—cf. our Subsection 4.8 below. As a consequence, the appearence that [8] and [9, Sec.s 7.4–7.6] would state and prove the same theorems would not be quite correct. However, we shall ignore the difference in the sequel.

6I.e., for { (x, y) | ∃z : x R z R′ y }.

7To be explicit, trichotomicity of R means that whenever x ≠ y, x R y or y R x.

As a simple example, the intervals of a linear order (Q, L) together with their relation of “complete precedence” with respect to L^{8} trivially form an interval order—the natural interval order of (Q, L). (The term ‘natural interval order’ will also be used for suborders of such interval orders.) An IR of (X, R) may then just be viewed as a “strong”^{9} homomorphism from (X, R) to the natural interval order of some linear order, and “general” interval orders are just those (X, R) from which there is such a strong homomorphism into some natural interval order.

From now on, we deal especially with one arbitrary interval order (A, T) where T ⊆ A × A. A may well be infinite (otherwise representability problems to be dealt with would be trivial); but A must not be void. Introducing I as ∼_{T} gives rise to the well-known composite binary relations IT and T I on A, properties of which will be recalled below.

2.3 Visualization.

However, at this stage some visualization of IT and T I may be helpful. Assume for a moment A is a three-element set {a, b, c} and T = {(a, b)}. This situation may be visualized by Figure 1. a T b is visualized by arranging

\underline{a}  \underline{b}
\underline{c}

⟶ (some quantity? time?)

Figure 1: A = {a, b, c}, T = {(a, b)}.

horizontal strokes representing a and b so that a vertical stroke can be filled in right-hand to the horizontal stroke representing a and left-hand to the horizontal stroke which represents b.

In contrast, no vertical stroke would have two horizontal strokes on different sides such that one of them would represent a and the other would represent c. This holds for b in place of a, as well. Rather, c is “overlapping” a as well as b—this is a I c I b.

Furthermore, that c “starts at the left of” b is “witnessed” by a overlapping c but wholly preceding b—this is c IT b. Similarly, a “ends to the left of where c ends”, “witnessed” by b overlapping c but being wholly preceded by a—this is a T I c.^{10}

However, one cannot “read” a IT c from the diagram, since there is no “witness” d such that a I d T c.

8To be precise, this relation !L!, say, of “complete precedence” with respect to L is meant to be defined by, for H_{0}, H_{1} ∈ I(Q, L), H_{0} !L! H_{1} iff, for all p ∈ H_{0} and all q ∈ H_{1}, p L q.

9Cf. [3, 1.1.9].

10In the interpretation of the situation as temporally related events, c begins earlier than b, while a ends earlier than c.

With the latter reservation, such visualizations show all properties of T, I, IT, and T I that will be needed, and they may be helpful in checking and understanding respective claims below.

3 Known and new results.

3.1 “Closed” representability as known.

Particular interest has been enjoyed by those CBIRs of (A, T) in (R, <), the “less-than” ordering of the real numbers—we call them closed bounded real interval representations (CBRIRs). A real interval is just meant to be an element of I(R, <).

CBRIRs usually appear as function pair representations (FPRs), i.e., as maps u, v : A → R such that

a T b iff v(a) < u(b).

(u ≤ v follows.) More precisely, if F is a CBRIR, u : A → R, a ↦ inf F (a) and v : A → R, a ↦ sup F (a) form a FPR; and if (u, v) is a FPR, a ↦ [u(a), v(a)] is a CBRIR.^{11} So existence of a FPR is the same as existence of a CBRIR. Mathematical economy typically asks for such representations by (semi-)continuous functions with respect to some topology on A (which may be viewed, e.g., as a subset of R^{n})—see [3, Chap. 6], in particular for Chateauneuf’s solution of a respectively restricted version of the problem that the present subsection deals with.

Fishburn ([8, 9, Sec. 7.5]) presented a necessary and sufficient condition for the existence of a CBRIR that can be stated as a conjunction of two parts. The first of them is:

(F1) A be IT - as well as T I-separable.

Unlike pairs of countability conditions dual to each other the equivalence of which turns out below, IT - and T I-separability are independent.^{12} There is some redundancy in the above presentation of (F1), however, which will be revealed in Subsection 6.5 below.

Knowing that ∼_{T I} is an equivalence relation and that a singular element a of A is (by Fishburn’s [8] definition)^{13} one for which b I a I c implies b I c, the second part of Fishburn’s condition can be stated thus:

11According to widespread use, [u(a), v(a)] here denotes { r ∈ R | u(a) ≤ r ≤ v(a) }, of course.

12An example for each direction of non-implication is provided by the “self-representing”

interval order of all (bounded) real intervals which contain their lower [upper, resp.] boundary. Thus, [r, s) as well as [r, s] occur in one of the two examples. The example depends essentially on the fact that, e.g., [s, s] “witnesses” the former two intervals ending differently upwards.

13In [9], Fishburn uses the term ‘simplicial’ instead for some graph-theoretical reason.

(F2) There be only countably many T I-equivalence classes^{14} which contain no singular element and for an element b of which the set of a such that b T a has some IT -minimum, but no singular one.^{15}

One may feel uneasy with such counting equivalence classes in a characterization of some interval orders. To avoid it, one may (at the cost of assuming the Axiom of Choice)^{16} word (F2) equivalently thus: Every subset C of A which is linearly ordered by T I, which contains no singular element, and for every element c of which the set of a such that c T a has some IT -minimum, but no singular one, be countable.

Oloriz, Candeal and Induráin [15] from the (Public) Universities of Pamplona and Zaragoza (Spain), obviously not aware of Fishburn’s result, more recently presented another necessary and sufficient existence condition, viz.

(E) there be a countable D ⊆ A such that for all (a, b) ∈ T there is some d ∈ D such that a T d ≺ ∼_{IT} b.^{17}

As a “test” that both Fishburn and the Spanish authors are right (if one of them is), one may reason just in terms of (A, T) that the conjunction of Fishburn’s conditions (F1), (F2) is equivalent to the “Spanish” condition (E). This will be done (not as a “test”, but just to show it) in Subsection 6.3 below.

A slightly weaker characterization has been presented by Doignon et al. [6, Prop. 9f.] already in 1984, using

(D1) there be a countable D ⊆ A such that for all (a, b) ∈ T there is some d ∈ D such that a T d ≺ ∼_{IT} b or a ≺ ∼_{T I} d T b.

One could drop the restriction of boundedness and consider CRIRs— note that, in topological terminology, a real interval having just one boundary which it contains counts as closed (as a closed set, at least). By the same token, even R is a “closed” real interval.—Clearly, CRIRs do not really make a difference; though the following summary including them might be welcome.^{18} 3 KNOWN AND NEW RESULTS. 9

14T I-equivalence, of course, is meant to be ∼_{T I}—since this is known to be an equivalence relation (as will be indicated below or clear from the “visualization” above).

15Fishburn’s way of stating this condition may be more perspicuous, but the way we have presented it better fits into the framework of the present paper. Some notation and reasoning introduced below should, however, improve perspicuity of (F2)—see Subsection 6.2.

16Cf., e.g., [12]. The present author is, up to now, not able to see how the Countable Axiom of Choice could suffice for both directions to be proved.

17At least, this is a way of stating the condition the present author prefers. We shall return to this “translation problem” in Subsection 6.3.—IT is, in fact, asymmetric, so d ≺ ∼_{IT} b means not b IT d as well as d (IT ∪ ∼_{IT}) b here.

18Literally, Fishburn’s [8] deals with ‘closed-interval representability’ in the sense of existence of a CRIR: In proving his Thm. 5 on [8, p. 102], he takes care of unbounded in-

Theorem 1 (Fishburn; Oloriz/Candeal/Induráin). The following conditions are equivalent.

(i) (A, T) has a CBRIR;

(ii) (A, T) has a CRIR;

(iii) (A, T) has a FPR;

(iv) (F1) and (F2) hold;

(v) (E) holds;

(vi) (D1) holds.

In this summary, however, Conditions (F1) and (F2) may be replaced by somewhat weaker ones. This will be done in Theorem 7 in Subsection 3.3 and in Theorem 11 in Subsection 6.5.

Following Fishburn [8], we could have told more in the following way: In place of assuming (A, T) to be an interval order, we could have assumed nothing more than T ⊆ A × A—at the same time augmenting conditions (iv) through (vi) by and (A, T) is an interval order. Indeed, each of the first two conditions of Theorem 1 (under the parsimonious assumption) implies that (A, T) is an interval order according to Subsection 2.2.—This remark applies respectively to our representation theorems of subsections 3.3 and 3.5–3.7 below.^{19}

3.2 Some improvement concerning semiorders.

Following Luce [13], (A, T) is a semiorder if (additionally to being an interval order) a T c T b excludes a I d I b, i.e., no representing interval intersects each of three pairwise non-intersecting representing intervals. This may

tervals. On p. 92 of the same paper, he defines “closed-interval representable” by existence of a RIR (cf. Subsection 3.3) such that taking the closures of the image intervals yields a RIR again (assuming ‘inf A = ∞’ in case A has no lower bound etc.). By his own understanding, such intervals just need not be bounded! On p. 95, however, he assumes without explanation that, for a given ‘closed-interval representation’ ρ, there is pair of maps u, v such that ρ(x) = [u(x), v(x)].—In [9], in contrast, Fishburn defines “closed-interval representable” explicitly by existence of a FPR (in the sequel telling the same story as in [8]).—These observations indicate that Fishburn (already in [8]) considers closed intervals bounded (this may be common use), while he may have overlooked something on his [8, p. 92] (e.g., in writing the sentence following his (2), he may have thought that “closing open ends” turned RIRs into CBRIRs, disregarding unbounded image intervals). However, there is no plain error; it only might have been appropriate to supplement the reasoning of p. 95 by a similar hint on monotone transformations with bounded image set as on p. 102 in order to explain that his ‘closed-interval representable’ entails existence of a CBRIR.

19We cling to displaying the weaker versions for seeming better readability of the theorems and streamelinedness of the respective proofs.

be understood as representing intervals having “similar length”, maybe in connection with a constant threshold of noticeable differences with respect to some quality of experimental stimuli or to subjective utility.

For semiorders, the relation

T_{0} := IT ∪ T I

is of particular importance. In Fishburn’s [8, 9], representability theorems for interval orders involving (F1) are followed by respective variants for semiorders where (F1) is replaced by T_{0}-separability. In proofs of such variant theorems, Fishburn states that T_{0}-separability (obviously) implies (F1), whereas he proves necessity of T_{0}-separability for existence of a CBRIR just starting at the assumption of such a CBRIR (or FPR). Instead, he simply could have used (proved)

Theorem 2. If (A, T) is a semiorder, A is T_{0}-separable iff (F1) holds.

3.3 Results on other kinds of representations.

Besides C(B)RIRs, Fishburn ([8, 9, Sec. 7.5]) considered representations by arbitrary (bounded) real intervals (arbitrary (bounded) real IRs, ARIRs/ ABRIRs). In some contexts, we shall write RIR for real interval representation in place of ARIR.

Fishburn only found that his (F1) is a sufficient condition for their existence. That it is not necessary becomes obvious by taking (A, T) to be the “self-representing” natural interval order made up by the set of all (bounded) real intervals, where (F1) is not satisfied.^{20} Note that a set D ⊆ A according to the definition of IT -separability (which is required by (F1)) must contain an element of at least one of two “neighbouring” IT -equivalence classes. By contrast, in the previous example each real serves as a boundary contained in intervals of one IT -equivalence class as well as a boundary not contained by the elements of another IT -equivalence class. So there are uncountably many “jumps” of IT -equivalence classes, and a D according to the definition of IT -separability cannot exist. Dually, of course, neither is the A specified above T I-separable.

However, if (in the same example still) we restrict consideraration to real intervals (i) containing or (ii) not containing their lower boundaries, IT -separability obtains (“separately”) in both cases (i) and (ii). Dually, T I-separability obtains in both of the analogous two cases concerning upper boundaries. By additionally generalizing Fishburn’s notion of singular elements, this idea turns out to be the key to solving the characterization problem for A(B)RIRs.

20Fishburn [8] is aware that (F1) is not necessary and presents another example than is presented here.

The proof strategy developing in this way, furthermore, turns out to solve another problem to be posed now. Namely, instead of representations by closed real intervals one might prefer representations by open real intervals. Again, one may additionally consider the restriction of boundedness, and it is clear what ORIRs and OBRIRs are meant to be now. Just in order to complete the picture, one may additionally consider weak function pair representations (WFPRs), defined as pairs (u, v) of maps u, v : A → R such that

a T b iff v(a) ≤ u(b)

(now u < v follows)—although it is clear from the start what is to be said about them.

Doignon et al. [6, Prop. 8] already considered the problem of which interval orders have O(B)RIRs. They characterized such interval orders by the condition

(D2) there be a countable D ⊆ A such that for all (a, b) ∈ ≺ ∼_{T} there is some d ∈ D such that a ≺ ∼_{T} d ≺ ∼_{T I} b or a ≺ ∼_{IT} d ≺ ∼_{T} b.

We find another solution of the same problem in quite different terms.^{21}

The generalizations announced above are the following.^{22} Call an element a of A lower-singular if { b | a I b } has a T I-minimum. (If a is singular in Fishburn’s sense, a is such a T I-minimum itself.) Dually, call a upper-singular if the same set has an IT -maximum. (Again, if a is singular in Fishburn’s sense, a is such an IT -maximum itself.)

Thus, singular elements are both lower- and upper-singular; the converse does not hold: the element c in the above diagram is a counter-example. If (A, T) is finite, all a ∈ A are both lower- and upper-singular. (Subsection 3.6 provides a further elucidation still before diving into proofs.)

Let S_{−} be the set of lower-singular, S_{+} be the set of upper-singular elements of A. We shall find:

Theorem 3. S_{−} is IT -separable iff S_{+} is T I-separable.

In this case we shall call (A, T) singular-separable.

Theorem 4. There are only countably many IT -equivalence classes containing lower-singular elements iff there are only countably many T I-equiv-alence classes containing upper-singular elements.

21Indeed, the author considered and solved the problem without knowing of [6]. He was lead to the problem by Peter Schuster’s (member of the Mathematical Institute at Munich University) suggestion.

22There is a precursor to these generalizations in Fishburn’s proof of his characterization of interval orders having CBRIRs—cf. Fn. 35 and Proposition 1 below. Moreover, they appear in disguise in his proof that (F1) implies existence of an ABRIR.

In this case we shall call (A, T) singular-countable. Again, mentioning equivalence classes may be avoided by stating the condition equivalently as every subset of S_{−} linearly ordered by IT be countable or as every subset of S_{+} linearly ordered by TI be countable.

We call (A, T) regular-separable if A \ S_{−} is IT -separable and A \ S_{+} is T I-separable.^{23}

The terms thus explained allow the following solutions of the characterization problems introduced before. Theorem 5 is meant to be the main result of the paper.

Theorem 5. The following conditions are equivalent.^{24}

(i) (A, T) has an ABRIR;

(ii) (A, T) has an ARIR;

(iii) (A, T) is singular- and regular-separable.

Theorem 6. The following conditions are equivalent.^{25}

(i) (A, T) has an OBRIR;

(ii) (A, T) has an ORIR;

(iii) (A, T) has a WFPR;

(iv) (A, T) is singular-countable and regular-separable;

(v) (D2) holds.

Finally, as announced at the end of Subsection 3.1, the new singularity notions allow confining the countability condition (F2) occuring in Condition (iv) of Theorem 1 to an (in general proper) subset of the set of equivalence classes that (F2) is about in the following way.

Theorem 7. Each of the conditions of Theorem 1 is equivalent to the conjunction of (F1) with

(G) there be only countably many T I-equivalence classes which contain no upper-singular element and for whose elements a the set of b such that a T b has some IT -minimum, but no lower-singular one.^{26} By analogy to Subsection 3.1, (G) could equivalently be worded thus: Every subset of A which is linearly ordered by T I, which contains no upper-singular element, and for every element c of which the set of a such that c T a has some IT -minimum, but no lower-singular one, be countable.

23The intervals of the lexicographic order on R × N refute the conjecture that the two defining conditions might be equivalent by analogy to the case of singular-separability.

24To elucidate the second remark after Theorem 1, the equivalence even holds with assuming that (A, T) be an interval order only in (iii).

25Again, the equivalence holds with assuming that (A, T) be an interval order only in (iv) and (v).

26Since, as noted above, a singular element is both lower- and upper-singular, a set containing no lower- or no upper-singular element is a set containing no singular element— therefore the set of equivalence classes mentioned here is a subset of that mentioned in (F2), indeed.

Theorem 7 is meant to show that our singularity notions are somewhat more fundamental than Fishburn’s singularity notion: Our notions tie (F2) to a(n in general) smaller set; more generally, they help to solve the same problems as Fishburn’s notion as well as new problems.

3.4 Conditions (F1) etc.

The “relative position” of (F1) with respect to Condition (iii) of Theorem 5 and to Condition (iv) of Theorem 6 is the following.

Theorem 8. Of the following conditions, each implies the next one without itself being implied by it.

(i) (A, T) is singular-countable and regular-separable;

(ii) (F1) holds;

(iii) (A, T) is singular- and regular-separable.

By Theorem 5, this—or rather our proof of it—yields another insight into Fishburn’s result that (F1) is sufficient for the existence of an A(B)RIR. Another immediate consequence is

Corollary 1. Each of the conditions of Theorem 6 implies each of the conditions of Theorem 5—but not conversely.^{27}

3.5 Real homomorphisms, “exact” representations.

This subsection provides at least one definition of vital importance and prepares some generalizations of some of Fishburn’s [8, 9] results. It is concerned with representing IT and T I in some strict manner by RIRs.

We say that φ is a (strong) real R-homomorphism on X if it maps X into R and R is some binary relation such that for all x, y ∈ X

x R y iff φ(x) < φ(y).

For the sequel one might particularly keep in mind that a real R-homomor-phism on X maps x, y ∈ X to the same real iff x ∼_{R} y.

Furthermore, if (Q, L) is a linear order and H, H′ ∈ I(Q, L), then H (L-)exceeds H′ below if p L q for some p ∈ H and all q ∈ H′. Call an IR ρ of (A, T) in (Q, L) lower-exact if, for a, b ∈ A, ρ(a) exceeding ρ(b) below implies a IT b.^{28}

27The implications, of course, follow directly from the fact that singular-countability implies singular-separability or, therefore, that Condition (iv) of Theorem 6 implies Condition (iii) of Theorem 5. Only that the converses do not hold needs Theorem 8.

Dually, H (L-)exceeds H′ above if q L p for some p ∈ H and all q ∈ H′. Call an IR ρ of (A, T) in (Q, L) upper-exact if, for a, b ∈ A, ρ(a) exceeding ρ(b) above implies b T I a.^{29}

Call ρ exact if it is both lower- and upper-exact.

An exact IR of (A, T) maps a, b ∈ A to the same interval iff a, b are both IT - and T I-equivalent^{30} (whereas this equivalence does not suffice for exactness). As another elucidation, if an IR of (A, T) in (Q, L) is exact, it is a “strong” homomorphism of (A, IT) and of (A, T I) to the respective structures derived from the natural interval order of (Q, L).^{31} The converse does not hold.

The proof of [9, Thm. 2.6] shows that every interval order has an exact IR. Readers acquaintant with the matter will know a number of IRs without ever having thought of a non-exact one. A CRIR or ORIR ρ is lowerexact iff inf ρ(a) = inf ρ(b) whenever a ∼_{IT} b, etc. Concerning existence of exact CRIRs, Fishburn [8, 9] told everything. We extend his theorem in Subsection 3.6 and thus postpone the matter. Fishburn did not deal with exactness in the case of ARIRs. We shall do in the same Subsection 3.6. At this place, we just mention what concerns ORIRs:

Corollary 2. The following conditions are equivalent.^{32}

(i) (A, T) has an ORIR;

(ii) (A, T) has an exact OBRIR;

(iii) (A, T) has a WFPR (u, v) such that u is a real IT -homomorphism on A and v is a real T I-homomorphism on A.

3.6 Representing singularity.

Fishburn ([8, Thm.s 2, 5] [9, Thm.s 7.6, 7.10]) found that, if a CBRIR exists,^{33} then there is an exact one which maps each singular element of A to a singleton; and if an ABRIR exists, then there is one which maps each singular element of A to a singleton (nothing said about exactness).

28By Lemma 2 below, the converse implication holds anyway.

29Again by Lemma 2 below, the converse implication holds anyway.

30This may be considered an aspect of “minimality” according to Section 1: If ρ is exact and, e.g., a ∼_{IT}, then ρ(b) does not need “additional” points below ρ(a).

31To be precise, let !L! be as defined in Fn. 8. An exact IR of (A, T) in (Q, L), then, is a strong homomorphism from (A, IT) to (I(Q, L), ∼_{!L!} !L!) and from (A, T I)

to (I(Q, L),!L! ∼_{!L!}).

32According to the second remark after Theorem 1, the equivalence holds without assuming that (A, T) be an interval order.

33For exegetical doubts cf. Fn. 18, for their irrelevance cf. Theorem 1.

These results can be extended to lower- and upper-singularity, to ORIRs and concerning exactness as follows.

It is easy to see that, for a, b ∈ A, b is an IT -maximum of { c | a I c } iff a is a T I-minimum of { c | b I c }.^{34} Define a I* b to hold then.^{35} a then is a “witness” for b being lower-singular, and, dually, b is a “witness” for a being upper-singular.^{36} (Now a is singular in Fishburn’s [8] sense iff a I* a.)^{37}

Call an IR ρ of (A, T) in some linear order (Q, L) singular-exact if, (exactly)^{38} for (a, b) ∈ I*, ρ(a) and ρ(b) have exactly one element in common.^{39}

Our announced extensions then are:

Corollary 3. The following conditions are equivalent.^{40}

(i) (A, T) has a CRIR;

(ii) (A, T) has an exact and singular-exact CBRIR;

(iii) (A, T) has a FPR (u, v) such that u is a real IT -homomorphism on A, v is a real T I-homomorphism on A, and u(b) = v(a) iff a I* b.

We could have dealt with exactness and singular-exactness separately to tell more (cf. Corollary 2 above). This is done in Section 5.

Corollary 4. (A, T) has an ARIR iff it has an exact and singular-exact ABRIR.^{41}

In contrast, exact and singular-exact O(B)RIRs exist trivially, if at all:

Corollary 5. If (A, T) has an ORIR, the following conditions are equivalent.^{42}

(i) (A, T) has a(n exact and) singular-exact O(B)RIR;^{43}

(ii) S_{−} = ∅;

(iii) S_{+} = ∅.

34Cf. Proposition 1 in Subsection 4.5.

35I \ (I* ∪ (I*)^{−1}) is what Fishburn calls I in [8, (10)] and [9, p. 137].

36See Proposition 1 again.

37See Lemma 5.

38If ρ is any IR, ρ(a) ∩ ρ(b) is no singleton if not a I* b. This follows from Lemma 2 below.

39This quite obviously deserves to be called a “minimality” condition.

40Again, the equivalence holds without assuming that (A, T) be an interval order.

41Again, the equivalence holds without assuming that (A, T) be an interval order.

42The second remark after Theorem 1 makes no difference here, since existence of an ORIR implies that (A, T) is an interval order, anyway.

43There is no interesting WFPR version analogous to the FPR version in Corollary 3.

The parentheses are meant to indicate that singular-exactness is the problem, not exactness or boundedness.

In fact, Fishburn’s and our proofs of representability claims show that (A, T) has some exact and singular-exact CIR as well as some exact and singular-exact AIR in any case (it will be clear what these abbreviations and the following one are to be meant for “abstract” IRs); and that it has some singular exact OIR iff S_{−} = ∅ or, equivalently, S_{+} = ∅.^{44}

3.7 Extending Fishburn’s results on semiorders.

In [8, p. 97], Fishburn defines a RIR ρ (of (A, T)) to be monotonic if inf ρ(a) < inf ρ(b) and sup ρ(a) > sup ρ(b) for no a, b(∈ A). He then states two theorems on existence of such RIRs for semiorders.^{45} For ARIRs, however, there seems to be a more adequate notion: Call an IR ρ of (A, T) in some linear order (Q, L) semiorderlike if ρ(a) L-exceeds ρ(b) below and above for no a, b ∈ A. Now, monotonicity and semiorderlikeness are the same for CRIRs as well as for ORIRs, whereas for ARIRs semiorderlikeness only implies monotonicity—the converse not holding.

Rather obviously:

Corollary 6. Any exact RIR of (A, T) is semiorderlike (and, hence, monotonic) iff (A, T) is a semiorder.^{46}

Since in all his proofs of theorems mentioned so far, Fishburn presents exact RIRs, Corollary 6 (or its proof) is suggested to be an alternative to Fishburn’s proofs of his theorems on monotonicity.

Moreover, Fishburn’s results might be extended in various ways according to the two previous subsections, e.g.:

Corollary 7. In corollaries 2 through 5, ‘exact’ may be replaced by ‘exact and semiorderlike’ iff (A, T) is a semiorder.

To summarize: Closed/open/arbitrary representability implies exact representability of the respective kind; and in case of semiorders, it implies respective semiorderlike (a fortiori: monotonic) representability. The slogans are: Exactness is no problem; and for semiorders, semiorderlikeness (monotonicity) is no problem.

Furthermore, Fishburn [8, p. 97] defines a RIR ρ to be strictly monotonic if, for all a, b ∈ A, inf ρ(a) < inf ρ(b) iff sup ρ(a) < sup ρ(b). He states that a strictly monotonic CRIR exists where any CRIR exists, but confesses to have been unable to decide the case of ARIRs. Indeed, for ARIRs the question may be somewhat ill-posed, since, again, a perhaps more adequate notion presents itself: Call an IR ρ of (A, T) in some linear order (Q, L) strictly semiorderlike if, for any a, b ∈ A, ρ(a) L-exceeds ρ(b) below iff ρ(b) L-exceeds ρ(a) above. Now like above, strict monotonicity and strict semiorderlikeness are the same for CRIRs as well as for ORIRs, whereas for ARIRs strict semiorderlikeness only implies monotonicity—the converse not holding.^{47}

44In the present paper, we omit a third kind of “exactness” (“minimality”): An IR ρ might be required to meet that, if a T * b, then ρ(a), ρ(b) should be “as tight as possible”

(unless a ∉ S_{+}, b ∉ S_{−}; ρ(a) ∩ ρ(b) interval [but for one point]). Our proof of existence of an ARIR, however, shows existence of an ARIR meeting all three kinds of “exactness”.

45His [9, Sec.s 7.5f.] essentially states the same theorems without explicitly introducing the notion of monotonic RIRs.

46Again, the equivalence holds without assuming that (A, T) be an interval order.

In the present paper at least, we refuse to extend Fishburn’s theorem concerning this notion.^{48} Besides a space-time reason, there is a moral reason:

Corollary 8. Assume (A, T) is a semiorder having an exact RIR ρ. Then ρ is strictly semiorderlike iff IT = T I.

(This does not hold for strict monotonicity in place of strict semiorderlikeness.) We deem exactness a very high virtue; therefore, we consider a strictly monotonic RIR ρ of (A, T) “cheating” unless IT = T I. On the other hand, if IT = T I, (since exactness is granted by earlier results) strict monotonicity deserves no particular attention. Furthermore, the method of creating IRs used in the present paper only yields exact IRs (cf. Corollary 8) and is not as apt to create “extra points” needed for strict semiorderlikeness as Fishburn’s is.^{49}

Nevertheless, in contrast to the case of strict monotonicity, we are able to decide whether existence of a RIR entails existence of a strictly semiorderlike one:

Theorem 9. The natural interval order of all real intervals having length 1 and containing their lower boundaries is a semiorder having its identity as a (strictly monotonic!) RIR but having no strictly semiorderlike RIR.

3.8 Empirical significance?

Our results on ARIRs may be of mathematical value only. Empirical meaning of real intervals representing two alternatives or experimental stimuli and differing just in one or two real numbers may be difficult to explicate. To make things worse, the results are of no value when A is finite. Otherwise, however, it seems difficult to imagine an economic or psychological theory concerning an infinite set of possible alternatives or stimuli not bearing some topology relatively to which borders of real intervals change continuously (cf. Subsection 3.1). With respect to this, ARIRs are strange, while ORIRs (WFPRs) might be comparable to CRIRs (FPRs) (to be investigated).

47Cf. Theorem 9.

48[9, Thm. 7.8] states the same theorem without explicitly introducing the notion.

49However, we believe that Fishburn’s [8, Thm. 10]=[9, Thm. 7.8] can be extended to ARIRs and ORIRs in the way one would expect. The proof would require quite a complex modification of Fishburn’s respective construction of a weak order on a “doubled” version of A, taking into account lower- and upper-singularity in a similar way as in our suffiency proofs. We withhold this for reasons indicated above.

3.9 Where are the proofs?

This subsection guides from previous claims—in the order of their appearance above—to the places below where they are treated.

Some remarks or clarifications on Theorem 1 are presented in sections 5 and 6. Theorem 2 is proved in Subsection 6.5. Theorems 3 and 4 are proved in Subsection 6.4.

Necessity of representability conditions in theorems 5 and 6 is proved in Section 7. Sufficiency of the same conditions is proved in Subsection 8.5 for Theorem 5 and in Subsection 8.6 for Theorem 6. Concerning (D1) and (D2), we are just reporting [6] without presenting own proofs.^{50} Boundedness in both theorems and Condition (iii) of the latter are dealt with in Section 5.

Theorem 7 is proved in Subsection 6.6, Theorem 8 in Subsection 6.5. Corollary 1, told to be immediate from the latter theorem, needs nothing more.

Section 5 deals with corollaries 2 and 3. Besides, corollaries 2 through 4 need respective theorems 6, 1, and 5 as well as respective subsections 8.6, 8.2, and 8.5. Corollary 5 needs Corollary 2 and Section 7.

Claims of Subsection 3.7 are treated in Section 9.

The text has been arranged to make each of sections 6–8 work as if the other two were not present. By contrast, most of Section 4 will be needed for each of those sections.

4 Additional general preliminaries.

4.1 Further conventions concerning binary relations.

If R ⊆ X × X′ (and the context exhibits no such sets larger than X, X′), to allow succinct notations we just write Rx′ instead of { x ∈ X | x R x′ } and, dually, xR instead of { x′ ∈ X′ | x R x′ }.

We say that some binary relation R ( ⊆ X × X, say) has some property on a set Y (normally, Y ⊆ X) if R ∩ (Y × Y) has that property. Examples will be presented in Subsection 4.2.

R-Min Y will denote the set of R-minima of Y. For asymmetric R—to which we shall apply the notation exclusively—these are elements x of Y such that y R x for no y ∈ Y, or equivalently, such that x ≺ ∼_{R} y for all y ∈ Y. Dually, R-Max Y will be the set of R-maxima of Y.

50Theorem 6 could have been proved using the result of [6] by easily showing “directly”, i.e., just in terms of interval orders, equivalence of Condition (iv) with (D2).

4.2 Weak orders, their quotients, and representability.

A binary relation R (strictly) weakly orders some set X—and (X, R) will then be called a weak order—, if R is asymmetric on X and ≺ ∼_{R} is transitive on X. The latter condition is called negative transitivity of R.^{51} Recall from Subsection 2.1 that, for R weakly ordering X (as well as for any asymmetric binary relation R), x ≺ ∼_{R} y iff not y R x as well as iff x (R ∪ ∼_{R}) y. It follows that ∼_{R} is transitive on X (since at least ∼_{R} ⊆ ≺ ∼_{R}∩≺ ∼_{R}^{−1}) and that, since ∼_{R} is reflexive and symmetric from the start by its definition and by asymmetry of R, ∼_{R} is an equivalence relation on X.^{52}

We denote the corresponding equivalence class that x ∈ X belongs to by [x]_{R}. We even shall call it an ‘R-equivalence class’ (as we did in (F2) already). For Y ⊆ X, Y/R will be { [x]_{R} | x ∈ Y }.^{53} Moreover, according to the ensuing Lemma 1, a relation R/Y on Y/R is well defined by the condition

[x]_{R} R/Y [y]_{R} iff x R y (x, y ∈ X).

Lemma 1. Assume R ⊆ X × X weakly orders X. Then RR ⊆ R (R is transitive); R≺ ∼_{R} ⊆ R; and ≺ ∼_{R}R ⊆ R.

This may be considered “folklore”; though, we briefly present a proof.^{54}

Proof. If x R y ≺ ∼_{R} z, negative transitivity implies x ≺ ∼_{R} z. For R≺ ∼_{R} ⊆ R, it remains to show that not x ∼_{R} z. But x ∼_{R} z would imply y ≺ ∼_{R} z ≺ ∼_{R} x and, by negative transitivity, y ≺ ∼_{R} x, which would (by asymmetry) contradict the assumption x R y.

This yields R≺ ∼_{R} ⊆ R, and dually obtains ≺ ∼_{R}R ⊆ R.

Finally, x R y R z (transitivity, i.e.) is a special case of x R y ≺ ∼_{R} z (or of x ≺ ∼_{R} y R z—as you like).

It may be helpful to notice that (X/R, R/X) is a linear order (if R weakly orders X).^{55} A linear order (Q, L) may be viewed as a “reduced” weak order in the sense that L-equivalence classes contain just one element.^{56} Conversely, weak orders might be viewed as “redundant” linear orders the equivalence classes of which are occupied by a plurality of elements.—This theme will be continued under the label of ‘congruency’.

51In this case, namely, the “negation” of R is transitive.

52In fact, if R′ is any asymmetric binary relation, ∼_{R′} being transitive and being an equivalence relation are equivalent.

53To be sure, ⋃(Y/R) is, in general, no subset of Y.

54We are presenting proofs of “trivia”, which may appear superfluous to some readers but be helpful for others, in small type.

55For deep enlightenment cf. Fishburn’s [9, Thm. 1.2], but note that his notation is not as precise as ours.

56Compare categories where each object is isomorphic to itself only.

In proving Theorems 5f., we shall, like Fishburn [8, 9], use the “Cantor route”,^{57} or better: the “Birkhoff/Milgram route”^{58} to real representability:

Real Homomorphism Theorem. There is a (strong) real R-homomor-phism on X iff R weakly orders X such that X is R-separable.

This theorem is proved in [7, Thm. 3.1] as well as in [11] or in [17, Subsec. 3.1.4].^{59} Concerning the “range of applicability” of the separability notion involved (mentioned in Subsection 2.1 above), the equivalences of definitions according to [3, 1.4.3.f.] are proved there for weak orders (X, R), indeed.

4.3 How interval representations handle I, IT, and T I.

The following lemma is an easy consequence of the definitions of I, IT, T I, IRs, and intervals.^{60} We leave the proof to the reader.

Lemma 2. Assume ρ is an IR of (A, T) in a linear order (Q, L) and a, b ∈ A. Then ρ(a) ∩ ρ(b) ≠ ∅ iff a I b;^{61} if a IT b, then ρ(a) exceeds ρ(b) below; and if a T I b, then ρ(b) exceeds ρ(a) above.^{62}

4.4 Vital features of T, I, IT, and T I.

The ensuing has been presupposed several times earlier in this paper. It is well-known at least since [7] (or see [9, pp. 21f.]).^{63}

Lemma 3. IT and T I weakly order A.

Though, we present another proof in order to fit the present framework and some needs of later proofs.

In advance we gather, for reference, some other easy observations.

57Fishburn—[8, p. 93], [9, p. 133]—attributes the following theorem ‘essentially’ to Cantor’s 1895 [4]—cf. [5]. However, there is a trick in proving the necessity of the following representability condition which cannot be seen from this theorem of Cantor’s and neither from its proof. Moreover, a problem with the sufficiency part is that Cantor’s [4] original theorem uses a separability notion that is strictly stronger than the separability notion used in the “Real Homomorphism Theorem”—cf. the modern, more clearly purely ordertheoretic version of Cantor’s [4] theorem in [3, 1.5.8] and [3, 1.4.3, 1.4.5].

58To continue the previous footnote: according to [17, Subsec. 3.1.4] and [10], the ensuing theorem should better be attributed to G. Birkhoff and A. Milgram.

59Also cf. [3, Thm. 1.4.8].

60A rigorous proof, however straightforward, would need some lines and cases.

61Here, convexity and non-voidness of intervals are essential.

62Recall the definitions of Subsection 3.5.

63It must have been known to B. Russell according to [18] already, where irreflexivity and transitivity of T and transitivity of IT are assumed, which is another way of defining interval orders.

Lemma 4. T is irreflexive and

(W)  T IT ⊆ T.^{64}

I is irreflexive; T is transitive and asymmetric; and the following hold:

T ⊆ IT ∩ T I; (1) ∼_{IT} ∪ ∼_{T I} ⊆ I. (2)

Proof. Irreflexivity of T and (W) follow from “abstract” interval representability of (A, T) as fixed in Subsection 2.2. E.g., if ρ is an IR and a T c I d T b, ρ(c) ∩ ρ(d) has (by Lemma 2) an element which “tops” all members of ρ(a) and “is topped” by each member of ρ(b), etc.^{65}—Irreflexivity of T implies reflexivity of I by definition of the latter. Therefore, a I a T b and a T b I b, if a T b; which proves (1). The latter yields (2) and, by (W), T T ⊆ T IT ⊆ T —so T is transitive and, by irreflexivity, asymmetric.

Proof of Lemma 3. IT and T I are irreflexive by definition of I. (W) implies IT IT ⊆ IT and T IT I ⊆ T I, which say that IT and T I are transitive; thus, they are asymmetric, and ≺ ∼_{IT} , ≺ ∼_{T I} are their respective “reverse negations”.

The definitions of IT and T I, therefore, imply the equivalences

(3)  a ≺ ∼_{IT} b iff T a ⊆ T b;
(4)  a ≺ ∼_{T I} b iff bT ⊆ aT.

(3), e.g., obtains thus by contraposition: If b I c T a, then c ∈ T a \ T b. If, conversely, c ∈ T a\T b, then either c I b, implying b IT a, or b T c, which by transitivity of T (Lemma 4) yields b I b T a.—(3) and (4) yield transitivity of ≺ ∼_{IT} and ≺ ∼_{T I}.

Now, asymmetry of IT and T I together with (1) adds

(IT ∪ T I) ∩ T^{−1} = ∅. (5)

4.5 I*, singularity, and regularity.

This subsection exhibits easy proofs of incidental claims in Subsection 3.6 plus something more needed later on.

64In fact, these two conditions were used by N. Wiener [21] to define what is nowadays called ‘interval orders’. Nowadays, irreflexivity of T and if a T b and c T d, then a T d or c T b are common to define the same notion. It is the same notion, indeed: Assuming b I c, the ‘common’ condition immediately yields (W). If you start at (W) and irreflexivity, x T y I y T z yields transitivity of T, so assuming not c T b, the above ‘common’ condition follows from transitiviy in the case of b T c and immediately from (W) in the case of b I c.

65All of the following is visually clear using ρ—cf. Lemma 2; though we do without to achieve some formal rigour at the cost of relatively little space.

4 ADDITIONAL GENERAL PRELIMINARIES. 22

Proposition 1. b ∈ IT -Max Ia iff a ∈ T I-Min Ib. So b ∈ S_{−} iff I*b ≠ ∅; and a ∈ S_{+} iff aI* ≠ ∅. Moreover, S_{−} = ∅ iff S_{+} = ∅.

The first sentence justifies our definition of I*.

Proof. By duality, proof of ‘only if’ suffices for the first sentence. For reductio, assume b ∈ IT -Max Ia and a ∉ T I-Min Ib. The second assumption implies existence of c, d such that b I c T d I a, so b IT d I a. But this contradicts the first assumption, since the latter entails b I a.

The second sentence immediately follows from the definitions and straightforwardly implies the third one.

Lemma 5. a ∈ S iff a I* a; so S ⊆ S_{−} ∪ S_{+}.

Proof. For the first statement, we show its contraposition. If not a I* a, there are b, c such that a I b T c I a. Hence not b I c, so a ∉ S.—If a ∉ S, there are b, c ∈ Ia such that not b I c. Without loss of generality b T c. Then a I b T c I a, so—by any one of the two definitions of I* in Subsection 3.6—not a I* a.

Now the second statement obtains by Proposition 1.

So far, regularity has been defined “by negation” (via lower-/upper-singularity) only. Here is a “positive” characterizing^{66} feature.

Lemma 6. If a IT b and a ∉ S_{−}, there is an infinite IT -chain in a(IT) ∩ (IT)b. Dually, if a T I b and b ∉ S_{+} there is an infinite T I-chain in a(T I) ∩ (T I)b.^{67}

Proof. a IT b means that there is some c_{0} ∈ aI ∩ T b. If a ∉ S_{−}, no c_{n} ∈ aI ∩ T b is a T I-minimum of aI, so there is some c_{n+1} such that a I c_{n+1} T I c_{n}. By (W), this yields c_{n+1} ∈ T b. Moreover, there is some d_{n} ∈ A such that c_{n+1} T d_{n} I c_{n}.

To conclude, there are infinite sequences (c_{n}) and (d_{n}) such that

a I c_{n+2} T d_{n+1} I c_{n+1} T d_{n} I c_{n} T b

for any n ∈ N. The quintessence of this formula is a IT d_{n+1} IT d_{n} IT b, which meets the first claim concerning some infinite sequence (d_{n}) in A.

We need not carry out the dual matter.

4.6 Congruency—exemplified.

If (X, R) is a weak order, a subset Y of X will be called R-congruent if it is a union of R-equivalence classes. This is the same as being “closed” with respect to R-equivalence.^{68} Some examples needed below are the following.

66Lemma 6 claims one direction of each characterization only; the proof of the converse direction is easy to see at least from the proof presented.

67Actual infinity will never be used; we claim and prove it for narcissistic reasons only.

68I.e., Y is R-congruent iff x ∼_{R} y ∈ Y implies x ∈ Y.

Lemma 7. In the same situation, xR and Rx are R-congruent for each x ∈ X. For a ∈ A, aT and Ia ∩ a≺ ∼_{IT} are IT -congruent, while T a and Ia ∩ ≺ ∼_{T I}a are T I-congruent.

Seemingly everything about weak orders lies clearly visible to the mathematical inner eye. Though, some indications to “formal” proofs might be appropriate.

Proof. If x R y′ ∼_{R} y, then x R y by Lemma 1.

a T b′ ∼_{IT} b implies T b′ ⊆ T b by (3) and, therefore, a T b.

Now assume a (I ∩ ≺ ∼_{IT}) b′ ∼_{IT} b. Then, negative transitivity of IT (Lemma 3) yields a ≺ ∼_{IT} b. a I b remains to be proved. For reductio, assume a T b or b T a. In the first case, (3) yields a T b′; while in the second case, (3) yields the b′ T a—both contradicting the assumption a I b′.

The remaining proofs are duals of the former ones, using (4) where (A, T) is concerned.

An obvious, though eventually vital feature of congruent sets is

Lemma 8. If (X, R) is a weak order and Y ⊆ X is R-congruent and nonvoid, R-Min Y as well as R-Max Y is one R-equivalence class, if not void.

If we have R ⊆ X′ × X′′, R′ ⊆ X′ × X′ such that R′ weakly orders X′, and R′′ ⊆ X′′ × X′′ such that R′′ weakly orders X′′, then we shall call R a strong R′-R′′-congruence if both of the following conditions are satisfied.

(C1) For all x′, y′ ∈ X′ and x′′, y′′ ∈ X′′ such that x′ R x′′ and y′ R y′′
x′ R′ y′ iff x′′ R′′ y′′;

(C2) ∼_{R′}R∼_{R′′} ⊆ R.

Thus, if R is a map X′ → X′′, (C1) just means that R is a (“strong”) (cf. Subsection 2.2) homomorphism respecting R′ and reflecting R′′; conversely, (C1) generalizes the latter notion from maps to arbitrary binary relations. (C2) tells that R treats R′-equivalent elements the same way, as well as R′′-equivalent elements.^{69}

(C2) follows from the conjunction of ∼_{R′}R ⊆ R and R∼_{R′′} ⊆ R. In proofs, we shall only consider the first part, for the proof of the other one will go dually.

As a particular feature of such relations easily obtains

Lemma 9. Assume the above situation (so (X′, R′) and (X′′, R′′) are weak orders and R is a strong R′-R′′-congruence). Then for each x′ ∈ X′, x′R is an R′′-equivalence class if not void, and x′R = y′R if x′ ∼_{R′} y′; dually for each x′′ ∈ X′′, Rx′′ is an R′-equivalence class if not void, and Rx′′ = Ry′′ if x′′ ∼_{R′′} y′′.

69Of course, identity is implied by the inclusion statement of (C2), since the indifference relations are reflexive.

Proof. If x′ R x′′ and x′ R y′′, then x′ ∼_{R′} x′ and (C1) imply x′′ ∼_{R′′} y′′; so x′R is at most one R′′-equivalence class. By (C2), x′R is, if non-void, at least one R′′-equivalence class. Again by (C1), it is the same as y′R if neither x′R nor y′R is void and if x′ ∼_{R} y′. But if one is not void, by (C2) neither is the other. Dual reasonings yield what remains.

Thus, if in particular X′ = X′′ and R′ = R′′, R induces a relation R/R′ on X′/R′ well-defined by the condition

[x]_{R′} R/R′ [y]_{R′} iff x R y (x, y ∈ X′).

An example for use of this notation will appear in Subsection 4.7.

Another example for strong congruency is I* (introduced in Subsection 3.6 and reconsidered in Subsection 4.5).

Lemma 10. I* is a strong T I-IT -congruence.

Proof. For (C1), assume a I* b and a′ I* b′.

If a T I a′, there is c such that a T c I a′; therefore b I a T c. On the other hand, c I a′ I* b′ implies c ≺ ∼_{IT} b′. Putting these consequences together yields b IT c ≺ ∼_{IT} b′. Since IT weakly orders A (Lemma 3), Lemma 1 yields b IT b′.

The converse is proved dually using the dual version of the definition of I*. For (C2), conclude a′ ∈ T I-Min Ib = T I-Min(Ib ∩ ≺ ∼_{T I} b) from a ∼_{T I} a′ I* b

to get a I* b by lemmas 7f.

As a consequence, we get another example of congruency of sets.

Lemma 11. S_{−} is T I-congruent; dually, S_{+} is IT -congruent.

Proof. For the first of the dual parts assume a ∈ S_{−} and a ∼_{T I} b. By lemmas 9 and 10, then, I*a = I*b. Therefore b ∈ S_{−}, as well.

As a further example of strong congruency we define a relation T * on A by

T *:= T \ T IT.

This is how Fishburn [8, p. 95] started to present his version of Condition (F2). Note that, by (W), a T * b iff a ∈ T I-Max T b and iff b ∈ IT -Min aT.^{70} So if (A, T) is natural (Subsection 2.2), a T * b means that a, b “touch” each other in the sense that a is one of the most close intervals below b and—equivalently—that b is one of the most close intervals above a.

Now we continue the previous findings by

Lemma 12. T * is a strong T I-IT -congruence.

Proof. For (C1), assume a T * b and a′ T * b′. If a T I a′, there is c such that a T c I a′. By a T * b, this implies b ≺ ∼_{IT} c; while by a′ T * b′ (and T * ⊆ T), it implies c IT b′. By Lemma 1 both consequences together yield b IT b′. (Conversely dually.)

(C2) obtains, similarly to the above, by reading a′ T * b as a′ ∈ T I-Max T b and from lemmas 7f.

70[20, p. 59, (19)] seems to overlook that the latter two propositions are equivalent.

4.7 “Neighbourhood”, “jumps”, and regularity.

For any R weakly ordering some set X, we define an associated relation

N_{R} := R \ RR.^{71}

x N_{R} y means that x and y are immediate R-neighbours (in “direction” x R y, to be precise), and might have been defined equivalently by x ∈ R-Max Ry or by y ∈ R-Min xR.

Lemma 13. In the situation just depicted, N_{R} is a strong R-R-congruence.

Proof. For (C1), assume x′ N_{R} x′′ and y′ N_{R} y′′. If x′ R y′, then x′′ ≺ ∼_{R} y′ by x′′ ∈ R-Min x′R; and Lemma 1 using N_{R} ⊆ R yields x′′ R y′′. The converse is proved dually by using y′ ∈ R-Max Ry′′.

For (C2), interpret a ∼_{R} a′ N_{R} b as a ∼_{R} a′ ∈ R-Max Rb. a N_{R} b then obtains by lemmas 7f.

We call each element of N_{R}/R an R-jump of X. By the above “Real Homomorphism Theorem”, representability of (X, R) by a “utility function” requires that there are only countably many R-jumps of X—cf. Lemma 15 below.

The following concerns regularity.

Lemma 14. If a ∈ A \ S_{−}, then aN_{IT} = ∅.

Proof. Assume a ∉ S_{−} and, for reductio, a N_{IT} b for some b ∈ A. This yields a IT b. By Lemma 6 and the first assumption, there is some c ∈ A such that a IT c IT b, contradicting the second assumption.

4.8 Miscellanea on separability.

We insert a step into the definition of separability, a step we omitted in Subsection 2.1. If R is some binary relation on a set X, a set D will be called R-dense in X if D ⊆ X and if for all x, y ∈ X such that x R y there is d ∈ D such that x ≺ ∼_{R} d ≺ ∼_{R} y. Thus, X is R-separable iff there is a countable set that is R-dense in X. We are now in a position to state, for reference, the obvious

Lemma 15. Let R weakly order X and D be R-dense in X. Then, for every R-jump (B, C) of X, (B ∪ C) ∩ D is non-void. If X is R-separable, therefore, it has only countably many R-jumps.

Furthermore we shall need:

71For more preciseness, the term should also specify a range, since the latter determines “neighbourhood” of two objects as well as the relation R. (In the situation depicted, new “neighbourhoods” of two objects my arise by removing some others between them.)

Nevertheless, we drop the range and shall indicate it by the context.

5 PROOFS: “UNBOUNDED”/FP REPRESENTATIONS. 26

Lemma 16. If (X, R) is a weak order such that X is R-separable, and if Y ⊆ X, then Y is R-separable.

Proof. Assume the hypothesis. By the Real Homomorphism Theorem, then, there is a real R-homomorphism on X. It is a real R-homomorphism on Y ⊆ X, as well. Therefore, the Real Homomorphism Theorem entails that Y as well is Rseparable.^{72}

5 Proofs: “Unbounded”/FP representations.

This section provides the obvious (if so: skippable) explanations

1. of the equivalences of the first two conditions in each of Theorem 1 and of Theorems 5f., resp., (where irrelevance of the boundedness restriction for the existence of RIRs of the repective kinds is claimed);

2. concerning the existence of WFPRs in Theorem 6;

3. concerning exactness, singular-exactness and what corresponds to them for FPRs or WFPRs according to corollaries 2 and 3.

A CBRIR is a CRIR, an ABRIR is an ARIR, an OBRIR is an ORIR (thus in each case, existence of a former implies existence of a latter). Concerning the converse existence claims:

As may be recalled from trigonometry or from elementary analysis, arctan is a strictly monotone (therefore one-to-one) map from R onto the open real interval (−π/2, π/2).^{73} Now, if F is some ARIR or some ORIR of (A, T),

a ↦ arctan[F (a)] (a ∈ A)

is an ABRIR or an OBRIR of (A, T), respectively.^{74}—If F is, instead, a CRIR, we proceed essentially in the same way, but we complete arctan[F (a)] by each of −π/2, π/2, resp., whenever one of them is “touched” by arctan[F (a)]. More precisely, we define, for every a ∈ A, l(a) to be ∅ if F (a) is bounded; to be {π/2} if F (a) has a lower, but no upper bound; to be {−π/2} if F (a) has an upper, but no lower bound; finally to be {−π/2, π/2} if F (a) is unbounded in each direction. Then

a ↦ arctan[F (a)] ∪ l(a) (a ∈ A)

is a CBRIR of (A, T).—This completes proofs of all the earlier claims of irrelevance of boundedness restrictions for existence of RIRs.

Next (concerning theorems 1 and 6), by analogy to Subsection 3.1, if F is an OBRIR, u : A → R, a ↦ inf F (a) and v : A → R, a ↦ sup F (a) form a WFPR; and if (u, v) is a WFPR, a ↦ (u(a), v(a)) is an OBRIR.^{75} Thus, as claimed in Theorem 6, existence of a WFPR is the same as existence of an OBRIR. The analogous equivalence in Theorem 1 was explained in Subsection 3.1 already.

72The fact may also be proved elementarily on less than a whole page.

73It is a map inverse to one “branch” of tan = sin / cos. Of course, any other strictly monotone map from R into a bounded real interval would do as well.

74Each real interval occurring has −π/2 as a lower and π/2 as an upper bound.

75According to widespread use, (u(a), v(a)) here denotes { r ∈ R | u(a) < r < v(a) }, of course.

Finally (concerning corollaries 2 and 3), it is easy to check that a CBRIR or OBRIR is exact iff for the corresponding (according to Subsection 3.1) FPR or WFPR (u, v), u is a real IT -homomorphism and v is a real T I-homomorphism (in each case, one direction needs Lemma 2). It is obvious that a CBRIR is singularexact iff for the corresponding FPR (u, v), u(b) = v(a) iff a I* b. This proves equivalence of the last two conditions of corollaries 2 and 3.

6 Proofs on representability conditions.

6.1 Dual conditions in general.

While R-separability is a self-dual notion for any relation R, neither (F2), nor (E), nor (G) are (at least “syntactically”) self-dual.^{76} Though, in their contexts, they may be replaced by their duals.

To make this clear, we begin by introducing some shorthand definitions. If J is a set of real intervals, let J^{∗} be the image of J under multiplying by −1 (e.g., [p, q) turns into (−q, −p]). We say ρ is a RIR of some interval order (X, R) in some set J of real intervals if ρ is an IR of (X, R) in (R, <) such that ρ[X] ⊆ J. By multiplying the members of the image intervals by −1, we obtain some other map ρ^{∗} from X into the set of real intervals. The dual of an interval order (X, R) is (X, R^{−1}). Observe that ρ is a RIR of some interval order T in some set J of real intervals iff ρ^{∗} is a RIR of the dual of T in J^{∗}. Observe, furthermore, that some interval order meets some condition iff the dual interval order meets the dual condition.

Now we may state and prove:

Theorem 10. Let J be some set of real intervals such that J^{∗} ⊆ J. Let (C) be some condition on interval orders necessary and sufficient for existence of a RIR in J. Then the dual of (C) is necessary and sufficient for existence of an RIR in J, too.

Proof. Assume the hypotheses, and let T be some interval order.

For necessity of the dual of (C), assume T has a RIR ρ in J. Then ρ^{∗} is a RIR of the dual T^{∗} of T in J^{∗} and, by hypothesis, in J. By the other hypothesis, T^{∗} meets (C). The dual T of T^{∗}, therefore, meets the dual of (C).

For suffiency of the dual of (C), assume T meets the dual of (C). Then, the dual T^{∗} of T meets (C). By hypothesis, T^{∗} has a RIR ρ in J. ρ^{∗}, then, is a RIR of T in J^{∗}. By hypothesis, it is a RIR in J, as well.

Admittedly, this is no strict mathematical proof. Even the ‘theorem’ is too vague (‘condition on interval orders’) to be a clear mathematical proposition. A clear and strict mathematical version would need to introduce a formal language and to present model-theoretical statements.

76Indeed it is, presumably, not too difficult to find interval orders where one of these conditions holds but not its dual. I.e., the conditions are even “semantically” not self-dual.

6 PROOFS ON REPRESENTABILITY CONDITIONS. 28

When we apply the ‘theorem’ to (F2), (E), and (G) (and to their duals), however, it suffices that the previous indicates how to derive the dual of each of them in their context. Viewing J from Theorem 10 as the set of closed real intervals leads to the following

Corollary 9. In Theorem 1, the dual of (E)^{77} may be added to the list of equivalent conditions, and (F2) may be replaced by its dual. In Theorem 7, (G) may be replaced by its dual.

Proof. The case of (E) is straightforward. For (F2) and (G), one uses that (F1) is self-dual.

While the latter example of Theorem 10 is related to the notion of a CRIR, the other RIR notions introduced earlier lead to further obvious examples of J from Theorem 10.

All the above may have been “folklore” and arises from the “symmetry” of (R, <); i.e., (R, >) is isomorphic to (R, <).

6.2 A preliminary on (F2).

We supply a name for the set (F2) is about. S will denote the set of singular elements of A in Fishburn’s sense. By lemmas 9 and 12, aT * = bT * if a ∼_{T I} b. Therefore, we are allowed to define

G_{0} := { [a]_{T I} | a ∈ A; S ∩ [a]_{T I} = ∅; aT * ≠ ∅; S ∩ aT * = ∅ }.

Thus, (F2) tells G_{0} to be countable.^{78}

6.3 Condition (E).

Condition (E) appears in Theorem 1 just to summarize earlier contributions, relying on the equivalences of (F1)&(F2) with existence of a CBRIR as found by Fishburn and of (E) with existence of a FPR as found by [15]. After Section 5, the claim of Theorem 1 concerning (E) then follows from the obvious correspondence between FPRs and CBRIRs depicted in Subsection 3.1.

77The dual of (E) is: there be a countable D ⊆ A such that for all (a, b) ∈ T there is some d ∈ D such that a ≺ ∼_{T I} d T b. To check that this is the dual of (E), dualize the components a T b, a T d, and d ≺ ∼_{IT} b of (E), then interchange a, b.

78Fishburn [8] originally defined an equivalence relation E on T * such that (a, b) E (a′, b′) iff a T b′ and a′ T b. Now, this is just equivalent to a ∼_{T I} a′: Keep in mind that a T * b and a′ T * b′. Then a ∼_{T I} a′ implies a T b′ and a′ T b by (4). Conversely, prove the contraposition. If a T I a′, say a T c I a′. Then b ≺ ∼_{IT} c by a T * b. Therefore, by (3), T b ⊆ T c, so the assumption c I a′ excludes a′ T c and a′ T b.—Denoting the set of equivalence classes of T * with respect to E by T */E, countability of G′_{0} := { P ∈ T */E | P ∩ (S × A) = ∅ = P ∩ (A × S) } comes very close to how Fishburn [8] presented (F2). But by the equivalence of the conditions noted above, P ↦ pr_{1}[P] is a one-to-one map from G′_{0} onto G_{0}, where pr_{1} denotes the projection to the first factor.

In [9], Fishburn uses another version of G_{0}, which would need too much preparations to be explained in the present framework.

The previous, however, is not the whole truth. Whereas interval orders usually are considered asymmetric and therefore irreflexive, [15] deal with “weak”, i.e., reflexive “interval orders”. Furthermore, it remains to check our claim that Condition (E) presented here is equivalent to what in [15] is defined to be ‘i. o.- separable’. Summarizing, it remains to check whether Subsection 3.1 presents a correct “translation” of [15].^{79}

These tasks are not difficult. But if we rely on Fishburn’s [8, 9] and on having correctly reported them, we may replace such a check by a proof of the following just in terms of (A, T), which may be of some value on its own right.

We begin with some observations concerning singularity.

Lemma 17. If a T * b and a ∼_{T I} c ∈ S, then c N_{IT} b. Dually, if a T * b and b ∼_{IT} c ∈ S, then a N_{T I} c.

Proof. By (2) (Lemma 4), a ∼_{T I} c ∈ S implies a I c. By a T * b obtains c I a T b, thus c IT b.

Now, for reductio, assume c I d′ T d IT b for some d, d′ ∈ A. By Lemma 12, c T * b, i.e., b ∈ IT -Min cT, so not c T d. d T c is ruled out by (5) and the assumption. We conclude c I d.

Using the assumptions about d′, we get d′ I c I d. By c ∈ S, then, obtains d′ I d, which contradicts the assumption d′ T d. Therefore, c IT IT b does not hold.

Lemma 18. Let c, d ∈ S. Then c ∼_{IT} d iff c ∼_{T I} d.

Proof. Assume c ∼_{IT} d. (2) yields c I d. If c T a I d for some a ∈ A, then a I d I c and, by singularity, a I c—contradicting c T a. The assumption d T a I c is rejected by interchanging c and d in the former reasoning. Together, this yields c ∼_{T I} d. The converse direction is proved dually.

We can now prove the main claim of the present subsection.

Proposition 2. (E) holds iff (F1) and (F2) hold.

Proof. Let us firstly assume (F1) and (F2) in order to derive (E). So by T Iseparability of A and by lemmas 3 and 15, there are only countably many T Ijumps. We may, therefore, presuppose a countable D_{+} ⊆ A which intersects with B′ ∩ S whenever there is a T I-jump (B, B′). By IT -separability, there is a countable D_{−} ⊆ A, and, similarly to the previous reasoning, we may assume that D_{−} intersects with the right-hand term of each IT -jump. Furthermore, by lemmas 9 and 12 (strong congruency of T *), for every B ∈ G_{0} we may pick d_{B} from A such that for all b ∈ B, b T * d. Let D_{0} be the countable set { d_{B} | B ∈ G_{0} }. Assume (a, b) ∈ T. We show that the countable set D_{−} ∪ D_{+} ∪ D_{0} contains d such that a T d ≺ ∼_{IT} b.

79One firstly has to check that ≺ ∼_{T} = T ∪ I is an “interval order” in the sense of [15].

Assuming this, [15] define sets B(a, b) := { d ∈ A | there is c ∈ A such that a ≺ ∼_{T} c T d ≺ ∼_{T} b }. (In fact, [15] write A where we write B for having used A for another purpose already.) Now one has to check that the condition a T d ≺ ∼_{IT} b being part of our (E) is equivalent to the original condition d ∈ B(a, b) \ (B(a, a) ∪ B(b, b)).

If not a T * b, there is c such that a T c IT b. Then by IT -separability, there is d ∈ D_{−} such that c ≺ ∼_{IT} d ≺ ∼_{IT} b. By (3) obtains a T d ≺ ∼_{IT} b.

If a T * b, the way of reasoning depends on whether [a]_{T I}, [b]_{IT}, or none of both contain a singular element.

If there is c ∈ S∩[a]_{T I}, Lemma 17 yields c N_{IT} b. By the additional assumption on D_{−}, the latter set contains some d ∼_{IT} b. By strong congruency of T * obtains a T d ≺ ∼_{IT} b.

If there is c ∈ S ∩ [b]_{IT}, Lemma 17 yields a N_{T I} c, and D_{+} has been chosen to contain some singular d ∼_{T I} c. By Lemma 18, c ∼_{IT} d. Furthermore, c ∼_{IT} b, yielding d ∼_{IT} b. Now (3) yields a T d ≺ ∼_{IT} b.

Finally, if S ∩ ([a]_{T I} ∪ [b]_{IT}) = ∅, strong congruency of T * implies S ∩ aT * = ∅. Therefore [a]_{T I} ∈ G_{0}, and there is some d ∈ D_{0} ∩ aT *. Strong congruency of T * now implies d ∼_{IT} b, and this yields a T d ≺ ∼_{IT} b again.

For the other direction, we now assume (E) in order to derive (F1) and (F2). So let D ⊆ A be countable such that for all (a, b) ∈ T there is d ∈ D such that a T d ≺ ∼_{IT} b.

For (F2), we show that there is a one-to-one map B ↦ d_{B} from G_{0} into D. If B ∈ G_{0}, pick b from B and a from bT *. Now we may pick d_{B} from D such that b T d_{B} ≺ ∼_{IT} a.^{80} b T * a implies d_{B} ∼_{IT} a. If B′ ≠ B is another element of G_{0}, Lemma 12 by way of (C1) yields that d_{B′} is not IT -equivalent to d_{B}. Therefore, d_{B} ≠ d_{B′}.

For the IT -separability part of (F1), assume a I c T b. Then c T d ≺ ∼_{IT} b for some d ∈ D, and, therefore, a ≺ ∼_{IT} d ≺ ∼_{IT} b.

Finally, T I-separability follows dually to the previous from the dual of (E), which holds according to Corollary 9.

Instead of proving T I-separability above, we could, by Theorem 11 below, just have proved that there are only countably many T I-jumps.^{81} Indeed, this is a way to meet our announcement of proving Proposition 2 ‘just in terms of (A, T)’— whereas the last sentence of the previous proof draws on Corollary 9, which was not proved ‘just in terms of (A, T)’.

6.4 Singular-separability and -countability.

Proof of theorems 3 and 4. By Proposition 1, S_{−} = ∅ iff S_{+} = ∅.

Otherwise, by strong congruency of I* (lemmas 9 and 10), the latter induces a one-to-one map Σ_{−} from S_{+}/T I onto S_{−}/IT, viz. Σ_{−}([a]_{T I}) = [b]_{IT} iff a I* b. This proves Theorem 4, already.

By (C1) as applied to I*, Σ_{−} is an isomorphism from (S_{+}/T I, T I/S_{+}) onto (S_{−}/IT, IT/S_{−}) (recall notation from Subsection 4.2). Therefore, S_{+}/T I is T I/S_{+}-separable iff S_{−}/IT is IT/S_{−}-separable. Furthermore, S_{+}/T I is T I/S_{+}-separable iff S_{+} is T I-separable, and the obvious dual holds for IT -separability of S_{−}. This proves Theorem 3.

80Independence on the choice of b holds in many respects, but is not needed here.

81If (B, B′) = ([b]_{T I}, [b′]_{T I}) is a T I-jump such that b T a I b′ for some a ∈ A, there is d_{B} ∈ D such that b T d_{B} ≺ ∼_{IT} a. Indeed, b T * d_{B}, because b N_{T I} b′. By strong congruency of T *, d_{C} ≠ d_{B} if (C, C′) ≠ (B, B′) is another T I-jump. Therefore, there can be only countably many T I-jumps.

6.5 (F1), above, and below.

This subsection proves theorems 2 and 8; moreover, it proves, meeting the announcement below Theorem 1, equivalence to (F1) of two “practically weaker” versions.

Proof of Theorem 2. Assume (A, T) is a semiorder. As Fishburn [8, 9, Sec. 7.5] notes for deriving (F1) from T_{0}-separability, any (countable) set T_{0}-dense in A is IT - and T I-dense in A, as well. But the converse direction is hardly noticeably less obvious: If D is (countable and) IT -dense in A and D′ is (countable and) T I-dense in A, D ∪ D′ is (countable and) T_{0}-dense in A.^{82}

Proof of Theorem 8. Firstly assume Condition (i) to derive (F1). Since Condition (i) is self-dual, we confine ourselves to proving that (A, T) is IT -separable. By the assumption of singular-countability and regular-sepa-rability, there is a countable D ⊆ A which intersects with each [a]_{IT} where a ∈ S_{−} and which for every a, b ∈ A \ S_{−} such that a IT b contains some d such that a ≺ ∼_{IT} d ≺ ∼_{IT} b.^{83} Now assume just a IT b. If a ∈ S_{−}, there is an IT -equivalent d ∈ D. If not, Lemma 6 tells that there is some c ∈ a(IT) ∩ (IT)b. If c ∈ S_{−}, there is an IT -equivalent d ∈ D. If not, D contains some d such that a ≺ ∼_{IT} d ≺ ∼_{IT} c. In each case, a ≺ ∼_{IT} d ≺ ∼_{IT} b.

The implication from (F1) to Condition (iii) derives from Lemma 16. Now, we need examples refuting the converse directions: Firstly, if (A, T)

is the natural interval order of all closed bounded real intervals, (F1) is met, but not Condition (i). Indeed, in this case A = S_{−} = S_{+}, so (A, T) is not singular-countable, since the real numbers correspond one-to-one to the IT - as well as to the T I-equivalence classes. (F1) is met since this correspondence even gives rise to an isomorphism from (A/IT, IT/A) onto (R, <) as well as from (A/T I, T I/A) onto (R, >).

If (A, T) is the natural interval order of all bounded real intervals, Condition (iii) is met, but not (F1).^{84} Here, “open ends” indicate belonging to A \ S_{−} or A \ S_{+}, while “closed ends” indicate belonging to S_{−} or S_{+}. In each of these four cases, there is an isomorphism onto (R, <) or onto (R, >) much like before, therefore Condition (iii) holds. On the other hand, (A/IT, IT/A) (e.g.) is now isomorphic to the lexicographic order on R × {0, 1}, which has one jump for each real and therefore is not separable according to Lemma 15.^{85}

82The claim of Theorem 2, thus, is so obvious that it deserves being mentioned only because Fishburn seems to have overlooked it.

83In fact, d ∈ A \ S_{−}, but this will not matter.

84This is just another, somewhat more technical, presentation of the example from Subsection 3.3.

85Two rather “unnatural” (but more explicit and “parsimonious”) examples serving, in view of our Theorem 5, for the same purpose have been presented by Fishburn in [8, 9, Sec.s 7.5f.].

Here come the announced “weak” versions of (F1).

Theorem 11. The following conditions are equivalent.

(i) (F1) holds;

(ii) A is IT -separable and has only countably many T I-jumps;

(iii) A is T I-separable and has only countably many IT -jumps.

Proof. (F1) implies the other two conditions by Lemma 15. By duality, it remains to conclude (e.g.) from Condition (ii) that A is T I-separable.

Thus, assume Condition (ii). There is, then, a countable D being IT - dense in A as well as a countable D_{0} ⊆ A intersecting with every [a]_{T I} where aN_{T I} ≠ ∅. For every (d, d′) ∈ (D × D) ∩ IT, pick one c_{d,d′} from A such that d I c_{d,d′} T d′. Let D_{1} be the countable { c_{d,d′} | d, d′ ∈ D; d IT d′ }. For convenience, we aim at reductio and assume that the countable D_{0} ∪D_{1} ⊆ A is not T I-dense in A.

If so, there is some (a, b) ∈ T I such that a ≺ ∼_{T I} d ≺ ∼_{T I} b for no d ∈ D_{0} ∩ D_{1}. Therefore (think of D_{0}), aN_{T I} = ∅, and there are a_{0}, a_{1}, a_{2} ∈ A such that a T I a_{0} T I a_{1} T I a_{2} T I b. This forces existence of “witnesses” b_{0}, b_{1}, b_{2}, b_{3} such that

a T b_{0} I a_{0} T b_{1} I a_{1} T b_{2} I a_{2} T b_{3} I b.

There are d_{0}, d_{2} ∈ D such that

b_{0} ≺ ∼_{IT} d_{0} ≺ ∼_{IT} b_{1} IT b_{2} ≺ ∼_{IT} d_{2} ≺ ∼_{IT} b_{3}.

By Lemma 1, d_{0} IT d_{2}; so there is d ∈ D_{1} such that d_{0} I d T d_{2}. By (3), a T d_{0} I d T b_{3} I b; thus, a ≺ ∼_{T I} d ≺ ∼_{T I} b—contradicting the assumption.

6.6 “Weakening” Fishburn’s Condition (F2).

This subsection proves Theorem 7.

As G_{0} already served to reformulate (F2), we define a variant of it to reformulate (G):

G_{1} := { [a]_{T I} | a ∈ A; S_{+} ∩ [a]_{T I} = ∅; aT * ≠ ∅; S_{−} ∩ aT * = ∅ }.

Thus, (G) tells G_{1} to be countable.

The definition of G_{1} differs to that of G_{0} in replacing S by S_{+} at one place and by S_{−} at another. Since S ⊆ S_{−} ∩ S_{+} (Lemma 5), therefore, G_{1} ⊆ G_{0}.

By Proposition 1, however, S_{+} ∩ [a]_{T I} = ∅ iff a ∉ S_{+}. Thus, G_{1} may be rewritten in the following way.

G_{1} = { [a]_{T I} | a ∈ A \ S_{+}; aT * ≠ ∅; S_{−} ∩ aT * = ∅ }.

By Lemma 11, S_{+} ∩ [a]_{T I} ≠ ∅ iff a ∈ S_{+}. The difference set G_{0} \ G_{1}, therefore, is

G_{2} := { [a]_{T I} | a ∈ S_{+}; aT * ≠ ∅;
S ∩ [a]_{T I} = ∅;
S ∩ aT * = ∅ ≠ S_{−} ∩ aT * }.

We shall compare this to the further variants

G_{3} := { [a]_{T I} | a ∈ S_{+}; aT * ≠ ∅ };
G_{4} := { [a]_{T I} | a ∈ A; aT * ≠ ∅; S_{−} ∩ aT * ≠ ∅ }.

Proof of Theorem 7. Theorem 7, now, just tells that, if (F1), G_{0} is countable iff G_{1} is countable. Being a subset of G_{0}, G_{1} is countable if G_{0} is countable without recourse to (F1). Thus, it suffices to prove that, if (F1) and if G_{1} is countable, G_{0} is countable, as well. And this just amounts to showing that, if (F1), G_{2} is countable. Now, G_{2} ⊆ G_{3} ∪ G_{4}, so it suffices to realize that, if (F1), G_{3} and G_{4} are countable.

Concerning G_{3}: Iff [a]_{T I} ∈ G_{3}, there are b, c ∈ A such that a T * b and a I* c. In this case, c N_{IT} b. Strong congruency of T * and N_{IT} (lemmas 9, 12, 13), therefore, induces a one-to-one map [a]_{T I} ↦ (N_{IT} (aT *), aT *)^{86} from G_{3} into (even onto) the set of IT -jumps of A. Now, by (F1) and Lemma 15, the set of these jumps is countable.

Concerning G_{4}: Iff [a]_{T I} ∈ G_{4}, there are b, c ∈ A such that a T * b and c I* b. In this case, a N_{T I} c. Therefore, by strong congruency of N_{T I}, there is a one-to-one map [a]_{T I} ↦ ([a]_{T I}, aN_{T I}) from G_{3} into (even onto) the set of T I-jumps of A. Now, by (F1) and Lemma 15, the set of these jumps is countable.

7 Necessity proofs.

In this section we prove that each of the representability conditions (iii) in Theorem 5 and (iv) in Theorem 6 follows from one of the other conditions listed in the respective theorem. Indeed, by Section 5, then, in each case the representability condition is necessary for all the other conditions of the respective theorem.—Finally, we nearly prove Corollary 5, only ignoring its “component” concerning existence of O(B)RIRs.

The following just summarizes a proof technique from Fishburn’s [8]. We call φ a weak real R-homomorphism on X if it maps X into R and

R is some binary relation such that x R y (just) implies φ(x) < φ(y). Thus in contrast to a strong one, a weak real R-homomorphism may treat Requivalent elements differently. Now the following differs from the “Real Homomorphism Theorem” (Subsection 4.2) in but one word.

86N_{IT} (aT *) here denotes { c ∈ A | c N_{IT} b ∈ aT * for some b }.

Real Homomorphism Corollary. There is a weak real R-homomor-phism on X iff R weakly orders X such that X is R-separable.

Proof. If R weakly orders X such that X is R-separable, by the Real Homomorphism Theorem there is a strong real R-homomorphism on X, which a fortiori is a weak real R-homomorphism on X. If there is a weak real R-homomorphism φ on X, define x R′ y by φ(x) < φ(y) for x, y ∈ X. Then φ is a strong real R′-homomorphism, and by the Real Homomorphism Theorem there is a countable D being R′-dense in X. Moreover, R∩(X×X) ⊆ R′, and if x, y ∈ X such that x ≺ ∼_{R′} y, then x ≺ ∼_{R} y. Therefore, D is R-dense in X, as well.

The following completes necessity of Condition (iii) in Theorem 5 and yields one part of necessity of Condition (iv) in Theorem 6.

Proposition 3. If (A, T) has a RIR, it is singular- and regular-separable.

Proof. Let ρ be some RIR of (A, T). We first show that S_{−} is IT -separable, ignoring the dual implicit claim. For any a ∈ S_{−}, pick b_{a} from I*a and q_{a} from ρ(b_{a}) ∩ ρ(a) (Lemma 2). This amounts to a map φ : S_{−} → R, a ↦ q_{a}. Now if a_{0}, a_{1} ∈ S_{−} and a_{0} IT a_{1}, lower-singularity yields b_{a_{0}} T a_{1}, hence φ(a_{0}) < φ(a_{1}). To sum up, φ is a weak real IT -homomorphism on S_{−}, so by the Real Homomorphism Corollary the latter is IT -separable.

Now we show that A \ S_{−} is IT -separable and, again, omit the dual claim. By Section 5, we may assume that ρ is a BRIR. Then φ : a → inf ρ(a) maps A \ S_{−} into R. If a, b ∈ A \ S_{−} and a IT b, there is c such that a IT c IT b by Lemma 6. By Lemma 2, there are p ∈ ρ(a) and q ∈ ρ(c) such that p < q < r for all r ∈ ρ(b). Hence φ(a) ≤ p < q ≤ φ(b) and, indeed, φ(a) < φ(b). So this φ is a weak real IT -homomorphism on A \ S_{−}, and we conclude that A \ S_{−} is IT -separable using the Real Homomorphism Corollary.

The following completes necessity of Condition (iv) in Theorem 6.

Proposition 4. If (A, T) has an ORIR, it is singular-countable.

Proof. Let ρ be an ORIR. Let S′ be a subset of S_{−} which intersects exactly once with each element of S_{−}/IT. For each a ∈ S′ pick one b_{a} from I*a. Then J := { ρ(b_{a}) ∩ ρ(a) | a ∈ S′ } is (by Lemma 2 and lower-singularity) a set of pairwise disjoint open real intervals. The countable set of rational numbers intersects with every open real interval, so J, hence S′, and hence S_{−}/IT is countable. By Theorem 4 (proved in Subsection 6.4 already) S_{+}/T I, then, is countable, as well.

Now, concerning Corollary 5:

Proposition 5. An ORIR of (A, T) is singular-exact iff S_{−} = ∅ iff S_{+} = ∅.

Proof. S_{−} = ∅ iff S_{+} = ∅ iff I* = ∅—cf. Proposition 1. Now, if I* = ∅, any ORIR is trivially singular-exact. On the other hand, if ρ is an ORIR and a I* b, then ρ(a) ∩ ρ(b) is (by Lemma 2) an open (non-void) interval and, hence, contains an infinity of points. So if ρ is singular-exact, then I* = ∅.

8 Sufficiency proofs.

8.1 Content and general strategy.

This section completes proofs of theorems 5 and 6 as well as of corollaries 2 through 5 (subsections 3.3, 3.5, and 3.6). There is the “closed”, the “arbitrary”, and the “open” case. In each case, one of theorems 1, 5, and 6 together with one or two of the corollaries mentioned forms a more comprehensive equivalence proposition. More precisely, in each case a number of countability conditions like (E) and the conditions of Theorem 8 is claimed to be equivalent to several claims of existence of a RIR. Of these existence claims, the ones from subsections 3.5 and 3.6 concerning exactness and singular-exactness, are “logically” stronger than the ones from Subsection 3.3. We essentially show that, in each case, a countability condition implies the strongest claim of existence of a RIR, an exact and—in the first two cases—singular-exact one. Since Section 7 has shown that already the “weak” claims of existence of an RIR (from theorems 5 and 6; for the “closed” case it is known according to Theorem 1) imply the respective countability conditions, the reasonings of the present section close the circle required for the “comprehensive” claims, from which the single theorems and corollaries follow.

8.2 Closed representations: proof of Corollary 3.

Concerning CRIRs, we have little more to say than Fishburn [8, 9], viz. Corollary 3.

According to Subsection 8.1, we instead ought to prove (e.g.)

Corollary 10. If (F1) and (F2), there is an exact and singular-exact CBRIR of (A, T).

However, Fishburn already has done most of this work. By proving Corollary 3, we add the little difference concerning our singularity notions as well as a simple equivalence literally not comprised by Corollary 10.

Proof of Corollary 3. Assume ρ is a CBRIR of (A, T), u : A → R, a ↦ inf ρ(a), and v : A → R, a ↦ sup ρ(a). It is then obvious from the definitions and from Lemma 2 that ρ is exact iff u is a real IT -homomorphism on A and v is a real T I-homomorphism on A. Thus let us call the FPR (u, v) exact in this case. It is likewise obvious that ρ is singular-exact iff u(b) = v(a) for a I* b. Call the FPR (u, v) singular-exact in this case. It is now clear that the last two conditions of Corollary 3 are equivalent. As an exact and singular-exact CBRIR is a CRIR, it remains to show that, if there is a CRIR, there is an exact and singular-exact FPR. So assume (A, T) has a CRIR.

By Theorem 1 or the reasoning in Section 5, (A, T) has a CBRIR.^{87} By Fishburn’s [8, Thm. 2] or [9, Thm. 7.6], (A, T) has an exact FPR (u′, v′).^{88} Define u, v : A → R by v(a) := v′(a) for a ∈ A \ S_{+}, u(b) := u′(b) for b ∈ A \ S_{−}, and u(b) := v(a) := (u′(b) + v′(a))/2 for a I* b.

For a I* b, Lemma 2 yields u′(b) ≤ v′(a). If, moreover, u′(b) = v′(a), then u(b) = u′(b) and v(a) = v′(a). If u′(b) < v′(a) instead, exactness yields the following essential facts: the open interval (u′(b), v′(a)) does not intersect with u′[A] ∪ v′[A] (the image sets of u′, v′), u′(b) ∉ u′[A \ [b]_{IT}] ∪ v′[A], and v′(a) ∉ v′[A \ [a]_{T I}] ∪ u′[A]. For these reasons, the relevant inequalities remain true when the ‘prime’ strokes in u′, v′ are removed—this means, (u, v) inherits being an exact FPR from (u′, v′). By construction, moreover, (u, v) is singular-exact.

8.3 A representing linear order of “cuts”.

In principle, our following proofs just vary Fishburn’s [8, 9] proof that (F1) implies existence of an ARIR. However, we use a different approach. While Fishburn applied the Real Homomorphism Theorem to appropriate weak orders on a “doubled” version of A, we apply it to appropriate suborders of one given linear order.^{89} The following may be considered a modification of [2].

Call C ⊆ A a cut if it is closed under ≺ ∼_{T I}, i.e., if a ≺ ∼_{T I} c ∈ C implies a ∈ C.^{90} Let K be the set of these cuts. In order to have a set (instead of the proper class ⊂), we use E to denote ⊂ ∩ (K × K). Now, (K, E) is a linear order.

Proof. Irreflexivity and transitivity of E on K are clear. For trichotomy, assume C, C′ ∈ K, C ≠ C′, and C ⊄ C′. Thus, there is some c ∈ C \ C′. We show C′ ⊂ C.

87We need this for the following because of our exegetical doubts according to Fn. 18 above. Also cf. Fishburn’s [8] proof of his Thm. 5—for the previous point as well as for our withholding details.

88Indeed, by Fishburn’s theorem, the FPR may be assumed to be singular-exact in a sense restricted to Fishburn’s notion of singularity, but this does not help here.

89Fishburn [8, 9] defines one relation on a “doubled” version of A for each of three purposes. In order to apply the Real Homomorphism Theorem, he then has to prove that this relation is a weak order. Using suborders of one linear order, we bypass this step.— However, there may well arise too much clumsy difficulties from our approach which may advise to go along Fishburn’s lines instead of ours. We have not yet investigated this suggestion. If other approaches should prove to be much less clumsy, our work will at least contribute to realize this fact.

90Our “cuts” are something quite different from the “instants” used in [19] according to the remark ensuing the proof of its Prop. 2—they typically violate its (14).

8 SUFFICIENCY PROOFS. 37

If C′ = ∅, we are ready. So assume c′ ∈ C′. Now, c′ ≺ ∼_{T I} c or c T I c′. In the first case, c′ ∈ C by definition of cuts. In the second case, c ≺ ∼_{T I} c′; so c ∈ C′ by the definition of cuts—but this contradicts the former assumption of c ∉ C′. We conclude c′ ∈ C, thus C′ ⊆ C and, by the assumption of C ≠ C′, C′ ⊂ C.^{91}

By the way, A → I(K, E), a ↦ { C ∈ K | T a ⊂ C ⊆ ≺ ∼_{T I}a } is an IR of (A, T) in (K, E).^{92} This amounts to another proof that (A, T), if only assumed to consist of an irreflexive T ⊆ A × A and to satisfy (W), has an IR in some linear order.^{93}

8.4 Two special kinds of cuts and their interrelations.

We shall meet cuts of two special kinds:

Lemma 19. For a ∈ A, T a and ≺ ∼_{T I}a are cuts.

Proof. T a is a cut by (4), and ≺ ∼_{T I}a is a cut by negative transitivity of the weakly ordering T I.

Furthermore, we shall need some knowledge on their interrelations and on how the latter interrelate with properties of the “source” objects in A:

Lemma 20. If T a ⊂ ≺ ∼_{T I}b and b ∉ S_{+}, then a IT IT I b.

Proof. Assume T a ⊂ ≺ ∼_{T I}b and b ∉ S_{+}. Then, by (4), not b T a. By b ∉ S_{+}, neither b nor anything is an IT -maximum of Ib. Hence, if a T b, then there is some c such that a I a T b IT c I b. If a I b, neither a nor anything is in IT -Max Ib, so there are c, c′ ∈ Ib such that a IT c IT c′ I b.

Lemma 21. If a (I ∪ IT I ∪ T) b, then T a ⊂ ≺ ∼_{T I}b.

Proof. Assume a I b; so b ∉ T a. Additionally assume c T a for some c. Then c T I b. To sum up, T a ⊂ ≺ ∼_{T I}b.—Now assume a IT c I b for some c. Then, using (3) and the previous, T a ⊆ T c ⊂ ≺ ∼_{T I}b. The case of IT follows by reflexivity of I.—Finally, assume a T b and c T a for some c as firstly. Then c T T b, so, by transitivity (Lemma 4), c T b I b and c T I b—desired as in the first case.

Lemma 22. If a T * b, then ≺ ∼_{T I}a = T b.

91Obviously, the proof works for any binary asymmetric relation on A instead of T I.

92This is a modification of [2]. The proof uses Lemma 19 below.

93The presumably earliest proof by B. Russell and N. Wiener [21] uses the axiom of choice. Furthermore, it is easy to see that Fishburn’s definition [9, Sec. 2.1] of interval orders ((W) replaced by if a T b and a′ T b′, then a T b′ or a′ T b) is equivalent to that of what Wiener calls a ‘relation of complete sequence’. (Thomason [19, 20] adds two relations defined from the first one and calls ‘event structures’ what results; in principle, however, this is the same.) Fishburn [9, Thm. 2.6] even proves that any interval order (as defined by irreflexivity of T and by (W) or a version of the latter) has a CBIR. Both proofs, and neither ours, do not need the axiom of choice.

Proof. Assume a T * b. By (4), then, ≺ ∼_{T I}a ⊆ T b. For equality assume, additionally, c T b. Then a T * b entails not a T IT b and, therefore, not a T I c, which means c ≺ ∼_{T I} a (T I weakly ordering A).

Lemma 23. If ≺ ∼_{T I}a ⊂ T b, then a T IT b.

Proof. Assume ≺ ∼_{T I}a ⊂ T b. Hence, a T b. Now, ≺ ∼_{T I}a being proper subset of T b by Lemma 22 rejects the stronger proposition a T * b. Therefore, a T IT b.

8.5 Existence of arbitrary real representations.

To complete proofs of our claims on ARIRs—viz. Theorem 5 and Corollary 4, we prove the following

Proposition 6. If S_{−} and { a ∈ A \ S_{−} | N_{IT} a = ∅ } are IT -separable and, furthermore, A \ S_{+} is T I-separable, (A, T) has an exact and singular-exact ABRIR.

Note that here is a condition logically (or set-theoretically) weaker than our original condition of singular- and regular-separability of (A, T) (even weaker than the respective condition yielded by Theorem 3). The new condition is entailed by the original one and, therefore, necessary for real representability, as well. Indeed, by Lemma 16 a subset of A \ S_{−} is IT -separable if A \ S_{−} is.

Idea of proof. Fishburn would start a proof of Proposition 6 by “merging” some of the equivalence classes associated with the weak order on a doubled version of A which he has defined in his proof of his part of our Theorem 1. We are replacing such “merging” by assigning same cuts in some cases of “overlapping” or of precedence with respect to IT or to T I. “Translated” into Fishburn’s method, we are (in general) merging much more equivalence classes than Fishburn ever did (in [8, 9]).^{94}

Proof of Proposition 6. First part of construction. For brevity, let A_{1} := S_{−}, A_{2} := { a ∈ A \ S_{−} | N_{IT} a = ∅ } A_{3} := A \ S_{+}; furthermore K_{1} := { T a | a ∈ A_{1} }, K_{2} := { T a | a ∈ A_{2} }, and K_{3} := { ≺ ∼_{T I}a | a ∈ A_{3} }. For a ∈ A, let

γ_{−}(a) := \{ \begin{matrix}T a & if a ∈ S_{−} ∪ A_{2}; \\ T b & if a ∉ S_{−} and b N_{IT} a. \end{matrix}

γ_{−}(a) is well-defined in the second case by (3) and lemmas 9f. (strong congruency of N_{IT}). By Lemma 19, γ_{−}(a) is an element of K in both cases. Thus we have defined a map γ_{−} from A into K. Since—by Lemma 14— b N_{IT} a implies b ∈ S_{−}, the image set γ_{−}[A] is K_{1} ∪ K_{2}.

94Fishburn did not merge more than two equivalence classes, while we (in Fishburn’s terms) are merging three of them in some cases. E.g., we are merging respective equivalence classes of a^{+}, b^{−}, and c^{−} (one of Fishburn’s notations) whenever a ∈ A \ S_{+}, c ∈ A \ S_{−}, and a T * b N_{IT} c.

Next let, for a ∈ A,

γ_{+}(a) := \{ \begin{matrix}T b & if a I* b; \\ ≺ ∼_{T I}a & if a ∉ S_{+}. \end{matrix}

By (3) and strong congruency of I* (Lemma 10), γ_{+}(a) is well-defined in the first case. a I* b implies a ∈ S_{+} (Proposition 1), so the two cases exclude each other and exhaust all possibilities, indeed. As ≺ ∼_{T I}a is a cut (Lemma 19) and by the above reasoning concerning γ_{−}, γ_{+}(a) is in K again in both cases, so we have a map γ_{+} : A → K. Since a I* b also implies b ∈ S_{−}, its image set γ_{+}[A] is K_{1} ∪K_{3}. Thus, γ_{−}[A]∪γ_{+}[A] = K_{1} ∪K_{2} ∪K_{3}. Call the latter set K_{0}. According to the above thoughts about γ_{−} and γ_{+}, it is a subset of K. Recall that, now, (K_{0}, E) is a linear order and, therefore, a weak order.

Separability. Assume the hypothesis of Proposition 6; in particular, there are countable D_{1} being IT -dense in S_{−}, D_{2} IT -dense in A_{2}, and D_{3} T Idense in A \ S_{+} (so D_{k} ⊆ A_{k} for k = 1, 2, 3). In order to apply the Real Homomorphism Theorem, we show that K_{0} is E-separable. Let D′_{1} := { T d | d ∈ D_{1} }, D′_{2} := { T d | d ∈ D_{2} }, and D′_{3} := { ≺ ∼_{T I}d | d ∈ D_{3} }. We show that D′ := D′_{1} ∪ D′_{2} ∪ D′_{3}—being countable—moreover is E-dense in K_{0}.

Clearly, D′_{i} ⊆ K_{i} for i = 1, 2, 3; so D′ ⊆ K_{0}. For density, assume C, C′ ∈ K_{0} and C ⊂ C′. We distinguish 9 cases numbered i.j, i, j = 1, 2, 3, where Case i.j means assuming C ∈ K_{i} and C′ ∈ K_{j}. In Case i.j we may pick a from A_{i} and b from A_{j} such that

C [C′] = \{ \begin{matrix}T a [T b] & if i [j] < 3; \\ ≺ ∼_{T I}a [≺ ∼_{T I}b] & if i [j] = 3. \end{matrix}

We shall write [c_{1}, c_{2}]_{k} for { c_{0} ∈ D_{k} | c_{1} ≺ ∼_{R_{k}} c_{0} ≺ ∼_{R_{k}} c_{2} } where R_{1} := R_{2} := IT and R_{3} := T I. (Hence, 1 indicates (S_{−}, IT), 2 indicates (A_{2}, IT), and 3 indicates (S_{+}, T I) being “reference order” for taking “intervals” [notion generalized from linear orders].—c_{1} or c_{2} may be no member of [c_{1}, c_{2}]_{k}.) Furthermore, we shall write K* for { C_{0} ∈ K_{0} | C ⊆ C_{0} ⊆ C′ }∩D′ (recall ⊆ = ≺ ∼_{E} on K). Thus, we are trying to show K*≠ ∅.

Keep in mind that i, j < 3 implies T a ⊂ T b, so a IT b follows by (3). Case 1.1. Here, by hypothesis and the previous remark, we may pick d

from [a, b]_{1}. Then T d ∈K* by (3).

Case 1.2. Again, a IT b. By j = 2, N_{IT} b = ∅, so we may pick c from a(IT IT) ∩ (IT)b. If there is some c′ ∈ N_{IT} c, then a IT c′ IT b, and there is (by Lemma 14) some d ∈ [a, c′]_{1} such that T d ∈K* by applying (3) and transitivity of IT.—Otherwise, N_{IT} c = ∅, so there is some d ∈ [a, c]_{1} ∪[c, b]_{2}, and T d ∈K* essentially as before.

Case 2.1. Here, a IT IT c IT b for some c by a ∉ S_{−} and Lemma 6. Continue almost as in Case 1.2 (using [c′, b]_{1}, [a, c]_{2}, and [c, b]_{1} instead).

Case 2.2. By hypothesis, pick d from [a, b]_{2} and proceed analogously to Case 1.1.

For the following cases, recall that ≺ ∼_{T I} is involved when i = 3 or j = 3. Case 3.3. Here, ≺ ∼_{T I}a ⊂ ≺ ∼_{T I}b and, therefore (Lemma 19 and b ∉ ≺ ∼_{T I}a),

a T I b. Now ≺ ∼_{T I}d ∈K* for some d ∈ [a, b]_{3}.

Case 1.3. By Lemma 20, a(IT IT) ∩ Ib ≠ ∅. If there even is some c ∈ a(IT IT) ∩ Ib ∩ S_{−}, there is some d ∈ [a, c]_{1} such that T d ∈K* by (3) and Lemma 21. Otherwise, there might be c, c′ such that c′ N_{IT} c I b. In this subcase, c′ ∈ a(IT)∩N_{IT} c∩S_{−} as in Case 1.2, so pick d from [a, c′]_{1} and continue as above (using the IT I case of Lemma 21). If the two previous subcases apply to no c, there only may be c in a(IT) ∩ Ib ∩ A_{2}. By b ∉ S_{+}, then, there is some c′ ∈ c(IT) ∩ Ib, which (being element of a(IT IT) ∩ Ib) must be in A_{2}, as well. Now, there is some d ∈ [c, c′]_{2} such that T d ∈K* by (3) and Lemma 21.

Case 2.3. If there are c, c′ ∈ S_{−} such that a IT c IT c′ IT I b, one may pick d from [c, c′]_{1} in order to get, by (3) and Lemma 21, T d ∈K*. Otherwise, by a ∉ S_{−} and lemmas 6 and 20, there are c_{1}, c_{2}, c_{3} such that a IT IT c_{1} IT c_{2} IT c_{3} IT I b. In this subcase, two out of c_{1}, c_{2}, c_{3} cannot both be in S_{−}. Among these two, only one c can meet N_{IT} c ≠ ∅ (Lemma 14; first subcase of 2.3 being excluded here). Concerning the other—c′, say—, c′ ∈ A_{2}, and for some d ∈ [a, c′]_{2}, T d ∈K* as earlier.

Cases 3.1 and 3.2. By Lemma 23, a(T I) ∩ T b ≠ ∅. If there even is some c ∈ (a(T I)∩T b)\S_{+}, there is some d ∈ [a, c]_{3} yielding ≺ ∼_{T I}d ∈K* by lemmas 1, 3, and 21 (case of T), and by (W). Otherwise, a(T I) ∩ T b ⊆ S_{+}. If, now, there are c, c′ ∈ S_{+} such that a T I c T I c′ T b, then there is d ∈ [c, c′]_{3}, and ≺ ∼_{T I}d ∈K* similarly as before. Otherwise again, a(T I) ∩ T b ⊆ a(T *I). Then, by Lemma 22, ≺ ∼_{T I}a = T c for some c ∈ aT *, so one of the above cases with i, j < 3 applies.

Second part of construction. Now that K_{0} is E-separable, we may choose a real E-homomorphism φ on K_{0}. Thereby, we may define, for a ∈ A,

ρ_{−}(a) := \{ \begin{matrix}≥φ(γ_{−}(a)) & if a ∈ S_{−}; \\ >φ(γ_{−}(a)) & if a ∉ S_{−}; \end{matrix}
ρ_{+}(a) := \{ \begin{matrix}≤φ(γ_{+}(a)) & if a ∈ S_{+}; \\ <φ(γ_{+}(a)) & if a ∉ S_{+}; \end{matrix}
ρ(a) := ρ_{−}(a) ∩ ρ_{+}(a).

(Now, e.g., ρ(a) = [φ(γ_{−}(a)), φ(γ_{+}(a))] if a ∈ S_{−} ∩ S_{+}.)

It remains to show that this ρ is an exact and singular-exact ABRIR. A lemma. Proposition 1 yields

If a I* b, then γ_{+}(a) = T b = γ_{−}(b). (6)

Another lemma. Suppose a ∈ I*b \ S. Then by Lemma 5, not a I* a, i.e., not a ∈ IT -Max Ia. Hence, by Lemma 8, not a ∼_{IT} b. On the other hand, b ∈ IT -Max Ia, hence a ≺ ∼_{IT} b. To conclude:

If a ∈ I*b \ S, then a IT b. (7)

Image set consisting of bounded real intervals. For ρ(a) ∈ I(R, <) (a ∈ A), it clearly suffices to show that ρ(a) ≠ ∅. It will then be clear that ρ(a) has φ(γ_{−}(a)) as a lower and φ(γ_{+}(a)) as an upper bound.—First, consider a ∈ S. By Lemma 5, then, S ⊆ S_{−} ∪ S_{+}, so, by (6), γ_{−}(a) = T a = γ_{+}(a) and ρ(a) = {φ(T a)} ≠ ∅.—Now suppose a ∉ S. We are going to show γ_{−}(a) ⊂ γ_{+}(a) in order to obtain inf ρ(a) = φ(γ_{−}(a)) < φ(γ_{+}(a)) = sup ρ(a) and, thus, (inf ρ(a) + sup ρ(a))/2 ∈ ρ(a) ≠ ∅. There are four cases according to which two of S_{−}, A \ S_{−}, A \ S_{+}, S_{+} a belongs. Recall that, by trichotomy of E, C ⊂ C′ iff C′ \ C ≠ ∅ whenever C, C′ ∈ K.

a ∈ S_{+} ∪ S_{−}: Here, there is some b ∈ aI*, so there is some c ∈ aI ∩ T b by (7). The latter entails c ∈ T b \ T a, hence γ_{−}(a) = T a ⊂ T b = γ_{+}(a).

a ∈ S_{+} \ S_{−}: If N_{IT} a = ∅, then γ_{−}(a) = T a ⊂ T b = γ_{+}(a) nearly as before.^{95} Otherwise, there are b, c such that γ_{−}(a) = T b, γ_{+}(a) = T c, and b N_{IT} a I* c. (7) yields b IT a IT c and, by transitivity of the weakly ordering IT, b IT c. Now, γ_{−}(a) = T b ⊂ T c = γ_{+}(a) nearly as in the previous case.

a ∈ S_{−} \ S_{+}: Here, γ_{−}(a) = T a ⊂ ≺ ∼_{T I}a = γ_{+}(a) by a ∈ ≺ ∼_{T I}a \ T a. a ∉ S_{−} ∪ S_{+}: If N_{IT} a = ∅, the previous proof applies, again. Otherwise,

there is some b ∈ N_{IT} a, so a ∈ ≺ ∼_{T I}a \ T b by (5), and, finally, γ_{−}(a) = T b ⊂ ≺ ∼_{T I}a = γ_{+}(a).

ρ interval representation. We have to show that a T b iff

ρ_{+}(a) ∩ ρ_{−}(b) = ∅. (8)

There are four cases according to which two of S_{−}, A \ S_{−} a belongs and to which two of S_{+}, A \ S_{+} b belongs.

a ∈ S_{+}, b ∈ S_{−}: Here, there is some c ∈ I*a such that ρ_{+}(a) = ≤φ(T c). Furthermore ρ_{−}(b) = ≥φ(T b). We need a number of equivalences dependant on these conditions. The first is a T b iff c IT b. a T b implies c I a T b— one direction. c ∈ I*a means c ∈ IT -Max Ia, so c IT b entails not a I b. Similarly, c I* a implies a ≺ ∼_{IT} b, so c IT b entails a IT b (Lemma 1) and not b T a (cf. (5))—the equivalence is established.—Detailed proofs of the further equivalences may be left to the reader: (a T b iff) c IT b iff (cf. (3)) T c ⊂ T b iff sup ρ_{+}(a) < inf ρ_{−}(b) iff (8).

a ∈ S_{+}, b ∉ S_{−}: Consider ρ_{+}(a) and c as before. If N_{IT} b = ∅, then ρ_{−}(b) = >φ(T b). Now, a T b entails (8) as before, again. For the other direction, (8) at first only yields sup ρ_{+}(a) ≤ inf ρ_{−}(b), T c ⊆ T b, and c ≺ ∼_{IT} b. However, c ∈ S_{−} while b ∉ S_{−}. Thus, as S_{−} is IT -congruent, not c ∼_{IT} b, so c IT b obtains, and a T b is derived as in the previous case.— If, on the other hand, there is d ∈ N_{IT} b, we get ρ_{−}(b) = >φ(T d). Some appropriate modification of the above yields a T b iff c ≺ ∼_{IT} d iff T c ⊆ T d iff sup ρ_{+}(a) ≤ inf ρ_{−}(b) iff (8).

95Distinction of cases according to the cases of the definitions of γ_{−}, γ_{+} here and below might be shorter; however, we suppose that it rather would be less perspicuous.

a ∉ S_{+}, b ∈ S_{−}: Here, ρ_{+}(a) = <φ(≺ ∼_{T I}a) and ρ_{−}(b) = ≥φ(T b). Now, a T b iff ≺ ∼_{T I}a ⊆ T b iff sup ρ_{+}(a) ≤ inf ρ_{−}(b) iff (8).

a ∉ S_{+}, b ∉ S_{−}: Here, ρ_{+}(a) = <φ(≺ ∼_{T I}a) as previously. If N_{IT} b = ∅, then ρ_{−}(b) as previously, and the previous reasoning applies, again. Otherwise, pick d from N_{IT} b. Then, ρ_{−}(b) = >φ(T d) as in the second case above, and a T b follows from ≺ ∼_{T I}a ⊆ T d by (W). a T b, conversely, does not allow d T a, since the latter would contradict d N_{IT} b by (1). Neither, it allows d I a, since this would contradict d N_{IT} b by a ∉ S_{+} and (W) (consider d IT d′ IT d′′, d′, d′′ ∈ Ia, then d IT d′ IT b). To conclude, a T b yields a T d; so a T b iff ≺ ∼_{T I}a ⊆ T d iff sup ρ_{+}(a) ≤ inf ρ_{−}(b) iff (8).

Exactness. By IT -congruency of S_{−} and of A \ S_{−} (Lemma 11; complements are congruent because the whole set is), strong IT -congruency of N_{IT}, and (3), ρ_{−}(a) = ρ_{−}(b) if a ∼_{IT} b. By T I-congruency of S_{+} and of A \ S_{+}, strong T I-congruency of I*, and (4), ρ_{+}(a) = ρ_{+}(b) if a ∼_{T I} b.

Singular-exactness. By (6), ρ(a) ∩ ρ(b) = {φ(T b)} if a I* b.

8.6 Existence of open real representations.

To complete proofs of our claims on ORIRs—viz. Theorem 6 and corollaries 2 and 5, we prove the following

Proposition 7. If (A, T) is singular-countable and regular-separable, it has a WFPR (u, v) such that u is a real IT -homomorphism and v is a real T Ihomomorphism.

Proof. Assume (A, T) is singular-countable and regular-separable. This is a special case of the hypotheses in Proposition 6, so there are φ, ρ_{−}, ρ_{+}, ρ as in our proof of Proposition 6.

By R^{+} we denote the set of real numbers r > 0. Let exp : R → R^{+}, r ↦ e^{r}.^{96} Then exp ∘φ is a real E-homomorphism like φ and could have been used for defining ρ, as well. Without loss of generality, therefore, we may assume that each φ(C) > 0 (C ∈ K_{0}); so each ρ(a) ∈ I(R^{+}, <) (a ∈ A). Let Q_{0} := { inf ρ(a) | a ∈ S_{−} } ⊆ R^{+}. Since ρ is exact, Q_{0} is countable by singular-countability. Thus, we may choose some sequence (q_{n})_{n∈N} such that n ↦ q_{n} maps N one-to-one onto Q_{0}. (We are somewhat replacing each point q_{n} of Q_{0} by an interval of length 2^{−n}.)

Now let ψ_{−}, ψ_{+} : R^{+} → R^{+} such that ψ_{−}(r) := r + ∑_{n∈N,q_{n}<r} 2^{−n} and ψ_{+}(r) := r + ∑_{n∈N,q_{n}≤r} 2^{−n}. (The sums are subseries of a convergent geometric series and have a value independent on the order by which partial sums are taken.)^{97} 9 PROOFS CONCERNING SEMIORDERS. 43

96e is Euler’s number 2,71828…

97More precisely, let p_{n}^{(r)} := 2^{−n} if q_{n} < r and p_{n}^{(r)} := 0 otherwise; and let q_{n}^{(r)} := 2^{−n} if q_{n} ≤ r and q_{n}^{(r)} := 0 otherwise. Then ψ_{−}(r) := r +∑_{n=0}^{∞} p_{n}^{(r)} and ψ_{+}(r) := r +∑_{n=0}^{∞} q_{n}^{(r)}.

Next let, for a ∈ A,

u(a) := \{ \begin{matrix}ψ_{−}(inf ρ(a)) & if a ∈ S_{−}; \\ ψ_{+}(inf ρ(a)) & if a ∈ A \ S_{−}; \end{matrix}
v(a) := \{ \begin{matrix}ψ_{+}(sup ρ(a)) & if a ∈ S_{+}; \\ ψ_{−}(sup ρ(a)) & if a ∈ A \ S_{+}; \end{matrix}

This defines u, v : A → R^{+}. (u, v) straightforwardly proves to be a WFPR of (A, T) having the additional ‘homorphism’ property required by the proposition.

However, one might overlook simple proofs, so we try to present one as follows. We consider a, b ∈ A and show that a T b iff

v(a) ≤ u(b). (9)

But we know that a T b is equivalent to (8), hence it suffices to show that (9) is equivalent to (8).

Assume (8). Then sup ρ(a) ≤ inf ρ(b). If sup ρ(a) < inf ρ(b), then (9) follows from ψ_{−}(r) ≤ ψ_{+}(r) < ψ_{−}(r′) ≤ ψ_{+}(r′) for 0 < r < r′. (10)

If sup ρ(a) = inf ρ(b) =: r_{0}, then one of ρ_{+}(a), ρ_{−}(b) is open; hence a ∈ A \ S_{+} or b ∈ A \ S_{−} by definitions of ρ_{−}, ρ_{+}, furthermore v(a) = ψ_{−}(r_{0}) or u(b) = ψ_{+}(r_{0}), and this yields (9).

Now assume (8) does not hold. In this case, inf ρ(b) ≤ sup ρ(a). If inf ρ(b) < sup ρ(a), then (10) yields u(b) < v(a). If inf ρ(b) = sup ρ(a) = r_{0}, then ρ(a)∩ρ(b) = {r_{0}}.^{98} Lemma 2 leads from this to a I* b; hence Proposition 1 yields r_{0} ∈ Q_{0} and u(b) = ψ_{−}(r_{0}) < ψ_{+}(r_{0}) = v(a). Thus, not (8) implies not (9), and we know that (u, v) is a WFPR of (A, T).

That u is a weak^{99} real IT -homomorphism and v a weak real T I-homomorphism follows from Lemma 2 and ρ being an IR. That they are even strong ones follows from exactness of ρ and from respective congruency of S_{−}, A \ S_{−}, A_{+}, A \ S_{+}.

9 Proofs concerning semiorders.

This section deals with Subsection 3.7.

Corollaries 6 through 8, however, are straightforward from the definitions and Lemma 2—recognizing that (A, T) is a semiorder iff a IT b T I a for no a, b ∈ A.

Proof of Theorem 9. Assume (A, T) is the natural interval order of all real intervals having length 1 and containing their lower bounds and, for reductio, ρ is a strictly semiorderlike RIR of (A, T). Clearly, then, (A, T) is a semiorder. If r ∈ R, let a_{r} := [r, r + 1) and b_{r} := [r, r + 1]. Some applications of Lemma 2 are ensuing: For r ∈ R, there is some q_{r} ∈ ρ(b_{r−1}) ∩ ρ(b_{r}).

98Assumption of not (8) is still at work.

99Cf. Section 7.

Moreover, a_{r} T b_{r+1} I b_{r}, so (by strict semiorderlikeness) ρ(a_{r}) <-exceeds ρ(b_{r}) below, i.e., p_{r} < q for some p_{r} ∈ ρ(a_{r}) and all q ∈ ρ(b_{r}). In particular, p_{r} < q_{r}. If r < r′, then b_{r−1} T a_{r′} and, hence, q_{r} < p_{r′}. Therefore, the uncountably many open real intervals in { (p_{r}, q_{r}) | r ∈ R } are pairwise disjoint, and each intersects with the countable set of rational numbers—a contradiction.

10 Acknowledgements

Dr. Peter Schuster’s hint on [3]^{100} at least removed terrible errors from the present paper—the latter would even have been impossible without it. Moral encouragement was given by the same, by Professor Douglas Bridges (having given valuable hints as well), and by Professor Godehard Link, who supervises the doctoral thesis the work presented is part of. Notwithstanding minor criticisms on some of the cited works, they all were very inspiring and a great pleasure to read.

Without some manœuvre of Dr. Volker Halbach’s, the present author probably never would have done original work on interval orders. V. Halbach, P. Schuster, and D. Bridges moreover helped by suggestions concerning publication.

Dr. Karl-Georg Niebergall pointed out that some original definition plainly did not work as intended. Discovery of a wrong original “proof” resulted. Likewise, the author is grateful to the rest of the audience of his presentation of the paper to the colloquy directed by G. Link and K.- G. Niebergall, in particular for suggestions by P. Schuster and Tobias Hürter and for encouragement by Dr. Martin Rechenauer.

Financially the work, which grew out of the work on the doctoral thesis at Munich University mentioned above, was enabled by an exhibition according to the Bavarian Law for the Advancement of Young Scientists and Artists dating from December 18, 1984.

References

[1] Bell, J. L., and A. B. Slomson, Models and Ultraproducts. An Introduction, North-Holland, Amsterdam, 1969.

[2] Bogart, K. P., ‘An obvious proof of Fishburn’s interval order theorem’, Discrete Mathematics 118 (1993), 239–242.

[3] Bridges, D. S., and G. B. Mehta, Representations of Preference Orderings (LNEMS 422), Springer, Berlin, 1995.

100In particular, this book solved tremendous troubles with order-separability/-density conditions that float in the literature.

[4] Cantor, G., ‘Beiträge zur Begründung der transfiniten Mengenlehre’, Mathematische Annalen 46 (1895), 481–512.

[5] Cantor, G., Contributions to the Founding of the Theory of Transfinite Numbers, Dover, New York, 1952.

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

[7] Fishburn, P. C., Utility Theory for Decision Making, Wiley, New York, 1970.

[8] Fishburn, P. C., ‘Interval representations for interval orders and semiorders’, Journal of Mathematical Psychology 10 (1973), 91–105.

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

[10] Herden, G., and G. Mehta, ‘The continuous analogue and generalization of the classical Birkhoff–Milgram theorem’, Mathematical Social Sciences 28 (1994), 59–66.

[11] Krantz, D. H., R. D. Luce, P. Suppes, and A. Tversky, Foundations of Measurement, Vol. I, Academic Press, New York, 1971.

[12] Levy, A., Basic Set Theory, Springer, Berlin, 1979.

[13] Luce, R. D., ‘Semiorders and a theory of utility discrimination’, Econometrica 24 (1956), 178–191.

[14] Niederée, R., Maß und Zahl. Logisch-modelltheoretische Untersuchungen zur Theorie der fundamentalen Messung, Lang, Frankfurt/M., 1992.

[15] Oloriz, E., J. C. Candeal, and E. Induráin, ‘Representability of interval orders’, Journal of Economic Theory 78 (1998), 219–227.

[16] Pirlot, M., and Ph. Vinke, Semiorders. Properties, Representations, Applications, Kluwer, Dordrecht, 1997.

[17] Roberts, F. S., Measurement Theory with Applications to Decisionmaking, Utility and the Social Sciences, Addison-Wesley, Reading, Mass., 1979.

[18] Russell, B., ‘On order in time’, in Logic and Knowledge, ed. R. C. Marsh, Allen and Unwin, London, 1956, 124–137. (First published in Proceedings of the Cambridge Philosophical Society 32 [1936], 216–228.)

[19] Thomason, S. K., ‘On constructing instants from events’, Journal of Philosophical Logic 13 (1984), 85–96.

[20] Thomason, S. K., ‘Free construction of time from events’, Journal of Philosophical Logic 18 (1989), 43–67.

[21] Wiener, N., ‘A contribution to the theory of relative position’, Proceedings of the Cambridge Philosophical Society 17 (1914), 441–449.