next up previous
Next: About this document ...

    

論理と集合要約 No.15

第15回目の主題 : 復習と補足。

◎ 同値関係

◯「関係」

定義 15.1   集合 $ S$ の上の二項関係とは、 $ S \times S$ の部分集合 $ \mathcal R$ の ことである。 $ x,y \in S$ にたいして、 $ (x,y)\in \mathcal R$ のとき $ x \underset{\mathcal R}{\sim} y$ と書いたりする。

   関係\begin{displaymath}
\begin{cases}
\text{2項関係} &
\begin{cases}
\text{大...
...\end{cases} \\
\text{3項関係 } & \\
\text{etc}
\end{cases}\end{displaymath}

◯ クラス分け(分類)をするのに用いられる関係:同値関係

* クラス分けがうまくできるためには守らなければならないルールがある。

それが、推移律、反射律、対称律。

◯ 問題を2つに分ける

  1. $ \sim $ は 同値関係か?
  2. $ \sim $ によるクラス分けを行え。

◯ 同値関係による等化写像。

集合 $ X$ に同値関係 $ \sim $ が定まると、 「等化写像」(「自然な射影」)

$\displaystyle X \to X /\sim
$

が、各 $ x \in X$ に対して $ x$ の クラスを対応させることで定まる。

◎ 部分集合全体の集合。 $ X$ の部分集合 $ S$ は、$ X$ 上の $ \{0,1\}$ のみに値をとる関数

\begin{displaymath}
\chi_S(x)=
\begin{cases}
1 & \text{$x \in X$ のとき} \\
0 & \text{$x \notin X$ のとき} \\
\end{cases}\end{displaymath}

と一対一に対応する。

ところで:

定義 15.2   $ X$ から $ Y$ への写像の全体のなす集合を $ Y^X$ と書き表す。

この定義に従うと、$ X$ の部分集合の全体は $ \{0,1\}^X$ の元と一対一に対応する ということになる。そこで:

定義 15.3   $ X$ の部分集合の全体のなす集合を $ 2^X$ と書き表す。

定理 15.4   $ X$ から $ 2^X$ への全射は存在しない。

とくに、 例えば $ {\mbox{${\mathbb{Z}}$}}$ の部分集合の全部を書きたいとき、 $ S_1,S_2,\dots,$ と 添え字をつけていたのでは、添字が足りなくなる。そこで 添字集合が必要にな。



docky 2016-07-21