2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение08.08.2021, 19:51 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Vladimir Pliassov в сообщении #1528344 писал(а):
Биекция это взаимно-однозначное отображение. Разве

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ...

это не взаимно-однозначное отображение?
А почему это взаимно однозначное отображение?
Чему равны здесь эти $b$-шки, $c$-шки и т.д.? Где у Вас гарантия, что все возможные последовательности нулей и единиц у Вас получаются с помощью такой функции?

Впрочем, неважно, чему они равны. К той функции, которую Вы построили, тоже можно применить диагональный процесс. Убедитесь, что последовательность $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$ не совпадает с $f(n)$ ни при каком натуральном $n$.

Наверное, Ваша ошибка вот в чём: Вы почему-то решили, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ единственная неучтённая, и если её добавить (например как $f(2)$), то получится биекция. Но это не так.

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение08.08.2021, 19:54 
Заслуженный участник
Аватара пользователя


16/07/14
8341
Цюрих
Vladimir Pliassov в сообщении #1528340 писал(а):
это будет означать признание $n=\infty.$
Что это вообще значит?
Нам принесли функцию $f$, и мы из неё делаем последовательность.
Vladimir Pliassov в сообщении #1528344 писал(а):
Разве $f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... это не взаимно-однозначное отображение?
Это вообще не конкретное отображение - для разных $a_i$, $b_i$ и т.д. будут разные функции.
И ни одна из них не будет биекцией. Диагональный метод выдаст последовательность $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$, которая образу этой функции не принадлежит.

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение08.08.2021, 21:47 
Аватара пользователя


23/12/18
430
Vladimir Pliassov в сообщении #1528344 писал(а):
$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ...
У вас $f(2) = (1-a_1, 1-b_2, 1-c_3, …)$? Странно. У меня $f(2) = (b_1, b_2, b_3, …)$, они не совпадают.

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 01:11 


21/04/19
1182
Mikhail_K в сообщении #1528347 писал(а):
А почему это взаимно однозначное отображение?

Бесконечные последовательности нулей и единиц -- в том числе и $(1-a_1, 1-b_2, 1-c_3, …)$, -- каждая из которых взаимно-однозначно соответствует единственному натуральному числу -- разве это не взаимно-однозначное отображение?

Mikhail_K в сообщении #1528347 писал(а):
Чему равны здесь эти $b$-шки, $c$-шки и т.д.?

Я не понимаю, что вы имеете в виду: $a, b, c \ldots$ с индексами это члены последовательностей. И здесь тоже:

mihaild в сообщении #1528348 писал(а):
Vladimir Pliassov в сообщении #1528344 писал(а):
Разве $f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... это не взаимно-однозначное отображение?
Это вообще не конкретное отображение - для разных $a_i$, $b_i$ и т.д. будут разные функции.

Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?

Mikhail_K в сообщении #1528347 писал(а):
Где у Вас гарантия, что все возможные последовательности нулей и единиц у Вас получаются с помощью такой функции?

Я и не говорю, что есть такая гарантия, здесь речь идет не обо всех последовательностях, а об этих: $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …);$ $f(3) = (c_1, c_2, c_3, …);$ ... плюс еще одна.

Mikhail_K в сообщении #1528347 писал(а):
Убедитесь, что последовательность $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$ не совпадает с $f(n)$ ни при каком натуральном $n$.

Я сначала подумал, что Вы имеете в виду $(1-a_1, 1-b_2, 1-c_3, …)$, но теперь смотрю и не пойму, что это за последовательность: $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$.

Но если бы Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$, то я бы сказал, что я в этом убеждался много раз, но мне кажется, что главный вопрос здесь не тот, отличается ли она от всех других указанных последовательностей (это само собой), а тот, может ли быть биекция между натуральными числами и последовательностями, привлеченными к доказательству, приведенному в начале темы. Этими последовательностями являются все те, которые в этом доказательстве представлены как строки таблицы, то есть $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …);$ $f(3) = (c_1, c_2, c_3, …);$ ... -- и, кажется, никто не спорит с тем, что они находятся в биекции с натуральными числами, -- плюс еще одна, то есть $(1-a_1, 1-b_2, 1-c_3, …)$.

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

Mikhail_K в сообщении #1528347 писал(а):
Наверное, Ваша ошибка вот в чём: Вы почему-то решили, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ единственная неучтённая,

Нет, я так не решил, я думаю, что неучтенные последовательности составляют подмножество $\{0, 1\}^\mathbb N$, равное разности $\{0, 1\}^\mathbb N$ и множества (не знаю, как его обозначить) последовательностей-строк бесконечной таблицы. Эти последовательности находятся в биекции с натуральными числами. То есть я полагаю, что теорема верна (то есть, что в биекции с натуральными числами находятся только последовательности-строки), но доказательство можно критиковать: к этим последовательностям-строкам можно добавить еще одну (инвертированную "диагональную"), и они вместе смогут находиться в биекции с натуральными числами.

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

