البنية (المنطق الرياضي)

نطاق البنية هو مجموعة اختيارية؛ ويُسمى أيضًا المجموعة الأساسية للبنية، أو حاملها (خاصة في الجبر الشامل)، أو كونُها ( خاصة في نظرية النماذج، انظر الكون )، أو نطاق خطابها . في منطق الرتبة الأولى الكلاسيكي، يمنع تعريف البنية النطاق الفارغ . ^{[ 6 ]}

أحيانًا يكون الترميز${\displaystyle \operatorname {dom} ({\mathcal {A}})}$أو${\displaystyle |{\mathcal {A}}|}$يُستخدم في مجال${\displaystyle {\mathcal {A}},}$لكن في كثير من الأحيان لا يتم التمييز بين البنية ومجالها من الناحية الرمزية (أي، نفس الرمز).${\displaystyle {\mathcal {A}}}$يشير إلى كل من البنية ومجالها.) ^{[ 7 ]}

التوقيع${\displaystyle \sigma =(S,\operatorname {ar} )}$يتكون الهيكل من:

• مجموعة${\displaystyle S}$من رموز الدوال ورموز العلاقات ، بالإضافة إلى
• دالة${\displaystyle \operatorname {ar}$ :\ S\to \mathbb {N} _{0}} التي تُنسب إلى كل رمز${\displaystyle s}$عدد طبيعي${\displaystyle n=\operatorname {ar} (s).}$

العدد الطبيعي${\displaystyle n=\operatorname {ar} (s)}$رمز${\displaystyle s}$يُطلق عليه اسم رتبة${\displaystyle s}$لأنها مسألة تفسير​${\displaystyle s.}$

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

