Presentation is loading. Please wait.

Presentation is loading. Please wait.

集合の中の二項関係 ・反射律、対称律、推移律、反対称律 ・同値関係 ・順序関係

Similar presentations


Presentation on theme: "集合の中の二項関係 ・反射律、対称律、推移律、反対称律 ・同値関係 ・順序関係"— Presentation transcript:

1 集合の中の二項関係 ・反射律、対称律、推移律、反対称律 ・同値関係 ・順序関係
先週の復習 集合の中の二項関係 ・反射律、対称律、推移律、反対称律 ・同値関係 ・順序関係

2 反射律(reflexive law) 反射律: 任意の 𝑥 に対して、 𝑥𝑅𝑥 反射的関係: 反射律を満たす関係 関係行列では
教科書p.142■中の関係の性質 反射律(reflexive law) 反射律: 任意の 𝑥 に対して、    𝑥𝑅𝑥 反射的関係: 反射律を満たす関係 関係行列では 関係グラフでは 1 ・𝒩の中の関係「=」、「≤」は反射的関係 ・𝒩の中の関係「<」は反射的でない

3 対称律(symmetric law) 対称律: 任意の𝑥,𝑦に対して、 𝑥𝑅𝑦 ならば 𝑦𝑅𝑥 対称的関係: 対称律を満たす関係
教科書p.142■中の関係の性質 対称律(symmetric law) 対称律: 任意の𝑥,𝑦に対して、 𝑥𝑅𝑦 ならば 𝑦𝑅𝑥 対称的関係: 対称律を満たす関係 関係行列では 関係グラフでは ・𝒩の中の関係「≠」は対称的関係 ・人の集合の中の「友人関係」が対称的なら円満なのだが...

4 推移律(transitive law) 𝑅 2 ⊆𝑅 推移律: 任意の𝑥,𝑦, 𝑧に対して、 𝑥𝑅𝑦 かつ 𝑦𝑅𝑧 ならば 𝑥𝑅𝑧
教科書p.142■中の関係の性質 推移律(transitive law) 推移律: 任意の𝑥,𝑦, 𝑧に対して、 𝑥𝑅𝑦 かつ 𝑦𝑅𝑧 ならば 𝑥𝑅𝑧 推移的関係: 推移律を満たす関係 関係グラフでは 間接的な関係があれば 直接の関係も存在する 𝑅 2 ⊆𝑅 2回でいけるなら 1回でもいける ・𝒩の中の関係「≤」、「<」は推移的関係 ・人の集合の中の「祖先子孫関係」は推移的関係

5 反対称律(asymmetric law) 反対称律: 任意の𝑥,𝑦に対して、𝑥𝑅𝑦 かつ 𝑦𝑅𝑥 ならば 𝑥=𝑦
教科書p.143■中の関係の性質 反対称律(asymmetric law) 反対称律: 任意の𝑥,𝑦に対して、𝑥𝑅𝑦 かつ 𝑦𝑅𝑥 ならば 𝑥=𝑦 反対称的関係: 反対称律を満たす関係 関係行列では 関係グラフでは ・𝒩の中の関係「<」、「≤」は反対称的関係 ・人の集合の中の「親子関係」、「祖先子孫関係」は 反対称的関係

