دعوت به رمزگذاری

مشکلات

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

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

و این همان چیزی است که اخیراً اتفاق افتاده است: مشکل فقط در (1) رمزگذاری یا رمزگشایی یک پیام نیست ، بلکه در "تأیید کردن" آن است، یعنی: (2) شناسایی فرستنده پیام و (3) درک آیا پیام دست نخورده است یا در حین انتقال دستکاری شده است . اما همچنین: (4) توافق با کسی در مورد یک قطعه داده که مخفی نگه داشته شود ، حتی اگر از یک کانال انتقال ناامن استفاده کنید. (5) به طور تصادفی تصمیم بگیرید، با شانس موفقیت برابر در مقایسه با یک همکار غیرقابل اعتماد . (6) بدون اینکه منبع یا راز آن را فاش کنید، آگاه سازید که علم خاصی دارید .
اولین مشکل ذکر شده، امنیت انتقال است که فیلم های جنگی و جاسوسی متعددی ما را به آن عادت کرده اند. دوم این است که از صحت فرستنده ; در این مورد، علاوه بر بازی دوگانه جاسوسی، لازم است مشکلات مدرن تراکنش های اقتصادی از راه دور را به خاطر بسپاریم: دستگاه خودپرداز یا به اصطلاح امضای دیجیتال که به ما امکان می دهد حتی از طریق ایمیل نیز شناسایی شویم. سومین مشکل ذکر شده مربوط به یکپارچگی پیام است . این تله ای است که پیشینه های معروفی دارد: رومئو به مانتوا پناه می برد و از پرستار مورد اعتماد خود (به اصطلاح!) خبر دروغ مرگ ژولیت را دریافت می کند. مشکلات (4) قرعه کشی از راه دور و (5) تعویض کلید مواردی هستند که قبلاً آلیس و باب را در حال کار در آنها دیده ایم و راه حل آنها بعداً آشکار خواهد شد. آخرین مشکل لیست شده به اصطلاح به دانش صفر می پردازد: چگونه می توانیم تضمین کنیم که اطلاعاتی داریم بدون اینکه جنبه های اساسی آن آشکار شود؟ به عنوان مثال، چگونه نیکولو فونتانا، تارتالیای معروف، در قرن شانزدهم اعلام کرد که فرمول حل رادیکال های معادلات درجه سوم را بدون اینکه مجبور باشد آن را برای جامعه ریاضی آشکار کند (حداقل تا زمانی که موفق به انجام این کار شود) کشف کرده است. )؟ در این مورد، مشکل دشوار نیست: فقط باید نشان دهید که می دانید چگونه ریشه برخی از معادلات پیشنهاد شده توسط دیگران را محاسبه کنید. هر کسی به راحتی می تواند درستی پاسخ را تأیید کند و پس از چند اجرا از این دست خود را متقاعد کند که هرکسی که ریشه معادلات را پیدا کرده است، لزوماً باید یک روش مطمئن داشته باشد، یک فرمول دقیقاً: تأیید اینکه آیا یک عدد معین یک ریشه است یا خیر، یک عملیات است. بسیار ساده تر از یافتن آن، حداقل برای کسانی که فرمول آن را نمی دانند. اما در عوض به این فکر کنید که اختراعی ساخته اید که برای ثبت اختراع آن درخواست بودجه می کنید: یک نگاه به پروژه برای درک ایده کافی است و می فهمید که ایده همه چیز است. در همان زمان، شما می خواهید وام دهنده شما مطمئن باشد که مکانیسم کار می کند. اعتماد کنیم یا نه؟ کدام مسیر را دنبال کنیم؟
واضح است که در این مسیر مشکلات چند برابر می شود. برای اکثر آنها، عمل راه حل های تجربی، خاص و متفاوت از مورد به مورد پیدا کرده است. ریاضیات سعی می کند همه این مسائل را به عنوان موارد خاصی از یک مسئله واحد و اساسی ببیند.

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

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

اطلاعات مختصر و جذاب در مورد رویدادهای تاریخی و ایده های مدرن فعالیت رمزنگاری از نقطه نظر فنی در Sgarro [1] و Berardi, Beutelspacher [2] موجود است. درمان گسترده‌تر، اما همچنان به شیوه‌ای قانع‌کننده روایت می‌شود، برخورد سینگ [3] است. هرکسی که بخواهد مشکل را از نقطه نظر تأثیر آن بر توسعه سیستم های ارتباطی دیجیتال - و در نتیجه عمدتاً با توجه به مشکلات اجتماعی و حقوقی - طرح ریزی کند، می تواند با Giustozzi، Monti و Zimuel [4] مشورت کند.

کلید رمزگذاری

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

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

نقش اساسی کلید رمزگذاری حتی در دوره ای مدون شد که در آن فعالیت رمزنگاری که همیشه در زمینه نظامی به طور گسترده مورد استفاده قرار می گرفت به نوعی حداکثر استفاده رسید. فیلولوژیست هلندی ژان گیوم کرکخوف (1835-1903)، در کار خود La cryptographie militaire در سال 1883، مشاهده می کند که امنیت یک سیستم رمزنگاری تنها به محرمانه بودن کلید بستگی دارد.
به عبارت دیگر، بدون بحث پذیرفته می شود که یک رهگیر احتمالی از پیام های رمزگذاری شده و همچنین از سیستم رمزگذاری استفاده شده آگاه می شود: چیزی که او نباید بداند کلید است. امنیت انتقال به محرمانه بودن آن بستگی دارد و بالعکس: رهگیر فقط باید کلید را بداند تا بتواند همه پیام ها را رمزگشایی کند.
پس مشکل از دید کسانی که می خواهند پیام های محرمانه رد و بدل کنند چیست؟ واضح است که قبل از هر چیز کلید سیستم رمزنگاری باید برای چند نفر شناخته شود، کسانی که ارسال می کنند و کسانی که دریافت می کنند و احتمالاً هیچ کس دیگری، زیرا - همانطور که می دانیم - رهگیرها ظلم های کمی دارند. و سپس لازمه سادگی را با هم ترکیب کنید - بتوانید آن را به خاطر بسپارید بدون اینکه اسنادی را در اطراف آن بنویسید که امکان یافتن آن وجود دارد و برای سهولت استفاده - همراه با نوعی پیچیدگی که اجازه نمی دهد به راحتی آن را ردیابی کنید. با بررسی تعداد معینی از پیام های رمزگذاری شده. بیایید بگوییم که مشکلات کلید رمزنگاری به اشتراک گذاری آن بین چندین موضوع و رابطه متعادل بین سادگی و پیچیدگی استفاده است.

کمی تاریخچه

