数学の基礎

　さてここで、自然数に関するいくつかの命題を証明しておきましょう。以下しばらく変数はすべて自然数を表すものとします。まず

(11-1)  m + n º 0  Þ  m º n º 0

を証明しましょう。
　実際、(10-6) により n は 0 に等しいか、又はある k により n º s(k) と書けます。
　ところが後者を仮定すると、(10-22b) により s(m + k) º m + s(k) º m + n º 0 となって (P-3) に反するので、前者、すなわち n º 0 でなければならず、このとき (10-22a) により m º m + 0 º 0 も得られます。

　次に

(11-2)  m + l º n + l  Þ  m º n

が成り立つことを l に対する帰納法で証明します。
　実際、(10-22a) により l が 0 のときは成立します。
　また、(11-1) が l に対して成り立つと仮定し、m + s(l ) º n + s(l ) とすると、(10-22b) により s(m + l ) º s(n + l ) が得られ、(P-4) により m + l º n + l が得られるので、帰納法の仮定により m º n が得られます。以上で帰納法が完成し、(11-2) は証明されました。

　次に

(11-3)  mn º 0  Þ  ( m º 0  Ú  n º 0 )

を証明します。
　実際、(10-6) により n º 0 となるか、又はある k により n º s(k) と書け、後者の場合は 0 º mn º ms(k) º mk + m ですから、(11-1) により m º 0 が得られます。

　次に

(11-4)  mn º 1  Þ  m º n º 1

を証明します。
　実際、(10-6) により m º 0 となるか、又はある k により m º s(k) と書けますが、前者の場合は (10-40a) により 0 º 0n º 1 º s(0) となって (P-3) に反します。
　ゆえに後者が成り立ち、(10-40b) により kn + n º s(k)n º 1 となります。
　ここで再び、(10-6) により、n º 0 となるか、又はある l により n º s(l ) と書けますが、前者の場合は (10-43) により 0 º m0 º 1 º s(0) となって (P-3) に反します。
　ゆえに後者が成り立ち、(10-40b) により ks(l ) + l + 1 º kn + l + 1 º kn + s(l ) º kn + n º 1 º 0 + 1 が成り立つので、(11-2) により ks(l ) + l º 0 となり、(11-1) により ks(l ) º l º 0 が得られますが、更に (11-3) と (P-3) により k º 0 もわかります。
　従って、m º s(k) º s(0) º 1 及び n º s(l ) º s(0) º 1 が得られます。

　次に、任意の自然数 m , n に対して $kÎN : n º m + s(k) のことを m < n 又は n > m と書いてn は m より大きい、又はm は n より小さいということにします。このとき任意の自然数 m と n に対して

(11-5)  m < n   Ú   m º n   Ú   m > n

が成り立つことを n に関する帰納法で証明しましょう。
　まず (10-6),(10-27) により m º 0 か、又は $kÎN : m º s(k) º 0 + s(k) すなわち 0 < m が成り立つので、(11-5) は n が 0 のときは成り立ちます。
　次に (11-5) が n で成り立つと仮定します。m < n 又は m º n のときは、明かに n º m + k となる k が存在するので、s(n) º m + s(k) となり、この場合は m < s(n) となります。
　また、m > n のときは、m º n + s(k) º s(n + k) º s(n) + k となる k が存在しますが、(10-5) により、k º 0 か又は k º s(l ) となる l が存在します。
　前者なら m º s(n) であり、後者なら m º s(n) + s(l ) ですから m > s(n) となるので、これで帰納法が完成し、(11-5) は証明されました。

　次に

(11-6a)  Ø ( m < n  Ù  m > n )

を証明しましょう。
　実際、括弧の中を仮定すると、n º m + s(k) 及び m º n + s(l ) となる k と l が存在し、n + 0 º n º m + s(k) º n + s(l ) + s(k) º n + s(l + s(k)) が得られるので、(11-2) により 0 º s(l + s(k)) となって (P-3) に反します。

　特に m º n とすれば

(11-6b)  Ø n < n

が得られますから、これらにより、(11-5) は、どの２つも両立できないことがわかります。したがって特に、º と < に対して排中律：

(11-7a)  n º m  Ú  Ø n º m

(11-7b)  n < m  Ú  Ø n < m

が成り立つことがわかります。また、m º l + s(i) かつ n º m + s( j) なら n º l + s(i) + s( j) º l + s(s(i) + j) ですから

