حذف سور

«حذف سور» (به انگلیسی: Quantifier elimination) یکی از ویژگی‌های «جبری» مورد بررسی در منطق ریاضی (در نظریهٔ مدلها) است.
تئوریِ

دارای حذف سور است (یا سورها را حذف می‌کند)
هرگاه هر فرمولی به پیمانهٔ آن معادلی بدون سور داشته باشد.

مصداقِ ملموسی از حذف سور،
فرمول تعیین‌کنندهٔ ریشه داشتن یا نداشتن یک معادلهٔ درجهٔ ۲ در اعداد حقیقی است:

حذف سور به دلایل گوناگون اهمیت دارد که برخی از آن‌ها را در ادامه ذکر کرده‌ایم. نخست، برای این که مطالعهٔ مجموعه‌های تعریف‌شدنی را آسان‌تر می‌کند: اگر تئوری

دارای حذف سور باشد، برای بررسی مجموعه‌های تعریف شدنی در مدل‌های آن، تنها کافی است مجموعه‌های تعریف‌شده با ترکیبات بولیِ فرمول‌های اتمی را در نظر بگیریم. دوم این که حذف سور، مطالعهٔ جبری مدل‌ها را ساده می‌کند. اگر

دارای حذف سور باشد، آن‌گاه برای هر دو
مدلِ

از آن، اگر

زیرساختاری از

باشد، آن‌گاه

زیرساختاری مقدماتی از

است، یعنی هر جملهٔ مرتبهٔ اول با پارامتر در

اگر
در

درست باشد، آن‌گاه در

نیز درست است. سوم این که، بررسی کامل بودنِ یک تئوری، در صورت حذف سور پذیرفتن آن، آسان‌تر است. منظور از تئوریِ کامل، تئوری‌ای است که در آن هر جملهٔ داده‌شده یا نقیض آن اثبات شدنی است. از این رو اگر
روندی تصمیم‌پذیر برای اثبات حذف سور داشته باشیم، اثبات تصمیم‌پذیر بودن یک تئوری نیز در حالتی که حذف سور داشته باشد، آسان‌تر است. چهارمین اهمیت حذف سور،
فراهم آوردن توصیف جبری ملموس برای برخی تئوری‌ها و بدینسان برقرار کردن پیوند میان جبر و نظریهٔ مدل است.
برای مثال، بررسی ساختار یا مدل تولید شده توسط یک مجموعهٔ داده شده، یا بررسی بستارِ جبری یک مجموعهٔ داده شده، در تئوری‌ای که حذف سور داشته باشد، به مراتب آسان‌تر است.
این نکته در مثال‌های جبری، مانند میدان‌های بستهٔ حقیقی و میدان‌های بستهٔ جبری
راحت‌تر به چشم می‌آید.

تعریف

تئوریِ

در زبانِ

«دارای حذف سور است»، یا «سورها را حذف می‌کند» هرگاه برای هر فرمولِ

فرمولی بدون سور مانند

پیدا شود که

با به روش‌های مقدماتی منطقی، فرمول بدون سورِ

را می‌توان به صورت

یا

در نظر گرفت که در آن هر

فرمولی اتمی یا نقیض یک فرمول اتمی است.

معادلاً تئوری

دارای حذف سور است، هرگاه «زیرساختارْکامل» باشد. یعنی برای هر مدلِ

و هر زیرساختارِ

تئوریِ

در زبانِ

(زبانی که با افزودن ثابت برای ازای هر
عنصرِ

به
زبان تئوریِ

به دست آمده باشد) یک تئوریِ کامل باشد. منظور از

مجموعهٔ همهٔ جمله‌های بدون سورِ با پارامتر در

است.
از این رو، همان‌گونه که در مقدمه اشاره شد، اگر

دارای حذف سور باشد و

و

