Произведение, степень, семейства

Три конструкции, из которых потом собирается почти всё: пары, множество всех подмножеств и индексированные семейства.

Декартово произведение

$A \times B = \{(a, b) : a \in A,\; b \in B\}$

Множество всех упорядоченных пар, где первый элемент взят из $A$, второй из $B$. Ключевое слово — упорядоченных: $(1, 2) \ne (2, 1)$, в отличие от $\{1, 2\} = \{2, 1\}$.

Для конечных множеств $|A \times B| = |A| \cdot |B|$ — отсюда и слово «произведение». Это в точности вложенный цикл:

[(a, b) for a in A for b in B]

Степень $A^n$ — это $A \times A \times \dots \times A$, то есть множество кортежей длины $n$. И вот тут конструкция окупается:

$$\htmlData{k=rn}{\R^n} = \underbrace{\R \times \R \times \cdots \times \R}_{\htmlData{k=n}{n} \text{ раз}}$$

Вектор из $\R^n$ — это просто элемент декартовой степени, то есть кортеж из $n$ чисел. Никакой магии в записи $x \in \R^{784}$ нет: это картинка MNIST, развёрнутая в 784 числа.

Так же читается и форма тензора: $X \in \R^{m \times n}$ — матрица, элемент множества всех таблиц $m$ на $n$.

Множество всех подмножеств

$2^A = \mathcal{P}(A) = \{S : S \subseteq A\}$

Элементы $2^A$ — это сами множества. Для $A = \{1, 2\}$:

$2^A = \{\emptyset,\; \{1\},\; \{2\},\; \{1,2\}\}$

Обозначение $2^A$ объясняется мощностью: $|2^A| = 2^{|A|}$. Каждое подмножество однозначно задаётся битовой маской длины $|A|$ — для каждого элемента решаем, брать его или нет. Буквально itertools.product([0,1], repeat=len(A)).

Заметьте: $\emptyset$ и само $A$ всегда входят в $2^A$.

Где это встретится: в блоке 3 вероятность определяется как функция на множестве подмножеств $\Omega$ — событие и есть подмножество исходов.

Индексированные семейства

Запись $\{A_i\}_{i \in I}$ означает: у нас есть множество индексов $I$, и каждому $i \in I$ сопоставлено множество $A_i$. Это словарь, где ключи — индексы.

Зачем нужна отдельная нотация, если можно просто перечислить? Затем, что $I$ может быть бесконечным. Тогда объединение и пересечение записываются так:

$$\bigcup_{i \in I} A_i = \{x : \exists i \in I,\; x \in A_i\}, \qquad \bigcap_{i \in I} A_i = \{x : \forall i \in I,\; x \in A_i\}$$

Обратите внимание на квантор в каждой формуле: объединение — это «существует хотя бы один», пересечение — «для всех». Та же пара or / and, что и в уроке про операции, только теперь по произвольному числу аргументов.

Разбиение

Семейство $\{A_i\}_{i \in I}$ называется разбиением множества $A$, если:

1. все $A_i$ непусты,
2. они попарно не пересекаются: $A_i \cap A_j = \emptyset$ при $i \ne j$,
3. в объединении дают всё: $\bigcup_i A_i = A$.

Разбиение — это ровно то, что делает groupby: каждый элемент попадает в одну и только одну группу. В следующем уроке выяснится, что разбиения и отношения эквивалентности — это одно и то же, увиденное с двух сторон.

Где это встретится дальше

• $\R^n$, $\R^{m \times n}$ — весь блок 1
• $2^\Omega$ — определение вероятности, блок 3
• $\bigcup$ и $\bigcap$ по бесконечному семейству — формулировки в теории меры
• разбиение — формула полной вероятности