Total relation: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 15:30, 7 February 2024

In mathematics, a binary relation R ⊆ X×Y between two sets X and Y is total (or left total) if the source set X equals the domain {x : there is a y with xRy }. Conversely, R is called right total if Y equals the range {y : there is an x with xRy }.

When f: X → Y is a function, the domain of f is all of X, hence f is a total relation. On the other hand, if f is a partial function, then the domain may be a proper subset of X, in which case f is not a total relation.

"A binary relation is said to be total with respect to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else."^[1]

Algebraic characterization

Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let $X,Y$ be two sets, and let $R\subseteq X\times Y.$ For any two sets $A,B,$ let $L_{A,B}=A\times B$ be the universal relation between $A$ and $B,$ and let $I_{A}=\{(a,a):a\in A\}$ be the identity relation on $A.$ We use the notation $R^{\top }$ for the converse relation of $R.$

$R$ is total iff for any set $W$ and any $S\subseteq W\times X,$ $S\neq \emptyset$ implies $SR\neq \emptyset .$ ^[2]^: 54
$R$ is total iff $I_{X}\subseteq RR^{\top }.$ ^[2]^: 54
If $R$ is total, then $L_{X,Y}=RL_{Y,Y}.$ The converse is true if $Y\neq \emptyset .$ ^{[note 1]}
If $R$ is total, then ${\overline {RL_{Y,Y}}}=\emptyset .$ The converse is true if $Y\neq \emptyset .$ ^{[note 2]}^[2]^: 63
If $R$ is total, then ${\overline {R}}\subseteq R{\overline {I_{Y}}}.$ The converse is true if $Y\neq \emptyset .$ ^[2]^: 54^[3]
More generally, if $R$ is total, then for any set $Z$ and any $S\subseteq Y\times Z,$ ${\overline {RS}}\subseteq R{\overline {S}}.$ The converse is true if $Y\neq \emptyset .$ ^{[note 3]}^[2]^: 57

Notes

^ If $Y=\emptyset \neq X,$ then $R$ will be not total.
^ Observe ${\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},$ and apply the previous bullet.
^ Take $Z=Y,S=I_{Y}$ and appeal to the previous bullet.

References

^ Functions from Carnegie Mellon University
^ ^a ^b ^c ^d ^e Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.
^ Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

Gunther Schmidt & Michael Winter (2018) Relational Topology
C. Brink, W. Kahl, and G. Schmidt (1997) Relational Methods in Computer Science, Advances in Computer Science, page 5, ISBN 3-211-82971-7
Gunther Schmidt & Thomas Strohlein (2012)[1987] Relations and Graphs, p. 54, at Google Books
Gunther Schmidt (2011) Relational Mathematics, p. 57, at Google Books

[3] If $Y=\emptyset \neq X,$ then $R$ will be not total.

[4] Observe ${\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},$ and apply the previous bullet.

[6] Take $Z=Y,S=I_{Y}$ and appeal to the previous bullet.

[1] Functions from Carnegie Mellon University

[R&G-2] Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.

[GS11-5] Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

[1]

[2]

[note 1]

[note 2]

[3]

[note 3]

