7
$\begingroup$

I see two apparently different definitions for totality which don't seem to be equivalent.

Definition 1. A relation $R \subset X \times Y$ is total if it associates to every $x \in X$ at least one $y \in Y$; that is

$\forall x \in X \;\; \exists y \in Y: (x,y) \in R$.

References:

  1. Gunther Schmidt and Thomas Strohlein, Relations and Groups, page 54, Springer.
  2. Chris Brink et al, Relational Methods for Computer Science, page 5, Springer.

Definition 1'. A (binary) relation $R$ over $X$ is total if

$\forall a, b \in X: (a,b) \in R \vee (b,a) \in R$.

Reference:

  1. http://en.wikipedia.org/wiki/Total_relation

Can you please elaborate on the incompatibility of these two definitions (if you think they are) and the reasons for it? Is there any de facto standard? Would you suggest other names (e.g. 'linearity' for the second property)?

Edit: More information

Looking at a number of resources on the Web, it seems that left-totality is a more common name for the first definition. For example see:

  1. https://www.proofwiki.org/wiki/Definition:Left-Total_Relation
  2. https://en.wikipedia.org/wiki/Binary_relation#Special_types_of_binary_relations

Totality seems to be a more common name for the second definition. I would personally prefer "strictly connected" for the second definition because if you call it totality, one would expect to see a connection between that and left-totality or right-totality whereas I don't think there is one.

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

They do not seem incompatible to me since they talk about different types of 'totality'. The first definition takes 2 sets $X, Y$. While the second definition uses only one set. (It's a binary relation over one set, wikipedia speaks of endorelation)

You could transform the first definition so that it uses one set:

A relation $R \subset X\times X$ is total if it associates to every $a \in X$ at least one $b \in X$; that is

$$\forall a \in X, \exists b \in X: (a,b) \in R$$

However, this is weaker than the second definition. Wikipedia would speak of left-total.

Roughly said:

  • The first definition demands that from every element in the source at least one relation departs.

  • While the second definition demands that every element in a set has a connection with every other element in either one, or another direction (or both)

Compare following examples: In the first picture the relation is left-total from $X$ to $X$. (Every element has at least one arrow departing - C has even two arrows departing). While the (endo)relation is not total as in definition 2. In the second picture it is total as in in definition 2. It also seems to be left-total.

(When a relation is total as in definition 2, it does not have to be left-total. Can you find an example?) total relation

$\endgroup$
3
  • $\begingroup$ They use the "binary relation" as an example of a relation, not necessarily totality. $\endgroup$
    – Don Larynx
    Dec 20, 2014 at 0:42
  • $\begingroup$ "When a relation is total as in definition 2, it does not have to be left-total. Can you find an example?". I think it has to be left-total (and also right-total) as the second definition implies reflexivity. $\endgroup$
    – Loax
    Dec 20, 2014 at 2:04
  • $\begingroup$ Whoops, forgot about reflexivity. You're completely right! (=> second picture is not complete, I should have included the loops..., first picture looks complete though) $\endgroup$
    – dietervdf
    Dec 20, 2014 at 2:08
1
$\begingroup$

Consider the relation $(n, 2n) \in R \lor (2n, n) \in R$.

This would not be total if the $Y$ consisted only of the identical objects (members) in $X$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .