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

1Corresponding lectures講義こうぎ

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

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.

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.

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

5.1Problem

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

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.