19063

2134 دكتري

دكتري

منطق رياضي

اصفهان : دانشگاه صنعتي اصفهان

1402

هشت، 113ص.

1402/08/30

كتابنامه

رياضي محض

رياضي

1402/09/11

2966547

در اين رساله ما تصميم‌پذيري چهار ساختار مختلف را با استفاده از روش‌هاي متفاوت نظريهٔ مُدلي ثابت كرده‌ايم. ابتدا براي ساختار (Z,+,0,1,lfloor varphi.x rfloor)، كه در آن varphi همان نسبت طلايي است، حذف‌سور ثابت كرده و تصميم‌پذيري اين ساختار را به‌عنوان نتيجه‌اي از حذف‌سور بيان كرده‌ايم. سپس به اين ساختار ترتيب را افزوده‌ايم و با افزودن محمول‌هايي به ساختار قبلي، ثابت كرده‌ايم كه اين ساختار جديد حذف‌سور مي‌پذيرد، نظريهٔ كامل دارد و درنتيجه تصميم‌پذير است. سپس با استفاده از ايده‌اي مشابه، حذف‌سور پذيرفتن، كامل بودن و در نتيجه تصميم‌پذيري ساختار (R,+,<,Z,0,1,lfloor varphi.x rfloor) را نشان داده‌ايم. تصميم‌پذيري اين سه ساختار، قبلاً با روش‌هاي دشواري و با استفاده از نظريهٔ اتوماتا ثابت شده است ولي اثبات‌هاي ما مبتني بر تكنيك‌هاي سادهٔ نظريهٔ مُدل‌ است. در نهايت، نشان‌ داده‌ايم كه ساختار (Z,+,0,1,lfloor alpha .x rfloor )براي هر عدد غيرگوياي محاسبه‌پذير alpha مدل‌ْكامل است و از مدلِ اول داشتن، كامل بودن و در نتيجه تصميم‌پذيريِ آن را بيان كرده‌ايم. تصميم‌پذيري اين ساختار نتيجهٔ كاملاً جديدي است.

We proof the decidability of four different structures using different methods of model theory. At first, we proof quantifier-elimination for the structure (Z,+,0,1,lfloor varphi.x rfloor), where varphi is the golden ratio. We then conclude the decidability is obtained as a result. We extend this decidability result to the case where an order relation is also added. A similar result also proof when we consider this structure together with the real numbers. Finally, we proof that the structure (Z,+,lfloor alpha .xrfloor,0,1) is model-complete, for any computable irrational number alpha, the decidability of the latter structure is a result of model-completeness.

محسن خاني , مجتبي آقائي فروشاني

علي ولي‌زاده

محمدرضا كوشش , مسعود پورمهديان , نازنين روشن دل توانا