Парадокс Расселла

Парадокс Расселла
Названо на честь	Бертран Расселл
Автор	Бертран Расселл і Ернст Цермело
Досліджується в	теорія множин і аксіоматична теорія множин
Першовідкривач або винахідник	Бертран Расселл і Ернст Цермело
Дата відкриття (винаходу)	1901
Формула	$R:=\{x\mid x\notin x\}$
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика

Бертран Расселл 1916 року

Парадо́кс Ра́сселла (антиномія Расселла, також парадокс Расселла — Цермело) — відкритий 1901 року Бертраном Расселлом теоретико-множинний парадокс (антиномія), що демонструє суперечливість логічної системи Фреге, яка була ранньою спробою формалізації наївної теорії множин Георга Кантора. Був відкритий раніше, однак не опублікований, Ернстом Цермело.

Неформальною мовою парадокс можна описати так. Умовимось називати множину «звичайною», якщо вона не є своїм власним елементом. Наприклад, множина всіх людей є «звичайною», оскільки сама множина — не людина. Прикладом «незвичайної» множини є множина всіх множин, оскільки вона сама є множиною, а отже й своїм власним елементом (тобто містить саму себе).

Можна розглядати множину, що складається лише з усіх «звичайних» множин, така множина називається расселловою множиною. Парадокс виникає за спроби визначити, чи є ця множина «звичайною» чи ні, тобто, чи містить вона сама себе як елемент. Є два варіанти.

• З одного боку, якщо вона «звичайна», то повинна містити сама себе за елемент, оскільки вона за визначенням складається з усіх «звичайних» множин. Але тоді вона не може бути «звичайною», оскільки «звичайні» множини — це ті, які самі себе не містять.
• Залишається припустити, що ця множина є «незвичайною». Однак, вона не може містити себе за елемент, оскільки за визначенням має складатися лише зі «звичайних» множин. Але, якщо вона не містить себе за елемент, то це «звичайна» множина.

В обох випадках — суперечність.

Формулювання

Парадокс Расселла формалізується в наївній теорії множин. Як наслідок, наївна теорія множин є суперечливою. Більше того, суперечливим є фрагмент наївної теорії множин, який можна визначити як теорію першого порядку з бінарним відношенням належності $\in ,$ і схемою виділення: для кожної логічної формули $P(x)$ з однією вільною змінною в наївній теорії множин є аксіома

$\exists y\forall x(x\in y\iff P(x))$.

Ця аксіома стверджує, що для кожної умови $P(x)$ існує множина $y,$ що складається з тих $x,$ які задовольняють умові $P(x)$.

Цього цілком достатньо, щоби сформулювати парадокс Расселла таким чином. Нехай $P(x)$ є формулою $x\notin x.$ (Тобто $P(x)$ означає, що множина $x$ не містить себе за елемент, або, нашою термінологією, є «звичайною» множиною.) Тоді, за аксіомою виділення, знаходиться множина $y$ (расселлова множина) така, що

$\forall x(x\in y\iff x\notin x)$.

Оскільки це справджується для будь-якого $x,$ то справджується і для $x=y.$ Тобто

$y\in y\iff y\notin y.$

Із цього випливає, що в наївній теорії множин виводиться суперечність.

Парадокс би не виник, якщо припустити, що расселлової множини не існує. Однак саме таке припущення є парадоксальним: у канторовій теорії множин вважається, що будь-яка властивість визначає множину елементів, що задовольняють цій властивості. Оскільки властивість множини бути «звичайною» виглядає коректно визначеною, то має існувати множина всіх «звичайних» множин. Зараз така теорія називається наївною теорією множин.

Варіанти

Є декілька видозмін парадоксу Расселла. На відміну від самого парадоксу, вони, здебільшого, не виражаються формальною мовою.

Парадокс брехуна

Парадокс Расселла пов'язаний із відомим ще з античних часів парадоксом брехуна. Парадокс можна сформулювати так: хтось стверджує: 

 — Це висловлювання хибне.