به گفته سوتونیوس ویتا سزاروم ، یکی از قدیمی‌ترین سیستم‌های رمزی به ژولیوس سزار برمی‌گردد و در جنگ او علیه گول‌ها مورد استفاده قرار می‌گرفت. مشخص است که قبلاً از سیستم‌های دیگر، اغلب بسیار اصلی نیز استفاده شده بود، اما این یکی از Cesare شاید اولین موردی باشد که گاه به گاه نیست: یک روش، یک سیستم را پیشنهاد می‌کند، با کلیدهای مختلف قابل تکرار است.
این ایده در حقیقت آنقدر ساده است که زیرکی گول ها را ارج نمی نهد، اما ما آن را برای راحتی توضیح فرض می کنیم: پس از مرتب کردن حروف به ترتیب الفبایی کلاسیک، دایره ای در نظر گرفته شده - بنابراین، با حرف a به دنبال z - هر حرف به همان میزان به سمت راست منتقل می شود. بنابراین، اگر ترجمه از دو حرف باشد، a تبدیل به c، b تبدیل به d ... و به همین ترتیب، تا زمانی که z تبدیل به b شود مانند طرح زیر که در آن هر حرف متن ساده بالای حرف رمزگذاری شده مربوطه قرار می‌گیرد :

abcdefghilmnopqrstuvz
cdefghilmnopqrstuvzab

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

n'=n+k

جایی که n نشان دهنده موقعیت حرفی است که باید رمزگذاری شود، n' موقعیت حرف رمزگذاری شده مربوطه (n, n' =1, 2, ... , 21) و k کلید است، یک عبارت از نوع خواهد بود. استفاده می شود:

n'=an+b

در این مورد ، کلید توسط جفت اعداد صحیح مرتب شده (a, b) داده می شود که هر دو از 21 تجاوز نمی کنند . لازم است که اجازه دهید GCD(a,21)=1 باشد ، یعنی عدد صحیح a هیچ مقسوم علیه مشترکی با 21 نداشته باشد (همانطور که می گویند: a و 21 باید برای یکدیگر اول باشند ). محاسبه (تمرین!) تعداد رمزهای مشابه که متمایز هستند آسان است: 252 است که یکی از آنها هنوز هویت است.
تعداد رمزها بیشتر از قبل است، اما هنوز خیلی کم است که نمی‌توان با حمله رمزگشاهای ماهر روبرو شد. یک استراتژی می تواند این باشد که به جای استفاده از یک فرمول ساده مانند ترجمه یا قرابت، هر گونه جایگشتی را برای تعیین حروف رمزگذاری شده فرض کنیم. 21 جایگشت احتمالی وجود دارد! و این عددی است که دارای 20 رقم اعشاری است و هر رمزی را از خطر شکسته شدن در اثر تلاش محافظت می کند. اما خوب نیست. زیرا هر کسی که ارسال می‌کند و دریافت می‌کند باید جایگشت حروفی را که انتخاب کرده‌اند، به زیان پنهان کاری، در جایی ثبت کند: کلید رمزنگاری با اطلاعاتی که به خاطر سپردن و استفاده ساده باشد داده نمی‌شود، بلکه خود کل جایگشت است.
بنابراین مشکلی که پیش می‌آید این است: چگونه با استفاده از یک مکانیسم ساده برای به خاطر سپردن، یک جایگشت از حروف الفبا ایجاد کنیم؟ در عمل این مشکل باعث ایجاد ایده کلمات کلیدی شده است . در این مرحله، از زمان سزار، ما قبلاً به رنسانس رسیده‌ایم، زمانی که تکنیک‌های رمزنگاری - مرتبط با رشد تجارت و تماس‌های دیپلماتیک بین دولت‌ها - از یک دوره تاریک احیا شدند.
پس از برداشتن یک کلمه بدون تکرار، حروف آن به عنوان اولین جایگشت مورد استفاده قرار می گیرد و از یک مکان خاص شروع می شود. حروف دیگر رمز در ادامه فهرست شده‌اند و از حروفی که قبلاً استفاده شده‌اند صرفنظر می‌کنند. به عنوان مثال، با استفاده از کلمه کلیدی hello که از حرف d شروع می شود، یعنی از جایگاه چهارم، جایگشت زیر به دست می آید:

abcdefghilmnopqrstuvz
tuzsalvebcdfghimnopqr

در این مورد، کلید رمزنگاری به جفت کاهش می یابد (سلام، 4). اما داستان به اینجا ختم نمی شود: یک رمزگشا با دانش خوبی از آمار، برخی جداول و تعداد کافی پیام رمزگذاری شده که A و B رد و بدل کرده اند، می تواند به سرعت کلید را ردیابی کند. طبیعتاً، او می‌داند که حروف مختلف الفبا با چه فراوانی در متون همسانی که می‌خواهد رمزگشایی کند - چه حروف عاشقانه یا پیام‌های نظامی - ظاهر می‌شوند و به زودی، برای مثال، حروف صدادار و صامت‌های خاص را بیشتر تشخیص خواهد داد. از حروف دیگر استفاده می شود. همه با ابهام زیاد، اما فقط برای لحظه. او آزمایش‌ها، حدس‌ها، تلاش‌های کم و بیش انگیزه‌ای را انجام می‌دهد تا زمانی که کلمه‌ای با معنای کامل پیدا کند یا دوره‌ای را که رمزگذاری انجام می‌شود تشخیص دهد: اساساً طول کلمه کلیدی.
در این مرحله انجام شده است. از اینجا یک گام کوتاه برای شکستن کل رمز است.
چگونه می توان فرکانس های آماری را لغو کرد و از تکرارهای دوره ای اجتناب کرد؟ به راحتی می توان تشخیص داد که تجزیه و تحلیل فرکانس با این واقعیت امکان پذیر است که رمز جایگزین تک الفبایی است ، یعنی هر حرف همیشه با همان حرف در طول انتقال کل پیام رمزگذاری می شود. این اشکال را می توان با جابجایی به رمزهای جایگزین چند الفبایی حل کرد ، برای مثال با استفاده از صد علامت مختلف، از هر ماهیت، برای رمزگذاری 21 حرف متن ساده. برای مثال، اگر بدانیم که در پیام‌هایی که به آن علاقه داریم، حرف a به طور متوسط ​​ده بار از صد مورد اتفاق می‌افتد، کافی است از ده علامت مختلف برای رمزگذاری آن استفاده کنیم. نگران نباشید: لازم نیست بین متن ساده و الفبای رمزگذاری شده تناظر یک به یک وجود داشته باشد، بلکه فقط باید یکسان باشد: عبور از متن رمزگذاری شده به متن ساده. به این ترتیب، حرف a یک بار به یک صورت و یک بار به روش دیگر به ده روش مختلف رمزگذاری می شود و بسامد آن عملاً لغو می شود: اما هرکس پیام را دریافت کند و سیستم رمزگذاری را بشناسد، در هر صورت قادر است تا ده مورد را تشخیص دهد. نمادهای مختلف باید به عنوان a تفسیر شوند.

رمز دیسک

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

