Equivalence and order relations: Definition & Examples

An equivalence relation groups objects that count as the same under a specified rule. An order relation describes which objects precede or lie below others; a partial order allows some pairs to be incomparable, while a total order compares every pair. In quant work, these distinctions prevent “same model payoff” from becoming “same contract,” and “higher expected payoff” from becoming “better in every state.”

A binary relation on a set

X

is a collection of ordered pairs from

X

. Writing

xRy

means the pair

(x,y)

belongs to that collection. The rule and the objects it acts on must both be specified.

Grouping three contracts by their payoffs

Consider three fictional labelled contracts, all settling at the same terminal time in the same currency. The model has two exhaustive states. Their payoff vectors, in currency units, are

f(A)=(1,0),\qquad f(B)=(1,0),\qquad f(C)=(0,1).

Define $x\sim y$ when $f(x)=f(y)$ . This is an equivalence relation because equality of vectors is:

Reflexive: $f(x)=f(x)$ , so $x\sim x$ .
Symmetric: $f(x)=f(y)$ implies $f(y)=f(x)$ .
Transitive: $f(x)=f(y)$ and $f(y)=f(z)$ imply $f(x)=f(z)$ .

The equivalence class of

x

contains every object equivalent to it:

[x]=\{y\in X:y\sim x\}.

Here

[A]=[B]=\{A,B\}

and

[C]=\{C\}

. The distinct classes form a partition: nonempty, nonoverlapping groups covering the original set. The quotient set

X/{\sim}

is the set of these classes. Lehman and Leighton's MIT notes, §9.2, explain the equivalence-class and partition correspondence.

This classification retains only the specified payoff map. It says nothing by itself about A and B having the same price, counterparty, collateral terms or legal obligations. If such features matter, they must enter the representation or be considered separately.

Fictional contracts A and B both pay (1, 0), forming class {A, B}; C pays (0, 1), forming class {C}. In payoff space the zero vector is below both vectors, while A and C are incomparable because each pays more in one state.

Grouping contract labels and comparing payoff vectors answer different questions. A and B occupy one payoff point; A and C cannot be ordered component by component.

Ordering vectors, then ordering classes

Use the componentwise order on two-dimensional payoff vectors:

u\preceq v\quad\Longleftrightarrow\quad u_1\le v_1\ \text{and}\ u_2\le v_2.

This is a partial order: it is reflexive, transitive and antisymmetric. Antisymmetry means

u\preceq v\ \text{and}\ v\preceq u\quad\Longrightarrow\quad u=v.

It permits self-comparison; it does not mean “never related in both directions.” A set equipped with a partial order is a partially ordered set, or poset. We use the reflexive convention here. A strict partial order instead is irreflexive and transitive. Fleck's Relations chapter, §§6.3–6.5, develops these distinctions.

The zero vector

(0,0)

is below both

f(A)

and

f(C)

. But neither

f(A)\preceq f(C)

nor

f(C)\preceq f(A)

holds: A pays more in state 1 and C pays more in state 2. They are incomparable, not equal. A total order adds the requirement that

u\preceq v

v\preceq u

for every pair.

Now apply the same comparison to labelled contracts, defining

x\preceq_f y

when

f(x)\preceq f(y)

. Then

A\preceq_f B

and

B\preceq_f A

, although

A\ne B

. Antisymmetry fails on labels. The resulting relation is a preorder, which requires only reflexivity and transitivity; see Software Foundations, “Partial Orders and Preorders”.

Passing to payoff-equivalence classes repairs this:

[x]\preceq[y]\quad\Longleftrightarrow\quad f(x)\preceq f(y).

Choosing another representative changes neither payoff vector, so the comparison is well-defined. Comparison in both directions forces equal payoff vectors and therefore the same class. The classes have a genuine partial order.

What a ranking can hide

Suppose state 1 has probability

0.75

and state 2 has probability

0.25

. The expected payoffs are

0.75

for A and B, and

0.25

for C, in currency units. A has the larger expectation but still pays less than C in state 2. This is a ranking of expected terminal cash flows, not returns or investment attractiveness: purchase prices have not been supplied. Numeric score values are totally ordered, but ranking labelled contracts by those scores allows ties and generally gives a total preorder.

Likewise, “within a tolerance” is usually unsuitable for defining classes. With tolerance 1, the numbers 0 and 0.75 are close, as are 0.75 and 1.5, yet 0 and 1.5 are not. Transitivity fails. Grouping by an explicitly chosen bin label can define an equivalence relation, but its boundary choices are part of the rule.

There is also a useful computational application. In a directed graph, reachability allowing a zero-length path is a preorder. Mutual reachability groups vertices into equivalence classes—the strongly connected components. Reachability between those components is a partial order. Topological Sort and Strongly Connected Components develops the graph algorithms behind this construction. Its public preview is available; the full lesson requires membership. A topological ordering of a finite dependency graph can choose a sequence for incomparable components without turning that choice into a dependency between them.

Sources

Eric Lehman and Tom Leighton, Mathematics for Computer Science, Chapter 9 — equivalence classes, partitions, partial and total orders, and topological orderings.
Margaret M. Fleck, Building Blocks for Theoretical Computer Science, Chapter 6: Relations — relation properties and the reflexive versus strict order conventions.
Software Foundations, Logical Foundations: Properties of Relations — equivalence, partial-order and preorder definitions, and reflexive transitive closure.

Grouping three contracts by their payoffs

Ordering vectors, then ordering classes

What a ranking can hide

Sources

Related terms

Expected value

Payoff

Set

Vector