Total (Complete) Relation

A relation is total (or complete) if any two distinct elements are comparable. This means that for every a,b ∈ A, either (a,b) ∈ R or (b,a) ∈ R.

In other words: between any two elements, we can always determine which one comes before the other or is related to it; there is no pair that cannot be compared.

Examples of Total Relations

• The ≤ relation on natural numbers: for any two numbers, we can decide which is smaller or equal.
• The ≥ relation is also total, because every two numbers can be compared with it too.
• Alphabetical order (lexicographic order) among words: between any two words, we can determine which follows the other.

Counterexamples (Non-Total Relations)

• The divisibility relation on natural numbers is not total, because for example 2 does not divide 3, and 3 does not divide 2.
• The sibling relation is also not total, because not every pair of people has such a connection.

Summary

In total relations, every two elements are comparable, which is fundamental in orderings, such as arranging numbers or words. If a relation is not total, there are certain pairs that cannot be compared.

Practice Exercise