写像の分類(1) - 非専門的シンギュラリティー研究所

「エレファントな整数論(21) - エレファント・ビジュアライザー調査記録」、「エレファントな整数論(23) - エレファント・ビジュアライザー調査記録」で写像を分類して自然数を表そうとしていました。「人工知能的写像の理論(1) - エレファント・ビジュアライザー調査記録」に引き継いだのですが分類はまだやっていないので、新しく「写像の分類」という項目を作ることにしました。ChatGPT で調べていきます。

エレファントな整数論の内容

$M$ を集合、 $s: M \to M$ を写像とします。 $x \in M$ に対して $s^*(x)$ を $x$ を含み $s$ に関して閉じた最小の $M$ の部分集合とします。 $x \le y \iff y \in s^*(x)$ と定義します。 $x \le y$ かつ $y \le x$ であるとき $x, y$ は同値ということにします。 $x_0 \in M$ をとり $N = s^*(x_0)$ とおきます。

以下の条件を考えます。

$(N_1)$ 任意の $x \in N$ に対して $s(x) \ne x$
$(N_2)$ 任意の $x \in N$ に対して $s(x) \ne x_0$
$(N_3)$ $N$ 上で $s$ は単射
$(N_4)$ $N$ 上で $\le$ は全順序
$(N_5)$ $N$ は無限集合
$(N_6)$ $X \subseteq N$ かつ $X \ne \varnothing$ ならば $X$ は極小元を持つ
$(N_7)$ 任意の $x \in N$ に対して $x$ と同値である $N$ の元は $x$ のみ
$(N_8)$ 任意の $x \in N$ に対して $s(x) \not\le x$

これらの条件により以下の表のようにタイプ $T_1$ から $T_5$ に分類することができます。

タイプ	$N_1$	$N_2$	$N_3$	$N_4$	$N_5$	$N_6$	$N_7$	$N_8$	図式
$T_1 = N_1 \land N_2 \land N_3$	○	○	○	○	○	○	○	○	$0 \to 1 \to \cdots$
$T_2 = N_1 \land N_2 \land \neg N_3$	○	○	×	×	×	×	×	×	$0 \to 1 \to \cdots \to n \to \cdots \to n$
$T_3 = N_1 \land \neg N_2$	○	×	○	×	×	×	×	×	$0 \to 1 \to \cdots \to 0$
$T_4 = \neg N_1 \land N_2$	×	○	×	○	×	○	○	×	$0 \to 1 \to \cdots \to n \to n$
$T_5 = \neg N_1 \land \neg N_2$	×	×	○	○	×	○	○	×	$0 \to 0$

(1) $N_2 \land N_3 \implies N_4$
(2) $N_1 \land N_4 \implies N_3$
(3) $N_1 \land N_4 \implies N_2$
(4) $\neg N_1 \implies N_4$
(5) $N_2 \land N_3 \implies N_5$
(6) $N_1 \land N_4 \implies N_6$
(7) $N_4 \iff N_7$
(8) $N_5 \iff N_8$
(9) $N_5 \implies N_2$
(10) $N_5 \implies N_3$
(11) $\neg N_2 \implies N_3$
(12) $N_2 \land N_3 \implies N_1$
(13) $N_4 \iff N_6$

が成り立ちます。

これを ChatGPT で調べていきます。

$\le$ は前順序となることを証明してください

以下の結果となりました。

この問題の解決には、以下の手順で進めます：
1. 前順序の定義を確認する。
前順序 $\leq$ は以下を満たす関係です：

反射律: 任意の $x \in M$ に対して $x \leq x$ 。

推移律: 任意の $x, y, z \in M$ に対して、 $x \leq y$ かつ $y \leq z$ ならば $x \leq z$ 。

2. 反射律の証明。
$x \in s^*(x)$ を示す。
3. 推移律の証明。
$y \in s^*(x)$ かつ $z \in s^*(y)$ のとき $z \in s^*(x)$ を示す。

証明

反射律

$x \leq x$ が成立することを示します。
定義によれば、 $x \leq x \iff x \in s^*(x)$ です。
$s^*(x)$ は $x$ を含み、 $s$ に関して閉じた最小の部分集合なので、明らかに $x \in s^*(x)$ が成り立ちます。
したがって、反射律が成立します。

推移律

任意の $x, y, z \in M$ に対して、
$x \leq y$ かつ $y \leq z$ ならば $x \leq z$ を示します。
まず定義を展開すると、以下を示す必要があります：

$y \in s^*(x)$ （つまり $x \leq y$ ）。

$z \in s^*(y)$ （つまり $y \leq z$ ）。

このとき、 $z \in s^*(x)$ （つまり $x \leq z$ ）を示す。

