Rel, bicategory of relations, allegory
left and right euclidean;
extensional, well-founded relations.
A total relation or linear relation is a binary relation on a set with the property that distinguishes the total orders/linear orders among the partial orders.
An entire relation is sometimes called ‘total’, but these are unrelated concepts. The ‘total’ there is in the sense of a total (as opposed to partial) function, while the ‘total’ here is in the sense of a total (as opposed to partial) order.
A total relation is necessarily reflexive. For an irreflexive version, see connected relation. In classical mathematics, total relations and connected relations are equivalent concepts, since either may be constructed from the other by changing every truth value of the form , and so the distinction is not always maintained.
A binary relation on a set is total if any two elements are related in one order or the other:
In other words, is total if its union with its reverse is the universal relation?:
(Of course, this containment is in fact an equality.) In this way, the concept can be generalized from Rel to any -poset-with-duals?; part of the definition then becomes the requirement that the union exists.
In constructive mathematics, we can distinguish between a strongly total relation, defined as above, and a weakly total or linear relation:
(In theory, this should be conjoined with , but this follows because the original definition is symmetric in and .) This can also be expressed in using the weak union instead of and generalized to other -posets with the structure to support this operation. We can define an even weaker notion:
which is based on using the double negation of union in , but I'm not sure that anyone uses this in practice.
We can also let be a disjoint pair? of relations, denoted and or (more suggestively) and , related according to the antithesis interpretation of linear logic within constructive mathematics, which requires that
(but not the converse). Then is weakly total or linear if additionally
It's strongly total if, in addition to all of the above,
This can all be expressed in a -poset of disjoint pairs of relations equipped with strong () and weak () notions of union.
A total order is precisely a partial order that is total in the sense of this article.
In classical logic, is total if and only if for some connected relation , and then must be . (Here, is the equality relation on the set .)
Totality is antithetical to asymmetry. In classical logic, this means that is total if and only if its negation is asymmetric. More generally, in terms of the antithesis interpretation, the disjoint pair is strongly/weakly total if and only if its formal negation is strongly/weakly asymmetric.
In particular, is asymmetric in its own right whenever a disjoint pair is weakly total. Conversely, a disjoint pair is strongly total if (and only if) is strongly total in its own right and is asymmetric in its own right.
For linearity of relations as weak totality, see section 11.2.1 of:
Last revised on December 26, 2023 at 04:50:05. See the history of this page for a list of all contributions to it.