2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 "всё дискретное - счетно"
Сообщение24.07.2021, 15:23 


02/05/21
14
Детский пример биекции (конечные множества):

В зале дамы и кавалеры. Зазвучал вальс, закружились пары.
Если, скажем, не танцующих дам нет, а кавалеры еще остались - делаем вывод, что кавалеров больше.
Если не танцующих нет вообще - делаем вывод что дам и кавалеров поровну.

Ясно и прозрачно )
Бесконечные множества не могут быть "равны", про них мы говорим "равномощны". Но инструмент тот же - установление взаимно-однозначного соответствия, т.е. те же самые дамы и кавалеры танцуют парами. Однако, тот, да не тот...
Важным отличием является слово "можно".
Конечных дам и кавалеров как ни разбей на пары "кавалер - дама" - результат будет абсолютно одинаковым.
А бесконечных дам и кавалеров можно поставить в пары так, что не танцующих не будет, а можно и так, что все дамы танцуют, а кавалеров еще осталось сколько угодно.
Например (извините за банальности), есть множество натуральных чисел и множество четных чисел.
Поставим в пару каждому четному равное ему натуральное - останутся "лишними" все нечетные натуральные.
Поставим в пару каждому четному 2n натуральное n - все дамы и кавалеры окажутся вальсирующими.
Поэтому определение биекции в случае бесконечных множеств не может обойтись без слова "можно" - если _можно_ поставить в пары дам и кавалеров так, чтобы все танцевали, то множества равномощны. Достаточно предъявить ровно один способ (он часто вообще единственный), дающий соответствие, а все остальные способы постановки в пары (а их сколько угодно) нас просто не интересуют и нами никак не учитываются, отбрасываются.
И это вполне законно, конечно. Раз мы указали конкретный способ, как "занумеровать" элементы множества (останемся в рамках самых простых счетных множеств), то оно счетно. А всё остальное (из серии "как в заполненную до отказа бесконечную гостиницу подселить еще одну бесконечную делегацию") сколь угодно забавно, но никак не опровергает уже установленный факт.
Ок! Проблема не в этом.
Да, в некоторых случаях (типа биекции n - 2n) до способа установить соответствие догадается почти любой школьник. Но в других случаях - далеко не любой и не только школьник. Вот перед нами, скажем, множество узлов целочисленной решетки (бесконечной клетчатой бумаги). Предположим на секунду, что мы еще не додумались до спирального обхода. Мы и так прикидываем, и эдак, но пока что не изобрели метода, как явно занумеровать узлы натуральными числами. Значит ли это, что мы сомневаемся в счетности узлов решетки? Нет! Нам абсолютно очевидно, что это так и есть, просто мы пока не доказали этого факта, но это дело времени - чуток подумаем еще и укажем способ.
А почему нам очевидно?
Потому что рассматриваемое множество очевидно (в буквальном смысле - глазами видно) дискретно.
А всё дискретное - счетно.
Такого определения в явном виде нет, но оно же верно!
Как и обратное: всё непрерывное - несчетно.
Ну ладно, приведенный пример слишком прост, спиральный обход мы быстро придумаем. А если что посложнее? Скажем, до строгого доказательства счетности рациональных чисел уж точно не каждый самостоятельно додумается. Если вообще додумается. Но если мы не может придумать алгоритм нумерации, то это не должно быть помехой в доказательстве счетности! Ибо в каждом конкретном случае догадаться до метода нумерации может быть сколь угодно трудно. Но при этом сама счетность (или нет) может быть совершенно очевидна.
Для установления факта счетности или несчетности множества вполне достаточно установления факта его дискретности или непрерывности соответственно.
Например, те же рациональные числа. Они "всюду плотны", и это поначалу смущает. Но показать, что они дискретны не составляет труда. Ну, скажем, так: возьмем две дроби с числителями 1 и 2, а знаменатель любой. Независимо от знаменателя, мы можем между числителями 1 и 2 поставить иррациональное "корень из двух". Так же и между любыми целыми числами. Следовательно рациональные числа не непрерывны, т.е. дискретны. А всё дискретное - счетно.
Вопрос: согласны ли вы, что утверждение "всё дискретное счетно" истинно и вполне корректно?

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 15:32 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Дайте определение "дискретности", которым вы пользуетесь. Оно хотя бы про метрику, про порядок, или про что-то еще?

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 16:49 


