Тождество максимумов и минимумов

Пусть ${\displaystyle (X;\leqslant )}$ — частично упорядоченное множество.

Элемент ${\displaystyle a\in X}$ называется минимальным элементом множества ${\displaystyle X}$, если не существует ни одного элемента ${\displaystyle x\in X}$ такого, что ${\displaystyle x<a}$.

Это равносильно условию: ${\displaystyle x\leqslant a}$. Из этого следует: ${\displaystyle x=a}$.

${\displaystyle \forall a\in X\;(x\leqslant a\Rightarrow x=a).}$

Записывается как: ${\displaystyle a=\min X}$.

Элемент ${\displaystyle a\in X}$ называется максимальным элементом множества ${\displaystyle X}$, если не существует ни одного элемента ${\displaystyle x\in X}$ такого, что ${\displaystyle x>a}$ (из ${\displaystyle x\geqslant a}$ следует ${\displaystyle x=a}$).

${\displaystyle \forall a\in X\;(x\geqslant a\Rightarrow x=a)}$.

Записывается как: ${\displaystyle a=\max X}$^[2].

Пусть ${\displaystyle x_{1},\ldots ,x_{n}}$ — произвольные действительные числа.

Тогда тождество утверждает:

${\displaystyle \max(x_{1},\ldots ,x_{n})=\sum _{i}x_{i}-\sum _{i<j}\min(x_{i},x_{j})+\sum _{i<j<k}\min(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\min(x_{1},\ldots ,x_{n})}$.

Аналогичное соотношение возникает, если поменять местами минимумы и максимумы:

${\displaystyle \min(x_{1},\ldots ,x_{n})=\sum _{i}x_{i}-\sum _{i<j}\max(x_{i},x_{j})+\sum _{i<j<k}\max(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\max(x_{1},\ldots ,x_{n})}$.

Докажем, например, первое из приведённых соотношений.

Заметим, что если заменить: ${\displaystyle x\mapsto x+a}$,

где ${\displaystyle a}$ — произвольное число, то обе части доказываемого соотношения также изменятся на ${\displaystyle a}$.

Действительно, левая часть:

${\displaystyle \max(x_{1}+a,\ldots ,x_{n}+a)=\max(x_{1},\ldots ,x_{n})+a}$.

Правая часть:

${\displaystyle {\begin{aligned}\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,&\min(x_{i_{1}}+a,\ldots ,x_{i_{k}}+a)=\\&=\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,\min(x_{i_{1}},\ldots ,x_{i_{k}})+a\sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1\end{aligned}}}$.

Второе слагаемое в точности равно ${\displaystyle a}$ в силу известного свойства биномиальных коэффициентов:

${\displaystyle \sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}=1}$.

Заменим теперь все ${\displaystyle x_{i}}$ на ${\displaystyle x'_{i}=x_{i}+a}$,

где ${\displaystyle a=-\min(x_{1},\ldots ,x_{n})}$.

В силу вышеизложенных соображений соотношение для набора ${\displaystyle x'_{i}}$ будет выполнено тогда и только тогда, когда выполнено соотношение для набора ${\displaystyle x_{i}}$.

Но при этом все ${\displaystyle x'_{i}\geq 0}$ и одно или несколько чисел из набора ${\displaystyle x'_{i}}$ равны ${\displaystyle 0}$.

Если все ${\displaystyle x'_{i}=0}$, то соотношение, очевидно, выполнено.

Рассмотрим случай, когда не все ${\displaystyle x'_{i}=0}$.

Пусть для определённости ${\displaystyle x'_{1},\ldots ,x'_{m}>0}$, а ${\displaystyle x'_{m+1}=\ldots =x'_{n}=0}$. Тогда все нулевые ${\displaystyle x'_{i}}$ можно исключить из равенства, которое превращается в:

${\displaystyle \max(x'_{1},\ldots ,x'_{m})=\sum _{i}x'_{i}-\sum _{i<j}\min(x'_{i},x'_{j})+\sum _{i<j<k}\min(x'_{i},x'_{j},x'_{k})+\ldots +(-1)^{m-1}\,\min(x'_{1},\ldots ,x'_{m})}$.

Таким образом, мы свели соотношение для ${\displaystyle n}$ чисел к аналогичному соотношению для меньшего количества ${\displaystyle m<n}$ чисел. Отсюда в силу принципа математической индукции следует, что исходное соотношение верно для любого натурального ${\displaystyle n}$.

Как частный случай тождества можно рассматривать формулу включений-исключений:

${\displaystyle \max(a_{1},\ldots ,a_{n})=\sum _{i}a_{i}-\sum _{i<j}\min(a_{i},a_{j})+\ldots +(-1)^{n-1}\,\min(a_{1},\ldots ,a_{n}).}$

Это соотношение справедливо для произвольных чисел ${\displaystyle a_{i}}$.

В частном случае, когда: ${\displaystyle a_{i}\in \{0,1\}}$, получают одну из форм принципа включений-исключений.

Если положить: ${\displaystyle a_{i}=\mathbf {1} _{A_{i}}(x)}$, где ${\displaystyle x}$ — произвольный элемент из ${\displaystyle U}$, то соотношение для индикаторных функций множеств следующее^[3]: