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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Зміст

1 Означення
2 Формально-множинне означення та наслідки для теорії множин
3 Приклади
- 3.1 Гетерологічні слова/вирази
- 3.2 Автологічні слова/вирази
4 Посилання

[ред.] Означення

Визначимо атрибути "автологічний" (використовують також синонім бларді (en:blardy)) і "гетерологічний" наступним чином:

Слово є автологічним тоді і тільки тоді, коли воно описує самого себе. 
Наприклад, багатоскладовий є автологічним.

Слово є гетерологічним тоді і тільки тоді, коли воно не описує самого себе.  
Наприклад, односкладовий є гетерологічним.

Парадокс полягає в наступному: чи є "гетерологічний" гетерологічним? Запитання не має відповіді: якщо так, тоді воно не є гетерологічним; якщо ні, то воно є.

[ред.] Формально-множинне означення та наслідки для теорії множин

Скористаємось для зручності синонімом бларді для автологічний. Це штучне слово було винайдене саме для демонстрації парадоксу Ґреллінга-Нельсона.

В термінах теорії множин, бларді можна визначити наступним чином: Для властивості $x$ , нехай $S (x)$ це множина слів або фраз $S$ така що всі вони посідають властивість $x$ :

1. S("багатоскладовий") множина всіх багатоскладових слів, тоді 
   S("багатоскладовий")={багато, велосипед,...}.

2. Подібним чином, 
   S("римується із Ківалов")={Кідалов,...}.

Атрибут $x$ є бларді якщо $x \in S(x)$ , та антибларді якщо $x \notin S(x)$

Теорема: Існують слова що не є ні бларді, ані антибларді. Приклад: "бларді".

Доведення від супротивного: Припустимо, "бларді" є бларді. Тоді S(бларді) містить "бларді". Тоді "антибларді" належить S(антибларді), і звідси є по означенню бларді. Отже, "антибларді" є і бларді і антибларді, що є суперечністю.

Тепер припустимо, що "бларді" є антибларді. Тоді "антибларді" не є антибларді, а отже бларді. По означенню, S(антибларді) тоді містить "антибларді", отже "антибларді" є як антибларді так і бларді знову, що є суперечністю.

Дана теорема доводить неможливість розбиття множини на підмножини що містять самі себе та підмножини що не містять самі себе. Дивись також парадокс Рассела.