6 反対称律 任意の 𝑥, 𝑦∊𝐴 に対して 𝑥≤𝑦 かつ 𝑦≤𝑥 ⇒ 𝑥=𝑦 対偶 任意の 𝑥, 𝑦∊𝐴 に対して
教科書p.143■中の関係の性質 反対称律 任意の 𝑥, 𝑦∊𝐴 に対して    𝑥≤𝑦 かつ 𝑦≤𝑥 ⇒ 𝑥=𝑦 対偶 任意の 𝑥, 𝑦∊𝐴 に対して    𝑥≠𝑦 ⇒¬ 𝑥≤𝑦) または ¬( 𝑦≤𝑥

7 次の関係グラフで表された関係は、反射律、対称律、推移律、反対称律の性質を満足するかどうか、答えよ
教科書p.148■演習問題4 次の関係グラフで表された関係は、反射律、対称律、推移律、反対称律の性質を満足するかどうか、答えよ (1) (2) (3) 𝑎 𝑏 𝑎 𝑏 𝑎 𝑏 𝑐 𝑑 𝑐 𝑑 𝑐 𝑑 (4) (5) 𝑎 𝑏 𝑎 𝑏 𝑐 𝑑 𝑐 𝑑

8 教科書p.143■同値関係 同値関係 𝐴 の中の関係 𝑅 が反射律、対称律、推移律を満たすとき、𝑅 は 𝐴 における同値関係(equivalence relation)であるという 同じとみなせるものどうしに分類 同値関係は「等号」で表すのが適当であり、=と区別できる ≅,≈,≡ などが用いられる

9 同値関係ではない関係 ∼={ 𝑥,𝑦 ∣𝑥,𝑦∈𝒬, 𝑥−𝑦 <1} 反射律は満たす ∵ 任意の𝑥∈𝒬 に対して 𝑥−𝑥 =0
教科書p.143■同値関係 同値関係ではない関係 ∼={ 𝑥,𝑦 ∣𝑥,𝑦∈𝒬, 𝑥−𝑦 <1} 反射律は満たす ∵ 任意の𝑥∈𝒬 に対して 𝑥−𝑥 =0 対称律も満たす ∵ 任意の𝑥,𝑦∈𝒬 に対して 𝑥−𝑦 =|𝑦−𝑥| 推移律は満たさない  反例 「0∼0.7」 かつ 「0.7∼1.5」 であるけれども 「0∼1.5」ではない nearly equal

10 教科書p.186■順序関係 順序関係 𝐴 の中の関係 𝑅 が反射律、反対称律、推移律を満たすとき、𝑅 は 𝐴 における順序関係(order relation)であるという 全順序関係 半順序関係 𝒩(あるいは𝒵)の中の大小関係「≤」は、順序関係 順序関係は「等号つき不等号」で表すのが適当であり ≤,⊆,≼ などあるいは、その逆向きの記号が用いられる

11 復習はここまで

12 𝑛を法として合同(これも復習か) 自然数 𝑛 で整数 𝑚 1 と 𝑚 2 を割った剰余が同じであるとき 𝑚 1 ≡ 𝑚 2 mod 𝑛
教科書p.105■合同 𝑛を法として合同(これも復習か) 自然数 𝑛 で整数 𝑚 1 と 𝑚 2 を割った剰余が同じであるとき 𝑚 1 ≡ 𝑚 2 mod 𝑛 あるいは 𝑚 1 ≡ 𝑛 𝑚 2 と書き、 𝑚 1 と 𝑚 2 は 𝑛 を法として合同(congruent modulo 𝑛)であるという ≡ 𝑛 は𝒵(整数の集合)における同値関係 反射律: 任意の 𝑥∈𝒵 に対して 𝑥 ≡ 𝑛 𝑥 対称律: 任意の 𝑥,𝑦∈𝒵 に対して 𝑥 ≡ 𝑛 𝑦 ならば 𝑦 ≡ 𝑛 𝑥 推移律: 任意の 𝑥,𝑦,𝑧∈𝒵 に対して  𝑥 ≡ 𝑛 𝑦 かつ 𝑦 ≡ 𝑛 𝑧 ならば 𝑥≡ 𝑛 𝑧

13 同値類と商集合 𝑅 を 𝐴 における同値関係として、 𝑎 𝑅 ={𝑥∣𝑥∈𝐴 𝑎𝑅𝑥}
教科書p.144■同値類 同値類と商集合 𝑅 を 𝐴 における同値関係として、 𝑎 𝑅 ={𝑥∣𝑥∈𝐴 𝑎𝑅𝑥} を 𝐴 における 𝑅 による 𝑎 の同値類(equivalence class)という 𝑎 𝑅 と表記すると、 𝑎 がその同値類の代表元(representative) 同値関係 𝑅 による 𝐴 のすべての同値類の集合 𝐴/𝑅= { 𝑎 𝑅 ∣𝑎∈𝐴} を 𝐴 の𝑅 に関する商集合 (quotient set)という 𝐴/𝑅 は 𝐴 の直和分割

14 教科書p.144■同値類 同値関係の関係グラフ 𝑎 𝑖 𝑏 𝑐 𝑗 𝑘 𝑑 𝑒 𝑙 𝑚 𝑔 𝑛 𝑜

15 同値関係の関係グラフ と同値類 [ℎ] 𝑅 [𝑏] 𝑅 [𝑎] 𝑅 [𝑖] 𝑅 [𝑑] 𝑅 [𝑔] 𝑅 [𝑙] 𝑅 代表元は何でも良い ℎ
教科書p.144■同値類 同値関係の関係グラフ と同値類 代表元は何でも良い [𝑎] 𝑅 [𝑔] 𝑅 [ℎ] 𝑅 [𝑖] 𝑅 [𝑙] 𝑅 [𝑑] 𝑅 [𝑏] 𝑅 𝑎 𝑖 𝑏 𝑐 𝑗 𝑘 𝑑 𝑒 𝑙 𝑚 𝑔 𝑛 𝑜

16 同値関係の関係グラフ と同値類、商集合 [ℎ] 𝑅 [𝑎] 𝑅 [𝑖] 𝑅 [𝑑] 𝑅 [𝑔] 𝑅 [𝑙] 𝑅 [ℎ] 𝑅 [𝑎] 𝑅
教科書p.144■同値類 同値関係の関係グラフ と同値類、商集合 𝐴/𝑅 [ℎ] 𝑅 [𝑎] 𝑅 [𝑖] 𝑅 [𝑑] 𝑅 [𝑔] 𝑅 [𝑙] 𝑅 [𝑎] 𝑅 [𝑔] 𝑅 [ℎ] 𝑅 [𝑖] 𝑅 [𝑙] 𝑅 [𝑑] 𝑅 𝑎 𝑖 𝑏 𝑐 𝑗 𝑘 𝑑 𝑒 𝑙 𝑚 𝑔 𝑛 𝑜

17 𝒵 の ≡ 𝑛 に関する商集合 𝒵における ≡ 𝑛 による 同値類
教科書p.108■剰余類と剰余系 𝒵 の ≡ 𝑛 に関する商集合 𝒵における ≡ 𝑛 による 同値類 𝑘 ≡ 𝑛 = 𝑛𝑥+𝑘 𝑥∈𝒵 ={…,𝑘−𝑛,𝑘,𝑘+𝑛,𝑘+2𝑛…} を法 𝑛 による剰余類(residue class)といい、 𝑘 𝑛 とも書く 法 𝑛 によるすべての剰余類の集合(𝒵 の ≡ 𝑛 に関する商集合) 𝒵/ ≡ 𝑛 ={ 0 𝑛 , 1 𝑛 ,… 𝑛−1 𝑛 } を法 𝑛 による剰余系(residue system)といい、 𝒵 𝑛 とも書く 𝒵 3 = , , ={0,1,2}   = 3𝑥 𝑥∈𝑍 ={…,−6,−3,0,3,6,…}   = 3𝑥+1 𝑥∈𝑍 ={…,−5,−2,1,4,7,…}   = 3𝑥+2 𝑥∈𝑍 ={…,−4,−1,2,5,8,…} 代表元は本当は何でも良いけど普通 0,…,𝑛−1を用いる

18 剰余系における加法 𝒵 𝑛 における加法「 + 𝑛 」を以下のように定義する 𝑥 𝑛 + 𝑛 𝑦 𝑛 = 𝑥+𝑦 𝑛
教科書p.109■剰余系における加法 剰余系における加法 𝒵 𝑛 における加法「 + 𝑛 」を以下のように定義する 𝑥 𝑛 + 𝑛 𝑦 𝑛 = 𝑥+𝑦 𝑛 𝒵 𝑛 における加法演算子 𝒵における加法演算子 [1] 5 = [3+1] 5 = [4] 5 [4] 5 = [3+4] 5 = [7] 5 = [7−5] 5 = [2] 5 [1] 5 = [3+1] 5 = [4] 5 [4] 5 = [3+4] 5 = [7] 5 = [7−5] 5 = [2] 5 多くの場合「 + 5 」ではなく「+」と書く

19 剰余系における加法 零元(加法の単位元) 𝑥 𝑛 + 𝑛 [0] 𝑛 = [𝑥+0] 𝑛 = [𝑥] 𝑛
教科書p.109■剰余系における加法 剰余系における加法 零元(加法の単位元) 𝑥 𝑛 + 𝑛 [0] 𝑛 = [𝑥+0] 𝑛 = [𝑥] 𝑛 0 𝑛 + 𝑛 [𝑥] 𝑛 = [0+𝑥] 𝑛 = [𝑥] 𝑛 より [0] 𝑛 は 𝒵 𝑛 の零元 符号替え(加法の逆元) − 𝑛 𝑥 𝑛 = −𝑥 𝑛 特に 0<𝑥<𝑛 のとき − 𝑛 𝑥 𝑛 = 𝑛−𝑥 𝑛 e.g. − 5 [1] 5 = [−1] 5 = [5−1] 5 = [4] 5 「引く」=逆元を加える 減法 𝒵 𝑛 における減法「 − 𝑛 」を以下のように定義する 𝑥 𝑛 − 𝑛 [𝑦] 𝑛 = 𝑥 𝑛 + 𝑛 ( − 𝑛 𝑦 𝑛 ) [3] 5 − = − = [1] 5 = [4] 5 結局 − 5 [4] 5 = [3−4] 5 = [−1] 5 = [4] 5

20 剰余系における乗法 𝒵 𝑛 における乗法「 × 𝑛 」を以下のように定義する 𝑥 𝑛 × 𝑛 𝑦 𝑛 = 𝑥×𝑦 𝑛
教科書p.110■剰余系における乗法 剰余系における乗法 𝒵 𝑛 における乗法「 × 𝑛 」を以下のように定義する 𝑥 𝑛 × 𝑛 𝑦 𝑛 = 𝑥×𝑦 𝑛 𝒵 𝑛 における乗法演算子 𝒵における乗法演算子 [7] 5 × 5 [8] 5 = [7×8] 5 = [56] 5 = [1] 5 [7] 5 × 5 [8] 5 = [2] 5 × 5 [3] 5 = [2×3] 5 = [6] 5 = [1] 5

21 剰余系における乗法 単位元 𝑥 𝑛 × 𝑛 [1] 𝑛 = [𝑥×1] 𝑛 = [𝑥] 𝑛
教科書p.110■剰余系における乗法 剰余系における乗法 単位元 𝑥 𝑛 × 𝑛 [1] 𝑛 = [𝑥×1] 𝑛 = [𝑥] 𝑛 1 𝑛 × 𝑛 [𝑥] 𝑛 = [1×𝑥] 𝑛 = [𝑥] 𝑛 より [1] 𝑛 は 𝒵 𝑛 の単位元 (乗法の)逆元 [1] 5 −1 = [1] 5  (∵ [1] 5 × [1] 5 = [1] 5 ) [2] 5 −1 = [3] 5  (∵ [2] 5 × [3] 5 = [6] 5 = [1] 5 [3] 5 −1 = [2] 5 [4] 5 −1 = [4] 5  (∵ [4] 5 × [4] 5 = [16] 5 = [1] 5 𝑛 が素数のとき、 0 𝑛 を除く 𝒵 𝑛 のすべての要素に逆元が存在する

22 教科書p.110■剰余系における乗法 剰余系における乗法 「割る」=逆元をかける 𝒵 𝑛 における除法「 ÷ 𝑛 」を以下のように定義する 𝑥 𝑛 ÷ 𝑛 [𝑦] 𝑛 = 𝑥 𝑛 × 𝑛 ( 𝑦 𝑛 −1 ) [4] 5 ÷ 5 [3] 5 = [4] 5 × [3] 5 −1 = × 5 [2] 5 = [4×2] 5 = = [3] 5

23 例題 (1) = (2) 2 11 − 5 11 = (3) 5 11 × 5 11 = (4) 3 11 ÷ 5 11 = (ただし ( 5 11 ) −1 = 9 11 )

24 次は順序関係

25 トーナメント戦における強弱関係 規則 自分は自分より強い 2. 𝑥が𝑦に勝った ⇒ 𝑥は𝑦より強い 3. 𝑥が𝑦に勝った かつ
教科書p.186■順序関係 トーナメント戦における強弱関係 規則 自分は自分より強い 2. 𝑥が𝑦に勝った   ⇒ 𝑥は𝑦より強い 3. 𝑥が𝑦に勝った かつ 𝑦が𝑧に勝った   ⇒ 𝑥はzより強い 𝐶 反射律 反対称律 𝐶 𝐹 𝐴 𝐶 𝐹 𝐺 推移律 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺 𝐻

26 トーナメント戦における強弱関係 反射律 推移律 𝐶 𝐶 𝐹 𝐴 𝐶 𝐹 𝐺 結論 ・𝐶が一番強い ・2番目に強いのは
教科書p.186■順序関係 トーナメント戦における強弱関係 反射律 推移律 𝐶 𝐶 𝐴 𝐷 𝐹 𝐶 𝐹 𝐵 𝐸 𝐺 𝐴 𝐶 𝐹 𝐺 𝐻 結論 ・𝐶が一番強い ・2番目に強いのは  𝐹か𝐴か𝐷(𝐹の2位は籤運) 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺 𝐻

27 教科書p.186■順序関係 順序関係 𝐴 の中の関係 𝑅 が反射律、反対称律、推移律を満たすとき、𝑅 は 𝐴 における順序関係(order relation)であるという 比較不能 全要素対が比較可能 全順序関係 (total order relation) 半順序関係 (partial order relation) 大小関係、上下関係、前後関係(反射律も必要) 順序集合(𝐴;≤):順序関係 ≤ の定義された集合 𝐴

28 全順序関係 すべての要素対が比較可能 𝑎≠𝑏 ならば 𝑎𝑅𝑏 または 𝑏𝑅𝑎 のいずれか一方が成立
教科書p.186■順序関係 全順序関係 すべての要素対が比較可能 𝑎≠𝑏 ならば 𝑎𝑅𝑏 または 𝑏𝑅𝑎 のいずれか一方が成立 線形順序(linear order)ともいう 数直線上に一直線に並ぶ数の集合𝒩, 𝒵, 𝒬, ℛ, etc. は全順序集合

29 関係グラフとハッセ図 ・反射的関係のループを省略 a f ・推移的に得られる b 有向辺を省略 𝑥𝑅𝑧 𝑧𝑅𝑦 なる 𝑧 があれば
教科書p.187■順序集合のグラフと関係行列 関係グラフとハッセ図 ・反射的関係のループを省略 a f b ・推移的に得られる 有向辺を省略 𝑥𝑅𝑧 𝑧𝑅𝑦 なる  𝑧 があれば  𝑥𝑅𝑦の有向辺を除く e c d ・上位の要素を上に配置し 辺の向きをなくす 関係グラフ

30 関係グラフとハッセ図 ・反射的関係のループを省略 a f ・推移的に得られる b 有向辺を省略 𝑥𝑅𝑧 𝑧𝑅𝑦 なる 𝑧 があれば
教科書p.187■順序集合のグラフと関係行列 関係グラフとハッセ図 ・反射的関係のループを省略 a f b ・推移的に得られる 有向辺を省略 𝑥𝑅𝑧 𝑧𝑅𝑦 なる  𝑧 があれば  𝑥𝑅𝑦の有向辺を除く e c d ・上位の要素を上に配置し 辺の向きをなくす ハッセ図

31 𝒩上の約数関係 ・𝑥∣𝑦 : 𝑥 は 𝑦 の約数である 反射律、反対称律、推移律を満たし、(教科書側注) 比較不能な要素対をもつ 半順序関係
教科書p.187■いくつかの順序関係の例 𝒩上の約数関係 ・𝑥∣𝑦 : 𝑥 は 𝑦 の約数である 反射律、反対称律、推移律を満たし、(教科書側注) 比較不能な要素対をもつ 半順序関係 12 8 6 3 2 1 最小元

32 冪集合上の包含関係「⊆」 普遍集合𝑈 の冪集合 𝒫(𝑈)上の包含関係 反射律、反対称律、推移律を満たし、(教科書側注)
教科書p.187■いくつかの順序関係の例 冪集合上の包含関係「⊆」 普遍集合𝑈 の冪集合 𝒫(𝑈)上の包含関係 反射律、反対称律、推移律を満たし、(教科書側注) 比較不能な要素対をもつ 半順序関係 𝑈={𝑎,𝑏,𝑐}の場合 𝑈={𝑎,𝑏,𝑐} 最大元 {𝑎,𝑏} {𝑏,𝑐} {𝑎,𝑐} {𝑎} {𝑏} {𝑐} 最小元

33 𝑎 1 , 𝑏 1 ≤ 𝐴,𝐵 𝑎 2 , 𝑏 2 iff 𝑎 1 ≤ 𝐴 𝑎 2 かつ 𝑏 1 ≤ 𝐵 𝑏 2
教科書p.187■いくつかの順序関係の例 2項組の優越関係 順序集合 (𝐴; ≤ 𝐴 ), (𝐵; ≤ 𝐵 )に対して、𝐴×𝐵 上の関係「 ≤ 𝐴,𝐵 」 𝑎 1 , 𝑏 1 ≤ 𝐴,𝐵 𝑎 2 , 𝑏 2  iff 𝑎 1 ≤ 𝐴 𝑎 2 かつ 𝑏 1 ≤ 𝐵 𝑏 2 (𝒩,≤)に対する 𝒩 2 上の関係 ≤ 2 (1,5) (2,4) (3,3) (4,2) (5,1) (1,4) (2,3) (3,2) (4,1) (1,3) (2,2) (3,1) (1,2) (2,1) (1,1)

34 派生語関係 単語(文字列) 𝑐 1 𝑐 2 … 𝑐 𝑛 の中の関係
教科書p.198■演習の解1 派生語関係 単語(文字列) 𝑐 1 𝑐 2 … 𝑐 𝑛 の中の関係   𝑐 1 … 𝑐 𝑖 ≤ 𝑐 1 … 𝑐 𝑖 𝑐 𝑖+1 … 𝑐 𝑖+𝑗 𝑗≥0 𝑤≤𝑤𝑤′ affectation affect affected affectedness affectedly affecting affectingly affection affective affectionate affectionately

35 辞書式順序 派生語関係の拡張 (i.e. 𝑤≤𝑤𝑤′ に加えて) ・文字の集合𝐶の中の全順序関係「 ≥ 𝐶 」に基づいて
𝑐 𝑖 ≠ 𝑐′ 𝑖 , 𝑐 𝑖 ≤ 𝐶 𝑐′ 𝑖 ならば   𝑐 1 … 𝑐 𝑖−1 𝑐 𝑖 … 𝑐 𝑗 ≤ 𝑐 1 … 𝑐 𝑖−1 𝑐′ 𝑖 … 𝑐 ′ 𝑘 (𝑖≥1) a, able, all, angry, arrive, bad, beautiful, best, big, black, buy,careful, cold, collect, come, cook, cool, dance, dark, do, drink,early, easy, eat, enjoy, every, famous, fast, favorite, free, friendly,full, funny, get, give, go, good, green, happy, have, help, high,home, honest, hot, hungry, ill, live, long, look, make,many, meet, much, new, next, nice, no, noise, open, play, poor,popular, put, quiet, read, red, sad, sell, send, shy, short, sick,sing, slow, smart, small, some,stop, strong, study, swim, tall, true, try, up, use, visit, wait, walk,want, wash, warm, yesterday 全順序

36 教科書p.190■上限と下限 順序集合の最大と最小 極大元 最大元なし a b c d e f g i 最小元

37 順序集合の最大と最小 順序集合(𝑋; ≦) において ・極大元:自分より大きい(上位の)他の元を持たない𝑋の元 有限集合の場合1個以上存在
教科書p.190■上限と下限 順序集合の最大と最小 順序集合(𝑋; ≦) において ・極大元:自分より大きい(上位の)他の元を持たない𝑋の元  有限集合の場合1個以上存在 ・最大元:唯一の極大元(もしあれば) max(𝑋) 有限集合かつ全順序の場合必ず存在 ・極小元、最小元(min(𝑋) )も同様 無限集合の場合  𝒩: 最小元1、極大元なし   𝑄 0,1 0以上1以下の有理数の集合 : 最小元0、最大元1   𝑄 0,1 (0以上1未満の有理数の集合): 最小元0、極大元なし

38 上限と下限 順序集合(𝑋; ≦)と、その部分集合𝐴において ・𝐴の上界 𝑈𝑝𝑝𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑎≦𝑥}
教科書p.190■上限と下限 上限と下限 順序集合(𝑋; ≦)と、その部分集合𝐴において ・𝐴の上界 𝑈𝑝𝑝𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑎≦𝑥} ・𝐴の下界 𝐿𝑜𝑤𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑥≦𝑎}

