علاقة راسخة

العلاقات الثنائية المتعدية  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 تشبه المجموعة ، أي أن العناصر الأقل من أي عنصر معين تشكل مجموعة.

Equivalently, assuming the axiom of dependent choice, a relation is well-founded when it contains no infinite descending chains, meaning there is no infinite sequence x₀, x₁, x₂, ... of elements of X such that x_n+1Rx_n for every natural number n.^[2][3]

In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order, then it is called a well-order.

In set theory, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x. The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded.

A relation R is converse well-founded, upwards well-founded, or Noetherian on X, if the converse relationR⁻¹ is well-founded on X. In this case R is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating.

An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if (X, R) is a well-founded relation, P(x) is some property of elements of X, and we want to show that

P(x) holds for all elements x of X,

it suffices to show that:

If x is an element of X and P(y) is true for all y such that yRx, then P(x) must also be true.

That is, $${\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