3 ४໑౨ࢇ࢘ʇ Higman ʍൊ੠

NASH ਲʇˋ˻ʶ˲੖ߥƕ४໑լࢇ࢘௬ฉ

ࣆπφ२Ɣ֮୤੝ӌॐ๽҈উٰ֖ࢊ

1 ʎɷʠʊ

ࢬজўUrsula K. Le Guin (1929 - 2018)ʎƐਜ਼೅ݴʍ1ʃdžʼ˳˻ˋɪʨൈʞ֞ʪऩƧLJ ʱऐʍज໿(psychomyth)ʇڐʲɿƑɼʫʊൕɣƐΤђ2ʃʍ໼๽ʍज໿(logicomyth) ʱ ۵ɧʪƑ

ฆ੠1.1

ɡʪफ़ҚʊʎƐnˋ˻ʶ˲ʉʪॲ෡੄ɫ௰ίʍ߭োॐn^{ʊʃɣʅਮݥɸʪ}(ਅ࣌ɶʅ અʊˋ˻ʶ˲ʇڐʕƹƑ0ˋ˻ʶ˲ʱ۞َɸʪʇઅʊࣁ෩ɸʪɫƐ(n+ 1)ˋ˻ʶ˲ʱ

۞َɸʪʇѕಬɪʍnˋ˻ʶ˲ʊഒ໔ɸʪƸѕಬʊഒ໔ɸʪɪʎ۞َɶʅʞʪʝʆʮ ɪʨʉɣƹƑɴʅƐɡʉɾʍৈʊѕಬɪʍˋ˻ʶ˲ɫɡʨʮʫɾƘ ɡʉɾʎอڌ҉ʍ

۞َʆˋ˻ʶ˲ɾʀʱɺʲ෩ɸʪɲʇɫʆɬʪɿʬɥɪƗ

ฆ੠1.2

ऩ෠ʱʑʨɫʉʆ೅ɸƑ෠ৈu^ɫt^{ʊඨʠܦʠʪʇʎƐ}tɪʨɣɮʃɪഞߞʱࠪʩ࢜

ɮʇuʊʉʪɲʇʱɣɥƑɾʇɧʏDŽʥɪDžʎDŽʥɥɪDžʣDŽɪʥɪʥDžʊඨʠܦʠ ʪɫDŽɪʥʥDžʊʎඨʠܦʠʉɣƑɡʪʇɲʬʊNASHਲʇڐʏʫʪਲɫɡʂɾ¹Ƒ NASHਲʆʎߣƧʇ޶֯ɫॲʝʫʅɣɮɫƐओॲߝʍ෡෠ʊʎʑʇʃɬʝʩɫɡʩƐ ѷ֞ʊॲʝʫɾ޶ʍ෠ৈɫओॲߝʍ෠ৈʊඨʠܦʠʅʎʉʨʉɣʇɸʪƑɲʍ෡෠՜

ਝʎ ɣʃʝʆʡηߡњఉɿʬɥɪƗ ɼʫʇʡɣʃɪʎओॲߝʊ෠ৈʱʃɰʨʫʉɣ ߚੌɫॲɷʪɿʬɥɪƗ

චۮʆʎ0ʱ߭োॐʊ԰ʠƐ߭োॐৌ੄ʍࡘ܏{0,1,2, . . .}^ʱN^ʇ࢑ɮƑ

2 ४໑ࢇ࢘ʇਵࡥࡘ܏

ʝɹʎࢇ࢘ࡘ܏ʍՂ৛ߚ܈ʱজ෢ɶƐฆ੠1.1ʊʃɣʅ۵ɧʪƑ

Xʱࡘ܏ʇɸʪƑ૰ঋࡘ܏X×X:= {(a, b) :a, b∈X}^{ʍ೼ഒࡘ܏}R ⊆X×X^ʱX

ࣣʍԪؤʇɣɥƑ(a, b) ∈R^ʍɲʇʱa R b^ʇʡ࢑ɮƑX^ࣣʍԪؤR₁, R₂^ɫR₁ ⊆R₂^ʱ ෂɾɸʇɬƐR₂^ʱR₁^{ʍҼ૗ʇɣɥƑ}

1ɲʍฆ੠ʎ˧ʵˁˉ˹̅ʆɡʩƐബܙʍ୤޸NashvilleʇʎφঔԪؤʉɣƑਲ෠ʎॐӌࠖCrispin St. John Alvah Nash-Williams^{ʊʀʉʲʆɣʪƑ}

ΤђʱෂɾɸԪؤ≤^ʱX^{ࣣʍ౨ࢇ࢘ʇɣɥ}(ৠX,≤^{ʍɲʇʱ౨ࢇ࢘}(ࡘ܏)ʇʡɣɥ)Ƒ

a≤a (౩ࠏ१)

a≤b ^ɪʃ b≤a =⇒ a=b (^౩੆࣌१) a≤b ^ɪʃ b≤c =⇒ a≤c (ीζ१)

ɲɲʆa, b, c^ʎX^{ʍ௰ίʍ๗য়ʆɡʪ2Ƒɴʨʊ}

a≤b ^ʝɾʎ b≤a

ɫ௰ίʍa, b∈Xʊʃɣʅ२ʩງʃʇɬƐ≤^{ʱৌࢇ࢘ʇɣɥƑ}

౨ࢇ࢘ʇৌࢇ࢘ʍԪؤʱߪɸɾʠʊൊ੠ʱ1ʃࣘ෢ɸʪƑX^ࣣʍԪؤR^ʆƐ௰ίʍn∈N ʇa₀, . . . , a_n∈X^ʊʃɣʅ

a0 R a1 R a2· · ·anR a0 =⇒ a0=a1 =· · ·=an

ʱෂɾɸʡʍʱಝࡻԖʇɣɥƑ෢ʨɪʊ౨ࢇ࢘ʎಝࡻԖʆɡʪƑ

ൊ੠2.1

ࡘ܏XࣣʍʈʲʉಝࡻԖԪؤʡৌࢇ࢘ʊҼ૗ʆɬʪƑʇɮʊʈʲʉ౨ࢇ࢘ʡৌࢇ࢘

ʊҼ૗ʆɬʪƑ

ࣘ෢. ಝࡻԖԪؤRɫ฿ɧʨʫɾʇɬƐࡘ܏

{R ⊆X×X:R⊆R, R^ʎಝࡻԖ}

ʊ੆ɶʅZornʍൊ੠ʱ଼๑ɸʫʏי੝ʉԪؤR^{ɫமʨʫʪƑɲʍ}R^{ʎৌࢇ࢘ʆɡʪƑ} ଜձ2.2

X,≤^{ʱৌࢇ࢘ʇɸʪƑ}X^{ʊ෗ڌђ܇໑}

a₀ > a₁ > a₂ >· · ·^Ə (a_i ∈X) ɫਮݥɶʉɣʇɬƐX,≤^{ʱ४໑ࢇ࢘ʇɣɥƑ}

ലʍڊɣൣʱɸʫʏƐ४໑ࢇ࢘ʇʎ؃ʆʉɣʈʲʉ೼ഒࡘ܏Y ⊆X^{ʡݍࢬٿʱߡʃʧɥ} ʉৌࢇ࢘ʍɲʇʆɡʪƑʈʲʉࡘ܏ࣣʊʡ४໑ࢇ࢘ʱ௬ʫʨʫʪʇɣɥʍɫZermeloʍ४ ໑ଜ๽ʆɡʪƑɲʫʎূ੨ۂ๽ʇடડʆɡʪƑ

ߣʊਵࡥࡘ܏ʱଜձɶƐ(N^ࣣʍ)ਵࡥࡘ܏ʍԨʊ߭োʉࢇ࢘ԪؤʱଜʠʪƑࡘ܏X^ʍ Һ๗য়a∈X^{ʊʃɣʅࡥഉ୩}t(a)∈NɫଜʝʂʅɣʪʇɬƐԪॐt:X −→N^ʍɲʇʱX

ࣣʍਵࡥࡘ܏ʇɣɥƑt(a) =m^ʍʇɬƐt^ʎ๗য়a^ʱmڎ԰ʟʇ۵ɧʪƑਵࡥࡘ܏t^ʎƐ

a∈Xt(a)ɫอڌʍʇɬอڌʆɡʪʇɣɥƑอڌਵࡥࡘ܏ʱt= [a, a, a, b, b, c]ʍʧɥʊ࢑

ɮƑɲʫʎa^ʱ3ڎ,b^ʱ2ڎ,c^ʱ1ڎ,ɼʍ਴ʍ๗য়ʎ0ڎɹʃ԰ʟਵࡥࡘ܏ʆɡʪƑX

ࣣʍอڌਵࡥࡘ܏ৌ੄ʱM(X)ʇ࢑ɮƑ

2౩ࠏ१Ɛीζ१ʍʞʱෂɾɸԪؤʱլࢇ࢘ʝɾʎৈࢇ࢘ʇɣɥƑ೅੠ʊɡʪ४໑լࢇ࢘(well quasi-order) ʎɲʫʊำ๨ɸʪʡʍʆɡʪɫƐචۮʆʎ౨ࢇ࢘ʊॣڌɶʅ໿ʱदʠʪʍʆլࢇ࢘ʎ෢ߪ଺ʊʎࡰʅɲʉɣƑ

N^{ࣣʍอڌਵࡥࡘ܏}t, u ∈M(N)ʊʃɣʅ۵ɧʪƑt^ʊ1ڎΤࣣ԰ʝʫʪ๗য়n^ʊʃɣ ʅƐt^ɪʨn^ʱ1ʃࠪʩ࢜ɬƐഉॐڎʍn−1∈N (0ڎʆʡʧɣ)ʱљɧʪʇu^ɫமʨʫ ʪʇɬu t^{ʇ࢑ɮƑʇɮʊ}t^ɪʨ0ʱ1ʃࠪʩ࢜ɮʇu^{ɫமʨʫʪʇɬ}u t^ʆɡʪƑ ɲʍ৸ݴʱഉॐ҉ؗʩ഼ɸʇt^ɪʨu^{ɫமʨʫʪʇɬʡ}u t^ʇ࢑ɮ(0҉ʍ࣪܏ʡ԰ʠ ʪ)ƑԪؤ ʎਵࡥࡘ܏ࢇ࢘ʇڐʏʫʪƑ

Һt∈M(N)ʎˋ˻ʶ˲ʍࡘઘʊ੆жɸʪƑɾʇɧʏ[7,7,7,6,0,0]ʎ7ˋ˻ʶ˲3ಬƐ 6ˋ˻ʶ˲1ಬƐ0ˋ˻ʶ˲2ಬɪʨʉʪࡘઘʱ೅ɸƑʝɾԪؤ ʎˋ˻ʶ˲ʊ੆ɸʪ۞

َʱ෱ɶʅɣʪƑɶɾɫʂʅฆ੠1.1ʊ੆ɸʪ҈ʎΤђʍଜ๽ʊʧʩ฿ɧʨʫʪƑ ଜ๽2.3

M(N), ^{ʎ४໑ࢇ࢘ʆɡʪƑ}

ࣘ෢. ௰ίʍn∈N^ʊʃɣʅM({0, . . . , n}), ɫ४໑ࢇ࢘ʆɡʪɲʇʱɣɧʏʧɣƑࣘ

෢ʎnʊʃɣʅʍՒఈ൥ʊʧʪƑ

n= 0ʍʇɬʎ෢ʨɪʉʍʆn >0ʇɸʪƑ෗ڌђ܇໑

t₀t₁ t₂ · · · (t_i∈M({0, . . . , n}))

ɫਮݥɸʪʇєଜɶʅෙࢂʱ஡ɮƑt_i^ʊ԰ʝʫʪn^ʍڎॐʱt_i(n)ʇɸʫʏƐ ʍଜձʧ ʩt₀(n) ≥ t₁(n) ≥ t₂(n) ≥ · · · ɫ२ʩງʃƑʧʂʅ࡝ഒ੝ɬʉk ∈ N^ʱʇʫʏt_k(n) = t_k+1(n) =t_k+2(n) = · · · ^{ʇʉʪƑɼɲʆ}t_i^ɪʨnʱৌ೼ࠪʩ࢜ɣʅமʨʫʪਵࡥࡘ܏ʱ uiʇɩɰʏ෗ڌђ܇໑

u_ku_k+1u_k+2 · · · (u_i∈M({0, . . . , n−1})) ɫமʨʫʪɫƐɲʫʎՒఈ൥ʍєଜʊ౩ɸʪƑ

ࣣʆʎM(N)ࣣʍਵࡥࡘ܏ࢇ࢘ʊʃɣʅ۵ɧɾɫƐࠄݣʊʎʈʲʉ४໑ࡘ܏X=X,≤ ɫ฿ɧʨʫʅʡM(X)ࣣʍਵࡥࡘ܏ࢇ࢘≤^mʱ߭োʊଜʠʪɲʇɫʆɬʪƑɼʫʊʎƐਵ ࡥࡘ܏t∈M(X)ɪʨ๗য়a∈X^ʱ1ʃࠪʩ࢜ɬƐa^{ʧʩछʊࢬɴɣ๗য়}b1, . . . , bk (k= 0 ʆʡʧɣ)^ʱљɧʪʇu^{ɫமʨʫʪʇɬ}u ≤^m tʇ࢑ɮɲʇʊɸʫʏʧɣƑɲʍ৸ݴʱഉ ॐ҉ؗʩ഼ɸʇt^ɪʨu^{ɫமʨʫʪʇɬʊʡ}u≤^mtʇ࢑ɮƑɲʍʇɬߣɫ२ʩງʃƑ

ଜ๽2.4

X,≤^{ɫ४໑ࢇ࢘ʉʨʏ}M(X),≤^{mʡ४໑ࢇ࢘ʆɡʪƑ}

ࣘ෢ʎ४໑ࢇ࢘≤ʊʃɣʅʍ૨ڌՒఈ൥ʊʧʪƑK¨onigʍൊ੠ʱ๑ɣɾ૰Ԉ଺ʊʮɪʩ ʣɸɣࣘ෢ʡʧɮઢʨʫʅɣʪƑ

3 ४໑౨ࢇ࢘ʇ Higman ʍൊ੠

ߣʊฆ੠1.2ʊʃɣʅ۵ɧʪƑ

ଜձ3.1

X,≤^{ʱ౨ࢇ࢘ʇɸʪƑ}X^{ࣣʍ෗ڌ໑}a₀, a₁, a₂, . . .ʆΤђʱෂɾɸʡʍʱ·໑ʇɣɥƑ i < j =⇒ a_i a_j (i, j∈N)

·໑ʱ԰ʝʉɣ౨ࢇ࢘ʱ४໑౨ࢇ࢘ʇɣɥƑ

ڊɣԋɧʫʏƐa₀, a₁, a₂, . . . ^{ɫ·໑ʆɡʪʇʎƐ}i < j^ɪʃa_i ≤a_j ^ʇʉʪi, j∈N^ɫਮ ݥɶʉɣɲʇʆɡʪƑ·໑ʍ೼ഒ໑ʎʔɾɾʒ·໑ʊʉʪɲʇʊુίƑ

X,≤ɫৌࢇ࢘ʍʇɬƐ·໑ʇʎ෗ڌђ܇໑ʍɲʇʊ਴ʉʨʉɣƑʧʂʅଜձ3.1ʎଜ ձ2.2ʇφફɸʪƑʧʩφ౶ʊƐ४໑ࢇ࢘ʇ४໑౨ࢇ࢘ʍԪؤʎߣʍʧɥʊʉʂʅɣʪƑ

ଜ๽3.2

౨ࢇ࢘X=X,≤ɫ४໑౨ࢇ࢘ʆɡʪɲʇʍ಴๗࡝ഒࣰٛʎƐʈʍʧɥʊৌࢇ࢘ʊ Ҽ૗ɶʅʡ४໑ࢇ࢘ʊʉʪɲʇʆɡʪƑ

ࣘ෢. єʊ≤^{ʱҼ૗ɸʪৌࢇ࢘ ʆ෗ڌђ܇໑}a₀ a₁a₂ · · · ^{ʱ԰ʟʡʍɫɡʂɾʇ} ɸʪƑɲʍʇɬa₀, a₁, a₂, . . . ^ʎX,≤ʍ·໑ʆɡʪƑࠄݣƐɡʪi < j^ʊʃɣʅa_i ≤a_j ɫ२ʩງʃʉʨʏƐa_i a_j^ʆɡʩa_i a_j ^{ʊෙࢂɸʪƑ}

օʊX,≤^ɫ·໑a0, a1, a2, . . . ʱ԰ʟʇɸʪƑɲʍʇɬԪؤR^ʱ

b R c ⇐⇒ b≤c^ʝɾʎ (b, c) ∈R, R :={(a_j, a_i) :i < j}

ʊʧʩଜʠʪʇRʎಝࡻԖʆɡʪƑࠄݣʡɶࡻԖɫɡʪʉʨƐɡʪ(aj0, ai0), . . . ,(ajn, ain)∈

R^ɫਮݥɶ

a_j0 R a_i0 ≤a_j1 R a_i1 ≤a_j2 R a_i2· · ·a_jn R a_in ≤a_j0

ʇʉʪƑR^ʍଜձʧʩj₀ > i₀, j₁ > i₁, . . . , j_n > i_n^ɿɪʨƐɡʪ0≤ k < n^ʊʃɣʅ i_k< j_k+1 (ʝɾʎi_n< j₀)ʆɡʪɫƐɼɥɸʪʇࣣʧʩa_ik ≤a_jk+1 (ʝɾʎa_in ≤a_j0)ʇ ʉʩa₀, a₁, a₂, . . . ɫ·໑ʆɡʪɲʇʊ౩ɸʪƑ

ൊ੠2.1ʧʩX, R^ʎৌࢇ࢘X, ^{ʊҼ૗ʆɬʪɫƐ}a₀a₁ a₂ · · · ^ʇʉʪʍʆ ४໑ࢇ࢘ʊʎʉʨʉɣƑ

४໑౨ࢇ࢘ʊʎ਴ʊʡอ๑ʉற૙ʄɰɫɣɮʃʡɡʪƑɼʍɥʀ2ʃʱΤђʆ࣐҆ɸʪƑ ݍࢉʍʡʍʎ(Nash-Williams 1963)ʊʧʪƑ

ൊ੠3.3

౨ࢇ࢘X=X,≤ɫ४໑౨ࢇ࢘ʆɡʪɲʇʍ಴๗࡝ഒࣰٛʎƐX^{ࣣʍʈʲʉ෗ڌ໑} a₀, a₁, a₂, . . . ʡەձઅ૦ਕљʉ෗ڌ໑

a_i0 ≤a_i1 ≤a_i2 ≤ · · · (i₀ < i₁< i₂ <· · ·) ʱ೼ഒ໑ʇɶʅ԰ʟɲʇʆɡʪƑ

ࣘ෢. ࡝ഒ१ʎ෢ʨɪʉʍʆ಴๗१ʱߪɸƑXʱ४໑౨ࢇ࢘ʇɸʪƑ෗ڌ໑a0, a1, a2, . . . ɫ฿ɧʨʫɾʇɬƐΤђʱෂɾɸamʱයઐʇڐʕƑ

m < j =⇒ a_m a_j (j∈N)

ʡɶʡයઐʍa_mɫ෗ڌʊਵɮɡʫʏƐɼʫʨʱࡘʠʪʇ·໑ɫʆɬʅɶʝɥʍʆX^ɫ४ ໑౨ࢇ࢘ʆɡʪɲʇʊ౩ɸʪƑɼʫʥɧයઐʍa_mʎอڌڎɶɪʉɣƑɼʫʨৌ೼ʧʩگ ʍ๗য়ʱ1ʃʇʩa_i0 ^ʇɩɰʏƐa_i0 ≤a_i1 ≤a_i2 ≤ · · · ^{ʱෂɾɸʧɥ}a_ik ^{ʱߣƧʊʇʂʅ} ɣɮɲʇɫʆɬʪƑ

౨ࢇ࢘X =X,≤^ʇ๗য়a∈X^{ɫ฿ɧʨʫɾʇɬƐ}L(a) := {b∈X :ab}^ʇଜʠ ʪƑX^ࣣʍԪؤ≤^ʱL(a)ࣣʊॣڌɶɾʡʍʱʔɾɾʒ≤^ʇ࢑ɮƑ

ൊ੠3.4

Xɫ४໑౨ࢇ࢘ʆɡʪɾʠʊʎƐ௰ίʍa∈X^ʊʃɣʅL(a),≤^{ɫ४໑౨ࢇ࢘ʆɡ} ʪɲʇɫ಴๗࡝ഒʆɡʪƑ

ࣘ෢. ಴๗१ʎ෢ʨɪƑ࡝ഒ१ʎߣʍɲʇɪʨ࡞ɥƑa₀, a₁, a₂, . . . ^ɫX^{ࣣʍ·໑ʉʨʏ} a₁, a₂, a₃, . . . ^ʎL(a₀)ࣣʍ·໑ʆɡʪƑ

Τࣣʆࢀಡɫ४ʂɾʍʆƐฆ੠1.2ʊʃɣʅ۵ɧʪƑΣʱഞߞʍอڌࡘ܏ʇɸʪʇɬƐ Σʊ԰ʝʫʪഞߞʍڎॐʱ|Σ|^{ʊʧʩ೅ɸƑʝɾƐ}Σʍ๗য়ɪʨʉʪอڌ໑ৌ੄ʍࡘ܏ʱ Σ^∗ʇ࢑ɮƑʇɮʊ؃໑ε^ʎΣ^∗ʍ๗য়ʆɡʪƑഞߞ໑t, u^ʊʃɣʅƐt^ɪʨ1ഞߞࠪʩ࢜

ɮʇu^{ɫமʨʫʪʇɬ}ut^{ʇ࢑ɮƑɲʫʎʃʝʩ}t=t₁xt₂,u=t₁t₂^{ɫ२ʩງʃʇɣɥ} ɲʇʆɡʪ(x∈Σ, t₁, t₂ ∈Σ^∗)Ƒɲʍ৸ݴʱഉॐ҉ؗʩ഼ɸʇt^ɪʨu^{ɫமʨʫʪʇɬʊ} ʡut^{ʇ࢑ɮƑɲʫʎʃʝʩ}tɪʨѕഞߞɪࠪʩ࢜ɮʇuɫமʨʫʪ࣪܏ʆɡʪƑԪؤ ^ʱ(ഞߞ໑ʍ)ඨʠܦʞࢇ࢘ʇɣɥƑ

Σʱʑʨɫʉৌ೼ʍࡘ܏ʇɸʫʏƐΣ^∗ʎ෠ৈৌ೼ʍࡘ܏ʊʉʪƑɲʍ࣪܏·໑ʇʎƐ NASHਲʍኚʊʍʂʇʂʅ෡෠ɴʫɾ෠ৈʍ໑ʍɲʇʊ਴ʉʨʉɣƑɼʫʥɧΤђʍଜ๽

ɫฆ੠1.2ʊ੆ɸʪ҈ஊʊʉʪƑ ଜ๽3.5(Higman 1952)

௰ίʍอڌࡘ܏ΣʊʃɣʅΣ^∗,^{ʎ४໑౨ࢇ࢘ʆɡʪƑ}

ࣘ෢ʎ|Σ|ʊԪɸʪՒఈ൥ʊʧʪƑ|Σ|= 1ʍ࣪܏ʎ෢ʨɪƑΤђ|Σ|>1ʇɶƐɼʫʧ ʩࢭʉɣഞߞॐʍ࣪܏ʊʎଜ๽ɫ२ʩງʃʇєଜɸʪƑՒఈ൥ʱɥʝɮʝʮɸɾʠʊʎƐ Σʊʃɣʅʍմ໼ʱΣʧʩφഞߞࢭʉɣ࣪܏ʊԦٿɶʉɰʫʏʉʨʉɣƑΤђʍʴʶ˙ʴ ʎ(Jullien 1968)ʊʧʪƑ

ഞߞࡘ܏Σɪʨφഞߞa∈Σʱࠪʩ࢜ɣʅமʨʫʪࡘ܏ʱΣ_a:= Σ\{a}^{ʇɩɮƑഞߞ} ໑t=x⁽⁰⁾· · ·x^{(n)ʱڑଜɸʫʏƐʈʲʉ}u∈L(t)ʡΤђʍʧɥʊ೅ɸɲʇɫʆɬʪƑ

u=u⁽⁰⁾x⁽⁰⁾u⁽¹⁾x⁽¹⁾· · ·u^(m), (m≤n, u^(k) ∈Σ^∗_x(k))

ࠄݣu∈L(t)ɫ฿ɧʨʫɾʇɬƐx⁽⁰⁾ʱ԰ʝʉɣʧɥࡰ๨ʪɿɰ૫ɮu^(0)ʱʇʩƐx^(1)ʱ

԰ʝʉɣʧɥࡰ๨ʪɿɰ૫ɮ u^{(1)ʱʇʩƐɼɥʣʂʅ}u⁽⁰⁾, u⁽¹⁾, . . .^{ʱࢇߣଜʠʅɣɰʏƐ}

ભɮʇʡu^(n)ʝʆʊuৌ੄ʱഊɣरɮɺʪʎɹʆɡʪƸɴʡʉɮʏt u^ʇʉʂʅɶʝ ɥ)Ƒɸʪʇ|Σ_x(k)|=|Σ| −1ʉʍʆƐՒఈ൥ʍєଜʧʩΣ_x(k)ʊ੆ɶʅൊ੠3.3ʱ๑ɣʪ ɲʇɫњఉʊʉʪƑ