(11-8)  ( l < m  Ù  m < n )  Þ  l < n

が成り立ちます。また、演算と順序の関係として、(11-2) により n º m + s(k)  Û  l + n º l + m + s(k) なので

(11-9)  m < n  Û  l + m < l + n

が成り立ちます。

　また、l > 0 かつ m < n なら、l º s(i) 及び n º m + s(k) と書けるので、ln º lm + ls(k) º lm + lk + l º lm + lk + s(i) º lm + s(lk + i) すなわち lm < ln が得られます。
　ゆえに、l > 0 のとき、m < n , m º n , m > n のそれぞれに対して lm < ln , lm º ln , lm > ln が得られ、しかも (11-5) により、最初の３つはそのいずれかが成り立ち、(11-6) により、あとの３つは互いに両立しないので、結局

(11-10a)  l > 0  Þ  ( m < n  Û  lm < ln )

(11-10b)  l > 0  Þ  ( m º n  Û  lm º ln )

が成り立ちます。

　次に、m < n  Ú  m º n のことを m £ n あるいは n ³ m と書いて m は n 以下、あるいは n は m 以上と読みます。このとき (11-5) により

(11-11)  m £ n  Ú  m > n

が成り立ち、(11-6) により

(11-12a)  Ø ( m £ n  Ù  m > n )

(11-12b)  ( m £ n  Ù  m ³ n )  Þ  m º n

が成り立ちます。従って特に (11-11) と (11-12a) により、£ に対する排中律：

(11-13)  m £ n  Ú  Ø m £ n

及び

(11-14a)  m £ n  Û  Ø n < m

(11-14b)  n < m  Û  Ø m £ n

が得られます。また £ の定義と (10-6) により

(11-15)  m £ n  Û  ( n º m  Ú  $kÎN : n º m + s(k) )  Û  $kÎN : n º m + k

が成り立ちます。特に n º 0 + n ですから

(11-16)  n ³ 0

が成り立ちます。また、0 º n + k なら (11-1) により n º 0 なので

(11-17)  n £ 0  Û  n º 0

が成り立ちます。また、これの対偶を取って (11-11) を使えば

(11-18)  n > 0  Û  Ø n º 0

がわかります。n > 0 であるような自然数 n を正の自然数といい、その全体を N⁺ と書くことにします。

　さて、£ の定義と (11-8) により

(11-19a)  n £ n

(11-19b)  ( l £ m  Ù  m £ n )  Þ  l £ n

が成り立つので、£ は擬順序になりますが、更に (11-12b) により £ は順序であることがわかります。しかも、(11-11) により、順序 £ は条件：

(11-20)  m £ n  Ú  m ³ n

も満たしています。このような順序を全順序といいます。

　また、£ の定義と (11-8) により

(11-21a)  ( l < m  Ù  m £ n )  Þ  l < n

(11-21b)  ( l £ m  Ù  m < n )  Þ  l < n

が成り立ちます。更に、n º m + k  Û  s(n) º m + s(k) 及び n º s(m) + k  Û  n º m + s(k) により

(11-22a)  m £ n  Û  m < s(n)

(11-22b)  s(m) £ n  Û  m < n

がわかります。また、(11-2),(11-9),(11-10) により

(11-23a)  m £ n  Û  l + m £ l + n

(11-23b)  l > 0  Þ  ( m £ n  Û  lm £ ln )

が成り立ちます。

　ところで (11-15) と (11-2) により、n £ m のとき、m º n + k となる k がただ一つ存在するので、この k を m と n の差とよんで m - n と書くことにします。まず明らかに

(11-24a)  (m + n) - n º m

(11-24b)  (m - n) + n º m       ( n £ m )

(11-24c)  m - n £ m       ( n £ m )

が成り立ちます。また、(11-24b) の両辺に l を加えれば l + (m - n) + n º l + m ですから

(11-24d)  l + (m - n) º (l + m) - n       ( n £ m )

　従って特に l :º 1 とすれば、(10-24),(10-32) により

(11-24e)  s(m - n) º 1 + (m - n) º (1 + m) - n º s(m) - n       ( n £ m )

　また、m £ l のとき l + k º m + n  Û  n º (k + l ) - m º k + (l - m) ですから

(11-24f)  l £ m + n  Û  l - m £ n       ( m £ l )

(11-24g)  (m + n) - l º n - (l - m)       ( m £ l £ m + n )

