Парадокс Берри (Hgjg;ktv >yjjn)

Парадокс Берри — парадокс самореференции, заключённый во фразе «наименьшее натуральное число, которое нельзя описать менее чем заданным количеством слов» (англ. «the smallest possible integer not definable by a given number of words»). Впервые парадокс опубликовал Бертран Расселл, приписав его авторство Дж. Дж. Берри (1867—1928), младшему библиотекарю Бодлианской библиотеки в Оксфорде. Считается, что Берри нашёл лишь частный случай парадокса — «первое неопределяемое порядковое» (англ. the first undefinable ordinal).

Парадокс

Рассмотрим выражение:

«Наименьшее натуральное число, которое нельзя описать менее чем одиннадцатью словами»

Поскольку слов конечное число, существует конечное множество фраз из менее чем одиннадцати слов, и, следовательно, конечное подмножество натуральных чисел, определяемых фразой из одиннадцати слов. Однако множество натуральных чисел бесконечно, следовательно, существуют числа, которые нельзя определить фразой из менее чем одиннадцати слов. Среди них, очевидно, существует наименьшее натуральное число (наименьшее число можно выбрать из любого подмножества натуральных чисел), «не описываемое менее чем одиннадцатью словами». Но именно это число определяется приведённой выше фразой и в ней менее одиннадцати слов, а значит, не может являться искомым наименьшим числом и не может описываться данной фразой. Возникает парадокс: должно существовать число, описываемое данной фразой, но поскольку выражение само себе противоречит, не может существовать числа, им описываемого.

См. также

• Колмогоровская сложность