با این حال، گام بعدی که در قرن پانزدهم توسط برخی از محققان رنسانس شناسایی شد و به صراحت توسط هنرمند و ریاضیدان بزرگ لئون باتیستا آلبرتی (1406-1472) پیشنهاد شد، تعیین کننده است: او در اثر خود Modus scribendi in ziferas در سال 1466، چند الفبایی را معرفی می کند. جایگزینی که انجام آن آسان است و چرخه‌هایی را که در رمزگذاری رخ می‌دهد و بنابراین درک دوره‌های رمز را بسیار دشوارتر می‌کند. این ایده تا دوران مدرن به طور قابل ملاحظه ای بدون تغییر باقی خواهد ماند.
برای این منظور باید خود را به رمز پویا مجهز کرد : هر حرف از متن ساده بسته به موقعیت آن در خود متن، هر از گاهی به طور متفاوت رمزگذاری می شود. آلبرتی، به عنوان سازنده ماهری که بود، مکانیزم عملی را نیز ابداع کرده بود، مجهز به دو نسخه الفبا بر روی دو دیسک که می‌توانستند نسبت به یکدیگر بچرخند و بنابراین از طرق مختلف با یکدیگر مکاتبه کنند. : پس از رمزگذاری یک حرف از پیام، یک چرخش ساده از یک یا چند بریدگی به شما امکان می دهد مکاتبات را برای حرف بعدی که باید رمزگذاری شود تغییر دهید. برای استفاده از آن توسط شخص دریافت کننده پیام، دانستن نقطه تطابق اولیه دیسک ها و تعداد بریدگی هایی که باید بعد از هر عملیات رمزگذاری بچرخند، کافی است. این کلید سیستم رمزگذاری ایجاد شده توسط لئون باتیستا آلبرتی است. این ایده مربوط به تناظر پویا بین حروف الفبا که در طول پیام متغیر بود، توسط دیپلمات فرانسوی بلز دو ویژنر (1523-1596) در قرن بعد محقق شد و مورد استفاده قرار گرفت و در اثر او Traité des chiffres ou گسترده شد. secrètes maniéres d'escrire of 1586: رمزهای به دست آمده، که عملاً تا دهه 1900 فعال بودند، همگی نام او را گرفتند: رمزهای ویژنر.
در این رمزها، تناظر پویا با استفاده از یک کلمه متعارف ترکیب می شود تا به عنوان کلیدی استفاده شود که دیگر نیازی به انتخاب بدون تکرار ندارد، که به نظر می رسد اولین رسمی سازی آن در رساله De furtivis literarum notos، vulgo وجود دارد. de ziferis ، نوشته شده در سال 1563 توسط دانشمند و فیلسوف Giovan Battista della Porta.

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

ریاضیات بخون و همیشه خوشحال خواهی بود.

عملیات به شرح زیر است:
1. هر حرف از پیام ساده مطابق با یک حرف کلید قرار می گیرد که در صورت لزوم مطابق با حروف آن تکرار می شود:

ریاضی بخون
سلام سلام

سلام علیکم همیشه
شاد سلام سلام سلام سلام سلام

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

3. برای رمزگذاری پیام، از حروف کلمه کلیدی برای شناسایی رمز استفاده می شود: بنابراین، برای حرف اول s ، خطی که با s همان hello شروع می شود استفاده می شود و n مشخص می شود . برای حرف t ساده بعدی، رمز رمزی است که با a در hello شروع می شود و بنابراین حتی پس از رمزگذاری t باقی می ماند. اکنون از l کلمه کلیدی برای رمزگذاری u و تبدیل آن به g و غیره استفاده می کنیم . پیام رمزگذاری شده شکل می گیرد...

تو ادامه بده برای درک بهتر استفاده از رمز پویا، مشاهده کنید که چگونه از این قطعه کوچک به نظر می رسد که حرف e بار اول با p و دفعه بعد با c رمزگذاری شده است . برعکس، حرف f مخفف m و t به دلیل این واقعیت است که این حروف موقعیت‌های مختلفی را در پیام متنی معمولی اشغال می‌کنند.
بدیهی است که با تغییر کلمه کلیدی، تعداد نامحدودی از رمزها از این طریق به دست می آید. و اگر کلید به اندازه کافی طولانی باشد - و محدودیتی که در آن حروف تکراری وجود ندارد دیگر مورد نیاز نیست - دوره سیستم رمزگذاری به نسبت طولانی است. با این حال، ما نباید روش های آمار و یا توانایی و سرسختی رمزگشاها را دست کم بگیریم: برای دانستن تعداد کافی از پیام های رمزگذاری شده، در طول زمان روش هایی برای یافتن دوره سیستم رمزگذاری و از اینجا به صورت تجربی ایجاد شده است. راه، کلید را ردیابی کنید.
این نتایج، ناگفته نماند که در زمینه نظامی به دست آمده است. معماران اصلی افسر پروس فریدریش ویلهلم کاسیکی (1805-1881) و بعدها ژنرال آمریکایی ویلیام فردریک فریدمن (1891-1969) بودند. ایده اتخاذ شده توسط کاسیسکی مبتنی بر تجزیه و تحلیل تکرار گروه‌هایی از حروف است که در رابطه مستقیم با طول کلمه کلیدی قرار می‌گیرند: این امکان را فراهم می‌کند که رمز به اجزای تک الفبایی خود تقسیم شود، که رمزگشایی آنها ساده‌تر است. کار فریدمن در عوض بر این احتمال تمرکز دارد که هر دو حرف در یک متن رمزی در واقع با یک حرف متن ساده مطابقت دارند. شرح مختصری از این روش ها، بدون پیچیدگی های فنی بیش از حد، را می توان در متن چابک Berardi و Beutelspacher [2] یافت. بنابراین ما به سپیده دم دهه 1900 رسیدیم، زمانی که دستگاه های الکترومکانیکی برای پردازش مقادیر روزافزون داده هایی که به عملیات رمزگشایی متصل بودند و در نتیجه برای عملیات دوگانه تنظیم دقیق سیستم رمزگذاری آماده بودند. .

ماشین های رمزگذاری

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

