Total relation

In mathematics, a binary relation R over a set X is total or complete if for all a and b in X, a is related to b or b is related to a (or both).

In mathematical notation, this is

\forall a, b \in X,\ a R b \or b R a.

Total relations are sometimes said to have comparability.

Examples

For example, "is less than or equal to" is a total relation over the set of real numbers, because for two numbers either the first is less than or equal to the second, or the second is less than or equal to the first. On the other hand, "is less than" is not a total relation, since one can pick two equal numbers, and then neither the first is less than the second, nor is the second less than the first. (But note that "is less than" is a weak order which gives rise to a total order, namely "is less than or equal to". The relationship between strict orders and weak orders is discussed at partially ordered set.)

The relation "is a subset of" is also not total because, for example, neither of the sets {1,2} and {3,4} is a subset of the other.

Properties and related notions

Totality implies reflexivity.

If a transitive relation is also total, it is a total preorder. If a partial order is also total, it is a total order.

A binary relation R over X is called connex if for all a and b in X such that a ≠ b, a is related to b or b is related to a (or both):[1]

\forall a, b \in X,\ a R b \or b R a\or (a=b).

Connexity does not imply reflexivity. A strict partial order is a strict total order if and only if it is connex.

See also

References

  1. ↑ Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
This article is issued from Wikipedia - version of the Saturday, May 17, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.