離散数学及び演習 講義52 項関係（復習）

離散数学及び演習講義 5 2014. 5.15（木）集合 A から集合 B への 2 項関係 R
R ⊆ A×B

例： A＝{ 1，2，3，4 } ， B＝{ a，b，c，d，e }R＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }
B
⊆ A×B
A
R
1a関数
（教科書 pp.3-5，26-28）
教科書･･･野崎昭弘：離散系の数学、近代科学社

2b3c4

de2関数（function）
関数（続き）集合 A から集合 B への関数（写像（mapping）） ff ⊆A×B， かつ，任意の x∈A に対して，y∈B が唯一存在して，（x，y）∈f である．

例： A＝{ a，b，c }，B＝{ 1，2，3，4 }f ＝{（a，1），（b，2），（c，2）} ⊆ A×B
A


関数 f ⊆A×B… f：A→B関数 f ： A → Bf ⊆A×B， かつ，任意の x∈A に対して，y∈B が唯一存在して，（x，y）∈f である．

例： A＝{ a，b，c }，B＝{ 1，2，3，4 }R ＝{（a，1），（b，2）} ⊆ A×B
faBA
12bc∈A に対して，（c，y）∈R となるy∈B が存在しないので，R は関数ではない．

34cR

a12bc？

3関数（続き３）関数 f ： A → B
（x，y）∈f ， x f y 関数 f ： A → A
f ⊆A×B， かつ，任意の x∈A に対して，y∈B が唯一存在して，（x，y）∈f である．

例： A＝{ a，b，c }，B＝{ 1，2，3，4 }S ＝{（a，1），（b，3），（b，2），（c，3）} ⊆ A×B
A
b∈A に対して，（b，y）∈S となるy∈B は唯一でないので，S は関数ではない．

344関数（続き２）BabcS

A＝{ a1，…，an }， f ： A → B
B
12… y ＝ f（x）
… 集合 A 上の関数

f＝a 1 … anf （a1） … f （an）

例： f ＝{（a，1），（b，2），（c，2）}＝a b c1 2 234561

離散数学及び演習 講義5

n 変数関数（n-ary function）
関数 f ： A → B に対して，
 f による a∈A の 像（image）（値（value））

集合 A1，…， An から集合 B への n 変数関数


像，逆像

f ⊆ A1×…× An×B，かつ，任意の（x1，…，xn）∈A1×…× An 対して，y∈B が唯一存在して，（ x1，…，xn，y）∈f である．
… f ： A1 ×…× An → B（ x1，…，xn，y）∈f ， y ＝ f（（x1，…，xn））… y ＝ f（ x1，…，xn ）X af（a）

f（X）

b ＝ f（a） であるような a∈AA

f（X）＝{ f （x）｜x ∈ X } （⊆B）

f×f による Y⊆B の 逆像（原像）
B
××f による X⊆A の 像
fAf による b∈B の 逆像（原像）（inverse image） … f－1（b）
f（a）
a … f の引数（argument）

f －1（Y）＝{ x｜ f （x） ∈ Y } （⊆A）

f －1（b）

B×b

Y

f －1（Y）
78定理

証明
集合 X⊆A， Y⊆B と関数 f ：A→B に対して，（1） X ⊆f －1（ f （X）），
f （ f －1（Y））⊆Y

集合 X，X1，X2⊆A， Y，Y1，Y2 ⊆B と関数 f ：A→B に対して，次の（1）～（5）が成り立つ．
（1） X ⊆f －1（ f （X）），
f （ f －1（Y））⊆Y（2） X1⊆X2 ならば， f （X1）⊆ f （X2） ，Y1⊆Y2 ならば， f －1（Y1）⊆ f －1（Y2）（3） f （X1∪X2）＝ f （X1）∪f （X2） ，f －1（Y1∪Y2）＝ f －1（Y1）∪f －1（Y2）（4） f （X1∩X2）⊆f （X1）∩f （X2） ，f －1（Y1∩Y2）＝ f －1（Y1）∩f －1（Y2）（5） f （X1）－ f （X2） ⊆ f （X1－X2） ，f －1（Y1－Y2）＝f －1（Y1）－ f －1（Y2）「任意の x∈X に対して，x∈ f －1（ f （X））」を示す．
「任意の y∈ f （ f －1（Y）） に対して，y∈Y」を示す．