مجموعه ای از روش ها برای رمزگشایی مفید بودند، از جمله روش هایی که از طریق به دست آوردن اطلاعات از طریق جاسوسی سنتی و همچنین آمار، مطالعه ساختارهای جبری و ترکیبی، بررسی عادات فرستنده های آلمانی و عبارات عامیانه، تجزیه و تحلیل مقادیر زیادی از داده ها با استفاده از دیگر ماشین‌های الکترومکانیکی مخصوص ساخته شده ( بمب‌های معروف ، به‌اصطلاح تیک تاک کلاسیک‌شان). برای سهولت بیشتر در کار و صرفه جویی آشکار در ابزار، انیگما از یک بازتابنده استفاده کرد که به لطف آن از کلیدهای یکسان و عملیات های مشابه هم برای رمزگذاری و هم برای رمزگشایی استفاده می شد: متن ساده روی صفحه کلید تایپ می شود و دستگاه به طور مناسب مرتب می شود. با توجه به کلید، متن کدگذاری شده روی صفحه نمایش خوانده می شود. برعکس، اگر متن کد شده را تایپ کنید، متن ساده را مستقیماً می خوانید. سیستم رمزنگاری برگشت پذیر است و این ویژگی ساختاری عناصر اساسی را برای رمزگشایی فراهم می کند.
داستان جذاب این ماشین، اصول ساخت آن و اینکه چگونه گروهی از ریاضیدانان، فیلسوفان و معمدانان که توسط فرماندهی انگلیسی در پارک بلتی جمع شده بودند، توانستند آن را حداقل در برخی از جنبه های آن، به ویژه برای جنگ در دریا رمزگشایی کنند. آنها به خوبی در زندگینامه آلن تورینگ نوشته اندرو هاجز t6 و در تاریخ رمزنگاری سینگ [3] آمده است.
سایر ماشین‌ها و سیستم‌های دیگر بخشی از تاریخ رمزنگاری قرن بیستم هستند. بهترین سیستم شناخته شده که برای طولانی ترین مدت در برابر حملات رمزگشایی مقاومت کرده است، سیستمی است که به طور رسمی در سال 1977 توسط دولت ایالات متحده تأسیس شد، DES ( استاندارد رمزگذاری داده ها )، یک رمز تک الفبایی که امنیت آن بر روی کلید 56 بیتی (که 8 بیت کنترل هستند)، در سال 1998 شکسته شد. این اولین سیستم رمزگذاری تجاری است که به عنوان یک استاندارد توسط یک نهاد نظارتی ایجاد شد تا از گسترش سیستم های رمزگذاری ناسازگار با یکدیگر جلوگیری شود.

DES یک سری تبدیلات ابتدایی را انجام می دهد که چندین بار بر روی بسته های ساختاری مناسب متن تکرار می شود تا بیت هایی را که آن را تشکیل می دهند تحت یک تغییر کلی قرار دهد که اساساً به کلید انتخاب شده وابسته است: الگوریتم ها عمومی می شوند. کلید - با رعایت دقیق‌ترین اصل کرک‌هوف - تنها داده‌ای است که کاربر تنظیم می‌کند.

جنبه مهم این است که رمزگذاری می تواند در زمان واقعی با یک کامپیوتر با قدرت متوسط ​​انجام شود. علاوه بر این، سیستم متقارن است به این معنا که، مانند همه سیستم‌هایی که تا این لحظه مثال زده شده، از کلید مستقیماً برای رمزگشایی استفاده می‌شود. یک
عدد 56 بیتی حاوی مقدار زیادی اطلاعات است: شما 7، 2 x 10 16 کلید مختلف دارید. با این حال، از اولین ظهور، به نظر محققان برای مقابله با منابعی که به طور قابل پیش بینی در آینده توسعه خواهند یافت، کوتاه تر از آن به نظر می رسید. و همانطور که انتظار می رفت، این دلیل اصلی رمزگشایی آن بود، اگرچه این امر نیازمند قدرت هزاران رایانه بود که به طور همزمان کار می کردند، هماهنگ شده از طریق اینترنت .
در واقع، در زمینه ماشین‌های محاسباتی بزرگی است که به مسائل رمزنگاری اختصاص داده شده است که در دهه 1900 این آگاهی به وجود آمد که برای داشتن یک رمز کامل ، یعنی رمزی که نمی‌توان آن را شکست، کلید باید به این صورت باشد. اطلاعات زیادی به عنوان کلید پیام های ممکن. یک پارادوکس ظاهری، که با این حال، تنها مفهوم کلید رمزنگاری را به جلو می برد. به عنوان مثال رمز Vernam است که به نام مهندس ارتباطات راه دور گیلبرت ورنام (1890-1960) نامگذاری شده است که در آن کلید یک مولد اعداد تصادفی است. تعجب آور نیست که هر کلید را می توان به صورت عددی کدگذاری کرد: واضح است که با این سطح از پیشرفت و شروع روش های دیجیتال، می توان به خوبی فکر کرد که پیام نیز چیزی جز یک عدد نیست که در تعداد معینی کدگذاری شده است. از بیت ها . مشکل واقعی که باقی می ماند مشکل کلید است: تولید، حفاظت و انتقال آن.
به این ترتیب، با هر استفاده جدید، کلید همیشه جدید است. هرگز از انتقالی به انتقال دیگر تکرار نمی‌شود و در واقع، پس از استفاده حذف می‌شود (آمریکایی‌ها از پد یک‌بار مصرف صحبت می‌کنند تا تاکید بر استفاده غیرقابل تکرار از کلید داشته باشند) اما راز واقعی اکنون در راه متمرکز شده است. که تولید می شود.

اولین رمزی که توسط Vernam در سال 1917 طراحی شد شامل دستگاهی است که قادر به اجرای انحصاری یا V، مدت به ترم، سیگنال های دوتایی بر روی دو نوار است. در یک نوار متنی وجود دارد که باید رمزگذاری شود، در دیگری کلید: در نتیجه، در هر موقعیت خروجی ، 1 به دست می آید اگر و فقط اگر دو موقعیت متناظر روی نوارها متفاوت باشند: 0 و 1 یا 1. و 0. ابتکار روش در این واقعیت نهفته است که ناتوانی عملیات "a V -"، که در آن a یک متغیر باینری است:

aV(aVb)=b

برگشت پذیری سیستم را تضمین می کند.
اما برای نشان دادن معنای استفاده از کلید یکبار مصرف لزوماً یک محیط تکنولوژیکی بسیار پیچیده ضروری نیست: برای مثال، به این فکر کنید که با همکار خود ثابت کنید که کلید انتقال پیام های رمزگذاری شده توسط نسخه خاصی از کمدی الهی داده شده است. . شما رمزگذاری à la Vigenère را با استفاده از تمام حروف متوالی کار دانته به عنوان کلید انجام می دهید: " nelmezzodelcammindinostravita...... " با این قرارداد که برای پیام بعدی کلید از جایی شروع می شود که در پیام قبلی متوقف شده است. بدیهی است که سیستم هیچ دوره ای ندارد: رمزگذاری هرگز به همان شکل تکرار نمی شود. اما ماشینی که با آزمون و خطا پیش می رفت، مطمئناً دیر یا زود می تواند پیام های شما را رمزگشایی کند و شاید همه آیات کمدی الهی را بازنویسی کند !
در این مرحله از توسعه، ما به ایده‌ای نیاز داریم که مفهوم کلید رمزنگاری را با امکانات بسیار زیادی ارائه کند و در عین حال آن را از نیاز به اشتراک گذاری بین چندین طرف، حتی بین فرستنده و گیرنده، رها کند. مدیریت کلیدها، که اغلب دست و پا گیر هستند، تولید آنها، ارسال آنها به گیرندگان، نیازهای امنیتی... این نقطه حیاتی واقعی سیستم های رمزگذاری است. و این همان چیزی است که از ایده کلید عمومی ، در مقابل استفاده خصوصی، شخصی و مخفیانه از کلید، پیشرفت زیادی دریافت کرد. کلیدی که می‌توانید با هر کسی که می‌خواهد پیامی را رمزگذاری کند و برای شما ارسال کند، ارتباط برقرار کنید، اما برای رمزگشایی که فقط شما می‌دانید چگونه آن را انجام دهید مفید نیست.

