順序関係じゅんじょかんけいorder relationと束そくlattice - 基本演習きほんえんしゅう

1対応たいおうする講義こうぎlecture

2演習えんしゅう方針ほうしん

順序関係じゅんじょかんけいorder relationでは、反射性はんしゃせいreflexivity、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityを確認かくにんする。全順序ぜんじゅんじょtotal orderかどうかは、任意にんいの 2 元げんが比較可能ひかくかのうcomparableかで判定はんていする。

3問題もんだい 1

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2\left\}\right)$$\mathcal P(\{1,2\}) を $$\subseteq$$\subseteq で順序じゅんじょづける。この関係かんけいが半順序関係はんじゅんじょかんけいpartial orderであることを説明せつめいせよ。

3.1解答かいとう

任意にんいの $$B$$B について $$B\subseteq B$$B\subseteq B なので反射性はんしゃせいreflexivityが成立せいりつする。$$B\subseteq C$$B\subseteq C かつ $$C\subseteq B$$C\subseteq B なら外延性がいえんせいextensionalityより $$B=C$$B=C なので反対称性はんたいしょうせいantisymmetryが成立せいりつする。$$B\subseteq C$$B\subseteq C かつ $$C\subseteq D$$C\subseteq D なら $$B\subseteq D$$B\subseteq D なので推移性すいいせいtransitivityが成立せいりつする。したがって半順序関係はんじゅんじょかんけいpartial orderである。

3.2解説かいせつ

包含ほうがんinclusionは半順序関係はんじゅんじょかんけいpartial orderの基本例きほんれいである。

3.3よくある誤あやまり

対称性たいしょうせいsymmetryを確認かくにんしようとする誤あやまりである。順序じゅんじょで必要ひつようなのは反対称性はんたいしょうせいantisymmetryである。

4問題もんだい 2

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2\left\}\right)$$\mathcal P(\{1,2\}) の包含順序ほうがんじゅんじょinclusion orderは全順序関係ぜんじゅんじょかんけいtotal orderか。

4.1解答かいとう

$$\left\{1\right\}$$\{1\} と $$\left\{2\right\}$$\{2\} は、どちらも相手あいてを含ふくまない。したがって比較可能ひかくかのうcomparableではない 2 元げんが存在そんざいする。よって全順序関係ぜんじゅんじょかんけいtotal orderではない。

4.2解説かいせつ

全順序関係ぜんじゅんじょかんけいtotal orderでは任意にんいの 2 元げんが比較ひかくできる必要ひつようがある。1 組くみでも比較不能ひかくふのうなら失敗しっぱいである。

4.3よくある誤あやまり

半順序関係はんじゅんじょかんけいpartial orderだから全順序関係ぜんじゅんじょかんけいtotal orderでもあると判断はんだんする誤あやまりである。

比較不能ひかくふのうincomparableな 1 組くみを見みつければ、全順序関係ぜんじゅんじょかんけいtotal orderではないことが分わかる。半順序関係はんじゅんじょかんけいであることと全順序関係ぜんじゅんじょかんけいであることを混同こんどうしない。

5問題もんだい 3

$$P=\left\{\right\{1\},\{2\},\{1,2\left\}\right\}$$P=\{\{1\},\{2\},\{1,2\}\} を $$\subseteq$$\subseteq で順序じゅんじょづける。極大元きょくだいげんmaximal elementと最大元さいだいげんgreatest elementを求もとめよ。

5.1解答かいとう

$$\{1,2\}$$\{1,2\} は $$P$$P のすべての元げんelementを含ふくむので最大元さいだいげんgreatest elementである。最大元さいだいげんgreatest elementは自分じぶんより上うえの元げんelementを持もたないため、極大元きょくだいげんmaximal elementでもある。したがって極大元きょくだいげんmaximal elementは $$\{1,2\}$$\{1,2\}、最大元さいだいげんgreatest elementも $$\{1,2\}$$\{1,2\} である。

5.2解説かいせつ

最大元さいだいげんgreatest elementが存在そんざいするとき、それは必かならず極大元きょくだいげんmaximal elementである。ただし逆ぎゃくは一般いっぱんに成立せいりつしない。

5.3よくある誤あやまり

極大元きょくだいげんmaximal elementと最大元さいだいげんgreatest elementを常つねに同おなじと考かんがえる誤あやまりである。

