二項関係 ②
Def.
$A,B$ を集合とし、$R,S\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
このとき、$R$ と $S$ の和関係とは
$$
R\cup S:=\{(a,b)\in A\times B\mid (a,b)\in R\lor (a,b)\in S\}
$$
で定まる $A$ から $B$ への二項関係のことである。
集合 $A,B$ を
$$
A=\{1,2\},\qquad B=\{x,y,z\}
$$
で定める。$A$ から $B$ への二項関係 $R,S\subseteq A\times B$ を
$$
R=\{(1,x),(2,y)\}
$$
$$
S=\{(1,y),(2,y),(2,z)\}
$$
で定める。このとき、$R$ と $S$ の和関係は
$$
R\cup S=\{(1,x),(1,y),(2,y),(2,z)\}
$$
である。一方、たとえば
$$
(1,z)\notin R\land (1,z)\notin S
$$
であるから、
$$
(1,z)\notin R\cup S
$$
である。
$R$ と $S$ の和関係 $R\cup S$ は、二項関係に特有の新しい演算ではなく、集合としての通常の和集合である。
ただし、$R,S\subseteq A\times B$ であるため、
$$
R\cup S\subseteq A\times B
$$
が成り立ち(
証明はコチラ
)、$R\cup S$ も $A$ から $B$ への二項関係となる。
$A,B$ を集合とし、$R,S\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
このとき、$R$ と $S$ の共通関係とは
$$
R\cap S:=\{(a,b)\in A\times B\mid (a,b)\in R\land (a,b)\in S\}
$$
で定まる $A$ から $B$ への二項関係のことである。
集合 $A,B$ を
$$
A=\{1,2\},\qquad B=\{x,y,z\}
$$
で定める。
$A$ から $B$ への二項関係 $R,S\subseteq A\times B$ を
$$
R=\{(1,x),(1,y),(2,y)\}
$$
$$
S=\{(1,y),(2,y),(2,z)\}
$$
で定める。
このとき、$R$ と $S$ の共通関係は
$$
R\cap S=\{(1,y),(2,y)\}
$$
である。
したがって、$R\cap S$ は $R$ と $S$ の両方に属する順序対だけを集めた関係である。
$R$ と $S$ の共通関係 $R\cap S$ は、二項関係に特有の新しい演算ではなく、集合としての通常の共通部分である。
ただし、$R,S\subseteq A\times B$ であるため、
$$
R\cap S\subseteq A\times B
$$
が成り立つ(
証明はコチラ
)。
したがって、$R\cap S$ も $A$ から $B$ への二項関係である。
$A,B$ を集合とし、$R,S\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
このとき、$R$ から $S$ を引いた差関係とは
$$
R\setminus S:=\{(a,b)\in A\times B\mid (a,b)\in R\land (a,b)\notin S\}
$$
で定まる $A$ から $B$ への二項関係のことである。
集合 $A,B$ を
$$
A=\{1,2\},\qquad B=\{x,y,z\}
$$
で定める。$A$ から $B$ への二項関係 $R,S\subseteq A\times B$ を
$$
R=\{(1,x),(1,y),(2,y),(2,z)\}
$$
$$
S=\{(1,y),(2,z)\}
$$
で定める。このとき、$R$ から $S$ を引いた差関係は
$$
R\setminus S=\{(1,x),(2,y)\}
$$
である。
$R$ から $S$ を引いた差関係 $R\setminus S$ は、二項関係に特有の新しい演算ではなく、集合としての通常の差集合である。
ただし、$R,S\subseteq A\times B$ であるため、
$$
R\setminus S\subseteq A\times B
$$
が成り立つ(
証明はコチラ
)。
したがって、$R\setminus S$ も $A$ から $B$ への二項関係である。
$A,B$ を集合とし、$R\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
このとき、$R$ の $A\times B$ に関する補関係とは
$$
R^c:=(A\times B)\setminus R
$$
で定まる $A$ から $B$ への二項関係のことである。
すなわち、
$$
R^c=\{(a,b)\in A\times B\mid (a,b)\notin R\}
$$
である。
集合 $A,B$ を
$$
A=\{1,2\},\qquad B=\{x,y,z\}
$$
で定める。
このとき、
$$
A\times B=\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}
$$
である。$A$ から $B$ への二項関係 $R\subseteq A\times B$ を
$$
R=\{(1,x),(2,y)\}
$$
で定める。
このとき、$R$ の $A\times B$ に関する補関係は、$A\times B$ に属する順序対のうち、$R$ に属さないものをすべて集めた関係である。
したがって、
$$
R^c=\{(1,y),(1,z),(2,x),(2,z)\}
$$
である。
$R$ の補関係 $R^c$ は、単に $R$ の外側すべてを集めたものではなく、
$A\times B$ の中で $R$ に属さない順序対を集めたものである。
すなわち、
$$
R^c=(A\times B)\setminus R
$$
であり、ここでの全体集合は $A\times B$ である。
したがって、全体集合を変えると補関係も変わる。
$A,B$ を集合とし、$R,S\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
このとき、$R$ と $S$ の対称差関係とは
$$
R\triangle S:=\{(a,b)\in A\times B\mid \bigl((a,b)\in R\land (a,b)\notin S\bigr)\lor \bigl((a,b)\notin R\land (a,b)\in S\bigr)\}
$$
で定まる $A$ から $B$ への二項関係のことである。
同値に、
$$
R\triangle S=(R\setminus S)\cup (S\setminus R)
$$
と定めてもよい。
集合 $A,B$ を
$$
A=\{1,2\},\qquad B=\{x,y,z\}
$$
で定める。
$A$ から $B$ への二項関係 $R,S\subseteq A\times B$ を
$$
R=\{(1,x),(1,y),(2,y)\}
$$
$$
S=\{(1,y),(2,y),(2,z)\}
$$
で定める。
このとき、$R$ と $S$ の対称差関係は
$$
R\triangle S=\{(1,x),(2,z)\}
$$
である。
したがって、$R\triangle S$ は、$R$ と $S$ のどちらか一方だけに属する順序対を集めた関係である。
$R\triangle S$ は、$R$ または $S$ の少なくとも一方に属する順序対をすべて集める和関係 $R\cup S$ とは異なる。
$R\triangle S$ は、$R$ と $S$ のどちらか一方だけに属する順序対を集める関係である。
したがって、
$$
R\triangle S=(R\cup S)\setminus(R\cap S)
$$
とも表せる。
Prop&Proof.
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。さらに
$$
R\subseteq S
$$
とする。このとき
$$
\operatorname{dom}(R)\subseteq \operatorname{dom}(S)
$$
が成り立つ。
$\operatorname{dom}(R)\subseteq \operatorname{dom}(S)$ を示す。
任意に $x\in \operatorname{dom}(R)$ をとる。定義域の定義より、
$$
x\in A\land \exists y\in B\ ((x,y)\in R)
$$
が成り立つ。
したがって、
$$
x\in A
$$
であり、かつ、ある $y\in B$ が存在して
$$
(x,y)\in R
$$
が成り立つ。
仮定 $R\subseteq S$ より、
$$
(x,y)\in S
$$
である。
よって、$x\in A$ であり、かつ、ある $y\in B$ が存在して
$$
(x,y)\in S
$$
が成り立つ。
したがって、定義域の定義より、
$$
x\in \operatorname{dom}(S)
$$
である。
ゆえに、任意の $x\in \operatorname{dom}(R)$ に対して $x\in \operatorname{dom}(S)$ が成り立つので、
$$
\operatorname{dom}(R)\subseteq \operatorname{dom}(S)
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。さらに
$$
R\subseteq S
$$
とする。このとき
$$
\operatorname{ran}(R)\subseteq \operatorname{ran}(S)
$$
が成り立つ。
$\operatorname{ran}(R)\subseteq \operatorname{ran}(S)$ を示す。
任意に $y\in \operatorname{ran}(R)$ をとる。値域の定義より、
$$
y\in B\land \exists x\in A\ ((x,y)\in R)
$$
が成り立つ。
したがって、
$$
y\in B
$$
であり、かつ、ある $x\in A$ が存在して
$$
(x,y)\in R
$$
が成り立つ。
仮定 $R\subseteq S$ より、
$$
(x,y)\in S
$$
である。
よって、$y\in B$ であり、かつ、ある $x\in A$ が存在して
$$
(x,y)\in S
$$
が成り立つ。
したがって、値域の定義より、
$$
y\in \operatorname{ran}(S)
$$
である。
ゆえに、任意の $y\in \operatorname{ran}(R)$ に対して $y\in \operatorname{ran}(S)$ が成り立つので、
$$
\operatorname{ran}(R)\subseteq \operatorname{ran}(S)
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{dom}(R\cup S)=\operatorname{dom}(R)\cup \operatorname{dom}(S)
$$
が成り立つ。
集合の外延性により、任意の $x$ について
$$
x\in \operatorname{dom}(R\cup S)\ \Leftrightarrow\ x\in \operatorname{dom}(R)\cup \operatorname{dom}(S)
$$
を示せば十分である。
$ $
そこで、$\operatorname{dom}(R\cup S)$ の定義より、
$$
x\in \operatorname{dom}(R\cup S)
\ \Leftrightarrow\
x\in A\land \exists y\in B\ ((x,y)\in R\cup S)
$$
が成り立つ。
さらに、任意の $y\in B$ について、和集合の定義より
$$
(x,y)\in R\cup S
\ \Leftrightarrow\
(x,y)\in R\lor (x,y)\in S
$$
であるから、
$$
x\in \operatorname{dom}(R\cup S)
\ \Leftrightarrow\
x\in A\land \exists y\in B\ ((x,y)\in R\lor (x,y)\in S)
$$
となる。
ここで、存在記号と論理和の性質より、
$$
x\in A\land \exists y\in B\ ((x,y)\in R\lor (x,y)\in S)
$$
は
$$
\bigl(x\in A\land \exists y\in B\ ((x,y)\in R)\bigr)
\lor
\bigl(x\in A\land \exists y\in B\ ((x,y)\in S)\bigr)
$$
と同値である(
証明はコチラ
)。
一方、$\operatorname{dom}(R),\ \operatorname{dom}(S)$ の定義より、
$$
x\in \operatorname{dom}(R)
\ \Leftrightarrow\
x\in A\land \exists y\in B\ ((x,y)\in R)
$$
$$
x\in \operatorname{dom}(S)
\ \Leftrightarrow\
x\in A\land \exists y\in B\ ((x,y)\in S)
$$
であるから、
$$
x\in \operatorname{dom}(R\cup S)
\ \Leftrightarrow\
x\in \operatorname{dom}(R)\lor x\in \operatorname{dom}(S)
$$
が成り立つ。これはすなわち、和集合の定義より
$$
x\in \operatorname{dom}(R\cup S)
\ \Leftrightarrow\
x\in \operatorname{dom}(R)\cup \operatorname{dom}(S)
$$
である。
したがって、任意の $x$ について上の同値が成り立つので、集合の外延性により
$$
\operatorname{dom}(R\cup S)=\operatorname{dom}(R)\cup \operatorname{dom}(S)
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{ran}(R\cup S)=\operatorname{ran}(R)\cup \operatorname{ran}(S)
$$
が成り立つ。
集合の外延性により、任意の $y$ について
$$
y\in \operatorname{ran}(R\cup S)\ \Leftrightarrow\ y\in \operatorname{ran}(R)\cup \operatorname{ran}(S)
$$
を示せば十分である。
$ $
任意に $y$ をとる。まず、$\operatorname{ran}(R\cup S)$ の定義より、
$$
y\in \operatorname{ran}(R\cup S)
\ \Leftrightarrow\
y\in B\land \exists x\in A\ ((x,y)\in R\cup S)
$$
が成り立つ。
さらに、任意の $x\in A$ について、和集合の定義より、
$$
(x,y)\in R\cup S
\ \Leftrightarrow\
(x,y)\in R\lor (x,y)\in S
$$
であるから、
$$
y\in \operatorname{ran}(R\cup S)
\ \Leftrightarrow\
y\in B\land \exists x\in A\ ((x,y)\in R\lor (x,y)\in S)
$$
となる。
ここで、存在記号と論理和の性質より、
$$
y\in B\land \exists x\in A\ ((x,y)\in R\lor (x,y)\in S)
$$
は
$$
\bigl(y\in B\land \exists x\in A\ ((x,y)\in R)\bigr)
\lor
\bigl(y\in B\land \exists x\in A\ ((x,y)\in S)\bigr)
$$
と同値である(
証明はコチラ
)。
一方、$\operatorname{ran}(R),\ \operatorname{ran}(S)$ の定義より、
$$
y\in \operatorname{ran}(R)
\ \Leftrightarrow\
y\in B\land \exists x\in A\ ((x,y)\in R)
$$
$$
y\in \operatorname{ran}(S)
\ \Leftrightarrow\
y\in B\land \exists x\in A\ ((x,y)\in S)
$$
であるから、
$$
y\in \operatorname{ran}(R\cup S)
\ \Leftrightarrow\
y\in \operatorname{ran}(R)\lor y\in \operatorname{ran}(S)
$$
が成り立つ。
これはすなわち、和集合の定義より
$$
y\in \operatorname{ran}(R\cup S)
\ \Leftrightarrow\
y\in \operatorname{ran}(R)\cup \operatorname{ran}(S)
$$
である。
したがって、任意の $y$ について上の同値が成り立つので、集合の外延性により
$$
\operatorname{ran}(R\cup S)=\operatorname{ran}(R)\cup \operatorname{ran}(S)
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{dom}(R\cap S)\subseteq \operatorname{dom}(R)\cap \operatorname{dom}(S)
$$
が成り立つ。
$\operatorname{dom}(R\cap S)\subseteq \operatorname{dom}(R)\cap \operatorname{dom}(S)$ を示す。任意に $x\in \operatorname{dom}(R\cap S)$ をとる。
$\operatorname{dom}(R\cap S)$ の定義より、
$$
x\in A\land \exists y\in B\ ((x,y)\in R\cap S)
$$
が成り立つ。
したがって、ある $y\in B$ が存在して
$$
(x,y)\in R\cap S
$$
が成り立つ。
ここで、共通部分の定義より、
$$
(x,y)\in R\cap S\ \Leftrightarrow\ (x,y)\in R\land (x,y)\in S
$$
であるから、
$$
(x,y)\in R,\ (x,y)\in S
$$
が成り立つ。
よって、$\operatorname{dom}(R)$ の定義より
$$
x\in \operatorname{dom}(R)
$$
が成り立ち、同様に $\operatorname{dom}(S)$ の定義より
$$
x\in \operatorname{dom}(S)
$$
が成り立つ。
したがって、
$$
x\in \operatorname{dom}(R)\cap \operatorname{dom}(S)
$$
である。
以上より、任意の $x\in \operatorname{dom}(R\cap S)$ に対して $x\in \operatorname{dom}(R)\cap \operatorname{dom}(S)$ が成り立つので、
$$
\operatorname{dom}(R\cap S)\subseteq \operatorname{dom}(R)\cap \operatorname{dom}(S)
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{dom}(R)\cap \operatorname{dom}(S) \subseteq \operatorname{dom}(R\cap S)
$$
は成り立たない。集合 $A,B$ を
$$
A=\{1\},\qquad B=\{0,1\}
$$
で定める。
- $A$ から $B$ への二項関係 $R,S\subseteq A\times B$ を
$$ R=\{(1,0)\},\qquad S=\{(1,1)\} $$
で定める。このとき、
$$ \operatorname{dom}(R)=\{1\} $$
であり、
$$ \operatorname{dom}(S)=\{1\} $$
である。したがって、
$$ \operatorname{dom}(R)\cap \operatorname{dom}(S)=\{1\} $$
である。
$ $ - 一方で、
$$ R\cap S=\varnothing $$
である。実際、$R$ に属する順序対は $(1,0)$ のみであり、$S$ に属する順序対は $(1,1)$ のみであるから、両方に属する順序対は存在しない。
したがって、
$$ \operatorname{dom}(R\cap S)=\varnothing $$
である。ゆえに、
$$ \operatorname{dom}(R)\cap \operatorname{dom}(S)=\{1\} $$
であるが、
$$ \operatorname{dom}(R\cap S)=\varnothing $$
である。
-したがって、
$$
\operatorname{dom}(R)\cap \operatorname{dom}(S)\subseteq \operatorname{dom}(R\cap S)
$$
は成り立たない。
$A,B$ を集合とし、$R,S\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{ran}(R\cap S)\subseteq \operatorname{ran}(R)\cap \operatorname{ran}(S)
$$
が成り立つ。
$\operatorname{ran}(R\cap S)\subseteq \operatorname{ran}(R)\cap \operatorname{ran}(S)$ を示す。
任意に $y\in \operatorname{ran}(R\cap S)$ をとる。値域の定義より、
$$
y\in B\land \exists x\in A\ ((x,y)\in R\cap S)
$$
が成り立つ。
したがって、$y\in B$ であり、かつ、ある $x\in A$ が存在して
$$
(x,y)\in R\cap S
$$
が成り立つ。
共通部分の定義より、
$$
(x,y)\in R\cap S
\Longleftrightarrow
(x,y)\in R\land (x,y)\in S
$$
であるから、
$$
(x,y)\in R\land (x,y)\in S
$$
が成り立つ。特に、
$$
(x,y)\in R
$$
である。さらに、$x\in A$ かつ $y\in B$ であるから、値域の定義より、
$$
y\in \operatorname{ran}(R)
$$
である。同様に、
$$
(x,y)\in S
$$
であり、$x\in A$ かつ $y\in B$ であるから、値域の定義より、
$$
y\in \operatorname{ran}(S)
$$
である。したがって、
$$
y\in \operatorname{ran}(R)\cap \operatorname{ran}(S)
$$
である。
ゆえに、任意の $y\in \operatorname{ran}(R\cap S)$ に対して
$$
y\in \operatorname{ran}(R)\cap \operatorname{ran}(S)
$$
が成り立つので、
$$
\operatorname{ran}(R\cap S)\subseteq \operatorname{ran}(R)\cap \operatorname{ran}(S)
$$
である。
$$ \Box$$
一般には、
$$
\operatorname{ran}(R)\cap \operatorname{ran}(S)\subseteq \operatorname{ran}(R\cap S)
$$
は成り立たない。実際、
$$
A=\{1,2\},\qquad B=\{0\}
$$
とし、
$$
R=\{(1,0)\},\qquad S=\{(2,0)\}
$$
と定める。
このとき、
$$
\operatorname{ran}(R)=\{0\}
$$
かつ
$$
\operatorname{ran}(S)=\{0\}
$$
であるから、
$$
\operatorname{ran}(R)\cap \operatorname{ran}(S)=\{0\}
$$
である。
一方、$R$ に属する順序対は $(1,0)$ のみであり、$S$ に属する順序対は $(2,0)$ のみであるから、
両方に属する順序対は存在しない。したがって、
$$
R\cap S=\varnothing
$$
である。よって、
$$
\operatorname{ran}(R\cap S)=\operatorname{ran}(\varnothing)=\varnothing
$$
である。ゆえに、
$$
\operatorname{ran}(R)\cap \operatorname{ran}(S)=\{0\}
$$
であるが、
$$
\operatorname{ran}(R\cap S)=\varnothing
$$
である。したがって、
$$
\operatorname{ran}(R)\cap \operatorname{ran}(S)\subseteq \operatorname{ran}(R\cap S)
$$
は成り立たない。
この記事を高評価した人
この記事に送られたバッジ
投稿者
