問
$x$ を任意の無理数とする。
集合
S = \left\{nx+m \mid n, m \in \mathbb{Z}\right\}
は $\mathbb{R}$ の中で稠密であることを示せ。
記号と用語
稠密
実数の集合 $S$ が実数 $\mathbb{R}$ の中で稠密であるとは、$S$ が次の条件を満たすことを言う。
\forall a, b \in \mathbb{R}, a < b \implies \exists x \in S\ s.t. a < x < b
鳩の巣原理
10箱の巣箱に11羽の鳩が住んでいるならば、少なくとも1つの箱の中には2羽の鳩がいる、という原理。
直感的にわかりやすく、数学的にも有用なので全人類から好かれている（要出典）
証明
方針
証明にはみんな大好き鳩の巣原理を使う。
区間 $[0, 1]$ を $N$ 等分すると各区間の長さは $1/N$ となる。
$S$ の元で、$[0,1]$ に含まれる値を $N+1$ 個用意してやれば、鳩の巣原理により少なくとも1つの区間には2個含まれている。
この2個の差は再び $S$ の元であり、しかも $1/N$ よりも小さい。
$N$ を十分大きく取れば、この差を $b-a$ より小さくすることができる。
あとはこれを歩幅として数直線上を歩いていけば、いつかは $a$ と $b$ の間に足を踏み入れることになる。
この点が求めたい $S$ の元である。
証明
区間 [0, 1] の中に無限個の元があることの証明
鳩の巣原理を使うには、任意の自然数 $N$ に対して $N+1$ 個の異なる元が区間[0,1]の中に存在する必要がある。証明には背理法を用いる。
区間 $[0, 1]$ の中に$S$の元が有限個しか無いと仮定し、その個数を$N$個とする。
$N+1$個の$S$の元を、次のように用意する。
\begin{align}
s_1 & = & x & - [x] \\
s_2 & = & 2x & - [2x] \\
& ... \\
s_N & = & Nx & - [Nx] \\
s_{N+1} & = & (N+1)x& -[(N+1)x]
\end{align}
ただし、$[t]$ で $t$ の整数部分を表す。
つまり $s_i$ は $ix$ の小数部分であり、この $N+1$ の元は区間$[0,1]$に含まれる。
しかし区間$[0,1]$には$N$個の元しか無いと仮定したのだから、どれか2つは値が同じはずである。
その2つを $s_i, s_j (i \neq j)$とすると、
ix - [ix] = jx - [jx]
が成り立つ。これを x について整理すると
x = \frac{[ix] - [jx]}{i-j}
となる。$i$, $j$, $[ix]$, $[jx]$ は整数であるから右辺は有理数となり、これは $x$ が無理数であることと矛盾する。
したがって仮定は誤りであり、区間 $[0,1]$の中に無限個の元があることが示された。
本題
a < b
となる実数 $a$, $b$ を任意に取る。この $a$, $b$ に対し、
\frac{1}{b-a} < N
を満たす自然数 $N$ を一つ取る。
\begin{align}
s_1 & = & x & - [x] \\
s_2 & = & 2x & - [2x] \\
& ... \\
s_N & = & Nx & - [Nx] \\
s_{N+1} & = & (N+1)x& -[(N+1)x]
\end{align}
とすると、$s_1,...s_{N+1}$ は $N+1$ 個の相異なる $S$ の元であり、区間 $[0,1]$ に含まれる。
区間 $[0,1]$ を $N$ 等分すると、鳩の巣原理より少なくとも1つの区間に $s_1,...s_{N+1}$ のいずれかが2つ存在する。この2つを $s_i, s_j (s_i < s_j )$とすると、この2つの差は $1/N$ よりも小さい。
\begin{align}
s & = & & s_j - s_i \\
& = & & (jx - [jx]) - (ix - [ix]) \\
& = & & (j - i)x - ([jx] - [ix])
\end{align}
と置けば、 $s \in S$ であり、 $s < 1/N < b - a$ を満たす。
$a/s$ より大きい最小の自然数を $m$ とおくと、
ms = m(j - i)x - m([jx] - [ix]) \in S
であり、
(m-1)s < a < ms
である。したがって、
a < ms = (m-1)s + s < a + (b - a) = b
となる。
$a, b$ を任意に取って、aより大きくbより小さい $S$ の元を得ることができた。したがって、S は$\mathbb{R}$ の中で稠密である。