二項関係 ①
Def.
$A,B$ を集合とする。
$A$ から $B$ への二項関係とは、$A\times B$ の部分集合 $R$ のことである。すなわち、
$$
R\subseteq A\times B
$$
を満たす集合 $R$ を、$A$ から $B$ への二項関係という。
$A,B$ を集合とし、$R$ を $A$ から $B$ への二項関係とする。このとき、任意の対象 $a,b$ について、
$$
(a,b)\in R\Rightarrow a\in A\land b\in B
$$
が成り立つ。これは、$R\subseteq A\times B$ と直積集合の定義から直ちに従う。
特に、$A$ 上の二項関係とは、$A$ から $A$ への二項関係のことである。
すなわち
$$
R\subseteq A\times A
$$
を満たす集合 $R$ を、$A$ 上の二項関係という。
二項関係は、$2$つの集合の要素同士がどのような条件で結びついているかを数学的に表現したものである。
具体的なイメージを掴むために、いくつかの例を挙げる。
- 大小関係：$A$と$B$を集合
$$ A = \{1, 2\},\ B = \{1, 2, 3\}$$
で定める。このとき、$A$から$B$への直積集合$A\times B$は、考えられるすべてのペアの集合となる。
$$ A\times B = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)\}$$
ここで、「$A$の要素$a$は、$B$の要素$b$より小さい（$a < b$）」という関係を考える。
この条件を満たすペアだけを$A\times B$から選び出し、その部分集合を$R$とする。すなわち、
$$ R = \{(1, 2), (1, 3), (2, 3)\}$$
この$R$は定義通り$A\times B$の部分集合であるため、$A$から$B$への二項関係となる。
$ $ - 整除関係（割り切れる関係）
要素の条件を変えて、「割り切れる」という関係を考える。
$$ A = \{2, 3\},\ B = \{4, 5, 6\}$$
「$a$は$b$を割り切る（$b$は$a$の倍数である）」という条件を満たすペアを集めた集合を$R$とすると、以下のようになる。
$$ R = \{(2, 4), (2, 6), (3, 6)\}$$
これも$A\times B$の部分集合であり、二項関係の具体例である。
$ $ - 関数（写像）
私たちがよく知っている関数や写像も、実は二項関係の特殊な形として捉えることができる。
$$ A = \{1, 2, 3\},\ B = \{2, 3, 4, 5\}$$
ここで、関数$f(x) = x + 1$について、「$b = a + 1$を満たす」という関係$R$を考える。
$$ R = \{(1, 2), (2, 3), (3, 4)\}$$
-このように、二項関係とは「何らかの規則や条件によって結びついた要素のペアの集まり」を一般化した概念といえる。
$A,B$ を集合とし、$R,S\subseteq A\times B$ とする。このとき
$$
R\cup S\subseteq A\times B,\qquad R\cap S\subseteq A\times B,\qquad R\setminus S\subseteq A\times B
$$
が成り立つ(
証明はコチラ
)。したがって、$R\cup S,R\cap S,R\setminus S$ も $A$ から $B$ への二項関係である。
$A,B$ を集合とする。このとき
$$
\varnothing\subseteq A\times B,\qquad A\times B\subseteq A\times B
$$
であるから(
証明はコチラ
)、$\varnothing$ も $A\times B$ も $A$ から $B$ への二項関係である。
- $A,B$ を集合とする。
$A$ から $B$ への空関係とは、空集合 $\varnothing$ のことである。これは
$$ \varnothing\subseteq A\times B $$
を満たすので、$A$ から $B$ への二項関係である。
$ $ - $A,B$ を集合とし、$R\subseteq A\times B$ を $A$ から $B$ への関係とする。このとき、
$$ R=A\times B $$
が成り立つとき、$R$ を $A$ から $B$ への全関係という。
$ $
すなわち、$A$ の任意の元 $a$ と $B$ の任意の元 $b$ に対して、順序対 $(a,b)$ はすべて $R$ に属する。
言い換えれば、$A$ から $B$ へのあり得るすべての組が関係している関係である。
$A,B$ を集合とし、$R\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
$a\in A,\ b\in B$ とする。このとき
$$
(a,b)\in R
$$
が成り立つとき、$a$ は $R$ によって $b$ と関係しているといい、
$$
aRb
$$
と書く。
簡単な例として、集合 $A,B$ を
$$
A=\{1,2,3\},\qquad B=\{x,y\}
$$
とし、関係$R$を
$$
R=\{(1,x),(2,y)\}
$$
で定める。このとき、
$$
(1,x)\in R,\qquad (2,y)\in R
$$
であるから、
$$
1Rx,\qquad 2Ry
$$
と書くことができる。一方で、
$$
(3,x)\notin R
$$
であるから、$3Rx$ は成り立たない。
また、同様に
$$
A=\{1,2\},\qquad B=\{x,y\}
$$
とする。このとき、空関係は
$$
R=\varnothing
$$
である。この場合、$R$ は何も順序対を含まないので、
$$
1Rx,\qquad 1Ry,\qquad 2Rx,\qquad 2Ry
$$
はすべて成り立たない。
$A$上の二項関係の具体例として、
$$
A=\{1,2,3,6\}
$$
とし、$A$ 上の関係 $R$ を
$$
aRb\ \Leftrightarrow\ a\mid b\quad ※\ a\mid b:aはbを割り切る
$$
によって定める。このとき、たとえば
$$
1R2,\qquad 2R6,\qquad 3R6
$$
は成り立つ。実際、対応する順序対は
$$
(1,2),(2,6),(3,6)\in R
$$
である。また、$2$ は $3$ を割り切らないので、
$$
2R3
$$
は成り立たない。
$R\subseteq A\times B$ を二項関係とし、$a\in A,\ b\in B$ とする。このとき
$$
(a,b)\notin R
$$
が成り立つとき、$a$ は $R$ によって $b$ と関係していないといい、
$$
\neg(aRb)
$$
と書く。
$\neg(aRb)$ は、順序対 $(a,b)$ が $R$ に属さないことを表す命題である。
すなわち、
$$
\neg(aRb)\Longleftrightarrow (a,b)\notin R
$$
である。
これは新しい二項関係を定義しているのではなく、命題 $aRb$ を否定しているだけである。
$A$ を集合とする。$A$ 上の恒等関係(等号関係)とは
$$
\Delta_A:=\{(a,a)\mid a\in A\}
$$
で定まる $A$ 上の関係のことである。
集合論の文脈では、このような、各要素が同じ順序対となる
$$
\Delta_A:=\{(a,a)\mid a\in A\}
$$
で定まる $A\times A$ の部分集合のことを対角集合と言う。
$A$ を集合とする。$A$ 上の恒等関係 $\Delta_A$ は、$A$ の元どうしについて等号が成り立つ場合だけを集めた関係である。
すなわち、$a,b\in A$ に対して
$$
a\Delta_A b\Longleftrightarrow a=b
$$
である。したがって、
$$
\Delta_A=\{(a,b)\in A\times A\mid a=b\}
$$
であり、これは
$$
\Delta_A=\{(a,a)\mid a\in A\}
$$
と等しい。
- 例として、
$$ A=\{1,2,3\} $$
とすると、$A$ 上の恒等関係は
$$ \Delta_A=\{(1,1),(2,2),(3,3)\} $$
です。
したがって、
$$ 1\Delta_A1,\qquad 2\Delta_A2,\qquad 3\Delta_A3 $$
は成り立つが、
$$ 1\Delta_A2,\qquad 2\Delta_A3 $$
は成り立たたない。
$ $ - 例として、
$$ A=\{x,y\} $$
のとき、
$$ \Delta_A=\{(x,x),(y,y)\} $$
である。この場合も、$x$ は $x$ と関係し、$y$ は $y$ と関係するが、$x$ と $y$ は関係しない。
$A,B$ を集合とし、$R\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
$R$ の定義域とは、
$$
\operatorname{dom}(R):=\{a\in A\mid \exists b\in B\ ((a,b)\in R)\}
$$
で定まる集合のことである。
$A,B$ を集合とし、$R\subseteq A\times B$ を $A$ から $B$ への二項関係とする。
$R$ の値域とは、
$$
\operatorname{ran}(R):=\{b\in B\mid \exists a\in A\ ((a,b)\in R)\}
$$
で定まる集合のことである。
$A$ を集合とする。このとき定義より
$$
\operatorname{dom}(\Delta_A)=A,\qquad \operatorname{ran}(\Delta_A)=A
$$
が成り立つ。
Prop.&Proof
$A$ を集合とする。このとき
$$
\operatorname{dom}(\Delta_A)=A,\qquad \operatorname{ran}(\Delta_A)=A
$$
が成り立つ。
- まず、
$$ \operatorname{dom}(\Delta_A)=A $$
を示す。
集合の外延性により、任意の $x$ について
$$ x\in\operatorname{dom}(\Delta_A)\Longleftrightarrow x\in A $$
を示せば十分である。
$ $
■ ($\Rightarrow$)を示す。
任意の $x$ をとる。$\Delta_A$ は $A$ 上の恒等関係であるから、
$$ \Delta_A=\{(a,a)\mid a\in A\} $$
である。また、定義域の定義より、
$$ x\in\operatorname{dom}(\Delta_A) \Longleftrightarrow x\in A\land \exists y\in A\ ((x,y)\in\Delta_A) $$
である。
まず、$x\in\operatorname{dom}(\Delta_A)$ とする。このとき上の同値より、特に
$$ x\in A $$
が成り立つ。
$ $
■ ($\Leftarrow$)を示す。
逆に、$x\in A$ とする。このとき $\Delta_A$ の定義より、
$$ (x,x)\in\Delta_A $$
である。さらに $x\in A$ であるから、
$$ \exists y\in A\ ((x,y)\in\Delta_A) $$
が成り立つ(存在導入 証明はコチラ )。したがって、定義域の定義より、
$$ x\in\operatorname{dom}(\Delta_A) $$
が成り立つ。
$ $
以上より、任意の $x$ について
$$ x\in\operatorname{dom}(\Delta_A)\Longleftrightarrow x\in A $$
が成り立つ。ゆえに
$$ \operatorname{dom}(\Delta_A)=A $$
である。
$ $ - 次に、
$$ \operatorname{ran}(\Delta_A)=A $$
を示す。
$ $
■ ($\Rightarrow$)を示す。
集合の外延性により、任意の $y$ について
$$ y\in\operatorname{ran}(\Delta_A)\Longleftrightarrow y\in A $$
を示せば十分である。
任意の $y$ をとる。値域の定義より、
$$ y\in\operatorname{ran}(\Delta_A) \Longleftrightarrow y\in A\land \exists x\in A\ ((x,y)\in\Delta_A) $$
である。
まず、$y\in\operatorname{ran}(\Delta_A)$ とする。このとき上の同値より、特に
$$ y\in A $$
が成り立つ。
$ $
■ ($\Leftarrow$)を示す。
逆に、$y\in A$ とする。このとき $\Delta_A$ の定義より、
$$ (y,y)\in\Delta_A $$
である。さらに $y\in A$ であるから、
$$ \exists x\in A\ ((x,y)\in\Delta_A) $$
が成り立つ(存在導入 証明はコチラ )。したがって、値域の定義より、
$$ y\in\operatorname{ran}(\Delta_A) $$
が成り立つ。
$ $
以上より、任意の $y$ について
$$ y\in\operatorname{ran}(\Delta_A)\Longleftrightarrow y\in A $$
が成り立つ。ゆえに
$$ \operatorname{ran}(\Delta_A)=A $$
である。
-したがって、
$$
\operatorname{dom}(\Delta_A)=A,\qquad \operatorname{ran}(\Delta_A)=A
$$
が成り立つ。
$$ \Box$$
$A,\ B$ を集合とし、$R\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{dom}(R)\subseteq A
$$
が成り立つ。
$\operatorname{dom}(R)\subseteq A$ を示す。
任意に $x\in \operatorname{dom}(R)$ をとる。$\operatorname{dom}(R)$ の定義より、
$$
x\in \operatorname{dom}(R)
\ \Leftrightarrow\
x\in A\land \exists b\in B\ ((x,b)\in R)
$$
である。いま、$x\in \operatorname{dom}(R)$ と仮定しているので、特に
$$
x\in A
$$
が成り立つ。したがって、任意の $x\in \operatorname{dom}(R)$ に対して $x\in A$ が成り立つので、
$$
\operatorname{dom}(R)\subseteq A
$$
である。
$$ \Box$$
$A,B$ を集合とし、$R\subseteq A\times B$ を二項関係とする。このとき
$$
\operatorname{ran}(R)\subseteq B
$$
が成り立つ。
$\operatorname{ran}(R)\subseteq B$ を示す。任意に $y\in \operatorname{ran}(R)$ をとる。
$\operatorname{ran}(R)$ の定義より、
$$
y\in \operatorname{ran}(R)
\ \Leftrightarrow\
y\in B\land \exists a\in A\ ((a,y)\in R)
$$
である。いま $y\in \operatorname{ran}(R)$ と仮定しているので、特に
$$
y\in B
$$
が成り立つ。
したがって、任意の $y\in \operatorname{ran}(R)$ に対して $y\in B$ であるから、
$$
\operatorname{ran}(R)\subseteq B
$$
が成り立つ。
$$ \Box$$
$A,B$ を集合とし、$\varnothing$ を $A$ から $B$ への空関係とする。このとき
$$
\operatorname{dom}(\varnothing)=\varnothing
$$
が成り立つ。
集合の外延性により、任意の $x$ について
$$
x\in \operatorname{dom}(\varnothing)\ \Leftrightarrow\ x\in \varnothing
$$
を示せば十分である。
$ $
任意の $x$ をとる。$\operatorname{dom}(\varnothing)$ の定義より、
$$
x\in \operatorname{dom}(\varnothing)
\ \Leftrightarrow\
x\in A\land \exists b\in B\ ((x,b)\in \varnothing)
$$
が成り立つ。
しかし、空集合の定義より、任意の対象 $y$ について
$$
y\notin \varnothing
$$
であるから、任意の $b\in B$ に対して
$$
(x,b)\notin \varnothing
$$
である。したがって、
$$
\exists b\in B\ ((x,b)\in \varnothing)
$$
は偽である。ゆえに連言も偽となり
$$
x\in \operatorname{dom}(\varnothing)
$$
は偽である。一方、空集合の定義より
$$
x\in \varnothing
$$
も偽である。したがって
$$
x\in \operatorname{dom}(\varnothing)\ \Leftrightarrow\ x\in \varnothing
$$
が成り立つ。ゆえに
$$
\operatorname{dom}(\varnothing)=\varnothing
$$
である。
$$ \Box$$
$A,B$ を集合とし、$\varnothing$ を $A$ から $B$ への空関係とする。このとき
$$
\operatorname{ran}(\varnothing)=\varnothing
$$
が成り立つ。
集合の外延性により、任意の $y$ について
$$
y\in \operatorname{ran}(\varnothing)\ \Leftrightarrow\ y\in \varnothing
$$
を示せば十分である。
$ $
任意の $y$ をとる。$\operatorname{ran}(\varnothing)$ の定義より、
$$
y\in \operatorname{ran}(\varnothing)
\ \Leftrightarrow\
y\in B\land \exists a\in A\ ((a,y)\in \varnothing)
$$
が成り立つ。しかし、空集合の定義より、任意の対象 $z$ について
$$
z\notin \varnothing
$$
であるから、任意の $a\in A$ に対して
$$
(a,y)\notin \varnothing
$$
である。
したがって、
$$
\exists a\in A\ ((a,y)\in \varnothing)
$$
は偽である。ゆえに連言も偽となり
$$
y\in \operatorname{ran}(\varnothing)
$$
は偽である。
一方、空集合の定義より
$$
y\in \varnothing
$$
も偽である。したがって
$$
y\in \operatorname{ran}(\varnothing)\ \Leftrightarrow\ y\in \varnothing
$$
が成り立つ。
ゆえに
$$
\operatorname{ran}(\varnothing)=\varnothing
$$
である。
$$ \Box$$
この記事を高評価した人
この記事に送られたバッジ
投稿者