@@ Line 1: / Line 1: @@
+{{Short description|Type of logical relation}}
-In [[mathematics]], a [[binary relation]] ''R'' over a [[Set (mathematics)|set]] ''X'' is '''total''' if for all ''a'' and ''b'' in ''X'', ''a'' is related to ''b'' or ''b'' is related to ''a'' (or both).
+{{for|relations ''R'' where ''<nowiki>x=y</nowiki>'' or ''xRy'' or ''yRx'' for all ''x'' and ''y''|connected relation}}
+In [[mathematics]], a [[binary relation]] ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is '''total''' (or '''left total''') if the source set ''X'' equals the domain {''x'' : there is a ''y'' with ''xRy'' }. Conversely, ''R'' is called '''right total''' if ''Y'' equals the range {''y'' : there is an ''x'' with ''xRy'' }.
-In [[mathematical notation]], this is
-:<math>\forall a, b \in X,\ a R b \or b R a.</math>
+When ''f'': ''X'' → ''Y'' is a [[function (mathematics)|function]], the domain of ''f'' is all of ''X'', hence ''f'' is a total relation. On the other hand, if ''f'' is a [[partial function]], then the domain may be a proper subset of ''X'', in which case ''f'' is not a total relation.
-Total relations are sometimes said to have ''comparability''.
+"A binary relation is said to be total with respect  to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else."<ref>[http://caae.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m15_functions/chapter15.html Functions] from [[Carnegie Mellon University]]</ref>
-== 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]].)
+==Algebraic characterization==
-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.
+Total relations can be characterized algebraically by equalities and inequalities involving [[composition of relations|compositions of relations]]. To this end, let <math>X,Y</math> be two sets, and let <math>R\subseteq X\times Y.</math> For any two sets <math>A,B,</math> let <math>L_{A,B}=A\times B</math> be the [[universal relation]] between <math>A</math> and <math>B,</math> and let <math>I_A=\{(a,a):a\in A\}</math> be the [[identity relation]] on <math>A.</math> We use the notation <math>R^\top</math> for the [[converse relation]] of <math>R.</math>
+* <math>R</math> is total iff for any set <math>W</math> and any <math>S\subseteq W\times X,</math> <math>S\ne\emptyset</math> implies <math>SR\ne\emptyset.</math><ref name=R&G>{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=54}}|date=6 December 2012|publisher=[[Springer Science & Business Media]]|isbn=978-3-642-77968-8|author-link1=Gunther Schmidt}}</ref>{{rp|54}}
-== Properties and related notions ==
+* <math>R</math> is total iff <math>I_X\subseteq RR^\top.</math><ref name=R&G/>{{rp|54}}
-Totality implies [[Reflexive relation|reflexivity]].
+* If <math>R</math> is total, then <math>L_{X,Y}=RL_{Y,Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>If <math>Y=\emptyset\ne X,</math> then <math>R</math> will be not total.</ref>
+* If <math>R</math> is total, then <math>\overline{RL_{Y,Y}}=\emptyset.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Observe <math>\overline{RL_{Y,Y}}=\emptyset\Leftrightarrow RL_{Y,Y}=L_{X,Y},</math> and apply the previous bullet.</ref><ref name=R&G/>{{rp|63}}
-If a [[transitive relation]] is also total, it is a [[strict weak ordering#Total preorders|total preorder]]. If a [[partially ordered set|partial order]] is also total, it is a [[total order]].
+* If <math>R</math> is total, then <math>\overline R\subseteq R\overline{I_Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref name=R&G/>{{rp|54}}<ref name=GS11>{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | title=Relational Mathematics  | publisher=[[Cambridge University Press]] | year=2011 }} Definition 5.8, page 57.</ref>
+* More generally, if <math>R</math> is total, then for any set <math>Z</math> and any <math>S\subseteq Y\times Z,</math> <math>\overline{RS}\subseteq R\overline S.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Take <math>Z=Y,S=I_Y</math> and appeal to the previous bullet.</ref><ref name=R&G/>{{rp|57}}
-A binary relation ''R'' over ''X'' is called '''connex''' if for all ''a'' and ''b'' in ''X'' such that ''a''&nbsp;≠&nbsp;''b'', ''a'' is related to ''b'' or ''b'' is related to ''a'' (or both):<ref>{{citation
-|title=A Concise Introduction to Mathematical Logic
-|last=Rautenberg
-|first=Wolfgang
-|authorlink=Wolfgang Rautenberg
-|edition=3rd
-|publisher=[[Springer Science+Business Media]]
-|year=2010
-|isbn=978-1-4419-1220-6
-|doi=10.1007/978-1-4419-1221-3
-|url=http://www.springerlink.com/content/978-1-4419-1220-6/
-|location=New York}}</ref>
-:<math>\forall a, b \in X,\ a R b \or b R a\or (a=b).</math>
-Connexity does not imply reflexivity. A strict partial order is a strict total order if and only if it is connex.
 ==See also==
+* [[Serial relation]] &mdash; a total homogeneous relation
-* [[Total order]]
+==Notes==
+{{reflist|group=note}}
 ==References==
+{{reflist}}
-<references />
+* [[Gunther Schmidt]] & Michael Winter (2018) ''Relational Topology''
+* C. Brink, W. Kahl, and G. Schmidt (1997) ''Relational Methods in Computer Science'', Advances in Computer Science, page 5, {{ISBN|3-211-82971-7}}
+* Gunther Schmidt & Thomas Strohlein (2012)[1987] {{Google books|ZgarCAAAQBAJ|Relations and Graphs|page=54}}
+* Gunther Schmidt (2011) {{Google books|E4REBTs5WsC|Relational Mathematics|page=57}}
+{{Order theory}}
-[[Category:Mathematical relations]]
+[[Category:Properties of binary relations]]
-[[pl:Relacja spójna]]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice