ریاضیات، معجزات و پارادوکس ها

نویسندگان بخشی از گروه منطق ریاضی گروه ریاضیات و علوم کامپیوتر دانشگاه کامرینو هستند. فعالیت تحقیقاتی آنها عمدتاً به نظریه مدل و کاربردهای آن در جبر مربوط می شود.
کارلو تافالوری با همکاری پاتریزیو سینتیولی متنی در مورد "منطق ریاضی" برای مک گراو هیل (2000) و با آنالیسا مارکجا "مقدمه ای بر نظریه مدل" (پیتاگورا، 1998) نوشت که نسخه انگلیسی آن اصلاح و گسترش یافت. در شرف آشنایی با کلوور است.

مقاله در n ظاهر شد. 46 از نامه ریاضی PRISTEM

استفانو لئونسی، کارلو توفالوری و سامانتا توردینی

معجزه ها

توجه خواننده ای که مقاله [1] را در مجله Fundamenta Mathematicae در سال 1924 مرور می کند، مطمئناً در صفحات 260-261 با بیانی شگفت انگیز که چیزی شبیه به این است جلب می کند: می توان یک کره از سه بعدی معمول را تقسیم کرد. فضایی در تعداد محدودی از قطعات که وقتی به درستی از نو ترکیب شوند، دو کره برابر با کره آغازین تشکیل می دهند .

همانطور که ذکر شد، این گزاره دست کم عجیب است و مطمئناً اناجیل رسمی و گزارشی که در آنجا از معجزه تکثیر نان ارائه شده است به ذهن متبادر می شود: در نسخه سنت جان (فصل 6) به عنوان مثال گفته می شود که چگونه از پنج نان جو به اندازه ای است که پنج هزار مرد (بدون احتساب زن و بچه) را سیر می کنید و دوازده سبد را از پسماندها پر می کنید.

اما بیانیه در مورد تکراری شدن کره ها هیچ چیز ماوراء طبیعی یا الهی ندارد: این یک قضیه بسیار درونی ریاضیات است - قطعاً شگفت انگیز است، به طوری که معمولاً آن را پارادوکس Banach-Tarski می نامند - اما در هر صورت فقط یک قضیه ریاضیات است. با فرضیه ها، تزها و شواهد خوبش.

اما دقیقاً به همین دلیل می توانیم از خود بپرسیم: آیا علم و به ویژه ریاضیات می توانند معجزات را توضیح دهند؟ و اگر چنین است، چرا از آن استفاده نمی کنید؟ شاید بتوانیم این مکانیسم را برای مقاصد بسیار محدودتر و عرفانی‌تر به کار ببریم، مثلاً به جای کره یا نان، شمش‌های طلا را بازتولید کنیم، و ابتدا ثروت خود را دو برابر کنیم و سپس صد برابر کنیم.

در هر صورت، حتی صرف نظر از این استدلال های بسیار زمینی و سطحی، ارزش آن را دارد که عمیق تر در بحث و درک اینکه چرا می توانیم از نظر ریاضی ثابت کنیم که ماده می تواند به معنایی که در بالا توضیح داده شد، مضاعف و بازتولید شود.

قضیه زرملو

برای ترسیم یک توضیح، باید لحظه ای 1924 (و مسئله کره ها) را کنار بگذاریم و چند سال قبل از آن، یعنی همان آغاز قرن بیستم، برگردیم.

چند سالی بود که کانتور قبلاً نظریه مجموعه‌ها و به‌ویژه در درون آن اعداد اصلی را معرفی کرده بود : اعدادی که 0، 1، 2، ... معمولی را گسترش می‌دهند و با آنها می‌شماریم و به ما امکان می‌دهند «قدر» را حتی اندازه‌گیری کنیم. از مجموعه های بی نهایت بنابراین، مجموعه عناصر طبیعی خود دارای تعدادی عنصر است که با À0 نشان داده می شود و به آن بی نهایت قابل شمارش می گویند، در حالی که خط راست واقعی R دارای تعدادی نقطه است که به آنها توان پیوستار می گویند و متفاوت بودن آنها ثابت شده است. از À0 و در واقع برابر است، به معنای مناسب، به توان 2Ào. اما در آغاز سال 1900 ایجاد یک حساب معقول برای این اعداد نامتناهی (قابل شمارش، استمرار و غیره) که ویژگی‌های معمول اعداد طبیعی را گسترش می‌داد، اصلاً آسان نبود. با این حال، مشاهده شد که اگر بتوان نشان داد که هر مجموعه را می توان به خوبی سفارش داد ، بسیاری از مشکلات مهم در این زمینه برطرف و حل می شود . بیایید سعی کنیم توضیح دهیم که این گزاره آخر چیست.

اعداد طبیعی، با ترتیب معمول «کمتر مساوی» خود، خاصیتی به نام اصل حداقل را برآورده می‌کنند : هر زیرمجموعه‌ای غیر خالی از آنها حداقل عنصر را می‌پذیرد. بنابراین می توان آنها را ردیف کرد و آنها را یکی پس از دیگری ارائه کرد: 0 اول، 1 دوم (حداقل بعد از 0) و غیره. این موضوع برای واقعی ها صدق نمی کند (دوباره با توجه به ترتیب معمول): برای مثال، حداقل واقعی مثبت وجود ندارد، زیرا هر e > 0 واقعی همچنان بزرگتر از نصف آن است.

مجموعه‌های مرتب‌شده‌ای که دارای ویژگی حداقل اعداد طبیعی هستند و بنابراین یک عنصر اول را برای هر زیرمجموعه غیر خالی می‌پذیرند، به خوبی مرتب شده‌اند. واقعی ها با نظم همیشگی خود یک کل منظم را تشکیل نمی دهند و بسیاری از نمونه های متقابل دیگر آنها را همراهی می کنند. اما هیچ چیز مستثنی نمی‌کند که همان واقعی‌ها، با توجه به ترتیب‌بندی‌های دیگر، به‌طور مناسبی بازآرایی شده‌اند، مجموعه‌ای مرتب شده‌اند و بنابراین در هر زیرمجموعه‌ای غیر خالی یک عنصر حداقلی دارند. عبارتی که ما در مورد آن بحث می کنیم حتی قوی تر است و معتقد است که هر مجموعه غیر خالی A، و نه فقط R ، می تواند دارای رابطه ای باشد که آن را به خوبی مرتب می کند و عناصر آن را پشت سر هم در یک ردیف قرار می دهد (همانطور که برای طبیعی). یک لحظه تأمل می‌تواند خواننده ما را، اگر نه در مورد معقول بودن، حداقل به قدرت این فرضیه متقاعد کند: اگر درست باشد، یک ابزار فنی قدرتمند را برای تسلط بر هر مجموعه A تضمین می‌کند و عناصر آن را به روشی که توضیح دادیم فهرست می‌کند. به ویژه، همانطور که قبلاً مشاهده شد، با این وسیله می‌توانیم مسائل اعداد اصلی نامتناهی را که در بالا ذکر کردیم حل کنیم.

کسی که برای اولین بار این حدس را در مورد نظم خوب مطرح کرد کانتور در سال 1883 بود. اما تنها در سال 1904 بود که ریاضیدان آلمانی زرملو مدرکی [2] را در مجله ریاضیات بسیار معتبر Mathematische Annalen منتشر کرد که سپس آن را در میان گذاشت. نام ویراستاران آن مانند کلاین و هیلبرت. اثبات زرملو حدود سه صفحه را در بر می گیرد و با نظراتی از نویسنده به پایان می رسد. به ویژه، درست قبل از پایان، زرملو تأکید می‌کند که اثبات او بر این اصل استوار است که «ضرب مجموع بی‌نهایت مجموعه‌ها، که هر کدام شامل حداقل یک عنصر است، خود با صفر متفاوت است. این اصل منطقی را نمی توان به طور دقیق به یک اصل ساده تر تقلیل داد، اما می توان آن را در همه جا در استنتاجات ریاضی بدون تردید به کار برد . به عبارت دیگر، زرملو - برای اثبات اینکه هر مجموعه غیر خالی را می توان به خوبی مرتب کرد - بر این واقعیت استوار است که حاصل ضرب دکارتی مجموعه های غیر خالی (احتمالاً نامتناهی) غیر خالی است و این مقدمه را کاملاً مشهود می داند و نیازی به اثبات بیشتر ندارد

با این حال، این موضوع برای معاصران زرملو چندان واضح به نظر نمی رسید، اگر قبلاً در شماره بعدی مقالات Mathematische Annalen توسط ریاضیدانانی مانند Schoenflies و Bernstein ظاهر شد که خود را به دور از قانع کردن اعلام کردند. در واقع، کسانی بودند که سعی کردند زرملو را به مستقیم ترین راه رد کنند، مثالی متقابل ارائه کردند و به طور خاص نشان دادند که نمی توان به خوبی به حق امتیاز دستور داد. در واقع، کونیگ چند ماه قبل از کار زرملو مدرکی را برای این واقعیت ارائه کرده بود، اما از آنجایی که از استدلال های او قانع نشد و با وجود زرملو متقاعد شد (با وجود زرملو) از عدم امکان نظم دادن به خانواده سلطنتی، در سال 1905 پیشنهاد جدیدی را ارائه کرد. تظاهرات، که اکنون سعی می کنیم آن را خلاصه کنیم.

بیایید لحظه ای بپذیریم که واقعیات را می توان به خوبی با توجه به یک رابطه مساوی مناسب تر مرتب کرد و بیایید لحظه ای به موضوعی بپردازیم که در نگاه اول بسیار دور به نظر می رسد و به طور تصادفی ریاضیات و دستور زبان را در هم می آمیزد. در واقع، می توانیم توافق کنیم که کلمات زبان ایتالیایی یک مجموعه محدود را تشکیل می دهند: یک فرهنگ لغت برای گنجاندن همه آنها کافی است. در نتیجه، به روشی نسبتاً ساده ثابت می‌شود که جملاتی که می‌توان در زبان ایتالیایی شکل داد (که در هر صورت دنباله‌های مرتب شده متناهی از کلمات هستند) حداکثر یک بی‌نهایت قابل شمارش (مانند جملات طبیعی) هستند. اجازه دهید تمام اعداد واقعی را که می توان با یک جمله معنی دار در ایتالیایی تعریف کرد (صفر، یک، ریشه دو، پی و غیره) در نظر بگیریم. مجموعه آنها فقط قابل شمارش است و از آنجایی که کل خط واقعی بسیار بزرگتر است و به قدرت پیوسته می رسد، رئال هایی وجود دارند که نمی توان آنها را با یک جمله معنی دار در ایتالیایی تعریف کرد. بنابراین، به ویژه، یک r واقعی وجود دارد که دارای این ویژگی است و با توجه به نظم خوبی که ما برای واقعیات تشخیص داده ایم، حداقل است. اما پس از آن r را می توان به عنوان عدد واقعی کوچکتر در مقایسه با "برابر بزرگتر" ارائه کرد که نمی توان آن را با یک جمله معنی دار در ایتالیایی تعریف کرد و این با یک جمله معنی دار در ایتالیایی تعیین می شود و ما را به یک تضاد ظاهراً غیرقابل حل می رساند. با این استدلال، کونیگ تصور می‌کرد که عدم امکان نظم دادن به خاندان سلطنتی را به خوبی اثبات کرده است و زرملو را به طور غیرقابل جبرانی رد کرده است. در واقع، استدلال کونیگ دارای نادرستی هایی است که خواننده می تواند به تنهایی آنها را شناسایی کند و در هر صورت بعداً در توضیح خود به آنها اشاره خواهیم کرد.

بنابراین وضعیت به نقطه شروع باز می گردد و می توانیم دوباره از خود بپرسیم: آیا قضیه زرملو صحیح است یا خیر؟ آیا باید آن را بپذیریم یا رد کنیم؟ این فرض که حاصلضرب دکارتی یک خانواده نامتناهی از مجموعه‌های غیرخالی غیرخالی باقی بماند چقدر قابل قبول است؟ در واقع، در حال حاضر، تنها می‌توانیم به طور منطقی اعتراف کنیم که زرملو ثابت کرده است - اگر نه دقیقاً هر مجموعه غیر خالی را می‌توان به خوبی سفارش داد - حداقل این که این گفته درست است، اگر فرضیه ذکر شده را بپذیریم.

اما، همانطور که بورل چند سال پس از کار زرملو مشاهده کرد، واقعیت این است که این دو گزاره، اگرچه ظاهراً بسیار از یکدیگر دور هستند، در عوض معادل هستند: دو روی یک سکه، دو روش متفاوت برای بیان یک چیز. بنابراین Zermelo به هیچ وجه ثابت نکرده بود که هر مجموعه غیر خالی را می توان به خوبی سفارش داد، بلکه فقط بر ارتباط بین این جمله و دیگری در محصولات دکارتی تأکید کرد. با جزئیات بیشتر، او نشان داده بود که شرط دوم برای اولی کافی است. گزاره دوم در حال حاضر معمولاً بدیهی ضربی نامیده می شود . قضیه اول، نادرست، زرملو (در واقع، به طور دقیق، اصلاً قضیه ای نیست که توسط زرملو اثبات شده باشد). همانطور که گفته شد، بورل خاطرنشان کرد که اصل ضربی نیز شرط لازم برای قضیه زرملو است و بنابراین معادل آن است. بنابراین، در پایان، علیرغم مشارکت زرملو، مشکل نظم خوب در آغاز قرن گذشته یک مشکل باز باقی ماند.

پارادوکس ها

در واقع، در آن سال‌ها در آغاز قرن بیستم، چیزی بدتر از توسعه نظریه مجموعه‌ها که هنوز جوان بود، مختل شد. فرگه مراقب بود که چارچوب بدیهی ساده ای داشته باشد که بر دو مفهوم ابتدایی، مجموعه و ویژگی ، و بر چند گزاره ظاهراً معقول، که به عنوان بدیهیات تثبیت شده بودند، مبتنی است: به ویژه، علاوه بر اصلی به نام امتداد. ، که از برابر بودن دو مجموعه با عناصر یکسان پشتیبانی می کند، اصل درک که طبق آن هر ویژگی یک مجموعه را تعریف می کند. اما در سال 1901، برتراند راسل مشاهده کرد که این گفته آخر متناقض است و پارادوکس معروف خود را برای رد آن پیشنهاد کرد.

پارادوکس راسل اشاره ای دور به پارادوکس معروف دروغگو است که به اپیمنیدس باستانی کرت نسبت داده می شود. همچنین توسط سنت پل در نامه به تیتوس گزارش شده است و وضعیت شخصی را پیشنهاد می کند که می گوید: "دروغ می گویم" اما با گفتن آن دقیقاً دروغ می گوید اگر حقیقت را بگوید (دایره ای باطل بدون هیچ راه گریز یا توضیحی). ). علاوه بر این، بسیاری از نسخه‌های محبوب پارادوکس راسل، حتی برای کسانی که در ریاضیات یا نظریه مجموعه‌ها متخصص نیستند، قابل دسترسی است. به عنوان مثال، گرلینگ و نلسون در سال 1908، هنوز ریاضیات و لغت نامه ها را با هم ترکیب می کنند، در مورد صفت هایی صحبت می کنند که خودشان را توصیف می کنند. به عنوان مثال، صفت short واقعا کوتاه است، در حالی که طولانی طولانی نیست. ما یک صفت جدید X را برای تعریف ویژگی عدم توصیف خود معرفی می کنیم. سپس X دقیقاً زمانی که قادر به انجام این کار نیست، خود را توصیف می کند: دوباره، وضعیتی بدون توضیح ممکن. نسخه محبوب دیگری از پارادوکس توسط خود راسل در سال 1918 ارائه شد و در مورد کشوری صحبت می کند که در آن آرایشگری وجود دارد که همه را می تراشد و فقط کسانی را می تراشد که خود را اصلاح نمی کنند. سوال این بار این است: چه کسی آرایشگر را می تراشد؟ در واقع، آرایشگر خودش را می تراشد اگر و فقط اگر خودش را نتراشد. آخرین نسخه محبوب، که توسط ریاضیدان انگلیسی Jourdain در سال 1913 ارائه شد و به عنوان مثال در [3] گزارش شد، به یک ورق کاغذ نیاز دارد: در یک طرف می خوانیم "گزاره پشتی درست است"، در طرف دیگر "گزاره در مورد" پشت آن دروغ است." بنابراین، اگر بخواهیم به هر دو گزاره اعتبار بدهیم، باید توجه داشته باشیم که گزاره اول دقیقاً در صورتی درست است که نادرست باشد.

همانطور که گفته شد، پارادوکس راسل تضادهای قبلی را در نظریه مجموعه‌ها بازتولید می‌کند، همانطور که فرگه آن را طرح‌ریزی کرد. برای معرفی آن، باید بر یک فرض آشکار توافق کنیم و بدون رسوایی بپذیریم که یک مجموعه می تواند همزمان عنصری از یک مجموعه باشد. به عنوان مثال، هر مجموعه A بخشی است، به عنوان یک عنصر، از مجموعه زیر مجموعه های A. سپس می توانیم از خود بپرسیم که آیا مجموعه A می تواند به عنوان یک عنصر به خودش تعلق داشته باشد و همچنان ویژگی "A متعلق به خودش است" را جدا کنیم یا حتی (به احتمال زیاد) نفی "A متعلق به خودش نیست". طبق اصل درک فرگه، این ویژگی آخر مجموعه B را تعیین می کند، مجموعه ای که شامل همه و فقط مجموعه هایی است که به خودشان تعلق ندارند. سوالی که از خود می پرسیم این است: آیا B به خودش تعلق دارد؟ اما پاسخ، بار دیگر، یک دور باطل است که هیچ راه خروجی ندارد: B متعلق به خودش است اگر و فقط اگر شرط تعلق به B را برآورده کند و بنابراین اگر و فقط اگر به خودش تعلق نداشته باشد.

راسل در نامه ای در سال 1902 تناقض خود را به فرگه منتقل کرد و فرگه آن را در سال 1903 به عنوان ضمیمه کار خود منتشر کرد [4] و با تأسف اظهار داشت که «برای یک نویسنده علمی ناخوشایندتر از این واقعیت است که پس از اتمام کار. یکی از پایه های آن متزلزل شده است». در واقع، کشف و رواج پارادوکس راسل نه تنها رویکرد فرگه به نظریه مجموعه‌ها، بلکه خود نظریه مجموعه‌ها را نیز با بحران جدی مواجه کرد: چگونه می‌توانیم به مطالعه و کاوش عمیق‌تر در موضوعی ادامه دهیم که در آن چنین آشکار و (در مجموع) تناقضات ابتدایی؟

