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

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

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

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

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

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

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

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

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

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

復習はここまで

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

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

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

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

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

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

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

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

剰余系における乗法 𝒵 𝑛 における乗法「 × 𝑛 」を以下のように定義する 𝑥 𝑛 × 𝑛 𝑦 𝑛 = 𝑥×𝑦 𝑛 教科書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

剰余系における乗法 単位元 𝑥 𝑛 × 𝑛 [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 𝑛 を除く 𝒵 𝑛 のすべての要素に逆元が存在する

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

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

次は順序関係

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

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

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

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

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

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

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

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

𝑎 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)

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

辞書式順序 派生語関係の拡張 (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 全順序

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

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

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

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

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

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

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

演習 𝑈={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}につい て、それぞれに上界、　下界が存在すればそれを答え よ。また上限、下限が存在すればそれを答えよ。

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