آن‌گاه
.
ولی عکس این گفته برقرار نیست. در واقع این ویژگی،
«مدلْ‌کامل»
بودن نام دارد. «زیرساختارْکامل بودن»
معادل «حذف سور» است و «مدل‌ْ‌کاملْ بودن» با «معادل بودن هر فرمول، با فرمولی فقط دارای سورهای وجودی» معادل است.

نیز
تئوریِ

حذف سور می‌پذیرد اگروتنهااگر
هر تایپ کاملی در آن
با فرمول‌های بدون سور آن تایپ
کاملاً تعیین شود. به بیان دیگر، برای هر

در مدل هیولا و هر زیرمجموعهٔ

از مدل هیولا، اگر

آن‌گاه
؛ که منظور از

مجموعهٔ همهٔ فرمول‌های بدون سور با پارامتر در

است که

آن‌ها را برآورده می‌کند.

مثالها

داشتن حذف سور، تنها در یک «زبان معقول» حائزِ اهمیت است. این زبان عموماً بهینه‌ترین زبانی است که ویژگی‌های جبری یک تئوری را بتواند بیان کند. اگر جز این بخواهد باشد، هر تئوری‌ای با اضافه کردن محمول برای هر فرمول دارای سور به زبان، دارای حذف سور می‌شود. به بیان واضح‌تر اگر برای هر فرمولِ
 محمول
 را به زبان و جملهٔ
 را به تئوری بیفزاییم، به یک تئوری دارای حذف سور می‌رسیم.

اعداد طبیعی و حساب پئانو

ساختارِ به‌ظاهرسادهٔ

سورها را حذف
 نمی‌کند.
مسئلهٔ حذف سور برای این ساختار،
هم‌ارزِ مسئلهٔ ناکامل بودن اصول پئانو برای حساب است که گودل آن را ثابت کرده‌است. نیز به بیان دیگر، این مسئله معادل
مسئلهٔ وجود یک زیرمجموعهٔ
بازگشتی شمارش‌پذیر
(آر. ای)
از

است که بازگشتی نباشد. در واقع زیرمجموعه‌های بازگشتی‌ِ شمارش‌پذیرِ

دقیقاً آنهایند که با فرمولهای

تعریف می‌شوند که در آن

یک چندجمله‌ای در

باشد.

حساب پِرِسْبِرگِر

برخلافِ حسابِ پئانو، «حسابِ پِرِسْبِرگِر» دارای حذف سور است. حساب پرسبرگر، به بیان ساده حسابی است که
از تئوریِ کاملِ ساختار

به دست می‌آید که در آن تعبیرِ محمولِ

زیرمجموعهٔ

از

است. نتیجهٔ
تأمل‌برانگیزِ
حذف سور حساب پرسبرگر این است که بر خلاف

که گرفتار دشواری‌های قضیهٔ ناتمامیت گودل است،
ساختارِ

تصمیم‌پذیر است.
حساب پرسبرگر دارای یک اصل‌بندی ساده است که ویژگی‌های گروه جمعیِ ترتیبیِ

را به همراه تعبیرِ
ها بیان می‌کند.

میدانِ ترتیبیِ اعداد حقیقی به همراه جرم توابع تحلیلیِ حقیقی

تئوری میدان بستهٔ حقیقی

بهمراه «جرم توابع تحلیلی حقیقی» و جمع و ضرب و کمتریِ تحدید شده، مدل‌کامل است، یعنی هر فرمولی در آن معادل فرمولی به صورت

است که در آن

فرمولی بدون سور است. (وَن‌ْ دِنْ دریز)
به بیان دیگر،
اگر با

خانوادهٔ همهٔ توابع تحلیلیِ حقیقیِ
محدود شده به بازهٔ بستهٔ

را نشان دهیم، و با

تابع تغییردادهٔ شدهٔ تقسیم را که هر جا

باشد تعریف شده‌است،
تئوریِ ساختارِ

سورها را حذف می‌کند.

