مجموعة قابلة للتحديد

في المنطق الرياضي ، تُعرَّف المجموعة القابلة للتعريف بأنها علاقة من الرتبة n على مجال بنية ما، حيث تحقق عناصرها صيغة معينة في لغة الرتبة الأولى لتلك البنية. ويمكن تعريف المجموعة بمعاملات أو بدونها ، وهي عناصر المجال التي يمكن الرجوع إليها في الصيغة التي تُعرّف العلاقة.

يترك${\displaystyle {\mathcal {L}}}$أن تكون لغة من الدرجة الأولى،${\displaystyle {\mathcal {M}}}$أن${\displaystyle {\mathcal {L}}}$- بنية ذات مجال${\displaystyle M}$،${\displaystyle X}$مجموعة فرعية ثابتة من${\displaystyle M}$، و${\displaystyle m}$عدد طبيعي . ثم:

• مجموعة${\displaystyle A\subseteq M^{m}}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$مع المعلمات من${\displaystyle X}$إذا وفقط إذا كانت هناك صيغة${\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]}$والعناصر${\displaystyle b_{1},\ldots ,b_{n}\in X}$بحيث يكون ذلك لجميع${\displaystyle a_{1},\ldots ,a_{m}\in M}$،

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$إذا وفقط إذا${\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}].}$

يشير رمز الأقواس هنا إلى التقييم الدلالي للمتغيرات الحرة في الصيغة.

• مجموعة${\displaystyle A}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$بدون معلمات إذا كان من الممكن تحديدها في${\displaystyle {\mathcal {M}}}$باستخدام معلمات من المجموعة الفارغة (أي بدون معلمات في الصيغة المحددة).
• يمكن تعريف الدالة في${\displaystyle {\mathcal {M}}}$(مع المعاملات) إذا كان رسمها البياني قابلاً للتحديد (باستخدام تلك المعاملات) في${\displaystyle {\mathcal {M}}}$.
• عنصر${\displaystyle a}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$(مع المعاملات) إذا كانت المجموعة الفردية${\displaystyle \{a\}}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$(مع تلك المعايير).

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

يترك${\displaystyle {\mathcal {M}}}$كن${\displaystyle {\mathcal {L}}}$- بنية ذات مجال${\displaystyle M}$،${\displaystyle X\subseteq M}$، و${\displaystyle A\subseteq M^{m}}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$مع المعلمات من${\displaystyle X}$. يترك${\displaystyle \pi :M\to M}$أن يكون شكلاً ذاتياً لـ${\displaystyle {\mathcal {M}}}$هذه هي الهوية على${\displaystyle X}$ثم للجميع${\displaystyle a_{1},\ldots ,a_{m}\in M}$،

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$إذا وفقط إذا${\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}$

يمكن استخدام هذه النتيجة أحيانًا لتصنيف المجموعات الفرعية القابلة للتحديد لبنية معينة. على سبيل المثال، في حالة${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$أعلاه، أي ترجمة لـ${\displaystyle {\mathcal {Z}}}$هو تماثل ذاتي يحافظ على المجموعة الفارغة من المعاملات، وبالتالي يستحيل تعريف أي عدد صحيح معين في هذا الهيكل بدون معاملات في${\displaystyle {\mathcal {Z}}}$في الواقع، بما أن أي عددين صحيحين يُنقلان إلى بعضهما البعض عن طريق الإزاحة ومعكوسها، فإن مجموعات الأعداد الصحيحة الوحيدة القابلة للتعريف في${\displaystyle {\mathcal {Z}}}$بدون معلمات تكون المجموعة فارغة و${\displaystyle \mathbb {Z} }$في المقابل، توجد مجموعات لا نهائية قابلة للتعريف من الأزواج (أو في الواقع n -tuples لأي n > 1 ثابت) من عناصر${\displaystyle {\mathcal {Z}}}$(في حالة n = 2) تركيبات منطقية للمجموعات${\displaystyle \{(a,b)\mid ab=m\}}$ل${\displaystyle m\in \mathbb {Z} }$. على وجه الخصوص، أي تماثل ذاتي (إزاحة) يحافظ على "المسافة" بين عنصرين.

يُستخدم اختبار Tarski–Vaught لتوصيف البنى الفرعية الأولية لبنية معينة.

• هينمان، بيتر. أساسيات المنطق الرياضي ، إيه كيه بيترز، 2005.
• ماركر، ديفيد. نظرية النموذج: مقدمة ، سبرينغر، 2002.
• رودين، والتر . مبادئ التحليل الرياضي ، الطبعة الثالثة. ماكجرو هيل، 1976.
• سلامان، ثيودور أ. وودين ، دبليو. هيو . المنطق الرياضي: دورة بيركلي الجامعية . ربيع 2006.