Search Results for “comparability”

Source: Comparability

In mathematics, two elements x and y of a set P are said to be comparable with respect to a binary relation ≤ if at least one of x ≤ y or y ≤ x is true. They are called incomparable if they are not comparable.

Rigorous definition

is written in place of

x
R
y
,

{\displaystyle xRy,}

which is why the term "comparable" is used.
Comparability with respect to

R

{\displaystyle R}

induces a canonical binary relation on

P

{\displaystyle P}

; specifically, the comparability relation induced by

R

{\displaystyle R}

is defined to be the set of all pairs

(
x
,
y
)
∈
P
×
P

{\displaystyle (x,y)\in P\times P}

such that

x

{\displaystyle x}

is comparable to

y

{\displaystyle y}

; that is, such that at least one of

x
R
y

{\displaystyle xRy}

and

y
R
x

{\displaystyle yRx}

is true.
Similarly, the incomparability relation on

P

{\displaystyle P}

induced by

R

{\displaystyle R}

is defined to be the set of all pairs

(
x
,
y
)
∈
P
×
P

{\displaystyle (x,y)\in P\times P}

such that

x

{\displaystyle x}

is incomparable to

y
;

{\displaystyle y;}

that is, such that neither

x
R
y

{\displaystyle xRy}

nor

y
R
x

{\displaystyle yRx}

is true.
If the symbol

<

{\displaystyle \,<\,}

is used in place of

≤

{\displaystyle \,\leq \,}

then comparability with respect to

<

{\displaystyle \,<\,}

is sometimes denoted by the symbol

=
>

<

{\displaystyle {\overset {<}{\underset {>}{=}}}}

, and incomparability by the symbol

=
>

<

{\displaystyle {\cancel {\overset {<}{\underset {>}{=}}}}\!}

.
Thus, for any two elements

x

{\displaystyle x}

and

y

{\displaystyle y}

of a partially ordered set, exactly one of

x

=
>

<

y

{\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}

and

x

=
>

<

y

{\displaystyle x{\cancel {\overset {<}{\underset {>}{=}}}}y}

is true.

Example

A totally ordered set is a partially ordered set in which any two elements are comparable. The Szpilrajn extension theorem states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable.

Properties

Both of the relations comparability and incomparability are symmetric, that is

x

{\displaystyle x}

is comparable to

y

{\displaystyle y}

if and only if

y

{\displaystyle y}

is comparable to

x
,

{\displaystyle x,}

and likewise for incomparability.

Comparability graphs

The comparability graph of a partially ordered set

P

{\displaystyle P}

has as vertices the elements of

P

{\displaystyle P}

and has as edges precisely those pairs

{
x
,
y
}

{\displaystyle \{x,y\}}

of elements for which

x

=
>

<

y

{\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}

.

Classification

When classifying mathematical objects (e.g., topological spaces), two criteria are said to be comparable when the objects that obey one criterion constitute a subset of the objects that obey the other, which is to say when they are comparable under the partial order ⊂. For example, the T1 and T2 criteria are comparable, while the T1 and sobriety criteria are not.