Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Η σχέση
R
{\displaystyle R}
και η αντίστροφή της
Η γραφική αναπαράσταση και ο πίνακας μίας σχέσης
R
{\displaystyle R}
και της αντίστροφής της
R
T
{\displaystyle R^{T}}
Στην θεωρία συνόλων , η αντίστροφη σχέση μίας σχέσης
R
⊆
X
×
Y
{\displaystyle R\subseteq X\times Y}
R
T
⊆
Y
×
X
{\displaystyle R^{T}\subseteq Y\times X}
[ 1] :23 [ 2] :5 [ 3]
R
T
=
{
(
y
,
x
)
:
(
x
,
y
)
∈
R
}
{\displaystyle R^{T}=\{(y,x):(x,y)\in R\}}
δηλαδή έχει όλα τα ζεύγη της
R
{\displaystyle R}
Η αντίστροφη σχέση συμβολίζεται επίσης ως
R
−
1
{\displaystyle R^{-1}}
R
op
{\displaystyle R^{\text{op}}}
Η αντίστροφη σχέση της σχέσης "είναι γονιός του/της" είναι "είναι παιδί του/της".
Η αντίστροφη σχέση της σύγκρισης
<
{\displaystyle <}
>
{\displaystyle >}
Η αντίστροφη σχέση μίας συμμετρικής σχέσης είναι η ίδια η σχέση. Έτσι, η ταυτοτική σχέση είναι η αντίστροφη του εαυτού της.
Η αντίστροφη της σχέσης
R
=
{
(
1
,
β
)
,
(
1
,
δ
)
,
(
3
,
δ
)
,
(
4
,
α
)
,
(
4
,
δ
)
,
(
5
,
β
)
}
{\displaystyle R=\{(1,\beta ),(1,\delta ),(3,\delta ),(4,\alpha ),(4,\delta ),(5,\beta )\}}
είναι η σχέση (δείτε και τις δύο εικόνες παραπάνω)
R
T
=
{
(
α
,
4
)
,
(
β
,
1
)
,
(
β
,
5
)
,
(
δ
,
1
)
,
(
δ
,
3
)
,
(
δ
,
4
)
}
{\displaystyle R^{T}=\{(\alpha ,4),(\beta ,1),(\beta ,5),(\delta ,1),(\delta ,3),(\delta ,4)\}}
Ο πίνακας της αντίστροφης σχέσης είναι ο ανάστροφος της αρχικής, δηλαδή
M
(
R
T
)
=
(
M
(
R
)
)
T
{\displaystyle M(R^{T})=(M(R))^{T}}
Η αντιστροφή μίας σχέσης είναι ταυτοδύναμη πράξη, δηλαδή
(
R
T
)
T
=
R
{\displaystyle (R^{T})^{T}=R}
Η γραφική αναπαράσταση της
R
T
{\displaystyle R^{T}}
R
{\displaystyle R}
Για οποιεσδήποτε δύο σχέσεις
R
,
S
{\displaystyle R,S}
[ 3] : 1
Αν
R
⊆
S
{\displaystyle R\subseteq S}
R
T
⊆
S
T
{\displaystyle R^{T}\subseteq S^{T}}
Απόδειξη
R
⊆
S
⇔
∀
x
∈
X
.
∀
y
∈
Y
.
(
x
,
y
)
∈
R
⇒
(
x
,
y
)
∈
S
⇔
∀
x
∈
X
.
∀
y
∈
Y
.
(
y
,
x
)
∈
R
T
⇒
(
y
,
x
)
∈
S
T
⇔
R
T
⊆
S
T
{\displaystyle {\begin{aligned}&R\subseteq S\Leftrightarrow \\&\forall x\in X.\ \forall y\in Y.\ (x,y)\in R\Rightarrow (x,y)\in S\Leftrightarrow \\&\forall x\in X.\ \forall y\in Y.\ (y,x)\in R^{T}\Rightarrow (y,x)\in S^{T}\Leftrightarrow \\&R^{T}\subseteq S^{T}\end{aligned}}}
(
R
∩
S
)
T
=
R
T
∩
S
T
{\displaystyle (R\cap S)^{T}=R^{T}\cap S^{T}}
Απόδειξη
Η απόδειξη προκύπτει από τις εξής ισοδυναμίες
(
x
,
y
)
∈
R
T
∩
S
T
⇔
(
x
,
y
)
∈
R
T
∧
(
x
,
y
)
∈
S
T
⇔
(
y
,
x
)
∈
R
∧
(
y
,
x
)
∈
S
⇔
(
y
,
x
)
∈
R
∩
S
{\displaystyle {\begin{aligned}&(x,y)\in R^{T}\cap S^{T}\Leftrightarrow \\&(x,y)\in R^{T}\wedge (x,y)\in S^{T}\Leftrightarrow \\&(y,x)\in R\wedge (y,x)\in S\Leftrightarrow \\&(y,x)\in R\cap S\end{aligned}}}
(
R
∪
S
)
T
=
R
T
∪
S
T
{\displaystyle (R\cup S)^{T}=R^{T}\cup S^{T}}
Απόδειξη
Η απόδειξη προκύπτει από τις εξής ισοδυναμίες
(
x
,
y
)
∈
R
T
∩
S
T
⇔
(
x
,
y
)
∈
R
T
∧
(
x
,
y
)
∈
S
T
⇔
(
y
,
x
)
∈
R
∧
(
y
,
x
)
∈
S
⇔
(
y
,
x
)
∈
R
∩
S
⇔
(
x
,
y
)
∈
(
R
∩
S
)
T
{\displaystyle {\begin{aligned}&(x,y)\in R^{T}\cap S^{T}\Leftrightarrow \\&(x,y)\in R^{T}\wedge (x,y)\in S^{T}\Leftrightarrow \\&(y,x)\in R\wedge (y,x)\in S\Leftrightarrow \\&(y,x)\in R\cap S\Leftrightarrow \\&(x,y)\in (R\cap S)^{T}\end{aligned}}}
(
R
∘
S
)
T
=
S
T
∘
R
T
{\displaystyle (R\circ S)^{T}=S^{T}\circ R^{T}}
Απόδειξη
(
x
,
y
)
∈
S
T
∘
R
T
⇔
∃
z
.
(
x
,
z
)
∈
S
T
∧
(
z
,
y
)
∈
R
T
⇔
∃
z
.
(
z
,
x
)
∈
S
∧
(
y
,
z
)
∈
R
⇔
∃
z
.
(
y
,
z
)
∈
R
∧
(
z
,
x
)
∈
S
⇔
(
y
,
x
)
∈
R
∘
S
⇔
(
x
,
y
)
∈
(
R
∘
S
)
T
.
{\displaystyle {\begin{aligned}(x,y)\in S^{T}\circ R^{T}\Leftrightarrow \\\exists z.\ (x,z)\in S^{T}\wedge (z,y)\in R^{T}\Leftrightarrow \\\exists z.\ (z,x)\in S\wedge (y,z)\in R\Leftrightarrow \\\exists z.\ (y,z)\in R\wedge (z,x)\in S\Leftrightarrow \\(y,x)\in R\circ S\Leftrightarrow \\(x,y)\in (R\circ S)^{T}.\end{aligned}}}
Μία σχέση είναι συμμετρική ανν
R
=
R
T
{\displaystyle R=R^{T}}
Μία σχέση είναι αντισυμμετρική ανν
R
∩
R
T
⊆
i
d
X
{\displaystyle R\cap R^{T}\subseteq \mathrm {id} _{X}}
i
d
X
{\displaystyle \mathrm {id} _{X}}
ταυτοτική σχέση στο σύνολο
X
{\displaystyle X}
Μία σχέση είναι μερική συνάρτηση ανν
R
∘
R
T
⊆
i
d
Y
{\displaystyle R\circ R^{T}\subseteq \mathrm {id} _{Y}}
Μία σχέση είναι (ολική) συνάρτηση ανν
R
∘
R
T
⊆
i
d
Y
{\displaystyle R\circ R^{T}\subseteq \mathrm {id} _{Y}}
R
T
∘
R
⊆
i
d
X
{\displaystyle R^{T}\circ R\subseteq \mathrm {id} _{X}}
