Well-order

Transitive binary relations v t e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total,Semiconnex Anti-reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions,for all ${\displaystyle a,b}$ and ${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&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{exists}}\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 indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteedin general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric,is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation${\displaystyle R}$ be transitive: for all ${\displaystyle a,b,c,}$ if ${\displaystyle aRb}$ and ${\displaystyle bRc}$ then ${\displaystyle aRc.}$ A term's definition may require additional properties that are not listed in this table.

In mathematics, a well-order (or well-ordering or well-order relation) on a setS is a total ordering on S with the property that every non-emptysubset of S has a least element in this ordering. The set S together with the ordering is then called a well-ordered set (or woset).^[1] In some academic articles and textbooks these terms are instead written as wellorder, wellordered, and wellordering or well order, well ordered, and well ordering.

Every non-empty well-ordered set has a least element. Every element s of a well-ordered set, except a possible greatest element, has a unique successor (next element), namely the least element of the subset of all elements greater than s. There may be elements, besides the least element, that have no predecessor (see § Natural numbers below for an example). A well-ordered set S contains for every subset T with an upper bound a least upper bound, namely the least element of the subset of all upper bounds of T in S.

If ≤ is a non-strict well ordering, then < is a strict well ordering. A relation is a strict well ordering if and only if it is a well-foundedstrict total order. The distinction between strict and non-strict well orders is often ignored since they are easily interconvertible.

Every well-ordered set is uniquely order isomorphic to a unique ordinal number, called the order type of the well-ordered set. The well-ordering theorem, which is equivalent to the axiom of choice, states that every set can be well ordered. If a set is well ordered (or even if it merely admits a well-founded relation), the proof technique of transfinite induction can be used to prove that a given statement is true for all elements of the set.

The observation that the natural numbers are well ordered by the usual less-than relation is commonly called the well-ordering principle (for natural numbers).

إذا كانت المجموعة مرتبة ترتيباً كلياً ، فإن ما يلي يكون متكافئاً مع بعضه البعض:

1. المجموعة مرتبة ترتيباً جيداً. أي أن كل مجموعة جزئية غير فارغة تحتوي على أصغر عنصر.
2. يعمل الاستقراء المتسامي على المجموعة المرتبة بأكملها.
3. يجب أن تنتهي كل سلسلة متناقصة تمامًا من عناصر المجموعة بعد عدد محدود من الخطوات فقط (بافتراض بديهية الاختيار التابع ).
4. كل ترتيب فرعي متماثل مع جزء أولي (انظر §  الأجزاء الأولية أدناه).

مقطع أولي ، يتم تحديده بواسطة عنصر${\displaystyle x}$من مجموعة مرتبة${\displaystyle X}$، هي مجموعة فرعية من الشكل${\displaystyle \{y\in X\mid y<x\}}$[ ^{4 ] بحسب} العرف،${\displaystyle X}$يُعتبر نفسه أيضاً جزءاً ابتدائياً (غير صحيح).

للحصول على مجموعة مرتبة بشكل جيد${\displaystyle X}$، مجموعة فرعية${\displaystyle S\subset X}$هو جزء أولي (إما${\displaystyle X}$أو مقطع أولي بواسطة عنصر ما) إذا وفقط إذا كان يحتوي

${\displaystyle \{y\in X\mid y<x\}}$

لكل${\displaystyle x}$في${\displaystyle S}$^{[ 5 ] [ 6 ]} بعبارة أخرى ، القطعة الأولية هي نفسها المجموعة الدنيا في نظرية الترتيب ، ويُعتبر هذا التوصيف أحيانًا تعريفًا للقطعة الأولية. ^{[ 7 ]}

تُستخدم المقاطع الأولية غالبًا في دراسة المجموعات المرتبة جيدًا والمجموعات المؤسسة جيدًا . على سبيل المثال، العدد الترتيبي هو مجموعة مرتبة جيدًا${\displaystyle \alpha }$والتي تكون جميع عناصرها عبارة عن أجزاء أولية تحددها بنفسها؛ أي، لكل عنصر${\displaystyle x}$في${\displaystyle \alpha }$لدينا:

