順序同型じゅんじょどうけいorder isomorphismとブール代数だいすうBoolean algebra 基本きほん演習えんしゅう

Order isomorphisms順序同型じゅんじょどうけい and Boolean algebraブール代数だいすう: basic exercises

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

1Corresponding lectures講義こうぎ

2問題もんだい1：順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapを確認かくにんする

$$P=\{1,2,3\}$$P=\{1,2,3\}、$$Q=\{2,4,6\}$$Q=\{2,4,6\} を通常つうじょうの大小だいしょうで順序じゅんじょづける。$$f:P\to Q$$f:P\to Q を $$f\left(x\right)=2x$$f(x)=2x とする。$$f$$f は順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapか。

2.1解答かいとう

$$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y なら $$2x\text{[PARSE ERROR: Undefined("Command("le")")]}2y$$2x\le 2y である。したがって $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y) であり、$$f$$f は順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapである。

2.2解説かいせつ

順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapでは、大小だいしょうの向むきが保たもたれるかを見みる。値あたいの差さが保存ほぞんされる必要ひつようはない。

順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapでは、差さや比ひが保存ほぞんされるかではなく、$$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y から $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y) が必かならず従したがうかを確認かくにんする。

2Problem 1: check an order-preserving map順序保存写像じゅんじょほぞんしゃぞう

Let $$P=\{1,2,3\}$$P=\{1,2,3\} and $$Q=\{2,4,6\}$$Q=\{2,4,6\} be ordered by the usual order. Define $$f:P\to Q$$f:P\to Q by $$f\left(x\right)=2x$$f(x)=2x. Is $$f$$f an order-preserving map順序保存写像じゅんじょほぞんしゃぞう?

2.1Answer

If $$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y, then $$2x\text{[PARSE ERROR: Undefined("Command("le")")]}2y$$2x\le 2y. Hence $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y), so $$f$$f is order-preserving.

2.2Explanation

For an order-preserving map順序保存写像じゅんじょほぞんしゃぞう, check whether the direction of the order is preserved. The difference between values does not have to be preserved.

For an order-preserving map順序保存写像じゅんじょほぞんしゃぞう, do not check whether differences or ratios are preserved. Check that $$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y always implies $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y).

3問題もんだい2：鎖くさりchainと反鎖はんくさりantichainを判定はんていする

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2,3\left\}\right)$$\mathcal P(\{1,2,3\}) を包含ほうがんinclusionで順序じゅんじょづける。次つぎの集合族しゅうごうぞくは鎖くさりchainか、反鎖はんくさりantichainか。

3.1解答かいとう

最初さいしょの集合族しゅうごうぞくでは

なので鎖くさりchainである。

二ふたつ目めの集合族しゅうごうぞくでは、異ことなる 1 元げん集合しゅうごうどうしは互たがいに包含ほうがんしない。したがって反鎖はんくさりantichainである。

3.2解説かいせつ

包含順序ほうがんじゅんじょinclusion orderでは、要素数ようそすうの大小だいしょうだけでなく、実際じっさいに含ふくまれている元げんelementを比較ひかくする必要ひつようがある。

鎖くさりchainかどうかは任意にんいの 2 元げんが比較ひかくできるかで判定はんていし、反鎖はんくさりantichainかどうかは異ことなる 2 元げんが比較不能ひかくふのうかで判定はんていする。要素数ようそすうだけではなく、実際じっさいの包含ほうがんを見みる。

3Problem 2: decide chains鎖くさり and antichains反鎖はんくさり

Order $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2,3\left\}\right)$$\mathcal P(\{1,2,3\}) by inclusion包含ほうがん. Decide whether the following families are chains鎖くさり or antichains反鎖はんくさり.

3.1Answer

For the first family,

so it is a chain鎖くさり.

For the second family, distinct singleton sets do not contain each other. Therefore it is an antichain反鎖はんくさり.

3.2Explanation

In the inclusion order包含順序ほうがんじゅんじょ, compare the actual elements元げん contained in the sets, not only the number of elements.

4問題もんだい3：ド・モルガンの法則De Morgan's lawsを使つかう

全体集合ぜんたいしゅうごうを $$U=\{1,2,3,4,5\}$$U=\{1,2,3,4,5\}、$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{3,4\}$$B=\{3,4\} とする。$$U\setminus (A\cap B)$$U\setminus(A\cap B) と $$(U\setminus A)\cup (U\setminus B)$$(U\setminus A)\cup(U\setminus B) を求もとめ、一致いっちを確認かくにんせよ。

4.1解答かいとう

$$A\cap B=\left\{3\right\}$$A\cap B=\{3\} なので、

である。また

なので、

である。両者りょうしゃは一致いっちする。

4.2解説かいせつ

ド・モルガンの法則De Morgan's lawsは、補集合ほしゅうごうcomplementが共通部分きょうつうぶぶんintersectionを和集合わしゅうごうunionへ変かえることを表あらわす。全体集合ぜんたいしゅうごう $$U$$U を固定こていしないと補集合ほしゅうごうcomplementは定さだまらない。

4Problem 3: use De Morgan's lawsド・モルガンの法則

Let the universal set be $$U=\{1,2,3,4,5\}$$U=\{1,2,3,4,5\}, with $$A=\{1,2,3\}$$A=\{1,2,3\} and $$B=\{3,4\}$$B=\{3,4\}. Find $$U\setminus (A\cap B)$$U\setminus(A\cap B) and $$(U\setminus A)\cup (U\setminus B)$$(U\setminus A)\cup(U\setminus B), and verify that they agree.

4.1Answer

Since $$A\cap B=\left\{3\right\}$$A\cap B=\{3\},

Also,

so

The two sets are equal.

4.2Explanation

De Morgan's lawsド・モルガンの法則 say that complement補集合ほしゅうごう changes an intersection共通部分きょうつうぶぶん into a union和集合わしゅうごう. The universal set $$U$$U must be fixed before complements are determined.

5証明しょうめい演習えんしゅう：補元ほげんcomplementの一意性いちいせいuniqueness

5.1問題もんだい

ブール代数だいすうBoolean algebraで、ある元もと $$x$$x の補元ほげんcomplementが一意いちいであることを証明しょうめいせよ。

5Proof exercise: uniqueness一意性いちいせい of complements補元ほげん

5.1Problem

In a Boolean algebraブール代数だいすう, prove that the complement補元ほげん of an element $$x$$x is unique.

5.2解答かいとう

$$y,z$$y,z がどちらも $$x$$x の補元ほげんcomplementだとする。すると $$x\wedge y=0$$x\wedge y=0、$$x\vee y=1$$x\vee y=1、$$x\wedge z=0$$x\wedge z=0、$$x\vee z=1$$x\vee z=1 である。

同おなじ議論ぎろんで $$z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$z\le y である。よって反対称性はんたいしょうせいantisymmetryより $$y=z$$y=z である。

5.3解説かいせつ

補元ほげんcomplementの一意性いちいせいuniquenessは、ド・モルガンの法則De Morgan's lawsを証明しょうめいするときの土台どだいになる。

5.2Answer

Suppose $$y$$y and $$z$$z are both complements補元ほげん of $$x$$x. Then $$x\wedge y=0$$x\wedge y=0, $$x\vee y=1$$x\vee y=1, $$x\wedge z=0$$x\wedge z=0, and $$x\vee z=1$$x\vee z=1.

The same argument gives $$z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$z\le y. By antisymmetry反対称性はんたいしょうせい, $$y=z$$y=z.

5.3Explanation

The uniqueness一意性いちいせい of complements is the foundation for proving De Morgan's lawsド・モルガンの法則 in a Boolean algebra.