Чи є це висловлювання істинним, чи є хибним?

Якщо спробувати визначити, чи є висловлювання істинним, чи хибним, ми неминуче дійдемо до суперечності. Це твердження не може бути ні тим, ні іншим.

Расселл про цей парадокс писав:

Це давня загадка, і ніхто не ставився до неї серйозніше, ніж до жарту, допоки не виявилось, що вона стосується таких важливих і практичних питань, як існування найбільшого кардинального та порядкового чисел. Оригінальний текст (англ.) It is an ancient puzzle, and nobody treated that sort of thing as anything but a joke until it was found that it had to do with such important and practical problems as whether there is a greatest cardinal or ordinal number.

Сам Расселл так пояснював парадокс брехуна. Щоб стверджувати що-небудь про висловлювання, слід спочатку визначити саме поняття «висловлювання», при цьому не використовуючи невизначені досі поняття. Таким чином, можна визначити висловлювання першого типу, які нічого не говорять про висловлювання. Потім можна визначити висловлювання другого типу, які говорять про висловлювання першого типу, і так далі. Висловлювання ж «це висловлювання хибне» не підпадає ні під одне з цих визначень, і таким чином не має сенсу.

Парадокс цирульника

Расселл згадує такий варіант парадоксу, сформульований у формі загадки, яку йому хтось загадав:

Нехай у якомусь селі живе цирульник, який голить усіх тих і лише тих жителів села, хто не голиться сам. Чи голить цирульник сам себе?

Із будь-якої відповіді випливає суперечність. Бертран Расселл зазначає, що цей парадокс не еквівалентний його парадоксу й легко вирішується. Насправді, як парадокс Расселла показує, що не існує расселлової множини, парадокс цирульника показує, що такого цирульника просто не існує. Різниця полягає в тому, що в неіснуванні такого цирульника нічого дивного немає: не для всякої властивості можна знайти цирульника, який голить людей, що мають таку властивість. Однак те, що не існує множини елементів, заданих певною цілком визначеною властивістю, суперечить наївній уяві про множини й потребує пояснення.

Варіант з каталогами

Найближчим за формулюванням до парадоксу Расселла є такий варіант викладу:

Бібліографічні каталоги — це книги, що описують інші книги. Деякі каталоги можуть описувати інші каталоги. Деякі каталоги можуть навіть описувати самі себе. Чи можна укласти каталог усіх каталогів, що не описують самі себе?

Парадокс виникає за спроби визначити, чи повинен цей каталог описувати сам себе. Незважаючи на ніби-то очевидну схожість формулювань (це фактично парадокс Расселла, в якому замість множин використовуються каталоги), цей парадокс, як і парадокс цирульника, розв'язується легко: такий каталог неможливо укласти.

Парадокс Ґреллінґа — Нельсона

Цей парадокс 1908 року сформулювали німецькі математики Курт Ґреллінґ і Леонард Нельсон. Він фактично є перекладом первісного варіанту парадоксу Расселла, поданого ним у термінах логіки предикатів , нематематичною мовою.

Називатимемо прикметник рефлексивним, якщо цей прикметник має ту властивість, яку визначає. Наприклад, прикметники «український», «багатоскладовий» — мають властивості, які вони визначають (прикметник «український» є українським, а прикметник «багатоскладовий» є багатоскладовим), тому вони є рефлексивними, у той же час прикметники «німецький», «односкладовий» — є нерефлексивними. Чи є прикметник «нерефлексивний» рефлексивним, чи ні?

Із будь-якої відповіді випливає суперечність. На відміну від парадоксу цирульника, розв'язання цього парадоксу не є таким простим. Не можна просто сказати, що такого прикметника «нерефлексивний» не існує, оскільки ми його тільки-що визначили. Парадокс виникає через те, що визначення терміна «нерефлексивний» некоректне саме по собі. Визначення цього терміна залежить від значення прикметника, до якого воно застосовується. А оскільки слово «нерефлексивний» саме є прикметником у визначенні, то виникає хибне коло.

