Парадокс Ришара

21.3. Действительно, теория множеств Кантора привела к ряду парадоксов и глубоких вопросов, нерешенных и по сей день. Рассмотрим, например, задачу определения всех действительных чисел. Очевидно, что если дан любой конечный «алфавит» знаков, содержащий буквы, цифры, знаки препинания и пробелы, то можно перечислить в бесконечной последовательности все мыслимые словесные определения: существует только конечное множество определений длины п.

С другой стороны, как мы уже говорили, Кантор показал, что действительные числа нельзя расположить в последовательность. Следовательно, лишь небольшая часть действительных чисел допускает определение словами: язык, пригодный для печатания на пишущей машинке, недостаточен для того, чтобы охарактеризовать каждое число (каждую точку континуума) индивидуально. Этот весьма неприятный факт именуется парадоксом Ришара. Логики посвятили немало усилий описанию (счетного) множества WczR всех действительных чисел, (рекурсивно) определимых через конечные выражения. Так как существует биекция b:R—832Р действительных чисел х на подмножества SczP множества Р всех положительных целых чисел *, то существует и соответствующее множество b(W) определимых множеств положительных целых чисел. Аналогичным способом задаются «определимые» подмножества любого счетного множества (например, Z или Q). Можно определить также множество всех определимых функций f: U—>V из любого счетного множества в любое другое счетное множество, потому что существует биекция р: R—+РР. На фоне этих определений легко формулируется вывод Тьюринга (называемый часто тезисом Черча): каждое определимое действительное число вычислимо на машине Тьюринга и обратно. Определимость и вычислимость тем самым эквивалентны.

<< | >>

↑

Источник: Биркгофф Г.. Математика и психология. 1977

Еще по теме Парадокс Ришара: