مقالات

3.4: الهياكل الأساسية ونظريات Löwenheim-Skolem - الرياضيات


في هذا القسم سوف نناقش العلاقة بين الهياكل. نبدأ بتحديد مفهوم البنية التحتية.

التعريف 3.4.1.

إذا كان ( mathfrak {A} ) و ( mathfrak {B} ) هيكلين ( mathcal {L} ) - ، فسنقول أن ( mathfrak {A} ) هو بنية من ( mathfrak {B} ) ، واكتب ( mathfrak {A} subseteq mathfrak {B} ) ، إذا:

  1. (أ المجموعة الفرعية ب ).
  2. لكل رمز ثابت (c ) ، (c ^ mathfrak {A} = c ^ mathfrak {B} ).
  3. لكل (n ) - رمز علاقة ary (R ) ، (R ^ mathfrak {A} = R ^ mathfrak {B} cap A ^ n ).
  4. لكل (n ) - رمز دالة ary (f ) ، (f ^ mathfrak {A} = f ^ mathfrak {B} upharpoonright_ {A ^ n} ). بمعنى آخر ، لكل (n ) - رمز دالة ary (f ) وكل (a in A ) ، (f ^ mathfrak {A} left (a right) = f ^ mathfrak {ب} يسار (أ يمين) ). (وهذا ما يسمى ب تقييد الوظيفة (f ^ mathfrak {B} ) على المجموعة (A ^ n ).)

وبالتالي فإن البنية التحتية لـ ( mathfrak {B} ) يتم تحديدها تمامًا من خلال الكون الخاص بها ، ويمكن أن يكون هذا الكون أي مجموعة فرعية غير فارغة من (B ) تحتوي على ثوابت ومغلقة تحت كل دالة (f ).

المثال 3.4.2:

لنفترض أننا نحاول بناء بنية فرعية ( mathfrak {A} ) من البنية ( mathfrak {N} = left ( mathbb {N} ، 0 ، S ، + ، cdot ، E ، < حق)). نظرًا لأنه يجب إغلاق (A ) ضمن الوظائف وتحتوي على الثوابت ، يجب أن يكون الرقم 0 عنصرًا من عناصر الكون (A ). ولكن الآن ، نظرًا لأنه يجب إغلاق البنية التحتية تحت الوظيفة (S ) ، فمن الواضح أن كل رقم طبيعي يجب أن يكون عنصرًا في (A ). وبالتالي فإن ( mathfrak {N} ) لا يحتوي على بنى أساسية مناسبة.

المثال 3.4.3:

الآن ، لنفترض أننا نحاول إيجاد بعض البنى التحتية للهيكل ( mathfrak {B} = left ( mathbb {N} ، 0 ، < right) ) ، مع التفسيرات المعتادة لـ 0 و (< ). نظرًا لعدم وجود رموز وظيفية ، فإن أي مجموعة فرعية غير فارغة من ( mathbb {N} ) تتضمن الرقم 0 يمكن أن تكون بمثابة عالم بنية تحتية ( mathfrak {A} subseteq mathfrak {B} ).

