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

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

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

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

[0, 1](0, 1)[0, 1)[0, +∞)

inf

0

min

—

sup

1

max

—

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

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

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

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

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

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

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

$\inf_{\theta} \; L(\theta)$

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

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

Счётность

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

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

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

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

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

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

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

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

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

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