39 教科書p.190■上限と下限 上限と下限 𝑈𝑝𝑝𝑒𝑟(𝐴) 𝐴 𝐿𝑜𝑤𝑒𝑟(𝐴)

40 上限と下限 順序集合(𝑋; ≦)と、その部分集合𝐴において ・𝐴の上界 𝑈𝑝𝑝𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑎≦𝑥}
教科書p.190■上限と下限 上限と下限 順序集合(𝑋; ≦)と、その部分集合𝐴において ・𝐴の上界 𝑈𝑝𝑝𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑎≦𝑥} ・𝐴の上限(最小上界) sup(𝐴)=min(𝑈𝑝𝑝𝑒𝑟(𝐴)) ・𝐴の下界 𝐿𝑜𝑤𝑒𝑟(𝐴)={𝑥 | 𝑥∈𝑋, すべての𝑎∈𝐴に対し𝑥≦𝑎} ・𝐴の下限(最大下界) inf(𝐴)=max(𝐿𝑜𝑤𝑒𝑟(𝐴))

41 教科書p.190■上限と下限 上限と下限 𝑈𝑝𝑝𝑒𝑟(𝐴) sup⁡(𝐴) 𝐴 inf⁡(𝐴) 𝐿𝑜𝑤𝑒𝑟(𝐴)

