(Translated by https://www.hiragana.jp/)
良擬序 - 维基百科,自由的百科全书 とべ转到内容ないよう

りょうなずらえじょ

本页使用了标题或全文手工转换
维基百科ひゃっか自由じゆうてき百科ひゃっかぜん

数学すうがくぶんささえじょなかりょうなずらえじょあるあずかじょ英語えいごwell-quasi-ordering,簡寫さくwqo[1]あるWQO[2]特殊とくしゅてきなずらえじょ[註 1],其元素的すてき任意にんい无穷序列じょれつなか,必有先後せんごりょうこう遞增ていぞうそく存在そんざい使つかい

動機どうき

[编辑]

良基よしもと歸納きのうほう可用かよう於任なに良基よしもと關係かんけいうえよう證明しょうめいぼうしゅうてき全部ぜんぶ元素げんそみなぼう性質せいしつ所以ゆえんあるもとかい考慮こうりょぼうなずらえじょいや良基よしもと[註 3]良基よしもとなずらえじょてきるいたいぼう運算うんざんふう閉,そくゆかりぼう良基よしもとなずらえじょ出發しゅっぱつけい若干じゃっかん運算うんざん構造こうぞう而成てきしんなずらえじょ一定いってい良基よしもとよく使しんなずらえじょ仍為良基よしもとげんなずらえじょ追加ついか若干じゃっかんきりせい

べきしゅう運算うんざんためれいきゅうてい集合しゅうごううえてきなずらえじょ定義ていぎべきしゅううえてきなずらえじょ使つかいとう且僅とうたいまとごと元素げんそみなざいちゅう找到元素げんそだい於等於該元素げんそ證明しょうめい必良もとただし若原わかはらなずらえじょためりょうなずらえじょのりべきしゅうてきなずらえじょ確實かくじつ良基よしもと[3]:116

定義ていぎ

[编辑]

集合しゅうごううえてきりょうなずらえじょwell-quasi-orderingいちしゅ预序关系そく滿足まんぞくはんせい传递せいまとてき二元にげん關係かんけい),使つかいとくちゅう任意にんい无穷序列じょれつみなゆう先後せんごりょうこう遞增ていぞうわかゆう此種りょうなずらえじょのり本身ほんみたたえためりょうなずらえじょしゅうwell-quasi-ordered set),簡寫ためwqo[1]:210–211

りょうへんじょwell-partial-orderingすんでりょうなずらえじょまたこれへんじょそくじょ前述ぜんじゅつ條件じょうけんがいなお反對稱はんたいしょうせい

りょうなずらえじょゆう其他等價とうか定義ていぎ,如將條件じょうけんあらためためすんで含無きゅう嚴格げんかく遞減ていげん序列じょれつ[註 2]また任意にんいりょうこう不可ふかてき無窮むきゅう序列じょれつ換言かんげんなずらえじょためりょうなずらえじょとう且僅とう良基よしもと,且不含無きゅうはん。(あずか§ 無窮むきゅう遞增ていぞう序列じょれつてきひしげ姆齊論證ろんしょう相似そうじ。)[1]:211

性質せいしつ

[编辑]
  • きゅうていなずらえじょざいべきしゅうじょうゆう另一なずらえじょ,其中。此關係かんけいため良基よしもととう且僅とう本身ほんみwqo[3]:116
  • きゅうていりょうなずらえじょわかゆういちれつしゅう,其中ごとしゅうみな向上こうじょうふう[註 4]のり序列じょれつおわり必恆じょうそくぼうおこり以後いご各項かくこうかりわかしかのりたいまい存在そんざい使つかいそらしたがえちゅうせんいち元素げんそ,如此ぼう無窮むきゅう序列じょれつ,其無遞增ていぞうてきりょうこう
  • きゅうていりょうなずらえじょてきにんなんしゅうせき僅得有限ゆうげん極小きょくしょうもといやのり該些極小きょくしょうもと組成そせい無窮むきゅうはん鏈。

無窮むきゅう遞增ていぞう序列じょれつ

[编辑]

わかためwqoのり任意にんい無窮むきゅう序列じょれつみな有無うむきゅうじょうます序列じょれつかくしたしるべ)。此種子しゅし序列じょれつあるしょうためかん」(perfect)。[4]:245可用かようひしげ姆齊しょうほう[註 5]きゅうてい序列じょれつ考慮こうりょ全部ぜんぶなか何者なにもの使右邊うへんぼつゆうにんなに滿足まんぞく此種てき集合しゅうごうためわか無窮むきゅうのりためしるべしゅうてき序列じょれつはた不具ふぐ遞增ていぞうてきりょうこうあずかためwqoてき假設かせつ抵觸ていしょく所以ゆえんため有限ゆうげんしゅう。衹要だいちゅう所有しょゆう元素げんそのりぞくゆうぼう使つかい,如此逐項延伸えんしんとくいたきゅう遞增ていぞう序列じょれつ

