Язык математики

sup, inf и счётность

Почему max может не существовать, а sup существует всегда — и чем ℕ отличается от ℝ

Шаг 7 из 117 · ~22 мин

Максимум против точной верхней грани

max⁡A\max A — наибольший элемент множества, который сам принадлежит множеству.

sup⁡A\sup A — наименьшая из всех верхних границ. Принадлежать множеству она не обязана.

01
inf
0
min
—
sup
1
max
—
Вот ради этого случая и введены sup и inf. Единицы в множестве нет, максимума не существует, но точная верхняя грань всё равно равна 1.

Разница проявляется ровно там, где граница не достигается. У интервала (0,1)(0,1) максимума нет: какое число вы ни назовёте, найдётся большее, всё ещё меньшее единицы. А sup⁡=1\sup = 1 существует.

Формально s=sup⁡As = \sup A означает два условия:

  1. ss — верхняя граница: ∀x∈A,  x≤s\forall x \in A,\; x \le s;
  2. ss — наименьшая такая: любое s′<ss' < s уже не является верхней границей.

Аналогично inf⁡\inf — наибольшая нижняя граница.

Почему это важно

Ключевое свойство R\R: у всякого непустого ограниченного сверху множества существует супремум. Это не теорема, а аксиома полноты — то, чем R\R отличается от Q\Q. У множества {x∈Q:x2<2}\{x \in \Q : x^2 < 2\} супремум в Q\Q отсутствует, а в R\R он равен 2\sqrt2.

Практическое следствие для ML: когда пишут

inf⁡θ  L(θ)\inf_{\theta} \; L(\theta)

вместо min⁡\min, это признание того, что минимум может не достигаться. Функция потерь может стремиться к значению, которого никакой θ\theta не даёт. С inf⁡\inf запись корректна всегда, с min⁡\min — нет.

По той же причине в статьях аккуратно пишут arg min⁡\argmin отдельно от min⁡\min: первое может быть пустым или содержать много элементов, второе — число.

Счётность

Два бесконечных множества называются равномощными, если между ними существует биекция. Это единственное разумное определение «одинакового размера» для бесконечных множеств — и оно даёт неожиданные результаты.

Счётное множество — то, которое равномощно N\N: его элементы можно пронумеровать.

Счётны: N\N, Z\Z, Q\Q, множество всех конечных строк, множество всех программ. Последнее особенно показательно: программ счётное число, потому что каждая — конечная строка в конечном алфавите.

Несчётно: R\R, отрезок [0,1][0,1], множество всех функций N→{0,1}\N \to \{0,1\}.

Диагональный аргумент Кантора в одном абзаце: предположим, что все вещественные числа из [0,1][0,1] занумерованы. Построим число, у которого nn-я цифра отличается от nn-й цифры nn-го числа в списке. Оно отличается от каждого числа списка хотя бы одной цифрой, значит в списке его нет — противоречие.

Что из этого следует практически

Функций N→{0,1}\N \to \{0,1\} несчётно много, а программ счётно. Значит, почти все функции невычислимы — их нельзя задать никаким алгоритмом. Тот же аргумент объясняет, почему нейросеть с конечным числом параметров не может представлять произвольную функцию: пространство параметров имеет мощность континуума, а множество всех функций Rn→R\R^n \to \R — намного больше.

Для чтения статей этого уровня достаточно. Различать ℵ0\aleph_0 и 2ℵ02^{\aleph_0} и рассуждать о континуум-гипотезе не нужно ни разу.

Сводка обозначений

ЗаписьЧто этоВсегда ли существует
max⁡A\max Aнаибольший элемент AAнет
sup⁡A\sup Aнаименьшая верхняя границада, если AA ограничено сверху
min⁡A\min Aнаименьший элемент AAнет
inf⁡A\inf Aнаибольшая нижняя границада, если AA ограничено снизу
arg max⁡xf(x)\argmax_x f(x)точки, где достигается максимумнет; может быть много

Источники

Проверки

0 из 2
  1. Где существует максимум

    Для каких из перечисленных множеств max⁡\max существует?

  2. min против argmin

    Реализуйте min_and_argmin(values), которая возвращает список из двух элементов:

    1. минимальное значение в списке;
    2. список всех индексов, на которых оно достигается, по возрастанию.

    Для пустого входа верните [None, []] (в JS — [null, []]).

    Смысл упражнения в разнице между min⁡\min и arg min⁡\argmin: первое — число, второе — множество, которое может быть пустым или содержать несколько элементов.

    функция min_and_argmin

    Загрузка редактора…

    Ctrl/⌘ + Enter