2.7 Intervals in posets

Definition of intervals

An interval in a poset is a subset of elements that fall between two specified points according to the partial order. Intervals give you a way to "zoom in" on a portion of a poset and study its local structure, much like intervals on the real number line let you focus on a specific range.

Open vs closed intervals

These work similarly to intervals on the real line, but generalized to any poset $(P, \leq)$ with elements $a \leq b$:

• Closed interval: includes both endpoints. $[a,b] = \{x \in P \mid a \leq x \leq b\}$
• Open interval: excludes both endpoints. $(a,b) = \{x \in P \mid a < x < b\}$
• Half-open intervals: include one endpoint but not the other. Written $(a,b]$ or $[a,b)$ with the expected meanings.

One thing to watch: in a poset, $a < x < b$ means $a \leq x$, $x \leq b$, $x \neq a$, and $x \neq b$. Because posets aren't necessarily total orders, an open interval $(a,b)$ can behave quite differently from what you'd expect on the real line. It might even be empty when $a$ and $b$ are comparable but have no elements strictly between them.

Bounded vs unbounded intervals

• Bounded intervals have both a lower and upper bound within the poset. All the interval types above ($[a,b]$, $(a,b)$, etc.) are bounded.
• Unbounded intervals extend without limit in at least one direction. If the poset has no maximum or minimum element, you get intervals like $(\leftarrow, a] = \{x \in P \mid x \leq a\}$ or $[a, \rightarrow) = \{x \in P \mid a \leq x\}$.

Note: the notation $(-\infty, a)$ and $(a, \infty)$ is borrowed from the real line. In a general poset, $\infty$ and $-\infty$ aren't actual elements; they just signal that the interval has no bound in that direction.

Types of intervals in posets

Because posets generalize the real line to structures where not every pair of elements is comparable, several specialized interval types become useful.

Principal intervals

A principal interval (also called a principal ideal or principal filter) is defined by a single element $a \in P$:

• Principal downset (lower set): ${\downarrow}a = \{x \in P \mid x \leq a\}$. This collects everything at or below $a$.
• Principal upset (upper set): ${\uparrow}a = \{x \in P \mid a \leq x\}$. This collects everything at or above $a$.

These are useful for studying the local neighborhood of a specific element. For example, in a poset of divisors of 12 ordered by divisibility, ${\downarrow}6 = \{1, 2, 3, 6\}$.

Convex intervals

A subset $S \subseteq P$ is convex if whenever $x, y \in S$ and $x \leq z \leq y$, then $z \in S$ as well. In other words, a convex set contains everything "between" any two of its elements.

Every closed interval $[a,b]$ is automatically convex. But convexity is a more general property: a convex subset doesn't have to be defined by just two endpoints. Convex subsets are important because they preserve the order structure of the parent poset and show up naturally when studying sublattices and order-preserving maps.

Proper intervals

A proper interval is one that is neither empty nor equal to the entire poset $P$. This just filters out the trivial cases so you can focus on substructures that actually reveal something about the poset's internal organization.

Properties of intervals

Lattice structure of intervals

The collection of all closed intervals in a poset, ordered by set inclusion, often forms a lattice:

• Meet (greatest lower bound): the intersection of two intervals
• Join (least upper bound): the smallest interval containing both

This lattice of intervals gives you a higher-level view of how the poset's substructures relate to each other.

Interval topology

You can build a topology on a poset by using intervals (or complements of closed intervals) as a basis for open sets. This interval topology connects order-theoretic ideas with topological ones. It tends to be coarser (fewer open sets) than other natural topologies you might put on a poset, but it's useful for studying continuity of order-preserving functions.

Interval orders

An interval order is a special kind of partial order that arises when you represent each element as an interval on the real line, then say $x < y$ exactly when $x$'s interval lies entirely to the left of $y$'s interval.

Definition and characteristics

Formally, a partial order $(X, <)$ is an interval order if you can assign to each $x \in X$ a real interval $f(x) = [l_x, r_x]$ such that:

$x < y \iff r_x < l_y$

That is, $x$ precedes $y$ exactly when $x$'s interval finishes before $y$'s interval starts.

A key characterization: a poset is an interval order if and only if it contains no induced subposet isomorphic to $\mathbf{2} + \mathbf{2}$ (two disjoint two-element chains). In concrete terms, you can never find four elements $a < b$ and $c < d$ where $a, b$ are incomparable with $c, d$. This is sometimes called the Fishburn condition.

Representation theorem

Fishburn's theorem states that a finite poset is an interval order if and only if it avoids the $\mathbf{2} + \mathbf{2}$ configuration. Every such poset can be represented by a family of real intervals as described above. The representation isn't unique (you can stretch or shift the intervals), but this flexibility is actually useful since it allows you to choose representations that suit your application.

Applications of intervals

Scheduling problems