任意の x∈X に対して， f（x）∈f（X）．
ゆえに，x∈f－1（f（X））だから， X⊆f －1（ f （X））．
f－1（f（X））＝ { x｜ f （x） ∈ f（X） }一方，任意の y∈ f （ f －1（Y）） に対して，x∈f －1（Y）が存在して，y＝f（x）．
x∈f －1（Y） だから， f（x）∈Y．すなわち， y∈Y．
f－1（Y）＝ { x｜ f （x） ∈ Y }ゆえに， f （ f －1（Y））⊆Y．
910

証明（続き）

証明（続き２）

集合Y1，Y2 ⊆B と関数 f ：A→B に対して，（3） f －1（Y1∪Y2）＝ f －1（Y1）∪f －1（Y2）

集合Y1，Y2 ⊆B と関数 f ：A→B に対して，（3） f －1（Y1∪Y2）＝ f －1（Y1）∪f －1（Y2）a） 「f －1（Y1∪Y2）⊆ f －1（Y1）∪f －1（Y2）」とb） 「f －1（Y1）∪f －1（Y2） ⊆ f －1（Y1∪Y2）」の両方を示す．
a） 「任意の x∈f －1（Y1∪Y2）に対して，x∈f －1（Y1）∪f －1（Y2）」を示す．

b）任意の x∈f －1（Y1）∪f －1（Y2）に対して， x∈f －1（Y1）または
x∈f －1（Y2）．
ゆえに， f（x）∈Y1 または f（x）∈Y2 だから， f（x）∈Y1∪Y2 ．

a）任意の x∈f －1（Y1∪Y2）に対して，f（x）∈Y1∪Y2 だから，f（x）∈Y1 または f（x）∈Y2 ．
f－1（Y1∪Y2）＝ { x｜ f （x） ∈Y1∪Y2 }ゆえに，x∈f －1（Y1）または x∈f －1（Y2）だから，
x∈f －1（Y1）∪f －1（Y2）．
a） 「f －1（Y1∪Y2）⊆ f －1（Y1）∪f －1（Y2）」とb） 「f －1（Y1）∪f －1（Y2） ⊆ f －1（Y1∪Y2）」の両方を示す．
b） 「任意の x∈f －1（Y1）∪f －1（Y2）に対して，x∈ f －1（Y1∪Y2）」を示す．

f－1（Y1）＝ { x｜ f （x） ∈ Y1 } ，f－1（Y2）＝ { x｜ f （x） ∈ Y2 }このとき， x∈f －1（Y1∪Y2）．
f－1（Y1）＝ { x｜ f （x） ∈ Y1 } ，f－1（Y2）＝ { x｜ f （x） ∈ Y2 }f－1（Y1∪Y2）＝ { x｜ f （x） ∈ Y1∪Y2 }したがって， f －1（Y1）∪f －1（Y2） ⊆ f －1（Y1∪Y2）．
a），b）から，f －1（Y1∪Y2）＝ f －1（Y1）∪f －1（Y2）．

したがって， f －1（Y1∪Y2）⊆ f －1（Y1）∪f －1（Y2）．

11122

離散数学及び演習 講義5

全射（surjection）

関数の定義域，値域
関数 f ： A → Bに対して，
 f の定義域（domain）
 dom（f ）＝{ x∈A｜ある y∈B に対して， y＝ f（x）}
 f の値域（range）
 range（f ）＝{ y∈B｜ある x∈A に対して，y＝ f（x）}（ ＝{ f（x）｜ x∈A }＝ f（A） ）AB例：fa1 range（f ）
2dom（f ） b3c4



関数 f ：A → B は全射である（上への関数（onto function）である）


任意の y∈B に対して，ある x∈A が存在して，y＝ f（x）．

例： A＝{ a，b，c，d }，B＝{ 1，2，3 }f ＝{（a，1），（b，3），（c，2），（d，3）}AB
fa1b2c3d13

14

単射（injection）
全単射（bijection）

関数 f ：A → B は単射である（１対１関数（one-to-one function）である）




任意の x1，x2∈A に対して， x1≠x2 ならば f（x1）≠ f（x2）．
関数 f ：A → B は全単射である
f は全射かつ単射である

例： A＝{ a，b，c，d }，B＝{ 1，2，3，4 }f ＝{（a，1），（b，3），（c，2），（d，4）}

任意の x1，x2∈A に対して， f（x1）＝ f（x2） ならば x1＝x2 ．