${\displaystyle x=\{y\in \alpha \mid y<x\}.}$^{[ 8 ]}

انظر أيضًا القسم  الخاص بالأعداد الترتيبية أدناه. تُستخدم المقاطع الأولية أيضًا في نص نظرية الاستدعاء الذاتي المتسامي .

تشمل خصائص الأجزاء الأولية ما يلي:

• لا يمكن لأي مجموعة مرتبة ترتيبًا جيدًا أن تكون متماثلة مع جزء أولي مناسب منها. ^{[ 9 ]} كذلك، إذا أُعطيت مجموعتان مرتبتان ترتيبًا جيدًا${\displaystyle X,Y}$، أيضاً${\displaystyle X}$متماثل مع جزء أولي من${\displaystyle Y}$أو${\displaystyle Y}$متماثل مع جزء أولي من${\displaystyle X}$.
• يُرسل التشكل بين المجموعات المرتبة جيدًا أجزاءً أولية إلى أجزاء أولية، حيث يكون التشكل عبارة عن دالة أحادية تحافظ على الترتيب وتكون صورتها جزءًا أوليًا. ^{[ 10 ]}
• تُعطي الأجزاء الأولية ترتيبًا${\displaystyle \trianglelefteq }$في الفصل${\displaystyle \operatorname {Well} }$من المجموعات المرتبة ترتيباً جيداً؛ أي${\displaystyle A\trianglelefteq B}$إذا وفقط إذا${\displaystyle A\subset B}$هي مجموعة جزئية مع تقييد الترتيب من${\displaystyle B}$و${\displaystyle A}$هو جزء أولي من${\displaystyle B}$[ ^{11 ]} اتحاد سلسلة من المجموعات المرتبة ترتيبًا جيدًا يكون مرتبًا ترتيبًا جيدًا، حيث تكون السلسلة بالنسبة ^إلى${\displaystyle \trianglelefteq }$[ ^{11 ] بالنسبة للأعداد الترتيبية، يتطابق هذا الترتيب الذي} تحدده الأجزاء الأولية مع احتواء المجموعة. ^{[ 12 ]}
• تكون المجموعة ذات العلاقة الثنائية مؤسسة جيداً إذا وفقط إذا كانت مغطاة بقطاعات أولية مؤسسة جيداً. ^{[ 13 ]}

يمكن تحويل كل مجموعة مرتبة جيدًا إلى فضاء طوبولوجي عن طريق تزويدها بطوبولوجيا الترتيب .

فيما يتعلق بهذا التكوين الطوبولوجي، يمكن أن يكون هناك نوعان من العناصر:

• النقاط المعزولة - هذه هي العناصر الدنيا والعناصر التي لها عنصر سابق.
• نقاط النهاية - لا يظهر هذا النوع في المجموعات المنتهية، وقد يظهر أو لا يظهر في المجموعات غير المنتهية؛ المجموعات غير المنتهية التي لا تحتوي على نقاط نهاية هي مجموعات من النوع ω ، على سبيل المثال الأعداد الطبيعية .${\displaystyle \mathbb {N} .}$⁠

بالنسبة للمجموعات الجزئية، يمكننا التمييز بين:

• المجموعات الجزئية ذات الحد الأقصى (أي المجموعات الجزئية المحدودة بنفسها )؛ يمكن أن تكون هذه نقطة معزولة أو نقطة حدية للمجموعة بأكملها؛ في الحالة الأخيرة قد تكون أو لا تكون نقطة حدية للمجموعة الجزئية.
• المجموعات الجزئية التي لا تكون محدودة في حد ذاتها ولكنها محدودة في المجموعة بأكملها؛ ليس لها قيمة عظمى، ولكن لها قيمة عظمى خارج المجموعة الجزئية؛ إذا كانت المجموعة الجزئية غير فارغة، فإن هذه القيمة العظمى هي نقطة نهاية للمجموعة الجزئية وبالتالي للمجموعة بأكملها أيضًا؛ إذا كانت المجموعة الجزئية فارغة، فإن هذه القيمة العظمى هي الحد الأدنى للمجموعة بأكملها.
• المجموعات الجزئية غير المحدودة في المجموعة الكاملة.