Історія

Імовірно, що Расселл відкрив свій парадокс у травні або червні 1901 року. Згідно з Расселлом, він намагався віднайти помилку в доказах Кантора того парадоксального факту (відомого як парадокс Кантора), що не існує максимального кардинального числа (або ж множини всіх множин). Як наслідок, Расселл одержав набагато простіший парадокс. Він повідомив про свій парадокс іншим логікам, зокрема Вайтгеду та Пеано. У своєму листі до Фреге 16 червня 1902 року він писав, що виявив суперечність у «Беґриффсшрифті» — книзі Фреге, опублікованій 1879 року. Він виклав свій парадокс термінами логіки, а, відтак, термінами теорії множин, використовуючи визначення Фреге для функції:

У мене були труднощі не лише в одному місці. Ви стверджуєте (ст. 17), що функція сама може поставати як невідоме. Раніше й я так вважав. Однак зараз цей погляд мені видається сумнівним через таку суперечність. Нехай w предикат: «бути предикатом, який не застосовується до себе самого». Чи може w застосовуватись до себе самого? З будь-якої відповіді випливає протилежне. Відповідно, ми маємо зробити висновок, що w — не предикат. Аналогічно не існує класу (як цілого) тих класів, які, взяті за ціле, не належать собі. Тому я роблю висновок, що інколи певна множина не формує цілісного утвору.

Оригінальний текст (нім.)

Nur in einem Punkte ist mir eine Schwierigkeit begegnet. Sie behaupten (S. 17) es könne auch die Funktion das unbestimmte Element bilden. Dies habe ich früher geglaubt, jedoch jetzt scheint mir diese Ansicht zweifelhaft, wegen des folgenden Widerspruchs: Sei w das Prädicat, ein Prädicat zu sein welches von sich selbst nicht prädicirt werden kann. Kann man w von sich selbst prädiciren? Aus jeder Antwort folgt das Gegentheil. Deshalb muss man schließen dass w kein Prädicat ist. Ebenso giebt es keine Klasse (als Ganzes) derjenigen Klassen die als Ganze sich selber nicht angehören. Daraus schliesse ich dass unter gewissen Umständen eine definierbare Menge kein Ganzes bildet.

Фреге одержав лист саме в той час, коли завершив роботу над другим томом «Основних законів арифметики» (нім. Grundgesetze der Arithmetik). У Фреге не залишалось часу виправити свою теорію множин. Він лише зробив додаток до другого тому з викладенням і своїм аналізом парадоксу, який починався із знаменитої зауваги:

Навряд чи зі вченим може статись що-небудь гірше, ніж, коли в нього заберуть підґрунтя саме в той час, коли він завершить свою працю. Саме в такій ситуації опинився я, одержавши лист від Бертрана Расселла, коли моя праця вже була завершена.

Оригінальний текст (нім.)

Einem wissenschaftlichen Schriftsteller kann kaum etwas Unerwünschteres begegnen, als daß ihm nach Vollendung einer Arbeit eine der Grundlagen seines Baues erschüttert wird. In diese Lage wurde ich durch einen Brief des Herrn Bertrand Russell versetzt, als der Druck dieses Bandes sich seinem Ende näherte.

Далі Фреге запропонував спосіб виправлення своєї теорії, аби уникнути парадоксу Расселла. Замість аксіоми:

$z\in \{x\colon P(x)\}\iff P(z)$,

яка стверджувала, що можна побудувати множину $\{x\colon P(x)\}$ елементів, що задовольняють властивості $P(x),$ він запропонував використовувати таку аксіому:

$z\in \{x\colon P(x)\}\iff P(z)\ \&\ z\neq \{x\colon P(x)\}$,

водночас виключивши можливість для множини бути елементом себе самої. Однак невелика модифікація парадоксу Расселла доводить, що й ця аксіома призводить до суперечності.

Расселл опублікував свій парадокс у власній книзі «Принципи математики» 1903 року.

