Строимые бесконечные последовательности в доказательствах

[manul91]

Под "бесконечной последовательности" пусть для конкретности понимаем детерминированную двоичную последовательность типа 101101000...... у которой каждому натурального n (номеру "разряда"), сопоставлена вполне определенная цифра 0 или 1; для краткости далее буду обозначать такие последовательности как $I$.

Допустим где-то встречается фраза "построим бесконечную последовательность $I$..."
Такое "построение", в принципе можно понимать как:
a) мы бесконечно выписываем соответные цифры (этот процесс никогда не закончится, не задумываемся конечные или бесконечные ресурсы при этом нам понадобятся; можно считать что разряды нам выдает оракул и т.д.)
б) можно попытаться обойтись финитным описанием данной бесконечности (типа "для каждого", "существует" и т.д. наподобие известного доказательства бесконечности простых чисел "не используя слова бесконечность" - где мы доказывем, что "для любого конечного n, найдется простое p>n"; или как Коши определил пределы/бесконечно малые не используя бесконечности а только "для любого", "найдется" и т.д.)

Пример "построения $I$ не используя бесконечность":
Буду говорить что "последовательность $I$ построена(построима)" если задан(существует) финитный (разумеется детерминированный) алгоритм $A_I$, который по заданному на входе любого конечного натурального числа n, за конечное время выдает либо 0 либо 1; этот выход мы трактуем как n-ую цифру $I_n$ данной бесконечной последовательности: $A_I(n) \rightarrow I_n$
В этом смысле, хотя мы и не можем выписать "всю $I$ целиком" конечным способом, она "финитно задана" постольку, поскольку располагая конечным алгоритмом, за конечное время мы однозначно можем вычислить любой ее разряд n, чем она и однозначно определяется.

Думаю, это совпадает с тем что вроде называют "конструктивными" последовательностями; как бы оно не было; любое финитное описание $I$ (например возможность с любыми, но конечными ресурсами выдать любой желаемый n-тый разряд последовательности; или что-то что ее однозначно определяет) в этом смысле было бы "удовлетворительным".

С другой стороны как известно, множество конечных алгоритмов счетно; в то же время как множество последовательностей $I$ имеет мощность континуума.
Т.е. как бы "заведомо существуют", "непостроимые" последовательности $I$ , т.е. такие которые нельзя описать финитным способом (по меньшей мере, конечным алгоритмичеспособом указанном выше).

Теперь собственно вопрос...

Допустим в доказательстве, используется "построение последовательности $I$ "; при этом $I$ "непостроима" (либо не доказано, что "построима") - т.е. возможно $I$ на которой опирается доказательство, принадлежит множеству "неконструктивных" последовательностей.

Тогда можно ли считать, что такое доказательство приемлемо, и в каком смысле?
Ведь доказательства должны быть конечными, опираться на конечными построениями, рассуждениями, объектами и т.д. разве нет?
А построение такого объекта (которое существенно для доказательства) возможно требует бесконечных ресурсов - хотя оно и "декларируется", то нельзя его предъявить ни явно, ни в неявном (но конечном) смысле описанном выше.

П.П. Все из-за того, что уже два дня меня мучит вопрос про теореме Кантора - в смысле можно ли ее формулировать в финитном смысле (через "конечных алгоритмов", "для любого заданного натурального n" и т.д., без допущения "наперед заданных бесконечных списков", и последующего "построения бесконечного опровергаюшего примера" и т.д).
Возможно ли вообще это? Или в "конструктивных терминов", про теореме Кантора (и мощности континуума) вообще бессмысленно говорить в принципе?
И что произойдет, если мы попытаемся провернуть аналогичные рассуждения, в "конструктивных" (финитных) рамках, наподобие описанных выше?

(Вот до чего я пока дошел:)