تبادل کلید

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

(n a ) b = (n b ) a = n ab

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

این ایده ای است که در دهه 70 بوجود آمد و سپس در Diffie and Hellman [7] منتشر شد: ارائه یک تابع - معکوس بله، در غیر این صورت رمزگشایی ممکن نیست، اما به یک معنا به راحتی محاسبه می شود و بسیار دشوار است. محاسبه معکوس طولانی یا عملاً غیرممکن است - تابعی که در اصطلاحات آنگلوساکسون در حال حاضر مرسوم است، به آن trapdoor می گویند .

سقوط آسان است، در حالی که صعود به عقب عملاً غیرممکن است (مگر اینکه یک مسیر مخفی بدانید).

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

کلید عمومی

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

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

سیستم RSA

این سیستم، چند سال پس از ایده توابع ترفند ، در Rivest، Shamir و Adleman [8] ظاهر می‌شود و دقیقاً بر اساس دشواری یافتن منابع محاسباتی کافی برای تجزیه به عوامل اول اعداد صحیح است که دارای ارقام متعدد هستند.

الگوریتمی که برای اجرای عملی پیشنهاد شده است، از پیچیدگی محاسباتی برخی از فرآیندهای تئوری اعداد، مربوط به محاسبات مدولار (که در کادر مقابل بحث شده است، که نتایجی را که به الگوریتم اجازه عملکرد می‌دهد، نیز توضیح می‌دهد) بهره‌برداری می‌کند.
شایان توجه است که این نتایج، که همه خلاصه شده و به طور کامل در Disquisitiones Arithmeticae گاوس (1801) بیان شده‌اند، اساساً برای اویلر و در برخی موارد برای فرما در قرن هفدهم شناخته شده بود. به نظر می رسد به کارگیری این نتایج، که در دوره ای یافت می شود که چشم انداز محاسبه سریع حتی از دور قابل تصور نبود، نمونه خارق العاده ای از ثمربخشی تفکر ریاضی و عقلانیتی است که در تحقیق این بزرگان ذاتی است. ارقام ریاضی
بیایید با توضیح ایده پشت سیستم رمزنگاری کلید عمومی شروع کنیم و مشاهده کنیم که برخی از عملیات که ممکن است در نگاه اول در مقایسه با زمان محاسبه بسیار گران به نظر برسند، در عوض به راحتی قابل محاسبه هستند: این مورد، برای مثال، نمایی و بزرگترین مقسوم‌کننده مشترک است. از دو عدد - حتی بسیار بزرگ - و همچنین محاسبه مدول باقیمانده n. جالب است بدانید که این سادگی، علیرغم انواعی که در طول زمان ایجاد شده اند، اساساً توسط یک نتیجه کلاسیک دیگر با اهمیت بسیار ارائه شده است: الگوریتم تقسیمات متوالی یا الگوریتم اقلیدسی که ریشه و منطق آن در عناصر اقلیدس است. و در مسائل مورد بحث در قرن 3 قبل از میلاد (برای مشکلات پیچیدگی محاسباتی در مورد عملیات مختلف می توان به عنوان مثال Salomaa [9] یا Ferragine و Luccio [10] مراجعه کرد).

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

با این حال، در اینجا ارزش پرداختن به این جزئیات را ندارد، بلکه تلاش برای روشن کردن روش در اصول آن است (کسانی که برای دانستن این جزئیات بی تاب هستند باید با Koeblitz [11]، Salomaa [9] یا Ferragine و Luccio [10] مشورت کنند. ).
باب یک جفت از اعداد ( e, n ) را با این شرط انتخاب می کند که e و φ(n) ضریب اول مشترک نداشته باشند:
GCD(e, φ(n)) = 1
گفتیم که این انتخاب حتی در محاسبه مشکل ایجاد نمی کند. اگر دو عدد e و n کاملاً بزرگ باشند و همانطور که مشاهده شد بهترین کار این است که معیارهای مناسب برای افزایش استحکام سیستم رعایت شود. این جفت ( e, n ) کلید عمومی باب است که او آن را در دسترس همه قرار می دهد، اما مراقب باشید... باب هیچ اشاره ای به مقدار φ( n ) - حتی به آلیس - نخواهد کرد، زیرا این راز اوست. ، کلید شخصی او که به او امکان رمزگشایی پیام ها را می دهد.
در واقع، باب با استفاده از φ( n )، عدد d را محاسبه می کند که همخوانی درجه اول را حل می کند:

e*x≡1 (mod φ(n))

این عدد d (mod φ( n )) است که مستقیماً برای رمزگشایی پیام ها استفاده می کند. شرط اول بودن e و φ( n ) برای یکدیگر تضمین می کند که همخوانی قبلی یک راه حل منحصر به فرد را تا مدول همخوانی φ( n ) می پذیرد.
اکنون هر کسی توانایی ارسال یک پیام محرمانه را برای باب دارد و او آماده است تا آن را رمزگشایی کند. این روش به این صورت انجام می شود: برای مثال آلیس می خواهد پیام m را (که قبلاً به طور مناسب با یک عدد کدگذاری شده است) ارسال کند. برای این کار، m را به توان e ببرید و مدول باقیمانده n عدد به دست آمده را محاسبه کنید. او دقیقاً از اطلاعاتی که باب به همه اطلاع داده بود - کلید عمومی خود ( e, n ) - برای دریافت پیام رمزگذاری شده c استفاده کرد :

c≡m e (mod n)

چگونه باب می تواند پیام را بازسازی کند، یعنی از c به m برگردد ، و چرا هیچ کس دیگری که c را رهگیری می کند و کلید عمومی باب را می داند قادر به انجام همین کار نیست؟ برای باب آسان است، زیرا او φ(n) را می داند و d را محاسبه کرده است . او فقط باید پیام رمزگذاری شده c را به توان مخفی d برساند . در واقع، همانطور که پیدا شد، ed = kφ(n)+1 مربوط به مقداری عدد صحیح k است و بنابراین داریم:

c d ≡(m e ) d ≡m ed ≡m kφ(n)+1 ≡(m φ(n) ) k *m ≡m(mod n)

که در آن از ویژگی پایداری رابطه همخوانی با توجه به حاصلضرب و قضیه اویلر-فرمات استفاده کردیم: m φ(n) ≡1 (mod n).
رازی که فقط به باب اجازه می دهد پیام را رمزگشایی کند چیست؟ واضح است که در توان d قرار دارد که از کلید رمزگذاری e استفاده می کند و آن را معکوس می کند (مدول φ(n)) . و d با دانستن φ(n) به دست می آید: همانطور که گفتیم این راز واقعی است زیرا محاسبه φ(n) به اندازه تجزیه n به عوامل پیچیده است. وقتی باب کلید عمومی خود را انتخاب کرد، آینده نگری داشت که n را به عنوان حاصلضرب اعداد اول خاص انتخاب کند و بنابراین، به لطف خاصیت ضربی φ اویلر، محاسبه φ(n) برای او بسیار آسان است. در این فرآیند، ویژگی‌های اساسی حساب مدولار و φ اویلر شناسایی خواهند شد.
استراتژی بهینه باب دقیقاً این است که n را به عنوان حاصل ضرب تنها دو عدد اول، به اندازه کافی بزرگ و نه خیلی نزدیک به یکدیگر انتخاب کند. به این ترتیب n = p*q با p و q اول است و داریم:

