دالة رتيبة

في الرياضيات ، الدالة الرتيبة (أو الدالة الرتيبة ) هي دالة بين مجموعات مرتبة تحافظ على الترتيب المعطى أو تعكسه . [ ^{1 ] [ 2 ] [ 3 ] ظهر} هذا المفهوم لأول مرة في حساب التفاضل والتكامل ، ثم عُمِّم لاحقًا إلى الإطار الأكثر تجريدًا لنظرية الترتيب .

في حساب التفاضل والتكامل ، الدالة${\displaystyle f}$تُسمى الدالة المعرفة على مجموعة جزئية من الأعداد الحقيقية ذات القيم الحقيقية دالة رتيبة إذا كانت إما غير متناقصة تمامًا أو غير متزايدة تمامًا. ^{[ 2 ]} أي، كما هو موضح في الشكل 1، فإن الدالة المتزايدة بشكل رتيب لا يشترط أن تكون متزايدة بالضرورة، بل يكفي ألا تكون متناقصة.

تُسمى الدالة متزايدة بشكل رتيب (أو متزايدة أو غير متناقصة ) ^{[ 3 ]} إذا كان لكل${\displaystyle x}$و${\displaystyle y}$بحيث${\displaystyle x\leq y}$يمتلك المرء ${\displaystyle f\!\left(x\right)\leq f\!\left(y\right)}$، لذا${\displaystyle f}$يحافظ على الترتيب (انظر الشكل 1). وبالمثل، تُسمى الدالة متناقصة بشكل رتيب (أو متناقصة أو غير متزايدة ) ^{[ 3 ]} إذا، كلما${\displaystyle x\leq y}$، ثم${\displaystyle f\!\left(x\right)\geq f\!\left(y\right)}$لذلك يعكس الترتيب (انظر الشكل 2).

