ترتيب شبه أفضل

في نظرية الترتيب، يُعرف الترتيب شبه الجيد (bqo) بأنه ترتيب شبه لا يقبل نوعًا معينًا من المصفوفات غير الجيدة. كل ترتيب شبه جيد هو ترتيب شبه جيد .

على الرغم من أن مفهوم الترتيب شبه الجيد جذاب، إلا أن العديد من العمليات اللانهائية المهمة لا تحافظ على خاصية الترتيب شبه الجيد. يوضح مثالٌ من ريتشارد رادو هذا الأمر. ^{[ 1 ]} في ورقة بحثية نُشرت عام 1965، صاغ كريسبين ناش ويليامز مفهومًا أقوى هو الترتيب شبه الأفضل، وذلك لإثبات أن فئة الأشجار ذات الارتفاع ω مرتبة ترتيبًا شبه جيدًا في ظل علاقة التقسيم الطوبولوجي . ^{[ 2 ]} ومنذ ذلك الحين، تم إثبات أن العديد من الترتيبات شبه الجيدة هي ترتيبات شبه جيدة من خلال إثبات أنها ترتيبات شبه أفضل. على سبيل المثال، أثبت ريتشارد لافر نظرية لافر (التي كانت في السابق تخمينًا لرولان فرايسيه ) من خلال إثبات أن فئة أنواع الترتيب الخطي المبعثرة مرتبة ترتيبًا شبه أفضل. ^{[ 3 ]} في الآونة الأخيرة، أثبت كارلوس مارتينيز-رانيرو أنه في ظل بديهية الإجبار المناسبة ، تكون فئة خطوط أرونساين مرتبة شبه مرتبة بشكل أفضل في ظل علاقة التضمين. ^{[ 4 ]}

من الشائع في نظرية الترتيب شبه الأفضل كتابة${\displaystyle {_{*}}x}$بالنسبة للتسلسل${\displaystyle x}$مع حذف الحد الأول. اكتب${\displaystyle [\omega ]^{<\omega }}$بالنسبة لمجموعة المتتاليات المنتهية والمتزايدة تمامًا ذات الحدود في${\displaystyle \omega }$، وتحديد علاقة${\displaystyle \triangleleft }$على${\displaystyle [\omega ]^{<\omega }}$على النحو التالي:${\displaystyle s\triangleleft t}$إذا كان هناك${\displaystyle u\in [\omega ]^{<\omega }}$بحيث${\displaystyle s}$هو جزء أولي صارم من${\displaystyle u}$و${\displaystyle t={}_{*}u}$العلاقة${\displaystyle \triangleleft }$ليست فعلًا متعديًا .

كتلة​${\displaystyle B}$هي مجموعة جزئية غير منتهية من${\displaystyle [\omega ]^{<\omega }}$التي تحتوي على جزء أولي من كل مجموعة جزئية لانهائية من${\displaystyle \bigcup B}$. لترتيب شبهي${\displaystyle Q}$، أ${\displaystyle Q}$-pattern هي دالة من كتلة ما${\displaystyle B}$داخل${\displaystyle Q}$أ.${\displaystyle Q}$-نمط${\displaystyle f\colon B\to Q}$يقال إنه أمر سيئ إذا${\displaystyle f(s)\not \leq _{Q}f(t)}$لكل زوج${\displaystyle s,t\in B}$بحيث${\displaystyle s\triangleleft t}$؛ خلاف ذلك${\displaystyle f}$جيد . شبه ترتيب${\displaystyle Q}$يُطلق عليه اسم الترتيب شبه الأفضل إذا لم يكن هناك ترتيب سيئ${\displaystyle Q}$-نمط.

ولتسهيل التعامل مع هذا التعريف، يُعرّف ناش-ويليامز الحاجز بأنه كتلة تكون عناصرها غير قابلة للمقارنة ثنائياً في ظل علاقة التضمين.${\displaystyle \subset }$أ.${\displaystyle Q}$-array هو${\displaystyle Q}$نمط يكون نطاقه حاجزًا. بملاحظة أن كل كتلة تحتوي على حاجز، يتضح أن${\displaystyle Q}$يكون الترتيب شبه الأفضل إذا وفقط إذا لم يكن هناك ترتيب سيئ${\displaystyle Q}$-array.