Допустим, у нас "задан счетный список соответствия", где каждому натуральному числу сопоставлена "построимая последовательность $I$ "; в указанном выше смысле, это на самом деле означает что каждому натуральному n мы сопоставили "свой" алгоритм $A_n$ который определен над любым входом k (т.е. за конечное время мы можем получить результат $A_n(k)$ для любых натуральных $n,k$).
Тогда нетрудно аналогичным способом получить "противоречие", показывая что всегда можно сконструировать новый алгоритм $P$ который определяет новую построимую последовательность $I$, которая в данном счетном списке не встречается.
На самом деле однако, из этого разумеется отнюдь не следует, что "построимые последовательности $I$" несчетны.
Проблема тут в самом оригинальном списке - его невозможно построить "детерминированным образом" - чтобы из номера n, мы однозначно (конечным алгоритмическим образом) могли бы вытащить соответствующий ему алгоритм $A_n$ (чтобы далее емулировать его над соответным входом k, чтобы получить соответный k-тый разряд и инвертировать и т.д. и тому подобное).
Здесь из получения "противоречия" (возможности всегда предъявить "алгоритм $P$ для построимой последовательности $I$" не в списке) следует только то, что такого списка соответствий $n \rightarrow A_n$ нельзя "построить" (конструктивно).

Это видно еще из следующего рассуждения:
Упорядочим все возможные алгоритмы лексикографски. Тогда любому натуральному числу n сопоставлен какой-нибудь алгоритм $Q_n$, и это "исчерпывает" любые алгоритмы, т.е .нет алгоритма которому не было бы сопоставленно какое нибудь n.
Разумеется измежду $Q_n$ встречаются "дурные алгоритмы" типа неостанавливающиеся хотя бы над каким-то входом, дублирующиеся по функциональности и т.д. вообще "не всегда вычисляющие последовательности $I$" требуемым образом.
Тем не менее, все "хорошие" алгоритмы $A_n$ генерирующие "построимые последовательности $I$" тоже имеют номера, откуда заведомо следует что "построимые последовательности" не более чем счетны (как подмножество счетного множества).
Теперь четко видно, что проблема "построения противоречия" т.е. алгоритма $P$ для последовательности $I$ не имеющего номера генерящего ее алгоритма где-то в списке, сводится к проблеме останова (и тому, что нельзя алгоритмически узнать какие из алгоритмов в списке "дурные", и какие генерят построимые последовательности $I$).

Итак, теперь у меня по аналогию, закрались сомнения:
В оригинальной формулировке теореме Кантора где строится последовательность не принадлежащей данному бесконечному счетному списку, разве не может быть подобная ситуация?
Т.е. чтобы построение такой "последовательности не из списка", означало бы НЕ несчетность всех бесконечных последовательностей, а просто невозможность "детерминированно-конструктивно" упорядочить их в список (таким образом, чтобы алгоритмически по номеру n мы смогли получить n-тую цифру соответной n-той последовательности).
А "на самом деле", какой-то "неконструктивный" список где каждому натуральному n (или даже только некоторым из n) соответствует бесконечная последовательность, и он "исчерпателен" (любая бесконечная последовательность есть в этом списке) - возможно "существует", хотя и "не построим конструктивно"?

Тоесть теперь мне "кажется", что из оригинального построения Кантора, следует разве что:
а) либо бесконечные последовательности несчетны
б) либо бесконечные последовательности "все-таки счетны", но просто не существует метода их упорядочить в список таким образом, чтобы мы по заданному номеру n в списке могли бы "систематически-алгоритмически-детерминированно за конечное время" вытащить n-тый разряд n-той последовательности.
Когда кажется нужно "крестится" а мне что-то не хочется, есть ли тут ошибка, и где она?

[mihaild]

В теории множеств мы ничего на самом деле не строим, а просто берем множества, существование которых нам гарантировано аксиомами.
Диагональный метод Кантора чуть более формально работает так:
Пусть $F$ - некоторая функция $\mathbb N \to (\mathbb N \to \{0, 1\})$, т.е. множество пар вида $\langle i, f\rangle$, удовлетворяющее понятно каким свойствам.
Запишем схему преобразования:

$$\forall a \ ( \ \forall b \ (b \in a \to \exists^{\{1\}}y \ (\varphi[b,y]) \ ) \quad \to \quad \exists d \forall c \ (c \in d \leftrightarrow \exists b \ (b \in a \ \land \ \varphi[b,c]) \ ))$$

(скопировал из рувики, вроде опечаток нет, но претензии если что к авторам статьи там)
Подставим $\varphi(\langle i, f\rangle, x) \leftrightarrow (x = \langle i, 1 - f(i) \rangle)$.
В качестве $a$ возьмем наше $f$.
Тогда $d$, существование которого гарантирует аксиома - это как раз наша диагональная последовательность. И легко проверяется, что $\langle j, d\rangle$ не принадлежит $F$ ни для какого $j$, т.к. имеем $F(j)(j) \neq d(j)$.