Ернст Цермело стверджував, що відкрив цей парадокс незалежно від Расселла та повідомив про нього 1903 року Гільберту й іншим. Це підтвердив і Гільберт, написавши до Фреге 7 листопада 1903 року, що він знав про цей парадокс. Гільберт писав: «я думаю Цермело знайшов його років 3—4 тому… Я зустрів й інші, переконливіші суперечності ще 4—5 років тому». Окрім цього, 1978 року серед паперів Едмунда Гуссерля було віднайдено формулювання цього парадоксу, яке Цермело повідомив Гуссерлю 16 квітня 1902 року. У цьому формулюванні доводиться, що множина М, яка містить усі свої підмножини за елементи, призводить до суперечності. Для доведення розглядається множина М, що складається з множин, які не містять самі себе.

Варіанти розв'язання

У парадоксі Расселла нема помилки: він справді доводить суперечність наївної теорії множин. Щоби позбавитись суперечності, потрібно виправити теорію множин так, щоб вона не дозволяла расселлової множини. Це можна зробити декількома способами. Найприроднішим шляхом є заборона тим чи іншими способом множин, які можуть містити себе за елемент. Таким чином буде заборонено і множину всіх множин (як мінімум, сукупність усіх множин не буде сама вважатись множиною). Однак необхідно розуміти, що з одного боку, лише самої заборони множині мати себе за елемент не достатньо, аби позбавитись суперечності (як показала перша спроба Фреге виправити свою систему). З іншого боку, сам собою дозвіл множинам мати себе за елемент, не зумовлює суперечностей. Наприклад, нічого не заважає укласти каталог, який буде містити всі каталоги, водночас описуючи й себе. Низка мов програмування дають змогу контейнерам містити себе за елемент. Існують логічні системи, позбавлені парадоксів типу расселлових, які дають змогу множинам містити самих себе (наприклад, New Foundations Віларда Ван Ормана Квайна).

Нижче наведено кілька з можливих підходів до побудови системи аксіом, позбавленої расселлових парадоксів.

Теорія типів Расселла

Першим, хто запропонував позбавлену від парадоксу Расселла теорію, був сам Расселл. Він розробив теорію типів, перша версія якої з'явилась у книзі Расселла «Принципи математики» 1903 року. В основі цієї теорії полягає така ідея: прості об'єкти в цій теорії мають тип 0, множини простих об'єктів мають тип 1, множини множин простих об'єктів мають тип 2 і так далі. Таким чином жодна множина не може містити себе за елемент. Ні множина всіх множин, ні расселлова множина не можуть бути визначені в цій теорії. Аналогічна ієрархія вводиться для висловлень і властивостей. Висловлення щодо простих об'єктів належать до типу 1, висловлення щодо властивостей висловлень типу 1 належать до типу 2 і так далі. Загалом, функція за визначенням належить до типу вищого, ніж змінні, від яких вона залежить. Такий підхід дає змогу позбавитись не лише від парадоксу Расселла, але і від багатьох інших парадоксів, як-от парадоксу брехуна, парадоксу Ґреллінґа — Нельсона, парадоксу Буралі-Форті. Расселл і Вайтгед показали, як звести до аксіом теорії типів усю математику, у своїй обсяжній тритомній праці «Principia Mathematica», виданій у 1910—1913 роках.

Однак такий підхід спіткали труднощі. Зокрема, виникають проблеми за визначення таких понять, як точна верхня границя для множини дійсних чисел. За визначенням точна верхня границя є найменшою серед усіх верхніх границь. Відповідно, визначаючи точну верхню границю, використовують множину дійсних чисел. Це означає, що точна верхня границя є об'єктом вищого типу, ніж дійсні числа. А значить, сама не є дійсним числом. Аби уникнути цього, довелось вводити так звану аксіому звідності. Через її довільність аксіому звідності відмовлялись підтримувати багато математиків, та й сам Расселл називав її дефектом своєї теорії. Окрім цього, теорія виявилось дуже складною. Як наслідок, вона не мала широкого застосування.