φ(n)=(p - 1)*(q - 1)

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

امضای دیجیتال

مشکل اصالت فرستنده اهمیت فزاینده ای پیدا می کند زیرا عملیات های بیشتر و بیشتری با ماهیت و اهمیت مختلف به صورت الکترونیکی انجام می شود. امضای دیجیتال در حال تبدیل شدن به یک ابزار قانونی در بسیاری از کشورها است.
اصل آن چیست؟ در واقع، با «معکوس کردن» اصل انتقال رمزگذاری شده با یک کلید عمومی به دست می آید. بنابراین، بیایید فرض کنیم که باب - همیشه او - می خواهد پیام را منتقل کند، اما این بار، جنبه مهم در رازداری m نهفته است - که همه باید بدانند - بلکه در این است که خود را با قطعیت توسط گیرنده شناسایی کند . این در نهایت عملکردی است که توسط امضای ما انجام می‌شود: فقط ما می‌توانیم آن را انجام دهیم و در نتیجه همه می‌توانند تشخیص دهند که یک سند از طرف ما آمده است.
به عنوان مثال، باب از طریق ایمیل از خارج به بانک خود می نویسد تا مقداری اعتبار را دریافت کند: شناسایی باید ایمن باشد. البته باب کلید عمومی خود را دارد ( e, n ) که همه می‌دانند و به تنهایی توان d را نیز محاسبه کرده است که به او امکان رمزگشایی پیام‌ها را می‌دهد. با مسلح شدن به این داده ها، باب جفت ( m, m d ) را به عنوان پیامی به بانک خود می فرستد و با اطمینان شناسایی می شود زیرا با محاسبه ای مشابه آنچه که انجام شده است، بلافاصله این اتفاق می افتد:

m≡(m d ) e (mod n)

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

قرعه کشی آلیس و باب

آنچه باید مورد بررسی قرار گیرد روشی است که در آن دو مدعی می توانند قرعه کشی را انجام دهند، بدون اینکه امکان ملاقات برای بررسی درستی انجام تمام عملیات ها وجود داشته باشد. این مشکل مستقیماً به رویه‌های رمزنگاری - انتقال و اعتبارسنجی پیام‌های محرمانه - مربوط نمی‌شود، بلکه بر اساس همان اصل کلید عمومی است ، یعنی امکان انجام عملیاتی که معکوس آن برای محاسبه فوری قابل دسترسی نیست، مگر اینکه مقداری وجود داشته باشد. اطلاعات اضافی
در این حالت، آلیس و باب متقابلاً یک تابع ترفند f را انتخاب می کنند. بنابراین، آلیس، برای مثال، مقدار x آرگومان را ثابت می‌کند، f (x) را محاسبه می‌کند و به باب پیشنهاد می‌کند که به طور تصادفی خاصیتی از x را انتخاب کند که احتمال درستی آن 50٪ است: برای مثال، وقتی x یک عدد کامل است، از او می خواهد بگوید زوج است یا فرد. واضح است که برای باب ردیابی از f (x) تا x غیرممکن است: اگر او درست حدس بزند، پیروزی در تساوی متعلق به اوست، در غیر این صورت از آن آلیس است و خود باب می تواند به راحتی خود را در این مورد متقاعد کند. انتخاب تصادفی و منصفانه بود، همانطور که در قرعه کشی لازم بود.
معمولاً حتی برای رویه ای از این نوع جالب ترین توابع از نظریه اعداد گرفته می شود. در اینجا یکی است که از یک ویژگی غیر پیش پا افتاده استفاده می کند: مانند انتخاب کلید عمومی، آلیس دو عدد اول بسیار بزرگ p و q را ثابت می کند و حاصلضرب آنها n=p*q را محاسبه می کند . او ارزش n را به باب می گوید، اما نه فاکتورگیری را که طبق معمول راز اوست. به نوبه خود، باب نیز یک عدد صحیح u را بین 1 و n/2 انتخاب می کند ، u 2 (mod n) را محاسبه می کند و این عدد را به آلیس می رساند. آلیس به راحتی می تواند دو ریشه مربع u 2 را که در بازه (1,n/2) قرار گرفته اند پیدا کند زیرا او فاکتورگیری n را می داند و اگر مقدار u انتخاب شده توسط باب را حدس بزند، برنده قرعه کشی خواهد شد: زیرا این دقیقاً 50٪ شانس برنده شدن دارد. بنابراین آلیس انتخاب خود را به باب اعلام می کند، که تنها در صورتی می تواند موافقت کند که آلیس به درستی حدس زده باشد، زیرا در غیر این صورت از او خواسته می شود که بگوید جذر دیگر u 2 چیست ... اما او قادر به محاسبه آن نیست.

نتیجه گیری

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

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

همانطور که مشاهده می شود، در پوشش مدرن رمزنگاری کلید عمومی، یک زمینه تحقیقاتی با علاقه نظری بزرگ است که مستقیماً با ارزش برنامه ها مرتبط است، در واقع اغلب بلافاصله توسط نیازهای آنها دیکته می شود.
اما شایان ذکر است که منطقه زمانی سیستم های رمزنگاری کاملاً آزاد نیست. به دلایل امنیتی، برنامه‌های رمزگذاری در نظر گرفته شده برای برنامه‌های غیرنظامی تحت کنترل هستند و با برخی پیچش‌های خنده‌دار، با «سلاح‌های جنگی» با هدف ممنوعیت صادرات آن‌ها برابر می‌شوند: این داستان واقعی است که فیل زیمرمن، نویسنده کتاب به آن پرداخته است. نرم افزار PGP ( Pretty Good Privacy ) و مدافع متقاعد شده حق شخصی برای حفظ حریم خصوصی است که برنامه آن را دیگر نمی توان آزادانه از اینترنت دانلود کرد.
و بنابراین، به نوعی، رمزنگاری به اجبار به حوزه مشکلات نظامی، تحت پوشش محرمانه، "پس زده می شود".

https://matematica.unibocconi.eu/articoli/invito-alla-crittografia

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