[manul91]

mihaild в сообщении #1567791 писал(а):

Пусть $F$ - некоторая функция $\mathbb N \to (\mathbb N \to \{0, 1\})$, т.е. множество пар вида $\langle i, f\rangle$, удовлетворяющее понятно каким свойствам.

mihaild
А вы читали, что я писал под тегом оффопа, чтобы не утяжелять сообщение?
Вопрос ведь именно в этом почему мы решили считать что из функций "удовлетворяющих понятно каким свойствам" можно сделать упорядоченный список чтобы его далее каким-то образом использовать - какая аксиома/теорема гарантирует нам возможность существования/построения такого отображения?

А если возможность этого показывать ненужно (или гарантируется свыше), то "доказательство несчетности конструктивных последовательностей" можно провести ровно таким же образом:
Пусть задан бесконечный список "конструктивных последовательностей" ("удовлетворяющих понятно каким свойствам").
Тогда аналогичным образом строим "диагональную конструктивную последовательность", которая не в списке.
Точно так же получили (и сделали вывод) что "конструктивные последовательности" - несчетное множество.

Но мы-то знаем что это не так (из-за совершенно другого типа доказательства - предъявления в явном виде списка, где они исчерпательно отображаются на подмножество натуральных чисел).

Тогда, в аналогичном доказательстве (для несчетности не любых, а "конструктивных" бесконечных последовательностей) должна быть ошибка - так где она конкретно?

(Я не сомневаюсь, что символьное доказательство - подвергая манипуляций соответные строчки - формально проходит; наверное все-таки кто-нибудь это проверил. Вопрос не в строчках аксиом и правил вывода - ведь мы можем брать самых разных исходных наборов строчек-аксиом плюс правил-вывода и "получать" всяких самых разных других строчек; это по себе мало информативно и без "интерпретаций-моделей-связи-с-реальности" несколько бессмысленно. И не то что математики думают сильно по-другому - например, строчка аксиомы выбора некоторым из них "не нравится".
Поэтому, мне хотелось бы обсудить мой вопрос "на человеческом языке", а не убеждать меня что можно получить какую-то строчку посимвольно манипулируя строчек аксиом через правил вывода и пр. - в последнем я и так не сомневаюсь.)

[mihaild]

manul91 в сообщении #1567855 писал(а):

"удовлетворяющих понятно каким свойствам"

Ну раз вам не понравилось это выражение - давайте я запишу явно: $F$ такое, что для любого $i \in \mathbb N$ существует ровно одна $f \in (\mathbb N \to \{0, 1\})$ такая что $\langle i, f\rangle \in F$, и все элементы $F$ имеют вид $\langle i, f\rangle$ где $i \in \mathbb N$и $f\in (\mathbb N \to \{0, 1\})$. В общем просто определение функции как множества пар, которое вы наверняка знаете и без меня.

manul91 в сообщении #1567855 писал(а):

можно сделать упорядоченный список

А что это значит? Что в точности вы понимаете под "списком"? Это чем-то отличается от функции из натуральных чисел в последовательности? Если нет, то мы как раз и доказываем, что полного списка нет.

manul91 в сообщении #1567855 писал(а):

Тогда аналогичным образом строим "диагональную конструктивную последовательность", которая не в списке.

Если исходный список должен быть конструктивным - то мы доказали, что множество конструктивных последовательностей конструктивно несчетно, что правда. Если не обязательно - то диагональная последовательность тоже не обязана быть конструктивной. Я не понимаю, в чем проблема.

Диагональный метод показывает, что если допустимость последовательности и их нумерации определяются "одинаково" (так что можно, ссылаясь на нумерацию, определить новую последовательность), то не все допустимые последовательности пронумерованы. Если допустимы все возможные последовательности и нумерации - это дает стандартную теорему о неравномощности. Если допустимы только конструктивные - это дает конструктивную неравномощность.

И мой любимый парадокс Скулема в том числе про это: у $ZF$ есть модель, в которой множество двоичных последовательностей "на самом деле" счетно. Но если мы требуем, чтобы и нумерация, и последовательности были из этой модели - то опять же получаем, что с точки зрения этой модели множество последовательностей несчетно. А с точки зрения "внешней" модели - во "внутренней" не хватает нумераций, а если взять "внешнюю" нумерацию - то окажется, что и последовательностей во внутренней модели не хватает.

