علاقة راسخة

العلاقات الثنائية المتعدية  v ت هـ
متماثل مضاد للتناظر متصل مؤسس بشكل جيد لديه روابط لديه لقاءات انعكاسي غير انعكاسي غير متماثل توتال، سيميكونكس مضاد للانعكاس علاقة التكافؤ Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ طلب مسبق (طلب شبه رسمي) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ طلب جزئي ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ إجمالي الطلبات المسبقة ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ إجمالي الطلب ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ الطلب المسبق ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ ترتيب شبه جيد ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ ترتيب جيد ✗ Y Y Y ✗ ✗ Y ✗ ✗ شعرية ✗ Y ✗ ✗ Y Y Y ✗ ✗ الانضمام إلى شبه الشبكة ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ شبكة اللقاءات ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ ترتيب جزئي صارم ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y ترتيب ضعيف صارم ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y إجمالي الطلب الصارم ✗ Y Y ✗ ✗ ✗ ✗ Y Y متماثل مضاد للتناظر متصل مؤسس بشكل جيد لديه روابط لديه لقاءات انعكاسي غير انعكاسي غير متماثل التعريفات، للجميع${\displaystyle a,b}$و${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ و }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{يوجد}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
يشير الرمز Y إلى أن خاصية العمود صحيحة دائمًا بالنسبة لعنصر الصف (في أقصى اليسار)، بينما يشير الرمز ✗ إلى أن الخاصية غير مضمونة بشكل عام (قد تكون صحيحة أو خاطئة). على سبيل المثال، يُشار إلى أن كل علاقة تكافؤ متناظرة، ولكن ليس بالضرورة مضادة للتناظر، بالرمز Y في عمود "متناظر" والرمز ✗ في عمود "مضاد للتناظر". تتطلب جميع التعريفات ضمنيًا العلاقة المتجانسة${\displaystyle R}$يكون متعدياً : للجميع${\displaystyle a,b,c,}$لو${\displaystyle aRb}$و${\displaystyle bRc}$ثم${\displaystyle aRc.}$ قد يتطلب تعريف المصطلح خصائص إضافية غير مدرجة في هذا الجدول.

في الرياضيات ، تُسمى العلاقة الثنائية R علاقةً مؤسسةً ( أو أساسية ) ^{[ 1 ]} على مجموعة أو، بشكلٍ أعم، على فئة X إذا كان لكل مجموعة جزئية (أو فئة جزئية) غير فارغة S ⊆ X عنصرٌ أدنى بالنسبة إلى R ؛ أي، يوجد m ∈ S بحيث أنه لكل s ∈ S ، لا يوجد s R m . وبشكلٍ أكثر رسمية، تكون العلاقة مؤسسةً إذا: $${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$ يدرج بعض المؤلفين شرطًا إضافيًا وهو أن R تشبه المجموعة ، أي أن العناصر الأقل من أي عنصر معين تشكل مجموعة.

بصورة مكافئة، وبافتراض بديهية الاختيار التابع ، تكون العلاقة مؤسسة جيدًا عندما لا تحتوي على سلاسل تنازلية لانهائية ، أي أنه لا يوجد تسلسل لانهائي ^x₀ ، _x₁ ، _x₂ ، _... من _عناصر X بحيث يكون _xₙ₊₁ ∈ _xₙ لكل عدد ^طبيعي n . ^{[ 2 ]} [ ³ ]

في نظرية الترتيب ، يُطلق على الترتيب الجزئي اسم الترتيب الجيد إذا كان الترتيب الصارم المقابل له علاقة جيدة الأساس. أما إذا كان الترتيب ترتيبًا كليًا ، فيُطلق عليه اسم الترتيب الجيد .

في نظرية المجموعات ، تُسمى المجموعة x مجموعةً مؤسسةً جيدًا إذا كانت علاقة انتماء المجموعة مؤسسةً جيدًا على الإغلاق المتعدي لـ x . وتنص بديهية الانتظام ، وهي إحدى بديهيات نظرية زيرميلو-فرانكل للمجموعات ، على أن جميع المجموعات مؤسسة جيدًا.

تُسمى العلاقة R علاقةً ذات أساسٍ سليمٍ عكسي ، أو ذات أساسٍ سليمٍ تصاعدي ، أو علاقة نوثرية على X ، إذا كانت العلاقة العكسية R⁻¹ ذات أساسٍ سليمٍ على X. في هذه الحالة، ^يُقال أيضًا أن R تُحقق شرط السلسلة التصاعدية . في سياق أنظمة إعادة الكتابة ، تُسمى العلاقة النوثرية أيضًا علاقةً منتهية .

من الأسباب المهمة التي تجعل العلاقات المؤسسة جيدًا مثيرة للاهتمام هو إمكانية استخدام شكل من أشكال الاستقراء المتسامي عليها: إذا كانت ( X , R ) علاقة مؤسسة جيدًا، فإن P ( x ) هي خاصية ما لعناصر X ، ونريد أن نبين أن

P ( x ) صحيحة لجميع العناصر x من X ،

يكفي أن نوضح ما يلي:

إذا كان x عنصرًا من X و P ( y ) صحيحًا لجميع y بحيث y R x ، فإن P ( x ) يجب أن يكون صحيحًا أيضًا.

إنه، $${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).}$$