ൊ੠3.6

௰ίʍt∈Σ^∗ʊʃɣʅL(t),^{ʎ४໑౨ࢇ࢘ʆɡʪƑ}

ࣘ෢. t=x⁽⁰⁾· · ·x^{(n)ʇɸʪƑєʊ}L(t)ࣣʍ·໑u₀, u₁, u₂, . . . ɫ฿ɧʨʫɾʇɶʅෙࢂ

ʱ஡ɮƑࣣʊࡲʘɾʇɩʩҺu_i^ʎ

u_i=u⁽⁰⁾_i x⁽⁰⁾u⁽¹⁾_i x⁽¹⁾· · ·u^(m_i ⁱ⁾, (m_i ≤n, u^(k)_i ∈Σ^∗_x(k))

ʇ೅ɸɲʇɫʆɬʪƑɸʪʇɡʪm ≤nɫਮݥɶʅƐ෗ڌʊਵɮʍm_i^ɫm^ʊφફɸʪ ʎɹʆɡʪƑ·໑ʍ೼ഒ໑ʎ·໑ʉʍʆƐɼʍʧɥʉu_iɿɰʱࡘʠʫʏʔɾɾʒ·໑ʱ ʃɮʪɲʇɫʆɬʪƑಀ܎ʱʃɰɪɧʅu₀, u₁, u₂, . . . ʇɸʪʇƐߣʍʧɥʉధ໑ʱ۵ɧ ʪɲʇɫʆɬʪƑ

u₀ u₁ u₂ · · ·

= = =

u⁽⁰⁾₀ u⁽⁰⁾₁ u⁽⁰⁾₂ · · · x⁽⁰⁾ x⁽⁰⁾ x⁽⁰⁾ ... ... ...

u^(m)₀ u^(m)₁ u^(m)₂ · · ·

ൊ੠3.3ʱu⁽⁰⁾₀ , u⁽⁰⁾₁ , u⁽⁰⁾₂ , . . . ʊ଼๑ɸʫʏƐەձઅ૦ਕљ໑u⁽⁰⁾_i0 u⁽⁰⁾_i1 u⁽⁰⁾_i2 · · · ^ɫ மʨʫʪƑui0, ui1, ui2, . . . ʎΧোʇɶʅ·໑ʆɡʪƑɼɲʆಀ܎i0, i1, i2, . . . ^ʱ0,1,2, . . . ʇʃɰɪɧʅடํʍմ໼ʱk= 1, . . . , mʊʃɣʅʡۼɧʏƐ·໑u0, u1, u2, . . . ^ʆɡʩʉ ɫʨƐҺk= 0, . . . , m^ʊʃɣʅu^(k)₀ u^(k)₁ u^(k)₂ · · · ɫەձઅ૦ਕљʉʡʍɫமʨʪ ʎɹʆɡʪƑɿɫɼɥɸʪʇu₀ u₁^{ʇʉʩෙࢂʆɡʪƑ}

ଜ๽3.5ʎൊ੠3.4ʇൊ੠3.6ɪʨ࡞ɥƑ

ࣣʆʎอڌʍഞߞࡘ܏Σɪʨࡰౙɶʅմ໼ʱ޳ʠɾɫƐʧʩφ౶ʊ௰ίʍ४໑౨ࢇ࢘

X =X,≤^{ɪʨࡰౙɶʅ}X^∗ࣣʍඨʠܦʞࢇ࢘ʱଜʠʪɲʇɫʆɬʪƑɲʍ࣪܏ƐԪؤ

≤^{∗ʱߣʍʧɥʊଜʠʪƑ}u≤^∗ t^{ɫ२ʩງʃʍʎƐ}u=x0· · ·x_k^ʆɡʩƐt^{ɪʨѕഞߞɪࠪ}

ʩ࢜ɣʅy₀· · ·y_k^ʇɸʪʇx₀ ≤y₀, . . . , x_k≤y_kɫ२ʩງʃ࣪܏ʆɡʪƑ ଜ๽3.7(Higmanʍൊ੠)

X,≤^{ɫ४໑౨ࢇ࢘ʉʨʏ}X^∗,≤^{∗ʡ४໑౨ࢇ࢘ʆɡʪƑ}

4 ४໑ ( ౨ ) ࢇ࢘ʍಐӇ

ฆ੠1.1ʇฆ੠1.2ʎƐʈʀʨʡ໑ʍอڌ१ʱɥʂɾɧʪʡʍʆɡʪƑɼɥʉʪʇຜࠖ

ʱສ଺ʊಐӇɶɾɮʉʂʅɮʪʍɿɫƐɾʇɧʏݍ૫ʍอڌ໑ʍ૫ɴʱಐӇɸʪɲʇʊί

ළʎʉɣƑʉɻʉʨʈʀʨʍ࣪܏ʡƐɣɮʨʆʡ૫ɣอڌ໑ɫਮݥɸʪɪʨʆɡʪ(ɼʫ ʆʡ෗ڌ໑ʎਮݥɶʉɣ)Ƒ1ʃʍࠬઞʎࢇ࢘ॐʱ๑ɣʪɲʇʆɡʪƑ

X =X,≤ʱ४໑ࢇ࢘ʇɸʪƑ४໑ࢇ࢘ʉʍʆƐ؃ʆʉɣʈʲʉ೼ഒࡘ܏Y ⊆X^ʊʡ ݍࢬٿɫɡʪƑʇɮʊƕ

• X^{ɫ؃ʆʉɣʉʨ}Xৌ੄ʍݍࢬٿɫɡʪƑɲʫʱ0ʇ࢑ɮƑ

• ^ʈʲʉ๗য়a∈X^{ʊʃɣʅʡƐࡘ܏}{b∈X :a < b}ʎ؃ʆʉɣʉʨʏݍࢬٿʱߡ ʃƑɲʫʱa+ 1ʇ࢑ɮƑ

• ^{ʈʲʉ෗ڌࣣࢸ໑}a₀< a₁ < a₂<· · · ^{ʊʃɣʅʡƐࡘ܏}

{b∈X:ɸʘʅʍi∈N^ʊʃɣʅai < b}

ʎ؃ʆʉɣʉʨݍࢬٿʱߡʃƑɲʫʱsup_i∈Na_i, sup{a₀, a₁, a₂, . . .}^உʇ࢑ɮƑ ଜ๽4.1

Τђʱෂɾɸ४໑ࢇ࢘O(ω1),≤^{ɫடثʱ࢜ɣʅɾɿ}1ʃਮݥɸʪƑ

(i) 0∈O(ω₁) (ˎ˿)

(ii) α∈O(ω₁) =⇒ α+ 1∈O(ω₁) (گ਩ࢇ࢘ॐ) (iii) α₀< α₁< α₂ <· · · ∈O(ω₁) =⇒ sup_i∈Nα_i ∈O(ω₁) (њޟיڌࢇ࢘ॐ) (iv) O(ω₁)ʍ๗য়ʎɸʘʅ(i), (ii), (iii)ʍɣɹʫɪʊɡʅʎʝʪƑ

O(ω₁)ʍ๗য়αʱњޟࢇ࢘ॐʇɣɥƑʝɾࡘ܏{β ∈O(ω₁) :β < α}^ʱO(α)ʇ࢑ɮƑɾ ʇɧʏO(ω₁)ʍ઺ʊʎΤђʍʧɥʉࢇ࢘ॐɫਮݥɸʪƑ

ω := sup{0,1,2, . . .}

ω·2 := sup{ω, ω+ 1, ω+ 2, . . .} ω² := sup{ω, ω·2, ω·3, . . .} ω^ω := sup{ω, ω², ω³, . . .} ε₀ := sup{ω, ω^ω, ω^ωω, . . .}

ʀʉʞʊω1ʎݍࢬʍಝњޟࢇ࢘ॐʱ೅ɸƑʈʲʉࠄॐʊʡO(ω1)ʍ๗য়ʱ1੆1ʊ੆ж ɴɺʪɲʇʎʆɬʪɿʬɥɪƗ DŽʆɬʪDžʇɣɥʍɫCantorʍໞ਩੄єজʆɡʪɫƐɼ ʍ२ಇʎZFCࡘ܏໼ɪʨஶງʆɡʪƑ

n^ʱ2Τࣣʍ߭োॐʇɸʪʇɬƐʈʲʉ߭োॐʡnद൥ʊʧʩ೅ɸɲʇɫʆɬʪƑɾʇ ɧʏ

324 = 10²·3 + 10¹·2 + 10⁰·4 = 10²+ 10²+ 10²+ 10¹+ 10¹+ 10⁰+ 10⁰+ 10⁰+ 10⁰ nʱ੝ɬɮʇʫʏʇʪʚʈƐ੝ɬʉॐʱࢭʉɣّॐʆ೅ɸɲʇɫʆɬʪƑʃʝʩ࣮൙Ώ࡬

ɫॲɷʪƑடํʊɶʅƐ(њޟʊڌʨɹ)ʈʲʉࢇ࢘ॐʡωद൥ʊʧʩ೅ɸɲʇɫʆɬʪƑ

ଜ๽4.2(Cantorೀࢀح)

ʈʲʉࢇ࢘ॐαʡߣʍحʊφίʊ೅ɸɲʇɫʆɬʪƑ

α = ω^β0+· · ·+ω^βk, α≥β0 ≥ · · · ≥β_k. α=β₀^{ɫ२ʩງʃʍʎ}α=ω^{αʍʇɬʊڌʪƑ}

ε₀ෆෂʍࢇ࢘ॐʊڌʂʅɣɧʏƐωद൥ʎɪʉʩɥʝɮ஝ɮƑࠄݣƐࣣʍଜ๽ʱ݌Ւ଺ʊ

଼๑ɸʫʏʈʲʉα∈O(ε₀)ʊʡઅφʍอڌ೅ߪʱ฿ɧʪɲʇɫʆɬʪƑɶɪɶε₀ =ω^ε0 ʇʉʂʅɶʝɥʍʆƐε0Τࣣʍࢇ࢘ॐʱΑɥʊʎƐɴʨʉʪۑ೟ɫ಴๗ʊʉʪƑ

ߣʍଜ๽ʊʧʩ४໑ࢇ࢘ʍສ଺ಐӇɫњఉʊʉʪƑɲɲʆ౨ࢇ࢘X,≤^{ɫњޟʆɡʪʇ} ʎƐࡘ܏X^{ʍҺ๗য়ʱ߭োॐʇ}1੆1ʊ੆жʄɰʨʫʪɲʇʱɣɥƑ౨ࢇ࢘X1 =X1,≤1 ʇX₂ =X₂,≤₂^{ɫடثʆɡʪʇʎƐ}X₁ ^ɪʨX₂^{ʗʍৌઅࠏ}f :X₁ −→X₂^{ʆࢇ࢘ʱൃ}

ʃʡʍɫਮݥɸʪɲʇʱɣɥƑ

a≤₁b ⇐⇒ f(a)≤₂ f(b).

ɲʍʇɬX1∼=X2ʇ࢑ɮƑO(α)∼=O(β)ʇʉʪʍʎα=β^{ʍʇɬʊڌʨʫʪƑ} ଜ๽4.3

X =X,≤^{ʱ౨ࢇ࢘ʇɸʪƑ}Xɫњޟ४໑ࢇ࢘ʆɡʪɲʇʍ಴๗࡝ഒࣰٛʎƐɡʪ α∈O(ω₁)ɫਮݥɶX∼=O(α)ɫ२ʩງʃɲʇʆɡʪƑ

ࣣʍα^ʍɲʇʱX,≤ʍࢇ࢘ثʇɣɣƐචۮʆʎo(X,≤)ʆ೅ɸƑ

ɴʅƐฆ੠1.1ʊற૙଺ʉࢇ࢘ॐʎಐӇ଺Ԝઅʊ֑ʠʪɲʇɫʆɬʪƑN^{ࣣʍਵࡥࡘ܏}

t= [n₀, . . . , n_k]∈M(N)ʊ੆ɶʅࢇ࢘ॐ

t^• := ωⁿ⁰ +· · ·+ω^nk (n₀ ≥n₁ ≥ · · · ≥n_k) ʱӘʩஆʅʪƑଜ๽4.2ʊʧʩ

β < ω^ω ⇐⇒ β =ωⁿ⁰+· · ·+ω^nk (n₀, . . . , n_k∈N, n₀ ≥ · · · ≥n_k) ʉʍʆƐɲʍ੆жʎO(ω^ω)ʗʍৌઅࠏʆɡʪƑɴʨʊ

ωⁿ⁺¹ = ωⁿ·ω > ωⁿ·k = ωⁿ+· · ·+ωⁿ (k^҉)

ɫ௰ίʍk∈Nʊʃɣʅ२ʩງʃʍʆƐu t⇐⇒ u^• ≤t^•ʇʉʪɲʇʡʮɪʪƑʧʂʅ ߣʍɲʇɫٗ໼ʆɬʪƑ

ଜ๽4.4

o(M(N), ) =ω^ω.

४໑౨ࢇ࢘ʍ࣪܏ʊʎɲʫʚʈ૰খ଺ʉ੆жʎʉɣƑɼɲʆଜ๽3.2ʱ๑ɣƐњޟ४໑ ౨ࢇ࢘X,≤ʍי੝ࢇ࢘ثʱΤђʆଜʠʪƑ

o(X,≤) := sup{o(X,≤) :≤^ʎ≤^{ʱҼ૗ɸʪৌࢇ࢘}} ∈O(ω₁).

ଜ๽4.5(De Jongh and Parikh 1977)

ࡘ܏Σʎnڎʍ๗য়ɪʨʉʪʇɸʪƑ

o(Σ^∗,) =ω^ωn−1.

ࣘ෢ʎ੝ഷʉʍʆࣈຊɸʪƑ

5 ʡɶʡ෠ৈɫ෼ɿʂɾʨ —Kruskal ʍଜ๽

Higmanʍൊ੠ʊʎɣɮʃɪʍҼ૗ɫઢʨʫʅɣʪƑ઺ʆʡݍʡอ෠ʆɡʩƐ˅̅˦˷ƪ

ˑѠӌʆ੝ߚʉดӘʱѢɾɸʍɫKruskalʍଜ๽(1960)ʆɡʪƑNASHਲʍ؅໿ʆɣɧ ʏƐɲʫʎओॲߝʊʃɰʪ෠ৈɫഞߞ໑ʆʎʉɮഞߞ “෼”ʍ࣪܏ʊਂஆɸʪƑΤђʆʎ ɲʍଜ๽ʍறലʉ࣪܏ʊʃɣʅজ෢ɸʪƑ

Σʱഞߞʍอڌࡘ܏ʇɸʪƑΤђʱෂɾɸݍࢬʍࡘ܏ʱT(Σ)ʇɩɮƑ f ∈Σ, t∈T(Σ)^∗ =⇒ f(t)∈T(Σ).

Һt ∈T(Σ)ʎΣʆ˻˫˽ೝɰɴʫɾ෼ʱ೅ɸƑɾʇɧʏ؃໑ε^ʎT(Σ)^∗ʊਦɸʪʍʆƐ f ∈ Σʉʨʏ f(ε) ∈ T(Σ)ʆɡʪƑɲʫʎઅφʍছ୐ɪʨʉʪ෼ʱ೅ɸƑʝɾ෼ʍ໑ t=t0· · ·tk∈T(Σ)^∗ɫ฿ɧʨʫɾʇɬƐu=f(t)ʎ

t0 · · · t_k

f

@@@@@@@@

~~

~~

~~

~~

ʍحʍ෼ʱ೅ɸƑS(u) :={t₀, . . . , t_k}^{ʇɩɮƑʝɾ෼}u^ʍ੝ɬɴ(ছ୐ʍॐ)ʱ߭োॐ|u|

ʆ೅ɸƑt_i∈S(u)ʉʨʏ|t_i|<|u|^{ʇʉʪɲʇʊુίƑ}

T(Σ)ࣣʍ౨ࢇ࢘ʆΤђʱෂɾɸݍࢬʍʡʍʱ(෼ʍ)ඨʠܦʞࢇ࢘ʇɣɣƐ^ʆ೅ɸƑ 0≤i≤k =⇒ tif(t0· · ·t_k)

u^∗t =⇒ f(u)f(t)

ɾɿɶu^∗t^{ɫ२ʩງʃʍʎƐ}u=u₀· · ·u_k^{ʆɡʩƐ෼ʍ໑}tɪʨɣɮʃɪʍ෼ʱࠪʩ࢜

ɣʅt₀· · ·t_k^ʇɸʫʏu₀ t₀, . . . ,u_k t_k^{ɫ२ʩງʃ࣪܏ʆɡʪ} (ଜ๽3.7ʱޖࣆ)Ƒਫ਼ φʍ१ࠃʧʩƐt_i∈S(u)ʉʨʏt_i u^{ʇʉʪɲʇʊુίƑ}

ଜ๽5.1(Kruskal 1960)

௰ίʍอڌࡘ܏ΣʊʃɣʅT(Σ), ^{ʎ४໑౨ࢇ࢘ʆɡʪƑ}

φٵHigmanʍൊ੠ʍԜઅʉφ౶ѓʊٵɧʪɫƐɲʍ४໑౨ࢇ࢘ʍי੝ࢇ࢘ثʎʇʅʃ

ʡʉɮ੝ɬɮʉʪ(Γ₀Τࣣ)Ƒࣘ෢ʎ(Nash-Williams 1963)ʍݍ·໑໼൥ʊʧʪ³Ƒ

3ݍ·໑ʍڀڶʎminimal bad sequenceʆɡʪƑච๨ʉʨיࢬ·໑ʇทɸʘɬʆɡʪɫƐڶ໠ɫʧɣʍʆ ݍ·໑ʇɶɾƑ

ൊ੠5.2

ʡɶʡT(Σ), ɫ४໑౨ࢇ࢘ʆʉɣʉʨʏƐΤђʍ१ࠃʱෂɾɸ·໑t₀, t₁, t₂, . . .(ݍ

·໑)ɫਮݥɸʪƑ௰ίʍ·໑u₀, u₁, u₂, . . . ^ʊʃɣʅ|t₀| ≤ |u₀|. ʝɾҺn ∈ N^ʇ t0, . . . , tnɪʨ޳ʝʪ௰ίʍ·໑t0, . . . , tn, un+1, un+2, . . . ^ʊʃɣʅ|tn+1| ≤ |uu+1|.

ࣘ෢. єଜʧʩ·໑ɫਮݥɸʪƑɼʍ઺ʆਫ਼φ܈ʍ੝ɬɴɫݍࢬʇʉʪʡʍʱ1ʃূʒƐ ɼʍਫ਼φ܈ʱt₀^{ʇɩɮƑɸʪʇ}t₀ɪʨ޳ʝʪ·໑ɫਮݥɸʪʍʆƐɼʍ઺ʆਫ਼௡܈ʍ੝

ɬɴɫݍࢬʇʉʪʡʍ1ʃʱূʒƐɼʍਫ਼௡܈ʱt₁^{ʇɩɮƑΤђடํƑ}

ൊ੠5.3

T(Σ), ʎ४໑౨ࢇ࢘ʆʉɣʇєଜɶƐɼʍݍ·໑ʱ t₀, t₁, t₂, . . . ^ʇɸʪƑS :=

i∈NS(ti)ʇɸʪʇƐS,^{ʎ४໑౨ࢇ࢘ʆɡʪƑ}

ࣘ෢. єʊS^ɫ·໑s₀, s₁, s₂, . . . ʱ԰ʟʇɸʪƑɲʍʇɬƐɸʘʅʍi, n ∈ N^ʊʃɣʅ s_i ∈S(t_n)ʇʉʪɲʇʱnʊʃɣʅʍՒఈ൥ʆߪɸƑ

ʝɹsi∈S(t0)ʉʨʏ|si|<|t0|^ʇʉʪɫƐsi, si+1, si+2, . . . ʎ·໑ʉʍʆƐɲʫʎݍ·

໑ʍଜձʊ౩ɸʪƑ

ߣʊsi ∈S(tn+1)^{ʇєଜɸʪʇƐ}

t₀, . . . , t_n, s_i, s_i+1, s_i+2, . . .

ʎ·໑ʆɡʪƑࠄݣƐɡʪt_k^ʇs_j ^ʊʃɣʅt_k s_j^{ʇʉʂɾʇɸʪʇƐ}s_j ∈ S(t_l)ʉʪ t_l ^ʊʃɣʅt_k t_l^ʇʉʩƐt₀, t₁, t₂, . . . ɫ·໑ʆɡʪɲʇʊ౩ɸʪ (Ւఈ൥ʍєଜʧʩ s_j ∈S(t₀)∪ · · · ∪S(t_n)ʉʍʆk≤n < l^{ʇʉʪɲʇʊુί})Ƒɶɪɶ|s_i|<|t_n+1|^ʉʍʆƐ ɲʫʎݍ·໑ʍଜձʊ౩ɸʪƑʧʂʅs_i ∈S(t_n+1).

Τࣣɪʨs0∈S(tn)ɫɸʘʅʍnʊʃɣʅ२ʩງʃɲʇʊʉʪɫƐɲʫʎs0 ∈S^ʊෙ

ࢂɸʪƑ

Τࣣʆଜ๽5.1ʱࣘ෢ɸʪࢀಡɫ४ʂɾƑєʊT(Σ),ɫ४໑౨ࢇ࢘ʆʉɣʇɸʪʇƐ ݍ·໑t0, t1, t2, . . . ^{ʇ४໑౨ࢇ࢘}S,^{ɫਮݥɸʪƑ}ΣʎอڌʉʍʆƐɡʪf ∈Σɫਮݥ ɶƐݍ·໑t₀, t₁, t₂, . . . ^ʎ

f(u₀), f(u₁), f(u₂), . . . (u_i ∈S^∗)

ʍحʍ೼ഒ໑ʱ԰ʟƑɲʫʎ·໑ʍ೼ഒ໑ʉʍʆƐʔɾɾʒ·໑ʆɡʪƑɶɪɶଜ๽3.7 ʧʩS^∗,^{∗ʎ४໑౨ࢇ࢘ʉʍʆƐ}u₀,u₁,u₂, . . . ʎ·໑ʆʎʉɣƑʧʂʅɡʪi < j^ʊ ʃɣʅu_i ^∗ u_jɫ२ʩງʃƑɿɫɼɥɸʪʇf(u_i)f(u_j)ʇʉʩෙࢂʆɡʪƑʧʂʅ T(Σ),^{ʎ४໑౨ࢇ࢘ʆɡʪƑ}

ݍ·໑໼൥ʎత๽൥ʱѕ୩ʡ௬ʫ޶ʊɶʅ๑ɣʪʍʆƐۥ२଺ʉԣ୐ɪʨɣɧʏಝ࣭ʊ ʮɪʩʊɮɣƑʡʂʇʮɪʩʣɸɮƐʡʂʇ“ۥ२଺”ʉࣘ෢ʎʉɣɿʬɥɪƗ

ɴʨʊӌʕɾʠʊ. ޖ۵ഞٯʱ3ʃ֣ɱʅɩɮƑ

• Jean H. Gallier. What’s so special about Kruskal’s theorem and the ordinal Γ₀? A survey of some results in proof theory. Annals of Pure and Applied Logic, 53(3):

199 - 260, 1991. ಝ࣭ʊ૎௷ʊ࢑ɪʫɾˇƪ̆ʹʶƑ฽ಡઢ߳ʉɶʆʡஷʠʪƑ

• Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge, 1998.

˅̅˦˷ƪˑѠӌʊɩɰʪ܈࢑ɬԋɧػʍ׃Ѡ࢑ƑKruskalʍଜ๽ʎʇɮʊɲʍഒ ฐʆࡥ๗ʉดӘʱѢɾɸƑ

• ^ओπ೚ۗ. ॐӌՂ৛໼. Զఔ࢑୉, 2011. ॐӌՂ৛໼ʊԪɸʪࡥۆʉ௬ฉ࢑Ƒ४໑ࢇ

࢘ʣࢇ࢘ॐʎॐӌՂ৛໼ʊɩɣʅʡࡥ๗ʉดӘʱѢɾɸƑ

˾˯ƪ˚ѳ੠. Τђ4ฆʍɥʀ2 ∼3ฆʱূ੨ɶʅஊɧʧƑ

1. ৌࢇ࢘ʆʎʉɣɫ౨ࢇ࢘ʆɡʪX,≤ʍ׿੄ແʱ֣ɱʧƑɾɿɶX^{ʎ෗ڌࡘ܏ʆ} ʉɰʫʏʉʨʉɣƑ

2. Xܙʊʎ෗ڌڎʍˇ˕ʽƪ˓ƪ˲X ={a, b, c, . . .}ɫਮݥɸʪƑ˼ƪ˂঩ʱۼʂɾ

ٗѢƐҺ˓ƪ˲a∈X^{ʊʃɣʅ࢟ʀ୐}w(a) ∈N^ʇਅம୐s(a)∈N^{ɫଜʝʂɾƑɾ} ɿɶw(a) = w(b), s(a) = s(b)ʱִʊෂɾɸ2˓ƪ˲a, b∈ X^{ʎʉɪʂɾʇɸʪƑ}

ࢇΦೝɰʱΤђʍʧɥʊۼɥƑ

a≤b ⇐⇒ w(a)< w(b) ʝɾʎ (w(a) =w(b) ɪʃ s(a)≤s(b)). ɲʍʇɬX,≤ʎৌࢇ࢘ʆɡʩƐɴʨʊ४໑ࢇ࢘ʆɡʪɲʇʱࣘ෢ɺʧƑ

3. ४໑౨ࢇ࢘X₁,≤₁,X₂,≤₂^{ɫ฿ɧʨʫɾʇɬƐ}X₁×X₂^{ࣣʍ౨ࢇ࢘}≤^ʱΤђʍ ʧɥʊଜʠʪƑ

(a1, a2)≤(b1, b2) ⇐⇒ a1 ≤1b1 ɪʃ a2 ≤2b2 (a1, b1 ∈X1, a2, b2 ∈X2) ɲʍʇɬX₁×X₂,≤ɫ४໑౨ࢇ࢘ʆɡʪɲʇʱࣘ෢ɺʧ(ˤ̅˚ƕൊ੠3.3ʱ๑ ɣʧ)Ƒ

4. ɡʉɾʎʼ˳˻ˋɪʨൈʞ֞ʩʝɸɪƗ ൈʞ֞ʩʝɺʲɪƗʆɬʪɿɰఈமʍɣɮ

໼֢ʱ֣ɱʅ߭ഒʍূ੨ʱ९ஆѓɶʅɮɿɴɣƸ20ۼପ୩ƹƑ