　また、m £ l のとき l º k + m + n  Û  l - m º k + n ですから

(11-24h)  m + n £ l  Û  n £ l - m       ( m £ l )

(11-24i)  l - (m + n) º (l - m) - n       ( m + n £ l )

　また l £ k かつ n £ m なら k - l º m - n  Û  k º l + (m - n) º (l + m) - n  Û  k + n º l + m ですから

(11-24j)  k - l º m - n  Û  k + n º l + m       ( l £ k  Ù  n £ m )

　従って特に k :º s(m) , l :º s(n) とすれば、(10-22b),(10-30),(10-32) により k + n º s(m) + n º s(m + n) º m + s(n) º m + l º l + m ですから

(11-24k)  s(m) - s(n) º m - n       ( n £ m )

　ただし、(10-24) と (11-23a) により、n £ m なら l º n + 1 £ m + 1 º k となることを使いました。
　また、m º n + k  Þ  ml º nl + kl ですから、これを書き直せば k º m - n  Þ  kl º ml - nl となるので

(11-24l)  (m - n)l º ml - nl       ( n £ m )

　また、l £ m £ n なら k º m - l  Þ  k + l º m £ n  Þ  $i : k + i + l º n  Þ  k £ k + i º n - l ですから

(11-25a)  l £ m £ n  Þ  m - l £ n - l

　同様に、l £ m < n なら k º m - l  Þ  k + l º m < n  Þ  $i : k + s(i) + l º n  Þ  k < k + s(i) º n - l ですから

(11-25b)  l £ m < n  Þ  m - l < n - l

　また、l £ m £ n なら k º n - m  Þ  n º k + m  Þ  $i : n º k + l + i  Þ  k £ k + i º n - l ですから

(11-25c)  l £ m £ n  Þ  n - m £ n - l

　また、l < m £ n なら k º n - m  Þ  n º k + m  Þ  $i : n º k + l + s(i)  Þ  k < k + s(i) º n - l ですから

(11-25d)  l < m £ n  Þ  n - m < n - l

が成り立ちます。

　さて、述語 Î の場合と同様に、"kÎN : ( k < n  Þ  P ) を "k < n : P と略記することにし（他も同様）、帰納法のバリエーションとして、

(11-26)  ( "nÎN (( "k < n : P(k) ) Þ P(n) )) Þ "nÎN : P(n)

が成り立つことに注意します。
　実際、"k < n : P(k) を R(n) と略記すると、R(0) は自明に成り立ちます。
　また、R(s(n)) すなわち "k < s(n) : P(k) は、(11-22a) により "k £ n : P(k) すなわち R(n)  Ù  P(n) と同値です。
　ゆえに (11-26) の仮定から "nÎN ( R(n)  Þ  R(s(n)) ) が得られるので、(P-5) により "nÎN : R(n) が、従って特に R(s(n)) が、従って "nÎN : P(n) が得られます。

　さて、£ の定義により、任意の自然数 n に対して

(11-27a)  "k £ n : P(k)  Û  ( "k < n : P(k) )  Ù  P(n)

(11-27b)  $k £ n : Q(k)  Û  ( $k < n : Q(k) )  Ú  Q(n)

ですから、

(11-28)  "nÎN : ( P(n)  Ú  Q(n) )

が成り立てば、帰納法により、任意の自然数 n に対して