42 上限と下限 𝑈𝑝𝑝𝑒𝑟(𝐴) sup⁡(𝐴) max⁡(𝐴) 𝐴 min⁡(𝐴) inf⁡(𝐴) 𝐿𝑜𝑤𝑒𝑟(𝐴)

43 演習 𝑈={1,2,3,8,12,18,36}における約数関係を「≤」として、 順序集合 𝑈;≤ について次の問いに答えよ
教科書p.196■演習問題 演習 𝑈={1,2,3,8,12,18,36}における約数関係を「≤」として、 順序集合 𝑈;≤ について次の問いに答えよ 𝑈 における約数関係による順序集合をハッセ図に描け 極大元、極小元が存在すればそれを答えよ。また、最 大元、最小元が存在すればそれを答えよ 𝑈 の部分集合 2,18 , 3,36 , 8,18 , 2,3 , {12,18}につい て、それぞれに上界、 下界が存在すればそれを答え よ。また上限、下限が存在すればそれを答えよ。

44 まとめ 同値関係(反射、対称、推移) ・集合の要素をなんらかの観点で「同じとみなせるもの」に分類
同値類:同じとみなせる要素の集合 ⇒ 代表元 商集合:同値類の集合 ・同値関係の例 𝑛を法として合同 商集合  𝒵 𝑛 ={ 0 𝑛 , 1 𝑛 ,…, 𝑛−1 𝑛 } 𝒵 𝑛 上の加減乗除 順序関係(反射、反対称、推移) ・集合の要素間の大小(上下、前後)関係を規定 比較不能な要素対のあるのが半順序、ないのが全順序 ハッセ図による表現 ・約数関係、包含関係、2項組の優越関係、 派生語関係、辞書式順序 ・極大(小)元、最大(小)元、上(下)界、上(下)限


Download ppt "集合の中の二項関係 ・反射律、対称律、推移律、反対称律 ・同値関係 ・順序関係"

Similar presentations


Ads by Google