Теорія множин Цермело — Френкеля

Найвідомішим підходом до аксіоматизації математики є теорія множин Цермело — Френкеля (ZF), яка виникла як розширення теорії Цермело (1908). На відміну від Расселла Цермело зберіг логічні принципи, а змінив лише аксіоми теорії множин. Ідея цього підходу полягає в тому, що дозволяється використовувати лише множини, побудовані з уже побудованих множин за допомогою визначеного набору аксіом. Так, наприклад, одна з аксіом Цермело стверджує, що можна побудувати множину всіх підмножин певної множини (аксіома булеана). Інша аксіома (схема виділення) стверджує, що з кожної множини можна виділити підмножину елементів, що наділені вказаною властивістю. У цьому полягає головна відмінність теорії множин Цермело від наївної теорії множин: у наївній теорії множин можна розглядати множину всіх елементів, що наділені вказаною властивістю, а в теорії множин Цермело — лише можна виділити підмножину з уже побудованої множини. У теорії множин Цермело не можна побудувати множину всіх множин. Таким чином, і расселлову множину в ній побудувати не можна.

Класи

Іноді в математиці буває корисно розглядати всі множини за одне ціле, наприклад, аби розглядати сукупність усіх груп. Для цього теорію множин потрібно розширити поняттям класу, як, наприклад, у системі Неймана — Бернайса — Ґеделя (NBG). У цій теорії сукупність усіх множин є класом. Так, наприклад, можна розглядати клас усіх груп. Водночас сам клас не є множиною і не є елементом інших класів, що дає змогу уникнути парадоксу Расселла.

Сильнішою системою, що дає змогу брати квантори за класами, а не лише за множинами, є, наприклад, теорія множин Морса — Келлі (MK). У цій теорії основним є поняття класу, а не множини. Множинами в цій теорії вважають такі класи, які самі є елементами певних класів. У цій теорії формула $z\in \{x\colon P(x)\}$ вважається еквівалентною формулі

$P(z)\ \&\ \exists y.z\in y$.

Позаяк $\exists y.z\in y$ в цій теорії означає, що клас $z$ є множиною, цю формулу потрібно розуміти як те, що $\{x\colon P(x)\}$ є класом всіх множин (а не класів) $z$, таких що $P(z)$. Парадокс Расселла в цій теорії розв'язується тим, що не будь-який клас є множиною.

Можна піти далі і розглядати сукупності класів — конгломерати, сукупність конгломератів, і так далі.

Вплив на математику

Аксіоматизація математики

Парадокс Расселла разом з іншими математичними антиноміями, відкритими на початку XX століття, стимулював перегляд засад математики, наслідком якого стала побудова аксіоматичних теорій для обґрунтування математики, деякі з яких розглянуто вище.

У всіх побудованих нових аксіоматичних теоріях парадокси, відомі до середини XX століття (зокрема парадокс Расселла), було усунено. Однак довести, що не буде виявлено нових подібних парадоксів у майбутньому (у цьому полягає проблема суперечності побудованих аксіоматичних теорій), виявилось, у сучасному розумінні цієї задачі, неможливо. (див. Теореми Геделя про неповноту).

Інтуїціонізм

Паралельно виник новий рух у математиці, що називається інтуїціонізмом, засновником якого був Лейтзен Егберт Ян Брауер. Інтуїціонізм виник незалежно від парадоксу Расселла й інших антиномій. Однак, відкриття антиномій у теорії множин посилило недовіру інтуїціоністів до логічних принципів і пришвидшило формування інтуїціонізму. Основний тезис інтуїціонізму твердить, що для доведення існування певного об'єкту необхідно надати спосіб його побудови. Інтуїціоністи відкидають такі абстрактні поняття, як множину всіх множин. Інтуїціонізм заперечує закон виключеного третього, втім, необхідно зауважити, що закон виключеного третього не потрібний для виведення суперечності з антиномії Расселла чи будь-якої іншої (в будь-якій антиномії доводиться, що $A$ спричиняє заперечення $A$ і заперечення $A$ спричиняє $A,$ однак із $(A\Rightarrow \neg A)\&(\neg A\Rightarrow A)$ навіть в інтуїціоністичній логіці виникає суперечність). Варто також зауважити, що в пізніших аксіоматизаціях математики було виявлено парадокси, аналогічні расселловому, як-от, наприклад, парадокс Жирара в первісному формулюванні інтуїціоністичної теорії типів Мартіна-Льофа.