در نتیجهٔ حذف سور به راحتی می‌توان نشان داد که ساختار یادشده، کمینهٔ ترتیبی است.
نیز اهمیت دیگر حذف سور در این ساختار این است، که اثباتی نظریهٔ مدلی برای قضیهٔ هندسیِ
«گابْرییِلُف» فراهم می‌آورد. بنا بر قضیهٔ گابرییلف، مکمل هر مجموعهٔ زیرْتحلیلی در

مجموعه‌ای زیرْتحلیلی است.
مجموعه‌های زیرتحلیلی، با گرفتن تصاویرِ مجموعه‌های شبه‌تحلیلی روی محورها به دست می‌آیند.
نیز، مجموعه‌های شبه‌تحلیلی، دقیقاً مجموعه‌هایی هستند که در ساختارِ

بدون سور تعریف می‌شوند.

میدانهای بستهٔ جبری

تئوری کاملِ ساختار

سورها را حذف می‌کند (رابینسون). تئوری این ساختار، از این رو، معادل با تئوری میدان‌های بستهٔ حقیقی با
مشخصهٔ صفر است. در نتیجهٔ حذف سور، تئوری میدان‌های بستهٔ جبری مدلْ‌کامل است و تئوری میدان‌های بستهٔ جبری با مشخصهٔ

(که
 می‌تواند بی‌نهایت نیز باشد) کامل است.

حذف سور در میدان‌های بستهٔ جبری نیز نتایج جبری خوشایندی به دست می‌دهد. در واقع حذف سور در این میدان‌ها معادل
قضیهٔ «شُوالی» است که می‌گوید «تصویر هر مجموعهٔ ساخته‌شدنی تحت یک نگاشت چندجمله‌ای
مجموعه‌ای ساخته‌شدنی است». مجموعه‌های ساخته‌شدنی در میدان‌های بستهٔ جبری، ترکیبات بولی متناهیِ
مجموعه‌های بستهٔ زاریسکی هستند. به بیان دیگر، آن‌ها مجموعه‌های «تعریف‌شدنی»
با فرمول‌های بدون سور
در
یک میدان بستهٔ جبریند. طبیعی است که تصویر آن‌ها تحت نگاشت‌های چندجمله‌ای، دوباره تعریف شدنی، و بنا به حذف سور،
بدون‌سورتعریف‌شدنی، و از این رو ساخته‌شدنی است.

نیز حذف سور (در واقع مدل‌کاملی نتیجه‌شونده از آن) اثبات آسانی برای قضیهٔ ریشه‌های هیلبرت (نول‌اِشتِلِنْ‌سَتز) فراهم می‌آورد.
بنا به این قضیه،
در میدان‌های بستهٔ جبری، مجموعه‌های بستهٔ زاریسکی در تناظر یک‌به‌یکند با
ایده‌آل‌های رادیکال در حلقهٔ چندجمله‌ای‌های متناظر.

نتیجهٔ دیگرِ حذف سور در میدان‌های بستهٔ جبری، این است که آن‌ها بسیارکمینه هستند. یعنی اگر

یک میدان بستهٔ جبری باشد، هر زیرمجموعهٔ تعریف شدنی از

یا خودْ یا مکملش متناهی است (یعنی این مجموعه را می‌توان تنها با نمادِ تساوی تعریف کرد).

میدان ترتیبی اعداد حقیقی به همراه تابعِ نمایی نامحدود

تئوریِ
ساختارِ

یک تئوری مدل‌ْکامل است (ویلکی)؛ یعنی هر فرمول در آن معادلی دارد که تنها دارای سوروجودی است.
نکتهٔ تأمل‌برانگیز
این است که
در این جا
تابع نمایی، محدود در نظر گرفته نشده‌است و بنابراین این قضیه
از قضیهٔ ون‌دِن‌دریز برای