最大元さいだいげんgreatest elementは存在そんざいすれば極大元きょくだいげんmaximal elementであるが、極大元きょくだいげんmaximal elementがあるからといって必かならず最大元さいだいげんgreatest elementがあるとは限かぎらない。全員ぜんいんと比較ひかくできるかが分わかれ目めである。

6問題もんだい 4

$$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(\{1,2,3\}),\subseteq )$$(\mathcal P(\{1,2,3\}),\subseteq) において、$$B=\{1,2\}$$B=\{1,2\}、$$C=\{2,3\}$$C=\{2,3\} の $$B\vee C$$B\vee C と $$B\wedge C$$B\wedge C を求もとめよ。

6.1解答かいとう

包含順序ほうがんじゅんじょinclusion orderでは、結むすびjoinは和集合わしゅうごうunionである。したがって $$B\vee C=B\cup C=\{1,2,3\}$$B\vee C=B\cup C=\{1,2,3\} である。

交まじわりmeetは共通部分きょうつうぶぶんintersectionである。したがって $$B\wedge C=B\cap C=\left\{2\right\}$$B\wedge C=B\cap C=\{2\} である。

6.2解説かいせつ

束そくlatticeでは、結むすびjoinは共通きょうつうの上界じょうかいupper boundの最小さいしょう、交まじわりmeetは共通きょうつうの下界かかいlower boundの最大さいだいである。

6.3よくある誤あやまり

結むすびjoinと交まじわりmeetを逆ぎゃくにする誤あやまりである。

7問題もんだい 5

正せいの整数せいすうintegerを整除順序せいじょじゅんじょdivisibility orderで順序じゅんじょづける。$$6\vee 10$$6\vee10 と $$6\wedge 10$$6\wedge10 を求もとめよ。

7.1解答かいとう

整除順序せいじょじゅんじょdivisibility orderでは、結むすびjoinは最小公倍数さいしょうこうばいすうleast common multiple、交まじわりmeetは最大公約数さいだいこうやくすうgreatest common divisorである。したがって $$6\vee 10=30$$6\vee10=30、$$6\wedge 10=2$$6\wedge10=2 である。

7.2解説かいせつ

整除順序せいじょじゅんじょdivisibility orderでは「上うえにある」とは「倍数ばいすうである」ことを意味いみする。したがって最小さいしょうの共通きょうつうの上うえは最小公倍数さいしょうこうばいすうleast common multipleである。

7.3よくある誤あやまり

通常つうじょうの大小だいしょうで考かんがえて $$6\vee 10=10$$6\vee10=10 とする誤あやまりである。ここでの順序じゅんじょは通常つうじょうの $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le ではなく整除順序せいじょじゅんじょdivisibility orderである。

整除順序せいじょじゅんじょdivisibility orderでは上うえが倍数ばいすう、下したが約数やくすうを意味いみする。通常つうじょうの大小だいしょうに戻もどして考かんがえると、結むすびjoinと交まじわりmeetを取とり違ちがえやすい。

8証明しょうめい演習えんしゅう：順序じゅんじょの制限せいげんと meet の単調性たんちょうせいmonotonicity

8.1問題もんだい

$$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) が半順序集合はんじゅんじょしゅうごうpartially ordered setで、$$Y\subseteq X$$Y\subseteq X とする。$$Y$$Y への制限せいげんが半順序はんじゅんじょpartial orderになることを証明しょうめいせよ。また、束そくlatticeで $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b なら $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c であることを証明しょうめいせよ。

8.2解答かいとう

$$Y$$Y の制限せいげんでは、反射性はんしゃせいreflexivity、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityはいずれも $$X$$X で成立せいりつする性質せいしつを $$Y$$Y の元げんelementに対たいして使つかうだけでよい。

meet について、$$a\wedge c$$a\wedge c は $$a$$a と $$c$$c の下界かかいlower boundである。$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b なので、$$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\wedge c\le b かつ $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}c$$a\wedge c\le c である。したがって $$a\wedge c$$a\wedge c は $$b$$b と $$c$$c の下界かかいである。$$b\wedge c$$b\wedge c は $$b$$b と $$c$$c の最大下界さいだいかかいgreatest lower boundなので、$$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c である。

8.3解説かいせつ

順序じゅんじょの制限せいげんは公理こうりが壊こわれない例れいであり、meet の単調性たんちょうせいmonotonicityは演算えんざんが順序じゅんじょを保存ほぞんする例れいである。