(11-29)  ( "k < n : P(k) )  Ú  ( $k < n : Q(k) )

が成り立つことがわかります。
　実際、n が 0 なら "k < 0 : P(k) が自明に成り立つので (11-29) は成立します。
　また、(11-29) が n で成り立つとすると、(11-28) により P(n) 又は Q(n) が成り立ち、前者なら "k < s(n) : P(k) が、後者なら $k < s(n) : Q(k) が成り立つので、(11-29) の n に s(n) を代入したものが成り立ち、帰納法が完成しました。

　ところで、もし全ての自然数 n に対して P(n) と Q(n) が同時に成り立たないなら "k < n : P(k) と $k < n : Q(k) も同時に成り立ちません。
　従って、特に全ての自然数 n に対して P(n) に対して排中律が成り立つなら、"k < n : P(k) に対しても $k < n : P(k) に対しても排中律が成り立つことがわかります。

　さて、同値関係を持つ集合 A が与えられたとき、ある自然数 n に対する（等号を同値関係に持つ）集合 N_n :º { kÎN | k < n } から A への関数を A の（長さ n の）有限列といい、その全体を Aⁿ と書くことにします。これは、集合の圏における A の N_n 乗に他なりません。

　等号を同値関係に持つ集合 A が有限集合であるためには、ある nÎN に対する N_n の商集合となっていることが必要十分です。
　実際、後者の条件を満たす集合全体からなる類を A とすると、N₀ = Æ から空集合の上への写像が存在するので、空集合は A に属します。
　また、AÎA なら、ある自然数 n と、上への写像  f : N_n ® A が存在します。そこで、任意の t' 項 a に対し、写像 g : N_s(n) ® AÈ{a} を、k < n に対しては g(k) :º  f(k) と置き、g(n) :º a と置いて定義すれば、g も上への写像です。これは AÈ{a}ÎA を意味しています。
　ゆえに類 A は (5-25) を満たすので、すべての有限集合は A に属します。以上で必要性は証明されました。
　逆に後者の条件を満たす集合が有限集合であることを、n に関する帰納法で証明しましょう。
　まず n が 0 なら、N₀ は空集合ですから、空集合の商集合 A は空集合でなければならないので、まずこの場合は A は有限集合です。
　次に、N_n の商集合はすべて有限集合であると仮定し、N_s(n) から集合 A の上への写像 f が存在するとします。このとき、f の N_n への制限を g と置き、その値域 を B と書くと、A = BÈ{ f(n)} となりますが、帰納法の仮定により B は有限集合ですから、有限集合の定義により A も有限集合です。以上で帰納法が完成し、十分性も証明されました。

　そこで、一般の同値関係を持つ集合 A についても、ある nÎN に対する N_n の商集合となっているとき、これを有限集合とよぶことにします。また、有限集合の部分集合を部分有限集合といいます。

　同値関係を持つ集合 ( A , = ) は、その同値関係 x = y が排中律を満たすとき、可識であるということにします。

　任意の可識な有限集合 ( A , = ) に対し、自然数 n が唯一つ存在して ( A , = ) は N_n と（集合の圏で）同型になることを証明しましょう。
　実際、自然数 m と上への関数 j : N_m ® A が存在しますが、上記の主張を m に関する帰納法で証明しましょう。
　まず、m が 0 なら、A は空集合ですから n º 0 が同型射となる唯一の n です。
　次に m で成り立つと仮定します。( A , = ) に対して上への関数 j : N_s(m) ® A が存在したと仮定し、a :º j(m) と置き、j を N_m に制限したものを y と書くことにします。同値関係 = について排中律が成り立つので、(11-29) により j(k) = a となる k < m が存在するかしないかいずれかです。
　前者の場合、y も N_m から A への上への関数になるので、帰納法の仮定により、自然数 n が唯一つ存在して A は N_n と同型になります。
　後者の場合、a :º { xÎA | x = a } と置いたとき、y は N_m から A \ a への全射になるので、帰納法の仮定により、自然数 l が唯一つ存在して A \ a は N_l と同型になります。そこでその同型射を c : N_l ® A \ a とすると、c を N_l 上では c と一致し、l に対しては c(l ) :º a となるように定義すれば、c は N_{s(l )} から A への一対一上への関数、従って同型射になります。
　また n の一意性は、l : N_n ® A を同型射とするとき n º s(l ) を証明すれば十分です。そこで、l(k) = a となる k < n を取り、l の k と n - 1 における値を入れ替えた関数を l' とすれば、l'(n - 1) = a となるので、l' の N_n-1 への制限を l" と書けば、l" は N_n-1 からの、c は N_l からの、共に A \ a への同型射ですから、帰納法の仮定により n - 1 º l すなわち n º s(l ) が証明されました。

　そこで、このような同値関係 = を伴う集合 A は個数を持つといい、唯一定まる n を A の（元の）個数といい、#A と表します。逆に、A が個数を持てば、N_n の同値関係 º は排中律を満たすので、= も排中律を満たします。

　また、( A , = ) と ( B , @ ) が共に個数を持てば、それらの余積 A Å B º { (0, a) | aÎA }È{ (1, b) | bÎB } も個数 #A + #B を持ちます。
　なぜなら、j : N_n ® A と y : N_m ® B が共に同型射なら、c : N_n+m ® A Å B を i < n のとき c(i) :º (0, j(i)) で、i ³ n のとき c(i) :º (1, y(i - n)) で定義すれば、c は明らかに一対一上への関数、すなわち同型射になるからです。

　また、これらの積 A ´ B º { (a, b) | aÎA, bÎB } は個数 #A · #B を持ちます。
　実際、これを B の個数による帰納法で証明することにすると、まず #B º 0 の場合は B = Æ なので明らかです。
　また、B の個数が m のとき成り立つと仮定し、#B º s(m) とすると、B は元を持つので bÎB を任意に選んで B' :º B \ {b} と置けば、#B' º m で、しかも A ´ B は A ´ B' と A ´ {b} の余積に同型で、後者は更に A と同型です。
　ゆえに上に示したことと帰納法の仮定により #(A ´ B) º #(A ´ B' ) + #A º #A · m + #A º #A · s(m) º #A · #B となって帰納法が完成しました。

　次に、N から同値関係を持つ集合 A への関数を A の点列又は単に列といい、その全体を A^w と書きます。これは、集合の圏における A の N 乗に他なりません。
　また、N の商集合を可算集合といい、可算集合の部分集合を部分可算集合といいます。

　可算個の有限集合 S_n の合併と表される集合 S は可算集合です。
　なぜなら、n に対する帰納法により、ある自然数 N_n より小さい自然数全体の集合から È{ S_k | k £ n } の上への関数が存在するからです。
　更に可算個の可算集合の合併も可算集合であることが証明できます。
　実際、N ´ N が可算であることを示せば十分ですが、A_n :º { (i, j)ÎN ´ N | i + j = n } は個数 n + 1 の有限集合ですから、それらの合併集合である N ´ N は、可算個の有限集合の合併として可算集合です。

　さて、帰納的定義の有限版として、同値関係を持つ集合 A 、A の元 c 、N_n ´ A から A への関数 F が任意に与えられたとき、

(11-30a)  j(0) = c

(11-30b)  "k < n : j(s(k)) = F(k, j(k))

を満たす A の長さ s(n) の有限列 j が唯一つ存在することを、n に関する帰納法により証明しましょう。
　まず、n が 0 のときは (11-30b) が空な条件になるので明らかです。
　また、n については成り立つと仮定し、F が N_s(s(n)) ´ A から A への写像とすると、特に N_s(n) ´ A で定義されていますから、帰納法の仮定により、(11-30) を満たす長さ n の有限列 j が存在します。
　すると、y : N_s(s(n)) ® A を、k £ n のとき y(k) º j(k) となり、y(s(n)) º F(n, j(n)) が成り立つように一意的に定義できますが、この y は (11-30) で n を s(n) に置き換えたものを満たす長さ s(n) の有限列であることがわかります。一意性も明らかですから、帰納法により主張は証明されました。

　この応用例として、* を集合 A 上の２項演算とするとき、A の長さ s(n) の有限列 aに対して、(11-30) で c :º a(0) 及び F(k, x) :º x * a(s(k)) と置いて得られる写像 j を、記号 * を使って

(11-31a)

0 * i = 0

a(i) º a(0)

(11-31b)

s(k) * i = 0

a(i) º

æ ç è

k * i = 0

a(i)

ö ÷ ø

* a(s(k))       ( k < n )

で定義します。また、m £ n に対して { i | iÎN  Ù  m £ i £ n } で定義された a(i) に対し、n º m + k となる k がただ一つ存在するので、

(11-31c)

n *  i = m

a(i) :º

k * i = 0

a(m + i)

と定義します。ただし、* が加法 + のときは記号 * に替えて å という記号を、* が乗法 · のときは Õ という記号を用います。
　また、見た目のわかりやすさのために、(11-31c) の左辺のことを a(m) * a(m + 1) * a(m + 2) * ¼ * a(n) のように書くこともあります。

　次に、点列の帰納的構成について考えましょう。
　xÎAⁿ と aÎA に対し、y_i :º x_i ( i < n ) 、y_n :º a で定義される yÎA^s(n) のことを仮に x#a と表わし、xÎA^w に対して x の定義域を N_n に制限した長さ n の有限列を x|_n と書くことにします。
　このとき、A の有限列からなる任意の集合 F に対して、

(11-32)  ( A0 Ì F  Ù  "xÎF : $aÎA : x#aÎF ) Þ $xÎAw : "nÎN : x|nÎF

が成り立つことが証明できます。実際、(11-32) の前提部分を仮定し、F から A への写像 f を

(11-33)  f(x) :º εt' a ( aÎA  Ù  x#aÎF )

で定義し、A⁰ = {Æ} であることに注意して、A の同値関係として等号を取り、(10-7) で c :º Æ 及び F(n, x) :º x#f(x) と置いたとき唯一つ存在する写像 j を取ると、

(11-34a)  j(0) º Æ

(11-34b)  j(s(n)) º j(n)#f(j(n))

が成り立つので、まず帰納法により

(11-35)  j(n)ÎAnÇF

が成り立つことがわかります。
　実際、n が 0 のときは (11-34a) により明らかです。また n のとき成り立つと仮定すると、(11-33) により xÎF のとき f(x)ÎA  Ù  x#f(x)ÎF が成り立つので、帰納法の仮定により x に j(n) を代入することができて、(11-34b) により、(11-35) の n に s(n) を代入したものが成り立ち、帰納法が完成します。
　そこで xÎA^w を x_n :º f(j(n))  ( nÎN ) で定義すれば、任意の nÎN に対して

(11-36)  x|n = j(n)

が成り立つことが帰納法で証明できます。
　実際、n に 0 を代入したものは (11-34a) により成立します。また n に対して (11-36) を仮定すれば、(11-34b) と x_n の定義により

(11-37)  j(s(n)) º j(n)#f(j(n)) = x|n # xn = x|s(n)

が成り立つので帰納法が完成します。ゆえに (11-35),(11-36) により (11-32) は証明されました。

　次に、N の判定可能な部分集合すなわち

(11-38)  "nÎN ( nÎA  Ú  nÏA )

を満たす N の部分集合 A が元を持てば、必ず最小値：

(11-39)  min A :º εn( nÎA  Ù  "kÎA : k ³ n )

を持つことを証明します。そのためには、すべての自然数 n に対し、命題：「$k £ n : kÎA ならば A は最小値を持つ」を証明すれば十分です。
　まず n が 0 なら、0ÎA が最小値ですから明らかです。
　次に、n のとき命題が成り立つと仮定して s(n) の場合にも成り立つことを証明しましょう。
　まず A が判定可能な部分集合であることと (11-29) の直後の注意により、$k £ n : kÎA 又はその否定が成り立ちます。
　前者の場合は帰納法の仮定により A は最小値を持ちます。後者の場合は Ø$k £ n : kÎA すなわち第４節メタ定理46 (g) により "k £ n : kÏA が成り立つので、更に $k £ s(n) : kÎA を仮定すると、s(n)ÎA が最小値であることは明らかです。ゆえに帰納法により証明されました。

　次に、N の判定可能な部分集合 A が元を持ち、（上に）有界：

(11-40)  $nÎN : "kÎA : k £ n

であれば、必ず最大値：

(11-41)  max A :º εn( nÎA  Ù  "kÎA : k £ n )

を持つことを証明します。そのためには、すべての自然数 n に対し、命題：「$k £ n : kÎA かつ "kÎA : k £ n ならば A は最大値を持つ」を証明すれば十分です。
　まず n が 0 なら、0ÎA が最大値ですから明らかです。
　次に、n のとき命題が成り立つと仮定して s(n) の場合にも成り立つことを証明しましょう。
　まず A が判定可能な部分集合であることから s(n)ÎA 又はその否定が成り立ちます。
　前者の場合、明らかに s(n) が最大値です。後者の場合、仮定「$k £ s(n) : kÎA かつ "kÎA : k £ s(n)」から「$k £ n : kÎA かつ "kÎA : k £ n」が導かれますから、帰納法の仮定により A は最大値を持ちます。ゆえに帰納法により証明されました。

　さて一般に、有限集合 A :º { a_i | iÎN_n }（ただし n > 0）に全順序 £ が与えられている場合、A は最大値と最小値を持つことを n に関する帰納法で証明しましょう。
　まず n が 0 のときは仮定が偽なので成立します。n で成り立つと仮定し、A :º { a_i | iÎN_s(n) } について最大値と最小値の存在を証明しましょう。まず n º 0 ならば A = { a₀ } ですから min A º max A º a₀ は明らかなので、n > 0 と仮定します。
　すると、帰納法の仮定により m :º min { a_i | iÎN_n } が存在します。A は全順序集合なので、m £ a_n 又は m ³ a_n が成立しますから、前者の場合は m が、後者の場合は a_n が A の最小値であることは明らかです。最大値についても同様ですから、帰納法により証明されました。