Діагональний аргумент (самозастосовуваність)

Попри те, що міркування Расселла призводить до парадоксу, основна ідея цього міркування часто застосовується в доведенні математичних теорем. Як було згадано вище, Расселл одержав свій парадокс, аналізуючи доказ Кантора щодо неіснування найбільшого кардинального числа. Цей факт суперечить існування множини всіх множин, позаяк її потужність має бути максимальною. Тим не менш, за теоремою Кантора, множина всіх підмножин певної множини має більшу потужність, ніж сама множина. Доказ цього факту обґрунтовується діагональним аргументом:

Нехай існує взаємно однозначна відповідність, яка кожному елементу $x$ множини $X$ ставить у відповідність підмножину $s_{x}$ множини $X.$ Нехай $d$ буде множиною, що складається з елементів $x,$ таких, що $x\in s_{x}$ (діагональна множина). Тоді доповнення цієї множини $s={\overline {d}}$ не може бути ні одним з $s_{x}.$ А, значить, відповідність не була взаємно однозначною.

Кантор застосовував діагональний аргумент, доводячи незлічимість дійсних чисел 1891 року. (Це не перший його доказ незлічимості дійсних чисел, однак найпростіший із них).

Парадокс Кантора виникає, якщо застосувати цей аргумент до множини всіх множин. Фактично, расселлова множина є діагональною множиною Кантора $s$. Діагональний аргумент використовували ще до Рассела та Кантора (його в своїй роботі з математичного аналізу 1875 року використовував Дюбуа-Реймон). Однак, у парадоксі Расселла діагональний аргумент викристалізувано найчіткіше.

Діагональний аргумент використовувався в багатьох галузях математики. Так, наприклад, він є центральним аргументом у теоремі Геделя про неповноту, в доведенні існування перераховної множини та, зокрема, в доведенні нерозв'язності проблеми зупинки.

Пов'язані парадокси

Авторефлексія застосовується в багатьох парадоксах, окрім розглянутих раніше:

• Парадокс всемогутності — середньовічне запитання: «Чи може всемогутній бог створити камінь, який він сам не зможе підняти?»
• Парадокс Буралі-Форті (1897) — аналог парадоксу Кантора для порядкових чисел.
• Парадокс Міріманова (1917) — узагальнення парадоксу Буралі-Форті для класу всіх фундованих класів.
• Парадокс Рішара (1905) — семантичний парадокс, що висвітлює важливість розділення мови математики та метаматематики.
• Парадокс Беррі (1906) — опублікований Расселом спрощений варіант парадоксу Рішара.
• Парадокс Кліні—Россера — формулювання парадоксу Рішара термінами λ-числення.
• Парадокс Каррі (1941) — спрощення парадоксу Кліні — Россера.
• Парадокс Жирара (1972) — формулювання парадоксу Буралі-Форті термінами інтуїціоністичної теорії типів.
• Парадокс цікавих чисел — напівжартівливий парадокс, що нагадує парадокс Беррі.

Див. також

• Непредикативність (математика)

Джерела

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Курант Р., Роббінс Г. Що таке математика?. — 3-є. — Москва : МЦНМО, 2001. — 568 с.(рос.)
• Goldrei D.C. Classic Set Theory: A Guided Independent Study. — Chapman & Hall Mathematics, 1996. (англ.)
• Foreman M., Kanamori A. Handbook of Set Theory. — Springer, 2010. (англ.)