manul91 в сообщении #1567855 писал(а):

Поэтому, мне хотелось бы обсудить мой вопрос "на человеческом языке", а не убеждать меня что можно получить какую-то строчку посимвольно манипулируя строчек аксиом через правил вывода и пр. - в последнем я и так не сомневаюсь.)

Формальные строчки тут не самое ключевое, просто ими часто удобно записывать чтобы получился понятный результат.
Ключевой же момент - что, хотя мы и говорим, что что-то там меняется и строится по шагам - на более строгом (не обязательно формальном) уровне это реализуется с помощью функций, которые по номеру шага "выдают" результат на этом шаге, и

[manul91]

mihaild в сообщении #1567859 писал(а):

Если исходный список должен быть конструктивным - то мы доказали, что множество конструктивных последовательностей конструктивно несчетно, что правда. Если не обязательно - то диагональная последовательность тоже не обязана быть конструктивной. Я не понимаю, в чем проблема.

Нет, необязательно (что бы ни "конструктивный список" не значило)....
"Список конструктивных последовательностей" - это просто соответствие, которое каждому натуральному числу, сопоставляет "хороший алгоритм" $A_n$ (который "генерит" соответную конструктивную последовательность: т.е. если на вход $A_n$ подать натуральное число $k$ - номер разряда; то $A_n$ за конечное время выдает конкретное значение цифры этого разряда последовательности).
Теперь алгоритм $P$ для диагональной последовательности определен так: когда на вход $P$ подаем натуральное число $k$, то $P$ действует соответно: берет $k$-тую строку из списка, считывает из нее описание алгоритма $A_k$, емулирует его на универсальной машине Тьюринга над тем же входом $k$ (получая при этом $k$-тую цифирь $k$-той последовательности из списка) и детерминированным образом выдает цифру отличающейся от нее (напр. для двоичной последовательности делает $xor 1$ над ней).
Все операции конечны и детерминированы, мы построили конструктивную диагональную последовательность (ей соотвествует алгоритм $P$) которая не принадлежит списку.
Следовательно "конструктивных последовательностей - несчетное множество" (поскольку для любого заданного списка-соответствия, можно найти алгоритм конструктивной последовательности чей алгоритм в этом списке отсутствует).
Что тут "не так"?

mihaild в сообщении #1567859 писал(а):

Диагональный метод показывает, что если допустимость последовательности и их нумерации определяются "одинаково" (так что можно, ссылаясь на нумерацию, определить новую последовательность), то не все допустимые последовательности пронумерованы.

Этого не понял. Что конкретно значит "определяются одинаково", что значит "ссылаясь на нумерацию, определить последовательность"?

mihaild в сообщении #1567859 писал(а):

Но если мы требуем, чтобы и нумерация, и последовательности были из этой модели - то опять же получаем, что с точки зрения этой модели множество последовательностей несчетно. А с точки зрения "внешней" модели - во "внутренней" не хватает нумераций, а если взять "внешнюю" нумерацию - то окажется, что и последовательностей во внутренней модели не хватает.

mihaild в сообщении #1567859 писал(а):

авайте я запишу явно: $F$ такое, что для любого $i \in \mathbb N$ существует ровно одна $f \in (\mathbb N \to \{0, 1\})$ такая что $\langle i, f\rangle \in F$, и все элементы $F$ имеют вид $\langle i, f\rangle$ где $i \in \mathbb N$и $f\in (\mathbb N \to \{0, 1\})$. В общем просто определение функции как множества пар