قدّم سيمبسون تعريفًا بديلًا للترتيب شبه الأفضل بدلالة دوال بوريل.${\displaystyle [\omega ]^{\omega }\to Q}$، أين${\displaystyle [\omega ]^{\omega }}$، مجموعة المجموعات الجزئية اللانهائية من${\displaystyle \omega }$، يتم إعطاؤها بنية المنتج المعتادة . ^{[ 5 ]}

يترك${\displaystyle Q}$كن شبه ترتيب ومنح${\displaystyle Q}$مع الطوبولوجيا المنفصلة . أ${\displaystyle Q}$-array هي دالة بوريل${\displaystyle [A]^{\omega }\to Q}$لبعض المجموعات الجزئية اللانهائية${\displaystyle A}$ل${\displaystyle \omega }$أ.${\displaystyle Q}$-مصفوفة${\displaystyle f}$سيئ إذا​${\displaystyle f(X)\not \leq _{Q}f({_{*}}X)}$لكل${\displaystyle X\in [A]^{\omega }}$; ${\displaystyle f}$جيد في غير ذلك. الترتيب شبه الرسمي${\displaystyle Q}$يُعدّ ترتيبًا شبه مثالي إذا لم يكن هناك ترتيب سيئ.${\displaystyle Q}$-مصفوفة بهذا المعنى.

تُعدّ العديد من النتائج الرئيسية في نظرية الترتيب شبه الأمثل نتاجًا لفرضية المصفوفة السيئة الدنيا، والتي وردت في ورقة سيمبسون ^{[ 5 ]} على النحو التالي. انظر أيضًا ورقة لافر ^{[ 6 ]} ، حيث ذُكرت فرضية المصفوفة السيئة الدنيا لأول مرة كنتيجة. وقد وُجدت هذه التقنية في ورقة ناش-ويليامز الأصلية عام 1965.

يفترض${\displaystyle (Q,\leq _{Q})}$هو ترتيب شبه رسمي . تصنيف جزئي${\displaystyle \leq '}$ل${\displaystyle Q}$هو ترتيب جزئي متين لـ${\displaystyle Q}$بحيث${\displaystyle q\leq 'r\to q\leq _{Q}r}$. للسوء${\displaystyle Q}$-المصفوفات (بمعنى سيمبسون)${\displaystyle f\colon [A]^{\omega }\to Q}$و${\displaystyle g\colon [B]^{\omega }\to Q}$، يُعرِّف:

${\displaystyle g\leq ^{*}f{\text{ إذا كان }}B\subseteq A{\text{ و }}g(X)\leq 'f(X){\text{ لكل }}X\in [B]^{\omega }}$

${\displaystyle g<^{*}f{\text{ إذا }}B\subseteq A{\text{ و }}g(X)<'f(X){\text{ لكل }}X\in [B]^{\omega }}$

نقول سيئ${\displaystyle Q}$-مصفوفة${\displaystyle g}$هو أقل سوءًا (فيما يتعلق بالترتيب الجزئي)${\displaystyle \leq '}$) إذا لم يكن هناك شيء سيء${\displaystyle Q}$-مصفوفة${\displaystyle f}$بحيث${\displaystyle f<^{*}g}$تعريفات${\displaystyle \leq ^{*}}$و${\displaystyle <'}$يعتمد على تصنيف جزئي${\displaystyle \leq '}$ل${\displaystyle Q}$العلاقة${\displaystyle <^{*}}$ليس هذا هو الجزء الصارم من العلاقة${\displaystyle \leq ^{*}}$.

نظرية (مبدأ المصفوفة السيئة الدنيا) . ليكن${\displaystyle Q}$لنفترض أن لدينا ترتيبًا شبهيًا مزودًا بترتيب جزئي.${\displaystyle f}$إنه أمر سيء${\displaystyle Q}$-المصفوفة. ثم هناك حد أدنى من السيئ${\displaystyle Q}$-مصفوفة${\displaystyle g}$بحيث${\displaystyle g\leq ^{*}f}$.

• ترتيب شبه جيد
• نظام جيد