ヤバイ補題

電波通信

HTML変換日：2026年7月26日

この文章では $\mathbb{Z}_{\geq 0}=\{n\in\mathbb{Z}\ |\ n\geq 0\},\ \mathbb{Z}_{+}=\{n\in% \mathbb{N}\ |\ n>0\}$ とする。また $A=(a_{1},a_{2},\cdots,a_{k}),\ B=(b_{1},b_{2},\cdots,b_{k})$ について

[A,B]=\sum_{i=1}^{k}a_{i}b_{i}

と書くことにする。

定理 1 (The Horrible Lemma).

$\mathbb{Z}_{\geq 0}^{n}$ の任意の有限部分集合 $F$ に対して $w=(w_{1},w_{2},\cdots,w_{n})\in\mathbb{Z}_{+}^{n}$ が存在して次を充たす。

(1)		$\displaystyle w_{n}=1$
(2)		$\displaystyle p,q\in F,p\neq q\Longrightarrow[w,p]\neq[w,q]$

証明.

$\pi_{i}:\mathbb{Z}_{\geq 0}^{n}\to\mathbb{Z}_{\geq 0}$ を第 $i$ 成分への射影とする。さて

G=\{\pi_{i}(a)\ |\ a\in F\ i=1,2,\cdots n\}

と定義する。つまり $F$ の元の成分全体の集合である。 $F$ が有限集合であるから $G$ も有限集合である。今

L=1+\max G

と定義する。このとき

w=(L^{n-1},L^{n-2},\cdots,L^{0})

と置けば条件は充たされる。まず条件 $(1)$ に関しては明らかである。ところで $\mathbb{Z}_{\geq 0}^{n}$ に辞書式順序 $\prec$ を導入するつまり

(a_{1},a_{2},\cdots,a_{n})\prec(b_{1},b_{2},\cdots,b_{n})\iff\exists k\ a_{1}=% b_{1},a_{2}=a_{2},\cdots,a_{k-1}=b_{k-1},a_{k}<b_{k}

という順序である。よく知られているようにこの順序は線型順序である。

$A=(a_{1},a_{2},\cdots,a_{n})\in F$ に対して $L>\max G$ であるから

[w,A]=a_{1}L^{n-1}+a_{2}L^{n-2}+\cdots+a_{n}

は $L$ を底とした位取り進数表記になっている。よってよく知られているように、 $A,B\in F,A\prec B$ ならば

[w,A]<[w,B]

である。¹¹1要するに $L$ 進数は頭から位の大きい順に位毎に大きさを比べていけば大きさの大小がわかるということである。例えば10進数で4625と4689は一番大きい位から順に $4=4,6=6,2<8$ となるので $4625<4689$ という風に大小関係がわかるのである。3244と23は23を0023と考えれば $0<3$ から $23<3244$ がわかる。 $\prec$ が線型順序であることを思い出せば $(2)$ が充たされることはすぐわかる。 ∎