
スポンサードリンク
こんにちは、ももやまです。
"関係" というのは、日常生活にもなじみのある概念ですが、離散数学で出てくる関係である "二項関係" について習うと、「なんやねんこれ」と思う人も多いと、思います。
そこで今回は、離散数学の世界で出てくる二項関係について、分かりやすく復習をしていきましょう。
目次 [hide]
スポンサードリンク
1. 動画での解説はこちら!
本記事の内容は、動画でも解説しております。動画でご覧いただきたい方は、以下の動画をご覧ください。
スポンサードリンク
2. 二項関係のいろは
(1) 二項関係とは何か
日常生活に出てくる "関係" には様々なものがありますが、その中の1つに "人間関係" がありますね。
その人間関係を細分化すると、"友達関係" や "恋愛関係" など様々なあります。
例えば、恋愛関係に出てくる "関係"は、「ある2人が付き合っているときに成立する関係」と考えることができます。
[関係の具体的な例]- 翔くんと祐希さんは付き合っている
→ 翔くんと祐希さんに対しては、関係が成立している - 怜音くんと凛さんは付き合っていない
→ 翔くんと祐希さんに対しては、関係が成立していない
こんな感じに、ある2つの物事に対して、関係が成立するかしないかを考えるというのは、数学の世界にも登場し、二項関係と呼ばれます!
もう少し具体的に説明すると、数学の世界に出てくる二項関係
(2) 実は小学3年生でもわかる二項関係がある!?
二項関係って、なんだか難しそうですよね。
でも実は、小学3年生レベルでもわかる二項関係があるのです!
例えば、次の記号
言い換えると、この記号は "
離散数学で出てくる二項関係は、このような記号(=, ≠, >, <, ≧, ≦など)の関係を、自由気ままに定義できる道具みたいなもの、だと思ってください!
[高校数学までの二項関係]
[大学数学 (離散数学) での二項関係]
(3) 二項関係の定義の仕方
二項関係を用いて、ペアごとに関係
- 集合の形で、関係が成り立つペアを列挙する方法
- 関係が成り立つ条件を、数式を使って定義する方法
ここからは、2つの方法をそれぞれ詳しくみていきましょう。
(i) 集合の形で、関係が成り立つペアを定義する方法
二項関係
この場合、成り立つ関係のペアと成り立たない関係のペアは以下の通りです。
- 成り立つ関係: (1,1), (1,2), (2,2)
- 成り立たない関係: (2,1)
※ 上の例( (1,2) と (2,1) )のように、関係 (a,b) が成り立っていても、a, bを入れ替えた (b,a) は、必ず関係が成り立つとは限らないので注意です。また、関係 (a,b) が成り立っていなくて、a, bを入れ替えた関係 (b,a) が成り立つこともあります。
Tips1. 関係の有無の表記法
ここで、ある要素が関係が成り立つか否かを表す際には、以下のような表記が使われます。
- 関係が成り立つとき:
, - 関係が成り立たないとき:
, , でない、 でない
※ 複数表記法があるので、どれも使えるようになっておきましょう。
Tips2. 二項関係と直積集合
関係が成り立つペア(=二項関係
この書き方は直積集合の書き方
ここで、二項関係
さらに、元の集合の要素をいくつか抜き出して作った集合は、部分集合と呼ばれますよね。
そのため、二項関係
(ii) 関係が成り立つ条件を、数式や述語論理を使って定義する方法
領域が自然数領域、整数領域のように、無限に大きい値 (小さい値) が取れるような領域のときは(i) の集合の形でいちいち関係を列挙していたら、キリがありません。
そういうときに使われるのが、次のように2つ目のような数式や述語論理を使って定義する方法です。
ここで、関係
実際に、defを使った定義例はこんな感じですね。
※ 述語論理の読み方については、こちらの記事にて詳しく説明しておりますので、必要であれば以下のリンク先をご覧ください!
スポンサードリンク
3. 二項関係で重要な4つの関係 + おまけ2つ
ここからは、離散数学の期末試験で非常に重要である、二項関係で重要な4つの関係
- 反射性
- 対称性
- 反対称性
- 推移性
について、お勉強していきましょう!
おまけで、同値関係と比較可能な関係についても説明しています。
(1) 反射性
[述語論理を用いた定義]
反射性は、鏡の反射のように、二項関係において要素が自分自身と関係している性質です。

具体的に言うと、反射性を満たす二項関係とは、"定義域内において、値が等しいペアであれば、必ず関係が成り立つ" 二項関係のことを言います。
言い換えると、定義内において、1つでも値が等しいときに関係が成り立たなければ、反射性を満たすとは言えません。
[反射性を満たす例]
(1) 等号
(2)
(1) 自然数
[反射性を満たさない例]
(1) 不等号
(2)
(2) 自然数
(2) 対称性
[述語論理を用いた定義]
対称性とは、ペア
簡単に説明すると、対称性は
- 美玖さんにとって祐希さんはお友達の関係
→ 祐希さんにとっても美玖さんはお友達の関係成立
のように、関係が成立しているペアの順番を入れ替えても、関係が成立している性質です。
反対に、
- 祐希さんにとって瑠香さんはお友達の関係
→ 瑠香さんにとっては祐希さんはお友達の関係は成立していない
のような組み合わせが1つでもあれば、対称性を満たしません。
(この組み合わせが対称性を満たさない反例となります。)

また、関係が成立しているペアが1つもない場合(つまり
[対称性を満たす例]
(1) 等号
(2)
(3) 自然数
[対称性を満たさない例]
(1) 各種不等号
→ 例えば、
(2)
(3) 自然数
(3) 反対称性
[述語論理を用いた定義]
反対称性のイメージは、「異なるもの同士が、必ず双方向に関係を持たない」関係だと思ってください。(元の定義の対偶を取ったものです)

教科書によっては、対偶を取った形で定義を記載している参考書もあります。
としている参考書もあります。
ここで、注意ポイントが2つあります。
まず1つ目は、「対称性を満たすか否か」と「反対称性を満たすか否か」は、独立しているということです。
言い換えると、
- 対称性を満たす(満たさない)からと言って、必ず反対称性を満たさない(満たす)とは限らない
- 反対称性を満たす(満たさない)からと言って、必ず反対称性を満たさない(満たす)とは限らない
ということが言えます。例えば、
2つ目は、対称性のときと同じく、関係が成立しているペアが1つもない場合(つまり
[反対称性を満たす例]
(1) 等号
(2)
→ 値を入れ替えても なので関係成立。さらに、 なのでOK。 , は、ペアを入れ替えた仲間( がいない仲間外れ。なので、前提条件を満たしていないため、OK。
(3) 自然数
- 関係が成り立つ全てのペアは、
は正の偶数 - ペアの値を入れ替えて
とすると、 となり、正負が入れ替わる。よって、関係は絶対に成り立たない。 - よって、関係が成り立つ全てのペアにおいて、ペアの値を入れ替えると関係が成り立たなくなることが言える。
→ 反対称性が成り立つ。
[反対称性を満たさない例]
(1) 否定等号
(2)
色が対応している関係
しかし
(3) 自然数
※
(4) 推移性
[述語論理を用いた定義]
推移性とは、ペア
簡単に説明すると、推移性は
- 美玖さんと祐希さんはお友達の関係成立
- 祐希さんと大樹さんもお友達の関係成立
→ 美玖さんと大樹さんもお友達の関係成立
みたいな三段論法的が、常に成立する性質です。

こちらも対称性のときと同じく、関係が成立しているペアが1つもない場合(つまり
推移性は、前提条件が割と複雑なため、結構反例を逃しがちなので、反例を探す練習をしましょう。
[推移性を満たす例]
(1) 等号
→ 例えば、
(2)
(3) 自然数
ここで、推移性の前提条件ごとに場合分けすると、
- (偶数,偶数) かつ (偶数,偶数) → (偶数,偶数) [OK]
- (奇数,奇数) かつ (奇数,奇数) → (奇数,奇数) [OK]
となるため、必ず
[推移性を満たさない例]
(1) 否定等号
→
(2)
※ この例のように、見つかりにくいように反例が隠されていることもあるので注意! 前提条件を見つけるコツは、あるペアの右側の値
(3) 自然数
ある集合
(1) 反射性(反射律):
→ ペア内の値が同じときは常に関係が成り立つ。
(2) 対称性(対称律):
→ 関係
(3) 反対称性:
→ 2つの変数
(4) 推移性(推移律):
→
おまけ1. 同値関係
離散数学の第01羽では、「同値関係
ですが、今回の二項関係の知識を使うことで、同値関係は、
- 反射性(反射律)
→ 同じ値同士は、必ず同値関係となること。 - 対称性(対称律)
→ ペア内の順番を入れ替えても、同値関係の成立/不成立は変わらないこと。
(例えば同値関係 が成立していれば、必ず も成立している。) - 推移性(推移律)
→ 三段論法的な関係があること。
の3つを全て満たすもの、と厳密に定義できるようになります。
おまけ2. 比較可能
[述語論理を用いた定義]
二項関係における比較可能とは、領域内にあるすべての値に対して、その値の "大小 " や "等しい/等しくない" が関係の成立/不成立だけで比べられるような関係です。
例えば、皆さんが日常的に使っている記号
ここで、比較可能の定義の仕組みを
まず、
関係 | ||
---|---|---|
xよりyの方が大きい | 成立 | 不成立 |
xよりyの方が小さい | 不成立 | 成立 |
xがyと等しい | 成立 | 成立 |
この表から、
- あるペア
および値を入れ替えたペア のうち、どちらか片方が成立することで、大小関係が分かる - あるペア
および値を入れ替えたペア のうち、両方が成立することで、等しいことが分かる
ことが分かります。
よって、領域内のどの2つの値
例えば、
- 色なし部分は必ず成立させる
- 色あり部分は、同じ色がついた要素の中から少なくとも1つ成立させる
すればOKです。
(1,1) | (1,2) | (1,3) | (1,4) |
(2,1) | (2,2) | (2,3) | (2,4) |
(3,1) | (3,2) | (3,3) | (3,4) |
(4,1) | (4,2) | (4,3) | (4,4) |
例えば、
R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
は完全性を持ちます。
(色の部分が対応しています)
おまけ3. 半順序関係
※ 詳しい内容は、離散数学の第5羽にて説明します。
半順序関係とは、与えられた集合の要素の一部分において、順序付けができるような関係のことを表します。
厳密にいうと、以下の3つの関係性が成り立っている関係が半順序関係です。
- 反射性
- 反対称性
- 推移性
例えば、A = {翔くん, 祐希さん, 怜音くん} とし、足が速いという関係
- 翔くんは、祐希さん以上に足が速い
- 怜音くんは、祐希さん以上に足が速い
という関係が成立していたとき、「翔くんと祐希さんの足の速さの関係」は、上の関係から分かりますが、「翔くんと怜音くんの足の速さの関係」は、上の関係からでは分かりませんよね。
このように、与えられた要素の一部分だけが順序付けができるような関係のことを、半順序関係と呼びます。
おまけ4. 全順序関係
※ 詳しい内容は、離散数学の第5羽にて説明します。
全順序関係とは、与えられた集合の要素のどの要素を比べても、順序付けができるような関係のことを表します。
厳密にいうと、半順序関係の条件(反射性・反対称性・推移性)に加えて比較可能性が成立していることが、全順序関係が成立する条件です。
例えば、数学の世界で使われる関係
そのため、
4. 例題で確認!
では、ここからは「ある関係が反射性、対称性、反対称性、推移性を満たすかどうか」を判定するための練習として、例題を解いてみましょう!
二項関係
(1) 領域:
(2) 領域: 0以上の整数
このとき、
[略解1]
※ 各性質を満たす場合は〇を、満たさない場合は反例を1つ挙げている。
関係 | (i) 反射性 | (ii) 対称性 | (iii) 反対称性 | (iv) 推移性 |
---|---|---|---|---|
〇 | 〇 |
[解説1]
(1) 関係
(1-i) [反射性] 満たさない。反例:
(1-ii) [対称性] 満たさない。反例:
関係
すると、関係が成り立つペア
(1-iii) [反対称性] 満たさない。反例:
先ほどの色分けしたグループ分けに着目する。すると、前提条件として、
(1-iv) [推移性] 満たさない。反例:
反例を探すのが難しいが、
(2) 関係
(2-i) [反射性] 満たす。
(2-ii) [対称性] 満たす。
→ が平方数 → が平方数
ここで、
よって、対称性もOK。
(2-iii) [反対称性] 満たさない。反例:
ここで、(ii) より、
よって、反対称性は満たさない。
(2-iv) [推移性] 満たさない。反例:
「
見た目的に反例がなさそうだなと思うかもしれないが、油断するのはダメ。
反例がなさそうだなと思ったら、極端な例として0を代入するというのをやってみよう[8]0というのは、何を掛けても0という特殊な数なので、0を入れると反例が割と出てくることがある。。
(※ 領域に0が含まれていることを確認しましょう。)
すると、以下の [前提条件] を満たすけど、
反射性、対称性、反対称性、推移性が成り立つかどうかを考える際には、成り立つ理由を考える前に、まず身近な例で反例が見つからないかを調べる。特に0が許容されている場合には、0を代入することで反例が見つかることも多い。
関係
- 反射性:
以外のときに反例が見つかるかどうか - 対称性:
, を入れ替えたときの値の変化を見る - 反対称性: 対称性が成り立つ場合で、
となるような を探す - 推移性:
と が成り立つのに で成り立たないものを調べる。反射性が成り立たない場合は、 と で成り立つのに となるようなものを探すのもあり。
5. 二項関係と閉包 [応用]
閉包とは「(反射性、対称性、推移性などの条件を満たしていない)二項関係に対して、条件を満たすためには、最低限の要素としてどんな要素を追加すれば良いか」を追加した後の二項関係で表したものです。
ここで、閉包の中でも、試験によく出てくる閉包はこの3つです。
- 反射閉包
→ 関係 に最低限の要素を追加し、反射性を満たすようにした関係 - 対称閉包
→ 関係 に最低限の要素を追加し、対称性を満たすようにした関係 - 推移閉包
→ 関係 に最低限の要素を追加し、推移性を満たすようにした関係
閉包の求め方については、実際に例題(関係は例題1の
領域:
(1) 反射閉包
(2) 対称閉包
(3) 推移閉包
[解答2]
(1)
(2)
(3)
※ ピンク色の要素が、関係を成り立たせるために最低限補った要素である。
[解説2]
(1) 反射閉包
反射性を満たすためには、領域
しかし、与えられた
(2) 対称閉包
対称性を満たすためには、「関係が成立しているペア
ここで、「元のペア
なので、元の関係
(3) 推移閉包
推移閉包は、補い漏れが発生しやすいため、慎重に見ていきましょう。
補い漏れを防ぐためには、関係が成立しているあるペアの右側の値
今回の場合は、次の3つを確認します。
と が にあるかを確認。
→ ないため、 を補う必要あり。 と が にあるかを確認。
→ あるため、何もしなくてOK。 と が にあるかを確認。
→ あるため、何もしなくてOK。
よって、推移閉包は
6. 二項関係の数え上げ [応用]
最後に、今回お勉強した二項関係の知識を使って、少し難易度の高い数え上げにチャレンジしてみましょう!
集合
(1) 直積集合
(2) 集合
(3) 集合
(4) 集合
(5) 集合
[解答3]
(1) 9
(2) 512 [
(3) 64 [
(4) 64 [
(5) 8 [
[解説3]
(1) 答え: 9個
直積集合の要素数を数えるときは、こんな感じに表を書きましょう。
A \ A | 1 | 2 | 3 |
---|---|---|---|
1 | (1,1) | (1,2) | (1,3) |
2 | (2,1) | (2,2) | (2,3) |
3 | (3,1) | (3,2) | (3,3) |
すると、直観的に 3×3 = 9 だな、というのが分かります!
(2) 答え: 512通り
二項関係
つまり、
よって、二項関係
ここで、
A \ A | 1 | 2 | 3 |
---|---|---|---|
1 | (1,1) | (1,2) | (1,3) |
2 | (2,1) | (2,2) | (2,3) |
3 | (3,1) | (3,2) | (3,3) |
(3) 答え: 64通り
二項関係
今回の領域は、
一方、その他のペア(9 - 3 = 6ペア)は、関係が成り立っていようが成り立っていなかろうが、反射性を満たすか否かには関係ありません。
そのため、6ペアに対して、関係を成立させるかさせないかの2通りを組み合わせた数
A \ A | 1 | 2 | 3 |
---|---|---|---|
1 | (1,1) | (1,2) | (1,3) |
2 | (2,1) | (2,2) | (2,3) |
3 | (3,1) | (3,2) | (3,3) |
※ 赤い関係 → 必ず成立する必要あり
※ それ以外 → 成立していてもいなくてもどちらでもOK
(4) 答え: 64通り
二項関係
ただし、(1,1), (2,2), (3,3) のように、値が等しいペアについては、ペアの (x,y) の値を入れ替えて (y,x) の形にしても (1,1), (2,2), (3,3) と変わらないため、単独で成立している/成立していないを考えても問題ありません。
一方、値が異なる残りの6ペアについては、ペア
よって今回の場合、6ペアを2ペアごとに1組とするため、3組について、成立している/成立していないを考えることができます。
※ 本当に3ペアかどうか、値が等しくない (
A \ A | 1 | 2 | 3 |
---|---|---|---|
1 | (1,1) | (1,2) | (1,3) |
2 | (2,1) | (2,2) | (2,3) |
3 | (3,1) | (3,2) | (3,3) |
※ 色ありの関係 → 同じ色ごとに、成立している/成立していない、を考える [3組]
※ 色なしの関係 → 成立している/成立していないを単独で考えてOK [3ペア]
よって、対称性を満たす二項関係は、以下をすべて組み合わせた数だけ存在します。
- (1,2) と (2,1) の組の関係が共に成立しているか否かの2通り
- (1,3) と (3,2) の組の関係が共に成立しているか否かの2通り
- (2,3) と (3,2) の組の関係が共に成立しているか否かの2通り
- (1,1), (2,2), (3,3) それぞれのペアの関係が成立しているか否かの2通り
二項関係
(5) 答え: 8通り
二項関係
そのため、今回の例だと (1,1), (2,2), (3,3) は常に関係が成立している必要があります。
さらに、対称性を成り立たせるためには、あるペア
そのため、反射性・対称性をともに満たすような二項関係の総数は、
- (1,2) と (2,1) の組の関係が共に成立しているか否かの2通り
- (1,3) と (3,2) の組の関係が共に成立しているか否かの2通り
- (2,3) と (3,2) の組の関係が共に成立しているか否かの2通り
を組み合わせた数だけあるため、
「元のペア
7. 確認テスト
最後に、今回の記事や動画で勉強した内容が、理解できているかどうかをどうかを確認するための小テストを作りました!
理解度確認に是非チャレンジしてみてください!
※ 回答フォームに入力後、自動採点 & 自動解説表示が行われます。
8. さいごに
今回は、離散数学に出てくる二項関係について、色々お勉強していきました。
反射性、対称性、反対称性、推移性は離散数学のテストによく出てくるとても重要な概念なので、理解をしておきましょう!
次回は、半順序関係についてお勉強していきましょう。
注釈
↑1 | 直積集合 |
---|---|
↑2 | |
↑3 | 条件A → 条件B、を偽と言うためには、条件Aが成立しているにも関わらず、条件Bが成立していないことを言う必要がある。しかし、その条件Aを満たす例がないため、「条件A → 条件B」を偽と言うことは出来ない。よって、条件Aを満たす例が1つもないとき、「条件A → 条件B」は必ず真となってしまう。 |
↑4 | (1,1), (2,2), (3,3) はすべて2つの値が同じペアなため、単独で対称性の条件を満たしますね。さらに、3つのペアはともに、反対称性「元のペアと、値を入れ替えたペアが共に関係が成りたっている」の前提条件を満たしており、なおかつ、どのペアも2つの値が同じになっていますね。なので、反対称性の条件も満たしています。 |
↑5 | 偶数 + 偶数 = 偶数,奇数 + 奇数 = 偶数,偶数 + 奇数 = 奇数,奇数 + 偶数 = 奇数 |
↑6 | 2つの値が等しいペアに着目すると、 |
↑7 | 偶数 × 偶数 = 偶数,奇数 × 奇数 = 奇数,偶数 × 奇数 = 偶数,奇数 × 偶数 = 偶数 |
↑8 | 0というのは、何を掛けても0という特殊な数なので、0を入れると反例が割と出てくることがある。 |
関連広告・スポンサードリンク