Объясните понятно про мощности множеств

[realeugene]

B3LYP
Начните с выписывания определения. Два множества равномощны тогда и только тогда, когда...

[B3LYP]

Изначально я стал изучать эту тему, поскольку мне предложили разобраться в теореме Островского:

https://en.wikipedia.org/wiki/Ostrowski%27s_theorem

Цитата:

In number theory, Ostrowski's theorem, due to Alexander Ostrowski (1916), states that every non-trivial absolute value on the rational numbers
�
{\displaystyle \mathbb {Q} } is equivalent to either the usual real absolute value or a p-adic absolute value.[1]

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

[dgwuqtj]

Какая вообще связь с теоремой Островского, если теорема только про рациональные числа? Пополнения (вещественные и $p$-адические числа) — это уже потом.

[пианист]

B3LYP
Если я правильно понял, Вы говорите о том, что пары натуральных чисел можно пронумеровать (так же как, кстати, и тройки, четверки, etc, а также все конечные наборы). Засада в том, что вещественное число задается бесконечным набором, а вот бесконечные наборы Вы пронумеровать не сможете; то же верно по отношению к p-адическим.
Причем тут теорема Островского, тоже не уловил.

[wrest]

B3LYP в сообщении #1704054 писал(а):

Можно ли на примере спирали как-то проиллюстрировать, что для множества вещественных чисел такую биекцию сделать нельзя?

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

[Утундрий]

Очевидно, в сознании ТС смешались Колмогоров, Фомин и Островский. Осуществляя метафорический ля мур де труа.

[realeugene]

B3LYP
Воспользуйтесь теоремой Кантора: https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%80%D0%B0

Каждому подмножеству натуральных чисел можно сопоставить действительное число в интервале от 0 до 1, записав это действительное число в двоичной записи. При этом, в каждое такое действительное число отображается не более двух таких подмножеств. Но множество всех подмножеств натуральных чисел несчётно по теореме Кантора, так что множество, состоящее из не более чем объединённых в пары всех различных подмножеств натуральных чисел, тоже несчётно.

[B3LYP]

Может немного не в тему, но захотелось спросить.

Цитата:

Что лучше – вечное блаженство или бутерброд с ветчиной? На первый взгляд может показаться, что вечное блаженство лучше. Но, если рассуждать логически, можно взглянуть на вопрос по-иному. Что лучше вечного блаженства? Ничто. А бутерброд с ветчиной лучше, чем ничто. Следовательно, бутерброд с ветчиной лучше, чем вечное блаженство.

У меня вопрос к знатокам теории множеств. Можно ли так сформулировать, почему бутерброд лучше вечного блаженства:

Цитата:

Множество элементов, которые лучше вечного блаженства, пусто (не факт, но допустим, что так). Бутерброд лучше любого элемента пустого множества. Вроде как при аккуратной формулировке противоречия не возникает, поскольку пустое множество не содержит элемента, который лучше вечного блаженства.

[realeugene]

B3LYP
Лучше подумайте над поговоркой "одна ложка дёгтя портит бочку мёда". В приложении к форуму, один пост пурги делает всю тему пургой.

[chinaman]

B3LYP

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

$$ \begin{array}{lccccccccc} \text{первое число} = & . & \boxed{3} & 6 & 4 & 9 & 1 & 5 & 8 & \ldots \\ \text{второе число} = & . & 8 & \boxed{2} & 7 & 3 & 6 & 4 & 1 & \ldots \\ \text{третье число} = & . & 5 & 9 & \boxed{1} & 2 & 8 & 7 & 3 & \ldots \\ \text{четвёртое число} = & . & 1 & 6 & 5 & \boxed{7} & 3 & 9 & 2 & \ldots \\ \text{пятое число} = & . & 7 & 4 & 8 & 1 & \boxed{6} & 2 & 5 & \ldots \\ \text{шестое число} = & . & 2 & 3 & 6 & 4 & 9 & \boxed{5} & 8 & \ldots \\ \vdots & . & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$

Теперь построим новое число $y$, используя диагональ матрицы (выделенные цифры). Для каждой позиции в числе $y$ мы выберем цифру, которая отличается от соответствующей диагональной цифры. Например, если диагональная цифра не равна 1, мы используем 1; если она равна 1, мы используем 2.

$$y = .112111\ldots$$

Почему число $y$ не может находиться в нашей матрице?
* $y$ отличается от первого числа ($.364\ldots$) в первой позиции: $1 \neq 3$
* $y$ отличается от второго числа ($.827\ldots$) во второй позиции: $1 \neq 2$
* $y$ отличается от третьего числа ($.591\ldots$) в третьей позиции: $2 \neq 1$
* $y$ отличается от четвёртого числа ($.165\ldots$) в четвёртой позиции: $1 \neq 7$
* И так далее для всех чисел в списке...

Вот противоречие: Мы предположили, что матрица содержит все вещественные числа, которые можно сосчитать. Но мы только что построили новое вещественное число $y$, которое гарантированно не находится в этом списке! Это означает, что невозможно сосчитать все вещественные числа - их слишком много. Множество вещественных чисел несчётно.

[B3LYP]

chinaman

Не понимаю пока. Почему вы уверены что числа .112111... нет в изначально списке? Там же вы привели набор случайных чисел, значит и .112111 в принципе там может оказаться.

[realeugene]

B3LYP в сообщении #1704289 писал(а):

Почему вы уверены что числа .112111... нет в изначально списке?

Потому что по построению этого числа, хотя бы одна цифра в десятичной записи этого числа отличает его от любого другого числа в списке. Первая цифра отличается от первой цифры первого числа в списке, вторая цифра от второй цифры второго числа в списке, и так далее.

[B3LYP]

Попробую так рассуждать. Имеем набор из шести вещественных чисел:

.641732
.916649
.603318
.906649
.554671
.011772

Можно взять диагональ:
.613672

Далее можно построить число, во всех знаках отличающееся от диагонали:
.121111

Понятно что это число отличается от всех шести, т.е. если мы пронумеровали эти шесть чисел натуральными числами от 1 до 6, сейчас я доказал что "оно не пронумеровалось до конца".
Теперь возьмём массив 6*6 из целых чисел от 0 до 9:

641732
916649
603318
906649
554671
011772

Мы их можем пронумеровать 36-ю натуральными числами, от 1 до 36. И пока у меня получается, что такой массив было "сложнее пронумеровать" - элементов потребовалось больше. А вы говорите что такой массив пронумеровать "легче". Извиняюсь, пока собственно всё, у меня просто мысли вслух, может потом ещё какие-то идеи появятся.

[wrest]

B3LYP в сообщении #1704348 писал(а):

А вы говорите что такой массив пронумеровать "легче".

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

[provincialka]

wrest в сообщении #1704352 писал(а):

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

Собственно, а зачем предполагать это? Просто берем какой-то список вещественных чисел и утверждаем, что он неполный. Любой список неполный. И всё.