From Wikipedia, the free encyclopedia
Type of logical 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 }.
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
{\displaystyle X,Y}
be two sets, and let
R
⊆
X
×
Y
.
{\displaystyle R\subseteq X\times Y.}
For any two sets
A
,
B
,
{\displaystyle A,B,}
let
L
A
,
B
=
A
×
B
{\displaystyle L_{A,B}=A\times B}
be the
universal relation between
A
{\displaystyle A}
and
B
,
{\displaystyle B,}
and let
I
A
=
{
(
a
,
a
)
:
a
∈
A
}
{\displaystyle I_{A}=\{(a,a):a\in A\}}
be the
identity relation on
A
.
{\displaystyle A.}
We use the notation
R
⊤
{\displaystyle R^{\top }}
for the
converse relation of
R
.
{\displaystyle R.}
R
{\displaystyle R}
is total iff for any set
W
{\displaystyle W}
and any
S
⊆
W
×
X
,
{\displaystyle S\subseteq W\times X,}
S
≠
∅
{\displaystyle S\neq \emptyset }
implies
S
R
≠
∅
.
{\displaystyle SR\neq \emptyset .}
[2] : 54
R
{\displaystyle R}
is total iff
I
X
⊆
R
R
⊤
.
{\displaystyle I_{X}\subseteq RR^{\top }.}
[2] : 54
If
R
{\displaystyle R}
is total, then
L
X
,
Y
=
R
L
Y
,
Y
.
{\displaystyle L_{X,Y}=RL_{Y,Y}.}
The converse is true if
Y
≠
∅
.
{\displaystyle Y\neq \emptyset .}
[note 1]
If
R
{\displaystyle R}
is total, then
R
L
Y
,
Y
¯
=
∅
.
{\displaystyle {\overline {RL_{Y,Y}}}=\emptyset .}
The converse is true if
Y
≠
∅
.
{\displaystyle Y\neq \emptyset .}
[note 2]
[2] : 63
If
R
{\displaystyle R}
is total, then
R
¯
⊆
R
I
Y
¯
.
{\displaystyle {\overline {R}}\subseteq R{\overline {I_{Y}}}.}
The converse is true if
Y
≠
∅
.
{\displaystyle Y\neq \emptyset .}
[2] : 54
[3]
More generally, if
R
{\displaystyle R}
is total, then for any set
Z
{\displaystyle Z}
and any
S
⊆
Y
×
Z
,
{\displaystyle S\subseteq Y\times Z,}
R
S
¯
⊆
R
S
¯
.
{\displaystyle {\overline {RS}}\subseteq R{\overline {S}}.}
The converse is true if
Y
≠
∅
.
{\displaystyle Y\neq \emptyset .}
[note 3]
[2] : 57
See also
Notes
^ If
Y
=
∅
≠
X
,
{\displaystyle Y=\emptyset \neq X,}
then
R
{\displaystyle R}
will be not total.
^ Observe
R
L
Y
,
Y
¯
=
∅
⇔
R
L
Y
,
Y
=
L
X
,
Y
,
{\displaystyle {\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},}
and apply the previous bullet.
^ Take
Z
=
Y
,
S
=
I
Y
{\displaystyle Z=Y,S=I_{Y}}
and appeal to the previous bullet.
References
Key concepts Results Properties & Types (
list ) Constructions
Topology & Orders Related