فراتر از تلخی فرگه، واکنش دنیای ریاضی گسترده، بحث برانگیز، متنوع و پیچیده بود. در همان سالها، تناقضات دیگری در مبانی ریاضیات و به ویژه در نظریه مجموعه ها پدیدار شد که با پارادوکس راسل همراه شد و کنش انتقادی و شاید متلاشی کننده آن را برجسته کرد. به دلیل ریچارد و بری، به ذکر استدلالی محدود می‌شویم، که با اثبات ادعایی کونیگ (که در بالا به آن اشاره شد) تشابهات قوی دارد در مورد این واقعیت که مجموعه واقعی‌ها را نمی‌توان به خوبی مرتب کرد. در واقع، اجازه دهید نسخه بری از پارادوکس را در نظر بگیریم. در آن، حساب و دیکشنری دوباره با هم مخلوط شده و اعداد طبیعی که حداقل به یک صورت با کمتر از چهل هجا در زبان ایتالیایی قابل تعریف هستند، بحث شده است. از آنجایی که هجاهایی که باید از آنها استفاده کنیم فقط یک کمیت محدود هستند و دنباله‌های احتمالی آنها به طول 40 به همان اندازه محدود هستند، نتیجه می‌گیریم که اعدادی که می‌توان از این طریق تشکیل داد، دوباره یک کمیت محدود هستند. بنابراین طبیعی‌هایی وجود دارند که به هیچ وجه با کمتر از 40 هجا در ایتالیایی قابل بیان نیستند و بنابراین، از اصل حداقل، استنباط می‌کنیم که n اول طبیعی با این ویژگی وجود دارد: n کوچکترین عدد طبیعی است که نمی‌تواند. با کمتر از چهل هجا در زبان ایتالیایی تعریف کنید. اما یک بررسی سریع نشان می دهد که هجاهایی که فقط برای توصیف n استفاده شده اند کمتر از چهل هستند (38، خطاها به استثنای). بنابراین ما با یک تناقض روبرو هستیم.

همانطور که مشاهده می شود، در این فضای بحرانی عمیق، مسئله قضیه زرملو ممکن است بسیار نسبی و حاشیه ای به نظر برسد و در مواجهه با مشکلات فوری تر و اولویت های مطلق تر، مانند درک و به نحوی غلبه بر تناقضات، علاقه خود را از دست بدهد. که پایه‌ها و توسعه نظریه مجموعه‌ها و شاید خود ریاضیات را تضعیف می‌کند و به طور منسجمی کل ساختار آن را بازسازی می‌کند.

چگونه از پارادوکس جلوگیری کنیم

همانطور که گفته شد، تناقضات راسل، ریچارد، بری و دیگران به واکنش‌های متعدد و گاهی متضاد منجر شد، اما با نوعی لایت موتیف مشترک: نیاز به بازاندیشی و درک ماهیت واقعی ریاضیات. اکنون - به طور تقریبی - انجام ریاضیات به معنای اثبات قضایا است، حداقل بر اساس یک دیدگاه بسیار رایج و مطمئناً متاثر از بحثی که دقیقاً در آن سال‌های اوایل قرن بیستم درگرفت. از سوی دیگر، هر متن ریاضی (جبر، تجزیه و تحلیل یا هندسه) گواهی می دهد که یک قضیه با استدلال بر روی نتایج از پیش تعیین شده اثبات می شود. دقیقاً به همین دلیل، قضیه اول یک کتاب نمی تواند به چیزی که قبلاً ثابت شده است اشاره کند و باید مبتنی بر چیزی باشد که آنقدر بدیهی باشد که همه آن را بپذیرند: آن قضایا، که معمولاً آنها را بدیهیات می نامیم.

این تصور از ریاضیات، به عنوان علمی که قضایا را از بدیهیات به دست می‌آورد، اصلاً جدید نبود و در واقع به دنیای کلاسیک یونان و به‌ویژه به اقلیدس بازمی‌گردد. علاوه بر این، خود کلمه بدیهیات از یونانی باستان مشتق شده و به چیزی اشاره می کند که در خور توجه و اعتماد است. اولین کسی که از آن استفاده کرد ارسطو بود، برای اشاره به «گزاره‌ای که برهان از آن شروع می‌شود و همه می‌توانند از آن استفاده کنند، زیرا به وجود بودن تعلق دارد». آثار اقلیدس - عناصر او - بر این نقش بدیهیات در توسعه ریاضیات، به عنوان مبنای شهودی لازم برای هدایت نمایش ها تأکید کرده بودند.

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

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

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

در هر صورت، ویژگی خوب دیگری وجود دارد که می توان تأکید کرد که یک نظام بدیهی شایسته نام باید علاوه بر انسجام، کامل بودن را نیز داشته باشد: به عبارت دیگر، توانایی نشان دادن برای هر گزاره ممکنی که به آن مربوط می شود، یا گزاره خود یا نفی آن (اما البته نه هر دو تا فدای انسجام نشود). رویای هیلبرت این بود که بتواند کل ساختار ریاضیات را به‌عنوان خانواده‌ای از سیستم‌های بدیهی، با قواعد استنتاج خوب خود، همه منسجم و کامل و در نتیجه قادر به تسلط بر هر سؤالی در هر بخش تحقیقاتی بدون تناقض بسازد.

این تصور، و اهمیت روش بدیهی، قبلاً - حداقل در جنین - در آثاری که هیلبرت در سال 1899 به ترتیب کامل هندسه ابتدایی اختصاص داد (" Grundlagen der geometrie ") و سال بعد به تأملی مشابه در اعداد واقعی (" Über der zahlengriff ") اگرچه، صادقانه بگویم، رسمی شدن ایده های هیلبرت و برنامه او هنوز باید چند سال صبر می کرد و تنها در سال 1925 بیان صریح آن در رساله " در مورد بی نهایت " بود. آنچه پس از آن انتشار اتفاق افتاد، و قضایای ناقص بودن نتیجه گودل، نقطه شروع بسیار خوبی برای بسیاری از مقالات توصیفی بود (و بوده است).

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

انسجام (بدیهیات باید از هرگونه تناقض احتمالی که می تواند اعتبار آنها را در آینده باطل کند) اجتناب کند.

کامل بودن (بدیهیات باید به ما اجازه دهند که برای هر گزاره ممکن، خود گزاره یا نفی آن را ثابت کنیم).

همانطور که ذکر شد، اهمیت شرط انسجام قبلاً برای هیلبرت در سال 1900 آشکار بود، اگر در دومین کنگره بین‌المللی که در پاریس برگزار شد، در فهرست معروف مسائل ریاضی که او در دومین کنگره بین‌المللی ارائه کرد، تصمیم گرفت که مسئله انسجام حساب را مطرح کند. در این صورت، آخرین شرط لازم برای ذکر این نکته وجود دارد که یک سیستم ریاضی خوب باید دارای استقلال باشد: به عبارت دیگر، همه بدیهیات سیستم باید در واقع ضروری باشند و نباید این اتفاق بیفتد که، شاید به صورت پنهان و غیرمستقیم، یکی آنها از دیگران به عنوان پیامد آنها ناشی می شوند. در آن صورت، زائد خواهد بود، به یک قضیه تبدیل می شود و می تواند از فهرست بدیهیات حذف شود.

حالا اجازه دهید در نهایت به نظریه مجموعه ضعیف خود بازگردیم، که از پارادوکس راسل و سایر تضادهای مشابه آنقدر متزلزل و آشفته شده ایم. با پیروی از دیدگاه هیلبرت و روش بدیهی، زرملو تلاش کرد نظریه مجموعه‌های کانتور را با عبارات غیر متضاد فرموله کند. اول از همه، زرملو نگران تضعیف مناسب اصل درک فرگه بود. در واقع در آن گزاره و آزادی متعاقب آن برای تشکیل مجموعه هایی که از هر ویژگی شروع می شود، منشأ پارادوکس راسل نهفته بود. سپس زرملو پیشنهاد کرد که آن را با چیزی که او اصل انزوا می‌نامید جایگزین کند، که بله، امکان ساخت مجموعه‌هایی از عناصر را می‌دهد که خاصیت خاصی را برآورده می‌کنند، اما تنها با بریدن آنها در یک مجموعه موجود دیگر. به عنوان مثال، با اشاره به پارادوکس راسل، برای هر مجموعه A می توانیم مجموعه ای از مجموعه های X را بسازیم که متعلق به A هستند و عناصر خودشان نیستند، اما به صراحت مجاز نیستیم مجموعه ای از تمام مجموعه هایی را که به آن تعلق ندارند تشکیل دهیم. خودشان

سپس زرملو اصول دیگر فرگه را پذیرفت، به عنوان مثال، امتدادی که بیان می‌کند دو مجموعه با عناصر یکسان برابر هستند، و به اضافه کردن بدیهیات دیگری که وجود مجموعه خالی و مجموعه نامتناهی را تضمین می‌کنند و ساخت‌های ابتدایی را مجاز می‌کنند، می‌اندیشید. مجموعه ها مانند اتحاد، مجموعه قطعات، جفت و غیره. سیستم بدیهی زرملو برای نظریه مجموعه ها، که برای اولین بار در سال 1908 در [5] ظاهر شد، در نهایت شامل گزاره ای شد که ما آن را به خوبی می دانیم، یعنی آنچه را که قضیه زرملو یا در فرمول معادل آن، اصل ضربی نامیدیم. برای دقیق بودن، نسخه ای که با آن این گزاره در فهرست زرملو ظاهر شد، یک نسخه دیگر بود، و اظهار داشت که "اگر A مجموعه ای از مجموعه های جفتی غیرخالی X باشد، مجموعه S وجود دارد که هر X را دقیقاً در یک عنصر قطع می کند. و به عبارت دیگر در هر کدام یک عنصر را انتخاب می کند

این فرمول جدید که توسط راسل در سال 1906 ارائه شد، با این حال به روشی بسیار ساده نشان داده شده است که معادل اصل ضربی است. در آنجا، در واقع، بیان شده است که حاصلضرب دکارتی یک خانواده نامتناهی از مجموعه‌های غیر خالی، غیرخالی می‌ماند. حال اگر لحظه‌ای تأمل کنیم که حاصلضرب دکارتی یک خانواده از مجموعه‌ها چگونه تعریف می‌شود، یا شاید برویم و به متون ریاضی در این مورد مراجعه کنیم، متوجه می‌شویم که اگر {Ai : i ÎI} خانواده ما و من باشد. مجموعه شاخص های مربوطه، سپس P iÎI Ai به عنوان مجموعه ای از توابع f از I در È iÎI Ai معرفی می شود که یک عنصر از Ai را با هر i مرتبط می کند. بنابراین، اظهار وجود چنین تابعی از f (همانطور که بدیهیات ضربی انجام می دهد) به این معنی است که اعتراف می کنیم که راهی برای انتخاب یک عنصر در هر Ai وجود دارد، که ما را به راحتی به فرمول راسل که در بالا ذکر شد هدایت می کند. در واقع، روش دیگری برای بیان همان گزاره وجود دارد که به آن اصل انتخاب می گویند و کمابیش به این صورت است: "اگر A یک خانواده غیر خالی از مجموعه های غیر خالی X باشد، تابع f وجود دارد. تعریف شده بر روی A که یک عنصر f(X) از را مرتبط می کند

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

زرملو پس از تکمیل فهرست خود، به درستی مراقبت کرد که مطابق با روح هیلبرت، انسجام آن را تأیید کند. اما او باید صادقانه اعتراف می‌کرد که نمی‌توانست نشان دهد که بدیهیات او از هرگونه تناقضی اجتناب می‌کنند، حتی اگر خوشبختانه، همه تناقض‌هایی را که در آن سال‌ها پدیدار شد، از جمله مهم‌تر از همه پارادوکس‌های راسل، کنار گذاشته و بر آن غلبه کنند.

چند سال بعد، فرانکل (به همراه اسکلم و فون نویمان) سیستم زرملو را مجدداً کار کرد و تجدید نظری در آن پیشنهاد کرد [6] که معمولاً نظریه زرملو-فرانکل نامیده می شود و با حروف اول نام کسانی که دارای آن بودند مشخص می شود. آن را ساخت، ZF. فواید فرمول جدید چه بود؟ اول از همه، زبان منطقی صوری دقیق‌تر و دقیق‌تری را اتخاذ کرد که از برخی ابهامات زبانی و برخی نادرستی‌های نسخه اصلی زرملو اجتناب می‌کرد. ثانیاً، فرانکل اصل بحث برانگیز انتخاب را رد کرد. گزاره‌های باقی‌مانده، همانطور که قبلاً ذکر شد، به‌درستی بازنگری و ادغام شدند. به عنوان مثال، برخی از افزونگی‌های سیستم اولیه زرملو حذف شد، بنابراین الزام استقلال را تضمین کرد. به ویژه، پس از آن، اصل اساسی انزوا (تضعیف اصل درک فرگه) دوباره اقتباس شد و همچنین نام خود را تغییر داد و به اصل جدایی تبدیل شد. علاوه بر این، بیانیه جدیدی به نام اصل بنیاد یا قاعده مندی اضافه شد که برای جلوگیری از پارادوکس راسل و سایر تناقضات مشابه، از این که هر مجموعه ای از اشیایی که به ذهن می آید یک مجموعه است و به تفصیل بیان می کند که «هر غیر از مجموعه خالی X حاوی یک عنصر Y است که به عنوان یک مجموعه، جدا از الاستیسیته کافی در این رابطه است. ترتیب فرانکل، اگر نقص‌های خاصی از رویکرد زرملو را برطرف می‌کرد، شایستگی‌های خود را حفظ می‌کرد، به‌ویژه پارادوکس راسل را مستثنی می‌کرد. در اینجا دلیل آن است. اول از همه، دوباره به یاد بیاوریم که هر مجموعه ممکن C از مجموعه ها یک مجموعه نیست. گاهی اوقات این درست است، به عنوان مثال اگر C مجموعه ای از زیرمجموعه های یک مجموعه معین A باشد: در واقع بدیهی صریح ZF وجود دارد - یعنی قدرت - که تضمین می کند که C در این مورد یک مجموعه است. اما، بارها، دوباره بر اساس ZF، این بیانیه کاملاً نادرست است.

قضیه مجموعه C از همه مجموعه ها یک مجموعه نیست