Вот именно.
И в оригинальной теореме Кантора (все ниже про ней):
Каждая из тех бесконечных последовательностей $I$ которые в списке - это "обычная бесконечная последовательность" в следующем смысле: любой разряд (цифра) этой последовательности однозначно определяется только ее натуральным номером.
Знание натурального номера цифры (и ничего больше), однозначно определяет само значение цифры из последовательности, которое этому номеру соответствует. (И это не я придумал, т.к. данное свойство последовательностей из списка, существенно используется при определении диагональной последовательности $\Psi$, которая не в списке).
Является ли диагональная последовательность $\Psi$ которая строится Кантором и не в списке, "такого же типа" (из "этой же модели") как те последовательности $I$ из списка?
Отнюдь.
Для определения $k$-той цифры последовательности $\Psi$ (где $k$ произвольно), одно натуральное число $k$ недостаточно. Нужно еще иметь и бесконечную (точнее вдвойне-бесконечную) таблицу с которой "сверяться"; только после того как кроме $k$ дана и таблица, можно считать что $k$-ая цифра $\Psi$ определена однозначно (и да, вдвойне бесконечную таблицу нужно "иметь всю наперед" целиком, т.к. $k$ любое.)
Да, последовательность $\Psi$ несомненно внешне "похожа" на те последовательности $I$ из списка: и у ней и у тех есть первая цифра, и у ней и у тех имеется бесконечное (счетное) количество цифр, и т.д.
Но весь цимес в том, что у них эти цифры "есть", "имеются" и т.д. совершенно по-разному.
В последовательности $\Psi$ цифры "имеются" в совсем другом смысле, нежели "имеются" цифры в последовательностей $I$ из списка.
Для однозначного определения значения $k$-той цифры $I$ из списка, достаточно само $k$ (если $k$ известно, то и значение $k$-той цифры известно).
Для однозначного определения значения $k$-той цифры $\Psi$ одно $k$ недостаточно (нужно еще и наличие двойне-бесконечной таблицы).
Поэтому и неудивительно, что последовательности $\Psi$ нет в списке - хотя она и "внешне похожа" на последовательностей из списка - она "концептуально другого типа".
Если бы последовательности из списка $I$ были бы "такого же типа" как сама $\Psi$ (т.е. чтобы для этих последовательностий чтобы $k$-тая цифра считалась определенной, один ее номер $k$ был бы недостаточным - а нужна была бы еще и двойне-бесконечная таблица чтобы значение цифры определить) - то доказательство Кантора не прокатило бы (по меньшей мере, в его обычном виде).

[Dan B-Yallay]

manul91 в сообщении #1567868 писал(а):

Что конкретно значит "определяются одинаково"

Если я правильно понял. то это означает, что либо

"допустимые к рассмотрению последовательности и их нумерации заданы конструктивно"

либо

"допустимые к рассмотрению последовательности и их нумерации стандартны"

[Null]

manul91 в сообщении #1567868 писал(а):

это просто соответствие, которое каждому натуральному числу, сопоставляет "хороший алгоритм" $A_n$

В этом соответствии и проблема - оно не конструктивно. Вы же просто взяли подготовленный заранее список, такой операции в машине Тьюринга нет. Для конструктивных объектов лента в начале должна быть пустой(Иначе мы сможем получить вообще что угодно - начинаем с того что нам нужно и ни чего не делаем).

[manul91]

Null в сообщении #1567871 писал(а):

В этом соответствии и проблема - оно не конструктивно. Вы же просто взяли подготовленный заранее список, такой операции в машине Тьюринга нет. Для конструктивных объектов лента в начале должна быть пустой(Иначе мы сможем получить вообще что угодно - начинаем с того что нам нужно и ни чего не делаем).

Совершенно, на 100% согласен!
Другими словами, описанный алгоритм $P$ как минимум "не такой", как те алгоритмы $A_n$ в строках списка.
Для алгоритмов $A_n$ из списка: на вход подается только натуральное число $k$ - и за конечное время, они выплевывают значение $k$-той цифры последовательности (все это - по определению).
"Алгоритм" $P$ (если вообще можно называть это "алгоритмом"), на самом деле, чтобы "мог работать", кроме натурального $k$ на входе ("ленты"), требует еще и бесконечную таблицу (с конечными строками) на вход также, чтобы над ней мог "шаманить" (первое дело что $P$ делает, это "промотать" до строку $k$ таблицы чтобы сосчитать с ней описание алгоритма $A_k$ - очевидно, ему без таблицы на вход не обойтись).
В этом и ошибка в данном "доказательстве" несчетности конструктивных последовательностей.

Однако ведь, точно такую же претензию можно выкатить и Кантору, про его оригинальном доказательстве.
Строимая последовательность $\Psi$, которой нет в списке - совершенно не "такая же", как те последовательности $I$ которые в списке. У нее цифры "имеются" совершенно по-иному, нежели они "имеются" у последовательностей в списке. См. последний абзац моего прежнего сообщения где это расписано подробнее. Однако, почему-то у Кантора это не считается достаточной причины для "ошибочности доказательства", и $\Psi$ считается "такого же типа", как и те последовательности из списка?

[Null]

manul91 в сообщении #1567872 писал(а):