07/11/20
44
kirilych в сообщении #1526989 писал(а):
Как и обратное: всё непрерывное - несчетно.
Возьмите сужение линейной функции $f(x) = x$ на $\mathbb{Q}$ - получится всюду непрерывная функция, определённая на счетном множестве и принимающая счетное множество значений.

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 16:59 
Заслуженный участник
Аватара пользователя


28/09/06
10414
kirilych в сообщении #1526989 писал(а):
Достаточно предъявить ровно один способ (он часто вообще единственный), дающий соответствие

А самое интересное, это когда способа предъявить биекцию нет, но всё равно "доказано", что она существует.

kirilych в сообщении #1526989 писал(а):
Например, те же рациональные числа. Они "всюду плотны", и это поначалу смущает. Но показать, что они дискретны не составляет труда. Ну, скажем, так: возьмем две дроби с числителями 1 и 2, а знаменатель любой. Независимо от знаменателя, мы можем между числителями 1 и 2 поставить иррациональное "корень из двух".

Что бы это значило? Концепция "дискретности" остаётся загадкой. В чём, собственно, "дискретность" рациональных чисел, если между любыми двумя неравными рациональными числами всегда можно вставить третье рациональное число?

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 17:01 


07/11/20
44
kirilych в сообщении #1526989 писал(а):
А если что посложнее? Скажем, до строгого доказательства счетности рациональных чисел уж точно не каждый самостоятельно додумается. Если вообще додумается. Но если мы не может придумать алгоритм нумерации, то это не должно быть помехой в доказательстве счетности! Ибо в каждом конкретном случае догадаться до метода нумерации может быть сколь угодно трудно. Но при этом сама счетность (или нет) может быть совершенно очевидна.

Кстати чтобы доказать счетность рациональных чисел не обязательно предъявлять явную нумерацию. Достаточно заметить, что любое рациональное число можно записать с помощью символов конечного алфавита (10 цифр, дробная черта и минус).

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 17:48 


02/05/21
14
mihaild в сообщении #1526992 писал(а):
Дайте определение "дискретности"


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

epros в сообщении #1527005 писал(а):
В чём, собственно, "дискретность" рациональных чисел, если между любыми двумя неравными рациональными числами всегда можно вставить третье рациональное число?


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

kmpl в сообщении #1527007 писал(а):
Кстати чтобы доказать счетность рациональных чисел не обязательно предъявлять явную нумерацию. Достаточно заметить, что любое рациональное число можно записать с помощью символов конечного алфавита (10 цифр, дробная черта и минус).


Ну, это вообще-то верно, но не вполне честно )) Ведь это и есть _определение_ рационального числа - представимость в виде обыкновенной дроби. Доказательство типа "ибо таково определение". Хотя, впрочем, в данном случае оно законно... Если, конечно, вставить слово "конечного" - "...конечного числа символов..." Ибо числитель и/или знаменатель могут быть сколь угодно велики, но всегда конечны. А так-то и Пи записывается с помощью десяти цифр и запятой.

Я к тому, что далеко не всякий сходу изобретет способ, подобный спиральному обходу, для, скажем, узлов трехмерной целочисленной решетки, а уж тем более n-мерной. Однако, дискретность множества этих точек стопудово указывает на их счетность, т.е. иного доказательтсва, кроме факта дискретности, как бэ и не требуется. Разве не так?

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 17:49 
Заслуженный участник


16/02/13
4105
Владивосток
kmpl в сообщении #1527007 писал(а):
с помощью символов конечного алфавита
С помощью конечного количества символов конечного алфавита.

-- 25.07.2021, 00:50 --

А, опоздал.

-- 25.07.2021, 00:53 --

kirilych в сообщении #1527009 писал(а):
дискретность множества этих точек стопудово указывает на их счетность
Вы как-то, имхо, всё время неявно предполагаете дискретное множество на $\mathbb R$. Уже на действительной плоскости вы не разместите вот так запросто точку промежду двух других.

-- 25.07.2021, 00:56 --

Что-то я не нашёл определения дискретного множества в топологии. Не укажете? Дискретную топологию — нашёл. Дискретную метрику — нашёл. А вот дискретного множества — нет.

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 17:57 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
kirilych в сообщении #1527009 писал(а):
Дискретность в топологии - это множество изолированных друг от друга точек
А что такое "изолированные точки"? Ну и "дискретность" - это свойство (тогда определение должно бы иметь вид "дискретным множеством называется ...") или именно объект (типа области)?

В любом случае, подмножество $\l_\infty$, состоящее из всех последовательностей из нулей и единиц, вы считаете дискретным?

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 18:03 
Аватара пользователя


23/12/18
430
kirilych в сообщении #1527009 писал(а):
между любыми двумя неравными рациональными можно вставить иррациональное

