2001年度情報数学

Ver.２
1
このように “,” で区切って書くとき
には「かつ」(and)の意味になる。
関係 (relation)
集合Ａの要素aとＢの要素bとが、ある条件Ｒを満た
すとき「Ｒの関係にある」といい、aRb と書く。
 Ｒの関係にある要素の対<a,b>の全体は直積ＡＸＢ
の部分集合  a, b a  A, b  B, aRb と同一視できる。
 例：二つの実数の関係  は，集合
 x, y x  R, y  R, x  y のことである。

y
別の例：
グー
x
パー
チョキ
2
n項関係


x と y が関係 R を満たす、つまり x, y  R のとき、
良く x R y と書く (infix notation)。これは二項関係。
集合ＡからＢへの関数 f (写像) のグラフは、直積
A B の部分集合であり、一つの二項関係である。
Ａの要素aの関数 f による像 f(a)は f (a)  1, a  A.
A と A の間の関係を A 上の関係ともいう。
 前出の例題「ジャンケンの関係」
 3 項以上の関係もある。
 例: a氏がb氏にcというメールを出した <a,b,c>
 例: 夫aと妻bには子供cがいる<a,b,c>

3
二項関係の性質

∀x すべてのx
二項関係 R  A A においては、次の性質が基本的
 反射律 x  A ( x R x)
 推移律 x  A y  A z  A ( x R y  y R z  x R z )
 対称律 x  A y  A ( x R y  y R x)
 反対称律 x  A y  A ( x R y  y R x  x  y )

関係Ｒが反射律を満たすとき、Ｒは反射的という。

例：Ｎ上の大小関係  は反射的、推移的、反対称的
平面上の二直線の平行関係は反射的、推移的、対称的
4
同値関係 (equivalence relation)
反射的、推移的、対称的な関係を同値関係という
 例：平面上の直線の間の「平行関係」
二つの三角形が「合同である」「相似である」
 例：自然数 m, 整数 x, y に対して

def
x  m y  m | ( x  y)

x と y は m を法として合同
例：関数 f : A  B が与えられた時 a, b  A に対
def
して a ~ b  f (a)  f (b)
 例：自然数の上の等号（＝）
＊直和分割：集合A を、互いに交わらない（空で
ない）集合の和集合として表すことができる意味。
同値類

5
集合 A 上の同値関係 R とが与えられたとき

R[ x]   y x R y （x の属する同値類）
def
x と R の関係にある y の集合
 x を代表元という

集合 A の任意の同値関係 R に対して、
R の定める同値類の全体の集合は A の直和分割＊。
逆に A の任意の直和分割は A のある同値関係の
定める同値類の全体の集合に一致する。
6
商集合

A/ R
A の R による分割，商集合
A / R   R[ x] x  A
def
例：３を法として合同な整数
の集合 Z の商集合 Z / 3
は {[0], [1], [2]}

集合Aから、AのRによる商集合 A/ R への写像f
を f (a)  R [a] により定義すると、この f は全射。
AからA / R への標準的な(canonicalな)全射という.。
7
関係の合成

集合 A 上の関係の合成（積ともいう）
R1  R2  { x, z

|
y  A ( x, y  R1  y, z  R2 )}
合成の繰返しをベキ乗として定義する

R  { x, x x  A} （idA : A上の恒等関係）

Rn1  R  Rn (n  N)
0
8
関係の閉包

推移的閉包 (reflexive closure)


R  R
n
n 1

反射推移的閉包 (reflexive transitive closure)

R  R ,
*
n
R
0
R


n 0

推移的閉包は推移的である。
反射推移的閉包は反射的かつ推移的である。

性質：Rが推移的であれば、R+=Rである。
このa, b, c, dは
注釈であり、行列
の一部ではない
関係と隣接行列
有向グラフ (directed graph)
a
d

a
c
d
1 0 0


b 0 1 1 0
A A


R
({0,1} )
c 0 0 0 1
b
a 0
b

d 0
c

0 0 0
関係の合成は行列の積の０でない成分に対応
0

0
0

0
9
1 0 0

1 1 0

0 0 1

0 0 0
0

0
0

0
1 0 0 0
 
1 1 0 0

0 0 1 0
 
0 0 0 0
1 1 0

1 1 1
 R2
0 0 0

0 0 0
次回の予告
10
Googleのページランク

基本的な仕組は数学的
グラフの行列による表現
隣接行列（推移行列、遷移行列）
固有値と固有ベクトル
S学部
W大学
C学科
G研究室
WEBページのリンクの関係
W
W 0

S 0
C 0

G  1
S C G
1 0 0

0 1 0
0 0 1

1 1 0 
 1 頂点iから頂点 jに辺がある
aij  
０頂点iから頂点 jに辺がない
行列の上と左のW, S, C, Gは注釈
であり行列に含まれない
11
隣接行列と閉包

