次: 存在の間接証明−中間値の定理 上: 存在の証明 前: 最小自然数の存在

離散的写像の不動点定理

関数が有限集合から有限集合への写像である場合， その写像が一定の条件を満たすと，不動点つまり$f(x_0)=x_0$となる$x_0$が存在する． これはその条件に適するような離散的関数を図示して考えることで，存在に目安をつけ， その上で証明方法を考えるという観点で取り組んでみてほしい． 関数の図示と存在証明の結合である．

例題 1.19       ［92神戸大］

自然数 $n$ に対して，1から $n$ までのすべての自然数の集合を $N$ とする． $N$ から $N$ への写像 $f$ が次の条件

$$i,\ j \in N\ かつ\ i\le j\ ならば，つねにf(i)\le f(j)$$

をみたすとき， $f(k)=k$ となる $N$の要素 $k$ があることを示せ．

ただし，集合$A$ の各要素に対して集合$B$ の要素を1つずつ対応させる規則のことを， $A$ から$B$ への写像という． 写像は$f$ などで表し，$A$ の要素 $a$ に写像 $f$ で対応する $B$ の要素を$f(a)$ と書く．

解答   
$1\le f(i) \le n\ \ (i=1,\ 2,\ \cdots,\ n)$ である．

$f(1)=1$ なら $k$として$1$ をとればよい．そこで$f(1)>1$ とする． $f(n)=n$ なら $k$として$n$ をとればよい．そこで$f(n)<n$ とする．

このとき，$f(1)>1$かつ $f(n)<n$ なので $f(i)>i$ となる $i$ の中の最大のものが存在する． それを $i_0$ とする．$i_0<n$ である．

$i_0+1$ は $f(i)>i$を満たさないので $f(i_0+1)\le i_0+1$．

ところが$i\le j$ ならば，つねに$f(i)\le f(j)$なので

$$i_0<f(i_0)\le f(i_0+1)\le i_0+1$$

ここでもし $f(i_0+1)< i_0+1$なら，隣りあう二つの自然数 $i_0$ と $i_0+1$ の間にさらに自然数が存在し不合理．

$$∴ \quad f(i_0+1)= i_0+1$$

$i_0+1\le n$なので $k$として$i_0+1$ をとればよい．□

次のような別解もある．

背理法でやってみようとするのは自然な発想だ． 問題をその次の段階．数学的帰納法で$f(i)>i$を示せれば，$n$のところで矛盾が起こる．

別解     背理法で示す．

$1\le i \le n$ のすべての $i$ に対して $f(i)\ne i$ であるとする． このときすべての $i$ について $f(i)>i$ であることを数学的帰納法で示す．

$f(1)\ge 1$ かつ$f(1)\ne 1$なので $f(1)>1$ ．

$f(i)>i$ とする．$i\le j$ ならば，つねに$f(i)\le f(j)$なので $i<f(i)\le f(i+1)$． したがって $i+1\le f(i+1)$ であるが $i+1\ne f(i+1)$ なので $i+1< f(i+1)$ である． 数学的帰納法によってすべての $i$ について $f(i)>i$となる．

ところがこのとき$n<f(n)$ なので， $f$ が $N$ から $N$ への写像であることと矛盾した． ゆえに $1\le i \le n$ のの中に少なくとも一つ$f(k)=k$ となる $i=k$ が存在する．□