例： A＝{ a，b，c }，B＝{ 1，2，3，4 }f ＝{（a，1），（b，3），（c，2）}
ABfa1AfBa1b2b2c3c34d4

15

16

全射，単射，全単射（続き）
R … すべての実数からなる集合
例１： f ： R → R， f（x）＝2x

f は全単射である．

f は単射であるが，全射ではない．

f（x）＝x2

例３： f ： R → R， f（x）＝x2


f（x）＝2x

例２： f ： R → R， f（x）＝2x

f（x）＝ 2x全射，単射，全単射（続き２）f は単射でないが，全射である．

Af は単射でなく，全射でもない．

例４： f ： R → R， f（x）＝x3－2x

例： 集合 AS⊆A，｜A｜ 3， S≠φ， A－S≠φ
f ： A → { 0，1 }，f（x）＝ 1 （x∈S）
0 （xS）

Sf（x）＝x3－2x××

f は単射でないが，全射である．

17f××01183

離散数学及び演習 講義5置換（permutation）


恒等関数（identity function）

有限集合 A 上の置換


A 上の全単射



例： A＝{1，2，3}


f 1＝132
1，32

f2＝1223

任意の x∈A に対して， IA（x）＝x．

例： A＝{1，2，3}
 IA ＝
1 23
11｜A｜＝ n ならば，A 上の置換は n! 個ある．
集合 A 上の恒等関数 IA

A 上の置換の個数は A 上の順列の個数に等しい．

233

有限集合 A 上の恒等関数 IA は A 上の置換である．

1920関数の合成（composition）
定理

関数 f ：A→B と関数 g： B→C の合成関数 g・f ：A→C


関数 f ： A→B， g： B→C，h： C→D に対して，（ h ・ g ）・ f ＝ h ・（ g ・ f ）任意の x∈A に対して，（g・f ）（x）＝g（ f（x））（関数の合成に関する結合則）が成り立つ．
ABfyC
gxz
g・f2122定理

証明
関数 f ：A→B， g： B→C に対して，（1） f，g がともに全射であるならば， g・f も全射である．

関数 f ：A→B， g： B→C に対して，次の（1）～（4）が成り立つ．
（1） f，g がともに全射であるならば， g・f も全射である．
（2） f，g がともに単射であるならば， g・f も単射である．
（3） g・f が全射であるならば， g も全射である．
（4） g・f が単射であるならば， f も単射である．
ABfyx




g・f ：A→C「任意の z∈C に対して，ある x∈A が存在して，z＝ （g・f ）（x）」を示す．

g は全射だから，任意の z∈C に対して，ある y∈B が存在して，g（y）＝z．
また，f は全射だから，任意の u∈B に対して，ある x∈A が存在して， f（x）＝u．
特に，y∈B に対して，ある x∈A が存在して，f（x）＝y．
すなわち，任意の z∈C に対して，ある x∈A が存在して，（g ・ f ）（x）＝g（f（x））＝z だから，g・f は全射である．

Cgzg・f23244離散数学及び演習 講義5証明（続き）

定理

関数 f ：A→B， g： B→C に対して，（2） f，g がともに単射であるならば， g・f も単射である．


関数 f ：A→B が全単射であるとき，かつそのときに限り，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x）である．

g・f ：A→C「任意の x1，x2∈A に対して，（g・f ）（x1）＝ （g・f ）（x2） ならば x1＝x2 」 を示す．

任意の x1，x2∈A に対して，（g・f ）（x1）＝（g・f ）（x2）とする．
このとき，g（f（x1））＝g（f（x2））．
g は単射だから，f（x1）＝f（x2）．
さらに，f は単射だから，x1＝x2．
したがって, g・f は単射である．

Ax×f×By×××××2526

証明

証明（続き）

関数 f ：A→B が全単射であるとき，かつそのときに限り，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x）である．


関数 f ：A→B が全単射であるとき，かつそのときに限り，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x）である．

a）「 f が全単射であるならば，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x） 」とb） 「任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x） ならば，f は全単射である」の両方を示す．
 a-1）「 f は全単射である」を仮定して，「任意の y∈B に対して，ある x∈A が存在して，y＝f（x） 」を示す．
 a-2）「任意のy∈Bに対して，y＝f（x）となる x∈Aは唯一である」を示す．
a）「 f が全単射であるならば，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x） 」を示す．
 a-2） 「 f は全単射である」を仮定して，「任意のy∈Bに対して，y＝f（x）となる x∈Aは唯一である」を示す．