Intervals naturally model time slots for tasks. If each job occupies a time interval, then two jobs conflict exactly when their intervals overlap. This leads to interval graphs, where vertices are jobs and edges connect conflicting pairs. Algorithms on interval graphs (like greedy interval coloring) solve resource allocation problems efficiently, and tools like PERT/CPM use interval-based reasoning for project management.

Temporal reasoning

In AI and knowledge representation, intervals model time periods for events. Allen's interval algebra (covered below) provides a formal system for reasoning about how events relate in time. This supports applications in natural language processing (understanding sentences like "the meeting happened during lunch") and automated planning systems.

Interval algebra

Allen's interval algebra

Allen's interval algebra defines 13 basic relations that can hold between two time intervals. These are: before, after, meets, met-by, overlaps, overlapped-by, starts, started-by, during, contains, finishes, finished-by, and equals.

Any two intervals on a timeline stand in exactly one of these 13 relations. The power of the algebra is that you can compose relations: if you know how interval A relates to B, and how B relates to C, you can infer possible relations between A and C using a composition table. This forms the basis for constraint propagation in temporal reasoning systems.

Operations on intervals

Standard set-theoretic operations apply to intervals, though the results aren't always intervals themselves:

• Union: combines overlapping or adjacent intervals (e.g., $[1,3] \cup [2,5] = [1,5]$)
• Intersection: finds the common part (e.g., $[1,3] \cap [2,5] = [2,3]$)
• Complement: the set of elements not in the interval
• Scaling and translation: modify interval size and position (primarily relevant for real-valued intervals)

Interval-valued functions

These are functions whose outputs are intervals rather than single values. They're useful whenever you need to represent uncertainty or imprecision.

Interval-valued probability

Instead of assigning a single probability $P(A) = 0.3$ to an event, you assign a range like $P(A) \in [0.2, 0.4]$. This is valuable when you don't have enough data to pin down an exact probability. Interval-valued probabilities show up in risk analysis and decision-making under ambiguity, generalizing classical probability to handle imprecise information.

Interval analysis

Interval analysis (pioneered by Ramon Moore in the 1960s) replaces single numbers with intervals in computations to track how errors and uncertainties propagate. For example, if $x \in [1.9, 2.1]$ and $y \in [2.9, 3.1]$, then $x + y \in [4.8, 5.2]$. This provides guaranteed bounds on results, which matters in scientific computing, global optimization, and engineering where rounding errors can accumulate.

Computational aspects

Algorithms for interval manipulation

• Interval trees: a balanced binary search tree that stores intervals and supports efficient queries like "find all intervals overlapping a given point" in $O(\log n + k)$ time, where $k$ is the number of results.
• Sweep line algorithms: process a collection of intervals by "sweeping" a vertical line across sorted endpoints. Useful for finding all pairwise overlaps among $n$ intervals in $O(n \log n + k)$ time.
• Interval arithmetic: direct algorithms for addition, subtraction, multiplication, and division of intervals, each running in constant time.

Complexity considerations

Many interval problems are efficiently solvable:

• Recognizing whether a graph is an interval graph can be done in $O(n + m)$ time (linear in vertices and edges).
• Sorting intervals by endpoints and applying greedy algorithms solves many scheduling problems in $O(n \log n)$.

Some problems remain hard. For instance, certain interval coloring variants and optimization problems over interval orders are NP-hard, requiring approximation algorithms or heuristics.

Generalization to other structures

Intervals in metric spaces

In a metric space $(X, d)$, you can define a "ball" $B(c, r) = \{x \in X \mid d(c, x) \leq r\}$ as an analogue of an interval. These metric intervals generalize the concept beyond linear orders and appear in computational geometry and spatial database queries (e.g., "find all points within 5 km of this location").

Intervals in graphs

In a graph $G$, an interval $[u, v]$ can be defined as the set of all vertices lying on some shortest path between $u$ and $v$. This notion connects Order Theory with Graph Theory and is central to the study of interval graphs, which represent intersection patterns of intervals on a line. Interval graphs have applications in genetics (modeling DNA fragment overlaps), scheduling, and network analysis.

Historical development

Origins of interval theory

• Intervals as subsets of the real line have been studied since the foundations of analysis and topology.
• Ramon Moore developed interval arithmetic in the 1960s as a tool for bounding computational errors.
• Peter Fishburn formalized interval orders in the 1970s, connecting them to measurement theory and preference modeling.
• James F. Allen introduced his interval algebra for temporal reasoning in 1983, which became foundational in AI.

Key contributors and milestones

• Georg Cantor's set theory provided the framework for rigorously defining intervals and their properties.
• Garrett Birkhoff's work on lattice theory established the algebraic tools used to study intervals in posets.
• More recent work has extended interval concepts into fuzzy set theory and soft computing, broadening their applicability to problems involving vagueness and gradual membership.