نویسندگان بخشی از گروه منطق ریاضی گروه ریاضیات و علوم کامپیوتر دانشگاه کامرینو هستند. فعالیت تحقیقاتی آنها عمدتاً به نظریه مدل و کاربردهای آن در جبر مربوط می شود.
کارلو تافالوری با همکاری پاتریزیو سینتیولی متنی در مورد "منطق ریاضی" برای مک گراو هیل (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

الگوریتم تاد – کاکستر

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

در تئوری گروه ، الگوریتم تاد-کوکستر ، که توسط JA Todd و HSM Coxeter در سال 1936 ایجاد شد، الگوریتمی برای حل مسئله شمارش هم مچموعه است . با ارائه یک گروه G توسط مولدها و روابط و یک زیرگروه H از G ، الگوریتم مجموعه‌های H در G را برمی‌شمارد و نمایش جایگشت G را در فضای هم‌زیستی‌ها (که با عمل ضرب چپ به دست می‌آید) توصیف می‌کند. اگر ترتیب یک گروه G نسبتا کوچک باشد و زیرگروه H بدون پیچیدگی شناخته شود (مثلاً یک گروه چرخه ای )، آنگاه الگوریتم را می توان با دست انجام داد و توصیف معقولی از گروه G ارائه می دهد . کاکستر و تاد با استفاده از الگوریتم خود نشان دادند که سیستم های خاصی از روابط بین مولدهای گروه های شناخته شده کامل هستند، یعنی سیستم های تعریف روابط را تشکیل می دهند.

الگوریتم Todd-Coxeter را می توان برای گروه های نامتناهی اعمال کرد و مشخص است که در تعداد محدودی از مراحل به پایان می رسد، مشروط بر اینکه شاخص H در G محدود باشد . از سوی دیگر، برای یک جفت عمومی متشکل از یک ارائه گروهی و یک زیر گروه، زمان اجرای آن با هیچ تابع قابل محاسبه شاخص زیرگروه و اندازه داده های ورودی محدود نمی شود.

توضیحات الگوریتم [ ویرایش ]

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

جدول هم مچموعه برای ذخیره روابط بین هم مچموعه های شناخته شده هنگام ضرب در یک مولد استفاده می شود. دارای ردیف‌هایی است که نشان‌دهنده هم مجموعه هستندو یک ستون برای هر عنصر از". اجازه دهیدعلامت هم مچموعه ردیف i از جدول هم مچموعه، و اجازه دهیدمولد ستون j را نشان می دهد. ورودی جدول هم مچموعه در ردیف i ، ستون j به صورت k (در صورت شناخته شدن) تعریف می شود ، جایی که k به گونه ای است .

جداول رابطه برای تشخیص اینکه برخی از هم مچموعه هایی که پیدا کرده ایم واقعاً معادل هستند استفاده می شود. یک جدول رابطه برای هر رابطه درنگهداری می شود. اجازه دهید1تییک رابطه در، جایی که". جدول رابطه دارای ردیف هایی است که نشان دهنده هم مجموعه هستندمانند جدول هم مچموعه. دارای t ستون است و ورودی در ردیف i و ستون j به صورت k (در صورت شناخته شدن) تعریف می شود ، جایی که. به طور خاص،'امین ورودی در ابتدا من است ، از آنجا که1.

در نهایت، جداول زیر گروه مشابه جداول رابطه هستند، با این تفاوت که آنها روابط احتمالی مولدهای را دنبال می کنند.. برای هر مولداز، با"، یک جدول زیر گروه ایجاد می کنیم. فقط یک ردیف دارد که مربوط به هم مچموعه استخود دارای t ستون است و ورودی در ستون j (در صورت شناخته شدن) به صورت k تعریف می شود ، جایی کهسیک=12⋯.

هنگامی که یک ردیف از یک رابطه یا جدول زیرگروه تکمیل می شود، یک قطعه اطلاعات جدید،"، یافت می شود. این به عنوان کسر شناخته می شود . از کسر، ممکن است بتوانیم ورودی های اضافی جداول رابطه و زیرگروه را پر کنیم، که منجر به کسرهای اضافی احتمالی می شود. می توانیم ورودی های جدول هم مچموعه مربوط به معادلات را پر کنیمو-1.

با این حال، هنگام پر کردن جدول هم مچموعه، ممکن است قبلاً یک ورودی برای معادله داشته باشیم، اما ورودی مقدار متفاوتی داشته باشد. در این مورد، ما کشف کرده‌ایم که دو تا از مجموعه‌های ما در واقع یکسان هستند، که به عنوان تصادف شناخته می‌شود . فرض کنید، با. همه نمونه های j را در جداول با i جایگزین می کنیم . سپس، تمام ورودی‌های ممکن جداول را پر می‌کنیم، که احتمالاً منجر به کسر و تصادفات بیشتر می‌شود.

اگر پس از بررسی همه کسرها و تصادفات، ورودی های خالی در جدول وجود داشت، یک هم مچموعه جدید به جداول اضافه کنید و این روند را تکرار کنید. ما مطمئن می شویم که هنگام اضافه کردن هم مچموعه ها، اگر Hx یک هم مچموعه شناخته شده باشد، Hxg در یک نقطه برای همه اضافه می شود.". (این مورد برای تضمین خاتمه الگوریتم ارائه شده مورد نیاز استمحدود است.)

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

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

• گروه کوکستر

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

• تاد، جی . Coxeter، HSM (1936). "روشی کاربردی برای شمارش مجموعه های یک گروه انتزاعی محدود" . مجموعه مقالات انجمن ریاضی ادینبورگ . سری دوم. 5 : 26-34. doi : 10.1017/S0013091500008221 . JFM 62.1094.02 . Zbl 0015.10103 .
• Coxeter، HSM ; موزر، WOJ (1980). مولدها و روابط برای گروه های گسسته . Ergebnisse der Mathematik und ihrer Grenzgebiete . جلد 14 (ویرایش چهارم). Springer-Verlag 1980. ISBN 3-540-09212-9. MR 0562913 .
• سرس، آکوس (1997). "مقدمه ای بر نظریه گروه محاسباتی" (PDF) . اعلامیه های انجمن ریاضی آمریکا . 44 (6): 671-679. MR 1452069 .

https://en.wikipedia.org/wiki/Todd%E2%80%93Coxeter_algorithm

قانون رستاخیز

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

 

جان کانوی ، مخترع الگوریتم رستاخیز.

حکومت روز قیامت یک IS الگوریتم از تعیین روز هفته برای تاریخ داده شده. این یک تقویم دائمی را فراهم می کند زیرا تقویم گرگوری در چرخه های 400 سال حرکت می کند. الگوریتم محاسبه ذهنی توسط جان کنوی در سال 1973 ابداع شد . [1] [2] با الهام از الگوریتم تقویم دائمی لوئیس کارول طراحی شد . [3] [4] [5] هر سال داشتن یک روز معین از هفته ، به نام روز رستاخیز ، از این مزیت استفاده می کند، که بر روی آن تاریخ های آسان به خاطر سپرده می شوند. به عنوان مثال ، 4/4 ، 6/6 ، 8/8 ،/10/10 ، 12/12 و آخرین روز فوریه همه در همان روز هفته در هر سال اتفاق می افتد. اعمال الگوریتم رستاخیز شامل سه مرحله است: تعیین روز لنگر برای قرن ، محاسبه روز رستاخیز برای سال از روز لنگر ، و انتخاب نزدیکترین تاریخ از آنهایی که همیشه در روز رستاخیز قرار می گیرند ، به عنوان مثال ، 4/4 و 6/6 و تعداد روزها ( ماژول 7 ) بین آن تاریخ و تاریخ مورد نظر را برای رسیدن به روز هفته بشمارید . این روش هم برای تقویم گرگوری و هم برای تقویم ژولیان کاربرد دارد ، گرچه روزهای رستاخیز آنها معمولاً روزهای مختلف هفته است.

این الگوریتم به اندازه کافی ساده است که می توان از لحاظ ذهنی محاسبه کرد. کانوی معمولاً می تواند در کمتر از دو ثانیه جواب صحیح بدهد. برای بهبود سرعت ، او محاسبات تقویم خود را بر روی رایانه خود تمرین کرد ، که برنامه ریزی شده بود که هر بار ورود به سیستم ، وی را با تاریخ های تصادفی مسابقه دهید. [6]

 

فهرست

• 1روز رستاخیز برای سالهای معاصر
• 2تاریخ به یاد ماندنی که همیشه در روز رستاخیز به سر می برند
  • 2.1.مثال
• 3نام روزانه منی
• 4یافتن روز رستاخیز یک سال
  • 4.1چرا کار می کند
  • 4.2روش "عجیب + 11"
• 5مکاتبات با نامه غالب
• 6یافتن روز لنگر یک قرن
• 7نمای کلی از روز رستاخیز
• 8فرمول رایانه برای روز رستاخیز یک سال
• 9چرخه 400 ساله Doomsdays
  • 9.1چرخه 28 ساله
  • 9.2تقویم جولیان
• 10مثال کامل
  • 10.1مثال 1 (1985)
  • 10.2مثال 2 (قرن های دیگر)
• 11همچنین ببینید
• 12مرجع
• 13پیوند خارجی

روزهای رستاخیز برای چند سال معاصر [ ویرایش ]

روز رستاخیز برای سال جاری در تقویم گرگوری (2020) شنبه است. برای چند سال معاصر دیگر:

روزهای رستاخیز برای تقویم گرگوری

دوشنبه	سه شنبه	چهارشنبه	پنجشنبه	جمعه	شنبه	آفتاب.
1898	1899	1900	1901	1902	1903	→
1904	1905	1906	1907	→	1908	1909
1910	1911	→	1912	1913	1914	1915
→	1916	1917	1918	1919	→	1920
1921	1922	1923	→	1924	1925	1926
1927	→	1928	1929	1930	1931	→
1932	1933	1934	1935	→	1936	1937
1938	1939	→	1940	1941	1942	1943
→	1944	1945	1946	1947	→	1948
1949	1950	1951	→	1952	1953	1954
1955	→	1956	1957	1958	1959	→
1960	1961	1962	1963	→	1964	1965
1966	1967	→	1968	1969	1970	1971
→	1972	1973	1974	1975	→	1976
1977	1978	1979	→	1980	1981	1982
1983	→	1984	1985	1986	1987	→
1988	1989	1990	1991	→	1992	1993
1994	1995	→	1996	1997	1998	1999
→	2000	2001	2002	2003	→	2004
2005	2006	2007	→	2008	2009	2010
2011	→	2012	2013	2014	2015	→
2016	2017	2018	2019	→	سال 2020	2021
2022	2023	→	2024	2025	2026	2027
→	2028	2029	2030	2031	→	2032
2033	2034	2035	→	2036	2037	2038
2039	→	2040	2041	2042	2043	→
2044	2045	2046	2047	→	2048	2049
2050	2051	→	2052	2053	2054	2055
→	2056	2057	2058	2059	→	2060
2061	2062	2063	→	2064	2065	2066
2067	→	2068	2069	2070	2071	→
2072	2073	2074	2075	→	2076	2077
2078	2079	→	2080	2081	2082	2083
→	2084	2085	2086	2087	→	2088
2089	2090	2091	→	2092	2093	2094
2095	→	2096	2097	2098	2099	2100

جدول به صورت افقی پر شده است و برای هر سال جهشی یک ستون را پرش می کنید. این جدول هر 28 سال یکبار چرخه می کند ، به جز در تقویم گرگوری در سال هایی که مضرب 100 (مانند سال 1900 که سال جهشی نیست) است و همچنین مضرب 400 نیست (مانند 2000 که هنوز یک سال جهشی است). چرخه کامل در تقویم جورجیان 28 سال (1،461 هفته) ، 400 سال (20.871 هفته) است.

منبع

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

سیگنال

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

دوگان یک کد

دوگان یک کد

یک کد C دارای ماتریس مولد G و ماتریس چک-پاریته H است که در شرط زیر صدق می کنند: GHT = 0.  بنابراین می نویسیم

(H, G(code = C که در آن منظور این است که این کد خطی توسط ماتریس G تولید می شود و توسط ماتریس H چک می شود. حال ا گر طرفین رابطه ۴۶ را ترانهاده کنیم به شرط زیر می رسیم HGT = 0.  این رابطه نشان می دهد که ما می توانیم یک کد دیگر تعریف کنیم که توسط H تولید شده و توسط G چک شود. این کد را دوگان کد ِC می C نشان می دهیم. بنابراین می نویسیم نامیم و آن را با ⊥ C ⊥ = code(H, G). (۴٨)

C تعداد k − n بیت را درn بیت کد می کند.

■ تمرین : نشان دهید که ا گر کد C k بیت را در n بیت کد کند ، در این صورت ⊥ C را برای دوگان یک کد توجیه C بر تمام کلمه های C عمود هستند. این تمرین نمادگذاری ⊥

■ تمرین: نشان دهید که تمام کد-کلمه های ⊥ می کند.

Z قرار می دهیم:

4 2 مثال:

در C = 〈0011, 1100〉 = {0000, 0011, 1100, 1111}

 به آسانی معلوم می شود که

C ⊥ = {0000, 0011, 1100, 1111} = C.  چنین کدی را یک کدِ خود-دوگان می نامیم.

 در

C = 〈0011〉 = {0000, 0011},

 دراین صورت داریم C ⊥ = {0000, 0011, 1100, 1111} ⊃ C.

ادامه نوشته

تمرین با حل

کران برای کلمات

باند گیلبرت

کران بلای همینگ

تمرین

دیکودر

مثال: اصلاح خطا کدال تخمین زده شده

تصحیح خطا جانمایی الگوی خطا

رمز گشایی تصحیح خطا

تست سندرم

سندرم دیکد1

دیکد کدهای همینگ

الگوریتم سندرم دی کد

سندرم دیکد

GOLAY CODES - ساخت

گلی کد

مثال همینگ کد

همینگ کردن کدها و رمزگشایی

همینگ کد خطی

نظارت کلیدی برای محاسبه سندرم

ماتریس برابری کد

چک برابری ماتریس