$s^*(x)$ は $x$ を含み、 $s$ に関して閉じた最小の部分集合です。
また、 $s^*(x)$ は $s^*(y)$ を包含している必要があります。
具体的に説明すると：
1. $y \in s^*(x)$ より、 $s^*(y) \subseteq s^*(x)$ が成り立つ。
2. $z \in s^*(y)$ なので、 $z \in s^*(x)$ が従います。
したがって、推移律も成立します。

結論

以上により、関係 $\leq$ は前順序であることが示されました。

(1) から (4) までについて証明してもらいました。

(1) $(N_2)$ かつ $(N_3)$ ならば $(N_4)$

概略：

まず、 $\leq$ が前順序であることから、反射律と推移律は成立しています。従って、全順序を示すためには、任意の $x, y \in N$ に対して、
$\displaystyle x \leq y \text{ または } y \leq x$
が成立することを示せば十分です。

証明：

$N = s^*(x_0)$ であり、これは $x_0$ を含み $s$ に関して閉じた最小の部分集合なので、 $N$ の任意の $x \in N$ に対して $x, s(x), s^2(x), \dots$ のすべてが $N$ に含まれます。

$(N_3)$ より、 $s$ は $N$ 上で単射です。したがって、 $s^k(x) = s^m(y)$ のような形での重複は存在しません。

$(N_2)$ より、 $s(x) \neq x_0$ なので、 $x_0$ に戻るような経路は存在せず、 $s$ -列は線形に並ぶことになります。

この結果、任意の $x, y \in N$ に対して、どちらかが他方の $s$ -列の先頭か途中に位置します。よって、
$\displaystyle x \leq y \text{ または } y \leq x$
が成立し、 $\leq$ は全順序であることが示されました。

(2) $(N_1)$ かつ $(N_4)$ ならば $(N_3)$

概略：

$(N_3)$ を示すためには、任意の $x, y \in N$ に対して $s(x) = s(y)$ ならば $x = y$ が成立することを示せば十分です。

証明：

$(N_1)$ より、任意の $x \in N$ に対して $s(x) \neq x$ が成立します。つまり、 $s$ は自己ループを持ちません。

$(N_4)$ より、 $\leq$ は $N$ 上で全順序であり、任意の $x, y \in N$ に対して $x \leq y$ または $y \leq x$ が成立します。

仮に $s(x) = s(y)$ とすると、次のように考えられます：
1. $\leq$ の全順序性より、 $x \leq y$ または $y \leq x$ のどちらかが成立します。
2. $x \leq y$ の場合、 $y \in s^*(x)$ であり、 $s(x) = s(y)$ かつ $s$ は閉じた構造を保つので、 $x = y$ が従います。
3. 同様に、 $y \leq x$ の場合も同様に $x = y$ となります。
したがって、 $s(x) = s(y)$ のとき $x = y$ が成立し、 $s$ は単射であることが示されました。

(3) $(N_1)$ かつ $(N_4)$ ならば $(N_2)$

概略：

まず、 $(N_1)$ の仮定により、 $s(x) \neq x$ が任意の $x \in N$ に対して成立します。また、 $(N_4)$ の仮定により、 $\leq$ は全順序であり、任意の $x, y \in N$ に対して $x \leq y$ または $y \leq x$ が成立します。
$s(x_0) \neq x_0$ を仮定に基づき、矛盾なく $s(x) \neq x_0$ を示します。

証明：

仮に $s(x) = x_0$ となる $x \in N$ が存在したとします。

$N = s^*(x_0)$ より、 $x_0 \in N$ であり、全順序 $\leq$ の仮定から、 $x_0 \leq x$ または $x \leq x_0$ が成り立ちます。

$x_0 \leq x$ の場合、 $x_0$ は $s^*(x_0)$ の定義より、 $s(x_0) \in s^*(x_0)$ に含まれるべきですが、これは $s(x) = x_0$ に矛盾します。

$x \leq x_0$ の場合も、同様に $s(x) = x_0$ となることは $s^*(x_0)$ の閉性に矛盾します。

したがって、 $s(x) \neq x_0$ が任意の $x \in N$ に対して成立することが示されました。

(4) $(N_1)$ ではないならば $(N_4)$

概略：

$(N_1)$ ではない、つまり $s(x) = x$ となる $x \in N$ が存在する場合を考えます。このとき、 $x$ を固定点とすることにより、 $\leq$ が全順序となることを示します。

証明：

$s(x) = x$ となる $x \in N$ が存在すると仮定します。

$N = s^*(x_0)$ の定義より、 $x_0 \in N$ であり、全順序 $\leq$ の仮定から、任意の $y \in N$ に対して $x_0 \leq y$ または $y \leq x_0$ が成立します。

また、 $s(x) = x$ である $x$ が $N$ の中に唯一存在する場合、全ての要素は $x$ を基準にして比較可能になります（つまり、 $x_0 \leq x$ かつ $x \leq y$ が任意の $y$ に対して成立する）。

したがって、 $\leq$ が全順序であることが示されました。