Mikhail_K в сообщении #1528347 писал(а):
и если её добавить (например как $f(2)$), то получится биекция. Но это не так.

По-моему, это все-таки так: речь ведь идет не о биекции между $\mathbb N$ и всем множеством $\{0, 1\}^\mathbb N$, а о биекции между $\mathbb N$ и подмножеством $\{0, 1\}^\mathbb N$, состоящим из строк таблицы и ее инвертированной диагонали.

mihaild в сообщении #1528348 писал(а):
Что это вообще значит?

Vladimir Pliassov в сообщении #1528340 писал(а):
Если кто-то возразит, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ следует определять только после того, как определены последовательности $(a_1, a_2, a_3, …)$; $(b_1, b_2, b_3, …)$; $(c_1, c_2, c_3, …);$ ... , это будет означать признание $n=\infty.$

Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.

mihaild в сообщении #1528348 писал(а):
И ни одна из них не будет биекцией. Диагональный метод выдаст последовательность $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$, которая образу этой функции не принадлежит.

Здесь опять эта последовательность. Может быть, Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$? Если так, то:

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

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... .

xagiwo в сообщении #1528362 писал(а):
У вас $f(2) = (1-a_1, 1-b_2, 1-c_3, …)$? Странно. У меня $f(2) = (b_1, b_2, b_3, …)$, они не совпадают.

Я это сделал, чтобы, так сказать, "внести эту последовательность в список."

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 01:25 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Vladimir Pliassov в сообщении #1528371 писал(а):
По-моему, это все-таки так: речь ведь идет не о биекции между $\mathbb N$ и всем множеством $\{0, 1\}^\mathbb N$, а о биекции между $\mathbb N$ и подмножеством $\{0, 1\}^\mathbb N$, состоящим из строк таблицы и ее инвертированной диагонали.
Никто не спорит, что такая биекция возможна. И что? Вопрос-то был о существовании биекции
Vladimir Pliassov в сообщении #1528371 писал(а):
между $\mathbb N$ и всем множеством $\{0, 1\}^\mathbb N$


Vladimir Pliassov в сообщении #1528371 писал(а):
Может быть, Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$?
Нет, имелась в виду та, которая написана. Но если Вы согласны, что Вы не построили биекцию между $\mathbb N$ и $\{0, 1\}^\mathbb N$, а построили только биекцию между $\mathbb N$ и каким-то подмножеством $\{0, 1\}^\mathbb N$, то Вам необязательно в это вникать. В таком случае сформулируйте, в чём вообще Ваш вопрос.

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 02:10 
Аватара пользователя


23/12/18
430
Vladimir Pliassov в сообщении #1528371 писал(а):
Нет, я так не решил, я думаю, что неучтенные последовательности составляют подмножество $\{0, 1\}^\mathbb N$, равное разности $\{0, 1\}^\mathbb N$ и множества (не знаю, как его обозначить) последовательностей-строк бесконечной таблицы. Эти последовательности находятся в биекции с натуральными числами. То есть я полагаю, что теорема верна (то есть, что в биекции с натуральными числами находятся только последовательности-строки), но доказательство можно критиковать: к этим последовательностям-строкам можно добавить еще одну (инвертированную "диагональную"), и они вместе смогут находиться в биекции с натуральными числами.
Ага, значит, Вы согласны с доказательством того, что моя $f$ не является биекцией, но считаете, что можно построить какую-то другую функцию, которая это доказательство как-то обходит? Но тогда эта другая функция не будет возвращать уже свою инвертированную диагональ, то есть она тоже не биекция. Вы указали на какую-то функцию (давайте обозначим её $g$, потому что всё же $f(2) = (b_1, b_2, …)$) с $g(2) = (1-a_1, 1-b_2, …)$, а Вам показали, что она не возвращает свою инвертированную диагональ, которая выглядит как $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$

Короче говоря, доказательство работает для всех функций, включая те, которые Вы строите, чтобы его обойти.

-- 09.08.2021, 03:02 --

Vladimir Pliassov в сообщении #1528371 писал(а):
Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.
В каком смысле? Формула $a_n = n^2$, например, задаёт сразу все члены последовательности $a_n$

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 16:45 


21/04/19
1182
Кажется, понял.

В $\{0, 1\}^\mathbb N$ (в множестве всевозможных бесконечных последовательностей нулей и единиц) можно выделить подмножество $A$ (не знаю, как его обозначить более подробно), элементы которого можно представить в виде строк таблицы

