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

Order relations順序関係じゅんじょかんけい and lattices束そく: basic exercises

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

1Corresponding lectures講義こうぎ

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

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

2Exercise strategy

For an order relation順序関係じゅんじょかんけい, check reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, and transitivity推移性すいいせい. To decide whether it is a total order全順序ぜんじゅんじょ, check whether every pair of elements is 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である。

3Problem 1

Order $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2\left\}\right)$$\mathcal P(\{1,2\}) by $$\subseteq$$\subseteq. Explain why this relation is a partial order半順序関係はんじゅんじょかんけい.

3.1Answer

For every $$B$$B, $$B\subseteq B$$B\subseteq B, so reflexivity反射性はんしゃせい holds. If $$B\subseteq C$$B\subseteq C and $$C\subseteq B$$C\subseteq B, then $$B=C$$B=C by extensionality外延性がいえんせい, so antisymmetry反対称性はんたいしょうせい holds. If $$B\subseteq C$$B\subseteq C and $$C\subseteq D$$C\subseteq D, then $$B\subseteq D$$B\subseteq D, so transitivity推移性すいいせい holds. Therefore the relation is a partial order.

3.2Explanation

Inclusion包含ほうがん is a standard example of a partial order半順序関係はんじゅんじょかんけい.

3.3Common mistake

Do not try to prove symmetry対称性たいしょうせい. Order relations require antisymmetry反対称性はんたいしょうせい, not symmetry.

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ではないことが分わかる。半順序関係はんじゅんじょかんけいであることと全順序関係ぜんじゅんじょかんけいであることを混同こんどうしない。

4Problem 2

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

4.1Answer

The sets $$\left\{1\right\}$$\{1\} and $$\left\{2\right\}$$\{2\} do not contain each other. Therefore there are two elements that are not comparable比較可能ひかくかのう. Hence this is not a total order.

4.2Explanation

In a total order全順序関係ぜんじゅんじょかんけい, every pair of elements must be comparable. One incomparable pair is enough for failure.

4.3Common mistake

Do not conclude that every partial order半順序関係はんじゅんじょかんけい is also a 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があるとは限かぎらない。全員ぜんいんと比較ひかくできるかが分わかれ目めである。

5Problem 3

Order $$P=\left\{\right\{1\},\{2\},\{1,2\left\}\right\}$$P=\{\{1\},\{2\},\{1,2\}\} by $$\subseteq$$\subseteq. Find the maximal element極大元きょくだいげん and the greatest element最大元さいだいげん.

5.1Answer

The set $$\{1,2\}$$\{1,2\} contains every element元げん of $$P$$P, so it is the greatest element最大元さいだいげん. A greatest element has no element above it, so it is also maximal極大きょくだい. Therefore both the maximal element and the greatest element are $$\{1,2\}$$\{1,2\}.

5.2Explanation

When a greatest element最大元さいだいげん exists, it is always a maximal element極大元きょくだいげん. The converse is not true in general.

5.3Common mistake

Do not assume that maximal elements and greatest elements are always the same concept.

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を逆ぎゃくにする誤あやまりである。

6Problem 4

In $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(\{1,2,3\}),\subseteq )$$(\mathcal P(\{1,2,3\}),\subseteq), find $$B\vee C$$B\vee C and $$B\wedge C$$B\wedge C for $$B=\{1,2\}$$B=\{1,2\} and $$C=\{2,3\}$$C=\{2,3\}.

6.1Answer

In the inclusion order包含順序ほうがんじゅんじょ, the join結むすび is union和集合わしゅうごう. Hence $$B\vee C=B\cup C=\{1,2,3\}$$B\vee C=B\cup C=\{1,2,3\}.

The meet交まじわり is intersection共通部分きょうつうぶぶん. Hence $$B\wedge C=B\cap C=\left\{2\right\}$$B\wedge C=B\cap C=\{2\}.

6.2Explanation

In a lattice束そく, the join結むすび is the least common upper bound上界じょうかい, and the meet交まじわり is the greatest common lower bound下界かかい.

6.3Common mistake

Do not interchange join and 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を取とり違ちがえやすい。

7Problem 5

Order the positive integers整数せいすう by the divisibility order整除順序せいじょじゅんじょ. Find $$6\vee 10$$6\vee10 and $$6\wedge 10$$6\wedge10.

7.1Answer

In the divisibility order整除順序せいじょじゅんじょ, the join結むすび is the least common multiple最小公倍数さいしょうこうばいすう, and the meet交まじわり is the greatest common divisor最大公約数さいだいこうやくすう. Therefore $$6\vee 10=30$$6\vee10=30 and $$6\wedge 10=2$$6\wedge10=2.

7.2Explanation

In the divisibility order, being “above” means being a multiple. Therefore the least common upper element is the least common multiple.

7.3Common mistake

Do not use the usual numerical order and write $$6\vee 10=10$$6\vee10=10. The order here is divisibility, not the usual $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le.

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 であることを証明しょうめいせよ。

8Proof exercise: restriction of an order and monotonicity単調性たんちょうせい of meet

8.1Problem

Let $$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) be a partially ordered set半順序集合はんじゅんじょしゅうごう and let $$Y\subseteq X$$Y\subseteq X. Prove that the restriction to $$Y$$Y is a partial order半順序はんじゅんじょ. Also prove that in a lattice束そく, if $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, then $$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は演算えんざんが順序じゅんじょを保存ほぞんする例れいである。

8.2Answer

For the restriction to $$Y$$Y, reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, and transitivity推移性すいいせい are inherited from $$X$$X and applied only to elements元げん of $$Y$$Y.

For meet, $$a\wedge c$$a\wedge c is a lower bound下界かかい of $$a$$a and $$c$$c. Since $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, we have $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\wedge c\le b and $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}c$$a\wedge c\le c. Thus $$a\wedge c$$a\wedge c is a lower bound of $$b$$b and $$c$$c. Since $$b\wedge c$$b\wedge c is the greatest lower bound最大下界さいだいかかい of $$b$$b and $$c$$c, we get $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c.

8.3Explanation

Restricting an order is an example where the axioms remain valid. The monotonicity単調性たんちょうせい of meet is an example of an operation preserving the order.