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

date2026-07-14document_iddoc_721d03c4234dba7c65b3453691c68b59description半順序、全順序、Hasse図、極大極小、束の join と meet を定義から確認する基本演習である。prerequisites半順序関係と全順序関係 / Hasse図と極大・極小 / 束の基本type問題演習content_typeexercisestatusactive

mathdiscrete-mathexercisepartial-orderlattice

1Corresponding lectures講義こうぎ

data/lecture/math/discrete-math/partial-and-total-orders.lecture.n.md data/lecture/math/discrete-math/hasse-diagrams-and-maximal-minimal-elements.lecture.n.md data/lecture/math/discrete-math/lattice-basics.lecture.n.md

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比較可能ひかくかのう.

3Problem 1

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

3.1Answer

For every $B$ , $B \subseteq B$ , so reflexivity反射性はんしゃせい holds. If $B \subseteq C$ and $C \subseteq B$ , then $B = C$ by extensionality外延性がいえんせい, so antisymmetry反対称性はんたいしょうせい holds. If $B \subseteq C$ and $C \subseteq D$ , then $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.

4Problem 2

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

4.1Answer

The sets ${1}$ and ${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.

5Problem 3

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

5.1Answer

The set ${1, 2}$ contains every element元げん of $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}$ .

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.

6Problem 4

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

6.1Answer

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

The meet交まじわり is intersection共通部分きょうつうぶぶん. Hence $B \land 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.

7Problem 5

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

7.1Answer

In the divisibility order整除順序せいじょじゅんじょ, the join結むすび is the least common multiple最小公倍数さいしょうこうばいすう, and the meet交まじわり is the greatest common divisor最大公約数さいだいこうやくすう. Therefore $6 \lor 10 = 30$ and $6 \land 10 = 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 \lor 10 = 10$ . The order here is divisibility, not the usual $[PARSE ERROR: Undefined("Command(\"le\")")]$ .

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

8.1Problem

Let $(X, [PARSE ERROR: Undefined("Command(\"le\")")])$ be a partially ordered set半順序集合はんじゅんじょしゅうごう and let $Y \subseteq X$ . Prove that the restriction to $Y$ is a partial order半順序はんじゅんじょ. Also prove that in a lattice束そく, if $a [PARSE ERROR: Undefined("Command(\"le\")")] b$ , then $a \land c [PARSE ERROR: Undefined("Command(\"le\")")] b \land c$ .

8.2Answer

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

For meet, $a \land c$ is a lower bound下界かかい of $a$ and $c$ . Since $a [PARSE ERROR: Undefined("Command(\"le\")")] b$ , we have $a \land c [PARSE ERROR: Undefined("Command(\"le\")")] b$ and $a \land c [PARSE ERROR: Undefined("Command(\"le\")")] c$ . Thus $a \land c$ is a lower bound of $b$ and $c$ . Since $b \land c$ is the greatest lower bound最大下界さいだいかかい of $b$ and $c$ , we get $a \land c [PARSE ERROR: Undefined("Command(\"le\")")] b \land 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.