افترض أننا تركنا ( mathfrak {A} = left ( {0 }، 0، < right) ). ثم لاحظ أنه على الرغم من ( mathfrak {A} subseteq mathfrak {B} ) ، إلا أن هناك الكثير من الجمل الصحيحة في بنية واحدة غير صحيحة في البنية الأخرى. على سبيل المثال ، ( left ( forall x right) left ( موجود y right) x

كما يوضح المثال 3.4.3 ، إذا حصلنا على هيكلين مثل ( mathfrak {A} subseteq mathfrak {B} ) ، في أغلب الأحيان تتوقع أن ( mathfrak {A} ) و ( mathfrak {B} ) سيكون مختلفًا جدًا ، وسيكون هناك الكثير من الجمل التي قد تكون صحيحة في إحدى البنى التي لن تكون صحيحة في الأخرى.

ومع ذلك ، في بعض الأحيان ، ترتبط الحقيقة في الهيكل الأصغر ارتباطًا وثيقًا بالحقيقة في الهيكل الأكبر.

التعريف 3.4.4.

افترض أن ( mathfrak {A} ) و ( mathfrak {B} ) هما ( mathcal {L} ) - الهياكل و ( mathfrak {A} subseteq mathfrak {B} ) . نقول أن ( mathfrak {A} ) هو ملف البنية الأساسية من ( mathfrak {B} ) (بالتساوي ، ( mathfrak {B} ) هو التمديد الابتدائي من ( mathfrak {A} )) ، واكتب ( mathfrak {A} prec mathfrak {B} ) ، إذا كان لكل (s: Vars rightarrow A ) ولكل ( الرياضيات {L} ) - الصيغة ( phi ) ،

[ mathfrak {A} Models phi left [s right] : text {if and only if} : mathfrak {B} Models phi left [s right]. ]

قشر: لاحظ أنه إذا أردنا إثبات ( mathfrak {A} prec mathfrak {B} ) ، فإننا نحتاج فقط إلى إثبات ( mathfrak {A} Models phi left [s right] rightarrow mathfrak {B} Models phi left [s right] ) ، فبمجرد أن نفعل ذلك ، يأتي الاتجاه الآخر مجانًا باستخدام النفي والمعارض.

مقترح 3.4.5.

افترض أن ( mathfrak {A} prec mathfrak {B} ). إذن فإن الجملة ( sigma ) تكون صحيحة في ( mathfrak {A} ) إذا وفقط إذا كانت صحيحة في ( mathfrak {B} ).

المثال 3.4.6:

رأينا سابقًا أن البنية ( mathfrak {B} = left ( mathbb {N} ، 0 ، < right) ) بها الكثير من البنى التحتية. ومع ذلك ، لا يحتوي ( mathfrak {B} ) على بنى أساسية مناسبة. لنفترض أن ( mathfrak {A} prec mathfrak {B} ). بالتأكيد ، (0 in A ) ، مثل ( mathfrak {A} ) هي بنية فرعية. بما أن الجملة ( left ( موجود y right) left [0

[ mathfrak {A} Models left ( موجود y يمين) يسار [0

وبالتالي ، لأي وظيفة تعيين (s: Vars rightarrow A ) هناك بعض (a in A ) مثل

[ mathfrak {A} Models left [0

إصلاح مثل هذا (ق ) ومثل (أ في أ ). الآن نستخدم عنصرية مرة أخرى. منذ ( mathfrak {A} prec mathfrak {B} ) و (s left [y | a right]: Vars rightarrow A ) ، نحن نعلم ذلك

[ mathfrak {B} Models left [0

لكن في البنية ( mathfrak {B} ) ، يوجد عنصر فريد يجعل الصيغة ( left [0

يوضح هذا المثال أنه عند بناء بنية أساسية أولية لهيكل معين ( mathfrak {B} ) ، نحتاج إلى التأكد من أن الشهود لكل جملة وجودية صحيحة في ( mathfrak {B} ) يجب تضمينها في عالم البنية الأساسية ( mathfrak {A} ). ستكون هذه الفكرة جوهر إثبات نظرية Downward Löwenheim-Skolem ، نظرية 3.4.8. في الواقع ، يقول lemma التالي أن التأكد من أن هؤلاء الشهود هم عناصر ( mathfrak {A} ) هو كل ما هو مطلوب للتأكد من أن ( mathfrak {A} ) هو بنية أساسية أولية لـ ( mathfrak {ب} ).

Lemma 3.4.7.

افترض أن ( mathfrak {A} subseteq mathfrak {B} ) وذلك لكل صيغة ( alpha ) وكل (s: Vars rightarrow A ) مثل ( mathfrak {B} نماذج موجودة x alpha left [s right] ) يوجد (a in A ) مثل ( mathfrak {B} Models alpha left [s left [x | a صحيح صحيح]). ثم ( mathfrak {A} prec mathfrak {B} ).

دليل

سنبين ، بالنظر إلى افتراضات lemma ، أنه إذا كان ( phi ) أي صيغة و (s ) هي أي وظيفة تعيين متغيرة في (A ) ، ( mathfrak {A} Models phi left [s right] ) إذا وفقط إذا ( mathfrak {B} Models phi left [s right] ) ، وبالتالي ( mathfrak {A} prec mathfrak {B } ).

هذا دليل سهل عن طريق الاستقراء على تعقيد ( phi ) ، والذي سنجعله أسهل من خلال ملاحظة أنه يمكننا استبدال ( forall ) الخطوة الاستقرائية بخطوة استقرائية ( موجود ) ، كما يمكن تعريف ( forall ) من حيث ( موجود ).

لذلك بالنسبة للحالة الأساسية ، افترض أن ( phi ) ذرية. على سبيل المثال ، إذا كان ( phi ) هو (R left (x، y right) ) ، إذن ( mathfrak {A} Models phi left [s right] ) إذا وفقط إذا ( يسار (س يسار (س يمين) ، ق يسار (ص يمين) يمين) في R ^ mathfrak {A} ). لكن (R ^ mathfrak {A} = R ^ mathfrak {B} cap A ^ 2 ) ، لذلك ( left (s left (x right) ، s left (y right) يمين) في R ^ mathfrak {A} ) إذا وفقط إذا ( left (s left (x right) ، s left (y right) right) in R ^ mathfrak {B } ). لكن ( left (s left (x right) ، s left (y right) right) in R ^ mathfrak {B} ) إذا وفقط إذا ( mathfrak {B} Models phi left [s right] ) ، حسب الحاجة.

بالنسبة للجمل الاستقرائية ، افترض أن ( phi ) هو ( neg alpha ). ثم

[ start {array} {rll} mathfrak {A} Models phi left [s right] & text {if and only if} : mathfrak {A} Models neg alpha left [s right] & & text {if and only if} : mathfrak {A} not Models alpha left [s right] & & text {if and only if} : mathfrak {B} not Models alpha left [s right] & text {فرضية استقرائية & text {if and only if} : mathfrak {B} Models neg alpha يسار [s right] & & text {if and only if} : mathfrak {B} Models phi left [s right]. نهاية {مجموعة} ]

الجملة الاستقرائية الثانية ، إذا كانت ( phi ) هي ( alpha lor beta ) ، متشابهة.

بالنسبة للجملة الاستقرائية الأخيرة ، افترض أن ( phi ) هو ( موجود س ألفا ). افترض أيضًا أن ( mathfrak {A} Models phi left [s right] )؛ بمعنى آخر ، ( mathfrak {A} Models موجود x alpha left [s right] ). ثم بالنسبة لبعض (a in A ) ، ( mathfrak {A} Models alpha left [s left [x | a right] right] ). بما أن (s left [x | a right] ) هي دالة تعيين المتغيرات إلى (A ) ، من خلال فرضيتنا الاستقرائية ، ( mathfrak {B} Models alpha left [s left [s left [ x | a right] right] ). ولكن بعد ذلك ( mathfrak {B} Models موجود x alpha left [s right] ) حسب الحاجة. بالنسبة للاتجاه الآخر ، افترض أن ( mathfrak {B} Models موجود x alpha left [s right] ) ، حيث (s: Vars rightarrow A ). نستخدم افتراض lemma لإيجاد (a in A ) مثل ( mathfrak {B} Models alpha left [s left [x | a right] right] ). بما أن (s left [x | a right] ) هي دالة ذات نطاق (A ) ، من خلال الفرضية الاستقرائية ( mathfrak {A} Models alpha left [s left [x | a right] right] ) ، وبالتالي ( mathfrak {B} Models موجود x alpha left [s right] ) ، والإثبات كامل.

قشر: سنقوم الآن بإلقاء نظرة على نظريات Löwenheim-Skolem ، التي تم نشرها في عام 1915. لفهم هذه النظريات ، يجب أن يكون لديك على الأقل فهم أساسي للعناصر الأساسية ، وهو موضوع تم تحديده في الملحق. ومع ذلك ، إذا كنت في عجلة من أمرك ، يكفي أن تتذكر فقط أن هناك العديد من الأحجام المختلفة للمجموعات اللانهائية. تعد المجموعة اللانهائية (A ) قابلة للعد إذا كان هناك انحراف بين (A ) ومجموعة الأعداد الطبيعية ( mathbb {N} ) ، وإلا فإن المجموعة غير قابلة للعد. تتضمن أمثلة المجموعات المعدودة الأعداد الصحيحة ومجموعة الأرقام المنطقية. مجموعة الأرقام الحقيقية غير معدودة ، حيث لا يوجد انحياز بين ( mathbb {R} ) و ( mathbb {N} ). لذلك هناك عدد حقيقي أكثر من الأعداد الطبيعية. هناك عدد لا نهائي من الأحجام المختلفة للمجموعات اللانهائية. أصغر حجم لانهائي قابل للعد.

نظرية 3.4.8: نظرية löwenheim-skolem الهابط

افترض أن ( mathcal {L} ) لغة قابلة للعد و ( mathfrak {B} ) هي بنية ( mathcal {L} ) -. ثم ( mathfrak {B} ) له بنية أساسية قابلة للعد.

دليل

إذا كان (B ) محدودًا أو قابلًا للعد لانهائيًا ، فإن ( mathfrak {B} ) هو بنيته التحتية الأولية القابلة للعد ، لذا افترض أن (B ) غير معدود. نظرًا لأن اللغة ( mathcal {L} ) قابلة للعد ، فلا يوجد سوى عدد لا يحصى من الصيغ ( mathcal {L} ) - وبالتالي عددًا لا يحصى من الصيغ من النموذج ( موجود س ألفا ) .

لنفترض أن (A_0 ) أي مجموعة فرعية معدودة غير فارغة من (B ). نوضح كيفية إنشاء (A_1 ) بحيث يكون (A_0 subseteq A_1 ) و (A_1 ) قابلاً للعد. الفكرة هي إضافة (A_0 ) شهود على الحقيقة (في ( mathfrak {B} )) من البيانات الوجودية.

لاحظ أنه نظرًا لأن (A_0 ) قابل للعد ، لا يوجد سوى العديد من الوظائف (s ^ prime: Vars rightarrow A_0 ) التي تكون ثابتة في النهاية ، ونعني بها أن هناك عددًا طبيعيًا (k ) مثل أنه إذا (i، j> k ) ، ثم (s ^ prime left (v_i right) = s ^ prime left (v_j right) ). (هذا تمرين جيد لمن حصل منكم على دورة في نظرية المجموعات أو مرتاحًا بشكل معقول لحجج العلاقة الأساسية.) أيضًا ، إذا حصلنا على أي ( phi ) وأي (s: Vars rightarrow A_0 ) ) ، يمكننا العثور على ثابت (s ^ prime: Vars rightarrow A_0 ) بحيث يتفق (s ) و (s ^ prime ) على المتغيرات المجانية لـ ( phi ) ، وبالتالي ( mathfrak {B} Models phi left [s right] ) فقط في حالة ( mathfrak {B} Models phi left [s ^ prime right] ).

بناء (A_1 ): لكل صيغة من الصيغة ( موجود س ألفا ) وكل (s: Vars rightarrow A_0 ) مثل ( mathfrak {B} Models موجود x alpha left [s right] ) ، ابحث عن ثابت (s ^ prime: Vars rightarrow A_0 ) بحيث يتفق (s ) و (s ^ prime ) على المتغيرات المجانية لـ ( موجود س ألفا ) ). اختر عنصرًا (a _ { alpha، s ^ prime} in B ) مثل ( mathfrak {B} Models alpha left [s left [x | a _ { alpha، s ^ Prime} right] right] ) ، واسمحوا

[A_1 = A_0 cup {a _ { alpha، s ^ prime} } _ { text {all} : alpha، s: Vars rightarrow A_0}. ]

لاحظ أن (A_1 ) قابل للعد ، حيث لا يوجد سوى عدد لا يحصى من ( alpha ) والعديد من (s ^ prime ).

استمر في هذا البناء ، بشكل متكرر بناء (A_ {n + 1} ) من (A_n ). دعونا (A = cup_ {n = 0} ^ infty A_n ). نظرًا لأن (A ) اتحاد قابل للعد من المجموعات المعدودة ، فإن (A ) قابل للعد.

الآن قمنا ببناء كون محتمل (A ) لبنية تحتية لـ ( mathfrak {B} ). يجب أن نثبت أن (A ) مغلق تحت وظائف ( mathfrak {B} ) (بالملاحظات التالية للتعريف 3.4.1 وهذا يوضح أن ( mathfrak {A} ) هو بنية فرعية من ( mathfrak {B} )) ، وعلينا أن نبين أن ( mathfrak {A} ) يفي بالمعايير المنصوص عليها في Lemma 3.4.7 ، لذلك سنعرف أن ( mathfrak {A} ) هي بنية أساسية أولية لـ ( mathfrak {B} ).

أولاً ، لتوضيح أن (A ) مغلق تحت وظائف ( mathfrak {B} ) ، افترض أن (a in A ) و (f ) هو رمز دالة أحادية (عام الحالة متطابقة) وهذا (b = f ^ mathfrak {B} left (a right) ). يجب أن نظهر ذلك (ب في أ ). إصلاح (n ) كبير جدًا بحيث (a in A_n ) ، دع ( phi ) تكون الصيغة ( يسار ( موجود y يمين) y = f left (x right) ) ، وليكن (s ) أي وظيفة تعيين في (أ ) بحيث يكون (ق يسار (س يمين) = أ ). نعلم أن ( mathfrak {B} Models left ( موجود y يمين) y = f left (x right) left [s right] ) ، ونعلم أنه إذا ( mathfrak {B} Models left (y = f left (x right) right) left [s left [y | d right] right] ) ، ثم (d = b ). لذلك ، في بناءنا لـ (A_ {n + 1} ) يجب أن نستخدم (a_ {y = f left (x right) ، s} = b ) ، لذلك (b in A_ { n + 1} ) و (b in A ) حسب الحاجة.

لاستخدام Lemma 3.4.7 ، يجب أن نوضح أنه إذا كانت ( alpha ) صيغة و (s: Vars rightarrow A ) مثل ( mathfrak {B} Models alpha left [s left [x | a right] right] ). لذا ، قم بإصلاح مثل ( alpha ) ومثل (s ). ابحث عن ثابت في النهاية (s ^ prime: Vars rightarrow A ) بحيث يتفق (s ) و (s ^ prime ) على جميع المتغيرات المجانية لـ ( alpha ). وبالتالي ( mathfrak {B} Models موجود x alpha left [s ^ prime right] ) ، وجميع قيم (s ^ prime ) هي عناصر لبعضها ثابتة (A_n ) ، حيث إن (s ^ prime ) يأخذ فقط عددًا محدودًا من القيم. ولكن بعد ذلك ببناء (A_ {n + 1} ) مثل ( mathfrak {B} Models alpha left [s left [x | a right] right] ) ، حسب الحاجة.

لذا فقد قابلنا فرضيات Lemma 3.4.7 ، وبالتالي فإن ( mathfrak {A} ) عبارة عن بنية أساسية أولية معدودة لـ ( mathfrak {B} ) ، حسب الحاجة.

قشر: نود أن ننظر إلى القليل من هذا الدليل عن كثب. في بناء (A_1 ) ، ما فعلناه هو العثور على (a _ { infty، s ^ prime} ) لكل صيغة ( موجود x alpha ) ولكل (s: Vars rightarrow A ) ، والنقطة هي أن (a _ { infty، s ^ prime} ) سيكون شاهداً على الحقيقة في ( mathfrak {B} ) من البيان الوجودي ( موجود س ألفا ). لذلك قمنا ببناء ملف وظيفة والتي ، بالنظر إلى صيغة وجودية ( موجودة x alpha ) ووظيفة تعيين ، تجد قيمة لـ (x ) تجعل الصيغة ( alpha ) صحيحة. وظيفة من هذا النوع تسمى أ وظيفة Skolem، ويمكن تلخيص بناء (A ) في إثبات نظرية Downward Löwenheim-Skolem: لنفترض أن (A_0 ) مجموعة فرعية معدودة من (B ) ، وتشكل إغلاق (A_0 ) ضمن مجموعة وظائف Skolem. ثم أوضح أن هذا الإغلاق هو بنية أساسية أولية لـ ( mathfrak {B} ).

المثال 3.4.9:

لقد رأينا إشارة في التمرين 4 في القسم 2.8 إلى أن بديهيات نظرية مجموعة Zermelo-Fraenkel (المعروفة باسم ZF) يمكن إضفاء الطابع الرسمي عليها في منطق الدرجة الأولى. بقبول ذلك على أنه صحيح (وهو كذلك) ، نعلم أنه إذا كانت البديهيات متسقة ، فلديهم نموذجًا ، ومن ثم وفقًا لنظرية Downward Löwenheim-Skolem ، يجب أن يكون هناك نموذج قابل للعد لنظرية المجموعة. لكن هذا مثير للاهتمام ، حيث إن جميع نظريات ZF التالية هي:

  • هناك مجموعة لا حصر لها.
  • في حالة وجود مجموعة (أ ) ، فإن مجموعة مجموعات فرعية من (أ ) موجودة.
  • إذا كان (a ) لانهائيًا إلى حدٍّ ما ، فإن مجموعة مجموعات فرعية من (أ ) لا تعد. (هذه هي نظرية كانتور).

الآن ، لنفترض أن ( mathfrak {A} ) هو نموذجنا المعدود لـ ZF ، ونفترض أن (a ) هو عنصر (A ) ولانهائي إلى حد ما. إذا كانت (ب ) هي مجموعة كل المجموعات الفرعية لـ (أ ) ، فإننا نعلم أن (ب ) غير قابل للعد (حسب نظرية كانتور) ومع ذلك يجب أن يكون (ب ) قابلاً للعد ، مثل جميع عناصر (b ) موجودة في النموذج ( mathfrak {A} ) و ( mathfrak {A} ) قابلة للعد! لذلك يجب أن يكون (ب ) معدودًا وغير معدود! هذا يسمى (بشكل غير صحيح إلى حد ما) مفارقة سكوليم ، والتمرين 8 يطلب منك اكتشاف حل للمفارقة

ربما تكون طريقة التفكير في نظرية Downward Löwenheim-Skolem هي أنها تضمن أنه إذا كان هناك أي نماذج لا نهائية لمجموعة معينة من الصيغ ، فهناك نموذج صغير (يعني إلى حد كبير غير محدود) لتلك المجموعة من الصيغ. يبدو من المعقول التساؤل عما إذا كان هناك ضمان مماثل حول النماذج الكبيرة ، وهناك.

مقترح 3.4.10.

افترض أن ( Sigma ) عبارة عن مجموعة من ( mathcal {L} ) - صيغ ذات نموذج لا نهائي. إذا كان ( kappa ) عددًا لا نهائيًا من الكاردينال ، فهناك نموذج ( Sigma ) من أصل أكبر من أو يساوي ( kappa ).

دليل - إثبات

هذا تطبيق سهل لنظرية الضغط. قم بتوسيع ( mathcal {L} ) لتضمين ( kappa ) رموز ثابتة جديدة (c_i ) ، ودع ( Gamma = Sigma cup {c_i neq c_j | i neq j } ). إذن ، ( Gamma ) مرضي تمامًا ، حيث يمكننا أخذ نموذجنا اللامتناهي المعطى لـ ( Sigma ) وتفسير (c_i ) في هذا النموذج بطريقة (c_i neq c_j ) لأي مجموعة محدودة من الرموز الثابتة. وفقًا لنظرية الانضغاط ، توجد بنية ( mathfrak {A} ) تمثل نموذجًا لـ ( Gamma ) ، وبالتالي فإن أصل (A ) أكبر من أو يساوي () كابا). إذا قصرنا ( mathfrak {A} ) على اللغة الأصلية ، فسنحصل على نموذج ( Sigma ) من العلاقة الأساسية المطلوبة.

نتيجة طبيعية 3.4.11.

إذا كانت ( Sigma ) عبارة عن مجموعة من الصيغ من لغة معدودة بنموذج لا نهائي ، وإذا كان ( kappa ) عددًا لا نهائيًا من الكاردينال ، فهناك نموذج ( Sigma ) من أصل ( كابا ).

دليل - إثبات

أولاً ، استخدم Proposition 3.4.10 للحصول على ( mathfrak {B} ) ، نموذج ( Sigma ) من أصل أكبر من أو يساوي ( kappa ). بعد ذلك ، قم بتقليد إثبات نظرية Downward Löwenheim-Skolem ، بدءًا من مجموعة (A_0 subseteq B ) من العلاقة الأساسية تمامًا ( kappa ). بعد ذلك ، سيحتوي (A ) الذي تم إنشاؤه في هذا الدليل أيضًا على أصل ( kappa ) ، و ( mathfrak {A} prec mathfrak {B} ) ، ( mathfrak {A} ) سيكون نموذجًا لـ ( Sigma ) من أصل ( kappa ).

نتيجة طبيعية 3.4.12

إذا كانت ( mathfrak {A} ) بنية ( mathcal {L} ) لانهائية ، فهناك لا مجموعة من الصيغ من الدرجة الأولى التي تميز ( mathfrak {A} ) حتى تماثل الشكل.

دليل - إثبات

بتعبير أدق ، تقول النتيجة الطبيعية أنه لا توجد مجموعة من الصيغ ( Sigma ) مثل ( mathfrak {B} Models Sigma ) إذا وفقط إذا ( mathfrak {A} cong mathfrak { ب}). نحن نعلم أن هناك نماذج لـ ( Sigma ) لجميع الكاردينالات ، ونعلم أنه لا توجد تحيزات بين مجموعات من الكاردينالات المختلفة. لذلك يجب أن يكون هناك العديد من نماذج ( Sigma ) التي لا تتشابه مع ( mathfrak {A} ).

قشر: هناك مجموعات من البديهيات التي تميز الهياكل اللانهائية. على سبيل المثال ، تتضمن بديهيات الدرجة الثانية في حساب Peano البديهيات لضمان أن الجمع والضرب يتصرفان بشكل طبيعي ، كما أنها تتضمن مبدأ الاستقراء الرياضي: إذا كان (M ) مجموعة من الأرقام ، إذا (0 في) M ) ، وإذا (S left (n right) in M ​​) لكل (n ) مثل هذا (n in M ​​) ، ثم ( يسار ( forall n right ) يسار (n في M يمين) ).

أي نموذج من Peano Arithmetic يتشابه مع الأعداد الطبيعية ، لكن لاحظ أننا استخدمنا مفهومين (مجموعات من الأرقام وعلاقة العناصر) ليسا جزءًا من وصفنا لـ ( mathfrak {N} ). من خلال تقديم مجموعات من الأرقام ، نكون قد تركنا عالم منطق الدرجة الأولى ودخلنا منطق الدرجة الثانية ، ولا يمكننا تمييز ( mathfrak {N} ) إلا باستخدام منطق الدرجة الثانية. للحصول على مناقشة لطيفة لهذا الموضوع ، انظر [Bell and Machover 77 ، الفصل 7 ، القسم 2].

النتائج من الاقتراح 3.4.10 إلى النتيجة الطبيعية 3.4.12 تعطينا نماذج كبيرة ، لكن لها نكهة مختلفة قليلاً عن نظرية Downward Löwenheim-Skolem ، من حيث أنها لا تضمن أن النموذج الصغير هو بنية أساسية أولية من نموذج كبير. هذا هو محتوى نظرية Upward Löwenheim-Skolem ، والدليل الذي تم توضيحه في التمارين.

نظرية 3.4.13: نظرية löwenheim-Skolem التصاعدية

إذا كانت ( mathcal {L} ) لغة معدودة ، فإن ( mathfrak {A} ) عبارة عن بنية لا نهائية ( mathcal {L} ) و ( kappa ) أساسية ، ثم ( mathfrak {A} ) له امتداد أولي ( mathfrak {B} ) بحيث تكون عدد العناصر (B ) أكبر من أو يساوي ( kappa ).

تمارين

  1. افترض أن ( mathfrak {B} subseteq mathfrak {A} ) ، أن ( phi ) من الشكل ( left ( forall x right) psi ) ، حيث ( psi ) خالي من المحددات الكمية ، وهذا ( mathfrak {A} Models phi ). إثبات أن ( mathfrak {B} Models phi ). النسخة المختصرة من هذه الحقيقة هي ، "يتم الاحتفاظ بالجمل العامة إلى أسفل". صياغة وإثبات الحقيقة المقابلة للجمل الوجودية.
  2. تبرير قشر التعريف التالي 3.4.4.
  3. أظهر أنه إذا ( mathfrak {A} prec mathfrak {B} ) و ( mathfrak {C} prec mathfrak {B} ) و ( mathfrak {A} subseteq mathfrak {C } ) ، ثم ( mathfrak {A} prec mathfrak {C} ).
  4. افترض أن لدينا ملف سلسلة ابتدائية، مجموعة من هياكل ( mathcal {L} ) - مثل تلك
    [ mathfrak {A} _1 prec mathfrak {A} _2 prec mathfrak {A} _3 prec cdots ]
    ودع ( mathfrak {A} = bigcup ^ infty_ {i = 1} mathfrak {A} _i ). إذن الكون (A ) لـ ( mathfrak {A} ) هو اتحاد الأكوان (A_i ) ، (R ^ mathfrak {A} = bigcup ^ infty_ {i = 1} R ^ { mathfrak {A} _i} ) ، وما إلى ذلك. أظهر أن ( mathfrak {A} _i prec mathfrak {A} ) لكل (i ). [اقتراح: إظهار أن ( mathfrak {A} _i subseteq mathfrak {A} ) سهل جدًا من خلال التعريف. للحصول على هذا ( mathfrak {A} ) هو ملف ابتدائي التمديد ، عليك استخدام الاستقراء على مدى تعقيد الصيغ. لاحظ من خلال التعليقات التالية التعريف 3.4.4 أنك بحاجة إلى إثبات اتجاه واحد فقط. قد تجد أنه من الأسهل استخدام ( موجود ) بدلاً من ( forall ) في جزء المحدد الكمي من الخطوة الاستقرائية للإثبات.]
  5. إثبات اقتراح 3.4.5.
  6. أظهر أنه إذا كان ( mathfrak {A} prec mathfrak {B} ) وإذا كان هناك عنصر (b in B ) وصيغة ( phi left (x right) ) مثل هذا ( mathfrak {B} Models phi left [s left [x | b right] right] ) ولكل ( hat {b} in B ) ، ( mathfrak {B} not Models phi left [s left [x | hat {b} right] right] ) ، ثم (b in A ). [اقتراح: هذا مشابه جدًا للمثال 3.4.6.]
  7. افترض أن ( mathfrak {B} = { mathbb {N}، +، cdot } ) ، وليكن (A_0 = {2، 3 } ). لنفترض أن (F ) هو مجموعة وظائف Skolem ( {f _ { alpha، s} } ) المقابلة لـ ( alpha ) من النموذج ( left ( موجود x يمين) ) x = yz ). ابحث عن إغلاق (A_0 ) ضمن (F ). [اقتراح: لا تنس أن وظائف التعيين التي تحتاج إلى أخذها في الاعتبار هي وظائف يتم تعيينها في (A_0 ) في البداية ، ثم (A_1 ) ، وهكذا. ربما تريد كتابة (A_1 ) ، ثم (A_2 ) ، وما إلى ذلك. نحن نستخدم الترميز هنا المقابل لإثبات النظرية 3.4.8.]
  8. أن نقول أن المجموعة (أ ) قابلة للعد يعني أن هناك دالة ذات مجال الأعداد الطبيعية ومجال الترميز (أ ) وهذا هو انحياز. لاحظ أن هذا بيان وجودي ، يقول أن نوعًا معينًا من الوظيفة موجود. الآن ، فكر في المثال 3.4.9 ومعرفة ما إذا كان بإمكانك معرفة سبب عدم تناقض أن المجموعة (b ) قابلة للعد وغير قابلة للعد. على وجه الخصوص ، فكر في ما يعنيه أن تكون العبارة الوجودية صحيحة في بنية ( mathfrak {A} ) ، بدلاً من كونها صحيحة في العالم الحقيقي (أيًا كان الذي - التي يعني!).
  9. (نحو إثبات نظرية Löwenheim-Skolem التصاعدية) إذا كان ( mathfrak {A} ) عبارة عن ( mathcal {L} ) - بنية ، فلنترك ( mathcal {L} left (A right) = mathcal {L} cup { bar {a} | a in A } ) ، حيث يمثل كل ( bar {a} ) رمزًا ثابتًا جديدًا. بعد ذلك ، دع ( bar { mathfrak {A}} ) يكون ( mathcal {L} left (A right) ) - بنية لها نفس الكون مثل ( mathfrak {A} ) ونفس تفسير رموز ( mathcal {L} ) كـ ( mathfrak {A} ) ، وتفسير كل ( bar {a} ) كـ (a ). ثم نحدد ال رسم تخطيطي كامل لـ ( mathfrak {A} ) كما
    [Th left ( bar { mathfrak {A}} right) = { sigma | sigma : text {is an} : mathcal {L} left (A right) text {-formula that} : bar { mathfrak {A}} Models sigma }. ]
    أظهر أنه إذا كان ( bar { mathfrak {B}} ) هو أي نموذج من (Th left ( bar { mathfrak {A}} right) ) ، وإذا كان ( mathfrak {B} = bar { mathfrak {B}} upharpoonright_ mathcal {L} ) ، ثم ( mathfrak {A} ) متماثل مع بنية أساسية أولية لـ ( mathfrak {B} ). [اقتراح: لنحصل على (h: A rightarrow B ) من خلال (h left (a right) = bar {a} ^ mathfrak {B} ). دع (C ) يكون نطاق (ح ). إظهار (C ) مغلق تحت (f ^ mathfrak {B} ) لكل (f ) في ( mathcal {L} ) ، وبالتالي فإن (C ) هو عالم ( mathfrak {C} ) ، بنية فرعية لـ ( mathfrak {B} ). إذن show (h ) هو تماثل بين ( mathfrak {A} ) و ( mathfrak {C} ). أخيرًا ، بيّن أن ( mathfrak {C} prec mathfrak {B} ).]
  10. استخدم التمرين 9 لإثبات نظرية Löwenheim-Skolem التصاعدية من خلال إيجاد نموذج ( bar { mathfrak {B}} ) للرسم التخطيطي الكامل للنموذج المحدد ( mathfrak {A} ) بحيث تكون العلاقة الأساسية لـ ( bar {B} ) أكبر من أو يساوي ( kappa ).
  11. يمكننا الآن ملء بعض تفاصيل مناقشتنا للتحليل غير القياسي من المثال 3.3.5. نظرًا لأن اللغة ( mathcal {L} _ mathbb {R} ) في هذا المثال تتضمن بالفعل رموزًا ثابتة لكل رقم حقيقي ، فإن الرسم التخطيطي الكامل لـ ( mathfrak {R} ) ليس أكثر من (Th يسار ( mathfrak {R} يمين) ). اشرح كيف يوضح التمرين 9 وجود نسخة متشابهة من الخط الحقيقي الذي يعيش داخل الهيكل ( mathfrak {A} ).

- نظريات Löwenheim-Skolem

يقدم هذا الفصل لمحة عامة عن نظريات Löwenheim – Skolem. يقدم هذا الفصل صورة لما تم الحصول عليه فيما يتعلق بظاهرة Löwenheim – Skolem. يقدم هذا الفصل بعض المصطلحات الأساسية ، متبوعًا بوصف النتيجة الأصلية لـ Löwenheim و Skolem جنبًا إلى جنب مع الامتدادات الفورية لبعض المنطق الأخرى. يعالج هذا الفصل نظريات النقل الأقوى لمنطق الرتبة الأولى واللغات اللانهائية. إنها متغيرات لما يسمى نظرية Löwenheim – Skolem – Tarski. ثم يتم تفصيل مشكلة الطيف لمنطق الدرجة الأولى. يبحث هذا الفصل في التحويلات الخاصة من "كبير" إلى "صغير" ، ويتعامل مع مبادئ الانعكاس في نظرية المجموعات. تمت مناقشة خاصية النموذج المحدود ، التي توفر النقل من "لانهائي" إلى "محدود". يسأل الفصل عن صحة نظريات النقل للمنطق ، والتي تحتوي على عوامل لتحديد الأصول. يؤدي السؤال إلى نوع أكثر عمومية من نظريات التحويل من الدرجة الأولى ، والتي تتضمن العديد من الأصول الأساسية. بعد النظر في العديد من المنطق فيما يتعلق بصحة نظريات النقل ، يتم التعامل مع موضوع أرقام Löwenheim وأرقام Hanf كوسيلة لقياس مدى صحة نظريات النقل. عرض النتائج مصحوب بمعلومات محددة حول الأدبيات.


1. لغات وهياكل من الدرجة الأولى

تحمل نظرية النموذج الرياضي عبئًا كبيرًا من الترميز ، و HTML ليست أفضل حاوية لها. فيما يلي ، يتم كتابة الكائنات النحوية (اللغات ، والنظريات ، والجمل) بشكل عام بأحرف رومانية أو يونانية (على سبيل المثال L ، T ، & phi) ، وكائنات نظرية المجموعات مثل الهياكل وعناصرها مكتوبة بخط مائل (أ, أ). استثناءان هما أن المتغيرات مائلة (x, ذ) وأن تسلسل العناصر مكتوب بأحرف رومانية صغيرة (أ ، ب).

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

إذا كان K هو توقيع ، فعندئذٍ أ هيكل التوقيع ك ، قل أ، يتكون من العناصر التالية:

  1. مجموعة تسمى نطاق من أ وكتب دوم (أ) يُفترض عادةً أنه غير فارغ
  2. لكل ثابت على حدة ج في K عنصر ج أ من دوم (أ)
  3. لكل رمز المسند ص من arity ن، و نعلاقة -اري ف أ على دوم (أ)
  4. لكل رمز وظيفة F من arity ن، و ن-اري وظيفة و أ من دوم (أ) إلى دوم (أ).

ال عناصر من أ هي عناصر دوم (أ). وبالمثل عدد العناصر في المجموعة أو قوة من أ هي أصل مجالها. نظرًا لأنه يمكننا استعادة التوقيع K من لغة الدرجة الأولى L التي تولدها ، يمكننا وسنشير إلى هياكل التوقيع K كـ L-الهياكل. نفكر في ج كاسم للعنصر ج أ في الهيكل أ، وكذلك مع الرموز الأخرى.

على سبيل المثال ، يشكل مجال الأعداد الحقيقية بنية ر عناصرها هي الأرقام الحقيقية ، مع التوقيع الذي يتكون من الثابت الفردي 0 لتسمية الرقم صفر ، ورمز دالة 1-ary & ناقص لسالب ، ورمزين للوظيفة 2-ary + و. للإضافة والأوقات. للوهلة الأولى يمكننا & rsquot إضافة رمز للتعبير عن 1 /x، نظرًا لأنه يجب تحديد جميع الوظائف المسماة في المجال الكامل للهيكل ، ولا يوجد رقم حقيقي مثل 1/0. لكن في الأفكار الثانية ، هذه ليست مشكلة خطيرة يضعها أي عالم رياضيات مختص الشرط & lsquox ليس صفرا و rsquo قبل القسمة على x، لذلك لا يهم أبدًا ما هي قيمة 1/0 ، ويمكننا اعتبارها 42 بدون ضرر. لكن معظم منظري النموذج غير مرتاحين لأي نوع من القسمة على الصفر ، لذلك يتمسكوا بعلامة الجمع ، والضرب ، والسالب.

إذا كانت L هي اللغة من الدرجة الأولى للتوقيع K ، فإن تعريف الحقيقة النظرية للنموذج Tarski & rsquos يخبرنا عندما تكون جملة L صحيحة في أ، وعند إحالة عناصر أ إلى المتغيرات يلبي صيغة L في أ. بدلاً من الحديث عن التخصيصات التي ترضي الصيغة ، غالبًا ما يتحدث منظرو النموذج عن مجموعة ن- مضاعفات عناصر أ هذا هو معرف بواسطة صيغة & فاي (الخامس1، & hellip،الخامسن) الاتصال هو أن ملف ن- مضاعفة (أ1، & hellip،أن) في المجموعة المحددة إذا وفقط إذا كانت المهمة تأخذ كل منها الخامسأنا ل أأنا يرضي الصيغة.

إذا كانت & phi جملة ، نكتب

ليعني أن & phi صحيحة في أ، أو بعبارة أخرى ، أ هو نموذج من & phi. & فاي (الخامس1، & hellip،الخامسن) هي صيغة ذات متغيرات حرة كما هو موضح ، نكتب

ليعني أن ن-tuple a في المجموعة المحددة بواسطة & phi. (يستخدم الإدخال في المنطق الكلاسيكي الترميز & lsquoكما & # 8872 & فاي & رسقوو ، أين س هو أي تخصيص لجميع متغيرات L يتم تخصيصه لكل متغير الخامسأنا مجانًا في & فاي أناالعنصر -th في ن- مضاعفة أ.)

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

لمواصلة مثال المجال ر من الأعداد الحقيقية: غالبًا ما يكون من غير الواضح على الإطلاق ما إذا كانت هيكلين معينين متكافئين بشكل أساسي أم لا. كان وصف Tarski & rsquos في عام 1930 من أعظم إنجازات ما قبل التاريخ لنظرية النموذج (ر) (الذي نشره كاملاً فقط بعد الحرب انظر كتابه في قائمة المراجع أدناه). هذا الوصف ضمنيًا ، من بين أشياء أخرى ، أن الهياكل تعادلها بشكل أساسي ر هي بالضبط الحقول المغلقة الحقيقية ، وهي فئة من الحقول كانت معروفة بالفعل للجبريين في حد ذاتها.

عندما يقدم علماء الرياضيات فئة من الهياكل ، فإنهم يحبون تحديد ما يعتبرونه خرائط أساسية بين هذه الهياكل. تسمى الخرائط الأساسية بين الهياكل التي لها نفس التوقيع K تماثل، على النحو التالي. أ التشابه من الهيكل أ إلى الهيكل ب هي وظيفة F من دوم (أ) إلى دوم (ب) مع الخاصية التي لكل صيغة ذرية & phi (الخامس1، & hellip،الخامسن) وأي ن- مضاعفة أ = (أ1، & hellip،أن) من عناصر أ,

أين ب (F(أ1) و hellip ،F(أن)). إذا كان لدينا & lsquo & hArr & rsquo in place of & lsquo & rArr & rsquo في الحالة المقتبسة ، فنحن نقول ذلك F هو التضمين من أ داخل ب. بما أن اللغة تتضمن = ، تضمين أ داخل ب دائمًا واحد لواحد ، على الرغم من أنه لا يلزم أن يكون في مجال ب. إذا كانت في اتجاه ، فإن الخريطة العكسية من dom (ب) إلى دوم (أ) هو أيضًا تماثل الشكل ، ويقال إن كلا من التضمين وعكسه التماثل. نقول أن هيكلين متماثل إذا كان هناك تماثل من واحد إلى آخر. تماثل الشكل هو علاقة تكافؤ في فئة جميع الهياكل ذات التوقيع الثابت K. إذا كان هيكلان متماثلان ، فإنهما يشتركان في جميع الخصائص النظرية للنموذج على وجه الخصوص وهما مكافئتان بشكل أساسي.

إذا أ و ب هي هياكل التوقيع K مع dom (أ) مجموعة فرعية من dom (ب) والتفسيرات في أ الرموز الموجودة في K هي مجرد قيود على تفسيراتها في ب، ثم نقول ذلك أ هو بنية من ب وعلى العكس من ب هو تمديد من أ. إذا علاوة على ذلك ب يحتوي على بعض العناصر غير الموجودة أنقول ذلك أ هو البنية التحتية المناسبة من ب و ب هو التمديد المناسب من أ. إذا ب هو هيكل و X هي مجموعة فرعية غير فارغة من dom (ب) ، إذن هناك بنية أساسية فريدة من نوعها أصغر من ب الذي يحتوي مجاله على كل X. ومن المعروف باسم تم إنشاء البنية التحتية لـ B بواسطة X، ونجدها عن طريق الإضافة إلى أولاً X كل العناصر ج ب أين ج هي ثوابت فردية لـ K ، ثم تغلق تحت الوظائف و ب أين F هي رموز وظيفية لـ K.

على سبيل المثال البنية التحتية للحقل ر المتولدة من الرقم 1 تتكون من 1 ، 0 (حيث يتم تسميتها بالثابت 0) ، 1 + 1 ، 1 + 1 + 1 إلخ ، & ناقص 1 ، & ناقص 2 وما إلى ذلك ، بمعنى آخر حلقة الأعداد الصحيحة. (ليست هناك حاجة للإغلاق في ظل الضرب أيضًا ، لأن مجموعة الأعداد الصحيحة مغلقة بالفعل تحت الضرب.) إذا كنا قد أدرجنا رمزًا لـ 1 /x أيضًا ، فإن البنية التحتية التي تم إنشاؤها بواسطة 1 ستكون مجالًا للأرقام المنطقية. لذا فإن فكرة البنية التحتية حساسة لاختيار التوقيع.


منطق B1.1 (2019-2020)

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

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

تدوين ومعنى واستخدام حساب التفاضل والتكامل الافتراضى. اللغة الرسمية لحساب التفاضل والتكامل: وظائف الحقيقة مرتبطة ومفصلة بشكل طبيعي من الحشو والنتيجة المنطقية. اللغة الرسمية لحساب التفاضل والتكامل الأصلي: الرضا ، والحقيقة ، والصلاحية ، والنتيجة المنطقية.

النظام الاستنتاجي لحساب الافتراض: البراهين والنظريات ، البراهين من الفرضيات ، نظرية الاستنتاج ، الصحة. أقصى مجموعات متسقة من الصيغ اكتمال إثبات بنّاء للاكتمال.

بيان نظرية السلامة والكمال لنظام استنتاجي لاشتقاق حساب التفاضل والتكامل الأصلي لنظرية الانضغاط ، تطبيقات بسيطة لنظرية الضغط.

نظام استنتاجي لإثباتات التفاضل والتكامل الأصلية ونظريات نموذج prenex. إثبات نظرية الاكتمال. وجود نماذج معدودة ، نظرية L & oumlwenheim-Skolem.

  1. R. Cori و D. Lascar ، المنطق الرياضي: دورة مع تمارين (الجزء الأول) (مطبعة جامعة أكسفورد ، 2001) ، الأقسام 1 ، 3 ، 4.
  2. A.G. Hamilton، المنطق لعلماء الرياضيات (الطبعة الثانية ، مطبعة جامعة كامبريدج ، 1988) ، ص 1-69 ، ص 73-76 (لبيان نظرية الاكتمال (الكفاية)) ، ص 99-103 (لنظرية الضغط).
  3. دبليو بي إندرتون ، مقدمة رياضية في المنطق (مطبعة أكاديمية ، 1972) ، ص 101 - 144.
  4. D. Goldrei ، حساب التفاضل والتكامل الافتراضى: نموذج للمناقشة (سبرينغر ، 2005).
  5. أ.بريستل وسي.إن.ديلزيل ، المنطق الرياضي ونظرية النموذج (سبرينغر ، 2010).

يرجى ملاحظة أن إصدارات الكتب الإلكترونية للعديد من الكتب في قوائم القراءة يمكن العثور عليها في SOLO و ORLO.


Adámek، J.، Rosický، J: فئات جيدة المظهر محليًا ويمكن الوصول إليها. رقم 189 في ملاحظات محاضرة جمعية لندن الرياضية. مطبعة جامعة كامبريدج (1994)

أحمد ت.س .: حذف أنواع الامتدادات الجبرية لمنطق الدرجة الأولى. J. أبل. المنطق غير الكلاسيكي. 15(4), 465–489 (2005)

أحمد ت.س ، أندريكا هـ. ، نيميتي الأول: حذف أنواع لأجزاء متغيرة منتهية وتمثيلات كاملة للجبر. J. سيمب. سجل. 73(1), 65–89 (2008)

أحمد ت.س ، سمير ب: نظرية أنواع الحذف لمنطق الدرجة الأولى برموز العلاقة اللانهائية. رياضيات. سجل. س. 53(6), 564–570 (2007)

Astesiano E.، Bidoit M.، Kirchner H.، Krieg-Brückner B.، Mosses P.D.، Sannella D.، Tarlecki A: CASL: لغة المواصفات الجبرية الشائعة. النظرية. حاسوب. علوم. 286(2), 153–196 (2002)

باروايز جيه: ملاحظات حول التأثير والأجزاء المعدودة. طبعت (1970)

Chang، CC، Keisler، HJ: Model Theory. شمال هولندا ، أمستردام (1990)

الكنيسة أ: صياغة النظرية البسيطة للأنواع. J. سيمب. سجل.، 5(2), 56–68 (1940)

كودسكو ، م: النظرية النموذجية لمنطق الرتبة الأعلى. أطروحة الماجستير ، Şcoala Normală Superioară Bucureşti (2007)

M. Codescu، Găină D: اكتمال بيركوف في المؤسسات. لوجيكا يونيفيرساليس 2(2), 277–309 (2008)

كوهين ، بي جي: استقلال فرضية الاستمرارية. في: وقائع الأكاديمية الوطنية للعلوم بالولايات المتحدة الأمريكية ، 50(6): 1143-1148 ، ديسمبر 1963

كوهين ، بي جي: استقلال فرضية الاستمرارية ، II. وقائع الأكاديمية الوطنية للعلوم بالولايات المتحدة الأمريكية ، 51(1): 105-110 ، يناير 1964

Diaconescu R: منطق القيد المستند إلى الفئة. التراكيب الرياضية في علوم الكمبيوتر 10(3), 373–407 (2000)

دياكونيسكو آر: منتجات Ultraproducts المستقلة عن المؤسسة. أساسيات إنفورماتيكا 55(3-4):321–348 (2003)

Diaconescu R: دليل مستقل عن مؤسسة لنظرية استيفاء كريج. ستوديا لوجيكا 77(1), 59–79 (2004)

Diaconescu R: الرسوم البيانية الأولية في المؤسسات. J. سجل. حاسوب. 14(5), 651–674 (2004)

دياكونيسكو ر: نظريات هيربراند في المؤسسات العشوائية. المشاة. عملية. بادئة رسالة. 90, 29–37 (2004)

Diaconescu R: دراسة فئوية عن محدودية المواصفات. المشاة. عملية. بادئة رسالة.، 108(2), 75–80 (2008)

دياكونيسكو ، آر: نظرية النموذج المستقل عن المؤسسة. دراسات في Universal Logic. بيركويزر (2008)

Diaconescu، R.، Futatsugi، K.L .: تقرير CafeOBJ: اللغة ، تقنيات الإثبات ، ومنهجيات المواصفات الجبرية الموجهة للكائنات ، المجلد 6 من سلسلة AMAST في الحوسبة. العالم العلمي (1998)

Diaconescu R. ، Futatsugi K: الأسس المنطقية لـ CafeOBJ. النظرية. حاسوب. علوم ، 285(2), 289–318 (2002)

Diaconescu، R.، Futatsugi، K.، Ogata، K: CafeOBJ: Logical Foundations and Methologies. أجهزة الكمبيوتر والذكاء الاصطناعي 22(3) (2003)

Goguen J.، Burstall R: المؤسسات: نظرية النموذج المجرد للمواصفات والبرمجة. J. Assoc. كمبيوت ماخ 39(1), 95–146 (1992)

Goguen J.A.، Diaconescu R: An Oxford Survey of Order Sorted Algebra. التراكيب الرياضية في علوم الكمبيوتر 4(3), 363–392 (1994)

Goguen J.A.، Meseguer J: Order-Sorted Algebra I: Equalationضم للميراث المتعدد والحمل الزائد والاستثناءات والعمليات الجزئية. النظرية. حاسوب. علوم. 105(2), 217–273 (1992)

Goguen JA، Rosu G: مؤسسة Morphisms. الجانب الرسمي. حاسوب. 13(3-5), 274–307 (2002)

جيني د. ، بيتريا م: الاكتمال عن طريق الإجبار. J. سجل. حاسوب. 20(6), 1165–1186 (2010)

Găină D. ، Popescu A: تعميم مستقل عن المؤسسة لنظرية السلسلة الأولية لتارسكي. ياء المنطق. حاسوب. 16(6), 713–735 (2006)

Găină D. ، Popescu A: دليل مؤسسي مستقل عن نظرية تناسق روبنسون. ستوديا لوجيكا 85(1), 41–73 (2007)

هنكن إل: الاكتمال في نظرية الأنواع. J. سيمب. سجل. 15(2), 81–91 (1950)

هينكين إل: تعميم لمفهوم الاتساق ω. J. سيمب. سجل. 19(3), 183–196 (1954)

كيسلر ، هـ: نظرية أنواع الإجبار والحذف. في: Morley ، M. ، (محرر) ، دراسات في نظرية النموذج ، دراسات MAA في الرياضيات ، المجلد. 8 ، ص 96 - 133 (1973)

ماك لين ، إس: فئات لعالم الرياضيات العامل. سبرينغر ، الطبعة الثانية (1998)

Meseguer ، J: المنطق العام. في المنطق الندوة 87 ، ص 275 - 329. شمال هولندا (1989)

Meseguer J.، Goguen J.A: يحل الجبر المرتب حسب الترتيب المحدد والمنشئ والتمثيل المتعدد ومشكلات الإكراه. المشاة. حاسوب. 103(1), 114–158 (1993)

Möller، B.، Tarlecki، A.، Wirsing، M: المواصفات الجبرية لجبر الرتبة الأعلى الذي يمكن الوصول إليه. في: Sannella، D.، Tarlecki، A. (eds.) ADT، Lecture notes in computer science، vol: 332 pp. 154–169. سبرينغر (1987)

Mossakowski T: ربط casl بلغات المواصفات الأخرى: مستوى المؤسسة. النظرية. حاسوب. علوم. 286(2), 367–475 (2002)

Orey S: On ω- تناسق والخصائص ذات الصلة. J. سيمب. سجل. 21(3), 246–252 (1956)

بيتريا ، م: نسخة مؤسسية من نظرية الاكتمال لجودل. في: Mossakowski، T.، Montanari، U.، Haveraaen، M.، (eds.)، CALCO Lecture Notes in Computer Science، vol. 4624 صفحة 409-424. سبرينغر (2007)

Petria M.، Diaconescu R: Abstract Beth Definition في المؤسسات. J. سيمب. منطق. 71(3), 1002–1028 (2006)

روبنسون أ: التأثير في نظرية النموذج. ندوات الرياضيات 5, 69–82 (1971)

Tarlecki A: حول وجود النماذج الحرة في المعاهد الجبرية المجردة. النظرية. حاسوب. علوم. 37, 269–304 (1985)

Tarlecki، A: أجزاء وأجزاء من نظرية المؤسسات. في Pitt ، D. ، Abramsky ، S. ، Poigné ، A. ، Rydeheard ، D. ، (محرران) ، وقائع ورشة العمل الصيفية حول نظرية الفئات وبرمجة الكمبيوتر ، ملاحظات محاضرة في علوم الكمبيوتر ، المجلد. 240 ، ص 334-360. سبرينغر (1986)

Tarlecki A: أشباه الأصناف في المعاهد الجبرية المجردة. J. كومبوت. النظام. علوم. 33(3), 333–360 (1986)

Tarlecki، A: التنقل بين الأنظمة المنطقية. في الاتجاهات الحديثة في مواصفات نوع البيانات ، ص 478-502. سبرينغر (1998)


كتاب مدرسي عبر الإنترنت للمنطق الأساسي والمتوسط

لتسهيل التدوين ، نبدأ بتقديم بعض الاختصارات.

افترض أن t مصطلح له متغيرات بين u0 ، & # 8230 ، شن -1.

قد نكتب t (u0 ، & # 8230 ، شن -1 ) أو t (u & # 773) للتأكيد على ذلك.

افترض أن & phi هي صيغة بها متغيرات مجانية بين u0 ، & # 8230 ، شن -1.

قد نكتب & phi (u0 ، & # 8230 ، شن -1 ) أو & phi (u & # 773) للتأكيد على ذلك.

أيضًا ، إذا كان لدينا نموذج A و x0 ، & # 8230 ، سن -1 & في | A | ، ثم يمكننا الكتابة

في بعض الأحيان ، إذا كنا نعمل باستخدام u & # 773 ثابتًا ، فقد نختصر هذا أيضًا إلى فقط

(نحتاج إلى كل من u & # 773 و x & # 773 لمعرفة الثابت الذي يتم استبداله بأي متغير.)

باستخدام هذه الاختصارات ، يمكننا إعادة كتابة النتيجة من التمرين 3.5 على النحو التالي.

Lemma 4.1.1 تحديث

Let & pi: A & asymp B يكونان تماثلًا بين الهياكل.

بعد ذلك ، لكل صيغة & phi ، إذا كانت & phi بها متغيرات مجانية u0، & # 8230 ، شن -1,

الطريقة المعتادة للتعبير عن استنتاج Lemma 4.1 هي القول بأن & pi هو التضمين الأولي من A إلى B. وبالتالي فإن كل تماثل هو تضمين أولي. العكس خاطئ لأن حفلات الزفاف الأولية لا يجب أن تكون تخوفات.

والقسم 4.1 Downward L & oumlwenheim-Skolem

لقد رأينا بالفعل طريقتين يمكن أن ترتبط بهما الهياكل. في نهاية إثبات نظرية الوجود النموذجية 3.14 ، أخذنا اختزال بنية في لغة موسعة للحصول على بنية في اللغة الأصلية. في تمارين الفصل 3 ، حددنا التماثل بين الهياكل وشاهدنا حالات وعواقب مختلفة. هنا طريقة أخرى لمقارنة الهياكل.

  • | أ | & مجموعة فرعية | ب |
  • ج أ = ج ب لكل رمز ثابت ج
  • F A = ​​F B & # x21BE | أ | n لكل رمز دالة n-ary F
  • R A = R B & cap | أ | n لكل رمز دالة n-ary R

(لا يوجد خطر من الخلط بين هذا وبين "A هي مجموعة فرعية من B" لأنه من المفترض أن تكون A و B هياكل.)

ج ب & في | أ | لكل رمز ثابت ج

F B (x & # 773) & في | أ | لكل رمز دالة n-ary F وكل x & # 773 & in | أ | ن

على وجه الخصوص ، ليست كل مجموعة فرعية من | ب | هو كون البنية التحتية لـ B.

Lemma 4.2.1 تحديث

دع B يكون بنية لا نهائية في لغة معدودة.

لنفترض أن X مجموعة فرعية قابلة للعد من | ب |.

ثم توجد بنية فرعية قابلة للعد A من B مثل X & subseteq | أ |.

إثبات Lemma 4.2

تحديد تسلسل متزايد للمجموعات

من خلال الاستقراء على i & in & omega ، نرى أن Zأنا هي مجموعة فرعية معدودة من | ب |.

إذن Z هي مجموعة فرعية معدودة من B.

و c B & in Z0 & subseteq Z لكل رمز ثابت ج.

أيضًا ، لكل رمز دالة n-ary F وكل x & # 773 & في Z n ، يوجد i & in & omega مثل x & # 773 & in Zأنا n و F B (x & # 773) & في Zأنا + 1 & مجموعة فرعية Z.

لذلك ، F B & # x21BE Z n هي دالة n-ary على Z.

وهكذا نحصل على بنية تحتية معدودة أ من ب عن طريق الإعداد

ج أ = ج ب لكل رمز ثابت

F A = ​​F B & # x21BE Z n لكل رمز دالة n-ary F

R A = R B & cap Z n لكل رمز دالة n-ary R

Lemma 4.3.2 تحديث

دع & phi تكون صيغة خالية من المحددات الكمية.

لنفترض أن u & # 773 عبارة عن مجموعة من المتغيرات المجانية لـ & phi.

رسم تخطيطي لـ Lemma 4.3

أولاً ، ندعي أنه لكل مصطلح t (u & # 773) مع n متغيرات مجانية ، إذا كانت x & # 773 & in | أ | n ، ثم t (u & # 773 / x & # 773) A = t (u & # 773 / x & # 773) ب.

إثبات المطالبة هو استقراء سهل باستخدام افتراض أن A هو بنية فرعية لـ B.

باستخدام هذا الافتراض مرة أخرى ، نرى أن Lemma 4.3 ينطبق على الصيغ الذرية.

الآن نكمل إثبات Lemma 4.3 عن طريق الاستقراء.

حالات الاقتران والانفصال والحالات الشرطية والمشروطة تستخدم فرضية الاستقراء وهي تافهة.

لا توجد حالة محددة الكمية.

بشكل عام ، لا يمكننا أن نتوقع أن نفعل ما هو أفضل من Lemma 4.3. على سبيل المثال ، ضع في اعتبارك الهياكل

A = (& # x211A، 0، 1، +، & times، A، d A، F A، G A، R A)

B = (& # x211D، 0، 1، +، & times، B، d B، F B، G B، R B)

ثم A هي بنية أساسية لـ B.

ومع ذلك ، لأن الجذر التربيعي للعدد 2 غير منطقي ،

ولكن هناك مواقف خاصة يمكننا فيها أن نفعل ما هو أفضل من Lemma 4.3.

نقول أن أ هو ابتدائي البنية التحتية لـ B واكتب A & # x227C B iff

لكل صيغة & phi مع n متغيرات مجانية u & # 773 وكل x & # 773 & in | أ | ن ،

اختبار Tarski-Vaught 4.4.1

لنفترض أن A يكون بنية أساسية لـ B.

افترض أنه لكل صيغة و psi مع المتغيرات المجانية u & # 773 و v ، وكل x & # 773 من | أ | ،

إذن ، A هي بنية أساسية أولية لـ B.

إثبات النظرية 4.4

يقول Lemma 4.3 (*) يحمل لـ & phi وهي خالية من القيم الكمية.

تشير فرضية الاستقراء بسهولة إلى (*) يحمل لـ & phi التي هي نفي ، أو اقتران ، أو مفارقات ، أو شرطية أو ثنائية الشرط.

الآن ضع في اعتبارك الحالة التي يكون فيها & phi موجودًا v & psi (u & # 773، v).

افترض أولاً أن B & # 8872 & phi (u & # 773 / x & # 773) حيث x & # 773 من | أ |.

من خلال افتراض النظرية 4.4 ، يوجد y & في | أ | مثل B & # 8872 & psi (u & # 773 / x & # 773 ، v / y).

من خلال فرضية الاستقراء ، A & # 8872 & psi (u & # 773 / x & # 773 ، v / y).

افترض الآن أن A & # 8872 & phi (u & # 773 / x & # 773).

ثم يوجد y & في | أ | مثل أن A & # 8872 & psi (u & # 773 / x & # 773 ، y).

من خلال فرضية الاستقراء ، B & # 8872 & psi (u & # 773 / x & # 773 ، y).

الحالة الأخيرة التي يكون فيها & phi هو & forall v & psi (u & # 773، v) يتبع ما أثبتناه بالفعل.

Downward L & oumlwenheim-Skolem Theorem 4.5

دع B يكون بنية في لغة معدودة.

لنفترض أن X مجموعة فرعية قابلة للعد من | ب |.

ثم توجد بنية أساسية أولية قابلة للعداء A من B مثل X & subseteq | أ |.

إثبات النظرية 4.5

قد نفترض أن B لا نهائية.

لكل صيغة و phi (u & # 773 ، v) مع n + 1 متغيرات مجانية ، اختر دالة f& فاي : | ب | n & rarr | ب | لهذا السبب،

(نظرًا لأن | B | غير فارغ ، فيمكننا إعطاء f& فاي (x & # 773) بعض القيم الافتراضية بخلاف ذلك.)

قم بتوسيع اللغة لتشمل رموز دالة n-ary الجديدة F& فاي.

قم بتوسيع B إلى البنية B * التي تفسر F& فاي مثل و& فاي.

بواسطة Lemma 4.2 ، يحتوي B * على بنية فرعية قابلة للعد * A * مثل X & subseteq | أ * |.

لنفترض أن A هو اختزال A * للغة B.

من الواضح أن A هي بنية فرعية لـ B.

من الواضح أيضًا أن A يجتاز اختبار Tarski-Vaught لكونه بنية أساسية أولية لـ B.

& القسم 4.2 Upward L & oumlwenheim-Skolem

كالعادة ، ندع جx يكون رمزًا ثابتًا جديدًا لكل x & في | أ |.

قم بتوسيع أ إلى هيكل د = (أ ، س)& في | أ | أن يفسر جx بواسطة x.

بمعنى آخر ، D هو توسع A مع cx D = x لكل x & في | أ |.

بواسطة الرسم التخطيطي الأولي من أ نعني الرسم البياني النظري (أ) = <& phi & mid D & # 8872 & phi>.

من الواضح أن D & # 8872 مخطط (أ).

في اللغة الموسعة ، يعتبر الرسم التخطيطي (أ) نظرية كاملة ومغلق تحت الخصم.

Lemma 4.6.0 تحديث

لنفترض أن A يكون هيكلًا و D = (A ، x)& في | أ |.

افترض أن E نموذج للشكل التخطيطي (أ).

لنفترض أن B هي اختزال E إلى لغة A.

ثم الخريطة & pi: x & rarr cx E هو تماثل من A إلى بنية أساسية أولية A * من B.

إثبات Lemma 4.6

دع د يكون رمزًا ثابتًا في اللغة الموسعة.

إثبات المطالبة أ

ثم الجملة د & تقريبا جx ينتمي إلى الرسم التخطيطي (أ).

وهكذا د E = جx E = & pi (x) = & pi (d D).

دع F تكون دالة n-ary عشوائية و x & # 773 & in | أ | ن .

قد نحدد البنية التحتية D * من E عن طريق تحديد:

c D * = c E لكل رمز ثابت c في اللغة الموسعة.

F D * = F D * & # x21BE | ركض (& بي) | n لكل رمز دالة n-ary F.

R D * = R D * & cap | ركض (& بي) | n لكل رمز علاقة n-ary R.

فورًا من المطالبتين A و B.

دع x و y & in | أ | مثل أن x & ne y.

لذا فإن الجملة جx & # x0338 جذ ينتمي إلى الرسم التخطيطي (أ).

لنفترض أن R دالة n-ary عشوائية و x & # 773 & in | أ | ن .

على غرار البراهين أعلاه.

دع A * يكون اختزال D * للغة A.

& pi هو انحراف من | أ | = | د | إلى | أ * | = | أ * | بالمطالبة د.

& pi يحافظ على الثوابت والوظائف والعلاقات من خلال المطالبات A و B و E.

دع & phi (u & # 773) تكون صيغة بلغة A.

على وجه الخصوص ، يعد & pi تضمينًا أوليًا من A إلى B.

الشرط 1 هو اختصار للشرط 2.

الشرط 5 هو اختصار للشرط 4.

الشرط 2 يحمل iff الجملة & phi (u0 / جx0 ، & # 8230 ، شن -1 / جxن -1 ) ينتمي إلى الرسم التخطيطي (أ).

وينطبق الشيء نفسه على الشرط 3 ، لذا فهو معادل للشرط 2.

يحتاج معنى الشرط الرابع إلى بعض التفصيل.

تخيل أن لدينا x واحدًا فقط بدلاً من n-tuple x & # 773.

والذي يتم تفسيره على أنه & pi (x) في (E، & pi (x)).

بمعنى آخر ، ج& بي (x) (E ، & pi (x)) = & pi (x)

عن طريق الاستبدال Lemma 3.2 ، نستنتج أن (E، & pi (x)) & # 8872 & phi (u / cx ) & harr & phi (u / c& بي (x) ) .

لاحظ أن & phi (u / cx ) هي جملة بلغة E.

أيضا أن & فاي (ش / ج& بي (x) ) هي جملة بلغة (B، & pi (x)).

وكلاهما E و (B، & pi (x)) عبارة عن اختزال لـ (E، & pi (x)).

يوضح هذا أن الشرطين 3 و 4 متكافئان عندما يكون n = 1.

بالنسبة إلى n> 1 ، قم بإجراء التغييرات الواضحة.

دع & phi (u & # 773) تكون صيغة بلغة A * ، وهي لغة A.

iff (بالمطالبة F و Lemma 4.1)

تجدر الإشارة إلى أنه في إثبات Lemma 4.6 ، كان بإمكاننا إثبات المطالبة G أولاً ، ثم استخدامها لإثبات المطالبات A و B و D و E من خلال النظر في الصيغ الأربع:

Lemma 4.7.1 تحديث

كل بنية لا نهائية لها امتداد أولي مناسب.

إثبات Lemma 4.7

ندعي أن وسيغما لديها نموذج.

بواسطة Compactness Theorem 3.16 ، يكفي إظهار أن كل نظرية فرعية محدودة لـ & Sigma لها نموذج.

منذ | أ | لانهائية ، يوجد y & في | أ | مثل y & ne xأنا لجميع i * & # x227C B حيث B هو اختزال E إلى لغة A و & pi: x & map cx ه.

نظرًا لأن E هو نموذج لـ & Sigma ، فلدينا ذلك d E & T.

على وجه الخصوص ، T غير فارغ.

يمكننا "استبدال" كل y & T بعلامة x مميزة لا تنتمي إلى | أ |.

بتعبير أدق ، هناك مجموعة S منفصلة عن | أ | جنبًا إلى جنب مع الانحراف f: S & rarr T.

بمعنى آخر ، & sigma (x) = & pi (x) if x & in | أ | و & سيجما (x) = f (x) إذا كانت x & في S.

ثم & سيجما: | أ | & كأس S & rarr | ب | هو انحياز و & سيجما & # x21BE | أ | = & بي.

بعد ذلك نحدد البنية B 'مثل that & sigma: B' & asymp B.

هناك طريقة واحدة واضحة للقيام بذلك وهي تعمل!

ضع في اعتبارك أي x & # 773 & in | أ | n والصيغة & phi مع المتغيرات المجانية n.

يشير التكافؤ بين السطور الأولى والأخيرة من الحساب أعلاه بشكل مباشر إلى أن A هي بنية أساسية أولية لـ B '.

Upward L & oumlwenheim-Skolem 4.8.1 تحديث

كل بنية لا نهائية لها امتداد أولي غير معدود.

إثبات النظرية 4.8

ثم كل مجموعة فرعية محدودة من & سيجما لها نموذج.

لرؤية هذا ، ضع في اعتبارك أي x & # 773 & in | أ | م والثوابت الجديدة د0 ، & # 8230 ، دن -1.

لنفترض أن B هو امتداد (A، x & # 773) الذي يفسر دي مثل ذي لجميع ي أ

أين ك هو حجم S.ن.

قائمة تن بترتيب تصاعدي وفقًا لـ R B as

منذ فن هو تماثل ، يجب أن يكون ذأنا = ون (xأنا ) لجميع i A xأنا للجميع أنا ب ذأنا للجميع أنا أ أن للجميع أنا ب ب للجميع أنا أ أن R A xي لبعض i B b R B yي.

اختر أيًا من هذا النوع b واجعل fن + 1 ( أن ) = ب.

لهذا ، نقوم بإدراج S.ن & كوب <أن > بترتيب تصاعدي وفقًا لـ R A as

و تن & كوب <ب> بترتيب تصاعدي حسب R B as

حالة 1. بن R B ص * أنا للجميع أنا أ س * أنا للجميع أنا -1 (بن ) = أ.

الحالة 2. ذ * أنا R ب بن للجميع أنا * أنا R A a للجميع i -1 (bن ) = أ.

الحالة 3. ذ * أنا R ب بن R B ص * ي بالنسبة للبعض * أنا R A a R A x * ي.

اختر أيًا من هذا وقم بعمل fن + 1 -1 (بن ) = أ.

لإنهاء البناء العودي ، ضع

لقد حددنا بالفعل قيم fن + 1 على هذه المجموعات بطريقة تحافظ على النظام. وقمنا بتعريف fن + 1 لتمديد ون.

الآن ننتهي من إثبات النظرية.

بوضوح ، | أ | هو اتحاد المجموعات S.ن لـ n -1 (بن ) و k = max (m، n) ثم

لمعرفة أن & pi هو الحفاظ على النظام ، لاحظ أنه إذا كان k = max (m ، n) ، إذن

نظرية وسيغما قاطعة إلى حد كبير iff جميع أزواج النماذج المعدودة من & سيجما متشابهة.

تعد DLO قاطعة بشكل معدود بواسطة Theorem 4.9.

هذا لا يمتد إلى نماذج غير معدودة من DLO.

على سبيل المثال ، على الرغم من وجود انحراف بين & # x211D و ، فإن الهياكل (& # x211D ، * من A و B * من B.

حسب النظرية 4.9 ، A * و B * متماثلان.

بواسطة Lemma 4.1 ، يلبي A * و B * نفس الجمل بالضبط ، وهو تناقض.

نظرية 4.11

لنفترض أن & phi صيغة تكون متغيراتها الحرة من بين u & # 773 = (u0 ، & # 8230 ، شن -1 ).

ثم توجد صيغة خالية من المحددات الكمية و psi من هذا القبيل

إثبات النظرية 4.11

لـ x & # 773 & in | أ | n ، حدد النوع (x & # 773) ليكون مجموعة الصيغ & psi مثل ذلك

  • & psi إما ذري أو نفي ذري ،
  • المتغيرات المجانية لـ & psi هي من بين u & # 773 و
  • A & # 8872 & psi (u & # 773 / x & # 773).

ثم اكتب (x & # 773) محددًا لكل x & # 773 & in | أ | ن .

الاتجاه إلى الأمام واضح. يستخدم الاتجاه العكسي الحقيقة أ ، الجزء 3.

تشير النظرية 4.10 ونظرية الاكتمال 3.15 إلى أن كل جملة يتم استيفائها بواسطة A يتم استيفائها من خلال كل نموذج من DLO ، وبالتالي يمكن استنتاجها من DLO.

يقال أن النظرية تعترف القضاء على الكمي إذا كانت كل صيغة مكافئة بشكل مثبت لصيغة خالية من المحددات الكمية.

وهكذا يعترف DLO بإزالة المحدد الكمي بواسطة نظرية 4.11.

ملكية الحد الأعلى الأدنى

قلنا في بداية هذا القسم أن & # x211A قابل للعد بينما & # x211D غير معدود ، لذلك لا يوجد انحياز بينهما.

سبب آخر هو أن (& # x211A، 2 2 in & # x211D

ضع في اعتبارك أمرًا خطيًا تعسفيًا A.

إذا كانت & مجموعة فرعية | أ | و y & في | أ | ، إذن y هو الحد الاعلى لـ S في A iff x R A y أو x = y لكل x & in | أ |.

ذ هو أقل حد أعلى لـ S iff y هو الحد الأعلى لـ S و y R A z أو y = z لكل حد أعلى لـ S.

A لديه أقل خاصية للحد الأعلى iff لكل S & مجموعة فرعية غير فارغة | A | ، إذا كان S له حد أعلى ، فإن S له حد أعلى أقل.

إنها حقيقة أساسية حول (& # x211D ، B y R B z.

افترض أن B لديها خاصية الحد الأعلى الأقل.

دع & pi يكون تماثلًا من A إلى (& # x211A، B y>)

حيث يتم أخذ الحد الأعلى في (& # x211D، A.

أيضا ، نحن نكتب جx R d بدلاً من R (cx ، د ).

كما هو الحال في إثبات Lemma 4.7 ، نجد E & # 8872 & Sigma ونجعل B هو اختصار E إلى لغة A.

أيضًا ، نحدد & pi: x & map cx E وابحث عن A * & # x227C B مثل أن & pi: A & asymp A *.

لدينا ذلك لكل صيغة & phi (u & # 773) بلغة A ،

نظرًا لأن A * يتشابه مع A ، فإننا نعتبر معيار A * أيضًا.

على الرغم من أن B ترضي جميع الجمل نفسها مثل A * ، إلا أنها لا تتشابه مع A ، لذلك نعتقد أن B على أنها غير قياسية.

للبدء في معرفة مدى اختلاف B عن A ، تذكر أن B لديها عضو d E أكبر من كل عضو من A *.

حدد المنتهية (B) لتكون مجموعة y & في B بحيث يكون هناك x و z & في A * مع x B y B z.

أيضا ، حدد اللانهائي (ب) = | ب | - منتهي (ب).

ثم d E & Infinite (B) لأن E & # 8872 & Sigma.

دعونا نسيء استخدام التدوين بافتراض أن 0 و 1 هما رمزان ثابتان يفسره A على أنهما الرقمان صفر وواحد على التوالي.

إذن 0 A * = 0 B = & pi (0 A) و 1 A * = 1 B = & pi (1 A).

موجب (A *) ومجموعة فرعية موجبة (B) ولكن d E & في موجب (B) - موجب (A *).

أسيء استخدام التدوين بافتراض أن A لديه رموز وظيفية ثنائية + ، - ، & & & قسمة التي يفسرها A على أنها الجمع والطرح والضرب والقسمة. أيضًا ، يحتوي A على رمز وظائف أحادي مكتوب باستخدام الترميز الغريب | & sdot | التي يفسرها A على أنها قيمة مطلقة.

(نجعل بعض الاصطلاحات المعقولة حول قيمة x ونقسم A 0 A بحيث تكون & divide A دالة ثنائية إجمالية.)

يلبي الآن A الإصدارات من الدرجة الأولى من الجمل "إذا كان 1 * و B كذلك.

على وجه الخصوص ، نرى ذلك إذا سمحنا بذلك

لـ & دلتا وفي | ب | ، نقول أن & دلتا هي متناهي الصغر iff 0 ب ب | & دلتا | B B x لكل x & في موجب (A *).

(هنا | & دلتا | ب هي القيمة المطلقة لـ & دلتا المحسوبة في ب)

أعلاه رأينا أن & epsilon هو عدد متناهٍ في الصغر موجبًا من B لأنه إيجابي ولكنه أقل من كل عضو إيجابي في | أ * |.

في الواقع ، أظهرنا أن مقلوب أي عضو لانهائي موجب من B هو عضو موجب متناهي الصغر من B.

ربما تكون قد سمعت أو رأيت كلمة "متناهية الصغر" المستخدمة في دورة حساب التفاضل والتكامل الخاصة بك ، لكن من شبه المؤكد أن المعلم أو الكتاب المدرسي لم يبرر استخدامها بالمنطق! في الواقع ، قدم جوتفريد فيلهلم ليبنيز اللامتناهيات في الصغر بنوع من وصفة كتاب الطبخ لكيفية استخدامها في الحسابات. اكتشف إسحاق نيوتن حسابًا مشابهًا في نفس الوقت تقريبًا. تم استخدام أساليبهم لعمل تنبؤات صحيحة حول الفيزياء وعلم الفلك ولكنها كانت مثيرة للجدل للغاية. بعد كل شيء ، لا توجد أرقام حقيقية أكبر من الصفر ولكنها أصغر من كل رقم حقيقي موجب! بعد حوالي أربعمائة عام ، اكتشف أبراهام روبنسون طريقة التفكير هذه في اللامتناهيات في الصغر كأرقام حقيقية غير قياسية واستخدمها لشرح سبب إمكانية استخدام الحسابات التي تتضمن اللامتناهيات في الصغر لإصدار بيانات دقيقة حول الأعداد الحقيقية. يتلخص كل شيء في & pi: A & asymp A * & # x227C B.


اختبار Vaught

يعد اختبار Vaught اختبارًا مهمًا لنظرية Downward Lowenheim- Skolem Theorem. نحتاج أولاً إلى إعطاء تعريف البنية التحتية والبنية التحتية الأولية.

تعريف

تعريف

دعونا نكون اثنين إل-الهياكل. ثم ، هو ملف ابتدائي بنية من ، ونحن نكتب ، إذا كان لدينا ولكل صيغة iff .

نحن الآن جاهزون لإثبات وإثبات اختبار Vaught.

Lemma (اختبار Vaught)

دعونا نكون اثنين إل-هياكل من هذا القبيل. إذن ، هي بنية أساسية أولية لـ iff لجميع الصيغ ، إذا ، أين ، ثم هناك مثل هذا.

دليل

نفترض ذلك أولاً. ثم ، يعني ذلك ، من خلال تعريف البنى التحتية الأولية. ثم يوجد مثل هذا. ثم ، باستخدام التعريف مرة أخرى ، لدينا ذلك.

على العكس من ذلك ، فإن الدليل يذهب عن طريق الاستقراء على مدى تعقيد. هذا صحيح بالنسبة للصيغ الخالية من محددات الكم ، لأنه في هذه الحالة ، لدينا هذا يعني ضمنيًا iff . يمكن إثبات ذلك باستخدام الاستقراء على مدى تعقيد الصيغة.

افترض الآن أن النتيجة صحيحة لـ و. بعد ذلك ، من السهل التحقق من صحة النظرية لـ و.

يترك . إذا كان هناك مثل هذا. من خلال فرضية الاستقراء ، هذا يعني أن هناك مثل هذا. هكذا، .

على العكس من ذلك ، إذا ، باستخدام الافتراض ، يوجد مثل هذا. ثم يوجد مثل هذا. هكذا، . هذا يكمل الدليل.


تقريب معدود ونظريات Löwenheim-Skolem



يستخدم هذا الموقع ملفات تعريف الارتباط و Google Analytics (راجع الشروط والأحكام الخاصة بنا للحصول على التفاصيل المتعلقة بآثار الخصوصية).

يخضع استخدام هذا الموقع للشروط والأحكام.
جميع الحقوق محفوظة لمؤسسة PhilPapers

تم إنشاء الصفحة في الأحد 4 يوليو 16:12:10 2021 على philpapers-web-75c4f97565-gk4zj معلومات التصحيح

إحصائيات ذاكرة التخزين المؤقت: ضرب = 7596 ، ملكة جمال = 7749 ، حفظ =
المعالج التلقائي: 580 مللي ثانية
المكون المسمى: 566 مللي ثانية
الإدخال: 565 مللي ثانية
المدخلات المتشابهة: 270 مللي ثانية
entry_basics: 102 مللي ثانية
رأس الإدخال: 90 مللي ثانية
القائمة: 88 مللي ثانية
الاستشهادات - المراجع: 82 مللي ثانية
الاستشهادات - الاستشهادات: 55 مللي ثانية
entry_stats: 16 مللي ثانية
get_entry: 9 مللي ثانية
الإعداد المسبق: 9 مللي ثانية
روابط الدخول: 8 مللي ثانية
دخول القطط: 8 مللي ثانية
جانب الدخول: 4 مللي ثانية
entry_chapters: 2 مللي ثانية
حفظ كائن ذاكرة التخزين المؤقت: 2 مللي ثانية
سجل الكتابة: 1 مللي ثانية
استرداد كائن ذاكرة التخزين المؤقت: 1 مللي ثانية
entry_stats_query: 1 مللي ثانية
عارض الحرف الأول: 0 مللي ثانية
الإعداد: 0 مللي ثانية
المصادقة: 0 مللي ثانية
أزرار الدخول: 0 مللي ثانية
stat_db: 0 مللي ثانية


3.4: الهياكل الأساسية ونظريات Löwenheim-Skolem - الرياضيات

ملاحظات محاضرة لدورة الدراسات العليا التمهيدية (تحت)

  • مقدمة
  • المقدمات والتدوين
    • الهياكل
    • مجموعات
    • مصطلحات
    • الهياكل
    • الصيغ
    • بعد المزيد من التدوين
    • عواقب منطقية
    • التكافؤ الأولي
    • حفلات الزفاف والتشابهات
    • هياكل حاصل
    • الاكتمال
    • اختبار Tarski-Vaught
    • أسفل Löwenheim-Skolem
    • السلاسل الابتدائية
    • المرشحات والمرشحات الفائقة
    • المنتجات المباشرة
    • نظرية Łoś
    • الضغط عبر النحو
    • الاكتناز عبر المنتجات الفائقة
    • صاعد Löwenheim-Skolem
    • البديهية المحدودة
    • نصف مشابك وفلاتر
    • المشابك التوزيعية والمرشحات الأولية
    • أنواع كمرشحات
    • التشكل
    • أوامر خطية كثيفة
    • الرسوم البيانية العشوائية
    • ملاحظات ومراجع
    • نماذج غنية.
    • نظرية النماذج الغنية وإلغاء المحدد الكمي
    • ضعف مفاهيم الشمولية والتجانس
    • خاصية الدمج
    • مجموعات أبيليان
    • مجموعات أبيليان خالية من الالتواء
    • مجموعات أبيليان القابلة للقسمة
    • حلقات تبادلية
    • المجالات المتكاملة
    • الحقول المغلقة جبريا
    • هلبرت في Nullstellensatz
    • الهياكل المشبعة
    • هياكل متجانسة
    • نموذج الوحش
    • ليندون روبنسون ليما
    • القضاء على المحدد الكمي ذهابًا وإيابًا
    • اكتمال النموذج
    • العناصر الجبرية والمحددة
    • نظريات الحد الأدنى بقوة
    • الاستقلال والبعد
    • نظرية أنواع الحذف
    • النماذج الأولية والذرية
    • صفة معدودة
    • نظريات صغيرة
    • نسخة لعبة من نظرية Zil'ber
    • ملاحظات ومراجع
    • العديد من الهياكل المصنفة
    • توسيع مكافئ
    • الإغلاق المحدد في توسيع eq
    • الإغلاق الجبري في توسيع eq
    • القضاء على التخيلات
    • التخيلات: القصة الحقيقية
    • القضاء الموحد على التخيلات
    • مجموعات وأنواع ثابتة
    • الثبات من منظور مزدوج
    • ورثة ورثة
    • متواليات مورلي و indiscernibles
    • نظرية رامسي من متواليات كوهير
    • نظرية Ehrenfeucht-Mostowski
    • مدارات غير كافية في شبه مجموعات
    • نظرية هندمان
    • نظرية هالز-جيويت
    • ملاحظات ومراجع
    • التوسعات
    • أنواع لاسكار القوية
    • الرسم البياني لاسكار ونظرية نيولسكي
    • أنواع كيم بيلاي
    • ملاحظات ومراجع
    • مجموعات تقريبية
    • السلالم والتعريف
    • نظريات مستقرة
    • الاستقرار وعدد الأنواع
    • البعد Vapnik-Chervonenkis
    • تعريفات صادقة

    & # 8220 لماذا الضغط؟ & # 8221

    ملاحظات من الهامش ، وهي نشرة CMS Studc التي تصدر مرتين سنويًا والتي تعرض كتابة الطلاب لجمهور رياضي عام ، وقد وفرت لعدة سنوات منصة لموضوعات من تحليل فورييه عالي المستوى إلى مقابلات عمل تتبع مدة الحيازة. نحن متحمسون لتقديم هذا المنشور الأول على الملاحظات من مدونة الهامش ، والتي ستكمل ولكنها لن تحل محل المنشور نصف السنوي المطبوع. ندعو الطلبات على مدار العام على [email protected]

    & # 8220 لماذا الضغط؟ & # 8221

    تود شميد

    مع عواقب مثل نظرية Upward Löwenheim-Skolem ، فإن نظرية الضغط هي واحدة من أكثر النتائج الأساسية في دراسة منطق الدرجة الأولى. من الشائع أن ترى فقط برهانًا نحويًا على غرار Henkin أو إثبات منتج فائق وضعه على السندان للاكتناز من الدرجة الأولى. بغض النظر عن توضيح هذه البراهين ، لا يوضح أي منهما الصورة الطوبولوجية لما تمثله النظرية. كما قد يتخيل المرء ، هذه الصورة هي المكان الذي اكتسبت فيه النظرية اسمها.

    بعض التوضيحات قبل أن نبدأ: نحدد /> & # 8211نظرية لتكون مجموعة من الجمل المنطقية من الدرجة الأولى مكتوبة باللغة /> والتي يتم إغلاقها بموجب نتيجة منطقية. على سبيل المثال ، تفرد مجموعة معكوس نظري

    هي جملة في - نظرية المجموعات لأنها تنبع من بديهيات الجماعة. ان -نظرية يسمى ثابتة إذا لا تنتمي إلى متي ينتمي إلى . لاحظ أنني اخترت عدم التمييز بين جملتين متكافئتين منطقيًا ، وأن & # 8220iff & # 8221 يجب أن يقرأ & # 8220if وفقط إذا. & # 8221

    نظرية الضغط. إصلاح لغة الرموز ، والسماح فاصوليا -نظرية. ثم متسق إذا كان كل مجموعة فرعية محدودة من يتسق.

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

    تعريف. ان -نظرية يكون اكتمال إذا كان لأي -جملة او حكم على ، إما أو .

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

    (1) كل (متسقة) /> - نظرية موجودة في نظرية كاملة (ومتسقة) /> ،

    (2) أي تقاطع بين (ثابت) /> - النظريات هي أيضًا (متسقة) /> - نظرية ، و

    (3) يتم تحديد النظرية بدقة من خلال مجموعة كاملة /> - النظريات التي تحتوي عليها.

    على وجه الخصوص ، (3) يحمل الجمل المفردة.

    سأشير إلى مجموعة كاملة ومتسقة -نظريات مع . نحدد طوبولوجيا على كالتالي: لكل -جملة او حكم على ، يترك تشير إلى جمع - النظريات التي تحتوي على . ثم

    هو أساس لطوبولوجيا تسمى طوبولوجيا الحجر على (سميت على اسم عالم الرياضيات إم إتش ستون). لترى أن هذا صحيح ، لاحظ ذلك ، الذي - التي ، وذلك . النظرية التالية هي بالضبط العلاقة بين الاكتناز الطوبولوجي والمنطقي.

    ليما. مجموعة فرعية أغلفة iff غير متسق.

    نظرية. يكون مضغوطًا إذا كانت نظرية الانضغاط تحمل.

    دليل. افترض أن نظرية الانضغاط صحيحة ، ودع كن مجموعة من الذي يغطي . كل عنصر من عناصر من الشكل ، حتى نتمكن من تكوين مجموعة خارج ال -جمل . عن طريق اللمة ، هي مجموعة غير متسقة من الجمل ، لذلك تخبرنا نظرية الضغط أن هناك مجموعة فرعية محدودة من وهو أمر غير متسق. لقد تركنا مع مجموعة فرعية محدودة من الذي يغطي . تم اختياره بشكل تعسفي ، لذلك يجب أن تكون مضغوطة.

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

    ما يدهشني في الرسم التوضيحي أعلاه هو أنه يقترب من التناسق في منطق الدرجة الأولى من منظور طوبولوجي بحت. يمكن العثور على مزيد من الاستفسارات في هذا الاتجاه في [2] و [3] ، وإثبات ذلك مضغوط يمكن العثور عليها في مكان ما في [1].

    فهرس.

    [1] وجهة نظر طوبولوجية للمنطق ونظرية الانضغاط (2016). تي شميد. نهاية لهذه الغاية.

    [2] المرشحات الفائقة ، والمنتجات الفائقة ، ونظرية الضغط (2009). كايسيدو. نهاية لهذه الغاية.

    [3] ملاحظات حول المرشحات الفائقة. كروكمان. نهاية لهذه الغاية.

    تود شميد طالب جامعي في جامعة فيكتوريا. إنه يحب المشي لمسافات طويلة على الشاطئ ، والتداخل بين الهندسة والمنطق ، والأفلام الاسكندنافية الغريبة. من بين الاقتباسات المفضلة لديه هذا المقتبس من سيزار فاليجو: & # 8220 ، كن محبوبًا لمن يجلس. & # 8221


    شاهد الفيديو: رياضيات الشهادة السودانية 2020. المشتقات العليا. أ. مأمون الطماس (شهر اكتوبر 2021).