Изменения

Тогда <tex> [i: j]f(a)_i =</tex> <br> <tex> = [i: j](f(a_0), \dots, f(a_{n-1}))_i </tex> (по введенному нами определению)<br> <tex> = f([i: j](a))_i = f([i: j](a)_i) </tex> (по определению компаратора и по введенному нами определению)<br> <tex> = \min(f(a_i), f(a_j)) </tex> (по определению компаратора)<br> <tex> = f([i: j](a)_i) </tex> (по определению компаратора)<br> <tex> = f(\min(a_i, a_j)) </tex> (по определению компаратора и по уже доказанной лемме). То есть в результате <tex> i </tex>-й элемент Таким образом, результат не зависит от порядка применения компаратора <tex> [iтого, что мы сделаем с отдельным компаратором сначала: j] </tex> и функции <tex> f </tex>применим монотонную функцию или пропустим его через сеть. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </tex> для всех компараторов в сети, то есть лемма доказана.