「任意のy∈Bに対して，y＝f（x）となる x∈Aは2つ存在する」を仮定して，矛盾を導く．

a） f は全単射であると仮定する．
a-2）任意の y∈B に対して，y＝f（x1）かつ y＝f（x2） （x1≠x2）と仮定する．
ところが，f は単射だから， f（x1）≠f（x2）．
これは，y＝f（x1）＝f（x2）に矛盾する．
ゆえに，任意のy∈Bに対して，y＝f（x）となる x∈Aは唯一である．

「任意のy∈Bに対して，y＝f（x）となる x∈Aは2つ存在する」を仮定して，矛盾を導く．

a） f は全単射であると仮定する．
a-1） f は全射だから，任意の y∈B に対して，ある x∈A が存在して，y＝f（x）．
2728

証明（続き２）定理

関数 f ：A→B が全単射であるとき，かつそのときに限り，任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x）である．
関数 f ：A→B が全単射であるとき，かつそのときに限り，g・f ＝ IA かつ f・g ＝ IBを満たす関数 g： B→A は唯一存在する．

b） 「任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x） ならば，f は全単射である」を示す．
 b-1）「f は全射である」と
 b-2）「f は単射である」を示す．
 b-1）「任意の y∈B に対して，ある x∈A が存在して，y＝f（x）」を示す．
 b-2）「任意の x1，x2∈A に対して，f（x1）＝ f（x2）ならば x1＝x2 」を示す．

ABfb） 任意の y∈B に対して，ある x∈A が唯一存在して，y＝f（x） と仮定する．
b-1）このとき，明らかに f は全射である．
b-2）任意の x1，x2∈A に対して，f（x1）＝ f（x2）＝y とする．
このとき，y∈B に対して， y＝f（x） となる x∈A は唯一存在するから，
x1＝x2．ゆえに， f は単射である．
a），b）から， f は全単射である．

xyg

2930

5

離散数学及び演習 講義5逆関数（inverse function）


証明

関数 g ：B→A は関数 f ：A→B の逆関数である

関数 f ：A→B が全単射であるとき，かつそのときに限り，g・f ＝ IA かつ f・g ＝ IB を満たす関数 g： B→Aは唯一存在する．

g・f ＝ IA かつ f・g ＝ IB

f －1： B→A

f ： A→B の逆関数 …
x∈A，y∈Bに対して， f －1（y）＝x iff f（x）＝y

逆関数は逆関係である．
 関数 f の逆関係 f －1は，一般には関数ではない．
a） 「 f が全単射であるならば，g・f ＝ IA かつ f・g＝ IB を満たす
g：B→A が唯一存在する」とb） 「 g・f ＝ IA かつ f・g ＝ IB を満たす関数 g：B→A が唯一存在するならば，f は全単射である」の両方を示す．
 a-1）「 f は全単射である」を仮定して，「g・f ＝ IA かつ f・g＝ IB を満たす g が存在する」を示す．
 a-2）「g・f ＝ IA かつ f・g＝ IB を満たす g は唯一である」を示す．

f が全単射であるとき，かつそのときに限り，逆関係 f －1はf の唯一の逆関数である．
3132

証明（続き）

証明（続き２）a） 「f が全単射であるならば，g・f ＝ IA かつ f・g ＝ IB を満たす g は唯一存在する」を示す．
 a-1）「 f は全単射である」を仮定して，「g・f ＝ IA かつ f・g ＝ IB を満たす g が存在する」を示す．
 a-2）「g・f ＝ IA かつ f・g ＝ IB を満たす g は唯一である」を示す．
 「g・f ＝ IA かつ f・g ＝ IB を満たす g は2つある」と仮定して，矛盾を導く．

a） 「f が全単射であるならば，g・f ＝ IA かつ f・g ＝ IB を満たす g は唯一存在する」を示す．
 a-1）「 f は全単射である」を仮定して，「g・f ＝ IA かつ f・g ＝ IB を満たす g が存在する」を示す．
 a-2）「g・f ＝ IA かつ f・g ＝ IB を満たす g は唯一である」を示す．
a） f は全単射であると仮定する．
a-1） このとき，任意の y∈B に対して，x∈A が唯一存在して，y＝f （x）．
そこで，関数 g ：B→A を g（y）＝x と定義する．
このとき， （f・g）（y）＝f（g（y））＝f（x）＝y だから， f・g ＝ＩB．
また，任意の x∈A に対して，y＝f（x）とおくと，（g・f ）（x）＝g（f （x））＝g（y）＝x だから， g・f ＝ＩA．

