قضیه اردیش–ژکرس

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

قضیهٔ اردیش–ژکرس در ریاضیات نتیجه‌ای متناهی است که یکی از نتایج قضیهٔ رمزی را دقیق می‌سازد. به خاطر اینکه با استفاده از قضیهٔ رمزی اثباتی آسان برای اینکه هر دنباله نامتناهی از اعداد حقیقی متمایز دارای زیردنباله‌ای نامتناهی به صورت صعودی یا نزولی است، وجود دارد؛ با اثبات پل اردیش (به مجاری: Erdős Pál) و ژرژ ژکرس (به مجاری: Szekeres György) این قضیه بسط داده می‌شود. آن‌ها اثبات کردند که برای هر دنباله‌ای به طول K که K>mn؛ دارای زیردنباله‌ای صعودی به طول n+1 و یا زیردنباله‌ای نزولی به طول m+1 است (یا هر دو). این اثبات در سال ۱۹۳۵ در ورقهٔ اثبات مسأله پایان یافتن شادی به عنوان یادکرد آمده‌است.[۱]

مثال‌ها[ویرایش]

به عنوان مثال در جایگشت اعداد ۱ تا ۳:

  • ۱،۲،۳ هر سه عدد خود یک زیردنبالهٔ صعودی هستند.
  • ۱،۳،۲ دارای زیردنبالهٔ نزولی ۳،۲ است.
  • ۲،۱،۳ دارای زیر دنبالهٔ نزولی ۲،۱ است.
  • ۲،۳،۱ دارای دو زیردنبالهٔ نزولی ۲،۱ و ۳،۱ است.
  • ۳٬۱٬۲ دارای دو زیردنبالهٔ ۳،۱ و ۳،۲ است.
  • ۳،۲،۱ دارای سه زیردنباله نزولی به طول ۲ شامل ۳٬۲، ۳٬۱ و ۲٬۱ است.

اثبات[ویرایش]

فرض می‌کنیم اعضای دنباله به صورت a۱،a۲،...،ak است.

به ازای هر i بین ۱ تا bi k را طول بلندترین زیردنبالهٔ صعودی در دنباله درنظر می‌گیریم که جملهٔ آخرش ai است.

اگر به ازای یکی از iها bi≥n+۱ حکم اثبات می‌شود؛ پس فرض می‌کنیم چنین نباشد؛ در این صورت biها بین ۱ تا n هستند. پس بنابر اصل لانه کبوتری حداقل m+۱ تا از bi برابر هستند. فرض کنید bi۱=bi۲=...=bim+۱ که ijها صعودی هستند.

حال زیردنبالهٔ ai۱،ai۲،...،aim+۱ نزولی است زیرا اگر قرار باشد چنین نباشد به این نتیجه می‌رسیم که ۱+bi۱≥bi۲؛ که با فرضمان (bi۱=bi۲) تناقض دارد. پس حکم مسئله اثبات می‌شود.[۲]

این مسأله هم‌چنین به کمک نظریه دیلورث اثبات می‌شود.

جستارهای وابسته[ویرایش]

پانویس[ویرایش]

  1. Erdős, Paul; Szekeres, George. «A combinatorial problem in geometry». Compositio Mathematica، 1935، 463–470. 
  2. علیپور، علیرضا. ترکیبیات. ج. اول. فاطمی، ۱۳۸۲. شابک ‎۹۶۴-۳۱۸-۳۴۲-۴. 

پیوند به بیرون[ویرایش]