نتیجه نمی‌شود.
نیز بنا به حذف سور، این تئوری ترتیب‌کمینه است. اگر «حدس شانوئل» درست باشد، این تئوری، تصمیم‌پذیر است. حدس شانوئل این است که
اگر

روی

مستقل «خطی» باشند، آن‌گاه مرتبهٔ تعالی میدانِ

حداقل،

است. تصمیم‌پذیری تئوریِ

موردِ
سؤالی از تارسکی بوده‌است.

زوجهای چگال از میدانهای بستهٔ حقیقی

فرض کنید

تئوری «زوجهای چگال از میدانهای بستهٔ حقیقی» باشد (این تئوری، کامل است). به بیان دیگر
زوج

مدلی از

است اگروتنهااگر

و

دو میدان بستهٔ حقیقی در زبانِ

باشند و

در

چگال باشد؛ یعنی هر بازهٔ باز که دو سر آن عناصرِ

باشند، دارای نقطه‌ای در

باشد. این تئوری را می‌توان تئوریِ کاملِ ساختارِ

دانست که در آن منظور از

میدان بستهٔ حقیقی متشکل از همهٔ عناصر جبری روی

است و خطِ
بالایِ

یعنی این میدان به همراه جمع و ضرب و کمتری و صفر و یک.
تئوریِ  در زبانِ

که در آن 
یک نماد محمولی یک ظرفیتی برای میدانِ کوچکتر
()
است، دارای حذف سوری این‌چنین است:
هر فرمولی در این زبان، معادل ترکیبی بولی از فرمولهایی به صورت

است که در آن
.

تئوری یادشده، ترتیب کمینه نیست ولی همچنان از لحاظ توپولوژیک خوش‌رفتار است: هر مجموعهٔ باز از

که در ساختار

تعریف شدنی باشد، اجتماعی متناهی از بازه هاست.
در واقع هر مجموعهٔ باز تعریف شدنی در این ساختار،
در خودِ

تعریف شدنی است.
نیز هر زیرمجموعه از

که در این ساختار تعریف شدنی باشد، اشتراکِ

با زیرمجموعه‌ای چون

از

است که با فرمولی در

تعریف شده باشد. نیز هر زیرمجموعه‌ای چون

از

که در این ساختار تعریف‌شدنی باشد تجزیه‌ای به‌گونهٔ

دارد که در آن
هر

یا یک بازهٔ بازِ زیرمجموعهٔ

است یا یک نقطه است، یا یک بازهٔ باز به‌گونه‌ای است که

و

در

چگال است. مشابه این گفته برای مجموعه‌های تعریف شدنی در ابعاد بالاتر نیز برقرار است (تجزیهٔ سلولی چگال و مکمل‌ْچگال). در نتیجه

در این ساختار تعریف شدنی نیست و این امر برای در امان بودن از دشواری‌های ناتمامیت، در ساختارهای نظریهٔ مدلی اهمیت دارد.

میدانهای ارزیابی

تئوری
میدان‌های ارزیابی‌ِ بستهٔ جبریِ
که در آن مشخصهٔ میدانِ اصلی و میدانِ خارج‌قسمتی تبیین شده‌است،
در زبانِ به دست آمده از اجتماع زبان میدان‌ها با
محمول دوظرفیتیِ
،
سورها را حذف می‌کند (رابینسون).

در حالت کلی‌تر، میدان‌های ارزیابیِ (نه لزوماً بستهٔ جبری) هنسلیِ دارای مؤلفهٔ زاویه‌ای،
به گونهٔ

را در
زبان سه‌بخشیِ

مطالعه می‌کنند که حامل سه بخش برای میدان اصلی و میدان خارج‌قسمتی و گروه ارزیابی‌هاست.
نگاشت ارزیابی با نماد

نشان داده شده‌است. نیز