تكون المجموعة الجزئية نهائية مشتركة في المجموعة بأكملها إذا وفقط إذا كانت غير محدودة في المجموعة بأكملها أو كان لها قيمة عظمى هي أيضًا القيمة العظمى للمجموعة بأكملها.

تعتبر المجموعة المرتبة جيدًا كفضاء طوبولوجي فضاءً قابلاً للعد من الدرجة الأولى إذا وفقط إذا كان نوع ترتيبها أقل من أو يساوي ω ₁ ( أوميغا واحد )، أي إذا وفقط إذا كانت المجموعة قابلة للعد أو لها أصغر نوع ترتيب غير قابل للعد.

كل مجموعة مرتبة ترتيبًا جيدًا لها تماثل ترتيبي فريد مع عدد ترتيبي فريد ، يُسمى نوع الترتيب للمجموعة المرتبة ترتيبًا جيدًا. ويُحدد موقع كل عنصر داخل المجموعة المرتبة أيضًا بعدد ترتيبي. في حالة المجموعة المنتهية، فإن عملية العد الأساسية ، لإيجاد العدد الترتيبي لعنصر معين، أو لإيجاد العنصر ذي العدد الترتيبي المحدد، تُقابل إسناد أعداد ترتيبية واحدًا تلو الآخر للعناصر. حجم المجموعة المنتهية (عدد عناصرها، أو عددها الأصلي ) يساوي نوع الترتيب. ^{[ 14 ]} يبدأ العد في الاستخدام اليومي عادةً من واحد، لذا يُسند لكل عنصر حجم الجزء الأول الذي يكون فيه ذلك العنصر هو العنصر الأخير. لاحظ أن هذه الأعداد تزيد بمقدار واحد عن الأعداد الترتيبية الرسمية وفقًا للترتيب المتماثل، لأنها تساوي عدد العناصر السابقة (وهو ما يُقابل العد من الصفر). لذا، بالنسبة لقيم n المحدودة ، يتطلب التعبير " العنصر رقم n " لمجموعة مرتبة ترتيبًا جيدًا سياقًا لمعرفة ما إذا كان العد يبدأ من الصفر أو الواحد. في التعبير " العنصر رقم β " حيث يمكن أن يكون β عددًا ترتيبيًا لانهائيًا، فإنه عادةً ما يبدأ العد من الصفر.

بالنسبة لمجموعة غير منتهية، يحدد نوع الترتيب عدد عناصرها ، ولكن ليس العكس: يمكن أن تحتوي المجموعات ذات عدد عناصر غير منتهٍ معين على ترتيبات جيدة من أنواع مختلفة (انظر قسم  الأعداد الطبيعية أدناه كمثال). أما بالنسبة لمجموعة غير منتهية قابلة للعد ، فإن مجموعة أنواع الترتيب الممكنة غير قابلة للعد.

• الشجرة (نظرية المجموعات) ، التعميم
• العدد الترتيبي
• مجموعة ذات أساس متين
• طلب جزئي جيد
• الطلب المسبق
• مجموعة موجهة

• تاو، ت (28 يناير 2009). "245ب، ملاحظات 7: المجموعات المرتبة ترتيبًا جيدًا، والأعداد الترتيبية، ومبرهنة زورن (اختياري)" . ما الجديد .
• هالموس ، بول (1960). نظرية المجموعة الساذجة . برينستون، نيوجيرسي: شركة د. فان نوستراند.أُعيد طبعه بواسطة دار نشر سبرينغر-فيرلاغ، نيويورك، 1974. رقم الكتاب المعياري الدولي (ISBN) 0-387-90092-6(طبعة سبرينغر-فيرلاغ).
• تايلور، بول (13 مايو 1999). الأسس العملية للرياضيات . مطبعة جامعة كامبريدج. ISBN 978-0-521-63107-5.

• بول تايلور، نحو معالجة موحدة للاستقراء، الجزء الأول: نظرية الاستدعاء العام (1996).
• ملاحظة 2.5 في https://ncatlab.org/nlab/show/Zorn's+lemma