إذا كان الطلب${\displaystyle \leq }$يتم استبدال تعريف الرتابة بالترتيب الصارم${\displaystyle <}$عند عكس رمز الترتيب ، نحصل على شرط أقوى. تُسمى الدالة التي تتمتع بهذه الخاصية دالة متزايدة تمامًا (أو متزايدة ). ^{[ 3 ] [ 4 ]} وبالمثل، بعكس رمز الترتيب، نجد مفهومًا مقابلًا يُسمى دالة متناقصة تمامًا (أو متناقصة ). ^{[ 3 ] [ 4 ]} تُسمى الدالة التي تتمتع بأي من الخاصيتين دالة رتيبة تمامًا . الدوال الرتيبة تمامًا هي دوال أحادية (لأنها بالنسبة لـ${\displaystyle x}$لا يساوي${\displaystyle y}$، أيضاً${\displaystyle x<y}$أو${\displaystyle x>y}$وبالتالي، بحسب مبدأ الرتابة، إما${\displaystyle f\!\left(x\right)<f\!\left(y\right)}$أو${\displaystyle f\!\left(x\right)>f\!\left(y\right)}$، هكذا${\displaystyle f\!\left(x\right)\neq f\!\left(y\right)}$.

ولتجنب الغموض، غالباً ما تُستخدم المصطلحات "الرتابة الضعيفة" و" الزيادة الضعيفة" و "التناقص الضعيف" للإشارة إلى الرتابة غير الصارمة.

لا ينبغي الخلط بين مصطلحي "غير متناقص" و"غير متزايد" وبين التوصيفات السلبية (الأضعف بكثير) "غير متناقص" و"غير متزايد". على سبيل المثال، الدالة غير الرتيبة الموضحة في الشكل 3 تتناقص أولًا، ثم ترتفع، ثم تتناقص مرة أخرى. لذا فهي ليست متناقصة وليست متزايدة، ولكنها ليست غير متناقصة ولا غير متزايدة.

وظيفة${\displaystyle f}$يقال إنها رتيبة تمامًا على مدى فترة زمنية${\displaystyle \left(a,b\right)}$إذا كانت مشتقات جميع رتب${\displaystyle f}$تكون غير سالبة أو غير موجبة في جميع نقاط الفترة.

بعض التطبيقات والنتائج الأساسية

الخصائص التالية صحيحة بالنسبة للدالة الرتيبة${\displaystyle f\colon \mathbb {R} \to \mathbb {R} }$:

• ${\displaystyle f}$له حدود من اليمين ومن اليسار عند كل نقطة من نطاقه ؛
• ${\displaystyle f}$لها حد عند اللانهاية الموجبة أو اللانهاية السالبة (${\displaystyle \pm \infty }$) من عدد حقيقي،${\displaystyle \infty }$، أو${\displaystyle -\infty }$.
• ${\displaystyle f}$لا يمكن أن تحتوي إلا على انقطاعات قفزية وقابلة للإزالة .
• ${\displaystyle f}$لا يمكن أن تحتوي الدالة إلا على عدد محدود من نقاط الانقطاع في مجالها. ومع ذلك، لا تتكون نقاط الانقطاع بالضرورة من نقاط معزولة، بل قد تكون كثيفة في الفترة ( أ ، ب ). على سبيل المثال، لأي متتالية قابلة للجمع$(a_{i})$من الأعداد الموجبة وأي تعداد${\displaystyle (q_{i})}$من الأعداد النسبية ، الدالة المتزايدة بشكل رتيب$${\displaystyle f(x)=\sum _{q_{i}\leq x}a_{i}}$$تكون متصلة تمامًا عند كل عدد غير نسبي (انظر الصورة). وهي دالة التوزيع التراكمي للمقياس المنفصل على الأعداد النسبية، حيث${\displaystyle a_{i}}$وزن${\displaystyle q_{i}}$.
• لو${\displaystyle f}$قابلة للتفاضل عند${\displaystyle x^{*}\in {\mathbb {R}}}$و${\displaystyle f'(x^{*})>0}$إذن، توجد فترة غير منحلة I بحيث${\displaystyle x^{*}\in I}$و${\displaystyle f}$يزداد على I.
• كعكس جزئي، إذا${\displaystyle f}$دالة قابلة للتفاضل ومتزايدة على فترة،${\displaystyle I}$إذن، تكون مشتقتها غير سالبة عند كل نقطة في${\displaystyle I}$علاوة على ذلك، فإن المجموعة${\displaystyle A=\{x\in I:f'(x)>0\}}$كثيفة ذات مقياس ليبيغ موجب . لا يمكن قول الكثير أكثر من ذلك.${\displaystyle A}$؛ على سبيل المثال،${\displaystyle A}$قد تكون ضئيلة ، كما هو الحال في مشتق بومبيو ، وبالنسبة لقيم ثابتة${\displaystyle I}$مقياس ليبيغ لـ${\displaystyle A}$يمكن جعلها قريبة بشكل تعسفي من${\displaystyle 0}$عن طريق اختيار مناسب لـ${\displaystyle f}$.

تُعدّ هذه الخصائص السبب وراء فائدة الدوال الرتيبة في العمل التقني في مجال التحليل . ومن الخصائص المهمة الأخرى لهذه الدوال ما يلي:

• لو${\displaystyle f}$هي دالة رتيبة معرفة على فترة${\displaystyle I}$، ثم${\displaystyle f}$يمكن تفاضلها في كل مكان تقريبًا على${\displaystyle I}$أي مجموعة الأرقام${\displaystyle x}$في${\displaystyle I}$بحيث${\displaystyle f}$غير قابلة للتفاضل في${\displaystyle x}$لها قياس ليبيغ يساوي صفرًا . بالإضافة إلى ذلك، لا يمكن تحسين هذه النتيجة لتصبح قابلة للعد: انظر دالة كانتور .
• إذا كانت هذه المجموعة قابلة للعد، فإن${\displaystyle f}$متصل تمامًا
• لو${\displaystyle f}$هي دالة رتيبة معرفة على فترة${\displaystyle \left[a,b\right]}$، ثم${\displaystyle f}$قابل للتكامل وفقًا لريمان .

يُعدّ استخدام الدوال الرتيبة في نظرية الاحتمالات أحد أهم تطبيقاتها . إذا${\displaystyle X}$هو متغير عشوائي ، ودالة التوزيع التراكمي الخاصة به${\displaystyle F_{X}\!\left(x\right)={\text{Prob}}\!\left(X\leq x\right)}$هي دالة متزايدة بشكل رتيب.

تكون الدالة أحادية النمط إذا كانت تتزايد بشكل رتيب حتى نقطة معينة ( النمط ) ثم تتناقص بشكل رتيب.

متى${\displaystyle f}$إذا كانت دالة رتيبة تمامًا ،${\displaystyle f}$دالة أحادية على مجالها، وإذا${\displaystyle T}$هو نطاق​${\displaystyle f}$إذن توجد دالة عكسية على${\displaystyle T}$ل${\displaystyle f}$. في المقابل، كل دالة ثابتة رتيبة، ولكنها ليست أحادية، ^{[ 7 ]} وبالتالي لا يمكن أن يكون لها دالة عكسية.

يُظهر الرسم البياني ست دوال رتيبة. وتظهر أبسط أشكالها في منطقة الرسم، بينما تظهر التعبيرات المستخدمة لإنشائها على المحور الصادي .

خريطة${\displaystyle f:X\to Y}$يُقال إن الدالة رتيبة إذا كانت كل أليافها متصلة ؛ أي لكل عنصر${\displaystyle y\in Y,}$المجموعة (التي قد تكون فارغة)${\displaystyle f^{-1}(y)}$هو فضاء فرعي متصل من${\displaystyle X.}$

في التحليل الوظيفي على فضاء متجهي طوبولوجي${\displaystyle X}$، عامل (ربما غير خطي)${\displaystyle T:X\rightarrow X^{*}}$يُقال إنها مؤثر رتيب إذا

$${\displaystyle (Tu-Tv,u-v)\geq 0\quad \forall u,v\in X.}$$تُظهر نظرية كاتشوروفسكي أن الدوال المحدبة على فضاءات باناخ لها مؤثرات رتيبة كمشتقات لها.

مجموعة فرعية${\displaystyle G}$ل${\displaystyle X\times X^{*}}$يُقال إنها مجموعة أحادية اللون إذا كان لكل زوج${\displaystyle [u_{1},w_{1}]}$و${\displaystyle [u_{2},w_{2}]}$في${\displaystyle G}$،

$${\displaystyle (w_{1}-w_{2},u_{1}-u_{2})\geq 0.}$$${\displaystyle G}$يُقال إن المؤثر رتيبٌ أقصى إذا كان أقصى ما يمكن بين جميع المجموعات الرتيبة بمعنى احتواء المجموعة. رسم بياني لمؤثر رتيب${\displaystyle G(T)}$هي مجموعة رتيبة. يُقال إن المؤثر الرتيب هو رتيب أقصى إذا كان رسمه البياني مجموعة رتيبة قصوى .

تتناول نظرية الترتيب المجموعات المرتبة جزئيًا والمجموعات المرتبة مسبقًا كتعميم للأعداد الحقيقية. وينطبق تعريف الرتابة المذكور أعلاه على هذه الحالات أيضًا. مع ذلك، يُتجنب استخدام مصطلحي "التزايد" و"التناقص"، لأن تمثيلهما التصويري التقليدي لا ينطبق على الترتيبات غير الكلية . علاوة على ذلك، فإن العلاقات الصارمة${\displaystyle <}$و${\displaystyle >}$لا فائدة منها في العديد من الطلبات غير الكاملة، وبالتالي لم يتم إدخال مصطلحات إضافية لها.

تأجير${\displaystyle \leq }$تشير إلى علاقة الترتيب الجزئي لأي مجموعة مرتبة جزئيًا، وهي دالة رتيبة ، وتسمى أيضًا متساوية التناقص ، أويحافظ على النظام ، ويلبي الخاصية

$${\displaystyle x\leq y\implies f(x)\leq f(y)}$$

لكل قيم x و y في نطاقها. إن تركيب دالتين رتيبتين هو أيضًا دالة رتيبة.

يُطلق على المفهوم الثنائي غالبًا اسم مضاد التنافر ، أو مضاد الرتابة ، أو عكس الترتيب . وبالتالي، فإن الدالة المضادة للتنافر f تحقق الخاصية التالية:

$${\displaystyle x\leq y\implies f(y)\leq f(x),}$$

لكل x و y في نطاقها.

الدالة الثابتة تكون رتيبة ومضادة في نفس الوقت؛ وعلى العكس من ذلك، إذا كانت f رتيبة ومضادة في نفس الوقت، وإذا كان مجال f عبارة عن شبكة ، فإن f يجب أن تكون ثابتة.

تُعدّ الدوال الرتيبة أساسية في نظرية الترتيب. وتظهر في معظم المقالات التي تتناول هذا الموضوع، كما تُوجد أمثلة من تطبيقات خاصة في هذه المقالات. ومن أبرز الدوال الرتيبة الخاصة تضمينات الترتيب (الدوال التي يكون فيها${\displaystyle x\leq y}$إذا وفقط إذا${\displaystyle f(x)\leq f(y))}$وتماثلات الترتيب ( تضمينات الترتيب الشاملة ).

في سياق خوارزميات البحث، يُعدّ الرتابة (أو الاتساق) شرطًا يُطبّق على الدوال الاستدلالية .${\displaystyle h(n)}$تكون الدالة رتيبة إذا كان، لكل عقدة n ولكل عقدة لاحقة n' لـ n ناتجة عن أي إجراء a ، التكلفة المقدرة للوصول إلى الهدف من n لا تزيد عن تكلفة الخطوة للوصول إلى n' بالإضافة إلى التكلفة المقدرة للوصول إلى الهدف من n' .

$${\displaystyle h(n)\leq c\left(n,a,n'\right)+h\left(n'\right).}$$

هذا شكل من أشكال متباينة المثلث ، حيث n و n' والهدف G هو أقرب n إلى _n . ولأن كل دالة استدلالية رتيبة مقبولة أيضًا ، فإن الرتابة شرطٌ أكثر صرامة من القبول. يمكن إثبات أن بعض الخوارزميات الاستدلالية ، مثل A*، مثالية بشرط أن تكون الدالة الاستدلالية التي تستخدمها رتيبة. ^{[ 8 ]}

في الجبر البولياني _، الدالة الرتيبة هي دالة بحيث أنه لكل aᵢ و bᵢ في المجموعة _{ 0,1} ، إذا كان _a₁ ≤ b₁ ، _a₂ ≤ b₂ _، ... ، _an ≤ bₙ ( أي _أن حاصل الضرب الديكارتي للمجموعة {0,1} _ⁿ مرتب إحداثيًا )، فإن f( a₁ , ..., an ⁾ ≤ f( _b₁ , ..., _bₙ ) . بعبارة أخرى، تكون الدالة البوليانية رتيبة إذا كان تغيير أحد المدخلات من _خطأ إلى صواب، لكل توليفة من المدخلات، يؤدي فقط إلى تغيير المخرج من خطأ إلى صواب، وليس العكس. بيانيًا، يعني هذا أن _الدالة البوليانية من الرتبة n تكون رتيبة عندما لا يحتوي تمثيلها كمكعب من الرتبة n مُعَلَّم بقيم الصواب على أي حافة صاعدة من صواب إلى خطأ . ( مخطط هاس المسمى هذا هو ثنائي مخطط فين المسمى للدالة ، وهو التمثيل الأكثر شيوعًا لـ n ≤ 3. )

الدوال المنطقية الرتيبة هي تلك التي يمكن تعريفها بتعبير يجمع المدخلات (التي قد تظهر أكثر من مرة) باستخدام عاملي " و" و" أو " فقط (مع استثناء "ليس "). على سبيل المثال، "يتحقق اثنان على الأقل من a و b و c " ( دالة الأغلبية الثلاثية ) هي دالة رتيبة لـ a و b و c ، حيث يمكن كتابتها على سبيل المثال على النحو التالي: (( a و b ) أو ( a و c ) أو ( b و c )).

يُعرف عدد هذه الدوال على n متغيرًا باسم عدد ديديكيند لـ n .

يمكن حل مشكلة SAT ، وهي مهمة صعبة من نوع NP بشكل عام ، بكفاءة عندما تكون جميع الدوال والمسندات المعنية رتيبة ومنطقية. ^{[ 9 ]}

• الاستيفاء التكعيبي أحادي النغمة
• عامل شبه رتيب
• معامل ارتباط رتبة سبيرمان - مقياس للرتابة في مجموعة من البيانات
• الرتابة التامة
• الرتابة الدورية
• وظيفة الرتابة للمشغل
• دالة المجموعة الرتيبة
• الدوال والمتتابعات الرتيبة تمامًا

• بارتل، روبرت ج. (1976). عناصر التحليل الحقيقي (  الطبعة الثانية).
• غراتزر، جورج (1971). نظرية الشبكات: المفاهيم الأولية والشبكات التوزيعية . دبليو إتش فريمان. ISBN 0-7167-0442-0.
• بيمبرتون، مالكولم؛ راو، نيكولاس (2001). الرياضيات للاقتصاديين: كتاب تمهيدي . مطبعة جامعة مانشستر. ISBN 0-7190-3341-1.
• ريناردي، مايكل وروغرز، روبرت سي. (2004). مقدمة في المعادلات التفاضلية الجزئية . نصوص في الرياضيات التطبيقية 13 (  الطبعة الثانية). نيويورك: سبرينغر-فيرلاغ. ص  356. ISBN 0-387-00444-0.
• ريسز، فريجيس وبيلا سوكيفالفي ناجي (1990). التحليل الوظيفي . منشورات ساعي دوفر. رقم ISBN 978-0-486-66289-3.
• راسل، ستيوارت جيه؛ نورفيج، بيتر (2010). الذكاء الاصطناعي: منهج حديث (  الطبعة الثالثة). أبر سادل ريفر، نيو جيرسي: برنتيس هول. ISBN 978-0-13-604259-4.
• سيمون، كارل ب.؛ بلوم، لورانس (أبريل 1994). الرياضيات للاقتصاديين (  الطبعة الأولى). نورتون. ISBN 978-0-393-95733-4.(التعريف 9.31)

• "الدالة الرتيبة" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• تقارب متتالية رتيبة من تأليف أنيك ديبناث وتوماس روكسلو (مدرسة هاركر)، مشروع عروض وولفرام .
• وايسشتاين، إريك دبليو. "الدالة الرتيبة" . عالم الرياضيات .