نگاشت مؤلفهٔ زاویه‌ای، یک همومرفیسم گروه ضربی است که نگاشت کانونیِ
،
را «روی عناصرِ
یکهٔ
»
گسترش می‌دهد. در این زبان می‌توان نشان داد که میدان‌های ارزیابی هنسلی دارای مؤلفهٔ زاویه‌ای و با
مشخصهٔ صفر برای میدان خارج‌قسمتی، سورها را
از میدانِ اصلی، یعنی
،
حذف می‌کنند. به بیان دیگر،
اگر دو میدان ارزیابیِ

و

داشته باشیم و بدانیم که

(به عنوان دو گروه آبلی بخش‌پذیرِ بدونِ تاب)
و

(به عنوان دو میدان)
آنگاه
.

حذف سور تبعات خوشایند زیادی نیز برای میدان‌های ارزیابی دارد. برای مثال، تئوری میدان‌های بستهٔ جبریِ
با مشخصهٔ مشخص، سی‌کمینال (سی‌مینیمال) است. یعنی مجموعه‌های تعریف شدنی در آن ساختاری درخت‌مانند دارند.

نیز در میدان‌های ارزیابیِ بستهٔ جبری، گروه ارزیابی‌ها
و میدان خارج‌قسمتی، هر یک «ثابت‌ْنشانده» هستند. یعنی
زیرمجموعه‌هایی از آن‌ها را که در کل ساختار تعریف‌شدنی باشند می‌توان در خودِ ساختار گروه، یا در خودِ ساختارِ
میدان و بدون کمک‌گیری از بقیهٔ زبان تعریف کرد. این نکته دربارهٔ میدان‌های ارزیابیِ هنسلی دارای مشخصهٔ
خارج‌قسمتیِ
صفر و دارای مؤلفهٔ موضعی نیز درست است.

روش‌های معمول برای بررسی حذف‌سور

پیدا کردن معادل بدون سور
به روش مستقیم و با دستکاری فرمولها،
برای یک فرمول پیچیدهٔ دارای سور همواره عملی‌ترین راه آزمودن حذف سور نمی‌تواند باشد، به ویژه وقتی که زبان دارای چندین بخش است و فرمول‌ها بسیار پیجیده‌اند. عموماً
حذف سور را با کمک گرفتن از «محکهای جبری» زیر می‌آزمایند.

روش اول

تئوری

دارای حذف سور است اگر و تنها اگر برای هر دو مدلِ

و هر زیرساختارِ مشترک از این‌دو مانند

هر فرمولِ

که عطفی از فرمول‌های اتمی (فرمول‌های ساخته شده با کمک تساوی و نقیض و ترم‌ها و رابطه‌های زبان) است و پارامترهای

در آن از

می‌آیند، داشته باشیم

کامل بودن

تئوریِ

را «کامل» می‌خوانند هرگاه هر جمله‌ای یا نقیضِ آن
از

نتیجه شود. اگر

کامل باشد و

آن‌گاه

با تئوریِ کاملِ

هم‌ارز است. یعنی هر ویژگی‌ای که در یکی از مدلهای

برقرار باشد، در همهٔ مدل‌های دیگر نیز برقرار خواهد بود. به بیان دیگر، اگر

کامل باشد و

آن‌گاه
؛
یعنی

و

هم‌ارز مقدماتی هستند.

هرگاه

کامل باشد، می‌توان مدلی
بسیار بزرگ از آن را برای کار اندر آن برگزید و و آن را مدل «هیولا» خواند
و همهٔ مدل‌ها را زیرمدلی از مدل هیولا دانست.
نیز
بررسی تایپ‌ها عموماً در تئوری‌های کامل و در مدل هیولا صورت می‌پذیرد.

اگر

دارای حذف سور باشد و مدلی داشته باشد که در سایر مدل‌های دیگر، مقدماتی نشانده شود، آنگاه

کامل است. کامل بودن بسیاری از تئوریها، مانند
میدان‌های بستهٔ حقیقی و میدان‌های بستهٔ جبری، با کمک این نکته ثابت می‌شود.

