Lex Kravetski (lex_kravetski) wrote,
Lex Kravetski
lex_kravetski

Categories:

Контр-Канторовский процесс

Предположим, что возможно написание функции, которая генерирует «Канторовское число» на базе любого списка — как конечного, так и бесконечного.

Смысл генерации такого числа — исключить нахождение оного в каждой строке предоставленного списка.

При этом вариантов больше одного.

Несмотря на то, что в варианте Кантора у каждого числа цифра после десятичной точки, соответствующая порядковому номеру этого числа в списке, менялась на какую-то другую, можно менять, например, цифру, соответствующую порядковому номеру, умноженному на два.

Выберем какую-то одну из них — например, «классическую», и назовём её kantor1(list).

Теперь сделаем генератор бесконечного списка следующим образом: он будет стартовать с произвольного числа, а для генерации каждого следующего вызвать kantor1(cachedList). Где cachedList — запомненные им уже сгенерированные к данной итерации элементы.

Реализация такого списка на языке программирования довольно банальна: метод next у него просто определён как

class ContraKantor(start: BigDecimal) extends Iterator[BigDecimal] {
 val cachedList = ListBuffer[BigDecimal]()
 cachedList.append(start)
  
 var preparedNext = start
 
 def hasNext = true

 def next(): BigDecimal = {
  val res = preparedNext
  preparedNext = kantor1(cachedList.iterator)
  cachedList.append(preparedNext)
  res
 }
}


То есть сомнений в том, что при наличии функции kantor1 такое можно реализовать, быть не может.

Теперь смотрите, что получается.

Для генерации каждой следующей цифры, которая исключит нахождение данного частично сгенерированного Канторовского числа на i-й позиции, kantor1 с неизбежностью должна будет вызвать list.next() минимум i раз — иного способа узнать число на этой позиции у неё нет.

Однако это приведёт к тому, что генератор списка ContraKantor для i + 1 элемента «заготовит» ровно то самое число, которое к данному моменту уже успела сформировать функция kantor1.

Вообще говоря, нам тут без разницы, как именно kantor1 строит это число: что бы она уже ни построила к какому-то шагу, на следующем шаге в «бесконечном списке», для которого она генерирует число, будет лежать ровно вот это самое.

Если мы предполагаем, что генерация цифр на базе элементов списка «после бесконечного числа шагов» действительно сгенерирует число, которого нет в списке, мы одновременно с тем будем вынуждены предполагать, что в списке есть это число — ведь каждая промежуточная итерация генерации оного числа действительно отсутствовала среди первых i элементов, но при этом совершенно точно присутствовала на i+1 позиции.

Из этих двух вариантов один объявить «действующим в бесконечном пределе», а другой — «не действующим в бесконечном пределе», можно только в результате произвола. С логической точки зрения они совершенно равноправны: если из выполнения некоторой закономерности на каждом шаге следует, что она выполняется в «бесконечном пределе», то в нём должны выполняться они обе. То есть одновременно должно получиться отсутствующее в данном списке число, и до конца сгенерироваться этот же самый список, в котором это число есть.

Тут, заметьте, не утверждается, что в получившемся списке будут все вещественные числа. О нет, вместо этого тут показывается список, на котором Канторовская генерация приведёт к логическому противоречию.

Такой список, возможно, содержит не все вещественные числа, однако даже для списка с не всеми ими kantor1 не может создать такое число, которого в этом списке не будет «в финале».

При этом мы-то без проблем можем добавить в этот список все числа: просто будем «загадывать» на две позиции вперёд и на одну класть то число, которого нам не хватает, а на вторую — то самое, что к этому моменту успеет сгенерировать kantor1.

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

Тут может показаться, что чит-код состоит в том, что список как бы генерируется по мере построения числа функцией kantor1. Типа «так не честно — вы специально на ходу генерируете то, что сейчас уже известно kantor1».

Однако нет. Правда, что специально генерируем — так и задумано, но неправда, что «так не честно». Бесконечный список мы в любом случае можем завести только в виде генератора, но в процессе своей генерации он никак не использует тот экземпляр kantor1, который запустился со ссылкой на этот генератор в качестве параметра. Вместо этого он запускает новые экземпляры kantor1, причём передаёт в них не ссылку на себя, а итератор своего кэша.

То есть он никак не мешает работе «главного» экземпляра kantor1. Более того, он мог бы даже не ждать запроса следующего элемента из главного экземпляра, а нагенерировать кэш из стопицот элементов прямо на старте — ему всего лишь достаточно иметь доступ к функции kantor1. Или даже просто «знать» алгоритм работы оной и моделировать точно то же самое внутри себя.

В общем, в качестве чита тут используется иное: ровно то самое, что используется в качестве чита доказательством Кантора, основанным на смелом предположении о том, что «будет» в конце прохода по всему бесконечному списку.

Само это предположение уже противоречиво, поскольку, безотносительно возможности пронумеровать вещественные числа, оно приводит к тому, что оказывается «возможно» построить список, который одновременно содержит и не содержит некоторое «число».

Иными словами, в доказательстве Кантора утверждается, что такое число будет построено для абсолютно любого списка и в случае с конечными списками это было бы даже верно, однако избранный Кантором и теорией множеств способ экстраполяции закономерностей на бесконечные списки даёт возможность предъявить такой список (а точнее, такое множество списков), который оказывается исключён из числа «любых».

При этом, заметьте, при восприятии бесконечного генератора именно как бесконечного генератора — без предположений о том, что будет в конце его работы — логических противоречий не нарушает: действительно, сколько бы итераций мы ни проделали, всегда будет сгенерировано число, которого не было среди предыдущих итераций, но которое будет на следующей. Пока мы воспринимаем это как процесс — всё отлично.

Однако в таком восприятии, естественно, оказывается невозможным Канторовское доказательство и все ему подобные.



doc-файл

Tags: наука, философия
Subscribe

  • Информация о списке внутри списка

    Интересно, что не только мне в комментах русскоязычные типа знатоки математики такое писали, но и в англоязычном сегменте интернета люди друг другу…

  • Чисто для пафоса

    Вы знаете, в математике всё точно и строго — там не любят дешёвых сенсаций. Ну, в теории. Поскольку на практике у меня складывается впечатление,…

  • Чем современные дети

    Хотелось бы прокомментировать статью «Чем современные дети отличаются от школьников 1980-х: 10 пунктов учителя истории», заодно объяснив, почему «не…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 22 comments

  • Информация о списке внутри списка

    Интересно, что не только мне в комментах русскоязычные типа знатоки математики такое писали, но и в англоязычном сегменте интернета люди друг другу…

  • Чисто для пафоса

    Вы знаете, в математике всё точно и строго — там не любят дешёвых сенсаций. Ну, в теории. Поскольку на практике у меня складывается впечатление,…

  • Чем современные дети

    Хотелось бы прокомментировать статью «Чем современные дети отличаются от школьников 1980-х: 10 пунктов учителя истории», заодно объяснив, почему «не…