数理論理学・集合論の問題

1. 半束と半順序の対応

${\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ を満たす構造は、べき等・可換・結合的な演算をもつ。これを（交わり）半束という。

半束 $(A,\cdot )$ に対して、$x\le y⟺x\cdot y=x$ と定める。
- 反射律は ${\sigma }_1$ から従う。
- 反対称律は ${\sigma }_2$ から従う。$x\cdot y=x$ かつ $y\cdot x=y$ なら $x=x\cdot y=y\cdot x=y$ となる。
- 推移律は ${\sigma }_3$ から従う。$x\cdot y=x,y\cdot z=y$ なら $x\cdot z=(x\cdot y)\cdot z=x\cdot (y\cdot z)=x\cdot y=x$ となる。

したがって $\le$ は半順序である。さらに、$(x\cdot y)\cdot x=x\cdot y$、$(x\cdot y)\cdot y=x\cdot y$ より $x\cdot y$ は $x,y$ の下界であり、$z\le x,z\le y$ なら $z\cdot (x\cdot y)=(z\cdot x)\cdot y=z\cdot y=z$ より $z\le x\cdot y$ である。よって $x\cdot y$ は $x,y$ の最大下界（交わり）$x\wedge y$ である。

逆に、任意の 2 元が交わりをもつ半順序（交わり半束）が与えられれば、$x\cdot y=x\wedge y$ によって ${\sigma }_1,{\sigma }_2,{\sigma }_3$ を満たす演算が得られる。この 2 つの対応は互いに逆である。よって、$A$ 上の ${\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ のモデルは、$A$ 上の交わり半束である半順序と 1 対 1 に対応する。

2. ${\sigma }_4$ の意味

$e\cdot y=y$ は $y\cdot e=y$、すなわち $y\le e$ と同じである。よって「すべての $y$ で $e\cdot y=y$」は $e$ が最大元であることを意味し、${\sigma }_4$ は「最大元が存在しない」ことを意味する。

3. $A$ 上の交わり半束の数え上げ

有限な交わり半束には最小元が存在する（全元の積 $1\cdot 2\cdot 3\cdot 4$ はすべての元の下界である）。

逆に、$A$ 上の半順序が最小元 $0$ をもつとき、それは必ず交わり半束になることを示す。$Q=A\setminus \{0\}$（3 元）とし、$x,y\in A$ をとる。
- $x,y$ が比較可能なとき：小さい方が $x,y$ の交わりである。
- $x,y$ が比較不能なとき：$x,y$ はともに $Q$ の相異なる元である。$x,y$ の共通下界のうち $0$ 以外のもの $z$ は $Q$ に属し、$z\ne x$, $z\ne y$（もし $z=x$ なら $x\le y$ となり比較不能に反する）なので、$z$ は $Q$ の第 3 の元に限られる。したがって共通下界全体は $\{0\}$ または $\{0,z\}$ である。前者なら $0$ が交わり、後者なら $0<z$ なので $z$ が交わりである。

いずれの場合も交わりが存在する。したがって、$A$ 上の交わり半束は次の 2 つの選び方で決まる。
- 最小元 $0$ の選び方：$4$ 通り
- 残り 3 元 $Q$ 上の半順序（ラベル付き）の選び方（$0$ は $Q$ のすべての元より小さいと定める）

3 元集合上のラベル付き半順序は次のとおりである。
- 鎖：$3!=6$ 個（最大元あり）
- 反鎖：$1$ 個（最大元なし）
- 比較可能な 2 元と孤立した 1 元（$a<b$, $c$）：$3\times 2=6$ 個（最大元なし）
- $a<b,a<c$ 型：$3$ 個（極大元が 2 つあり、最大元なし）
- $a<c,b<c$ 型：$3$ 個（最大元あり）

合計は $19$ 個である。

$0$ は $Q$ の元より小さいので $A$ の最大元にはなりえない。よって $A$ が最大元をもつことと $Q$ が最大元をもつことは同値である。$Q$ が最大元をもたないものは $1+6+3=10$ 個ある。

4. 結論

求める個数は $4\times 10=40$ である。

（参考：${\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ だけのモデルは $4\times 19=76$ 個である。そのうち最大元をもつものが $4\times 9=36$ 個あるので、$76-36=40$ となり、結果と一致する。）

冪等かつ可換な半群は、$x\le y⟺x\cdot y=x$ で定まる順序による meet 半束と同じものである。このとき ${\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ を満たす構造は、4 元集合 $\{1,2,3,4\}$ 上のラベル付き meet 半束と一対一に対応する。

${\sigma }_4$ は単位元 $e$ が存在しないことを表す。可換なので $e\cdot y=y$ がすべての $y$ で成り立つことは、$e$ が最大元であることと同値である。よって求めるものは、最大元をもたない 4 元の meet 半束の個数である。

有限 meet 半束には最小元 $0$ が必ず存在する。残りの 3 元の順序集合を $P$ とすると、全体は $P$ の下に $0$ を付けたものである。$P$ の 2 元が比較不能なとき、共通の下界は $P$ 内には高々 1 つ（残りの 1 元）しかないので、meet は常に存在する。したがって、$P$ は 3 元のどんな半順序集合でもよい。

最大元がないことは、全体の極大元が 2 個以上であること、つまり $P$ の極大元が 2 個以上であることと同値である。3 元半順序集合の同型類 5 個のうち、これを満たすのは次の 3 個である。

1. 反鎖（$0$ の上に原子が 3 個）。自己同型群の位数は 6 なので、ラベル付けは $24/6=4$ 通り。
2. $0<a<b$ と $0<c$。自己同型は自明なので、ラベル付けは 24 通り。
3. $0<a$ かつ $a<b$, $a<c$。自己同型群の位数は 2 なので、ラベル付けは 12 通り。

残りの 2 個（鎖と $\Lambda$ 型）は最大元をもつので除く。

合計は $4+24+12=40$ である。