隣接行列の定義
1
if
a
Ra

i
j

rij  
0
if
a
R

a

i
j


Rを否定している斜線
隣接行列の性質
 行列Rnの(i,j)成分は、aiからajに至る長さnの相異
なる道の数。（道のことを経路ともいう）
 行列R*の(i,j)成分が０でないとき、 aiからajに至
る道がある。到達可能。（長さ０の道もあり）
12
二項関係と順序 ()
次の三つの性質を満たす二項関係  を半順序
(partial order) という。半順序集合を posetという。
x ( x  x )
 反射律
xyz ( x  y  y  z  x  z )
 推移律
xy ( x  y  y  x  x  y)
 反対称律
 さらに次の性質も満たすとき全順序 (total order) と
いう。全順序を線形順序 (linear order) ともいう。


xy ( x  y  y  x )
論理記号 or

単に順序という場合には半順序のことを指す。
順序集合
 A,  
13
N, Z, R：数の大小関係  これは自明な順序。
 複素数の集合 C：ここには自明な順序がない。
 文字 (a～z, A～Z)の集合：それほど自明でない。
 単語（文字列）：自明でない。
 学校の成績：いろいろな計算法があり自明でない。
 {red, green, blue} : 関係の定義が必要。
 部分集合の間の順序：包含関係⊂は順序である。
 {{ }, {red}, {green}, {blue}, {red,green}, {red,blue},
{green,blue}, {red,green,blue}}
 C や学校の成績にも特定の要素間には順序あり。

14
順序集合（部分集合、直積）

集合 A とその上の半順序  の組 < A,  > のこと。
 A の上の順序  が明示されていたり、自明な
場合には、単に A と書く。

例：集合 A に対して (2A, ) は順序集合。

例：順序集合の直積を順序集合にする方法は複数
通り考えられる
 直積順序： x, x'  *  y, y'   x  A y  x'  B y'
 辞書式順序：lexicographic order
 x, x'  l  y, y'   x  A y 
( x  A y  x'  B y ' )
15
順序集合（N, 関数）

N の自明な順序ではない順序がある。
 例：m | n （m は n の約数という二項関係）
これは順序である。ただし全順序ではない
［演習のヒント］反射的、推移的、反対称的。

Bが順序集合のとき、関数 f , g  A  B の間の順序
を B 上の順序を使って定義できる。
f  g  x ( f ( x)  B g ( x))
16
狭義の順序

狭義の順序を、以下の二つの性質を満たす関係と
して定義する。
 推移的： xyz ( x  y  y  z  x  z )
 非反射的： x ( ( x  x ))
否定 not

演習：Rを狭義の順序とする。二項関係R*を次のよ
うに定義すると、R*は順序になる。
xR * y  xRy  x  y
（詳しい説明は省略）
17
ハッセ (Hasse) の図式
 Aの各要素a,
bに対して平面上の点Pa , Pb
をとる。a<b の時、PbをPaよりもY座標
を大きな位置に描く。
が a の直後の要素であるとき、PaとPb
とを線分で結ぶ。この線分上にはPa , Pb
以外の点は描かない。
b
18
直前の要素、直後の要素

順序集合 (A, ) において xA が aA の直後の要素
(successor) であるとは、次の性質を満たすこと。
a  x  ( a  z  x  z  x)

同様に、直前の要素 (predecessor) を定義できる。
x  a  ( x  z  a  z  x)
 例：n ( N, n  0) の直前の要素は n  1
 例： a (Q) の直前の要素は存在しない。
順序集合(A, )が稠密（ちゅうみつ）であるとは、
任意のa, bAに対してa<bならば必ずa<c<bとな
る c が存在することである。Qは稠密。
19
ハッセ (Hasse) の図式の例
全順序
比較不能
{red,green,blue}
{red,green}
{red}
{green,blue}
{green}
{}
{red,blue}
{blue}
20
擬順序 (quasi-order, preorder)
Jane(100)
Smith(92)
Mary(85)
Tom(85)
Pat(80)
別の例：
 x, y    u , v 

x  y  u v
2
2
2
Bob(77)


反射律と推移律を満たす関係（反対称律は満たさ
なくてよい）を擬順序という。
x ~ y  x  y  y  x で定義される関係 ~ は同
値関係になる。商集合 A/~ の上の二項関係  *
[a]  *[b]  a ~ b は順序になる。
2
21
最大と極大
順序集合 (A, ) と、その部分集合Bがある。Bの要
素 b が次の性質を満たすとき、bをBの最大元とい
う。 ∀x∈B ( x  b )
maximum
 Bの要素 b が次の性質を満たすとき、bをBの極大
元という。 ∀x∈B ( b  x ⇒ x=b )
maximal

x
z
y
極大元（２つある）
w
u 最小元＝極小元
最大元が存在すれば、それが極大元。最大元は存在すれば一つ。
極大元は複数個が存在することがある。

Download Report