Однако, почему-то у Кантора это не считается достаточной причины для "ошибочности доказательства", и $\Psi$ считается "такого же типа", как и те последовательности из списка?

Это рассуждение можно записать через аксиомы и правила вывода. Значит все в порядке.

[manul91]

Null в сообщении #1567876 писал(а):

то рассуждение можно записать через аксиомы и правила вывода. Значит все в порядке.

Хорошо.
Я "утверждаю" (вполне допускаю, что ошибочно), что в оригинальном доказательстве Кантора:
Каждая из бесконечных последовательностeй из списка, определяется примерно как $(k \to D_k: k \in \mathbb N, D_k \in \{0, 1\})$ (здесь $k$ натуральное число, которому соответствует значение цифры $k$-того разряда $D_k$ последовательности, принимая значения из множества ${0,1}$). (Это не с потолка, так как я также считаю что это существенно используется в определении последовательности $\Psi$ которая не в списке).
С другой стороны, "мне кажется" что $\Psi$ (по ее же определению), не может определяться таким же образом, т.е. как $(k \to D_k: k \in \mathbb N, D_k \in \{0, 1\})$.
Я "считаю", что последовательность $\Psi$ в лучшем случае, определяется типа как $(\{k,S\} \to D_n: S:\mathbb N x \mathbb N, k \in \mathbb N, D_k \in \{0, 1\})$ (здесь $\{k,S\}$ множество из натурального числа и заданной наперед "вдвойне бесконечной таблицы", которому соответствует значение цифры $k$-того разряда $D_k$ последовательности). Существенно здесь - это наличие кроме натурального номера $k$, еще и таблицы $S$ в мэппинге на значения соответных разрядов последовательности.

Чтобы убедить меня что это не так, приведите пожалуйста доказательство из первых положений (последовательность символьных строчек, сгенерированных через аксиом и правил вывода) из которого следует, что в теореме Кантора последовательность $\Psi$ определяется таким же образом как и остальные последовательности в таблице (или разумеется, ссылку на такой вывод).

[Dan B-Yallay]

manul91 в сообщении #1567882 писал(а):

Существенно здесь - это наличие кроме натурального номера $k$, еще и таблицы $S$ в мэппинге на значения соответных разрядов последовательности.

Так ведь если рассматривать т. Кантора с предлагаемой Вами точки зрения, то по большому счёту она говорит следующее:

$$\forall \, S \in S_{\alpha}: \quad \exists \, I \notin S$$

где $S$ - пользуюсь Вашим термином "вдвойне бесконечная таблицa" (т.e. состоящая из счётного множества строк и элементами в $\{0,1\}$),
$\{S_{\alpha}\}$ - множество таких таблиц,
$I$ - строка из нулей и единиц.

При этом условия теоремы никак не оговаривают, каким образом нули и единицы "назначены" на свои места в таблице. Пусть даже и оракулом или самим Всевышним.

[mihaild]

считаю список синонимом функции из натуральных чисел куда нужно, если вы считаете списком что-то другое - скажите.

manul91 в сообщении #1567868 писал(а):

что бы ни "конструктивный список" не значило

Конструктивный список - это такой список, что существует вычисляющая его функция. Например конструктивный список конструктивных последовательностей - это такой список, что функция $f(i, j)$, сопоставляющая паре $i, j$ $j$-й элемент $i$-й последовательности, вычислима. Или, что эквивалентно, функция $f(i)$, выдающая по числу $i$ программу, вычисляющую $i$-ю последовательность, вычислима.

manul91 в сообщении #1567868 писал(а):

когда на вход $P$ подаем натуральное число $k$, то $P$ действует соответно: берет $k$-тую строку из списка

Вот это не так. Если исходный список был произвольный, то взять из него $k$-ю строку алгоритмически может не получиться.

manul91 в сообщении #1567868 писал(а):

Что конкретно значит "определяются одинаково", что значит "ссылаясь на нумерацию, определить последовательность"?

Это с моей стороны рукомахательство было, как формализовать - не знаю. Возможно в теории категорий есть что-то позволяющее это сделать.
Я говорю о том, что можно говорить что список и последовательности произвольные, или вычислимые, или (вроде бы можно) арифметические. В каждом из этих случаев последовательность, получаемая диагональным методом, будет принадлежать рассматриваемому классу последовательностей, и, соответственно, список неполон.
А вот если рассматривать списки произвольные, а последовательности вычислимые - то получающаяся диагональным методом последовательность вычислимой уже быть не обязана.