يُطلق على الاستقراء المبني على أسس جيدة أحيانًا اسم الاستقراء النويثري، ^{[ 4 ]} نسبة إلى إيمي نوثر .

على غرار الاستقراء، تدعم العلاقات المؤسسة جيدًا أيضًا بناء الكائنات عن طريق الاستدعاء الذاتي المتسامي . ليكن ( X , R ) علاقة مؤسسة جيدة تشبه المجموعة ، و F دالة تُسند كائنًا F ( x , g ) لكل زوج من عنصر x ∈ X ودالة g على مجموعة { y : y ∈ R x } من أسلاف x . عندئذٍ توجد دالة وحيدة G بحيث أنه لكل x ∈ X ، $${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).}$$

أي أنه إذا أردنا إنشاء دالة G على X ، فيمكننا تعريف G ( x ) باستخدام قيم G ( y ) لـ y R x .

كمثال، لننظر إلى العلاقة المؤسسة جيدًا ( N , S ) ، حيث N هي مجموعة الأعداد الطبيعية ، و S هي تمثيل دالة الخلف x ↦ x + 1. عندئذٍ، يكون الاستقراء الرياضي على S هو الاستقراء الرياضي المعتاد ، ويؤدي الاستدعاء الذاتي على S إلى الاستدعاء الذاتي الأولي . إذا نظرنا إلى علاقة الترتيب ( N , <) ، نحصل على الاستقراء الكامل ، واستدعاء مسار القيم الذاتي . تُعرف عبارة أن ( N , <) مؤسسة جيدًا أيضًا بمبدأ الترتيب الجيد .

توجد حالات خاصة أخرى مثيرة للاهتمام للاستقراء القائم على أساس متين. عندما تكون العلاقة القائمة على أساس متين هي الترتيب المعتاد على فئة جميع الأعداد الترتيبية ، تُسمى هذه التقنية بالاستقراء المتسامي . وعندما تكون المجموعة القائمة على أساس متين هي مجموعة من هياكل البيانات المعرفة بشكل متكرر، تُسمى هذه التقنية بالاستقراء البنيوي . وعندما تكون العلاقة القائمة على أساس متين هي انتماء المجموعة إلى الفئة الشاملة، تُعرف هذه التقنية بالاستقراء الـ ∈ . راجع تلك المقالات لمزيد من التفاصيل.

تشمل العلاقات الراسخة غير المنظمة تماماً ما يلي:

• الأعداد الصحيحة الموجبة {1، 2، 3، ...} ، مع الترتيب المحدد بواسطة a < b إذا وفقط إذا كان a يقسم b و a ≠ b .
• مجموعة جميع السلاسل المحدودة على أبجدية ثابتة، مع تحديد الترتيب بواسطة s < t إذا وفقط إذا كانت s سلسلة فرعية مناسبة من t .
• مجموعة N × N من أزواج الأعداد الطبيعية ، مرتبة حسب ( n1 _، n2 ) < ( m1 ، m2 ₎ إذا وفقط _{إذا كان} n1 < _{m1 و} n2 _{< m2} .​
• كل فئة عناصرها مجموعات، مع العلاقة ∈ ("هو عنصر من"). هذه هي بديهية الانتظام .
• عقد أي رسم بياني موجه محدود غير دوري ، مع تعريف العلاقة R بحيث يكون a R b إذا وفقط إذا كانت هناك حافة من a إلى b .

ومن أمثلة العلاقات غير المؤسسة على أسس متينة ما يلي:

• الأعداد الصحيحة السالبة {−1, −2, −3, ...} ، بالترتيب المعتاد، لأن أي مجموعة جزئية غير محدودة ليس لها عنصر أصغر.
• مجموعة السلاسل المكونة من أكثر من عنصر واحد على أبجدية منتهية، وفقًا للترتيب المعجمي المعتاد ، لأن المتتالية "B" > "AB" > "AAB" > "AAAB" > ... هي سلسلة تنازلية لانهائية. لا تُعتبر هذه العلاقة صحيحة حتى مع وجود عنصر أدنى في المجموعة بأكملها، وهو السلسلة الفارغة.
• مجموعة الأعداد النسبية غير السالبة (أو الأعداد الحقيقية ) وفقًا للترتيب القياسي، لأنه على سبيل المثال، تفتقر المجموعة الفرعية للأعداد النسبية الموجبة (أو الأعداد الحقيقية) إلى الحد الأدنى.

إذا كانت العلاقة ( X , <) علاقةً راسخةً وكان x عنصرًا من X ، فإن السلاسل التنازلية التي تبدأ من x تكون جميعها منتهية، ولكن هذا لا يعني بالضرورة أن أطوالها محدودة. لنأخذ المثال التالي: ليكن X اتحاد الأعداد الصحيحة الموجبة مع عنصر جديد ω أكبر من أي عدد صحيح. عندئذٍ، X مجموعة راسخة، ولكن توجد سلاسل تنازلية تبدأ من ω ذات طول كبير (محدود) كيفيًا؛ السلسلة ω, n − 1, n − 2, ..., 2, 1 طولها n لأي قيمة لـ n .

تشير مبرهنة انهيار موستوفسكي إلى أن عضوية المجموعة هي خاصية عالمية بين العلاقات الامتدادية ذات الأساس الجيد: لأي علاقة R ذات أساس جيد تشبه المجموعة على فئة X وهي امتدادية، توجد فئة C بحيث يكون ( X ، R ) متماثلًا مع ( C ، ∈) .

تُسمى العلاقة R علاقة انعكاسية إذا تحققت العلاقة a ∈ R a لكل عنصر a في مجال العلاقة. لكل علاقة انعكاسية على مجال غير فارغ سلاسل تنازلية لانهائية، لأن أي متتالية ثابتة هي سلسلة تنازلية. على سبيل المثال، في الأعداد الطبيعية بترتيبها المعتاد ≤، لدينا 1 ≥ 1 ≥ 1 ≥ ... لتجنب هذه المتتاليات التنازلية البسيطة، عند التعامل مع ترتيب جزئي ≤، من الشائع تطبيق تعريف التأسيس الجيد (ربما ضمنيًا) على العلاقة البديلة < المعرفة بحيث يكون a < b إذا وفقط إذا كان a ≤ b و a ≠ b . بشكل أعم، عند التعامل مع ترتيب جزئي ≤، من الشائع استخدام العلاقة < المعرفة بحيث يكون a < b إذا وفقط إذا كان a ≤ b و b ≰ a . في سياق الأعداد الطبيعية، يعني هذا استخدام العلاقة <، وهي علاقة صحيحة، بدلاً من العلاقة ≤، وهي علاقة غير صحيحة. في بعض النصوص، يُغيّر تعريف العلاقة الصحيحة من التعريف المذكور أعلاه ليشمل هذه الاصطلاحات.

• جست، وينفريد وويز، مارتن (1998) اكتشاف نظرية المجموعات الحديثة. الجزء الأول ، الجمعية الأمريكية للرياضيات، رقم ISBN 0-8218-0266-6.
• كارل هرباتشيك وتوماس جيتش (1999) مقدمة في نظرية المجموعات ، الطبعة الثالثة، "العلاقات المؤسسة جيدًا"، الصفحات 251-255، مارسيل ديكر، رقم ISBN 0-8247-7915-0

• https://ncatlab.org/nlab/show/well-founded+coalgebra