任意にんい序列じょれつみな有無うむきゅうじょうますれつあずかwqoてき條件じょうけん等價とうかまた作為さくいいちしゅ定義ていぎ[4]:245

れい

[编辑]
いち整數せいすうてき平常へいじょう順序じゅんじょ
自然しぜんすう整除せいじょじょてき哈斯
さんかくもう逐分りょうはいじょてき哈斯
  • 自然しぜんすうしゅう配備はいび平常へいじょうてき大小だいしょうじょりょうへんじょ乃至ないしりょうじょわか允許いんきょ負數ふすうかわなる整數せいすうしゅうてき大小だいしょうじょのりなみりょうなずらえじょいんため此大しょう關係かんけいなみ良基よしもと負數ふすう組成そせい遞增ていぞうりょうこうてき序列じょれつ。(いち
  • 自然しぜんすうしゅう整除せいじょじょりょうなずらえじょしつすう兩兩りょうりょう不可ふか比較ひかく組成そせい無窮むきゅうはん鏈。(
  • 自然しぜんすうもとくみてき集合しゅうごう逐分りょうはいじょえいproduct order[註 6]りょうへんじょ。此為すすむかつへりくだ引理えいDickson's lemma[5]さん)。さら一般いっぱんわかためりょうなずらえじょのりたい任意にんいせい整數せいすうせきじょえいproduct orderまたりょうなずらえじょ
  • しつらえため有限ゆうげんしゅう,且至しょうゆう兩個りゃんこ元素げんそかつ莱尼ほしごう字母じぼてき全體ぜんたい有限ゆうげんくしこれしゅう。按字典じてんじょりょうなずらえじょいんため有無うむきゅう遞降序列じょれつ同樣どうようせきぜんつづり關係かんけいまたりょうなずらえじょいんため前述ぜんじゅつ序列じょれつざい該偏じょ無窮むきゅうはん鏈。しか而,倘按序列じょれつ關係かんけいはいじょのりりょうへんじょ[6]ざい衹有いち元素げんそてき退化たいか情況じょうきょう,此さんしゅへんじょ完全かんぜんいちよう。)
  • 推而廣之ひろゆき,以ため字母じぼしゅうてき有限ゆうげんくししゅう,按「嵌入かんにゅうはいじょ,如此組成そせいなずらえじょとう且僅とう本身ほんみりょうなずらえじょ,此結論けつろんたたえためまれかく曼引えいHigman's lemma[7]。其中所謂いわゆるくし嵌入かんにゅういた意思いし中有ちゅううあずかひとしちょうてき序列じょれつ,逐項だい於等於わかははしゅうためじょしゅうのりくしとう且僅とうこれてき序列じょれつ退化たいかなりぜん款情きょう
  • 相反あいはんりょうなずらえじょうえてき無窮むきゅう序列じょれつしゅうため,按嵌入かんにゅうじょ一般いっぱん不為ふためりょうなずらえじょ換言かんげんまれかく曼引適用てきよう於無きゅう序列じょれつ數學すうがく引入ゆうなずらえじょえいBetter-quasi-ordering,以期もち推廣まれかく曼引
  • wqo これ元素げんそ標記ひょうき頂點ちょうてんてき有限ゆうげんじゅ全體ぜんたい,按嵌入かんにゅうはいじょ,也是wqoそくかつ魯斯かつなんじじゅ定理ていりえいKruskal's tree theorem[1]此處ここてきゆう選定せんてい節點せってん,而嵌入かんにゅうてき要求ようきゅう有三ゆうぞうぼう節點せってんてき節點せってんよううついた該節てんぞうてき後嗣こうしどう節點せってんてき不同ふどう節點せってんよううついた該節てんぞうてき不同ふどう子分こぶんささえじょうごと節點せってんしょてき標記ひょうきしょう於等於其ぞうてき標記ひょうき
  • 無窮むきゅうじゅあいだてき嵌入かんにゅう關係かんけい[註 7]これwqoゆかりかつさと斯平·おさめもと-れんえいCrispin St. J. A. Nash-Williamsところしょう[8][9]
  • すうぜんじょるいあいだてき嵌入かんにゅう關係かんけいりょうなずらえじょ同樣どうようえいscattered order[註 8]ぜんじょるいあいだまたしか。(萊弗定理ていりえいLaver's theorem[10]
  • すうぬの尔代すうてき嵌入かんにゅうじょりょうなずらえじょゆかり萊弗定理ていりしょうとく[11]:98
  • 有限ゆうげん图子しきじょぐみ成良なるよしなずらえじょしゅう。(はくへりくだ-西にし定理ていりえいRobertson–Seymour theorem
  • たいまいせい整數せいすうふかえいtree-depthいたりおおためまと,按导出じょくみ成良なりながなずらえじょしゅうまた同上どうじょう考慮こうりょ以良なずらえじょ標記ひょうき其頂てんなみ要求ようきゅう導出どうしゅつてき嵌入かんにゅううつ使つかいごと頂點ちょうてんてきぞうてき標記ひょうきみなだい於等於原標記ひょうき,仍得りょうなずらえじょ[12]此外,やくえいcograph導出どうしゅつじょ構成こうせいなずらえじょ[13]

與良よらへんじょてき關聯かんれん

[编辑]

字面じめんじょうりょうなずらえじょ較良へんじょ廣義こうぎただしもと於以觀察かんさつ兩者りょうしゃ實際じっさい分別ふんべつだい[4]:250一方いっぽうめんwpo必為wqo。另一方面ほうめんわかゆうぼうwqoのり其各等價とうかるい[註 9]組成そせいwpo。舉例整數せいすうしゅうてき整除せいじょじょなずらえじょただしりょうなずらえじょ),其等價とうかるいがた所以ゆえん等價とうかるい組成そせいてきへんじょどう構於

よりどころまいしかおさめ[2],「考慮こうりょなずらえじょなみへんじょさらため概括がいかつ……僅是いんため較方便びん。」またれい如,ざいぜんじょるいてき嵌入かんにゅうなずらえじょちゅうひらき區間くかんあずか閉區あいだ不同ふどう構,ただし互相嵌入かんにゅう所以ゆえんざい對應たいおうへんじょちゅうぞくどういち等價とうかるいたく斯·ぶく斯特えいThomas Forster (mathematician)しょう等價とうかるい乎不很有啓發けいはつせい」,而且,全體ぜんたいへんじょしゅう包含ほうがん關係かんけい組成そせいてきへんじょるい,雖然完備かんびえいChain completeただしなみ完備かんびえいCompleteness (order theory)わかあらためため考慮こうりょ全體ぜんたいなずらえじょしゅうそくかいゆう問題もんだい[3]:112

[编辑]
  1. ^ なずらえじょquasi-orderingためあずかじょpreorderてき別名べつめい
  2. ^ 2.0 2.1 いい
  3. ^ 此處ここらゆう濫用らんよう術語じゅつごしょうなずらえじょ良基よしもと實際じっさいせつ嚴格げんかくじょ[註 2]ため良基よしもと
  4. ^ しゅう向上こうじょうふう意思いし
  5. ^ ひしげ姆齊定理ていり斷言だんげん無窮むきゅう頂點ちょうてんてきちゅうまいあたりしみべにあいりょういろいちのり必有同色どうしょく無窮むきゅうかい完全かんぜん此處ここわかのりしみべにいやのりしみあいWqo條件じょうけんそく紅色こうしょく無窮むきゅうかい完全かんぜん必有藍色あいいろ無窮むきゅうかい完全かんぜんそく遞增ていぞう序列じょれつ
  6. ^ 逐個分量ぶんりょうゆう
  7. ^ そくひらけなぐしきえいtopological minor關係かんけい
  8. ^ ぼつゆういち元素げんそてき稠密ちゅうみつじょ
  9. ^ りょう元素げんそ等價とうか定義ていぎため

參考さんこう文獻ぶんけん

[编辑]
  1. ^ 1.0 1.1 1.2 1.3 Kruskal, J. B. Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture [りょうなずらえじょ定理ていりかわらようあま猜想] (PDF). Transactions of the American Mathematical Society (American Mathematical Society). 1960-05, 95 (2): 210–225 [2021-12-24]. JSTOR 1993287. MR 0111704. doi:10.2307/1993287. (原始げんし内容ないようそん (PDF)于2021-10-21) えい语). 
  2. ^ 2.0 2.1 Milner, E. C. Basic WQO- and BQO-theory [基礎きそWQOあずかBQOろん]. Rival, I. (编). Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and Its Applications [あずかじょゆうじょしゅう理論りろんちゅうてきかくしょく,及應用おうよう]. D. Reidel Publishing Co. 1985: 487–502 [2021-12-24]. ISBN 90-277-1943-8. (原始げんし内容ないようそん于2021-12-24) えい语). no real gain in generality is obtained by considering quasi-orders rather than partial orders… it is simply more convenient to do so. 
  3. ^ 3.0 3.1 3.2 Forster, Thomas. Better-quasi-orderings and coinduction [ゆうなずらえじょあずか歸納きのう]. Theoretical Computer Science. 2003, 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2可免费查阅 えい语). 
  4. ^ 4.0 4.1 4.2 Harzheim, Egbert. 8.2 The notions well-quasi-ordered and partially well-ordered set [だい8.2せつりょうなずらえじょあずかへんじょしゅう概念がいねん]. Ordered sets [ゆうじょしゅう]. [2021-12-20]. doi:10.1007/0-387-24222-8_9. (原始げんし内容ないようそん于2021-12-24) えい语). 
  5. ^ Dickson, L. E. Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors [r異質いしつ因數いんすうてき完全かんぜんすう與本よもとげん過剩かじょうすう僅得有限ゆうげん]. American Journal of MathematicsえいAmerican Journal of Mathematics. 1913, 35 (4): 413–422. JSTOR 2370405. doi:10.2307/2370405 えい语). 
  6. ^ W. GasarchえいW. Gasarch. A survey of recursive combinatorics [遞歸組合くみあいがく綜述]. Yu. L. Ershov, S.S. Goncharov, A. Nerode, J.B. Remmel, V.W. Marek (编). Handbook of Recursive Mathematics, Vol. 2 [遞歸數學すうがくしゅさつ·まき]. Stud. Logic Found. Math. 139. Amsterdam: North-Holland. 1998: 1041–1176. MR 1673598. doi:10.1016/S0049-237X(98)80049-9 えい语).  ゆう其見だい1160ぺーじ
  7. ^ Higman, G. Ordering by divisibility in abstract algebras [抽象ちゅうしょう代數だいすうちゅう,按整除せいじょはいじょ]. Proceedings of the London Mathematical Society. 1952, 2: 326–336. doi:10.1112/plms/s3-2.1.326 えい语). 
  8. ^ Nash-Williams, C. On well-quasi-ordering infinite trees [はた無窮むきゅうじゅりょうなずらえじょ]. Mathematical Proceedings of the Cambridge Philosophical Society. 1965, 61 (3): 697–720. doi:10.1017/S0305004100039062 えい语). 
  9. ^ Kühn, D. On well-quasi-ordering infinite trees – Nash–Williams's theorem revisited [はた無窮むきゅうじゅりょうなずらえじょ——再論さいろんおさめもと-れん定理ていり]. Mathematical Proceedings of the Cambridge Philosophical Society. 2001, 130 (3): 401–408. doi:10.1017/S0305004101005011 えい语). 
  10. ^ Laver, Richard. On Fraïssé's Order Type Conjecture [ろんどるひしげふさがじょるい猜想]. Annals of Mathematics, Second Series. 1971-01, 93 (1): 89–111 えい语). 
  11. ^ Ruškuc, Nik. Well quasi-order in combinatorics and algebra [組合くみあいあずか代數だいすうりょうなずらえじょ] (PDF). 2015 [2021-12-24]. (原始げんし内容ないようそん (PDF)于2021-12-24) えい语). 
  12. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice. Lemma 6.13. Sparsity: Graphs, Structures, and Algorithms [まれ疏性:結構けっこう算法さんぽう]. Algorithms and Combinatorics 28. Heidelberg: Springer. 2012: 137. ISBN 978-3-642-27874-7. MR 2920058. doi:10.1007/978-3-642-27875-4 えい语). 
  13. ^ Damaschke, Peter. Induced subgraphs and well-quasi-ordering [導出どうしゅつ與良よらなずらえじょ]. Journal of Graph Theory. 1990, 14 (4): 427–435. MR 1067237. doi:10.1002/jgt.3190140406 えい语). 
  • Kruskal, J. B. The theory of well-quasi-ordering: A frequently discovered concept [りょうなずらえ序論じょろんつね發現はつげんてき概念がいねん]. Journal of Combinatorial TheoryえいJournal of Combinatorial Theory. Series A. 1972, 13 (3): 297–305. doi:10.1016/0097-3165(72)90063-5可免费查阅 えい语). 
  • Ketonen, Jussi. The structure of countable Boolean algebras [すうぬのなんじ代數だいすうてき結構けっこう]. Annals of Mathematics. 1978, 108 (1): 41–89. JSTOR 1970929. doi:10.2307/1970929 えい语). 
  • Gallier, Jean H. What's so special about Kruskal's theorem and the ordinal Γがんまo? A survey of some results in proof theory [かつ魯斯かつしかていあずかあずかじょすうΓがんまoゆうなん特別とくべつ證明しょうめいろん若干じゃっかん結果けっかてき綜述]. Annals of Pure and Applied Logic. 1991, 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E可免费查阅 えい语).