این مدرک به درستی پارادوکس راسل را تطبیق می دهد. در واقع، اجازه دهید بر اساس تناقض فرض کنیم که C یک مجموعه (غیر خالی) است. سپس از اصل انزوا یا، اگر ترجیح می‌دهیم آن را با نام جدید بنامیم، از جداسازی استفاده می‌کنیم و مجموعه B از عناصر X از C را تشکیل می‌دهیم که به خودشان تعلق ندارند. سپس B [B اگر و فقط اگر B” B، که تضاد ایجاد می کند و منجر به انکار فرضیه غیرمجاز، یعنی اینکه C یک مجموعه است، می شود.

سپس ثابت می شود که:

قضیه هیچ مجموعه ایکس متعلق به خودش نیست

در واقع، اجازه دهید دوباره با تضاد پیش برویم و فرض کنیم یک مجموعه X [X داریم. از Isolation استفاده می کنیم و مجموعه Y از Z را می سازیم [ اکنون از مبانی Axiom استفاده می کنیم و یک عنصر U [Y جدا از Y را به دست می آوریم. اما U [Y U [U را تحمیل می کند، که تضاد مورد نظر را ایجاد می کند.

در این مرحله، پارادوکس راسل به راحتی برطرف می شود. مجموعه مجموعه هایی که به خودشان تعلق ندارند توسط قضیه 4.2 با مجموعه همه مجموعه ها منطبق می شوند و بنابراین طبق قضیه 4.1 یک مجموعه نیست. اما دیگر فکر کردن به اینکه متعلق به خود است یا نه چندان منطقی به نظر نمی رسد: راه حلی که شاید بتواند همان حس ناامیدی را به خواننده منتقل کند که داستان های پلیسی خاصی که ساعت ها فرد را با تنش خود پرچ می کند و سپس به پایان می رسد. با این کشف پیش پا افتاده که قاتل ساقی است. با این حال، هنوز هم یک راه حل و کاملاً منطقی است. بنابراین، ما می توانیم ادامه دهیم.

شاید، از آنجایی که ما در مورد پارادوکس ها هستیم، ارزش آن را داشته باشد که چند کلمه در مورد بری، یا ریچارد (یا کونیگ یا هر چیزی که ترجیح می دهید او را نامگذاری کنید) بگویید. اما نقص در اینجا در سردرگمی که قبلاً تأکید شده است بین ریاضیات و زبان و درک نادرست از معنای واقعی تعریف یک عدد با یک جمله کامل در ایتالیایی (یا در انگلیسی، فرانسوی و غیره) نهفته است: صفر نامیده می‌شود. برای مثال، نه قانون جهانی ریاضی، بلکه فقط یک قرارداد گذرا. همین امر در مورد نامی که می خواهیم به نظم ظاهراً خوب خانواده سلطنتی اختصاص دهیم نیز صدق می کند. بنابراین هیچ چیز قطعی در نحوه فراخوانی اعداد یا روابط وجود ندارد و هیچ چیز دقیقی در آنچه می توانیم در مورد آنها استنباط کنیم وجود ندارد.

برای خاتمه پاراگراف به مشکل انسجام ZF اشاره می کنیم. همانطور که به یاد آوردیم، زرملو نتوانست آن را اثبات کند (به دلیل سیستم بدیهی اولیه خود). با این حال، هیچ کس حتی نتوانست آن را رد کند، و تا به امروز هم کسی موفق نشده است که پارادوکس های جدیدی ایجاد کند. از سوی دیگر، یکی از پیامدهای قضایای ناتمامیت بنیادی گودل در سال 1930 این است که، حتی اگر ZF منسجم باشد و در نتیجه تناقضات را حذف کند، این ZF همان ZF نیست که موفق می شود آن را به عنوان قضیه خاص خود اثبات کند: بدون خود گواهی در سبک مورد نظر هیلبرت در اینجا امکان پذیر است.

و اصل انتخاب (در صورت‌بندی‌های مختلف آن)؟ آیا از فهرست مبانی ZF خارج شده و به قلمرو نامشخص قضایای قابل اثبات یا تناقض بازگشته است، آیا می توان در واقع نمونه های متقابل را اثبات کرد یا یافت؟ این موضوعی است که سعی خواهیم کرد در پاراگراف بعدی به آن بپردازیم.

اصل انتخاب

همانطور که گفتیم، چیزی که ما اصل انتخاب می نامیم در واقع یکی از فرمول بندی های ممکن یک گزاره ریاضی بسیار چند وجهی است، که می تواند به طور بی تفاوت و به طور معادل در ظاهر بدیهیات ضربی به ظاهر بی ضرر یا در موارد بحث برانگیز ظاهر شود. قضیه Zermelo یا حتی در نسخه های مجموعه انتخاب پیشنهاد شده توسط راسل. و فهرست مطمئناً به اینجا ختم نمی‌شود و می‌تواند بسیار طولانی‌تر باشد، زیرا خواننده علاقه‌مند می‌تواند به راحتی با مراجعه به کتاب Jech [7] یا مقاله بعدی [8] یا بسیاری از سایت‌های اینترنتی اختصاص داده شده به موضوع (جایی که فرمول‌بندی‌های متعدد دیگری از اصل انتخاب ارائه شده است). در هر صورت، در اینجا، در محدوده محدود این صفحات، لازم است به یکی دیگر اشاره کنیم، بسیار دشوار و پیچیده و در عین حال محبوب، زیرا اغلب در نمایش ها استفاده می شود و بنابراین به راحتی در کتابچه های ریاضی پیدا می شود: لمای زورن. این اصل، معادل تمام موارد قبلی، توسط زورن در سال 1935 شناسایی شد [9] و بیان می‌کند: «اجازه دهید بپذیریم که مجموعه‌ای غیر خالی A داریم و تا حدی با یک رابطه <= مرتب شده است. سپس فرض کنیم که هر زیر مجموعه سپس A حداکثر عناصر را با توجه به <=; به عبارت دیگر مقداری m Î A وجود دارد که لزوما از همه عناصر دیگر A بزرگتر نیست، اما با این وجود عناصر بزرگتر از خود را نمی پذیرد، به این معنا که هر b Î A قابل مقایسه با m با توجه به <= منجر به <= m” .

باید گفت که نام لما، مانند قضیه زرملو، نادقیق و گمراه کننده است. بنابراین، برای پاک کردن میدان سوء تفاهم، تکرار می‌کنیم که حتی در این مورد، لمای زورن هیچ چیز قطعی را نشان نمی‌دهد، به جز این واقعیت که بیان آن در واقع معادل اصل انتخاب در صورت‌بندی‌های مختلف آن است. همچنین باید اذعان داشت که لمای زورن بیانی بسیار پیچیده‌تر و غیرقابل هضم‌تر از سایر گزاره‌های معادل دارد و با این وجود، بی‌واسطه‌ترین و مستقیم‌ترین مورد استفاده در کاربردها است (که به زودی فرصت ذکر نمونه‌هایی از آن را خواهیم داشت).

اما در این مرحله، صرف نظر از نسخه خاصی که قصد داریم اصل انتخاب را با آن ارائه کنیم، باید همان سوالی را از خود بپرسیم که قبلاً کانتور و زرملو را مورد توجه قرار داده بود: اصل انتخاب (یا قضیه زرملو یا اصل موضوعی ضربی یا زورن). لم) درست است یا نادرست؟ به نظر می رسد هیچ پیشرفتی از همه ملاحظاتی که در این مدت ایجاد کرده ایم حاصل نشده است. با این حال، ما نسبت به کانتور و زرملو در سال 1904 مزیت هایی داریم، زیرا آنها هنوز مجبور بودند به رویکردهای ساده لوحانه نظریه مجموعه ها مانند فرگه مراجعه کنند و در عوض می توانیم سیستم ZF پیشرفته تری داشته باشیم. بنابراین سوال ما را می توان به صورت زیر فرموله کرد. اجازه دهید ابتدا فرض کنیم که ZF منسجم است: آیا اصل انتخاب با ZF قابل اثبات است؟ یا در صورت وجود می توان انکار آن را از ZF استنباط کرد؟

اما حتی اشاره به ZF هم نمی تواند وضعیت را برای ما روشن کند. این در واقع درست است که کورت گودل در سال 1938 در [10] ثابت کرد که

قضیه اگر ZF سازگار باشد، برای ZF غیرممکن است که خلاف اصل انتخاب را ثابت کند.

مجدداً با فرض سازگاری ZF و حذف تناقضات، این قضیه را می توان به عنوان استدلالی به نفع اصل انتخاب تفسیر کرد. با این حال، از این منظر، تطابق بین بدیهیات و نفی کاملاً مساوی است، زیرا تنها چند سال بعد، در سال 1963، پی کوهن [11] به این نتیجه رسید:

قضیه اگر ZF سازگار باشد، برای ZF نیز غیرممکن است که اصل انتخاب را اثبات کند.

بنابراین، ZF یک سیستم کامل از بدیهیات نیست و اصل انتخاب خود این شرط کامل بودن را تضعیف می کند، زیرا، نه تایید و نه رد، می تواند توسط ZF ثابت شود. به عبارت دیگر، دوباره می‌توانیم اصل انتخاب یا نفی آن را به‌عنوان یک گزاره جدید برای افزودن به پایه‌های ZF بپذیریم. برای قضایای گودل و کوهن فوق الذکر، هر دو گزینه (اگرچه در تقابل با یکدیگر) به یک اندازه قابل قبول هستند: اولی که با دیدگاه قدیمی زرملو مطابقت دارد، اما دیگری که آن را رد می کند.

از سوی دیگر، با توجه به اینکه گزاره ما از دقت مکانیکی قضایا می گریزد و به حوزه مبهم و نامشخص بدیهیات باز می گردد، می توانیم به بررسی و قضاوت آن از منظر شهود صرف بازگردیم و از خود بپرسیم: آیا بدیهیات انتخاب قابل قبول تر است یا انکار آن؟ اما حتی زمانی که در این عبارات تقلیل داده شود، سوال به وضوح بیشتر نمی رسد. واقعیت این است که اصل انتخاب فرمول بندی های ممکن زیادی دارد و آنچه برای یکی بدیهی به نظر می رسد برای دیگری بسیار کمتر قابل قبول است. برای بیان آن با جی. بونا، "اصول ضربی آشکارا درست است، اصل نظم خوب آشکارا نادرست است و در مورد لم زورن، چه کسی قادر به درک چیزی در مورد آن است؟" مشکل اینجاست که این شوخی (یا جوک فرضی) از حد و مرزهای جوک فراتر می رود و واکنشی بسیار منطقی و بسیار متغیر را در مقابل سه عبارت درگیر (که با این حال معادل یکدیگر هستند) کاملاً توصیف می کند.

با این حال، ویژگی مشترکی وجود دارد که آنها (همراه با جملات دوقلو دیگر) دارند و آنها را در واقع مشکوک می کند و آنقدرها که می خواهید قانع کننده نیستند. همه وجود یک شی را تأیید می کنند (یک تابع انتخاب، یک مجموعه انتخاب، یک نظم خوب، یک عنصر حداکثر، بسته به مورد) اما هیچ کس به ما نمی گوید که چگونه واقعاً چیزی را بسازیم که وجود آن را تضمین می کند. برای روشن شدن این نکته، می‌توان یک بار دیگر از برتراند راسل و مشاهدات او نقل کرد: «انتخاب یک جوراب از هر جفت بی‌نهایت جوراب، مستلزم اصل انتخاب است، در حالی که برای کفش، اصل موضوع دیگر ضروری نیست».

در واقع، اگر با تعداد زیادی جفت (احتمالا بی نهایت) کفش مواجه باشیم، برای انتخاب یک کفش از هر جفت، یک معیار کلی واضح داریم، مثلاً همیشه کفش راست یا چپ را انتخاب کنیم. اما وقتی با بی نهایت جفت جوراب روبه‌رو می‌شویم، همان روش دیگر جواب نمی‌دهد، زیرا جوراب‌های یک جفت یکسان هستند و هیچ اطمینانی وجود ندارد که جورابی که یک روز صبح در سمت راست می‌پوشیم، همان جورابی نیست که در سمت چپ می‌پوشیم. دفعه بعد در چنین موقعیت هایی است که برای به دست آوردن تابع انتخابی f، فقط می توانیم وجود آن را فرض کنیم. با این حال، هنگامی که به اثبات های بعدی ادامه می دهیم و f خود را در آنها دخالت می دهیم، صادقانه باید بپذیریم که f یک عمل ایمانی است و در واقع ما قادر به ارائه هیچ مثال صریح یا الگوریتم ساختی نیستیم. در واقع، یکی از استدلال‌های اصلی علیه اصل انتخاب دقیقاً ویژگی غیر سازنده آن است.

و با این حال، دلایل بسیار خوبی برای حمایت از اصل ما وجود دارد. در واقع، بسیاری از قضایای اساسی در جبر، در جبر خطی، در توپولوژی، در تجزیه و تحلیل ریاضی، اثبات خود را بر اساس استفاده قاطع از اصل انتخاب استوار می‌کنند: سیستم ZF به تنهایی، یتیم انتخابی، قادر به اثبات آنها نیست. برای مثال، در کتاب‌های درسی جبر می‌خوانیم که یک حلقه جابجایی واحد همیشه ایده‌آل‌های حداکثری را می‌پذیرد - یک قضیه معروف Krull در سال 1929 - اما، وقتی به اثبات بعدی نگاه می‌کنیم، بسیار محتمل است که لم زورن را درگیر کنیم (و در هر صورت). اصل موضوع انتخاب در برخی از فرمول ها). به همین ترتیب، ما عادت داریم در جبر خطی بپذیریم که هر فضای برداری یک مبنا و یک بعد دارد. این قطعیت نیز به طور قاطع از اصل انتخاب که از طریق لمای زورن یا از طریق قضیه زرملو استفاده می شود، ناشی می شود. ما می‌توانیم به ذکر مثال‌های جدید برای چند صفحه ادامه دهیم، که از تجزیه و تحلیل (مانند قضیه هان-باناخ) یا از توپولوژی (مانند قضیه Tychonoff) گرفته شده است. در همه این موارد، بدیهیات انتخاب ابزاری اساسی برای اثبات است، تا آنجا که اگر لحظه‌ای از آن دست برداریم و در مسیر انکار قدم برداریم، باید برای بازنگری در بسیاری از یقین‌های خود آماده شویم. اصل انتخاب می تواند یک گزینه اطمینان بخش باشد که می تواند حساسیت ما را به عنوان ریاضیدانان درست اندیش آرام کند.

چگونه معجزات را توضیح دهیم

و در اینجا ما در نهایت به قضیه Banach-Tarski و معجزه ادعایی ضرب کره آن برمی گردیم تا به دنبال توضیحی باشیم. پس از همه ملاحظات پاراگراف های قبلی، می توانیم به طور منطقی حرکت در ریاضیاتی را بپذیریم که دارای ZF و، چرا که نه؟، همچنین اصل موضوع انتخابی به عنوان پایه های آن است. نتیجه معروف این فرض، قضیه ای از تحلیل ریاضی (توسط جوزپه ویتالی [12]) است که بیان می کند:

قضیه زیر مجموعه هایی از خط واقعی R هستند که قابل اندازه گیری نیستند.

قضیه ویتالی بیان می‌کند که در حال حاضر در خط مستقیم، برای بعد 1، و حتی در بخش بسته اکسترنال‌های 0 و 1، می‌توان مجموعه‌هایی را ابداع کرد که به قدری پیچیده باشد که از هرگونه اندازه‌گیری ممکن فرار کند. همانطور که مشاهده می شود، این یک نتیجه عمیق است و در عین حال، شاید به دلیل عمق بسیار آن، ظاهراً بی ضرر و قابل پذیرش آسان است: نوعی شیطان ریاضی، آن استدلال ها آنقدر ظریف که از هر کنترل شهودی معقولی فراتر می روند و در نتیجه از آن هضم می شوند. تنبلی اگر از روی اعتقاد نباشد. با این حال، هیچ چیز رسوایی. با این حال، در حال حاضر تمام عجایب پارادوکس Banach-Tarski را در جنین گنجانده است: ما در یک لحظه خواهیم دید که چرا. در این رابطه، در واقع هنوز ارزش افزودن این نکته را دارد که نمایش اصلاً سازنده و مستقیم نیست، یعنی به صراحت آن مجموعه بی‌اندازه‌ای را که وعده می‌دهد تولید نمی‌کند، بلکه وجود آن را قاطعانه بر اساس اصل انتخاب استنتاج می‌کند. در واقع، اگر سعی می‌کردیم از استفاده از بدیهیات خود اجتناب کنیم و ترجیح می‌دادیم آن را نادیده بگیریم، با وضعیتی مشابه موارد ذکر شده در پاراگراف آخر مواجه می‌شویم: Solovay [13] در واقع در سال 1970 مدلی از ZF را پیشنهاد کرد (و نه از بدیهیات انتخابی) که در آن هر مجموعه ای از واقعیات دارای یک معیار Lebesgue است.

اما در این مرحله، پس از این انتظار طولانی و آماده‌سازی، در واقع به این نتیجه رسیدیم که از آن شروع کردیم، یعنی پارادوکس Banach-Tarski. قبل از هر چیز، برای پاک کردن میدان از هرگونه سوء تفاهم احتمالی، خوب است روشن شود که اصطلاح پارادوکس در اینجا به همان معنای راسل یا بری به کار نمی رود. این دیگر یک تناقض و ناسازگاری نیست، بلکه یک نتیجه عجیب، عجیب، شگفت‌انگیز و در عین حال کاملاً مطابق با ریاضیات رسمی است.

همانطور که ذکر شد، اثبات پارادوکس باناخ تارسکی به جهاتی، با پیچیدگی‌های بیشتر، استدلال‌هایی را که ویتالی برای خط واقعی به کار می‌برد، دنبال می‌کند. در واقع، به طور دقیق، به تحلیل مشابهی اشاره دارد که توسط هاسدورف در سال 1914 در فضای سه بعدی انجام شد، در مورد سطح کروی S به جای قطعه: با کمک قاطع اصل موضوع انتخاب و با استفاده به همان اندازه اساسی از ویژگی های چرخش در فضای سه بعدی، هاسدورف ثابت کرد که S را می توان به چهار قسمت غیر خالی و ناهمگون تجزیه کرد، که سه قسمت آن با یکدیگر برابرند - و تا اینجا چیز عجیبی وجود ندارد - بلکه برابر با اتحاد آنها هستند (و در اینجا به زمینی منحرف می شود که به نظر می رسد با شهود در تضاد است). باناخ و تارسکی این تجزیه هاسدورف را از سطح خارجی به داخل کره پیش بینی کردند و تکرار شگفت انگیز و قابل توجهی را استنتاج کردند که قبلاً فرصت صحبت در مورد آن را داشته ایم.

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

از سوی دیگر، فرمول های فیزیک ابتدایی به ما یادآوری می کنند که جرم جسمی با چگالی یکنواخت از حاصل ضرب چگالی و حجم به دست می آید. حال، از اصل انتخاب می‌توان نتیجه گرفت که مجموعه‌های بدون اندازه‌گیری وجود دارند و به‌ویژه، در فضای سه‌بعدی معمول، جامدات بدون حجم وجود دارند: این نتیجه‌ای است که قضیه ویتالی و قضیه هاسدورف و باناخ تارسکی مشترک هستند. اما، در مورد دومی، باید توجه داشته باشیم که اگر حجم وجود نداشته باشد و قابل محاسبه نباشد، حتی نمی‌توانیم دو برابر شدن آن را کنترل کنیم: بخش‌هایی از کره بدون اندازه‌گیری می‌توانند دوباره جمع شوند به گونه‌ای که اتحاد آنها دو برابر شود. دقیقاً به این دلیل که آنها از قوانینی فرار می کنند که این اقدام باید به طور منطقی با آنها مطابقت داشته باشد. دقیقاً فقدان حجم است که همراه با استفاده از چرخش های مناسب، امکان ایجاد یک طلسم ریاضی شگفت انگیز اما نه رسواکننده را فراهم می کند. بنابراین، در نهایت، پارادوکس Banach-Tarski، به دور از نقض اصل بقای جرم، نشان می‌دهد که مفهوم حجم بسیار پیچیده‌تر و ظریف‌تر از آن چیزی است که ما ساده‌لوحانه فکر می‌کنیم و اصلاً خودکار نیست یا خوب است. ثابت کرد که همه بدنها، به ویژه تمام بخشهای کره، اندازه خود را دارند. همچنین شایان ذکر است که بر نقش غیرثانویه ای که ویژگی های چرخش کره در یک فضای سه بعدی در نمایش بازی می کند، تأکید شود. به حدی که اگر به بعد 2 برویم، در صفحه دیگر پارادوکس وجود ندارد و تکرارهای جادویی امکان پذیر نیست. برای اصرار بر تشبیه مخاطره آمیز پاراگراف اول، می توان نان یا ماهی یا شمش طلا را ضرب کرد، اما اسکناس را نه.

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

با این حال، از سوی دیگر، می‌توانیم بدانیم که حداقل تعداد قسمت‌هایی که یک کره را می‌توان به آن تقسیم کرد و سپس تکثیر کرد چقدر است. مقاله ای از رافائل ام رابینسون در سال 1947 [14] این کمیت جادویی را 5 تعیین می کند.

این پایان سفر ماست. ما نمی توانیم واکنش خواننده را پیش بینی کنیم. شاید او همان ناامیدی آزاردهنده ای را داشته باشد که خوانندگان کتاب های جنایی خاص، که چند صفحه پیش شرح دادیم، یا شاید مجذوب همه استدلال های سطحی ما شود و به بینش های جدی تری منجر شود (که بتواند آنها را بیابد. به عنوان مثال، در [15]). به نوبه خود، نتیجه گیری یا اخلاقیات دشوار است، غیر از این که شاید بدیهی باشد که ریاضیات علمی ظریف و شایسته احترام است و گاهی اوقات چیزی که ظاهراً نادرست به نظر می رسد (مثل پارادوکس ما) یا آشکارا درست است (مثل عقیده کلاسیک). که دو به علاوه دو همیشه برابر است با چهار) اعماق غیر منتظره را پنهان می کند.

کتابشناسی

[1] S. Banach-A. تارسکی، در مورد تجزیه مجموعه‌ای از نقاط به قسمت‌های متجانس،

مبانی ریاضیات 6 (1924), pp. 244-277.

[2] E. Zermelo، اثبات این که هر مجموعه ای را می توان به خوبی مرتب کرد، سالنامه ریاضی 59 (1904)، ص 514-516.

[3] R. Smullyan، عنوان این کتاب چیست ، زانیچلی، بولونیا، 1981.

[4] G. Frege, Basic Laws of Arithmetic , II, Pohle, Jena, 1903.

[5] E. Zermelo, Investigations into the basics of set theory, I, Mathematical Annals 65 (1908), ص 261-281.

[6] AA Fraenkel، در مبانی نظریه مجموعه کانتور-زرملو، سالنامه ریاضی 86 (1922)، صفحات 230-237.

[7] تی جک، اصل انتخاب ، هلند شمالی، آمستردام، 1978.

[8] T. Jech, About the axiom of choice , pp. 345-370 in Handbook of Mathematical Logic, North Holland, Amsterdam, 1977.

[9] M. Zorn، نکته ای در مورد روش در جبر بینهایت، بولتن American Mathematical Society 41 (1935)، صفحات 667-670.

[10] K. Gödel، سازگاری بدیهیات انتخاب و فرضیه پیوستار تعمیم یافته ، Proc. نات. آکادمی علمی 24, 1938; ان ریاضی مطالعات 3، پرینستون، 1951.

[11] پی کوهن، نظریه مجموعه ها و فرضیه پیوستگی ، بنجامین، نیویورک، 1966.

[12] G. Vitali، در مورد مشکل اندازه گیری گروه از نقاط در یک خط - 1905 در: G. Vitali، آثار در تجزیه و تحلیل واقعی و پیچیده - مکاتبات ، Unione Matematica Italiana، بولونیا، 1984).

[13] R. Solovay، مدلی از نظریه مجموعه‌ها که در آن هر مجموعه واقعی قابل اندازه‌گیری Lebesgue است، Annals of Mathematics 92 (1970)، صفحات 1-56.

[14] RM Robinson، در مورد تجزیه کره ها، Fundamenta Mathematicae 34 (1947)، 246-260.

[15] S. Wagon، پارادوکس Banach-Tarski ، انتشارات دانشگاه کمبریج، کمبریج، 1985.

https://matematica.unibocconi.eu/articoli/matematica-miracoli-e-paradossi

+ نوشته شده در دوشنبه هفتم آبان ۱۴۰۳ ساعت 6:29 توسط علی رضا نقش نیلچی |

ماتریس مجاورت

از ویکیپدیا، دانشنامه آزاد

در نظریه گراف و علوم کامپیوتر ، یک ماتریس مجاورت یک ماتریس مربع برای نمایش یک محدود نمودار . عناصر ماتریس نشان می دهد که آیا جفت رأس در نمودار مجاور هستند یا نه.

در حالت خاص یک نمودار ساده محدود ، ماتریس همجواری یک ماتریس (0/1) است که صفرها روی مورب آن است. اگر نمودار بدون جهت باشد (یعنی همه لبه های آن دو جهته باشد) ، ماتریس مجاورت متقارن است . رابطه بین نمودار و مقادیر ویژه و بردار ویژه ماتریس مجاورت آن در تئوری نمودار طیفی مورد مطالعه قرار گرفته است .

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

فهرست

تعریف [ ویرایش ]

برای یک گراف ساده با مجموعه رئوس U = {u 1 ، ...، u N }، ماتریس مجاورت یک مربع است n × n با ماتریس به طوری که عنصر آن IJ است زمانی که یک یال از راس وجود دارد ui به راسu j و صفر در صورت عدم وجود لبه. [1] عناصر مورب ماتریس همه صفر هستند ، زیرا لبه های یک راس به سمت خود ( حلقه ها ) در نمودارهای ساده مجاز نیستند. همچنین گاهی اوقات در نظریه نمودار جبری جایگزینی عناصر غیر صفر با متغیرهای جبری مفید است. [2]با ذخیره تعداد لبه های بین دو راس در عنصر ماتریس مربوطه و با اجازه دادن به عناصر مورب غیر صفر ، می توان همین مفهوم را به چند نمودار و نمودارهای حلقه ای گسترش داد . حلقه ها ممکن است یک بار (به عنوان یک لبه) یا دو بار (به عنوان دو رخ لبه راس) شمارش شوند ، به شرطی که یک قرارداد سازگار دنبال شود. نمودارهای غیرمستقیم اغلب از قرارداد دوم برای شمارش حلقه ها دو بار استفاده می کنند ، در حالی که نمودارهای جهت دار به طور معمول از قرارداد قبلی استفاده می کنند.

نمودار دو بخشی [ ویرایش ]

ماتریس مجاورت از یک گراف دو بخشی که دو بخش R وs راس می توان در فرم نوشته

${\ displaystyle A = {\ start {pmatrix} 0_ {r، r} & B \\ B ^ {\ mathsf {T}} & 0_ {s، s} \ end {pmatrix}}،}$

که در آن B یک IS R × بازدید کنندگان ماتریس، و 0 R ، R و 0 بازدید کنندگان ، بازدید کنندگان نشان دهنده R × R و بازدید کنندگان × بازدید کنندگان ماتریس صفر است. در این حالت ، ماتریس کوچکتر B منحصراً نمودار را نشان می دهد و قسمتهای باقی مانده A را می توان به عنوان زائد کنار گذاشت. B را گاهی ماتریس biadjacency می نامند .

بعبارت دیگر، اجازه G = ( U ، V ، E ) یک گراف دو بخشی با قطعات U = { تو 1 ، ...، تو تحقیق }، V = { V 1 ، ...، V بازدید کنندگان } و لبه E . ماتریس biadjacency ماتریس r × s 0-1 B است که در آن b i ، j = 1 فقط و فقط اگر ( u i ، v j ) ∈E .

اگر G چند پاراگراف دو پاراگراف یا نمودار وزنی باشد ، عناصر b i ، j به ترتیب تعداد لبه های بین رئوس یا وزن لبه ( u i ، v j ) در نظر گرفته می شوند.

ماتریس همجواری نمودار دو بخشی کاملاً غیر مدول است . این بدان معنی است که تعیین کننده هر زیرماتریک مربع آن −1 ، 0 یا 1+ است.

تغییرات [ ویرایش ]

( ، ب ، ج ) -adjacency ماتریس از یک نمودار ساده است i ، J = اگر ( i ، J ) لبه، است ب اگر چنین باشد، نیست و ج در قطر. ماتریس مجاورت سیدل است (-1، 1، 0) ماتریس -adjacency. این ماتریس در مطالعه نمودارهای کاملا منظم و دو نمودار استفاده می شود . [3]

ماتریس فاصله دارد در موقعیت ( i ، J ) فاصله بین راس پنجم i و پنجم J . فاصله طول کوتاهترین مسیری است که رئوس رابط متصل می کند. تا زمانی که طول لبه ها به طور واضح ارائه نشوند ، طول یک مسیر تعداد لبه های آن است. ماتریس فاصله شباهت به توان بالای ماتریس مجاورت دارد ، اما به جای اینکه فقط بگوییم دو رئوس متصل هستند یا نه (یعنی ماتریس اتصال که حاوی مقادیر بولی است ) ، فاصله دقیق بین آنها را نشان می دهد.

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

نمودارهای بدون جهت [ ویرایش ]

این کنوانسیون به دنبال در اینجا (برای گرافهای بدون جهت) این است که هر یک از لبه اضافه می کند: از 1 به سلول مناسب در ماتریس، و هر حلقه اضافه می کند 2. [4] این اجازه می دهد تا به درجه ای از یک راس به راحتی با در نظر گرفتن مجموع مقادیر پیدا شده است یا در ردیف یا ستون مربوطه در ماتریس مجاورت.

نمودار دارای برچسب	ماتریس همجواری
	${\ displaystyle {\ start {pmatrix} 2 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \ end {pmatrix}}$ مختصات 1–6 هستند.
نمودار نائورو	مختصات 0–23 هستند. زمینه های سفید صفر هستند ، زمینه های رنگی یکی هستند.

نمودارهای هدایت شده [ ویرایش ]

ماتریس مجاورت یک نمودار جهت دار می تواند نامتقارن باشد. می توان ماتریس مجاورت یک نمودار جهت دار را تعریف کرد به گونه ای که

یک عنصر غیر صفر A ij یک لبه از i به j یا نشان می دهد
این نشان دهنده یک لبه از j به i است .

تعریف قبلی معمولاً در تئوری نمودار و تحلیل شبکه های اجتماعی (به عنوان مثال جامعه شناسی ، علوم سیاسی ، اقتصاد ، روانشناسی) استفاده می شود. [5] این مورد اخیر در سایر علوم کاربردی (به عنوان مثال ، سیستم های دینامیکی ، فیزیک ، علوم شبکه) که گاهی اوقات A برای توصیف پویایی خطی در نمودارها استفاده می شود ، بیشتر رایج است. [6]

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

نمودار دارای برچسب	ماتریس همجواری
کارگردان گراف کیلی از S 4	مختصات 0–23 هستند. همانطور که نمودار هدایت می شود ، ماتریس لزوماً متقارن نیست .

نمودارهای بی اهمیت [ ویرایش ]

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

خصوصیات [ ویرایش ]

طیف [ ویرایش ]

ماتریس همجواری یک نمودار ساده بدون جهت متقارن است ، بنابراین یک مجموعه کامل از مقادیر ویژه واقعی و یک بردار ویژه متعامد متعامد دارد. مجموعه مقادیر ویژه یک نمودار طیف نمودار است. [7] معمولاً مشخص کردن مقادیر ویژه با ${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}$

بزرگترین ارزش ویژه $\ lambda _ {1}$ در بالا با حداکثر درجه محدود شده است. این را می توان نتیجه قضیه Perron-Frobenius دانست ، اما می توان آن را به راحتی اثبات کرد. بگذارید v یک بردار ویژه باشد که به آن مرتبط است $\ lambda _ {1}$ وx جزء که در آن V است حداکثر ارزش مطلق است. بدون از دست دادن کلیت ، فرض کنید v x مثبت باشد زیرا در غیر این صورت شما به سادگی بردار ویژه را می گیرید $-v$ ، همچنین به $\ lambda _ {1}$ . سپس

${\ displaystyle \ lambda _ {1} v_ {x} = (Av) _ {x} = \ sum _ {y = 1} ^ {n} A_ {x، y} v_ {y} \ leq \ sum _ { y = 1} ^ {n} A_ {x ، y} v_ {x} = v_ {x} \ deg (x).}$

برای نمودارهای منظم d ، d اولین مقدار ویژه A برای بردار v = (1 ،… ، 1) است (به راحتی می توان مقدار ویژه آن را بررسی کرد و به دلیل حد بالا حداکثر است). تعدد این مقدار ویژه تعداد م ofلفه های متصل G به ویژه است ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}}$ برای نمودارهای متصل می توان نشان داد که برای هر مقدار ویژه $\ lambda _ {i}$ ، این برعکس آن است ${\ displaystyle - \ lambda _ {i} = \ lambda _ {n + 1-i}}$ اگر G یک نمودار دو بخشی باشد نیز یک مقدار ویژه A است . [8] به طور خاص - d یک مقدار ویژه از نمودارهای دو بخشی است.

تفاوت ${\ displaystyle \ lambda _ {1} - \ lambda _ {2}}$ است به نام فاصله طیفی و آن را به مربوط گسترش از G . این نیز مفید است را به شما معرفی شعاع طیفی از $آ$ نشان داده شده توسط ${\ displaystyle \ lambda (G) = \ max _ {\ left | \ lambda _ {i} \ right | <d} | \ lambda _ {i} |}$ . این تعداد محدود است ${\ displaystyle \ lambda (G) \ geq 2 {\ sqrt {d-1}} - o (1)}$ . این محدود در نمودارهای Ramanujan ، که در بسیاری از مناطق کاربرد دارند ، محکم است.

ایزومورفیسم و تغییر ناپذیرها [ ویرایش ]

فرض کنید دو نمودار G 1 و G 2 جهت دار یا غیرمستقیم با ماتریس همجواری A 1 و A 2 آورده شده است. G 1 و G 2 هستند ریخت اگر و تنها اگر وجود داشته باشد وجود دارد ماتریس جایگشت P به طوری که

$PA_ {1} P ^ {- 1} = A_ {2}.$

به طور خاص ، A 1 و A 2 مشابه هستند و بنابراین دارای چند جمله ای حداقل ، چند جمله ای مشخص ، مقادیر ویژه ، تعیین کننده و ردیف هستند . بنابراین اینها می توانند به عنوان تغییر شکل یکسان شکل نمودارها عمل کنند. با این حال ، دو نمودار ممکن است مجموعه ای از مقادیر ویژه یکسان را داشته باشند اما یکدست نباشند. [9] گفته می شود که چنین عملگرهای خطی همسان هستند .

قدرت ماتریس [ ویرایش ]

اگر ماتریس مجاورت گراف جهت و یا غیر مستقیم است G ، سپس ماتریس N (یعنی ماتریس از N نسخه از ) دارای تفسیری جالب توجه است: عنصر ( i ، J ) می دهد تعدادی از (به کارگردانی و یا بدون جهت) پیاده روی به طول N از رأس i به راس J . اگر n کوچکترین عدد صحیح غیر منفی است ، به طوری که برای برخی از i ، j ، عنصر ( i ، j) است) از A n مثبت است ، سپس n فاصله بین راس i و راس j است . این به معنی این، برای مثال، که تعدادی از مثلث در گراف بدون جهت G دقیقا اثری از 3 تقسیم بر 6. ماتریس مجاورت می توان برای تعیین اینکه آیا یا نه نمودار استفاده شده است متصل .