manul91 в сообщении #1567882 писал(а):

Каждая из бесконечных последовательностeй из списка, определяется примерно как $(k \to D_k: k \in \mathbb N, D_k \in \{0, 1\})$

Давайте вы сначала это формализуете?)
На уровне множеств никакие последовательности "не определяются". Теорема Кантора формулируется так: для любого списка последовательностей существует последовательность, не принадлежащая этому списку. Я думаю, вы справитесь сами записать это формулами и примерно вывести из аксиом, но если нет - я готов помочь.
Никаких "способов определения последовательности" здесь нет.
Для конструктивного случая опять же нет никаких "способов", просто добавляется в нужные места слово "конструктивно": "для любого конструктивного списка конструктивных последовательностей конструктивно существует [т.е. существует алгоритм, вычисляющий её по списку] конструктивная последовательность, не принадлежащая списку".

(я тут использую "конструктивно" и "вычислимо" как синонимы, что ЕМНИП некорректно, но вроде бы в данном контексте сойдет)

[manul91]

Dan B-Yallay в сообщении #1567886 писал(а):

При этом условия теоремы никак не оговаривают, каким образом нули и единицы "назначены" на свои места в таблице. Пусть даже и оракулом или самим Всевышним.

Так я и не оспариваю само построение Кантора как таковым, т.е. что можно определить "какую-то последовательность нулей и единиц" так, что бы она не содержалась в данном списке.