$$\begin {matrix}
\alpha_1=&\alpha_{11}&\alpha_{12}&\alpha_{13}&\ldots\\
\alpha_2=&\alpha_{21}&\alpha_{22}&\alpha_{23}&\ldots\\
\alpha_3=&\alpha_{31}&\alpha_{32}&\alpha_{33}&\ldots\\
\hdotsfor [1.5] {5} \\
\end {matrix}\eqno {(1)}$$
при этом элементы $A$ будут поставлены во взаимно-однозначное соответствие с $\mathbb N$ (с множеством всех натуральных чисел), то есть будет задана биекция $f\colon \mathbb N\to A$.

В $\{0, 1\}^\mathbb N$, кроме элементов подмножества $A$, имеется, по крайней мере, один элемент, которого нет в $A$ , а именно, последовательность $\beta$ (полученная инвертированием последовательности $\alpha_ {11}, \alpha_ {22}, \alpha_ {33}, \ldots$), которой не может быть в таблице, следовательно, биекции между $\mathbb N$ и $\{0, 1\}^\mathbb N$ быть не может.

Спасибо всем!

xagiwo в сообщении #1528375 писал(а):
Vladimir Pliassov в сообщении #1528371 писал(а):
Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.
В каком смысле? Формула $a_n = n^2$, например, задаёт сразу все члены последовательности $a_n$

Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены).

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 18:52 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Vladimir Pliassov в сообщении #1528371 писал(а):
Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?
Откуда здесь взялось взаимно однозначное соответствие? Процитированное равенство означает, что функция $f$ натуральному числу $1$ сопоставляет указанную последовательность. Вполне возможно, что и $f(2)=(a_1, a_2, a_3, …)$.

Vladimir Pliassov в сообщении #1528371 писал(а):
я думаю, что неучтенные последовательности составляют подмножество $\{0, 1\}^\mathbb N$, равное разности $\{0, 1\}^\mathbb N$ и множества (не знаю, как его обозначить) последовательностей-строк бесконечной таблицы. Эти последовательности находятся в биекции с натуральными числами.
Неучтённые последовательности находятся в биекции с натуральными числами? С какой стати? Где эта биекция? Вы её не предъявили.

Vladimir Pliassov в сообщении #1528371 писал(а):
Я это сделал, чтобы, так сказать, "внести эту последовательность в список."
А какой в этом смысл? Мы взяли произвольный список последовательностей (последовательность последовательностей) и показали, что список не полон, так как мы смогли указать последовательность, не входящую в него. Наше рассуждение работает для всех списков. В том числе и для того, который Вы получите в результате добавления новой последовательности. Следовательно, полных списков не существует. Поэтому множество всех последовательностей нулей и единиц несчётно.

-- Пн авг 09, 2021 18:56:54 --

Vladimir Pliassov в сообщении #1528402 писал(а):
Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены)
А зачем её всю записывать "на бумаге"? Она каким-то способом определена, и мы как-то можем найти любой её член. Нам неважно, как именно.

 Профиль  
                  
 
 Re: "Диагональное" доказательство теоремы Кантора
Сообщение09.08.2021, 21:38 


21/04/19
1182
Someone в сообщении #1528412 писал(а):
Vladimir Pliassov в сообщении #1528371 писал(а):
Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?
Откуда здесь взялось взаимно однозначное соответствие? Процитированное равенство означает, что функция $f$ натуральному числу $1$ сопоставляет указанную последовательность. Вполне возможно, что и $f(2)=(a_1, a_2, a_3, …)$.

Да, это я не подумал.

Someone в сообщении #1528412 писал(а):
Vladimir Pliassov в сообщении #1528371 писал(а):
я думаю, что неучтенные последовательности составляют подмножество $\{0, 1\}^\mathbb N$, равное разности $\{0, 1\}^\mathbb N$ и множества (не знаю, как его обозначить) последовательностей-строк бесконечной таблицы. Эти последовательности находятся в биекции с натуральными числами.
Неучтённые последовательности находятся в биекции с натуральными числами? С какой стати? Где эта биекция? Вы её не предъявили.

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

Someone в сообщении #1528412 писал(а):
Vladimir Pliassov в сообщении #1528371 писал(а):
Я это сделал, чтобы, так сказать, "внести эту последовательность в список."
А какой в этом смысл? Мы взяли произвольный список последовательностей (последовательность последовательностей) и показали, что список не полон, так как мы смогли указать последовательность, не входящую в него. Наше рассуждение работает для всех списков. В том числе и для того, который Вы получите в результате добавления новой последовательности. Следовательно, полных списков не существует. Поэтому множество всех последовательностей нулей и единиц несчётно.

Да, теперь я это понимаю.

Someone в сообщении #1528412 писал(а):
Vladimir Pliassov в сообщении #1528402 писал(а):
Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены)
А зачем её всю записывать "на бумаге"? Она каким-то способом определена, и мы как-то можем найти любой её член. Нам неважно, как именно.

Да, и теперь я понимаю это лучше, чем раньше, спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 159 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group