Manidh: 1 revision imported

2023-07-16T03:27:33Z

1 revision imported

← Older revision	Revision as of 08:57, 16 July 2023
(No difference)

wikipedia>OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T05:19:06Z

Open access bot: doi added to citation with #oabot.

New page

{{Short description|Property of elements related by inequalities}}
{{More citations needed|date=December 2021}}{{Wiktionary|comparability}}
{{See also|Comparison (mathematics)}}
[[File:Infinite lattice of divisors.svg|thumb|[[Hasse diagram]] of the [[natural number]]s, partially ordered by "''x''≤''y'' if ''x'' [[divides]] ''y''". The numbers 4 and 6 are incomparable, since neither divides the other.]]
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 ==

A [[binary relation]] on a set <math>P</math> is by definition any subset <math>R</math> of <math>P \times P.</math> Given <math>x, y \in P,</math> <math>x R y</math> is written if and only if <math>(x, y) \in R,</math> in which case <math>x</math> is said to be '''{{em|related}}''' to <math>y</math> by <math>R.</math>
An element <math>x \in P</math> is said to be '''{{em|<math>R</math>-comparable}}''', or '''{{em|comparable}}''' ({{em|with respect to <math>R</math>}}), to an element <math>y \in P</math> if <math>x R y</math> or <math>y R x.</math>
Often, a symbol indicating comparison, such as <math>\,<\,</math> (or <math>\,\leq\,,</math> <math>\,>,\,</math> <math>\geq,</math> and many others) is used instead of <math>R,</math> in which case <math>x < y</math> is written in place of <math>x R y,</math> which is why the term "comparable" is used.

Comparability with respect to <math>R</math> induces a canonical binary relation on <math>P</math>; specifically, the '''{{em|comparability relation}}''' induced by <math>R</math> is defined to be the set of all pairs <math>(x, y) \in P \times P</math> such that <math>x</math> is comparable to <math>y</math>; that is, such that at least one of <math>x R y</math> and <math>y R x</math> is true.
Similarly, the '''{{em|incomparability relation}}''' on <math>P</math> induced by <math>R</math> is defined to be the set of all pairs <math>(x, y) \in P \times P</math> such that <math>x</math> is incomparable to <math>y;</math> that is, such that neither <math>x R y</math> nor <math>y R x</math> is true.

If the symbol <math>\,<\,</math> is used in place of <math>\,\leq\,</math> then comparability with respect to <math>\,<\,</math> is sometimes denoted by the symbol <math>\overset{<}{\underset{>}{=}}</math>, and incomparability by the symbol <math>\cancel{\overset{<}{\underset{>}{=}}}\!</math>.<ref>{{citation|title=Combinatorics and Partially Ordered Sets:Dimension Theory | authorlink=William T. Trotter|first=William T.|last=Trotter|publisher=Johns Hopkins Univ. Press|year=1992|pages=3}}</ref>
Thus, for any two elements <math>x</math> and <math>y</math> of a partially ordered set, exactly one of <math>x\ \overset{<}{\underset{>}{=}}\ y</math> and <math>x \cancel{\overset{<}{\underset{>}{=}}}y</math> is true.

== Example ==

A [[Total order|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 {{em|comparability}} and {{em|incomparability}} are [[Symmetric relation|symmetric]], that is <math>x</math> is comparable to <math>y</math> if and only if <math>y</math> is comparable to <math>x,</math> and likewise for incomparability.

== Comparability graphs ==
{{main article|Comparability graph}}
The comparability graph of a partially ordered set <math>P</math> has as vertices the elements of <math>P</math> and has as edges precisely those pairs <math>\{ x, y \}</math> of elements for which <math>x\ \overset{<}{\underset{>}{=}}\ y</math>.<ref>{{citation|title=A characterization of comparability graphs and of interval graphs|first1=P. C.|last1=Gilmore|first2=A. J.|last2=Hoffman|author2-link=Alan Hoffman (mathematician)|url=http://www.cms.math.ca/cjm/v16/p539|journal=Canadian Journal of Mathematics|volume=16|year=1964|pages=539–548|doi=10.4153/CJM-1964-055-5|doi-access=free}}.</ref>

== Classification ==

When [[Class (set theory)|classifying]] mathematical objects (e.g., [[topological space]]s), two {{em|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 space|T1]] and [[Hausdorff space|T2]] criteria are comparable, while the T1 and [[Sober space|sobriety]] criteria are not.

== See also ==
* {{annotated link|Strict weak ordering}}, a partial ordering in which incomparability is a [[transitive relation]]

==References==

{{reflist}}

==External links==

* {{cite web |url=http://planetmath.org/encyclopedia/PartialOrder.html |title=PlanetMath: partial order|author= |date= |publisher= |access-date=6 April 2010}}

{{Order theory}}

[[Category:Binary relations]]
[[Category:Order theory]]

Comparability - Revision history

Manidh: 1 revision imported

wikipedia>OAbot: Open access bot: doi added to citation with #oabot.