a） f は全単射であると仮定する．
a-2） g1・f ＝ IA かつ f・g1 ＝ IB， g2・f ＝ IA かつ f・g2 ＝ IB とする．
任意の y∈B に対して，
y＝ IB（y）＝（f・g1）（y）＝ f（g1（y）），
y＝ IB（y）＝（f・g2）（y）＝ f（g2（y））．
ゆえに， f（g1（y））＝ f（g2（y））．
f は単射だから，g1（y）＝ g2（y）．ゆえに，g1＝ g2．
すなわち， g・f ＝ IA かつ f・g ＝ IB を満たす g は唯一である．
3334

証明（続き３）定理b） 「 g・f ＝ IA かつ f・g ＝ IB を満たす関数 g：B→A が唯一存在するならば，f は全単射である」を示す．
 「 g・f ＝ IA かつ f・g ＝ IB を満たす関数 g が唯一存在する」を仮定して，「f は全単射である」を示す．
 b-1）「任意の y∈B に対して，ある x∈A が存在して，y＝f（x）」を示す．
 b-2）「任意の x1，x2∈A に対して， f（x1）＝ f（x2）ならば x1＝x2 」を示す．

関数 f ：A→B に対して，次の（1），（2）が成り立つ．
（1） f が単射であるならば， 逆関係 f －1は f（A）からA への逆関数であり，しかも単射である．
（2） f が全単射であるならば，逆関係 f －1は B からA への逆関数であり，しかも全単射である．

b） g・f ＝ IA かつ f・g ＝ IB を満たす関数 g が唯一存在すると仮定する．
b-1）このとき，任意の y∈B に対して， f （g（y））＝（f・g）（y）＝ IB（y）＝y．
g（y）＝x とおくと，y＝f （x）であり，x∈A．
ゆえに， f は全射である．
b-2）任意の x1，x2∈A に対して， f（x1）＝ f（x2）と仮定する．
ところで， x1＝ IA （x1）＝（g・f ）（x1）＝ g（f （x1）），
x2＝ IA （x2）＝（g・f ）（x2）＝ g（f （x2））
g（f （x1））＝ g（f （x2））だから， x1＝x2 ．
ゆえに，f は単射である．

AfB
f（A）

35

AfB
f（A）

36

6

離散数学及び演習 講義5定理

定理

全単射 f ：A→B， g： B→C に対して，（ g・f ）－1 ＝ f －1・g－1

有限集合 A から有限集合 B への全単射が存在するならば，｜A｜＝｜B｜．

が成り立つ．

AfB

a1

b2

c3

d4

3738

定理

関数の集合

有限集合 A 上の関数 f について，次の（1）～（3）は集合 A， B に対して，
 BA ＝ { f ｜f ：A → B }同値である．
（1） f は全射である．
（2） f は単射である．
（3） f は全単射である．
Af



Aaabbccdd

集合 A から集合 B へのすべての関数からなる集合（集合 A から集合 B への配置集合）

有限集合 A， B に対して，｜BA｜＝ ｜B｜｜A｜

3940

特性関数（characteristic function）
A

BA ＝ { f ｜f ：A → B }２ ＝ { 0，1} とおくと，
２A ＝ { f ｜f ： A → { 0，1} } S ＝{x∈A｜f（x）＝1} とおくと，x∈S⊆A iff f（x）＝1







S

f××××まとめ２0

今回の講義



今回の演習



次回の演習（5／22 1・2限）


f が決まれば S も決まる．逆に， S が決まれば f も決まる．
f と S を同一視することができる．



２A ＝ { S｜S ⊆ A }＝ P（A）

f ：A → { 0，1 }f ：A → [ 0，1 ]

試験範囲： 講義1～5（集合論）
持込み不可
教室： 演習時と同じ ，1人ずつ空けて着席すること
演習問題解答例（pdf 版）
… 集合 S の特性関数（characteristic function）… 集合 S の所属関数（membership function）
ファジー（fuzzy）集合（１限）束（２限）関数
解答用紙は提出不要

中間試験（ 5／29 1限）



半順序1

関数

次回の講義（5／29 2限）


41

http://www.kl.i.is.nagoya-u.ac.jp/~toyama/lecture/risan14/

約数・倍数（教科書 pp.101-106, 113-116）
427