読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

直観主義論理の入り口~Heyting 代数~(その 2)

有界束と完備束

有界

L は自然な方法で半順序集合とみなせることは前回分かりました. そうなると最小元や最大元は存在するのか, は自然な興味の対象になりますし, 当然ながら常に存在するとは限りません.

最小元と最大元がともに存在する束を有界と言います. 束の場合は最小元は 0 で, 最大元は 1 で表すのが習わしです. 最小元と最大元については以下が成り立ちます.

a \vee 0 = a (\Leftrightarrow a \wedge 0 = 0)
a \wedge 1 = a (\Leftrightarrow a \vee 1 = 1)

証明はいずれも簡単なので省略します. 逆に代数的に定義した束 \langle L, \vee, \wedge \rangle で, 上記の性質を満たす 0 \in L1 \in L があれば, 0 が最小元, 1 が最大元になります.

ちなみに最小元も最大元も存在すれば順序の意味では当然一意に定まりますが, 例えば 0 の他に 0' \in La \vee 0' = a を満たすものがあったとすれば
0' = 0' \vee 0 = 0 \vee 0' = 0
となり, そのような元は代数的にも一意に定まります.

さて, L空でない任意の有限部分集合 A = \{a_1, a_2, \dots, a_n\} \subset L については交わりと結び
\bigvee A = a_1 \vee a_2 \vee \dots \vee a_n, \bigwedge A = a_1 \wedge a_2 \wedge \dots \wedge a_n
が自然に定義できます( A = \{a\} のときは \bigvee A = \bigwedge A = a と約束する). なおかつ L の空でない有限部分集合 A, B については
\bigvee(A \cup B) = (\bigvee A) \vee (\bigvee B)
\bigwedge(A \cup B) = (\bigwedge A) \wedge (\bigwedge B)
が成り立つのですが, 仮に B = \emptyset とすると
\bigvee A = \bigvee(A \cup \emptyset) = (\bigvee A) \vee (\bigvee \emptyset)
\bigwedge A = \bigwedge(A \cup \emptyset) = (\bigwedge A) \wedge (\bigwedge \emptyset)
という式が出てきます.

気分としては x = \bigvee \emptyset

  • (\forall a)(a \in \emptyset \Rightarrow a \le x)
  • (\forall y \in L)((\forall a)(a \in \emptyset \Rightarrow a \le y) \Rightarrow x \le y)

を満たすようなものですから, 記号論理の知識がある人ならこれは
(\forall y \in L)(x \le y)
を満たすものでなければならないことがわかるでしょう. つまり xL の最小元でなければならないのです. 同様に \bigwedge \emptyset なるものが存在すれば, それは最大元でなければならないはずです. そこで, 有界束においては
\bigvee \emptyset = 0, \bigwedge \emptyset = 1
とすることで上記の式の整合性が保たれます. 逆に空集合も含めた任意の有限部分集合に交わりと結びが存在するような束は有界束となります.

ちなみに有界でない束を有界束に拡張する方法は至ってシンプルですので省略します.

完備束

ここまでは有限部分集合のみに話を絞っていましたが, 有限とは限らない一般の L の部分集合 A に対して b = \bigvee A (交わり)であるということを

  • (\forall a)(a \in A \Rightarrow a \le b)
  • (\forall x \in L)((\forall a)(a \in A \Rightarrow a \le x) \Rightarrow b \le x)

を満たすものとして定義します. 順序集合的に言えば \bigvee A = \sup A ということです. 結びの定義も同様で, 順序集合的には \bigwedge A = \inf A になります.

もちろん, どちらも一般的には存在しないのですが, これが必ず存在するような束を完備束と言います. 完備束 L には明らかに最小元 0 = \bigwedge L と最大元 1 = \bigvee L が存在するので, 完備束は常に有界束です.

実は完備束においては, 「交わりと最小元」か「結びと最大元」のどちらか一方の存在を仮定すれば, もう一方が定義できます. 例えば交わりと最小元が常に存在するとして, 結びは
\bigwedge A = \bigvee \{x | (\forall a \in A)(x \le a)\} (= \sup A_* = \min (A_*)^*)*1
で定義します. この式の右辺を b と置くとき, 任意の a \in A に対して a \in A \subset (A_*)^* なので b \le a が導かれます. *2

*1:X^* は集合 X の上界の集合, X_* は集合 X の下界の集合を表す.

*2:最小元が存在するのでいかなる A に対しても A_* が空でないことを暗黙のうちに利用しています.