طريقة التناوب

في المنطق الرياضي ، وخاصة في نظرية المجموعات ونظرية النماذج ، تُعدّ طريقة التناوب طريقةً لإثبات التماثل بين هياكل لا نهائية قابلة للعد تحقق شروطًا محددة. وعلى وجه الخصوص، يمكن استخدامها لإثبات ما يلي:

• أي مجموعتين مرتبتين بكثافة ، قابلتين للعد إلى ما لا نهاية (أي مرتبتين خطيًا بحيث يوجد بين أي عنصرين عنصر آخر)، بدون نقاط نهاية، تكونان متماثلتين. والتماثل بين الترتيبات الخطية هو ببساطة تقابل تزايدي تمامًا . وتدل هذه النتيجة، على سبيل المثال، على وجود تقابل تزايدي تمامًا بين مجموعة جميع الأعداد النسبية ومجموعة جميع الأعداد الجبرية الحقيقية .
• أي جبرين بوليانيين لا نهائيين قابلين للعد يكونان متماثلين مع بعضهما البعض.
• أي نموذجين ذريين متكافئين وقابلين للعد لنظرية ما يكونان متماثلين.
• إن نموذج Erdős–Rényi للرسوم البيانية العشوائية ، عند تطبيقه على الرسوم البيانية اللانهائية القابلة للعد، ينتج بشكل شبه مؤكد رسمًا بيانيًا فريدًا، وهو الرسم البياني Rado .
• أي مجموعتين قابلتين للتعداد بشكل متكرر وكاملتين متعددًا تكونان متماثلتين بشكل متكرر .

نحن نؤسس لغة${\displaystyle {\mathcal {L}}}$ونحن نعتبر اثنين${\displaystyle {\mathcal {L}}}$- الهياكل${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {N}}}$من المجالات على التوالي${\displaystyle M}$و${\displaystyle N}$.

نسمي التشاكل الجزئي بين${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {N}}}$أي تماثل بين اثنين${\displaystyle {\mathcal {L}}}$- البنى الفرعية لـ${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {N}}}$.

عائلة غير فارغة${\displaystyle {\mathcal {I}}}$من التشاكلات الجزئية بين${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {N}}}$يُطلق عليه اسم " الحوار المتبادل" إذا تحققت فيه الخاصيتان التاليتان:

• (إلى الأمام)${\displaystyle \forall \sigma \in {\mathcal {I}}\;\;\forall c\in M\;\;\exists \sigma '\in {\mathcal {I}}\;{\bigl (}\sigma \subseteq \sigma '\;\land \;c\in \mathrm {dom} (\sigma '){\bigr )}}$

• (خلف)${\displaystyle \forall \sigma \in {\mathcal {I}}\;\;\forall d\in N\;\;\exists \sigma '\in {\mathcal {I}}\;{\bigl (}\sigma \subseteq \sigma '\;\land \;d\in \mathrm {im} (\sigma '){\bigr )}}$

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

على سبيل المثال، يمكن استخدام طريقة التناوب لإثبات نظرية كانتور للتشاكل ، مع العلم أن هذا لم يكن برهان جورج كانتور الأصلي. تنص هذه النظرية على أن نظامين خطيين كثيفين غير محدودين وقابلين للعد متشاكلين. ^{[ 1 ]}

لنفترض أن

• ( A , ≤ _A ) و ( B , ≤ _B ) هما مجموعتان مرتبتان خطيًا؛
• كلاهما غير محدود، بمعنى آخر لا يوجد حد أقصى ولا حد أدنى لأي منهما ؛
• إنها مرتبة بشكل كثيف، أي بين أي عضوين يوجد عضو آخر؛
• إنها لا نهائية قابلة للعد.

قم بإصلاح تعدادات المجموعات الأساسية (بدون تكرار):

A = { a ₁ , a ₂ , a ₃ , ... },

B = { b ₁ , b ₂ , b ₃ , ... }.

الآن نقوم بإنشاء علاقة تناظر أحادي بين A و B تكون متزايدة تمامًا. في البداية، لا يوجد أي عنصر من A مقترن بأي عنصر من B.

(1) ليكن i أصغر فهرس بحيث لا يكون a_{_i} مرتبطًا بأي عنصر من B. وليكن j فهرسًا بحيث لا يكون b_{_j} مرتبطًا بأي عنصر من A ، ويمكن ربط a _{_i} بـ b_{_j} بشرط أن يكون الربط تزايديًا تمامًا. اربط a_{_i} بـ b_{_j}.

(2) ليكن j أصغر فهرس بحيث لا يكون bj مقترنًا بأي عنصر من A. وليكن i فهرسًا بحيث لا يكون ai مقترنًا بأي عنصر من B _، ويمكن إقران bj _{مع ai بشكل متسق} مع شرط أن يكون الإقران متزايدًا تمامًا _. قم بإقران bj مع ai _.

(3) ارجع إلى الخطوة (1) .

لا يزال يتعين التحقق من إمكانية اتخاذ الخيار المطلوب في الخطوتين (1) و (2) وفقًا للمتطلبات. لنأخذ الخطوة (1) كمثال:

_إذا وُجد بالفعل عنصران _p و q في _{المجموعة} A يُقابلان bp و bq في _{المجموعة} B على _{التوالي، بحيث يكون ap < ai < aq و bp < bq ،} فإننا نختار bj _بين bp _و bq باستخدام الكثافة . وإلا ، فإننا نختار عنصرًا مناسبًا كبيرًا _{أو صغيرًا من} B، مع _الأخذ في الاعتبار أن B ليس لها قيمة عظمى ولا قيمة صغرى. الخيارات المُتخذة في الخطوة (2) ممكنة أيضًا. أخيرًا، ينتهي البناء بعد عدد لا نهائي من الخطوات، لأن A و B مجموعتان لا نهائيتان. تجدر الإشارة إلى أنه كان علينا استخدام جميع الشروط المسبقة.

بحسب هودجز (1993):

غالباً ما تُنسب أساليب الذهاب والإياب إلى كانتور ، وبرتراند راسل، وسي إتش لانجفورد [...]، ولكن لا يوجد دليل يدعم أيًا من هذه الإسنادات.

على الرغم من أن نظرية المجموعات المرتبة بكثافة والقابلة للعد تُنسب إلى كانتور (1895)، إلا أن طريقة الإثبات المتبادل التي تُستخدم لإثباتها حاليًا طُوِّرت بواسطة إدوارد فيرميلي هنتنغتون (1904) وفيليكس هاوسدورف (1914). لاحقًا، طُبِّقت هذه النظرية في سياقات أخرى، أبرزها من قِبَل رولان فرايسيه في نظرية النماذج .

• مباراة إهرنفويشت وفرايسيه

• هاوسدورف، ف. (1914)، Grundzüge der Mengenlehre
• هودجز، ويلفريد (1993)، نظرية النموذج ، مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-30442-9
• هانتينغتون، إي. في. (1904)، المتصل وأنواع أخرى من الترتيب التسلسلي، مع مقدمة لأعداد كانتور المتسامية ، مطبعة جامعة هارفارد
• ماركر، ديفيد (2002)، نظرية النماذج: مقدمة ، نصوص الدراسات العليا في الرياضيات ، برلين، نيويورك: سبرينغر-فيرلاغ ، ISBN 978-0-387-98760-6