همان‌گونه که در تعریف گفتیم، تئوریِ

دارای حذف سور است اگر و تنها اگر برای هر مدل

و
هر
زیرساختارِ

تئوریِ

یک تئوری کامل باشد.

مدلْ‌کامل بودن

بسیاری از تئوری‌ها کامل نیستند
ولی
ویژگی‌ای را نزدیک به کامل‌بودن
دارا هستند که آن را «مدل‌کامل» بودن می‌خوانند.

تئوریِ

را مدل‌ْکامل می‌خوانند هرگاه برای هر مدلِ

تئوریِ

در زبان

یک تئوری کامل باشد.
منظور از

مجموعهٔ همهٔ
جمله‌های بدون سورِ
درست در

است و منظور از

زبانی است که با افزودن ثابت برای عنصرِ

به زبانِ تئوریِ

به دست آمده باشد.
به بیان دیگر، تئوریِ

مدل‌کامل است اگروتنهااگر هر مدل از آن بستهٔ وجودی باشد؛ یعنی اگر

و

یک فرمول بدون سور باشد و

آن گاه برای هر

داریم
.
نیز به بیان دیگر، تئوریِ

مدل‌کامل است اگروتنهاگر برای هر دو مدلِ

داشته باشیم
؛
یعنی

زیرمدلی مقدماتی از

باشد.
تئوریِ

مدل‌کامل است اگروتنهااگر هر فرمولی در آن معادلی با فقط سور وجودی داشته باشد. به بیان دیگر هر فرمول
با متغیرِ آزادِ

معادلی
به گونهٔ

داشته باشد.
که در آن

فرمولی بدون سور است.

از آنجا که «تایپ» مفهومی مقدماتی است (یعنی هر تایپ در یک گسترش مقدماتی برآورده می‌شود)
به مدل‌کامل بودن یک تئوری برای بررسی تایپ‌های آن در مدل هیولا نیاز است.
اگر

حذف سور داشته باشد، مدل‌ْکامل است.

همپای مدلی

برای بررسی راحت‌ترِ
ویژگی‌های تئوری‌های ناکامل، می‌توان «همپای مدلی» آن‌ها را در صورت وجود بررسی کرد که مدل‌ْکامل است.
تئوریِ

را «همپای مدلی» تئوری

می‌خوانیم
هرگاه

مدل‌ْکامل باشد و
.
منظور از

مجموعهٔ همهٔ جمله‌های با سور عمومی است که از

نتیجه می‌شوند.
به بیان دیگر،

یعنی هر مدل از

را بتوان به یک مدل از

گستراند و هر مدل از

را به یک مدل از
.
همپای مدلی یک تئوری لزوماً همیشه موجود نیست، ولی در صورت وجود، یکتاست.
تئوریِ

دارای همپای مدلی است، اگروتنهااگر کلاس همهٔ مدل‌های بسته‌ٔوجودیِ آن، کلاسی مقدماتی باشد.
در واقع همپای مدلیِ
،
تئوری‌ِ این کلاس مقدماتی است.
مدلِ

را «بستهٔ وجودی»
می‌خوانند هرگاه برای هر

و هر فرمولِ بدون سورِ

که در آن

داشته باشیم
.

مُکمّلِ مدلی

اگر

همپای مدلیِ

باشد و

دارای «ویژگی پیوندی» (همان گونه که در زیر آمده‌است) باشد، آن‌گاه

را «مکمل مدلیِ»

می‌خوانیم. مکمل‌ِ مدلی یک تئوری به داشتن حذف سور نزدیک است؛ از آن رو که
مکملِ مدلیِ یک تئوری با اصل‌بندیِ جهانی ()
دارای حذف سور است.

نیز

مکمل مدلیِ

است.
اگروتنهااگر
همپای مدلی

باشد و برای هر

تئوریِ

در زبان

یک تئوری کامل باشد.