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

قضیهٔ اردیش–سکرش در ریاضیات نتیجه‌ای متناهی است که یکی از نتایج قضیهٔ رمزی را دقیق می‌سازد. به خاطر اینکه با استفاده از قضیهٔ رمزی اثباتی آسان برای اینکه هر دنباله نامتناهی از اعداد حقیقی متمایز دارای زیردنباله‌ای نامتناهی به صورت صعودی یا نزولی است، وجود دارد؛ با اثبات پل اردیش  و جرج سکرش  این قضیه بسط داده می‌شود. آن‌ها اثبات کردند که برای هر دنباله‌ای به طول K که K>mn؛ دارای زیردنباله‌ای صعودی به طول n+1 یا زیردنباله‌ای نزولی به طول m+1 است (یا هر دو). این اثبات در سال ۱۹۳۵ در ورقهٔ اثبات مسئله پایان یافتن شادی به عنوان یادکرد آمده‌است.

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

 اثبات 
فرض می‌کنیم اعضای دنباله به صورت a1،a2،... ،ak است.

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

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

حال زیردنبالهٔ ai1،ai2،... ،aim+1 نزولی است زیرا اگر قرار باشد چنین نباشد به این نتیجه می‌رسیم که ۱+bi1≥bi2؛ که با فرضمان (bi1=bi2) تناقض دارد. پس حکم مسئله اثبات می‌شود.

این مسئله هم‌چنین به کمک قضیهٔ دیلورث اثبات می‌شود.

 جستارهای وابسته 
 طولانی‌ترین زیررشته صعودی

 پانویس 

 پیوند به بیرون 


رده:پل اردوش
رده:قضیه‌ها در ریاضیات گسسته
رده:قضیه‌ها در هندسه گسسته
رده:نظریه رمزی