Elementary equivalence

In model theory, a branch of mathematical logic, two structuresM and N of the same signatureσ are called elementarily equivalent if they satisfy the same first-orderσ-sentences.

If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary substructure of M if every first-order σ-formula φ(a₁, …, a_n) with parameters a₁, …, a_n from N is true in N if and only if it is true in M. If N is an elementary substructure of M, then M is called an elementary extension of N. An embeddingh: N → M is called an elementary embedding of N into M if h(N) is an elementary substructure of M.

A substructure N of M is elementary if and only if it passes the Tarski–Vaught test: every first-order formulaφ(x, b₁, …, b_n) with parameters in N that has a solution in M also has a solution in N when evaluated in M. One can prove that two structures are elementarily equivalent with the Ehrenfeucht–Fraïssé games.

Elementary embeddings are used in the study of large cardinals, including rank-into-rank.

تكون البنيتان M و N اللتان لهما نفس التوقيع σ متكافئتين أساسًا إذا كانت كل جملة من الدرجة الأولى (صيغة بدون متغيرات حرة) على σ صحيحة في M إذا وفقط إذا كانت صحيحة في N ، أي إذا كان لـ M و N نفس نظرية الدرجة الأولى الكاملة . إذا كانت M و N متكافئتين أساسًا ، يُكتب M ≡ N.    

تكون النظرية من الدرجة الأولى كاملة إذا وفقط إذا كان أي نموذجين منها متكافئين بشكل أساسي.

على سبيل المثال، لنفترض اللغة التي تحتوي على رمز علاقة ثنائية واحد '<'. إن نموذج R للأعداد الحقيقية بترتيبها المعتاد ونموذج Q للأعداد النسبية بترتيبها المعتاد متكافئان من الناحية الأساسية، لأنهما يفسران '<' على أنه ترتيب خطي كثيف غير محدود . وهذا كافٍ لضمان التكافؤ الأساسي، لأن نظرية الترتيبات الخطية الكثيفة غير المحدودة مكتملة، كما يمكن إثباته بواسطة اختبار Łoś–Vaught .

بشكلٍ أعم، أي نظرية من الدرجة الأولى ذات نموذج لانهائي لها نماذج غير متماثلة، ولكنها متكافئة من حيث العناصر، ويمكن الحصول عليها عبر نظرية لوفنهايم-سكوليم . فعلى سبيل المثال، توجد نماذج غير قياسية لحساب بيانو ، تحتوي على عناصر أخرى غير الأرقام 0 و1 و2 وما إلى ذلك، ومع ذلك فهي متكافئة من حيث العناصر مع النموذج القياسي.

تعتبر N بنية فرعية أولية أو نموذجًا فرعيًا أوليًا لـ M إذا كانت N و M بنيتين لهما نفس التوقيع σ بحيث أنه بالنسبة لجميع صيغ σ من الدرجة الأولى φ ( x ₁ , …, x _n ) مع متغيرات حرة x ₁ , …, x _n ، وجميع العناصر a ₁ , …, a _n من N ، فإن φ ( a ₁ , …, a _n ) تتحقق في N إذا وفقط إذا تحققت في M :           $${\displaystyle N\models \varphi (a_{1},\dots ,a_{n}){\text{ إذا وفقط إذا }}M\models \varphi (a_{1},\dots ,a_{n}).}$$

يظهر هذا التعريف لأول مرة في كتاب تارسكي، فوغت (1957). [ ^{1 ] ويترتب} على ذلك أن N هي بنية فرعية من M.

إذا كانت N بنية فرعية من M ، فيمكن تفسير كل من N و M على أنهما بنيتان في التوقيع σN _، تتكونان من σ بالإضافة إلى رمز ثابت جديد لكل عنصر من عناصر N. وتكون N بنية فرعية أولية من M إذا وفقط إذا كانت N بنية فرعية من M ، وكانت N و M متكافئتين أوليًا كبنيتين من _نوع σN . 

إذا كانت N بنية فرعية أولية من M ، فإن المرء يكتب N${\displaystyle \preceq }$M ويقول إن M هو امتداد أولي لـ N : M${\displaystyle \succeq }$ن .

تعطي نظرية لوفينهايم-سكوليم الهابطة بنية فرعية أولية قابلة للعد لأي بنية من الدرجة الأولى اللانهائية في توقيع قابل للعد على الأكثر؛ تعطي نظرية لوفينهايم-سكوليم الصاعدة امتدادات أولية لأي بنية من الدرجة الأولى اللانهائية ذات عدد كبير بشكل تعسفي.

يُعد اختبار تارسكي -فوت (أو معيار تارسكي-فوت ) شرطًا ضروريًا وكافيًا لكي تكون البنية الفرعية N من البنية M بنيةً فرعيةً أساسية. ويمكن أن يكون مفيدًا في بناء بنية فرعية أساسية لبنية كبيرة.

لتكن M بنية ذات توقيع σ و N بنية فرعية من M. عندئذٍ، _تكون N بنية فرعية أولية من M إذا وفقط إذا كان لكل صيغة من الدرجة الأولى φ ( x , y₁ , …, yn ) على σ وجميع العناصر b₁ _, …, _bₙ من N ، إذا _كانت M     ${\displaystyle \models }$${\displaystyle \exists }$إذا كان x φ ( x , b ₁ , …, b _n )، فإنه يوجد عنصر a في N بحيث M    ${\displaystyle \models }$φ ( أ , ب ₁ , …, ب _ن ). ^{[ 2 ]}   

التضمين الأولي لبنية N في بنية M لها نفس التوقيع σ هو دالة h : N → M بحيث يكون لكل صيغة σ من الدرجة الأولى φ ( x ₁ , …, x _n ) وجميع العناصر a ₁ , …, a _n من N ،        

شمال${\displaystyle \models }$φ ( a ₁ ,  …, a _n ) إذا وفقط إذا M ${\displaystyle \models }$φ ( h ( a ₁ ),  …, h ( a _n )). 

كل تضمين أولي هو تماثل قوي ، وهو يؤدي إلى تماثل بين N وبنية فرعية أولية من M.

تُعدّ التضمينات الأولية أهمّ الخرائط في نظرية النماذج. وفي نظرية المجموعات ، تلعب التضمينات الأولية التي يكون مجالها V (عالم نظرية المجموعات) دورًا مهمًا في نظرية الأعداد الكبيرة (انظر أيضًا النقطة الحرجة ).

• تشانغ، تشين تشونغ ؛ كيسلر، هـ. جيروم (1990) [1973]، نظرية النماذج ، دراسات في المنطق وأسس الرياضيات (  الطبعة الثالثة)، إلسيفير، ISBN 978-0-444-88054-3.
• هودجز، ويلفريد (1997)، نظرية نموذجية مختصرة ، كامبريدج: مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-58713-6.
• مونك، ج. دونالد (1976)، المنطق الرياضي ، نصوص الدراسات العليا في الرياضيات، نيويورك • هايدلبرغ • برلين: سبرينغر فيرلاغ، ISBN 0-387-90170-1