ساختار داده ها [ ویرایش ]

ماتریس مجاورت ممکن است به عنوان یک ساختار داده برای نمایش نمودارها در برنامه های رایانه ای برای دستکاری نمودارها استفاده شود. اصلی ترین ساختار داده جایگزین ، که برای این برنامه نیز استفاده می شود ، لیست همجواری است . [10] [11]

از آنجا که هر ورودی در ماتریس همجواری فقط به یک بیت نیاز دارد ، می تواند به صورت بسیار فشرده نمایش داده شود ، فقط اشغال | V | 2 /8 بایت برای نشان دادن یک نمودار، یا (با استفاده از یک فرمت مثلثی بسته بندی شده و تنها ذخیره سازی قسمت مثلثی پایین تر از ماتریس) حدود | V | 2 /16 بایت برای نشان دادن گراف بدون جهت. اگرچه نمایشی مختصرتر ممکن است ، اما این روش به حد پایین نظری اطلاعات برای حداقل تعداد بیت های مورد نیاز برای نشان دادن همه نمودارهای n -vertex نزدیک می شود. [12] برای ذخیره نمودارها در پرونده های متنی، بیت های کمتری در هر بایت می تواند مورد استفاده قرار گیرد تا اطمینان حاصل شود که همه بایت ها کاراکتر متن هستند ، به عنوان مثال با استفاده از نمایش Base64 . [13] این جمع و جور علاوه بر جلوگیری از اتلاف فضای ، محل مراجعه را تشویق می کند . با این حال ، برای یک نمودار پراکنده بزرگ ، لیست های مجاور به فضای ذخیره سازی کمتری نیاز دارند ، زیرا برای نمایش لبه هایی که وجود ندارند ، هیچ فضایی را تلف نمی کنند . [11] [14]

یک شکل جایگزین از ماتریس همجواری (که به فضای بیشتری نیاز دارد) اعداد موجود در هر عنصر ماتریس را با اشاره گرها به اشیا edge لبه (در صورت وجود لبه ها) یا اشاره گرهای پوچ (در صورت عدم وجود لبه) جایگزین می کند. [14] همچنین می توان وزن لبه ها را مستقیماً در عناصر ماتریس همجواری ذخیره کرد. [11]

علاوه بر مبادلات فضایی ، ساختارهای مختلف داده همچنین عملیات مختلف را تسهیل می کنند. یافتن همه رئوس مجاور یک راس معین در یک لیست مجاورتی به همان سادگی خواندن لیست است و متناسب با تعداد همسایگان زمان می برد. با یک ماتریس مجاورت ، باید یک ردیف کامل اسکن شود ، که متناسب با تعداد رئوس کل نمودار ، زمان بیشتری را می گیرد. از طرف دیگر ، آزمایش اینکه آیا لبه ای بین دو راس داده شده وجود دارد را می توان همزمان با یک ماتریس مجاورت تعیین کرد ، در حالی که نیاز به زمان متناسب با حداقل درجه دو راس با لیست مجاورت دارد. [11] [14]

همچنین به [ ویرایش ] مراجعه کنید

منبع

https://en.wikipedia.org/wiki/Adjacency_matrix

+ نوشته شده در سه شنبه بیست و یکم بهمن ۱۳۹۹ ساعت 17:21 توسط علی رضا نقش نیلچی |

مجموعه کانتور

در ریاضیات ، مجموعه کانتور مجموعه ای از نقاط است که در یک بخش خط قرار دارد که دارای چندین ویژگی قابل توجه و عمیق است. در سال 1874 توسط هنری جان استفان اسمیت [1] [2] [3] [4] کشف شد و توسط ریاضیدان آلمانی جورج کانتور در سال 1883 معرفی شد. [5] [6]

با در نظر گرفتن این مجموعه ، کانتور و دیگران کمک کردند تا مبانی توپولوژی مدرن نقطه ای قرار گیرد . اگرچه خود کانتور مجموعه را به روشی کلی و انتزاعی تعریف کرد ، اما متداول ترین ساخت مدرن مجموعه ای سه گانه Cantor است که با برداشتن وسط یک بخش خط و سپس تکرار روند با بخش های کوتاه تر باقی مانده ساخته شده است. خود کانتور ساخت و سازهای سه گانه را فقط در حال گذر ، به عنوان نمونه ای از یک ایده کلی تر ، از مجموعه ای کامل که در هیچ جا متراکم نیست ، ذکر کرد .

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

فهرست

ساخت و فرمول مجموعه سه گانه [ ویرایش ]

مجموعه سه گانه کانتور ${\ ریاضی {C}}$ با حذف تکراری قسمت سوم میانی باز از مجموعه ای از بخش های خط ایجاد می شود. یکی با حذف سوم میانی باز (1/3، 2/3) از فاصله [0 ، 1] ، و دو بخش خط باقی می ماند: [0 ، 1/3] ∪ [2/3، 1] در مرحله بعد ، یک قسمت میانی باز از هر یک از این بخش های باقیمانده حذف شده و چهار بخش خط باقی می ماند: [0 ، 1/9] ∪ [2/9، 1/3] ∪ [2/3، 7/9] ∪ [8/9، 1] این فرایند ادامه بینهایت ، که در آن N هفتم مجموعه ای است

$\ displaystyle C_ {n} = {\ frac {C_ {n-1}} {3}} \ cup \ left ({\ frac {2} {3}} + {\ frac {C_ {n-1}} {3}} \ درست) {\ متن {برای} \ n \ geq 1 ، {\ متن {و}} C_ {0} = [0،1].$

مجموعه سه گانه کانتور شامل تمام نقاط در فاصله زمانی [0 ، 1] است که در هیچ مرحله ای از این فرآیند نامحدود حذف نمی شوند:

$\ displaystyle {\ mathcal {C}}: = \ bigcap _ {n = 1} ^ {\ infty} C_ {n.$

شش مرحله اول این فرآیند در زیر نشان داده شده است.

با استفاده از ایده تحولات مشابه ، $display \ displaystyle T_ {L} (x) = x / 3 ، T_ {R} (x) = (2 + x) / 3$ , $cup \ displaystyle C_ {n} = T_ {L} (C_ {n-1}) \ cup T_ {R} (C_ {n-1})،}$ فرمولهای بسته صریح برای مجموعه کانتور [7]

$\ displaystyle {\ mathcal {C}} = [0،1] \ smallsetminus \ bigcup _ {n = 0} ^ {\ infty} \ bigcup _ {k = 0} ^ {3 ^ {n} -1} \ سمت چپ ({\ frac {3k + 1} {3 ^ {n + 1}}}، {\ frac {3k + 2} {3 ^ {n + 1}}} \ Right)،}$

جایی که هر سوم میانه به عنوان فاصله باز حذف می شود { ${\ displaystyle \ textstyle \ left ({\ frac {3k + 1} {3 ^ {n + 1}}}، {\ frac {3k + 2} {3 ^ {n + 1}}} \ Right)$ از فاصله بسته $\ displaystyle \ textstyle \ left [{\ frac {3k + 0} {3 ^ {n + 1}}}، {\ frac {3k + 3} {3 ^ {n + 1}}} \ Right] = \ سمت چپ [{\ frac {k + 0} {3 ^ {n}}} ، {\ frac {k + 1} {3 ^ {n}}} \ Right]$ اطراف آن ، یا

$\ displaystyle {\ mathcal {C}} = \ bigcap _ {n = 1} ^ {\ infty} \ bigcup _ {k = 0} ^ {3 ^ {n-1} -1} \ left (\ left [ \ frac {3k + 0} {3 ^ {n}}}، {\ frac {3k + 1} {3 ^ {n}} right \ Right] \ cup \ left [\ frac {3k + 2} 3 ^ {n}}} ، {\ frac {3k + 3} {3 ^ {n}}} \ Right] \ Right)،}$

