同値関係と半順序
「同じグループ」と「順序を付けられる関係」の性質を学びます。
説明
二つの要素の間に条件が成り立つとき、それらの間に関係があると考えます。たとえば「3で割った余りが同じ」や「片方がもう片方の約数である」という条件です。
このモジュールでは、まず余りが同じ整数をグループに分けます。その関係が反射律・対称律・推移律を満たすことを確認し、同値類を作ります。次に約数の関係を使い、すべての組に前後関係を付けられるとは限らない半順序を説明します。
13で割った余りが同じ整数
0〜5を対象に、3で割った余りを表示します。
values = list(range(6))対象の整数; [(n, n % 3) for n in values]整数と3で割った余り0と3、1と4、2と5の余りがそれぞれ同じです。この「余りが同じ」という関係を調べます。
2自分自身との関係は成り立つか
すべての要素で自分自身との関係が成り立つ性質を、反射律と呼びます。
same = lambda a, b: a % 3 == b % 3余りが同じかを判定; all(same(a, a) for a in values)全要素で自分自身との関係を確認Trueです。同じ整数同士なら余りも同じなので、反射律を満たします。
3向きを逆にしても成り立つか
aとbに関係があればbとaにも関係がある性質を、対称律と呼びます。
all((not same(a, b)) or same(b, a)関係があれば逆向きにもある for a in values for b in values全組合せ)Trueです。aとbの余りが同じなら、比較する順番を逆にしても同じです。式は「aとbに関係があるなら、逆向きにもある」という含意を全組で調べています。
4二つの関係をつなげられるか
aとb、bとcに関係があればaとcにも関係がある性質を、推移律と呼びます。
all((not (same(a, b) and same(b, c))) or same(a, c)二つの関係から三つ目が成り立つか for a in values for b in values for c in values全ての三つ組)Trueです。aとbの余りが等しく、bとcの余りが等しければ、aとcの余りも等しくなります。この理由は今回の0〜5以外の整数にも当てはまります。
5同値類で集合を分ける
反射律・対称律・推移律を満たす関係を同値関係と呼びます。互いに関係がある要素をまとめた集合が同値類です。
classes = {r: [n for n in values if n % 3 == r]同じ余りの整数をまとめる for r in range(3)余り0・1・2の各組}; classes同値類を表示0と3、1と4、2と5の三つの組に分かれます。各要素はいずれか一つに所属し、異なる同値類は重なりません。
6約数による順序の関係
次は1、2、3、6の中で、aがbの約数ならa≼bとする関係です。余りが0になる組を列挙します。
items = [1, 2, 3, 6]新しい対象集合; divides = lambda a, b: b % a == 0aがbの約数か; [(a, b) for a in items for b in items if divides(a, b)]関係がある組1は全要素の約数、2と3は6の約数です。ただし2は3の約数でも、その逆でもありません。
7反対称律と推移律
半順序は反射律・反対称律・推移律を満たす関係です。反対称律は、a≼bとb≼aが両方成り立つならa=bであるという条件です。
all((not (divides(a, b) and divides(b, a))) or a == b for a in items for b in items)反対称律, all((not (divides(a, b) and divides(b, c))) or divides(a, c) for a in items for b in items for c in items)推移律どちらもTrueです。各正整数は自分自身の約数なので反射律も満たします。余りが同じという関係の対称律と、ここでの反対称律は別の性質です。
8前後を決められない組
a≼bでもb≼aでもない組を抽出します。
[(a, b) for i, a in enumerate(items) for b in items[i+1:]異なる二要素の組 if not divides(a, b) and not divides(b, a)どちら向きの関係もない組]2と3が残ります。数値としては2<3ですが、約数という今回の順序では比較できません。半順序にはこのような組があり得ます。すべての組を比較できる場合は全順序と呼びます。
まとめ
同値関係は反射律・対称律・推移律を満たし、対象を重ならない同値類へ分けます。
半順序は反射律・反対称律・推移律を満たします。順序の規則によっては、異なる二要素の前後関係を決められない場合があります。
操作履歴と解説を振り返れます。
Python 3
values = list(range(6)); [(n, n % 3) for n in values][(0, 0), (1, 1), (2, 2), (3, 0), (4, 1), (5, 2)]
same = lambda a, b: a % 3 == b % 3; all(same(a, a) for a in values)True
all((not same(a, b)) or same(b, a) for a in values for b in values)True
all((not (same(a, b) and same(b, c))) or same(a, c) for a in values for b in values for c in values)True
classes = {r: [n for n in values if n % 3 == r] for r in range(3)}; classes{0: [0, 3], 1: [1, 4], 2: [2, 5]}items = [1, 2, 3, 6]; divides = lambda a, b: b % a == 0; [(a, b) for a in items for b in items if divides(a, b)][(1, 1), (1, 2), (1, 3), (1, 6), (2, 2), (2, 6), (3, 3), (3, 6), (6, 6)]
all((not (divides(a, b) and divides(b, a))) or a == b for a in items for b in items), all((not (divides(a, b) and divides(b, c))) or divides(a, c) for a in items for b in items for c in items)(True, True)
[(a, b) for i, a in enumerate(items) for b in items[i+1:] if not divides(a, b) and not divides(b, a)][(2, 3)]
演習完了