وظيفة التفسير${\displaystyle I}$ل${\displaystyle {\mathcal {A}}}$يُعيّن وظائف وعلاقات لرموز التوقيع. لكل رمز وظيفة${\displaystyle f}$من رتبة${\displaystyle n}$يتم تعيينه${\displaystyle n}$دالة -ary${\displaystyle f^{\mathcal {A}}=I(f)}$في المجال. كل رمز علاقة${\displaystyle R}$من رتبة${\displaystyle n}$يتم تعيينه${\displaystyle n}$العلاقات -ary${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$في المجال. صفري (${\displaystyle =\,0}$رمز الدالة (-ary)${\displaystyle c}$يُطلق عليه رمز ثابت ، لأن تفسيره${\displaystyle I(c)}$يمكن تحديدها بعنصر ثابت من المجال.

عندما يتم تحديد بنية (وبالتالي وظيفة تفسير) من خلال السياق، لا يتم التمييز بين الرموز.${\displaystyle s}$وتفسيره${\displaystyle I(s).}$على سبيل المثال، إذا${\displaystyle f}$هو رمز دالة ثنائية لـ${\displaystyle {\mathcal {A}},}$يكتب المرء ببساطة${\displaystyle f:{\mathcal {A}}^{2}\to {\mathcal {A}}}$بدلاً من${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\to |{\mathcal {A}}|.}$

التوقيع القياسي${\displaystyle \sigma _{f}}$تتكون الحقول من رمزين للدالة الثنائية${\displaystyle \mathbf {+} }$و${\displaystyle \mathbf {\times } }$حيث يمكن اشتقاق رموز إضافية، مثل رمز الدالة الأحادية${\displaystyle \mathbf {-} }$(يتم تحديده بشكل فريد بواسطة${\displaystyle \mathbf {+} }$) والرمزين الثابتين${\displaystyle \mathbf {0} }$و${\displaystyle \mathbf {1} }$(يتم تحديده بشكل فريد بواسطة${\displaystyle \mathbf {+} }$و${\displaystyle \mathbf {\times } }$على التوالي). وبالتالي، يتكون هيكل (جبر) هذه البصمة من مجموعة من العناصر${\displaystyle A}$بالإضافة إلى دالتين ثنائيتين، يمكن تعزيزهما بدالة أحادية، وعنصرين مميزين؛ ولكن لا يوجد شرط بأن يحقق أيًا من بديهيات الحقل. الأعداد النسبية${\displaystyle \mathbb {Q} ,}$الأرقام الحقيقية${\displaystyle \mathbb {R} }$والأعداد المركبة${\displaystyle \mathbb {C} ,}$مثل أي مجال آخر، يمكن اعتباره${\displaystyle \sigma }$-هياكل بطريقة واضحة: $${\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}$$

في الحالات الثلاث جميعها، لدينا التوقيع القياسي المقدم من $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ مع ^{[ 8 ]}${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$و $${\displaystyle {\begin{alignedat}{3}\operatorname {ar} _{f}&(+)&&=2,\\\operatorname {ar} _{f}&(\times )&&=2,\\\operatorname {ar} _{f}&(-)&&=1,\\\operatorname {ar} _{f}&(0)&&=0,\\\operatorname {ar} _{f}&(1)&&=0.\\\end{alignedat}}}$$

وظيفة التفسير${\displaystyle I_{\mathcal {Q}}}$يكون:

${\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$هو جمع الأعداد النسبية،

${\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$هو ضرب الأعداد النسبية،

${\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} }$هي الدالة التي تأخذ كل عدد نسبي${\displaystyle x}$ل${\displaystyle -x,}$و

${\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} }$هو الرقم${\displaystyle 0,}$و

${\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} }$هو الرقم${\displaystyle 1;}$

و${\displaystyle I_{\mathcal {R}}}$و${\displaystyle I_{\mathcal {C}}}$يتم تعريفها بشكل مماثل. ^{[ 8 ]}

لكن الخاتم${\displaystyle \mathbb {Z} }$من الأعداد الصحيحة ، وهو ليس حقلاً، هو أيضاً${\displaystyle \sigma _{f}}$-البنية بنفس الطريقة. في الواقع، ليس هناك شرط بأن تتحقق أي من بديهيات المجال في${\displaystyle \sigma _{f}}$-بناء.

يتطلب التوقيع الخاص بالحقول المرتبة علاقة ثنائية إضافية مثل:${\displaystyle \,<\,}$أو${\displaystyle \,\leq ,\,}$وبالتالي فإن الهياكل الخاصة بمثل هذه التوقيعات ليست جبرًا، على الرغم من أنها بالطبع هياكل جبرية بالمعنى المعتاد والفضفاض للكلمة.

تتضمن التوقيعات العادية لنظرية المجموعات علاقة ثنائية واحدة${\displaystyle \in .}$ يتكون هيكل هذا التوقيع من مجموعة من العناصر وتفسير لها.${\displaystyle \in }$العلاقة كعلاقة ثنائية على هذه العناصر.

يترك${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ليكن التوقيع القياسي للحقول مرة أخرى. عند اعتباره كذلك${\displaystyle \sigma }$تُشكل الأعداد النسبية ، وفقًا للبنية الطبيعية، بنيةً فرعيةً من الأعداد الحقيقية ، وتُشكل الأعداد الحقيقية بنيةً فرعيةً من الأعداد المركبة . وتُعد الأعداد النسبية أصغر بنية فرعية من الأعداد الحقيقية (أو المركبة) التي تُحقق أيضًا بديهيات الحقل.

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

إن أوضح طريقة لتعريف الرسم البياني هي بنية ذات توقيع.${\displaystyle \sigma }$يتكون من رمز علاقة ثنائية واحد${\displaystyle E.}$تشكل رؤوس الرسم البياني نطاق البنية، وبالنسبة لرأسين${\displaystyle a}$و${\displaystyle b,}$${\displaystyle (a,b)\!\in {\text{E}}}$هذا يعني أن${\displaystyle a}$و${\displaystyle b}$تتصل هذه العناصر بحافة. ​​في هذا الترميز، يكون مفهوم البنية الفرعية المستحثة أكثر تقييدًا من مفهوم الرسم البياني الفرعي . على سبيل المثال، ليكن${\displaystyle G}$ليكن رسمًا بيانيًا يتكون من رأسين متصلين بحافة، وليكن${\displaystyle H}$ليكن الرسم البياني مكونًا من نفس الرؤوس ولكن بدون حواف.${\displaystyle H}$هو رسم بياني فرعي من${\displaystyle G,}$لكن ليس بنية فرعية مستحثة. المفهوم في نظرية المخططات الذي يتوافق مع البنى الفرعية المستحثة هو مفهوم المخططات الفرعية المستحثة .

بالنظر إلى هيكلين${\displaystyle {\mathcal {A}}}$و${\displaystyle {\mathcal {B}}}$من نفس التوقيع σ، تماثل (σ-) من${\displaystyle {\mathcal {A}}}$ل${\displaystyle {\mathcal {B}}}$هي خريطة${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$وهذا يحافظ على الوظائف والعلاقات. بتعبير أدق:

• لكل رمز دالة من الرتبة n، f، من σ وأي عناصر${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$، تنطبق المعادلة التالية:

${\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))}$.

• لكل رمز علاقة من الرتبة n، R، لـ σ وأي عناصر${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$وبالتالي، فإن النتيجة التالية صحيحة:

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

أين${\displaystyle R^{\mathcal {A}}}$،${\displaystyle R^{\mathcal {B}}}$هو تفسير رمز العلاقة${\displaystyle R}$في الهيكل${\displaystyle {\mathcal {A}}}$،${\displaystyle {\mathcal {B}}}$على التوالى.

تماثل h من${\displaystyle {\mathcal {A}}}$ل${\displaystyle {\mathcal {B}}}$يُشار إليه عادةً بـ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$على الرغم من أن الدالة h تقع تقنيًا بين المجالين${\displaystyle |{\mathcal {A}}|}$،${\displaystyle |{\mathcal {B}}|}$من بين الهيكلين${\displaystyle {\mathcal {A}}}$،${\displaystyle {\mathcal {B}}}$.

لكل توقيع σ توجد فئة ملموسة σ- Hom تحتوي على هياكل σ ككائنات و σ-homomorphisms كـ morphisms .

التشاكل${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$يُطلق عليه أحيانًا اسم التشاكل القوي إذا كان الاستلزام العكسي المذكور أعلاه صحيحًا أيضًا. بتعبير أدق:

• لكل رمز علاقة من الرتبة n، R، لـ σ وأي عناصر${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$بحيث${\displaystyle (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$ثم هناك${\displaystyle a_{1}',a_{2}',\dots ,a_{n}'\in |{\mathcal {A}}|}$بحيث${\displaystyle (a_{1}',a_{2}',\dots ,a_{n}')\in R^{\mathcal {A}}}$و${\displaystyle h(a_{1}')=h(a_{1}),\,h(a_{2}')=h(a_{2}),\,\dots ,\,h(a_{n}')=h(a_{n}).}$^{[ 9 ]}

تؤدي التشاكلات القوية إلى ظهور فئة فرعية من الفئة σ- Hom التي تم تعريفها أعلاه.

تماثل (σ)${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$يُطلق عليه اسم تضمين (σ-) إذا كان حقنيًا و

• لكل رمز علاقة من الرتبة n، R، لـ σ وأي عناصر${\displaystyle a_{1},a_{2},\dots ,a_{n}}$، ويتحقق التكافؤ التالي:

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

(أين${\displaystyle R^{\mathcal {A}}}$،${\displaystyle R^{\mathcal {B}}}$هو تفسير رمز العلاقة${\displaystyle R}$في الهيكل${\displaystyle {\mathcal {A}}}$،${\displaystyle {\mathcal {B}}}$على التوالى).

وبالتالي، فإن التضمين هو نفسه التشاكل القوي الذي يكون حقنيًا. وتُعدّ فئة σ- Emb ، التي تضمّ هياكل σ وتضمينات σ، فئة فرعية ملموسة من σ- Hom .

تُقابل البنى الفرعية المُستحثة الكائنات الفرعية في σ- Emb . إذا كانت σ تحتوي فقط على رموز الدوال، فإن σ- Emb هي الفئة الفرعية من أحاديات الشكل في σ- Hom . في هذه الحالة، تُقابل البنى الفرعية المُستحثة أيضًا الكائنات الفرعية في σ- Hom .

كما رأينا سابقًا، في الترميز القياسي للرسوم البيانية كبنى، تكون البنى الفرعية المستحثة هي الرسوم البيانية الفرعية المستحثة نفسها. مع ذلك، فإن التشاكل بين الرسوم البيانية هو نفسه التشاكل بين البنيتين اللتين تُرمّزان الرسم البياني. في مثال القسم السابق، على الرغم من أن الرسم البياني الفرعي H من G ليس مستحثًا، فإن دالة التطابق id: H → G هي تشاكل. هذه الدالة في الواقع أحادية في الفئة σ- Hom ، وبالتالي فإن H كائن فرعي من G ليس بنية فرعية مستحثة.   

تُعرف المشكلة التالية بمشكلة التشاكل :

بالنظر إلى بنيتين محدودتين${\displaystyle {\mathcal {A}}}$و${\displaystyle {\mathcal {B}}}$بالنسبة لتوقيع علائقي محدود، ابحث عن تماثل${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$أو أثبت أنه لا يوجد مثل هذا التشاكل.

لكل مسألة إرضاء القيود (CSP) ترجمة إلى مسألة التماثل. ^{[ 10 ]} لذلك، يمكن دراسة تعقيد مسألة إرضاء القيود باستخدام أساليب نظرية النموذج المحدود .

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

كل بنية من الدرجة الأولى${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$توجد علاقة رضا${\displaystyle {\mathcal {M}}\vDash \phi }$محدد لجميع الصيغ${\displaystyle \,\phi }$ باللغة التي تتكون من لغة${\displaystyle {\mathcal {M}}}$بالإضافة إلى رمز ثابت لكل عنصر من عناصر${\displaystyle M,}$والذي يُفسَّر على أنه ذلك العنصر. تُعرَّف هذه العلاقة استقرائيًا باستخدام مخطط تارسكي T.

هيكل${\displaystyle {\mathcal {M}}}$ويُقال إنها نموذج لنظرية${\displaystyle T}$إذا كانت لغة${\displaystyle {\mathcal {M}}}$هي نفسها لغة${\displaystyle T}$وكل جملة في${\displaystyle T}$يرضى بـ${\displaystyle {\mathcal {M}}.}$وهكذا، على سبيل المثال، فإن "الحلقة" هي بنية للغة الحلقات التي تحقق كل بديهيات الحلقة، ونموذج نظرية مجموعة ZFC هو بنية في لغة نظرية المجموعات التي تحقق كل بديهيات ZFC.

أن${\displaystyle n}$العلاقات -ary${\displaystyle R}$في الكون (أي المجال)${\displaystyle M}$من الهيكل${\displaystyle {\mathcal {M}}}$يُقال إنها قابلة للتعريف (أو قابلة للتعريف بشكل صريح، انظر قابلية تعريف بيث ، أو${\displaystyle \emptyset }$- قابلة للتحديد ، أو قابلة للتحديد باستخدام معلمات من${\displaystyle \emptyset }$(انظر أدناه) إذا كانت هناك صيغة${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$بحيث $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$ بعبارة أخرى،${\displaystyle R}$يمكن تعريفها إذا وفقط إذا كانت هناك صيغة${\displaystyle \varphi }$بحيث $${\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}$$ هذا صحيح.

ومن الحالات الخاصة المهمة إمكانية تعريف عناصر محددة. عنصر${\displaystyle m}$ل${\displaystyle M}$يمكن تعريفها في${\displaystyle {\mathcal {M}}}$إذا وفقط إذا كانت هناك صيغة${\displaystyle \varphi (x)}$بحيث $${\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}$$

يدرس كل من الجبر الشامل ونظرية النماذج فئات من (البنى أو) الجبر التي تُعرَّف بواسطة توقيع ومجموعة من البديهيات. في حالة نظرية النماذج، تأخذ هذه البديهيات شكل جمل من الدرجة الأولى. أما شكلية الجبر الشامل فهي أكثر تقييدًا؛ إذ لا تسمح أساسًا إلا بجمل من الدرجة الأولى تأخذ شكل معادلات كمية شاملة بين الحدود، على سبيل المثال${\displaystyle \forall }$ x ${\displaystyle \forall }$y  ( x  + y = y + x ). إحدى النتائج المترتبة على ذلك هي أن اختيار التوقيع أكثر أهمية في الجبر الشامل منه في نظرية النماذج. على سبيل المثال، فئة الزمر، في التوقيع المكون من رمز الدالة الثنائية × والرمز الثابت 1، هي فئة أولية ، لكنها ليست صنفًا . يحل الجبر الشامل هذه المشكلة بإضافة رمز الدالة الأحادية ^-1 .     

في حالة الحقول، تنجح هذه الاستراتيجية فقط مع الجمع. أما مع الضرب، فهي تفشل لأن الصفر لا يملك معكوسًا ضربيًا. ومحاولةٌ مؤقتةٌ لمعالجة هذه المشكلة هي تعريف 0 ^{- 1}  =  0. (لكن هذه المحاولة تفشل، لأن هذا التعريف يجعل 0  ×  0 ^{- 1}  =  1 غير صحيح). لذلك، يُفضَّل السماح بالدوال الجزئية، أي الدوال المعرفة فقط على مجموعة جزئية من مجالها. مع ذلك، توجد عدة طرق واضحة لتعميم مفاهيم مثل البنية الجزئية، والتشاكل، والهوية.

في نظرية الأنواع ، توجد أنواع عديدة من المتغيرات، لكل منها نوع . تُعرَّف الأنواع استقرائيًا؛ فإذا كان لدينا نوعان δ و σ، يوجد أيضًا نوع σ → δ يُمثِّل الدوال من كائنات النوع σ إلى كائنات النوع δ. يجب أن يتضمن هيكل اللغة المكتوبة (في الدلالات العادية من الدرجة الأولى) مجموعة منفصلة من الكائنات من كل نوع، وبالنسبة لنوع الدالة، يجب أن يحتوي الهيكل على معلومات كاملة حول الدالة التي يُمثِّلها كل كائن من ذلك النوع.

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

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

في كتاب " برينسيبيا ماثيماتيكا " لبرتراند راسل ، سُمح أيضًا للهياكل بأن يكون لها فئة مناسبة كمجال لها.