جایی که سوم میانی ${\ displaystyle \ textstyle \ left ({\ frac {3k + 1} {3 ^ {n}}}، {\ frac {3k + 2} {3 ^ {n}}} \ Right)$ از فاصله بسته قبلی فوق $\ displaystyle \ textstyle \ left [{\ frac {k + 0} {3 ^ {n-1}}}، {\ frac {k + 1 {3 ^ {n-1}} right \ Right] = \ سمت چپ [{\ frac {3k + 0} {3 ^ {n}}}، {\ frac {3k + 3} {3 ^ {n}}} \ Right]$ با تقاطع با حذف می شود $\ displaystyle \ textstyle \ left [{\ frac {3k + 0} {3 ^ {n}}}، {\ frac {3k + 1} {3 ^ {n}} right \ Right] \ cup \ left [ \ frac {3k + 2} {3 ^ {n}}}، {\ frac {3k + 3} {3 ^ {n}}} \ درست].$

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

به تعبیر حسابی ، مجموعه Cantor از تمام اعداد واقعی فاصله واحد تشکیل شده است $[0،1]$ که به رقم 1 احتیاج ندارند تا به عنوان کسری سه قلو (پایه 3) بیان شود. همانطور که در نمودار بالا نشان داده شده است ، هر نقطه از مجموعه کانتور با یک مسیر از طریق یک درخت باینری بی نهایت عمیق قرار دارد ، جایی که مسیر به سمت چپ یا راست در هر سطح بسته می شود که مطابق آن کدام قسمت از قسمت حذف شده است. نمایانگر هر نوبت سمت چپ با 0 و هر چرخش سمت راست با 2 بازده کسر سه گانه را برای یک امتیاز به دست می آورد. با جایگزین کردن رقم های "2" در این بخش با رقم های "1" نقشه برداری surjective (و نه تزریقی ) بین مجموعه کانتور و مجموعه توالیهای باینری نامتناهی ایجاد می کند.

منبع

https://en.wikipedia.org/wiki/Cantor_set

+ نوشته شده در جمعه سی ام خرداد ۱۳۹۹ ساعت 18:43 توسط علی رضا نقش نیلچی |

اصل کبوتر

کبوترها در سوراخ ها. در اینجا تعداد = 10 کبوتر در سوراخ m = 9 وجود دارد . از آنجا که 10 بزرگتر از 9 است ، اصل کبوتر می گوید حداقل یک سوراخ بیش از یک کبوتر دارد.

در ریاضیات ، اصل کبوتر بیان می کند که اگر $ن$ موارد درج شده است $م$ ظروف ، با $n> m$ سپس حداقل یک ظرف باید بیش از یک مورد داشته باشد. [1] به تعبیر غیرمستقیم ، اگر "اشیاء" بیشتری نسبت به "سوراخ" دارید ، حداقل یک سوراخ باید چندین اشیاء در آن داشته باشد. یک مثال از زندگی واقعی می تواند باشد ، "اگر سه دستکش دارید ، حداقل دستکش دو دست راست یا حداقل دو دستکش دست چپ دارید" ، زیرا شما 3 شیء دارید ، اما فقط دو دسته برای قرار دادن آنها وجود دارد. (راست یا چپ). این جمله ظاهراً آشکار ، نوعی استدلال شمارش است، می تواند مورد استفاده قرار گیرد برای نمایش نتایج احتمالی غیر منتظره. به عنوان مثال ، اگر می دانید که جمعیت لندن (حداقل دو نفر) بیشتر از تعداد حداکثر موهایی است که می تواند در سر انسان وجود داشته باشد ، پس اصل کبوتر مستلزم این است که (حداقل) دو نفر وجود داشته باشد. در لندن که به همان تعداد موهای سر خود دارند.

اگر چه اصل لانه کبوتری به عنوان اوایل 1624 به نظر می رسد در یک کتاب منسوب به ژان Leurechon ، [2] آن است که معمولا به نام اصل جعبه دیریکله است یا اصل کشو دیریکله را پس از 1834 درمان اصل توسط پتر گوستاف لوژون دیریکله تحت نام Schubfachprinzip ( "کشو اصل "یا" اصل قفسه "). [3]

این اصل چندین تعمیم دارد و می توان به روش های مختلفی بیان کرد. در نسخه کمتری: برای اعداد طبیعی $ک$ و $م$ اگر $\ displaystyle n = km + 1$ اشیاء در میان توزیع می شوند $م$ سپس مجموعه کبوتر ادعا می کند که حداقل یکی از مجموعه ها حداقل شامل یک مجموعه است $k + 1$ اشیاء. [4] برای دلخواه $ن$ و $م$ این تعمیم به $\ displaystyle k + 1 = \ lfloor (n-1) / m \ rfloor + 1 = \ lceil n / m \ rceil،$ جایی که \ صفحه نمایش $\ lfloor \ cdots \ rfloor$ و $\ displaystyle \ lceil \ cdots \ rceil$ به ترتیب عملکرد کف و سقف را مشخص کنید.

اگرچه ساده ترین کاربرد ، مجموعه های محدود (مانند کبوتر و جعبه) است ، اما از مجموعه های نامتناهی نیز استفاده می شود که نمی توانند در مکاتبات یک به یک قرار گیرند . برای این کار نیاز به بیانیه رسمی از اصل لانه کبوتری است که "می کند وجود ندارد تابع یکبهیک که برد کوچکتر از آن است دامنه " . اثبات ریاضی پیشرفته مانند لیم Siegel بر این مفهوم کلی تر بنا شده است.

فهرست

اخلاق شناسی [ ویرایش ]

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

دیریکلت آثار خود را به دو زبان فرانسه و آلمانی منتشر کرد ، یا از Schubfach آلمانی (او در مورد توزیع مروارید نوشت) یا tiroir فرانسوی استفاده کرد . معنی اصلی دقیق هر دو با کشوی انگلیسی مطابقت دارد ، جعبه ای از روبرو که می تواند داخل و خارج از کابینت حاوی آن باشد. این اصطلاحات در اصطلاح كبوترخانه بود كه در فضای كوچك و کوچک در یك میز ، كابینت یا دیوار برای نگه داشتن حروف یا كاغذها ایستاده بود ، به طور استعاری ریشه در سازه هایی كه كبوترها در آن خانه دارند.

از آنجا که پدر دیرکلت پست مدرن بود و مبلمان با کبوتر معمولاً برای ذخیره یا مرتب کردن چیزها در بسیاری از دسته ها (مانند حروف در یک اداره پست یا کلیدهای اتاق در هتل) استفاده می شود ، کبوتر ترجمه می تواند یک نمایش کامل از استعاره دیریکلت باشد. این درک از کلمه ، با اشاره به برخی از ویژگی های مبلمان ، به ویژه در میان کسانی که به زبان انگلیسی انگلیسی صحبت نمی کنند بلکه به عنوان یک زبان انگلیسی در دنیای علمی است ، محو می شود - به نفع تعبیر تصویری بیشتر ، به معنای واقعی کلمه شامل کبوتر و سوراخ است. تعبیر پیشنهادی ، گرچه گمراه کننده از "کبوتر" به عنوان "کبوتر" به تازگی راهی برای بازگشت به آلمانی ترجمه "کتاب کبوتر" - اصل به عنوان "Taubenschlag" اصل ندارد.

علاوه بر اصطلاحات اصلی "Schubfach-Prinzip" به آلمانی [6] و "Principe des tiroirs" به زبان فرانسوی ، [7] ترجمه های لغوی دیگر هنوز در بلغاری ("принцип на чекмеджета") ، چینی ("抽屉原理") استفاده می شوند. ، دانمارکی ("Skuffeprincippet") ، هلندی ("ladenprincipe") ، مجارستانی ("skatulyaelv") ، ایتالیایی ("principio dei cassetti") ، ژاپنی ("引き出し論法") ، فارسی ("اصل لانه کبوتری") ، لهستانی ( "zasada szufladkowa") ، سوئدی ("Lådprincipen") ،و ترکی ("çekmece ilkesi").

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

چیدن جوراب [ ویرایش ]

فرض کنید یک کشو حاوی ترکیبی از جوراب های سیاه و جوراب آبی است که هر کدام را می توانید روی هر پا بپوشید ، و اینکه تعدادی جوراب را از کشو بیرون می کشید بدون اینکه نگاه کنید. حداقل جوراب کشیده شده برای تضمین یک جفت با همان رنگ چقدر است؟ با استفاده از اصل کبوتر ، برای داشتن حداقل یک جفت از همان رنگ ( m = 2 سوراخ ، یک رنگ در هر رنگ) با استفاده از یک کبوتر در هر رنگ ، باید فقط سه جوراب از کشو بکشید ( 3 عدد = ). یا سه تا از یک رنگ دارید ، یا دو رنگ یک رنگ و دیگری رنگی دارید .

لرزش دست [ ویرایش ]

اگر تعداد افرادی وجود داشته باشند که بتوانند دست خود را تکان دهند (در اینجا n > 1 ) ، اصل کبوتر نشان می دهد که همیشه یک جفت از افراد وجود دارند که با همان تعداد افراد دست خود را تکان خواهند داد. در این کاربرد اصل ، "سوراخی" که شخص به آن اختصاص داده می شود ، تعداد دستهایی است که توسط آن شخص تکان می خورد. از آنجا که هر حرکت فرد دست با برخی از تعداد زیادی از مردم از 0 تا N - 1 ، وجود دارد N سوراخ امکان پذیر است. از طرف دیگر ، یا سوراخ "0" یا سوراخ " n - 1" یا هر دو باید خالی باشند ، زیرا غیرممکن است (اگر n > 1) در حالی که بعضی از افراد با هیچ کس دست تکان نمی دهند. این برگ N مردم می شود را به حداکثر قرار داده N - 1 سوراخ غیر خالی، به طوری که اصل اعمال می شود.

شمارش مو [ ویرایش ]

ما می توانیم نشان دهیم که حداقل در لندن باید دو نفر با همان تعداد موهای سر خود به شرح زیر باشند. [8] از آنجا که یک سر معمولی انسان به طور متوسط حدود 150،000 مو دارد ، فرض منطقی است که تصور کنیم که هیچ کس بیش از 1،000،000 مو در سر خود نداشته باشد ( m = 1 میلیون سوراخ). بیش از 1،000،000 نفر در لندن وجود دارد ( Nاز 1 میلیون مورد بزرگتر است) اختصاص یک کبوتر به هر تعداد مو روی سر شخص و قرار دادن افراد به کبوترها با توجه به تعداد موهای روی سرشان ، باید حداقل دو نفر در انتهای یک کبوتر قرار داشته باشند تا با تعیین تکلیف 1000،001 (از آنجا که آنها دارای هستند همان تعداد موهای سرشان) (یا ، n > m ). برای مورد متوسط ( m = 150،000)) با این محدودیت: کمترین همپوشانی وجود دارد ، حداکثر یک نفر به هر کبوتر اختصاص داده می شود و فرد 150001st اختصاص داده شده به همان کبوتر مانند شخص دیگر. در صورت عدم وجود این محدودیت ، ممکن است سوراخ های کبوتر خالی وجود داشته باشد زیرا "برخورد" قبل از رسیدن به شخص 150001st اتفاق می افتد. این اصل فقط وجود یک همپوشانی را اثبات می کند. هیچ چیزی از تعداد همپوشانی ها (که تحت موضوع توزیع احتمال وجود دارد ) می گوید .

در انگلیسی به این نسخه از اصل در "تاریخچه انجمن آتنیان " ، یک تمثیل گذرا ، طنزآمیز وجود دارد ، پیشوند "" یک مکمل به اوراکل آتنی: مجموعه ای از سؤالات و پاسخ های باقیمانده در عطاران قدیمی آتنی " »، (چاپ شده برای اندرو بل ، لندن ، 1710). [9] به نظر می رسد این سؤال مطرح می شود كه آیا دو فرد در جهان وجود داشته اند كه تعداد موهایشان برابر است؟ قبل از سال 1704 در عطارد آتنی مطرح شده بود . [10] [11]

شاید اولین مرجع کتبی به اصل کبوترخانه در سال 1622 در یک جمله کوتاه از کار لاتین Selectæ Propositiones ، توسط فرانسوی Jesuit Jean Leurechon ، ظاهر شود ، [2] در جایی که وی نوشت: "لازم است که دو مرد به همان تعداد موها ، écus ، یا چیزهای دیگر ، مانند یکدیگر. " [12] این اصل دو سال بعد ، همراه با مثالهای اضافی ، در کتاب دیگری که اغلب به لورچون نسبت داده شده است ، بیان شده است ، اما ممکن است توسط یکی از شاگردانش نوشته شده باشد. [2]

مشکل تولد [ ویرایش ]

مشکل تولد می پرسد، برای مجموعه ای از Nافرادی که به طور تصادفی انتخاب شده اند ، احتمال دارد که برخی از جفت های آنها همان سال تولد داشته باشند؟ طبق اصل کبوترخانه ، اگر 367 نفر در اتاق حضور داشته باشند ، می دانیم حداقل یک جفت وجود دارد که در همان روز تولد مشترک هستند ، زیرا تنها 366 تولد ممکن برای انتخاب وجود دارد (از جمله 29 فوریه در صورت حضور). "پارادوکس" تولد به این نتیجه اشاره دارد که حتی اگر این گروه به اندازه 23 نفر کوچک باشد ، احتمال اینکه یک زوج با همان روز تولد وجود داشته باشد ، هنوز هم بالاتر از 50٪ است. اگرچه در نگاه اول این ممکن است شگفت آور به نظر برسد ، با در نظر گرفتن اینكه مقایسه ای بین هر جفت ممكن صورت می گیرد به جای ثابت كردن یك فرد و مقایسه آنها فقط با بقیه گروه ، بطور شهودی منطقی خواهد بود.

مسابقات تیمی [ ویرایش ]

هفت نفر را تصور کنید که می خواهند در یک تورنمنت تیمی بازی کنند ( تعداد 7 نفر ) ، با محدودیت فقط 4 تیم ( متر = 4 سوراخ) برای انتخاب. اصل کبوتر به ما می گوید که همه آنها نمی توانند برای تیم های مختلف بازی کنند. باید حداقل یک تیم باشد که حداقل دو نفر از هفت بازیکن را داشته باشد:

$\ displaystyle \ left \ lfloor {\ frac {n-1} {m}} \ Right \ rfloor + 1 = \ left \ lfloor {\ frac {7-1} {4}} \ Right \ rfloor + 1 = \ سمت چپ \ lfloor {\ frac {6} {4}} \ Right \ rfloor + 1 = 1 + 1 = 2$

مبلغ زیر مجموعه [ ویرایش ]

هر زیر مجموعه ای از اندازه شش از مجموعه S = 1،2،3 ، ... ، 9} باید شامل دو عنصر باشد که جمع آنها 10 باشد. مارپیچ های کبوتر توسط دو زیر مجموعه 1.9 {، {2 برچسب گذاری خواهند شد. ، 8} ، 3،7 {، 4،6 {} و Singleton {5 ، پنج سوراخ کبوتر در همه. هنگامی که شش "کبوتر" (عناصر اندازه 6 زیرمجموعه) در این کبوترها قرار داده شوند ، هر کبوتر به داخل کبوترانی که در برچسب آن وجود دارد ، می رود ، حداقل یکی از کبوترهای دارای برچسب دارای دو زیرمجموعه دارای دو کبوتر خواهد بود. در آن [13]

کاربردها و برنامه ها [ ویرایش ]

این اصل را می توان برای اثبات اینكه هر الگوریتم فشرده سازی بدون ضرر ، به شرط آنكه برخی ورودی ها كوچك تر شود (همانطور كه از نام فشرده سازی نام گرفته است) استفاده كرد ، همچنین باعث می شود ورودی های دیگری نیز بزرگتر شوند. در غیر این صورت ، مجموعه ای از همه توالی های ورودی تا طول معین L را می توان به (خیلی) مجموعه کوچکتر از تمام توالی های طول کمتر از L بدون برخورد نقشه کشید (زیرا فشرده سازی بدون ضرر است) ، امکانی که اصل کبوتر آن را حذف می کند.

یک مسئله قابل توجه در تجزیه و تحلیل ریاضی ، برای عدد غیر منطقی ثابت a است که نشان می دهد مجموعه na [ na ]: n یک عدد صحیح است} از بخش های کسری در [0 ، 1] متراکم است . یکی می یابد که از آن آسان است به صراحت اعداد صحیح پیدا کنید N ، متر به طوری که | NA - m | < e ، که در آن e > 0 یک عدد مثبت کمی است و یک عدد غیر منطقی دلخواه است. اما اگر کسی M را به گونه ای بگیرد که 1 / M < eطبق اصل کبوتر باید n 1 ، n 2 ∈ 1 ، 2 ، ... ، M + 1 } به گونه ای باشد که n 1 a و n 2 a در یک زیر مجموعه عدد صحیح با اندازه 1 / M قرار داشته باشند (وجود دارد فقط M چنین تقسیم بندی هایی بین اعداد صحیح متوالی). به طور خاص ، می توانیم n 1 ، n 2 را به گونه ای پیدا کنیم که n 1 a در ( p + k / M ، p + ( k + 1) باشد /M ) ، و n 2 a در ( q + k / M ، q + ( k + 1) / M ) است ، برای بعضی ازعدد صحیح p ، q و k در {0 ، 1 ، ... ، M - 1 . سپس می توانیم به راحتی تأیید کنیم که ( n 2 - n 1 ) a در ( q - p - 1 / M ، q - p + 1 / M ) است.. این بدان معنی است که [ na ] <1 / M < e ، که در آن n = n 2 - n 1 یا n = n 1 - n 2 . این نشان می دهد که 0 یک نقطه حد {[ na ] است. سپس می توانیم از این واقعیت برای اثبات مورد در p در (0 ، 1) استفاده کنیم : n را به گونه ای بیابیم که [ na ] <1 / M < e ؛ سپس اگر p ∈ (0 ، 1 / M ] باشد ، ما انجام می دهیم. p ∈ ( j/ M ، ( j + 1) / M ] ، و با تنظیم k = sup { r ∈ N : r [ na ] < j / M } ، یکی بدست می آید | [( k + 1) na ] - p | <1 / M < e .

انواع مختلفی که در اثبات شناخته شده وجود دارد: در اثبات لم پمپاژ برای زبانهای عادی ، از نسخه ای استفاده می شود که مجموعه های محدود و نامتناهی را با هم مخلوط می کند: اگر بی نهایت بسیاری از اشیاء در جعبه های نهایی به طور نهایی قرار گیرند ، دو شی وجود دارد که یک جعبه را به اشتراک می گذارند. [14] در حل فیسک از مشکل گالری هنر نوعی از مکالمه استفاده می شود: اگر n اشیاء در جعبه k قرار داده شوند ، در آن صورت جعبه ای وجود دارد که اکثر اشیاء n / k را در خود جای داده است. [15]

فرمول های جایگزین [ ویرایش ]

در زیر فرمول های جایگزین از اصل کبوترخانه است.

اگر n اشیاء در m مکانها توزیع شود ، و اگر n > m باشد ، در بعضی قسمت ها حداقل دو شیء دریافت می کنند. [1]
(فرمول معادل 1) اگر n اشیاء در بیش از N مکان توزیع شوند به گونه ای که هیچ مکانی بیش از یک شی را دریافت نکند ، سپس هر مکان دقیقاً یک شی را دریافت می کند. [1]
اگر n اشیاء بر روی مکانهای m توزیع شود ، و اگر n < m باشد ، در بعضی موارد جسم دریافت نمی شود.
(فرمول معادل 3) اگر n اشیاء بر روی n مکان ها توزیع شود به گونه ای که هیچ مکانی هیچ شیء را دریافت نمی کند ، سپس هر مکان دقیقاً یک شی را دریافت می کند. [16]

فرم قوی [ ویرایش ]

بگذارید q 1 ، q 2 ، ...، q n صحیح باشد. اگر

$q_ {1} + q_ {2} + \ cdots + q_ {n} -n + 1$

اشیاء به توزیع N جعبه، سپس هر دو جعبه اول شامل حداقل Q 1 اشیاء، و یا جعبه دوم شامل حداقل Q 2 اشیاء، ...، و یا N هفتم جعبه شامل حداقل Q N اشیاء. [17]

شکل ساده از این طریق با گرفتن q 1 = q 2 = ... = q n = 2 ، که n + 1 اشیاء به دست می آید. با استفاده از q 1 = q 2 = ... = q n = r نسخه کمی تر از اصل ، یعنی:

بگذارید n و r عدد صحیح مثبت باشند. اگر اشیاء n ( r - 1) +1 در جعبه n توزیع شوند ، حداقل یکی از جعبه ها حاوی r یا تعداد بیشتری از اشیاء است. [18]

این همچنین می تواند چنین بیان شود ، اگر قرار است اشیاء گسسته k به ظروف n اختصاص داده شود ، باید حداقل یک ظرف حداقل دارای یک ظرف باشد $\ lceil k / n \ rasil$ اشیاء ، که $\ lceil x \ rceil$ است تابع سقف ، دلالت کوچکترین عدد صحیح بزرگتر از یا مساوی x را . به طور مشابه ، حداقل یک ظرف باید بیش از چیزی نگه ندارد\ صفحه نمایش $\ lfloor k / n \ rfloor$ اشیاء ، کجا $\ lfloor x \ rfloor$ است تابع کف ، دلالت بزرگترین عدد صحیح کوچکتر یا مساوی x را .

کلیات اصل کبوتر [ ویرایش ]

تعمیم احتمالاتی از کشورهای اصل لانه کبوتری که اگر N کبوتر به صورت تصادفی به قرار متر pigeonholes با احتمال یکنواخت 1 / متر ، آنگاه حداقل یک لانه کبوتری را به بیش از یک کبوتر با احتمال برگزاری

$\ displaystyle 1 - {\ frac {(m) _ {n}} {m ^ {n}}}،$

که در آن ( m ) n عامل در حال سقوط m ( m - 1) ( m - 2) ( m - n + 1) است . برای n = 0 و برای n = 1 (و m > 0 ) ، این احتمال صفر است؛ به عبارت دیگر ، اگر فقط یک کبوتر وجود داشته باشد ، نمی تواند درگیری باشد. برای n > m (کبوترهای بیشتر از کبوتر) این یکی است که در این حالت با اصل کبوتر معمولی همزمان می شود. اما حتی اگر تعداد کبوترها از تعداد کبوترها ( n ≤ m) تجاوز نکند) ، به دلیل تصادفی بودن واگذاری کبوتران به کبوترها ، این احتمال وجود دارد که درگیری اتفاق بیفتد. به عنوان مثال ، اگر 2 کبوتر به طور تصادفی به 4 کبوتر اختصاص داده شوند ، احتمال 25٪ احتمال حداقل یک کبوتر بیش از یک کبوتر وجود دارد. برای 5 کبوتر و 10 سوراخ ، این احتمال 69.76٪ است. و برای 10 کبوتر و 20 سوراخ حدود 45/93 درصد است. اگر تعداد سوراخ ها ثابت بمانند ، همیشه هنگام اضافه کردن کبوترهای بیشتر احتمال یک جفت بیشتر است. این مشکل در پارادوکس تولد با طول بسیار بیشتری درمان می شود .

تعمیم احتمالی دیگر این است که وقتی که یک واقعی ارزش متغیر تصادفی X دارای محدود میانگین E ( X ) غیر صفر، پس از آن احتمال این است که X بزرگتر یا برابر E ( X ) ، و به همین ترتیب احتمال این است غیر صفر که X است کمتر یا مساوی E ( X ) است . برای دیدن اینکه این دلالت بر اصل کبوتر چاله استاندارد دارد ، هر نوع تنظیم کبوتر n را در سوراخ های M قرار دهید و بگذارید X تعداد کبوترهای موجود در یک سوراخ باشد که به طور یکنواخت به طور تصادفی انتخاب شده است. میانگین Xاست N / متر ، بنابراین اگر می کبوتر بیشتر وجود دارد از سوراخ متوسط بزرگتر از یک است. بنابراین ، X حداقل حداقل 2 است.

مجموعه های بی نهایت [ ویرایش ]

اصل کبوترخانه را می توان با تنظیم آن از نظر تعداد کاردینال به مجموعه های نامحدود گسترش داد : اگر کاردینال بودن مجموعه A از کارتال بودن مجموعه B بیشتر باشد ، تزریق از A تا B وجود ندارد . با این حال ، در این شکل اصل تتلوژیکی است ، زیرا معنای این جمله که نشان می دهد کاردینال بودن مجموعه A از بزرگترین مجموعه B بیشتر است ، دقیقاً این است که هیچ نقشه تزریقی از A تا B وجود ندارد . با این وجود ، اضافه کردن حداقل یک عنصر به یک مجموعه محدود برای اطمینان از افزایش کاردینال کافی است.

روش دیگر برای بیان اصل کبوتر برای مجموعه های محدود شبیه به این اصل است که مجموعه های محدود Dedekind متناهی هستند : بگذارید A و B مجموعه های متناهی باشند. اگر از A تا B سوراخی وجود داشته باشد که تزریقی نباشد ، هیچگونه تزریق از A به B تزریق نمی شود. در واقع هیچ عملکردی از هر نوع A تا B تزریقی نیست. این در مورد مجموعه های نامحدود صحیح نیست: این عملکرد را روی اعداد طبیعی که 1 و 2 به 1 ، 3 و 4 به 2 ، 5 و 6 به 3 و غیره می فرستند در نظر بگیرید.

یک اصل مشابه برای مجموعه های نامتناهی وجود دارد: اگر بیشماری کبوترها را به تعداد بیشماری کبوتر پر کنید ، حداقل یک کبوتر وجود دارد که تعداد کبوترهای بی شماری را در آن پر کرده است.

این اصل یک تعمیم اصل کبوترخانه ای برای مجموعه های محدود نیست. از نظر فنی می گوید كه اگر A و B مجموعه های محدود باشد به گونه ای كه هرگونه عملكرد نظری از A تا B تزریقی نباشد ، در این صورت عنصری از b از B وجود دارد به گونه ای كه بین پیش نمایش b و A یک حیات وجود دارد . این جمله کاملاً متفاوت است و برای کاردینالیتهای محدود متناهی پوچ است.

مکانیک کوانتومی [ ویرایش ]

یاکیر آهارونف و همکاران. استدلالهای ارائه شده مبنی بر اینکه ممکن است اصل کبوترخانه در مکانیک کوانتومی نقض شده باشد و آزمایشهای متداول سنجی را برای آزمایش اصل کبوترخانه در مکانیک کوانتومی ارائه داده اند. [19] اما تحقیقات بعدی این نتیجه گیری را زیر سوال برده است. [20] [21]در یک نسخه arXiv در ژانویه سال 2015 ، محققان Alastair Rae و Ted Freedan در دانشگاه بیرمنگام یک تحلیل تئوری عملکرد موج را با استفاده از اصل استاندارد کبوتر دریایی در پرواز الکترون ها در انرژی های مختلف از طریق یک تداخل سنج انجام دادند. اگر الکترون ها به هیچ وجه از قدرت متقابل برخوردار نبودند ، هر یک قله منفرد و کاملاً دایره ای تولید می کنند. در قدرت بالای تعامل ، هر الکترون چهار قله مجزا را برای کل 12 قله در ردیاب ایجاد می کند. این قله ها نتیجه چهار فعل و انفعال ممکن است که هر الکترون می تواند تجربه کند (به تنهایی ، تنها با ذره اول دیگر ، فقط با ذره دوم دیگر ، یا هر سه با هم). اگر قدرت تعامل نسبتاً پایین بود ، مانند بسیاری از آزمایش های واقعی ، انحراف از یک الگوی تعامل صفر تقریبا غیر قابل تشخیص خواهد بود ، بسیار کوچکتر از فاصله شبکه اتمها در مواد جامد ، مانند آشکارسازهای مورد استفاده برای رعایت این الگوهای. این امر باعث می شود که قدرت تعامل ضعیف اما غیرزرو از هیچ تعامل با هم بسیار دشوار یا حتی غیرممکن باشد ، و به این ترتیب توهم سه الکترون را نشان می دهد که علی رغم هر سه عبور از دو مسیر ، تعامل ندارند.

منبع

https://en.wikipedia.org/wiki/Pigeonhole_principle

+ نوشته شده در جمعه بیست و ششم اردیبهشت ۱۳۹۹ ساعت 2:34 توسط علی رضا نقش نیلچی |

شماره مارکوف

از ویکیپدیا، دانشنامه آزاد

سطح اول درخت شماره مارکوف

یک علامت مارکوف یا علامت Markoff یک عدد صحیح مثبت x ، y یا z است که بخشی از راه حل معادله مارکوف دیوفانتین است.

$x ^ {2} + y ^ {2} + z ^ {2} = 3xyz ، \ ،$

توسط آندری مارکف ( 1879 ، 1880 ) مورد مطالعه قرار گرفت .

چند عدد اول مارکوف هستند

1 ، 2 ، 5 ، 13 ، 29 ، 34 ، 89 ، 169 ، 194 ، 233 ، 433 ، 610 ، 985 ، 1325 ، ... (دنباله A002559 در OEIS )

به عنوان مختصات سه گانه مارکوف ظاهر می شوند

(1، 1، 1)، (1، 1، 2)، (1، 2، 5)، (1، 5، 13)، (2، 5، 29)، (1، 13، 34)، (1 ، 34، 89)، (2، 29، 169)، (5، 13، 194)، (1، 89، 233)، (5، 29، 433)، (1، 233، 610)، (2، 169 ، 985) ، (13 ، 34 ، 1325) و غیره

بی نهایت تعداد مارکف و سه گانه مارکوف وجود دارد.

فهرست

درخت مارکوف [ ویرایش ]

دو روش ساده برای به دست آوردن یک سه گانه جدید مارکوف از یک روش قدیمی ( x ، y ، z ) وجود دارد. در ابتدا ، ممکن است 3 عدد x ، y ، z را محدود کند ، بنابراین به طور خاص می توان سه گانه را به طور عادی تنظیم کرد تا x ≤ y ≤ z . دوم ، اگر ( x ، y ، z ) سه گانه مارکوف است ، سپس با پرش ویتا ( x ، y ، 3 xy - z) استفاده از این عمل دو بار همان سه گانه ای را که با آن شروع شده بود برمی گرداند. پیوستن به هر سه قلو عادی ماركوف به 1 ، 2 یا 3 تریپل عادی كه می توانید از این نمودار بدست آورید همانطور كه در نمودار آمده از (1،1،1) می باشد. این نمودار به هم متصل است. به عبارت دیگر ، هر سه گانه مارکوف را می توان با دنباله ای از این عملیات به (1،1،1) وصل کرد. [1] اگر به عنوان نمونه با (1 ، 5 ، 13) شروع کنیم ، سه همسایه آن (5 ، 13 ، 194) ، (1 ، 13 ، 34) و (1 ، 2 ، 5) را در مارکوف به دست می آوریم. اگر z به ترتیب 1 ، 5 و 13 تنظیم شود. به عنوان مثال ، با شروع (1 ، 1 ، 2) و تجارت y و z قبل از هر تکرار از تبدیل ، ماركوف را سه برابر با شماره های فیبوناچی لیست می كند. با همان سه برابر کردن و تجارت x شروع می شودو z قبل از هر تکرار به سه برابر عدد Pell می دهد.

تمام اعداد مارکوف در نواحی مجاور منطقه 2 دارای شماره های Pell با نمایه های عجیب و غریب هستند (یا اعداد n به گونه ای است که 2 n 2 - 1 یک مربع باشد ، OEIS : A001653 ) و تمام اعداد مارکوف در مناطق مجاور منطقه 1 هستند. شماره فیبوناچی با نمایه عجیب و غریب ( OEIS : A001519 ). بنابراین ، بی نهایت بسیاری از سه قلو مارکوف از فرم وجود دارد

$(1 ، F _ {{2n-1}} ، F _ {n 2n + 1}}) ، \،$

که در آن F X است X امین عدد فیبوناچی است. به همین ترتیب ، بسیاری از سه گانه فرم مارکوف بی نهایت هستند

$(2 ، P _ {{2n-1}} ، P _ {n 2n + 1}}) ، \ ،$

که در آن P X است X هفتم تعداد پل . [2]

خواص دیگر [ ویرایش ]

گذشته از دو کوچکترین تکین تکگانه (1،1،1) و (1،1،2) ، هر سه‌گانه مارکوف از سه عدد صحیح مجزا تشکیل شده است. [3]

حدس UNICITY بیان می کند که برای داده مارکوف تعداد ج ، دقیقا همان یک راه حل نرمال داشتن وجود دارد ج به عنوان بزرگترین عنصر آن: اثبات این حدس ادعا میشود اما هیچ کدام به نظر می رسد درست باشد. [4]

تعداد اعداد مارکوف 1 برابر بیشتر از تعداد 4 است ، در حالی که حتی اعداد مارکوف نیز 2 بیشتر از تعداد 32 است. [5]

در مقاله 1982 خود، دان Zagier حدس زده که N امین عدد مارکوف است مجانبی شده توسط:

$\ displaystyle m_ {n} = {\ tfrac {1} {3}} e ^ {C {\ sqrt {n}} + o (1) \ quad {\ text {با} C = 2.3523414972 \ ldots. }$

علاوه بر این ، او اشاره کرد که $x ^ {2} + y ^ {2} + z ^ {2} = 3xyz + 4/9$ ، تقریب معادله Diophantine اصلی ، معادل است $f (x) + f (y) = f (z)$ با f ( t ) = arcosh (3 t / 2). [6] حدس ثابت شد [ مورد مناقشه - بحث در مورد ] توسط گرگ مکشین و ایگور Rivin در سال 1995 با استفاده از روش های از هندسه هذلولی. [7]

N هفتم تعداد لاگرانژ را می توان از محاسبه N امین عدد مارکوف با فرمول

$L_ {n} = {\ sqrt {9- {4 \ {_ m_ {n}} ^ {2}}}}. \،$

علامت های مارکوف تعداد جفت مربعات (غیر منحصر به فرد) است.

قضیه مارکوف [ ویرایش ]

مارکف ( 1879 ، 1880 ) نشان داد که اگر

$\ displaystyle f (x، y) = ax ^ {2} + bxy + cy ^ {2}$

یک فرم دودویی نامحدود و بصری با ضرایب واقعی و تبعیض آمیز است $D = b ^ {2} -4ac$ ، سپس عدد صحیح x ، y وجود دارد که f برای آنها مقدار حداکثر مقدار خالص را دارد

$\ frac {{\ sqrt D}} {3}$

مگر اینکه f یک شکل مارکوف باشد : [8] یک بار ثابت یک فرم

$\ displaystyle px ^ {2} + (3p-2a) xy + (b-3a) y ^ {2}$

به طوری که

${\ displaystyle 0 <a <p / 2، aq \ equiv \ pm r {\ pmod {p}}، bp-a ^ {2} = 1،}$

جایی که ( p ، q ، r ) یک سه گانه مارکوف است.

در توپولوژی نیز یک قضیه مارکوف وجود دارد که پسرش آندری مارکوف ، آندری آندریویچ مارکوف نامگذاری شده است . [9]

ماتریس [ ویرایش ]

اجازه دهید Tr عملکرد ردیابی را روی ماتریس نشان دهد. اگر X و Y در SL 2 ( ℂ ) هستند ، پس از آن

Tr ( X ) Tr ( Y ) Tr ( X ⋅ Y ) + Tr ( X ⋅ Y ⋅ X ^−1 ⋅ Y ^−1 ) + 2 = Tr ( X ) ^2 + Tr ( Y ) ^2 +

Tr ( X ⋅ Y ) ^2

به طوری که اگر Tr ( X ⋅ Y ⋅ X^ −1 ⋅ Y^ −1 ) = −2 پس از آن

Tr ( X ) Tr ( Y ) Tr ( X ⋅ Y ) = Tr ( X ) ^2 + Tr ( Y ) ^2 + Tr ( X ⋅ Y ) ^2

به طور خاص اگر X و Y دارای ورودی های صحیح نیز باشند ، Tr ( X ) / 3 ، Tr ( Y ) / 3 و Tr ( X ⋅ Y ) / 3 یک مارکف سه قلو هستند. اگر X ⋅ Y ⋅ Z = 1 سپس( TR ( X ⋅ Y ) = TR ( Z ، بنابراین بیشتر متقارن اگر X ، Y ، و Z در SL هستند 2 (ℤ) با X ⋅ Y ⋅ Z = 1 و کموتاتور از دو تا از آنها اثری −2 است ، سپس ردیابی آنها / 3 یک سه گانه مارکوف هستند.[10]

منبع

https://en.wikipedia.org/wiki/Markov_number

+ نوشته شده در پنجشنبه هجدهم اردیبهشت ۱۳۹۹ ساعت 17:50 توسط علی رضا نقش نیلچی |

ادامه قانون رستاخیز

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

مثال 1 (1985) [ ویرایش ]

فرض کنید می خواهید روز هفته 18 سپتامبر 1985 را بدانید. شما با روز لنگر قرن ، چهارشنبه شروع می کنید. برای این کار a ، b و c را در بالا اضافه کنید:

کف است85/12 است که 7.
ب است 85 وزارت دفاع 12 ، است که 1 .
c کفb/4 است که 0 است.

این بازده a + b + c = 8 است . با حساب 8 روز از چهارشنبه ، به پنجشنبه می رسیم که روز رستاخیز در سال 1985 است. (با استفاده از اعداد: در ماژول 7 حسابی ، 8 متناسب با 1 است. زیرا روز لنگر قرن چهارشنبه است (فهرست 3) و 3 + 1 = 4 ، روز رستاخیز در سال 1985 پنج شنبه بود (شاخص 4). اکنون ما 18 سپتامبر را با یک روز قیامت در نزدیکی 5 سپتامبر مقایسه می کنیم. می بینیم که 18th ساعت گذشته از روز رستاخیز است ، یعنی یک روز کمتر از دو هفته. از این رو ، هجدهم یک چهارشنبه (روز قبل از پنجشنبه) بود. (با استفاده از اعداد: در حساب شماره 7 ماژول ، 13 مطابق با 6 یا به طور دقیق تر − 1 است. بنابراین ، ما یکی را از روز رستاخیز ، پنجشنبه ، دور می کنیم تا دریابیم که 18 سپتامبر 1985 یک چهارشنبه بود.)

مثال 2 (قرون دیگر) [ ویرایش ]

فرض کنید می خواهید روز هفته جنگ داخلی آمریکا را در فورت سامر ، که در 12 آوریل 1861 بود ، پیدا کنید. روز لنگر قرن برای 99 روز بعد از پنجشنبه یا به عبارتی جمعه (محاسبه شده به عنوان (18 + 1) × 5 + ⌊ 18/4 ⌋ ؛ و یا فقط در نمودار نگاه کنید، بالا، که لیست قرن روز لنگر). رقم 61 جابجایی شش روزه بدین ترتیب روز رستاخیز پنج شنبه بود. بنابراین ، چهارم آوریل پنجشنبه بود بنابراین 12 آوریل ، هشت روز بعد ، جمعه بود.

همچنین مشاهده کنید [ ویرایش ]

انواع سال گرگوری در هر چرخه جهش با حرف Dominical (DL) [10] و روز رستاخیز (DD)
1 ژانویه	شمردن	نسبت	31 دسامبر	DL	DD	شمردن	نسبت	31 دسامبر	DL	DD	شمردن	نسبت
سال شروع می شود			سالهای مشترک					سالهای کبیسه
آفتاب	58	14.50٪	آفتاب	آ	سه شنبه	43	10.75٪	دوشنبه	AG	چهارشنبه	15	3.75٪
نشسته	56	14.00٪	نشسته	ب	دوشنبه	43	10.75٪	آفتاب	کارشناسی	سه شنبه	13	3.25٪
جمعه	58	14.50٪	جمعه	ج	آفتاب	43	10.75٪	نشسته	CB	دوشنبه	15	3.75٪
پنجشنبه	57	14.25٪	پنجشنبه	د	نشسته	44	11.00٪	جمعه	دی سی	آفتاب	13	3.25٪
چهارشنبه	57	14.25٪	چهارشنبه	ه	جمعه	43	10.75٪	پنجشنبه	ED	نشسته	14	3.50٪
سه شنبه	58	14.50٪	سه شنبه	ف	پنجشنبه	44	11.00٪	چهارشنبه	FE	جمعه	14	3.50٪
دوشنبه	56	14.00٪	دوشنبه	ج	چهارشنبه	43	10.75٪	سه شنبه	GF	پنجشنبه	13	3.25٪
Σ	400	100.0٪				303	75.75٪				97	24.25٪

تاریخ معمولی
Computus - الگوریتم گاوس برای محاسبه تاریخ عید پاک
هماهنگی زلر - الگوریتمی (1882) برای محاسبه روز هفته برای هر تاریخ تقویم ژولی یا گرگوری.
محاسبه ذهنی

منابع

https://en.wikipedia.org/wiki/Doomsday_rule

+ نوشته شده در چهارشنبه دهم اردیبهشت ۱۳۹۹ ساعت 5:27 توسط علی رضا نقش نیلچی |

آندره ویل

از ویکیپدیا، دانشنامه آزاد

آندره ویل

بدنیا آمدن	6 مه 1906 پاریس ، فرانسه
فوت کرد	6 آگوست 1998 (92 ساله) پرینستون ، نیوجرسی ، ایالات متحده
آلما ماده	دانشگاه پاریس olecole Normale Supérieure Aligarh University University
شناخته شده برای	مشارکت در نظریه اعداد ، هندسه جبری
جوایز	جایزه گرگ (1979) جایزه لروی پی استیل (1980) مدال برنارد برای خدمات شایسته به علم (1980) جایزه کیوتو (1994) ForMemRS (1966) [1]
حرفه علمی
زمینه های	ریاضیات
موسسات	دانشگاه اسلامی علیگر (1930-1932) دانشگاه Lehigh دانشگاه سائوپائولو (1945-1947) دانشگاه شیکاگو (1947-1958) موسسه مطالعات پیشرفته
مشاور دکترا	ژاک حدامارد چارلز امیل پیکارد
دانشجویان دکترا	پیر کارتیه هارلی فلاندر ویلیام A. هوارد Teruhisa Matsusaka پیتر Swinnerton-Dyer [2]

آندره ویل ( / v eɪ / ؛ فرانسوی: [ɑ̃dʁe vɛj] ؛ 6 مه 1906 - 6 اوت 1998) یک ریاضیدان فرانسوی بود ، [3] که به دلیل کار اساسی در تئوری اعداد و هندسه جبری شناخته شده بود . او عضو موسس و رهبر اولیه de facto گروه ریاضی بورباکی بود . فیلسوف سیمون خواهرش بود. [4] [5]

فهرست

زندگی [ ویرایش ]

آندره ویل در متولد شد پاریس به اگنوستیک یهودی اهل آلزاس پدر و مادر که الحاق فرار آلزاس-لورن توسط امپراتوری آلمان پس از جنگ فرانسه و پروس در 1870-1871. فیلسوف مشهور سیمون ویل تنها خواهر و برادر ویل بود. وی در پاریس ، روم و گوتینگن تحصیل کرد و دکترای خود را در سال 1928 دریافت کرد . وی در حالی که در آلمان بود ، با کارل لودویگ سیگل دوست شد . وی از سال 1930 شروع به کار کرد و دو سال تحصیلی را در دانشگاه مسلمین الیگار سپری کرد . گذشته از ریاضیات ، ویل علایق مادام العمر در ادبیات کلاسیک یونان و لاتین ، درادبیات هندوئیسم و سانسکریت : او خود را در سال 1920 به زبان سانسکریت آموخت. [6] [7] پس از یک سال تدریس در دانشگاه Aix-Marseille ، شش سال در استراسبورگ تدریس کرد . وی در سال 1937 با آوینین ازدواج کرد.

ویل در فنلاند بود که جنگ جهانی دوم شروع شد. او از آوریل 1939 به اسکاندیناوی سفر کرده بود. همسرش اویلین بدون او به فرانسه بازگشت. ویل به اشتباه در فنلاند در آغاز جنگ زمستان به ظن جاسوسی دستگیر شد . با این حال ، گزارش هایی از زندگی وی که در معرض خطر قرار گرفته بود اغراق شده است. [8] ویل از طریق سوئد و انگلستان به فرانسه بازگشت و در ژانویه سال 1940 در لو هاور بازداشت شد. وی به دلیل عدم گزارش وظیفه متهم شد ، و در لو هاور و سپس روئین زندانی شد.. در زندان نظامی در بون-نوول ، ولسوالی روون ، از فوریه تا ماه مه ، ویل کار را انجام داد که باعث شهرت وی شد. وی در 3 مه 1940 محاکمه شد. محکوم به 5 سال ، وی به جای آن به یک واحد نظامی وصل شد و به وی فرصتی برای پیوستن به یک هنگ در چوربورگ داده شد . پس از سقوط فرانسه ، وی با خانواده خود در مارسی ملاقات کرد ، جایی که به دریا رسید. وی سپس به كلرمونت -فرند رفت و در آنجا موفق شد به همسرش اویلین كه در فرانسه تحت اشغال آلمان زندگی می كرد ، بپیوندد.

در ژانویه سال 1941 ، ویل و خانواده اش از مارسی به نیویورک سفر کردند. او باقیمانده جنگ را در ایالات متحده گذراند ، جایی که توسط بنیاد راکفلر و بنیاد گوگنهایم مورد حمایت قرار گرفت . به مدت دو سال ، او تدریس ریاضیات در مقطع کارشناسی ارشد در دانشگاه Lehigh ، جایی که او مورد قدردانی قرار نگرفت ، بیش از حد کار و کم درآمد بود ، اگرچه برخلاف دانشجویان آمریکایی خود ، نیازی به نگرانی در مورد آمادگی نداشت. اما ، او از لیگی خیلی بخاطر حجم کار سنگین تدریس آنها متنفر بود و قسم خورد که دیگر هرگز در مورد "لیگی" صحبت نخواهد کرد. [ نیاز به استناد ] او کار خود را در لیگی ترک کرد ، و سپس به برزیل نقل مکان کرد و در دانشگاه Universidade de São Paulo تدریس کرداز سال 1945 تا 1947 ، جایی که با اسکار زریسکی همکاری کرد . وی سپس به آمریكا بازگشت و از سال 1947 تا 1958 در دانشگاه شیكاگو مشغول تدریس بود ، قبل از اینكه به مؤسسه مطالعات پیشرفته بپیوندد ، جایی كه باقی مانده از دوران كار خود را سپری كند. وی در سال 1950 در کمبریج ، ماساچوست ، [9] در 1954 در آمستردام ، [10] و در 1978 در هلسینکی ، سخنگوی کامل در ICM بود . [11] در سال 1979 ، ویل دومین جایزه گرگ در ریاضیات را با ژان لری به اشتراک گذاشت .

کار [ ویرایش ]

ویل در تعدادی از مناطق کمکهای قابل توجهی انجام داد ، مهمترین آنها کشف ارتباطات عمیق بین هندسه جبری و نظریه اعداد است . این در کار دکتری او منجر به قضیه موردل-ویل (1928 ، آغاز شد و مدت کوتاهی در قضیه سیگل در نقاط انتگرالی اعمال شد ). [12] قضیه Mordell به در حال موقت اثبات؛ [13] ویل با استفاده از توابع قد برای اندازه گیری نقاط عقلانی ، و با استفاده از cohomology Galois ، جدایی آرگومان نزول نامحدود را به دو نوع رویکرد ساختاری آغاز کرد.، که برای دو دهه دیگر نمی تواند طبقه بندی شود. هر دو جنبه کار ویل به طور پیوسته به نظریه های اساسی تبدیل شده است.

از مهمترین دستاوردهای وی اثبات فرضیه ریمان در دهه 1940 برای عملکردهای zeta از منحنیهای بیش از مزارع محدود ، [14] و ریختن بعدی او مبانی مناسب برای هندسه جبری برای حمایت از آن نتیجه (از سال 1942 تا 1946 ، با شدت بیشتری) بود. به اصطلاح حدس ویل از حدود سال 1950 بسیار تأثیر پذیر بود. این اظهارات بعداً توسط برنارد کارگ ، [15] الكساندر گروتندیك ، [16] [17] [18] مایكل آرتین ، و سرانجام توسط پیر دلی نین اثبات شد كه سخت ترین مرحله را در سال 1973 به پایان رساند. [19] [20] [21 ] ][22] [23]

ویل حلقه آدل [24] را در اواخر دهه 1930 وارد کرد ، به دنبال رهبری کلود چواللی با بتها ، و اثبات نظریه ریمان-روچ را با آنها داد (نسخه ای در تئوری شماره اصلی او در 1967 ظاهر شد). [25] "تقسیم ماتریس" او ( وکتور دسته بندی Avant la lettre ) نظریه ریمان-روچ از سال 1938 پیش بینی خیلی زود ایده های بعدی مانند فضاهای بسته های مدولار بود. حدس ویل در شماره Tamagawa [26] برای سالهای زیادی مقاوم در برابر به اثبات رساند. سرانجام ، رویکرد آدلیک در تئوری نمایندگی اتومبیل اساسی شد . او اعتبار دیگری را برداشتحدس ویل ، حدود سال 1967 ، که بعداً تحت فشار سرگ لنگ (احترام Serre) به عنوان حدس تانیاماما-شیمورا (در رابطه با حدس تانیاماما-ویل) بر اساس یک سوال تقریباً فرموله شده از تانیاماما در کنفرانس نیکوی 1955 شناخته شد. نگرش او به حدس این بود كه نباید حدس را به راحتی حدس زد ، و در پرونده تانیاماما ، مدارك این شواهد تنها پس از كارهای محاسباتی گسترده ای كه از اواخر دهه 1960 انجام شد وجود داشت. [27]

نتایج معنی دار دیگر در دوگانگی و هندسه دیفرانسیل Pontryagin بود . [28] او مفهوم فضای یکنواخت را در توپولوژی کلی ، به عنوان محصول جانبی همکاری وی با نیکولاس بورباکی (که او یک پدر بنیانگذار بود) معرفی کرد. کار او در زمینه نظریه پوسته به سختی در مقالات چاپ شده خود ظاهر می شود ، اما مکاتبات با هنری کارتان در اواخر دهه 1940 و چاپ مجدد در مقالات جمع آوری شده وی اثرگذارترین اثبات بود. او همچنین نمادی را ایجاد کرد تا مجموعه خالی را به نمایش بگذارد .

ویل همچنین در اولین مقاله خود در سال 1926 ، هنگامی که نشان داد نابرابری ایزواتریمتریک کلاسیک بر روی سطوح منحنی غیر مثبت دارای سطح خوبی است ، در هندسه ریمانی سهم شناخته شده ای نیز داشته است . این مورد دو بعدی از آنچه بعداً به عنوان حدس Kartan-Hadamard شناخته شد ، ایجاد کرد .

وی کشف کرد که به اصطلاح نمایندگی ویل ، که قبلاً توسط ایروینگ سگال و دیوید شیل در مکانیک کوانتومی معرفی شده بود ، چارچوبی معاصر برای درک نظریه کلاسیک اشکال درجه دوم ارائه می دهد . [29] این همچنین آغاز یک پیشرفت اساسی توسط دیگران بود که تئوری نمایندگی و عملکردهای تتا را به هم متصل می کرد .

او همچنین چندین کتاب در مورد تاریخ تئوری شماره نوشت. ویل در سال 1966 به عنوان عضو خارجی انجمن سلطنتی (ForMemRS) انتخاب شد . [1]

به عنوان نماینده [ ویرایش ]

ایده های ویل سهم مهمی در نوشتارها و سمینارهای بورباکی ، قبل و بعد از جنگ جهانی دوم داشت .

او در صفحه 114 از خود می گوید زندگینامه که او مسئول نماد مجموعه تهی (بود ∅ ) و که آن را از نامه آمد Ø در الفبای نروژی ، که او به تنهایی در میان گروه Bourbaki با آن آشنا بود. [30]

اعتقادات [ ویرایش ]

اندیشه هندی (هندو) تأثیر زیادی بر ویل داشت. [31] او یک آگنوستیک بود ، [32] و به ادیان احترام می گذاشت. [33]

میراث [ ویرایش ]

سیارک 289085 آندروویل که در سال 2004 توسط ستاره شناسان در رصدخانه سن- سلیپیس کشف شد ، در یاد او قرار گرفت. [34] استناد به نامگذاری رسمی توسط مرکز Minor Planet در 14 فوریه 2014 ( MPC 87143 ) منتشر شد. [35]

کتابها [ ویرایش ]

کارهای ریاضی:

Arithmétique et géométrie sur les variétés algébriques (1935)
Sur les spaces à struktur uniforme et sur la topologie générale (1937) [36]
L'intégration dans les groupes topologiques et ses (1940)
ویل ، آندره (1946) ، مبانی هندسه جبری ، انتشارات محلولی انجمن ریاضی آمریکا ، جلد. 29، Providence، RI: انجمن ریاضی آمریکا ، ISBN 978-0-8218-1029-3، MR 0023093 [37]
Sur les courbes algébriques et les variétés qui s'en déduisent (1948)
Variétés abéliennes et courbes algébriques (1948) [38]
مقدمه à l'étude des variétés kählériennes (1958)
زیر گروه های ناپیوسته از گروه های کلاسیک (1958) یادداشت های سخنرانی شیکاگو
ویل ، آندره (1967) ، نظریه اعداد اساسی. ، Die Grundlehren der mathematischen Wissenschaften، 144 ، Springer-Verlag New York، Inc. ، نیویورک ، ISBN 3-540-58655-5، MR 0234930
سری Dirichlet و اشکال Automorphic ، Lezioni Fermiane (1971) یادداشت های سخنرانی در ریاضیات ، جلد. 189 ،
Essais historiques sur la théorie des nombres (1975)
توابع بیضوی با توجه به آیزنشتاین و کرونکر (1976)
تئوری شماره برای مبتدیان (1979) با ماکسول روزنلشت
گروههای Adeles and Algebraic (1982) [39]
نظریه اعداد: رویکردی در طول تاریخ از حموراپی گرفته تا افسانه (1984) [40]

مقالات جمع آوری شده:

Œuvres Scientifiques ، آثار مجموعه ، سه جلد (1979)
ویل ، آندره (مارس 2009). Œuvres Scientifiques / مقالات جمع آوری شده . Springer مجموعه آثار در ریاضیات (به انگلیسی ، فرانسوی و آلمانی). دوره 1 (1926-1951) (چاپ دوم). آبپاش شابک 978-3-540-85888-1.
ویل ، آندره (مارس 2009). Œuvres Scientifiques / مقالات جمع آوری شده . Springer مجموعه آثار در ریاضیات (به انگلیسی ، فرانسوی و آلمانی). جلد 2 (1954-1964) (چاپ دوم). آبپاش شابک 978-3-540-87735-6.
ویل ، آندره (مارس 2009). Œuvres Scientifiques / مقالات جمع آوری شده . Springer مجموعه آثار در ریاضیات (به انگلیسی ، فرانسوی و آلمانی). دوره 3 (1964-1978) (چاپ دوم). آبپاش شابک 978-3-540-87737-0.

زندگینامه :

فرانسوی: Souvenirs d'Apprentissage (1991) ISBN 3-7643-2500-3 . مرور به زبان انگلیسی توسط JE Cremona.
ترجمه انگلیسی: کارآموزی یک ریاضیدان (1992) ، ISBN 0-8176-2650-6 بررسی توسط Veeravalli S. Varadarajan ؛ نقد و بررسی توسط Saunders Mac Lane

خاطرات دخترش:

در خانه با آندره و سیمون ویل توسط سیلوی ویل ، ترجمه شده از بنیامین Ivry ؛ شابک 978-0-8101-2704-3 ، انتشارات دانشگاه شمال غربی ، 2010. [41]

منابع

https://en.wikipedia.org/wiki/Andr%C3%A9_Weil

+ نوشته شده در شنبه بیست و سوم فروردین ۱۳۹۹ ساعت 0:5 توسط علی رضا نقش نیلچی |

نابرابری کل چبیشف

از وی

در ریاضیات ، جمع نابرابری چبیشف ، به نام پافوتیت چبیشف ، نامگذاری شده است و بیان می کند که اگر باشد

$a_ {1} \ geq a_ {2} \ geq \ cdots \ geq a_ {n$

$b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n،$

سپس

${1 \ over n} \ sum _ {{k = 1}} ^ {n} a_ {k} \ cdot b_ {k} \ geq \ left ({1 \ over n \ sum _ {{k = 1 } ^ {n} a_ {k} \ سمت راست) \ سمت چپ ({1 \ بالای n n \ جمع _ {{k = 1}} ^ {n} b_ {k} \ درست).$

به همین ترتیب ، اگر

$a_ {1} \ leq a_ {2} \ leq \ cdots \ leq a_ {n$

$b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n،$

سپس

${1 \ over n} \ sum _ {{k = 1}} ^ {n} a_ {k} b_ {k} \ leq \ left ({1 \ over n} \ sum _ {{k = 1}} ^ {n} a_ {k} \ راست) \ سمت چپ ({1 \ over n} \ sum _ {{k = 1}} ^ {n} b_ {k} \ درست).$ [1]

فهرست

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

مبلغ را در نظر بگیرید

$S = \ sum _ {{j = 1}} ^ {n} \ sum _ {{k = 1}} ^ {n} (a_ {j} -a_ {k}) (b_ {j} -b_ {k })$

دو سکانس غیر در حال افزایش است ، بنابراین یک j - a k و b j - b k برای هر j ، k یک علامت یکسان دارند . از این رو S ≥ 0 .

با باز کردن براکت ها ، نتیجه می گیریم:

$0 \ leq 2n \ sum _ {{j = 1}} ^ {n} a_ {j} b_ {j} -2 \ sum _ {{j = 1}} ^ {n} a_ {j} \، \ sum _ {{k = 1}} ^ {n} b_ {k} ،$

از کجا

$\ frac {1} {n} \ sum_ {j = 1} ^ n a_j b_j \ geq \ left (\ frac {1} {n} \ sum_ {j = 1} ^ n a_j \ Right) \، \ left ( \ frac {1} {n} \ sum_ {k = 1} ^ n b_k \ درست).$

با نوشتن آن ، یک اثبات جایگزین به سادگی با نابرابری تنظیم مجدد بدست می آید

$\ displaystyle \ sum _ {i = 0} ^ {n-1} a_ {i} \ sum _ {j = 0 ^ {n-1} b_ {j} = \ sum _ i = 0} ^ { n-1} \ sum _ {j = 0} ^ {n-1} a_ {i} b_ {j} = \ sum _ {i = 0} ^ {n-1} \ sum _ {k = 0} ^ n-1} a_ {i} b_ {i + k ~ {\ text {mod}} ~ n} = \ sum _ {k = 0} ^ {n-1} \ sum _ {i = 0} ^ { n-1} a_ {i} b_ {i + k ~ {\ text {mod}} ~ n} \ leq \ sum _ {k = 0} ^ {n-1} \ sum _ {i = 0} ^ { n-1} a_ {i} b_ {i} = n \ sum _ {i} a_ {i} b_ {i}.}$

نسخه مداوم [ ویرایش ]

نسخه مستمر از نابرابری کل چبیشف نیز وجود دارد:

اگر f و g دارای ارزش واقعی باشند ، عملکردهای یکپارچه بیش از [0،1] ، چه افزایش دهنده یا هر دو کاهش نیافته ، سپس

$\ displaystyle \ int _ {0} ^ {1} f (x) g (x) \، dx \ geq \ int _ {0} ^ {1} f (x) \، dx \ int _ {0} ^ {1} g (x) \، dx،$

اگر نابرابری معکوس شود اگر یکی افزایش نیافته باشد و دیگری کاهش نیافته باشد.

منبع

https://en.wikipedia.org/wiki/Chebyshev%27s_sum_inequality

+ نوشته شده در چهارشنبه بیستم فروردین ۱۳۹۹ ساعت 23:26 توسط علی رضا نقش نیلچی |

برج هانوی

برج هانویْ (در بعضی منابع «برج‌های هانویْ») از سه میله و تعدادی دیسک در اندازه‌های متفاوت تشکیل شده‌است که می‌توان آن‌ها را بر میله‌ها جای داد.[۱][۲]

تاریخچه و صورت مسئله[ویرایش]

در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که یکی از آن‌ها حاوی تعدادی قرص طلایی بود. کاهنان معبد در تلاش بودند تا قرص‌های طلائی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند.[۳]

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

همانند شکل سه میله داریم. یکی از میله‌ها میله مبدأ (A)، دیگری میله کمکی (B) و دیگری میله مقصد (C) است. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است:

در هر زمان فقط یک دیسک را می‌توان جابجا نمود. نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد.

حل معادله[ویرایش]

هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد. مثلاً اگر n=۲ باشد، توالی حرکت به صورت زیر است:

حل مسئله برج هانوی با ۴ دیسک

دیسک ۱ را به میله B منتقل می‌کنیم.
دیسک ۲ را به میله C منتقل می‌کنیم.
دیسک ۱ را به میله C منتقل می‌کنیم.[۴]

حل مسئله برج هانوی با ۳ دیسک

توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد.

حال سؤال این است که آیا این مسئله به کمک تکنیک بازگشت قابل حل است؟ اصولاً چه مسائلی را می‌توان بازگشتی حل نمود؟

برای اینکه مسئله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مسئله اصلی (مسئله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر باشد. آنگاه می‌توان امیدوار بود که آن را به‌طور بازگشتی حل کرد! این ویژگی در مورد مسئله برج هانوی صدق می‌کند. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین‌ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم:

n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم.n - ۱ دیسک را که هم‌اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n - ۱ قرص راحتتر از جابجا نمودن n قرص است.[۵]

رج هانوی به زبان ++C[ویرایش]

تابع بازگشتی زیر به زبان ++C ترتیب حرکت‌ها را چاپ می‌کند:

void hanoi (int nDisk, char start, char temp, char finish)

{

  if (nDisk == 1)

  cout < " < " <برای مثال فراخوانی تابع به شکل ('hanoi(3, ‘A’, ‘B’, ‘C مسئله برج هانوی را با سه دیسک که در میله A قرار دارند و با کمک میله B به میله C منتقل خواهد شد، حل می‌کند.
ترتیب فراخوانی‌ها برای اجرا شدن دستور
درختی که ترتیب اجرای دستورها را نشان می‌دهد
برای این که به کاهنان کمک کنیم، باید دستور ('hanoi(64, ‘A’, ‘B’, ‘C را اجرا کنیم؛ ولی چه زمانی طول می‌کشد تا این دستور اجرا شود؟ در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟
در ابتدا باید بررسی کنیم که آیا تابع بازگشتی فوق کمترین تعداد حرکت را چاپ می‌کند؟ جواب مثبت است. زیرا واضح است که برای جابجا کردن بزرگترین دیسک از پایین میله A، بقیه دیسک‌ها باید در میله B باشند. فقط در این صورت این دیسک جابجا می‌شود. در فراخوانی‌های بعدی دیسک دوم از نظر بزرگی جابجا می‌شود و الی آخر. پس در این فراخوانی‌ها جابجایی بیهوده‌ای صورت نمی‌گیرد. همچنین توالی حرکت‌ها برای هر n منحصربه‌فرد است. یعنی برای یک n دو توالی متمایز از جابجایی‌ها وجود ندارد که تعداد جابجایی آن‌ها کمتر یا مساوی این حالت باشد.
حال به مسئله مرتبه اجرایی مسئله می‌پردازیم: فرض کنیم (T(n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق (T(n - ۱ حرکت برای انتقال n - ۱ دیسک به میله کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله مقصد، و باز (T(n - ۱ حرکت برای انتقال n - ۱ دیسک موجود در میله کمکی به میله مقصد نیاز است. پس می‌توان نوشت:
T(n) =2 T(n - ۱) + ۱
با حل این رابطه بازگشتی داریم:
T(n) = 2n-۱
همان‌طور که مشاهده می‌کنیم مرتبه اجرایی این الگوریتم (O(2n است که هرچند مرتبه مناسبی نیست، این روش حداقل تعداد حرکتهای ممکن را می‌دهد.
اگر فرض کنیم کاهنان با سرعت عمل زیاد توانسته باشند به صورت شبانه‌روزی و نسل به نسل در هر دو ثانیه یک قرص را جابجا کنند، برای انتقال تمامی ۶۴ قرص به میله مقصد، در حدود ۱٫۱۶۹ ترلیون (میلیون میلیون) سال زمان لازم دارند!
در واقع ما از روش Divide and Conquer یا حل و تقسیم برای ارائه راه حل استفاده نموده‌ایم. اما چون در تقسیم مسئله اصلی به دو زیر مسئله، اندازه ورودی‌های زیر مسئله‌ها نزدیک به اندازه ورودی اصلی هستند، کارایی الگوریتم مطلوب نیست.
حل مسئله برج هانوی به روش غیربازگشتی[ویرایش]
این مسئله علاوه بر روش تابع بازگشتی راه حلهای غیربازگشتی نیز دارد. در بالا به این نتیجه رسیدیم که بهترین راه حل برای جابجا کردن n دیسک ۲n - ۱ حرکت نیاز دارد. در نتیجه مرتبه راه حلهای آن در بهینه‌ترین حالت، چه بازگشتی و چه غیربازگشتی، از مرتبه (O(2n خواهد بود. اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای مصرفی آن است. حل بازگشتی مسئله، فراخوانی‌های تو در تو و فضای پشته از مرتبه (O(n نیاز دارد. در حالی که می‌توان با استفاده از روش غیربازگشتی این مرتبه را به (O(1 کاهش داد. البته این مسئله تنها دلیل بررسی روش غیربازگشتی نیست. تبدیل مرتبه مصرف فضا از (O(n به (O(1 زمانی که مرتبه اجرایی الگوریتم (O(2n است چندان قابل توجه نیست. دلیل دیگر می‌تواند این باشد که برخی زبانهای برنامه‌نویسی از فراخوانی بازگشتی توابع پشتیبانی نمی‌کنند و مجبور به استفاده ار روش‌های غیربازگشتی هستند. اما دلیل اصلی این است که با بررسی این روش‌ها تمرین کوچکی برای تبدیل الگوریتمهای بازگشتی به غیربازگشتی انجام می‌دهیم.
تا کنون چندین روش مختلف جهت پیاده‌سازی غیربازگشتی حل مسئله برج هانوی ارائه شده‌است، که ما در اینجا دو روش را معرفی کرده، و تنها یکی از آن‌ها را به‌طور کامل بررسی می‌کنیم. توجه داشته باشید که همه جزئیات حل مسئله به صورت دقیق و مشروح مطرح نمی‌شود، و استدلال قسمتی از نتیجه‌گیری‌ها به عنوان تمرین به شما واگذار می‌شود.
روش اول:
حل مسئله برج هانوی را می‌توان معادل پاسخ دادن به این سؤال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟
کدام دیسک؟
فرض کنیم دیسکهایی به شعاع y ,x و z که رابطه x بی‌نهایت را برای آن در نظر می‌گیریم. حال به استدلالهای منطقی زیر توجه کنید:
استدلال ۱
x برابر ۱ است. چرا که بر اساس قوانین حاکم بر مسئله، هیچ دیسکی نمی‌تواند روی دیسک ۱ قرار بگیرد. در نتیجه این دیسک همیشه بالاترین دیسک موجود در یکی از میله‌ها است.
استدلال ۲
در اولین مرحله دیسک ۱ جابجا می‌شود. در آغاز همه دیسکها روی یک میله قرار دارند که دیسک ۱ بالاترین دیسک آن است.
استدلال ۳
دیسکهایی که طی دو مرحله متوالی جابجا می‌شوند حتماً متمایز هستند. این مسئله از بهینه بودن راه حل ما ناشی می‌شود. اگر قرار باشد طی دو مرحله متوالی یک دیسک خاص را جابجا کنیم، می‌توانیم دو مرحله را با هم ادغام کرده و کل جابجایی را یکجا انجام دهیم.
استدلال ۴
با توجه به قوانین حاکم بر مسئله، دیسک z نمی‌تواند حرکت کند. چرا که دیسکهای x و y هر دو از آن کوچکتر هستند.
استدلال ۲ می‌گوید که اولین حرکت همیشه با دیسک ۱ است. استدلال ۳ می‌گوید حرکت بعدی با دیسکی غیر از دیسک ۱ است. استدلال ۴ می‌گوید این دیسک نمی‌تواند بزرگترین دیسک موجود در بالای میله‌ها باشد. پس در مرحله بعدی دیسک y جابجا خواهد شد؛ و بالاخره حرکت بعدی باز هم با دیسک ۱ است (چرا؟).
پس با بررسی منطقی خود به این نتیجه رسیدیم که دیسک ۱ و دیسکی که بزرگترین دیسک در آن مرحله نیست، به صورت متناوب جابجا می‌شوند. مراحل با شماره فرد برای دیسک ۱، و مراحل با شماره زوج برای دیسک y.
کدام میله؟
حال که می‌دانیم در هر مرحله کدام دیسک جابجا می‌شود، به سراغ میله مقصد می‌رویم. در مراحل زوج که دیسک y منتقل خواهد شد، تشخیص میله مقصد بسیار آسان است. چرا که روی یکی از میله‌ها دیسک ۱ قرار دارد که دیسک y نمی‌تواند روی آن قرار بگیرد. در نتیجه به تنها میله باقی‌مانده (میله دیسک z) منتقل می‌شود. در مورد مراحلی هم که دیسک ۱ قرار است جابجا شود، می‌توان اینطور استدلال کرد:
فرض کنیم دیسک ۱ روی میله A قرار داشته باشد و آن را به میله C منتقل کنیم. در مرحله بعدی دیسک y جابجا می‌شود؛ و در مرحله بعد باز هم دیسک ۱ باید جابجا شود. حال اگر این دیسک را به میله A بازگردانیم، به نوعی کار اضافی و بازگشت به عقب انجام داده‌ایم. برای آشکار شدن این موضوع کافی است مسئله برج هانوی را با دو دیسک حل کنید، و در حرکت دوم دیسک ۱، آن را به میله‌ای بازگردانید که از آن آمده بود. پس می‌توان گفت در حرکتهای متوالی، دیسک شماره ۱ به میله‌ای حرکت می‌کند که از آن به میله فعلی خود نیامده است. این مسئله نه تنها در مورد دیسک ۱، که در مورد همه دیسکها صادق است. یعنی همه دیسکها در حرکتهای خود به سمت میله‌ای می‌روند که در حرکت قبلی خود از آن نیامده‌اند. اما لحاظ کردن این شرط برای این دیسکها لازم نیست. چرا که در هر مرحله، تنها یک انتخاب برای حرکت خود دارند.
تنها مسئله باقی‌مانده، میله مقصد دیسک ۱ در اولین حرکت خود است. زمانی که این دیسک اولین حرکت خود را انجام می‌دهد، نمی‌توان از استدلال فوق برای تشخیص میله مقصد استفاده کرد (چرا!؟). استدلال این قسمت را هم که چندان دشوار نیست به شما وا می‌گذاریم و تنها به بیان نتیجه می‌پردازیم: اگر n (تعداد دیسکها) زوج باشد، دیسک ۱ در اولین حرکت به میله کمکی (یعنی میله B)، و در غیراینصورت به میله مقصد (یعنی میله C) منتقل می‌کنیم.
به این ترتیب حل مسئله برج هانوی به صورت غیربازگشتی به صورت کامل پیاده‌سازی می‌شود. حال می‌دانیم که در هر مرحله کدام دیسک به کدام میله منتقل می‌شود. تعداد مراحل هم همواره برابر ۲n - ۱ است. پیاده‌سازی کد این الگوریتم را نیز به شما وا می‌گذاریم تا با کار روی آن به خوبی بر الگوریتم تشریح شده مسلط شوید.
روش دوم:
یکی دیگر از روش‌های پیاده‌سازی غیربازگشتی حل مسئله برج هانوی از الگوریتم زیر تبعیت می‌کند:
void hanoi (int nDisk, char start, char temp, char finish)
{
  int max = nDisk;
  char dest = finish;
  int disk = max;
  while(true)
  {
  while(disk> 0)
  {
  if(moving disk succeeds)
  {
  if(disk == max)
  {
  max--;
  if(max == 0)
  {
  return;
  }
  }
  dest = the final place of max;
  }
  else
  {
  dest = the alternative place between dest and the current place of disk;
  }
  disk--;
  }
  p and q = the places different of dest;
  disk = the smaller of the disks on top of p and q;
  dest = the place between p and q with greater disk on top;
  }
}

در پایان توجه داشته باشید که دو روش ذکر شده، تنها روش‌های پیاده‌سازی غیربازگشتی حل مسئله نیستند.
برنامه برج هانوی به زبان c:
# include 
# include 
# define COUNT 8

enum Bar{L,C,R};
struct disk{int Size,Color;};
struct stack{int i; disk *Disks;};
void transfer(int,Bar,Bar,Bar);
void init(); // Init bars
void MoveDisk(Bar from,Bar to);
void DrawBars();
stack Bars[3]={ {0,{0}} ,{0,{0}}, {0,{0}} };
int main(void)
{
 textmode(C4350);
 clrscr();
 init();
 DrawBars();
 transfer(COUNT,L,R,C);
 getch();
 return 0;
}
char ConvertBarEnum2Char(Bar E){
 char r=0;
 switch (E) {
 case L: r='L'; break;
 case C: r='C'; break;
 case R: r='R'; break;
 }
 return r;
}

void msg(Bar from,Bar to){
 gotoxy(25,4);
 textattr(15|16*0);
 cprintf("Press anykey to move from %c to %c",ConvertBarEnum2Char(from),ConvertBarEnum2Char(to));
 gotoxy(37,5);
 cprintf("Esc = Exit");
}

void transfer(int n,Bar from,Bar to,Bar temp){
if(n>0){
 transfer(n-1,from,temp,to);
 msg(from, to);
 MoveDisk(from,to);
 transfer(n-1,temp,to,from);
 }
}
void init(){
Bars[L].Disks=new disk[COUNT];
for(int i=0;i

ادامه نوشته

+ نوشته شده در جمعه دوازدهم مهر ۱۳۹۸ ساعت 10:6 توسط علی رضا نقش نیلچی |

آموزش ریاضی

ریاضیات، معجزات و پارادوکس ها

فهرست

تعریف [ ویرایش ]

نمودار دو بخشی [ ویرایش ]

تغییرات [ ویرایش ]

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

نمودارهای بدون جهت [ ویرایش ]

نمودارهای هدایت شده [ ویرایش ]

نمودارهای بی اهمیت [ ویرایش ]

خصوصیات [ ویرایش ]

طیف [ ویرایش ]

ایزومورفیسم و ​​تغییر ناپذیرها [ ویرایش ]

قدرت ماتریس [ ویرایش ]

ساختار داده ها [ ویرایش ]

همچنین به [ ویرایش ] مراجعه کنید

فهرست

ساخت و فرمول مجموعه سه گانه [ ویرایش ]

فهرست

اخلاق شناسی [ ویرایش ]

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

چیدن جوراب [ ویرایش ]

لرزش دست [ ویرایش ]

شمارش مو [ ویرایش ]

مشکل تولد [ ویرایش ]

مسابقات تیمی [ ویرایش ]

مبلغ زیر مجموعه [ ویرایش ]

کاربردها و برنامه ها [ ویرایش ]

فرمول های جایگزین [ ویرایش ]

فرم قوی [ ویرایش ]

کلیات اصل کبوتر [ ویرایش ]

مجموعه های بی نهایت [ ویرایش ]

مکانیک کوانتومی [ ویرایش ]

فهرست

درخت مارکوف [ ویرایش ]

خواص دیگر [ ویرایش ]

قضیه مارکوف [ ویرایش ]

ماتریس [ ویرایش ]

منبع

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

مثال 1 (1985) [ ویرایش ]

مثال 2 (قرون دیگر) [ ویرایش ]

همچنین مشاهده کنید [ ویرایش ]

منابع

از وی

فهرست

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

نسخه مداوم [ ویرایش ]

تاریخچه و صورت مسئله[ویرایش]

حل معادله[ویرایش]

رج هانوی به زبان ++C[ویرایش]

حل مسئله برج هانوی به روش غیربازگشتی[ویرایش]

پیوندهای روزانه

نوشته‌های پیشین

آرشیو موضوعی

پیوندها

ایزومورفیسم و تغییر ناپذیرها [ ویرایش ]