Я пока склоняюсь к мысли, что:
Словесное понятие "последовательности нулей и единиц" - слишком расплывчатое; и (неформально говоря) та последовательность $\Psi$ которая не в списке, не является "таким же объектом", как те последовательности которые в списке.
Нам дан счетный список объектов какого-то типа, мы построили/определили "похожий" объект однако другого типа (который не в том же списке) - это ничего не может говорить о счетности или несчетности множества объектов того типа, что в списке (то что мы можем решить словесно обзывать этого другого типа объекта тем же именем - разумеется погоду не делает).
Конкретнее - если каждая из последовательностей в списке являются отображением натуральных чисел к {0,1} - то последовательность $\Psi$ таким отображением не является (а является отображением натуральных чисел ВМЕСТЕ с наперед заданной фиксированной бесконечной таблицей $S$, к {0,1}.
Возможно понадобится уточнять, что понимается под отображением... Лично я считаю что отображение $\mathbb N \in \{0, 1\}$ можно считать заданным, если по натуральному числу $k$ однозначным образом можно назвать соответствующую ему цифру (0 или 1). Например если взять $k=19272$ то этим же и значение для 19272-й цифры (например 0) однозначно определено. Для последовательности $\Psi$ строимой на базе S, это очевидно не так - значение цифры не определяется (только) ее номером.

Точно так же, как в случае для конструктивных последовательностей, "алгоритм" $P$ нельзя считать таким же алгоритмом как те алгоритмы $A_n$ из списка - но там понятие алгоритма прецизно определено, и поэтому и понятно что речь идет вовсе не о таком объекте как те из списка (и если мы настаиваем расплычато обзывать их одним и тем же именем - типа все обзывать "алгоритмами" - это не меняет того факта, что они не одно и то же).

И да, также я (пока) сомневаюсь, что существует символьное доказательство (из аксиом и правил вывода) насчет того что определение последовательности $\Psi$ (как мэппинг что-то к чему-то) изпользуемой в доказательстве Кантора записывается так же, как и определение последовательностей из строчек списка (типа что и одно, и другое определяется одинаково как $(k \to D_k: k \in \mathbb N, D_k \in \{0, 1\})$).

-- 27.10.2022, 02:40 --

mihaild в сообщении #1567887 писал(а):

Конструктивный список - это такой список, что существует вычисляющая его функция. Например конструктивный список конструктивных последовательностей - это такой список, что функция $f(i, j)$, сопоставляющая паре $i, j$ $j$-й элемент $i$-й последовательности, вычислима. Или, что эквивалентно, функция $f(i)$, выдающая по числу $i$ программу, вычисляющую $i$-ю последовательность, вычислима.

Понятно. Нет, для конструктивных(вычислимых) последовательностей я не требую из бесконечного списка чтобы он был конструктивным(вычислимым), требую только то чтобы он был "задан наперед" (известным), хотя и произвольным.

mihaild в сообщении #1567887 писал(а):

Вот это не так. Если исходный список был произвольный, то взять из него $k$-ю строку алгоритмически может не получиться.

Как так "алгоритмически можно не получится"? Алгоритм P имеет на расположении этот список. Это произвольный список с началом и далее бесконечного счетного количества строк; каждая строка однако конечна (так как на ней записан конечный алгоритм, "генерирующий" соответную конструктивную последовательность). Все что от $P$ нужно - когда ему на вход подано $k$ - это чтобы промотать первых $k$ конечных строк из списка, чтобы прочитать конечное описание алгоритма $A_k$ в $k$той строке (и далее подать его на эмулятор Тьюринга и т.д. как я расписывал).
Какие тут могут быть проблемы? Все операции конечны. Это делает например консольная программа "#head -k" в линуксе - проматывает $k$ конечных строк с начала "текстового файла" (пусть и состоящегося из бесконечного количества строк).

mihaild в сообщении #1567887 писал(а):

А вот если рассматривать списки произвольные, а последовательности вычислимые - то получающаяся диагональным методом последовательность вычислимой уже быть не обязана.

Список произвольный, не обязательно конструктивный/вычислимый (в указзаном вами смысле); если хотите считайте что не вычислимый/конструктивный; важно только то что он на расположении, им "можно пользоваться" в буквальном смысле. В каждую из строк записан алгоритм $A_n$ "генерирующий" какую-то соответную вычислимую последовательность (что под всем этим понимается, я объяснил). Функцией которая по одного только номеру строки вычисляет алгоритм которой на ней записан - можно и не существовать. Но зато разумеется функция/алгоритм которая может просмотреть этот заданный список сначала вниз и вытащить что записано у него на $k$-той строке, разумеется существует (и тривиальна).
Почему "получающаяся диагональным методом последовательность вычислимой уже быть не обязана"? Я же предъявил в явном виде алгоритм $P$, который ее вычисляет - значит она есть, и вычислима.
Что с этим конкретно не так, вы можете четко сказать?

mihaild в сообщении #1567887 писал(а):

На уровне множеств никакие последовательности "не определяются".

mihaild в сообщении #1567887 писал(а):

Никаких "способов определения последовательности" здесь нет.

А вот это жалко. Что тогда гарантирует, что и последовательности которые в списке, и та "последовательность" $\Psi$ которая не в списке - это объекты одного и того же типа? Только то, что нам нравится мутно обзывать и теми и другими словесно неясным определением "бесконечной последовательности нулей и единиц"? Сомнительно : (
А вот если мне дан счетных список объектов какого-то одинакового типа (пусть $I$), и я построил объект другого типа ($\Psi$) который не в списке - это ничего не говорит о счетности или несчетности объектов типа $I$. Более того то, что $\Psi$ не в списке - совершенно неудивительно. Чуднее было бы, если б он тоже оказался там! : )

[Dan B-Yallay]

manul91 в сообщении #1567898 писал(а):

Так я и не оспариваю само построение Кантора как таковым, т.е. что можно определить "какую-то последовательность нулей и единиц" так, что бы она не содержалась в данном списке.

Мне кажется, Вы меня неправильно поняли.

manul91 в сообщении #1567898 писал(а):

Нам дан счетный список объектов какого-то типа

Давайте отвлечёмся от понятия "список" и рассмотрим просто конкретно заданную нам таблицу $S:$

$$\begin{matrix} s_{11} & s_{12} & s_{13} & \ldots \\ s_{21} & s_{22} & s_{23} & \ldots && \hspace{80} s_{ij} \in \{0,1\}\\ s_{31} & s_{32} & s_{33} & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{matrix} $$

Вычленимиз таблицы строку ($s_{1, j}, \ j \in \mathbb N$).

Вы согласны, что при нахождении значения $k$-того элемента этой первой строки (да и вообще любого элемента любой строки), необходимо знание (использование) таблицы $S$?
Если "да", то строка $\Psi$, полученная диагональным методом, будет того же "типа", что и строки в таблице. Тогда (в целях "однотипности строк") теорема просто формулируется в терминах описанных выже таблиц, а не "списков последовательностей".

Если не согласны, то укажите с чем именно.

[svv]

(Оффтоп)

Dan B-Yallay в сообщении #1567899 писал(а):

Вычленимиз

Это что-то тюркское, типа башларымыз, ишлеримиз и т.д.?