Так же, как и между любыми двумя иррациональными.

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 18:08 


07/11/20
44
kirilych в сообщении #1527009 писал(а):
Ведь это и есть _определение_ рационального числа - представимость в виде обыкновенной дроби.

Нет, определение другое. Рациональное число - это элемент множества рациональных чисел. А само множество рациональных чисел - это поле частных кольца $\mathbb{Z}$. Очевидно, что рациональные числа можно отождествить с их несократимыми записями, а они образуют подмножество в множестве слов того конечного алфавита, о котором я выше написал.
iifat в сообщении #1527010 писал(а):
С помощью конечного количества символов конечного алфавита.

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

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 18:20 


02/05/21
14
iifat в сообщении #1527010 писал(а):
Что-то я не нашёл определения дискретного множества в топологии. Не укажете?


Тысяча извинений за лень и цитирование Википедии )) В статье "дискретность" сказано:
"Общая топология — дискретным называется множество, состоящее лишь из изолированных точек."
Мне кажется, что понятие "изолированная" достаточно прозрачно. Или нет?

iifat в сообщении #1527010 писал(а):
Вы как-то, имхо, всё время неявно предполагаете дискретное множество на $\mathbb R$. Уже на действительной плоскости вы не разместите вот так запросто точку промежду двух других.


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

mihaild в сообщении #1527011 писал(а):
В любом случае, подмножество $\l_\infty$, состоящее из всех последовательностей из нулей и единиц, вы считаете дискретным?


Дискретным и счетным в этом случае можно считать лишь множество самих символов "0" и "1". Ибо символы очевидно дискретны, как яблоки.

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 18:23 


07/11/20
44
По поводу определения дискретного множества
Someone в сообщении #1206652 писал(а):
Для подмножества $D$ топологического пространства $X$ мне встречались такие термины:
1) $D$ дискретно в себе, если оно дискретно в топологии подпространства, то есть, для каждой точки $x\in D$ существует такая окрестность $Ux\subseteq X$, что $D\cap Ux=\{x\}$, или, другими словами, $Ux$ не содержит других точек множества $D$;
2) $D$ дискретно в $X$, если для каждой точки $x\in X$ найдётся окрестность $Ux\subseteq X$, которая содержит не более одной точки множества $D$.

В первом случае множество $D$ может иметь предельные точки в пространстве $X$. Во втором случае в $T_1$-пространстве предельных точек не будет, но в общем случае предельные точки могут быть.

На всякий случай: точка $x_0\in X$ называется предельной точкой множества $M\subseteq X$, если каждая окрестность точки $x_0$ содержит хотя бы одну точку множества $M$, не совпадающую с точкой $x_0$.
Кстати, этого вполне достаточно, чтобы определение предела $\lim\limits_{x\to x_0}fx$ было осмысленным.

И ещё. В одной древней статье мне встречалось такое определение дискретного пространства: топологическое пространство называется дискретным, если в нём пересечение любого семейства открытых множеств является открытым.
Это определение в случае $T_1$-пространств эквивалентно обычному (все точки являются изолированными), но в общем случае — нет. Например, любое конечное топологическое пространство является дискретным в этом смысле.

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 19:53 


02/05/21
14
kirilych в сообщении #1527015 писал(а):
mihaild в сообщении #1527011

писал(а):
В любом случае, подмножество $\l_\infty$, состоящее из всех последовательностей из нулей и единиц, вы считаете дискретным?

Дискретным и счетным в этом случае можно считать лишь множество самих символов "0" и "1". Ибо символы очевидно дискретны, как яблоки.



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

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

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 20:36 
Заслуженный участник
Аватара пользователя


28/09/06
10414
kirilych в сообщении #1527009 писал(а):
элементы чего как-то отделены друг от друга

"Отделены" чем? Почему рациональные числа должны быть "отделены друг от друга" именно иррациональными числами, а не зелёными мартышками?

kirilych в сообщении #1527015 писал(а):
Мне кажется, что понятие "изолированная" достаточно прозрачно. Или нет?

Я бы предпочёл услышать определение, ибо мало ли что Вы думаете...

 Профиль  
                  
 
 Re: "всё дискретное - счетно"
Сообщение24.07.2021, 22:40 
Заслуженный участник
Аватара пользователя


01/09/13
4318
kirilych в сообщении #1527015 писал(а):
Мне кажется, что понятие "изолированная" достаточно прозрачно. Или нет?

В дискретной топологии на любом множестве все точки изолированы.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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